Конъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.
Определение 5. Дизъюнкция
(4.2)
называется элементарной дизъюнкцией или дизъюнктом.
Как и в случае конъюнктов, существует 2n различных элементарных дизюъюнкций от n переменных. При этом значение элементарной дизюъюнкции вида (4.2) равно 0 тогда и только тогда, когда xi=1-si для всех i=1, 2, …, n.
Конъюнкция вида (4.1) называется также конституентой нуля.
Определение 6. Конъюнктивной нормальной формой формулыА (КНФА) называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.
Пример 4.2. Для формулы А= ®( у) имеем, например, КНФА~хÚу.
Как и в случае ДНФ, КНФ формулы неединствен. Их можно составить сколько угодно. К КНФ формулы можно прийти по следующему алгоритму:
I шаг: Приведение операций |, ¯, ®, «, Å к операциям &, Ú или их отрицаниям:
1. Если в формуле участвуют операции |, ¯, и Å, то от них с помощью операции отрицания переходим к отрицанию соответственно конъюнкций, дизъюнкций или эквиваленций.
2. Если в формуле участвует операция «, то от неё с помощью закона т) упражнения 3.2 переходим к операции ®.
3. Если в формуле участвует операция ®, то от неё с помощью закона п) упражнения 3.2 преходим к операции Ú.
II шаг. Отнесение отрицаний к пропозициональным переменным.
4. Если в формуле участвуют отрицания конъюнкций или дизъюнкций, то с помощью законов де Моргана отрицания приводим к пропозициональным переменным.
5. Если в формуле участвует двойное отрицание, то с помощью закона снятия двойного отрицания они убираются.
III шаг. Получение КНФ.
С помощью свойства дистрибутивности Ú относительно & все подформулы вида AÚ(B1&B2&…&Bk) приводим к подформулам вида (AÚB1)&(AÚB2)&…&(AÚBk) до тех пор, пока не получим конъюнкцию элементарных дизъюнкций.
Таким образом, мы доказали, что любая формула эквивалентна некоторой КНФ.
Очевидно, А&А&…&А~А, и поэтому в КНФ элементарная дизъюнкция может повторяться сколько угодно раз. В результате мы приходим к тому, КНФ формулы можно построить сколько угодно.
Потребуем, чтобы КНФ удовлетворяла следующим четырём свойствам совершенства:
1. Каждый дизъюнкт КНФ формулы содержит все переменные или их отрицания, входящие в формулу.
2. Все дизъюнкты, входящие в КНФ, различны.
3. Ни один дизъюнкт, из которых состоит КНФ, не содержит одновременно переменную и её отрицание.
4. Ни один дизъюнкт не содержит одну же литеру два и более раз.
Определение 7. КНФ формулы, удовлетворяющей всем условиям совершенства, называется совершенной конъюнктивной нормальной формой данной формулы (СКНФ).
Для того, чтобы получить СКНФ формулы А, достаточно сначала формулу привести к КНФА, а затем применить к полученной КНФ эквивалентные преобразования следующих видов, позволяющие последовательно получать эквивалентную КНФА, удовлетворяющие всем условиям совершенства:
1. Если в КНФА какой-либо дизъюнкт В не содержит переменную хi или её отрицание, то используя равносильности B~ВÚ(хi& )~ ~(ВÚхi)&(BÚ ), дизъюнкт В заменяем на два дизъюнкта (ВÚхi) и (BÚ ), каждая из которых содержит хi или её отрицание .
2. Если в КНФА входят два или более одинаковых дизъюнкта B, то лишние отбрасываем, пользуясь равносильностью B&B&…&B~B.
3. Если некоторый дизъюнкт В, входящий в КНФА, содержит переменную хi и её отрицание , то В~1, и в силу эквивалентности C&1~C, В исключаем из КНФА.
4. Если некоторый дизъюнкт, входящий в КНФА, содержит одну и ту же литеру дважды или более, то, пользуясь равносильностью Ú Ú…Ú ~ , лишние отбрасываем.
Упражнение 4.3. С помощью эквивалентных преобразований привести формулы упражнения 3.4 к СКНФ.
Решение. з) Приведём формулу к КНФ:
(x| )®(zÅ ) ( )Ú(zÅ ) (x& )Ú
(x& )Ú (x& )Ú
(x& )Ú (x& )Ú
(x& )Ú( (x& )Ú )
(x&( Ú ))Ú ) (x&(( Úу)& ))Ú )
(x& )Ú ) (xÚz)& & &
(xÚz)& &
Получили КНФ формулы. Теперь преобразуем КНФ по алгоритму получения всех условий совершенства:
(xÚyÚz)&(xÚ Úz)&(xÚ )& &
(xÚyÚz)&(xÚ Úz)&(xÚ Úz)&(xÚ Ú )& & &
(xÚyÚz)&(xÚ Úz)&(xÚ Ú )& &
á(1) Одновременно заменили | на отрицание операции &,и ® - на отрицание Ú.
(2) Одновременно применили закон двойного отрицания и Å заменили на « и его отрицание.
(3) Операцию « заменили на ®.
(4) Применили закон де Моргана.
(5) Заменили ® на Ú.
(6), (7) Одновременно применили законы де Моргана и снятия двойного отрицания.
(8) Воспользовались ассоциативностью и коммутативностью Ú.
(9) 1-й и 2-й конъюнкты объединили в один с помощью дистрибутивности & относительно Ú.
(10) К подформуле Ú применили закон дистрибутивности.
(11) Воспользовались тем, что Úу~1.
(12) Применили сложную дизъюнкцию относительно Ú.
(13) Применили законы исключённого третьего и идемпотентности.
(14) В 1-й и 2-й дизъюнкты добавили недостающие литеры и разбили их по два дизъюнкта каждую (1-я операция приведения к СКНФ).
(15) Операцию, аналогичную (14) проделали с 3-м и 4-м дизъюнктами.
(16) Опустили лишние дизъюнкты.
СДНФ формулы существует и единственна.
Существование СКНФ для любой формулы вытекает из алгоритма её построения.
Другой способ построения СКНФА основывается на следующей эквиваленции:
A(х1, х2, …, хn)~ .
Другими словами, формула A(х1, х2, …, хn) в своей СДНФ содержит те и только те конъюнкты вида (4.2), значения которых равны 0 при xi=1-si для всех i=1, 2, …, n. Например, для формулы А= ®( у), состоящей из двух переменных, можно составить всевозможные конъюнкты ху, х , у и . Из них значение 0 принимают только при наборе (х, у)=(0, 0), (что можно проверить, непосредственно составив таблицу истинности). Поэтому, СКНФА~хÚу.
Таким образом, СКНФA(х1, х2, …, хn)= . Поэтому для нахождения СКНФ формулы достаточно: 1) построить её таблицу истинности; 2) выбрать те наборы значений переменных (которые входят в формулу), при которых формула принимает значение 0; 3) составить соответствующие им дизъюнкты и 4) составить из них КНФ.
Упражнение 4.4. С помощью таблиц истинности привести формулы упражнения 3.4 к СКНФ.
Решение. д). 1. Составим таблицу истинности формулы (она у нас уже составлена, см. решение задачи д) упражнения 4.2):
2. Выберем те наборы значений переменных, при которых формула принимает значение 0: (0, 0, 1), (0, 1, 1).
3. Составим соответствующие им дизъюнкты: xÚyÚ , xÚ Ú .
4. Составим из них КНФ: (xÚyÚ )&(xÚ Ú ).
Ответ: д) СКНФA=(xÚyÚ )&(xÚ Ú ).
4.3. Принцип двойственности. Операция & называется двойственнойк Ú, Ú - двойственной к &. Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания.
Определение 8. Формула A* называется двойственной кА, если A* получается из A заменой в ней каждой операции на двойственную.
Очевидно, если A* - двойственна к A, то A - двойственна к A*. Поэтому говорят о взаимно двойственных формулах.
Очевидно также, что если формулы А и В равносильны, то равносильны и двойственные им А* и В*. Кроме того, если A*(х1, х2, …, хп) - двойственна к A(х1, х2, …, хп), то ~A*(х1, х2, …, хп). Отсюда следует, что таблица истинности формулы A*, двойственной к А, получается из таблицы истинности А заменой всех 0 на 1 и всех 1 на 0.
Определение 9. Формула А называется самодвойственной, если A*~A.
Из определения следует, что формула A самодвойственна, если при замене 0 на 1, и 1 на 0 её таблица истинности не меняется (естественно, меняются между собой только строки). Очевидно, формула самодвойственна тогда и только тогда, когда на всех противоположных значениях переменных формула принимает противоположные значения.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|