Приведение к нормальным формам

Как, анализируя формулу в нормальной форме, можно сделать вывод о ее обще­значимости или невыполнимости? Возьмем ДНФ, то есть представление форму­лы в виде дизъюнкции конъюнкций К, vK₂ v...vK_n. Для того чтобы сделать вы­вод о ее общезначимости, нужно анализировать всю формулу целиком: каждая конъюнкция общезначимой формулы может быть истинной только на нескольких интерпретациях. В то же время вывод о невыполнимости дизъюнкции конъюнк­ций можно сделать легко: каждая конъюнкция ДНФ невыполнимой функции должна быть невыполнима, а это очень легко проверить: конъюнкция литер невыполнима тогда и только тогда, когда она содержит хотя бы одну пару противопо­ложных литер. Полностью аналогично можно использовать представление в виде КНФ, но для определения общезначимости функции. Очевидными следствиями предыдущих теорем являются:

Теорема 2.4. Для того, чтобы формула R была логическим следствием формул F₁, F₂,..., F_k, необходимо и достаточно, чтобы каждый конъюнкт дизъюнктивной нор­мальной формы представления формулы F₁,F₂...F_k R содержал пару противополож­ных литер.

Теорема 2.5. Для того, чтобы формула R была логическим следствием формул F₁, F₂,..., F_k, необходимо и достаточно, чтобы каждый дизъюнкт конъюнктивной нормальной формы представления формулы F₁,F₂...F_k => R содержал пару противо­положных литер.

Пример 2.7

Докажем правильность схемы рассуждения «Узнала — спросила» примера 2.4 при­ведением к ДНФ:

(Ск => У)(Сп => Ск)УСп =

= (Ск v У)(Сп v Ск)УСп = (СкСпУСп)v(СкСкУСп)v

v (УСпУСп) v (УСкУСп).

Поскольку каждый конъюнкт содержит пару противоположных литер, эта форму­ла невыполнима и, следовательно, схема рассуждения «Узнала — спросила» пра­вильна. Заметим, что это доказательство много проще построения и анализа таб­лиц истинности (см. табл. 2.6).

Источник: Ерош И.Л. Дискретная математика