Содержание этого параграфа изложим, следуя [24].
Будем рассматривать формулы, содержащие только логические операции &, Ú, Ø. Символы & и Ú называются двойственными друг другу.
Формула A* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, Ú на двойственные. Например, формула X1&(X2ÚØX1) двойственна формуле X1Ú(X2&ØX1). Заметим, что A* содержит те же высказывательные переменные, что и A.
Очевидно, что (A*)* совпадает с A.
Пусть <X1, X2,...,Xn> - некоторый упорядоченный список высказывательных переменных. Пусть <s1, s2,...,sn> - соответствующий список распределения истинностных значений для этих переменных (каждое si, i=1,2,..,n, есть И или Л). Список истинностных значений <t1, t2,...,tn> назовем двойственным к списку <s1, s2,...,sn>, если <t1, t2,...,tn> получается из <s1, s2,...,sn> заменой всех И на Л и всех Л на И.
Лемма 2.3. Пусть A -формула и <X1, X2,...,Xn> - высказывательные переменные этой формулы. Пусть <s1, s2,...,sn> - соответствующий список распределения истинностных значений для этих переменных. Тогда A принимает значение И при этих значениях переменных тогда и только тогда, когда A* принимает значение Л на списке истинностных значений <t1, t2,...,tn>, двойственном к списку <s1, s2,...,sn>.
Доказательство. Проведем математическую индукцию по числу k логических связок в формуле A.
Базис индукции. При k=0 формула A совпадает с одной из высказывательных переменных Xi и A* также совпадает с этой переменной. Поэтому формулы A и A* имеют противоположные истинностные значения si и ti и утверждение леммы выполнено.
Индуктивный переход. Пусть утверждение леммы справедливо при числе логических операций, меньшем k. Докажем, что оно остается справедливым и при числе операций, равном k. Рассмотрим три различных случая, в зависимости от того какой вид имеет формула A.
1. Пусть формула A совпадает с формулой ØB. Тогда A* совпадает с формулой Ø (B*). Пусть <s1, s2,...,sn> - некоторый список истинностных значений. Истинностное значение формулы B на этом списке противоположно истинностному значению формулы A на этом же списке. Так как количество логических операций в формуле B меньше k, то значение формулы B* на двойственном списке <t1, t2,...,tn> противоположно значению B на списке <s1, s2,...,sn>. Следовательно, значение Ø (B*) на списке <t1, t2,...,tn> совпадает со значением формулы B на списке распределения истинностных значений <s1, s2,...,sn>. Отсюда сразу получаем искомое утверждение для формулы A.
2. Пусть формула A имеет вид B&C. Из определения операции двойственности сразу следует, что A* = (B&C)* = B* Ú C*. Для распределения истинностных значений <s1, s2,...,sn> формула A истинна тогда и только тогда, когда формулы B и C также истинны. Поскольку B и C имеют логических операций меньше k, то значения формул B* и C* ложны на двойственном наборе истинностных значений <t1, t2,...,tn>. На этом же наборе ложна и формула B*ÚC* = A*. Эти рассуждения показывают справедливость искомого утверждения в данном случае.
3. Пусть формула A имеет вид BÚC. Из определения операции двойственности сразу следует, что A* = (BÚC)* = B* & C*. Для распределения истинностных значений <s1, s2,...,sn> формула A ложна тогда и только тогда, когда формулы B и C также ложны. Поскольку B и C имеют логических операций меньше k, то значения формул B* и C* истинны на двойственном наборе истинностных значений <t1, t2,...,tn>. На этом же наборе истинна и формула B*&C* = A*. Тем самым мы получаем справедливость искомого утверждения и в данном случае.
Разбор всех случаев позволил нам закончить индуктивный переход и убедиться в справедливости леммы.
Теорема 2.3. (принцип двойственности) Если A º B, то A* º B*.
Доказательство. Пусть <t1, t2,...,tn> - произвольный набор распределения истинностных значений для истинностных переменных в формуле A*. Тогда истинностное значение A* противоположно истинностному значению A (а, следовательно, и B) на двойственном списке <s1, s2,...,sn>. С другой стороны, значение формулы B* на списке истинностных значений <t1, t2,...,tn> противоположно истинностному значению B на списке <s1, s2,...,sn>. Следовательно, значения формул A* и B* при произвольном распределении истинностных значений переменных совпадают. Что и требовалось доказать.
Принцип двойственности можно использовать для нахождения новых равносильностей. Например, используя следующий частный случай дистрибутивности & относительно Ú
X & (Y Ú Z) º (X&Y)Ú(X&Z),
получаем равносильность
X Ú (Y & Z) º (XÚY)&(XÚZ).
Заметим, что в силу ассоциативности операций & и Ú, как бы мы не расставляли скобки в выражениях A1&A2&…&An и A1ÚA2Ú…ÚAn (n>3), всегда будем приходить к равносильным формулам. Допуская некоторую вольность речи, каждое из этих выражений будем считать формулами и называть соответственно многочленной конъюнкцией и дизъюнкцией формул A1, A2,…, An. Для этих формул, используя, например, индукцию по max(k, n), нетрудно получить равносильности, выражающие обобщенную дистрибутивность (для простоты записи, положим k=2, n=3):
(A1ÚA2) & (B1ÚB2ÚB3) º (A1&B1) Ú (A1&B2) Ú (A1&B3) Ú
(A2&B1) Ú (A2&B2) Ú (A2&B3),
(A1&A2) Ú (B1&B2&B3) º (A1ÚB1) & (A1Ú B2) & (A1ÚB3) &
(A2ÚB1) & (A2ÚB2) & (A2ÚB3).
Точно также получаем обобщенные законы де Моргана:
Ø( A1&A2&…&An) º ØA1ÚØA2Ú…ÚØAn,
Ø( A1ÚA2Ú…ÚAn) º ØA1&ØA2&…&ØAn.
Определим теперь некоторые канонические виды формул.
Формула называется элементарной конъюнкцией, если она является конъюнкцией (быть может, одночленной) переменных и отрицаний переменных. Например, формулы ØX2, X1, X1&X2, X1&ØX2&ØX1&X4 являются элементарными конъюнкциями.
Говорят, что формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (быть может, одночленной) элементарных конъюнкций. Например, формулы ØX2, X1, X1&X2, X1&ØX2&ØX1&X4, (X1&X2)Ú( X1&ØX2&ØX1&X4)&X1 находятся в ДНФ.
Теорема 2.4 (о приведении к ДНФ). Для любой формулы A можно найти такую формулу B, находящуюся в ДНФ, что AºB. Формула B называется дизъюнктивной нормальной формой формулы A.
Доказательство теоремы распадается на три этапа:
1-ый этап. Для формулы A строим такую формулу A1, что AºA1 и в A1 не содержатся символы ~ и É (теорема 2.2).
2-ой этап. Докажем теперь, что для формулы A1 можно найти формулу A2 такую, что A1 º A2 и в A2 отрицание находится только перед переменными. Такая формула называется формулой с "тесными" отрицаниями. Докажем это утверждение математической индукцией по числу n логических операций формулы A1.
Базис индукции. Если n=0, то A1 есть какая-то переменная Xi. В качестве A2 нужно взять Xi.
Индуктивный переход. Пусть утверждение выполняется для всех формул A1 с числом связок меньше n. Пусть в формуле A1 содержится точно n логических связок. Рассмотрим следующие случаи:
1) A1 имеет вид B1ÚC1. Тогда в B1, C1 логических символов меньше, чем n. Поэтому существуют формулы B2, C2 такие, что B1ºB2, C1ºC2 и в B2 и C2 отрицание встречается только перед переменными. Ясно, что B2ÚC2 равносильна A1 и является формулой с "тесными" отрицаниями;
2) A1 имеет вид B1&C1. Доказательство аналогично предыдущему случаю;
3) A1 имеет вид ØØB1. Тогда A1º B1 в B1 логических символов меньше, чем n. Поэтому к B1 применимо индуктивное предположение;
4) A1 имеет вид Ø(B1ÚC1). Тогда A1ºØB1&ØC1 и в ØB1, ØC1 логических символов меньше, чем n. Поэтому существуют такие формулы B2, C2, что ØB1ºB2, ØC1ºC2 и в B2 и C2 отрицание встречается только перед переменными. Ясно, что A1ºB2&C2 и B2&C2 является формулой с "тесными" отрицаниями;
5) A1 имеет вид Ø(B1&C1). Тогда A1ºØB1ÚØC1, и далее поступаем как в предыдущем случае.
При практическом преобразовании встречающиеся в формуле отрицания просто передвигают к переменным, используя законы де Моргана и уничтожая пары стоящих рядом отрицаний, если таковые встречаются.
Пример 2.5. Преобразуем к формуле с "тесными" отрицаниями:
Ø(ØØ(X1&ØX2)Ú(X2&ØX1)) º ØØØ(X1&ØX2)&Ø(X2&ØX1) º
Ø(X1&ØX2)&(ØX2ÚØØX1) º (ØX1ÚØØX2)&(ØX2ÚX1) º
(ØX1ÚX2)&(ØX2ÚX1).
3-ий этап. Полученная формула A2 построена из переменных и их отрицаний с помощью многочленных конъюнкций и дизъюнкций. Применив теперь обобщенную дистрибутивность & относительно Ú, последовательно преобразуем формулу (аналогично приведению алгебраического выражения, составленного из переменных, с помощью сложений и умножений, к виду многочлена). Заметим, что при этом Ú аналогично сложению, а & - умножению. Полученная в результате преобразований формула B будет удовлетворять требованиям теоремы.
Пример 2.6. Применим преобразования третьего этапа к формуле с "тесными" отрицаниями, полученной в примере 2.5:
(ØX1ÚX2)&(ØX2ÚX1) º (ØX1&ØX2)Ú(ØX1&X1)Ú(X2&ØX2)Ú(X2&X1).
Говорят, что формула A находится в конъюнктивной нормальной форме (КНФ), если формула A* определена (т. е. в A нет символов ~ и É) и находится в ДНФ.
КНФ можно дать и другое равносильное определение. Формулу называют элементарной дизъюнкцией, если она является дизъюнкцией (возможно, одночленной) переменных и отрицаний переменных. Формула находится в КНФ, если она является конъюнкцией (возможно, одночленной) элементарных дизъюнкций.
Теорема 2.5 (о приведении к КНФ). Для любой формулы A можно найти такую формулу B, что В находится в КНФ и AºB. Формула B называется конъюнктивной нормальной формой формулы A.
Первое доказательство. Пусть A º A1 и A1 не содержит символов ~, É. Пусть B1 - дизъюнктивная нормальная форма формулы A*1. Тогда B*1 находится в КНФ и, кроме того, по принципу двойственности B*1 º (A*1)* º A1 º A. Значит, B*1 удовлетворяет требованиям теоремы.
Второе доказательство. Применив первые два этапа из доказательства теоремы 2.6 о ДНФ, получим формулу A2, равносильную A, не содержащую символов ~, É и содержащую отрицания только перед переменными. Преобразуем теперь A2 как алгебраическое выражение, считая на этот раз & аналогом сложения, а Ú - аналогом умножения и применяя дистрибутивность Ú относительно &. Приведение формулы A2 к виду многочлена даст на этот раз КНФ.
Пример 2.7. Приведем к КНФ формулу:
(X1&X2)~(ØX1&X3) º
((X1&X2)&(ØX1&X3))Ú(Ø(X1&X2)&Ø(ØX1&X3)) º
(X1&X2&ØX1&X3)Ú((ØX1ÚØX2)&(ØØX1ÚØX3)) º
(X1&X2&ØX1&X3)Ú((ØX1ÚØX2)&(X1ÚØX3)) º
(X1ÚØX1ÚØX2)&(X1ÚX1ÚØX3)&(X2ÚØX1ÚØX2 )&(X2ÚX1ÚØX3)&
(ØX1ÚØX1ÚØX2)&(X1ÚX1ÚØX3)&(X3ÚØX1ÚØX2)&(X3ÚX1ÚØX3).
Заметим, что первое преобразование основано на равносильности 16.
Нетрудно видеть, что ДНФ и КНФ не являются однозначно определенными. Формула может иметь несколько равносильных друг другу ДНФ и КНФ.