Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Пример КНФ: ()()().
Пусть ДНФ 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) .
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)}.
Всего наборов функции четырех переменных 24=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) ;
б) f (x, y, z) ; д) f (x, y, z) .
в) f (x, y, z) ;
5. Привести формулы к ДНФ:
а) (, , ) ;
б) (, , ) ;
в) (, , ) ;
г) (, , ) .
6. Для функций (, , ), заданных в упражнении 5:
1) получить КНФ, используя правило приведения ДНФ к КНФ;
2) найти СДНФ и СКНФ, используя табличное представление функции.
7. Подтвердить самодвойственность функции f (x, y, z)= , используя принцип двойственности в булевой алгебре.
8. Для функции (, , ) найти ДНФ двойственной функции f *(, , ), исходя из:
1) определения двойственной функции;
2) принципа двойственности в булевой алгебре:
а) (, , ) ;
б) (, , ) ;
в) (, , ) .
9. Методом эквивалентных преобразований подтвердить справедливость правил 9, 12 §1.2 логически правильных рассуждений.
10. Убедиться в неправильности рассуждений а)–в), приведенных в §1.2:
а) стандартным методом;
б) методом эквивалентных преобразований.