Приведение к конъюнктивной нормальной форме

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Пример КНФ: ()()().

Пусть ДНФ F имеет вид F = , где – элементарные конъюнкции.

Процедура приведения ДНФ к КНФ:

1. Применить к F правило двойного отрицания F = и привести к ДНФ , где – элементарные конъюнкции. Тогда

F = = = .

2. С помощью правил де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции . Тогда

F = = × ×...× = × ×...×

5. Двойственность. Функция f *(,..., ) называется двойственной к функции f (,..., ), если f *(,..., )= (,..., ).

Отношение двойственности между функциями симметрично, т.е. если f * двойственна к f, то f двойственна к f *:

(,..., )= (,..., )= f *(,..., ).

Функция, двойственная к самой себе, называется самодвойственной.

Принцип двойственности: если в формуле F, представляющей функцию f, все знаки функций заменить соответственно на знаки двойственных функций, то полученная формула F * будет представлять функцию f *, двойственную f.

Принцип двойственности в булевой алгебре: если в формуле F, представляющей функцию f, все конъюнкции заменить на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F *, представляющую функцию f *, двойственную f.

Пример 1. Доказать справедливость обобщенного склеивания методом эквивалентных преобразований.

Выполним эквивалентные преобразования:

×1 .

Пример 2. Получить СДНФ функции, используя эквивалентные соотношения: f (x, y, z, u)= xy Ú xz Ú zu.

f(x, y, z, u)

= .

Пример 3. Упростить булевы формулы:

а) (, , ) ;

б) f (x, y, z) .

а) (, , )

×1 ;

б) f (x, y, z)

0× Ú 0× z Ú x ×0Ú xyz Ú Ú xzz .

Пример 4. Представить булеву формулу в базисе {&,Ø} и {Ú,Ø}.

а) ;

б) .

Пример 5. Упростить СДНФ функции

f (x, y, z, u)

Для эффективного упрощения СДНФ используем метод Блейка-Порецкого. Метод заключается в попарном склеивании всех элементарных конъюнкций СДНФ между собой, а также полученных в процессе склеивания элементарных конъюнкций меньшего числа переменных и затем – поглощении конъюнкциями меньшего числа переменных конъюнкций большего числа переменных.

Рассмотрим метод Блейка-Порецкого “в действии”, для чего пронумеруем элементарные конъюнкции СДНФ:

1 2 3 4 5 6 7

Выполним все возможные попарные склеивания элементарных конъюнкций в СДНФ (под результатом склеивания проставим номера склеиваемых конъюнкций):

1,6 1,7 2,3 2,4 2,5 3,7 4,6 4,7 5,6

Выполним все возможные попарные склеивания полученных элементарных конъюнкций трех переменных:

1,6 1,7 2,3 2,4 2,4 2,5

4,7 4,6 4,7 3,7 5,6 4,6

Очевидно, что дальнейшее склеивание в данном примере невозможно. Объединим символом Ú все полученные дизъюнкции элементарных конъюнкций.

Таким образом, в результате попарного склеивания получили:

f (x, y, z, u)

Выполним теперь в этом выражении поглощение, в результате чего получим: f (x, y, z, u)=

Пример 6. Привести к ДНФ формулу:

f (x, y, z)= .

f (x, y, z) .

Пример 7. Привести формулу к КНФ:

f (x, y, z) .

Пример 8. Получить СКНФ функции f (x, y, z, u) из примера 2.

В примере 2 для заданной функции f (x, y, z, u)= xy Ú xz Ú zu была получена СДНФ:

f (x, y, z, u) .

Воспользуемся этими данными для получения СКНФ, для чего определим единичное множество функции f (x, y, z, u), т.е. множество наборов, на которых f =1:{(1111),(1101),(1110),(1100),(1011),(1010), (0111),(0011)}.

Всего наборов функции четырех переменных 2⁴=16. Определим теперь нулевое множество для f (x, y, z, u), т.е. множество наборов, на которых f =0: {(0000),(0001),(0010),(0100),(0101),(0110),(1000), (1001)}. Отсюда по правилу построения СКНФ из нулевого множества функции:

f (x, y, z, u)

Пример 9. Доказать справедливость принципа двойственности в булевой алгебре, исходя из общего принципа двойственности.

Найдем для каждой операции булевой алгебры (; &, Ú, Ø) двойственные им операции.

а) Пусть f (x, y)= x × y. Тогда f *(x, y) x Ú y.

б) Пусть f (x, y)= x Ú y. Тогда f *(x, y) x × y.

в) Пусть f (x) . Тогда f *(x) .

Таким образом, конъюнкция двойственна дизъюнкции, дизъюнкция – конъюнкции, а отрицание самодвойственно.

Наконец, константы 0 и 1 принадлежат множеству логических функций , поэтому 0 и 1 могут содержаться в булевой формуле и являются двойственными друг к другу: если (,..., )=0, то f *(,..., ) (,..., ) 1. Аналогично, если f =1, то f *=0.

Отсюда следует справедливость принципа двойственности в булевой алгебре.

Пример 10. Пусть f (x, y, z) . Найти ДНФ двойственной функции f *(x, y, z), исходя из:

а) определения двойственности функции;

б) принципа двойственности в булевой алгебре.

а) f *(x, y, z) xz;

б) f *(x, y, z) xz.

Вопросы для самопроверки и упражнения.

1. Доказать методом эквивалентных преобразований справедливость соотношений п.11, п.12, п.13.

2. Упростить СДНФ импликации и функции Шеффера, используя эквивалентные соотношения.

3. Логическая функция (, , ) представлена формулой (, , ) . Упростить формулу и получить СДНФ, используя:

а) табличное представление функции f;

б) расщепление (обратное склеивание).

4. Для функций, заданных в виде ДНФ, получить СДНФ, используя эквивалентные преобразования, и упростить СДНФ, использую метод Блейка-Порецкого, описанный в примере 5.

а) f (x, y, z) ; г) f (x, y, z) ;