Эквивалентные преобразования. Сокращенные ДНФ. Простая импликанта. Тупиковая ДНФ

Эквивалентные преобразования – это такие преобразования, использующие эквивалентные соотношения и правило замены. Эквивалентные преобразования являются средством доказательства эквивалентности формул, как правило, более эффективным, чем их вычисление на наборах значений переменных.

1. Свойства констант:

2. Свойство двойного отрицания:

3. Идемпотентность (отсутствие степеней и множителей):

а) х Ù х = х; б) х Ú х = х.

4. Закон противоречия:

х Ù`х = 0.

5. Закон «исключенного третьего»:

х Ú`х = 1.

6. Ассоциативность:

а) х₁ Ù (х₂ Ù х₃) = (х₁ Ù х₂) Ù х₃; б) х₁ Ú (х₂ Ú х₃) = (х₁ Ú х₂) Ú х₃.

7. Коммутативность:

а) х₁ Ù х₂ = х₂ Ù х₁; б) х₁ Ú х₂ = х₂ Ú х₁.

8. Дистрибутивность конъюнкции относительно дизъюнкции:

х₁ Ù (х₂ Ú х₃) = (х₁ Ù х₂) Ú (х₁ Ù х₃).

9. Дистрибутивность дизъюнкции относительно конъюнкции:

х₁ Ú (х₂ Ù х₃) = (х₁ Ú х₂) Ù (х₁ Ú х₃).

10. Правила де Моргана:

11.

12.

13.

Определение. Говорят, что булева функция имеет сокращенную дизъюнктивную

нормальную форму, если она равна дизъюнкции всех своих простых импликант.

Сокращенная форма характеризуется тем, что ее члены самые короткие, из

нее уже нельзя

Определение. Булева функция g(x) называется импликантой булевой

функции f(x), если для любого набора аргументов, на которых

g(x)=1, f(x) также равна единице.

P.S.: Простейшими примерами импликант могут служить элементарные

конъюнкции, входящие в ДНФ данной функции. Произвольная дизъюнкция

этих термов также является импликантой функции.

Определение. Простой (первичной) импликантой булевой функции называется

такая импликанта функции, у которой никакая ее собственная часть уже не является

импликантой этой функции.

P.S.: Под собственной частью импликанты понимается новая импликанта, полученная из исходной, путем вычеркивания произвольного числа букв.

Определение. Если из сокращенной формы исключить все возможные члены, не

нарушая определения функции, то получится тупиковая дизъюнктивная

нормальная форма.

Тупиковых форм у булевой функции может быть несколько.

Определение. Тупиковая форма, содержащая наименьшее число членов, называется

кратчайшей дизъюнктивной нормальной формой.

P.S.: Кратчайшая и тупиковые формы в общем случае не совпадают.