§ 9. Дизъюнктивные и конъюнктивные нормальные формы
Дизъюнктивной нормальной формой (д.н.ф.) называется дизъюнкция элементарных произведений. Одно элементарное произведение тоже будем считать д.н.ф. Примеры д.н.ф.:
Теорема 3.10. Для каждой формулы существует равносильная ей д.н.ф. (не единственная).
Доказательство.Ранее было показано, что для любой формулы существует равносильная ей формула, содержащая только связки ¬ , &, ∨, причем связка ¬ относится только к отдельным переменным. Еще раньше было замечено, что с формулой, содержащей связки &, ∨, можно проводить операции раскрытия скобок (см. законы дистрибутивности). В результате получаем дизъюнкцию элементарных произведений, т.е. д.н.ф.
Пример. Пусть задана формула $¬(x≡y)\&z$. Исключим связку ≡, затем ⇒:
$¬ ((x⇒y)\&(y⇒x))\&z$
$¬((¬ x∨y)\&(¬ y∨x))\&z$
Теперь добьемся, чтобы относилась только к переменным:
$(x\&¬ y∨y\&¬ x)\&z$
Раскрыв скобки, получим x&¬y&z∨y&¬x&z. Последнее и есть д.н.ф. Полученная д.н.ф., очевидно, равносильна следующей д.н.ф.: x&¬y&z∨ ∨¬ x&y&z∨x&¬x. Из примера видно, что д.н.ф., равносильная заданной формуле, определяется не единственным образом.
Конъюнктивной нормальной формой (к.н.ф.) называется конъюнкция элементарных сумм. Одну элементарную сумму тоже будем считать к.н.ф. Легко доказать следующую теорему.
Теорема 3.11. Для каждой формулы существует равносильная ей к.н.ф. (не единственная).
Можно сформулировать правила для нахождения д.н.ф. и к.н.ф., равносильных заданной формуле. Пусть задана формула А:
- исключить из А все связки, кроме ¬ , &, ∨,
- добиться, чтобы ¬ относилась только к переменным,
- если раскрыть скобки по первому дистрибутивному закону, то получится д.н.ф.,
- если сгруппировать полученный результат в скобки, пользуясь вторым дистрибутивным законом, то получится к.н.ф.
Имеет место теорема.
Теорема 3.12. Для того, чтобы формула А была противоречием, необходимо и достаточно, чтобы равносильная ей д.н.ф. содержала в каждом слагаемом хотя бы одну пару множителей, из которых один - некоторая переменная, а второй - отрицание этой переменной.
Доказательство. Пусть для А равносильной ей д.н.ф. является форма
$В_1∨ В_2 ∨...∨ В_k (k ≥ 1),$
где Вi ( 1≤ i≤ k ) есть элементарное произведение. Дизъюнкция (3.14) будет противоречием тогда и только тогда, когда будет противоречием каждая Вi (1≤ i≤ k). Вi - элементарное произведение и по теореме 3.10 будет противоречием тогда и только тогда, когда содержит хотя бы одну пару множителей, из которых один - некоторая переменная, а второй - отрицание этой переменной. Теорема доказана.
Следствие 3.1. Формула А будет выполнимой, если равносильная ей д.н.ф. содержит хотя бы одно слагаемое, в котором нет таких множителей, что один из них - некоторая переменная, а другой множитель - отрицание этой переменной.
Также просто доказать следующую теорему.
Теорема 3.13. Для того, чтобы формула А была тавтологией, необходимо и достаточно, чтобы равносильная ей к.н.ф. содержала в каждом множителе хотя бы одну переменную вместе с отрицанием этой же переменной.