6.5. Дизъюнктивные и конъюнктивные нормальные формы

Покажем, что для каждой ПФ существует ей равносильная специального вида. Если Х – пропозициональная переменная, v есть 0 или 1, то выражение

называется литерой. Литеры X и называются контрарными.

Заметим, что ПФ тогда и только тогда, когда , то есть .

Следовательно, ПФ на наборе принимает значение 1, а на любом другом – значение 0. Аналогично ПФ принимает значение 0 только на наборе ( , ,..., ), а на всех остальных наборах – 1 [3].

Т еорема 6.5.1. Для любой ПФ имеет место равносильность

называемая дизъюнктивным разложением по переменной Х₁.

Доказательство.

Пусть – произвольная ПФ. Определим значения левой и правой частей равносильности при Х₁=1 и Х₁=0.

П ри Х₁=0 в левой части равносильности получаем ПФ , а в правой части –

Таким образом, в левой и правой частях равносильности получаем одну и туже ПФ .

Аналогично можно показать, что при Х₁=1 значением левой и правой частей равносильности является ПФ .

Итак, для любого набора значений переменных Х₁, Х₂, ..., Х_n левая и правая части равносильности совпадают, что и доказывает справедливость теоремы.

Пример. Для ПФ определить дизъюнктивное разложение по переменной Х₁.

С ледствие. Для любой ПФ и любого натурального k имеет место равносильность

,

называемая дизъюнктивным разложением по переменным .

Теорема 6.5.2. Для любой ПФ имеет место равносильность

называемая конъюнктивным разложением по переменной Х₁.

Доказательство теоремы 6.5.2 аналогично доказательству теоремы 6.5.1.

Пример. Для ПФ определить конъюнктивное разложение по переменной Х₁.

Следствие. Для любой ПФ и любого натурального k имеет место равносильность

,

называемая конъюнктивным разложением по переменным .

Таким образом, для любой ПФ существует равносильная ей, содержащая только константы 0 и 1, символы и переменные.

Определим некоторые канонические представления ПФ.

ПФ называется элементарной конъюнкцией (конъюнктом), если она является конъюнкцией переменных и отрицаний переменных (конъюнкцией литер).

ПФ называется элементарной дизъюнкцией (дизъюнктом), если она является дизъюнкцией переменных и отрицаний переменных (дизъюнкцией литер).

Пример.

– элементарная конъюнкция.

– элементарная дизъюнкция.

Говорят, что ПФ задана в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией элементарных конъюнкций.

Пример. – ДНФ.

Говорят, что ПФ задана в конъюнктивной нормальной форме (КНФ), если она является конъюнкцией элементарных дизъюнкций.

Пример. – КНФ.

На основе равносильных преобразований любая формула может быть приведена к нормальной форме (ДНФ или КНФ) [3,4].

6.5.1. Алгоритм приведения пф к нормальным формам

Алгоритм приведения ПФ к нормальным формам описывает следующая последовательность шагов.

1. Если ПФ содержит операции → и ↔, то их исключить с помощью равносильностей

, .

2. Привести отрицания к независимым переменным, используя законы де Моргана.

3. Раскрыть скобки по дистрибутивному закону конъюнкции относительно дизъюнкции для приведения к ДНФ или по дистрибутивному закону дизъюнкции относительно конъюнкции для приведения к КНФ.

Пример. Определить нормальные формы для ПФ .

Действуя, в соответствии с алгоритмом 6.5.1, получим ДНФ.

П рименяя к полученной ДНФ дистрибутивный закон дизъюнкции относительно конъюнкции, получим

Замечание. Для данной ПФ существует множество ДНФ и КНФ, переход от одной формы к другой осуществляется на основе равносильных преобразований.

В логике высказываний следующую проблему называют проблемой разрешимости. Существует ли такая процедура, которая позволяла бы для данной ПФ за конечное число шагов определить, является ли она тавтологией. С одной стороны, с помощью таблиц истинности можно определить тип любой ПФ, с другой стороны, для решения этой проблемы могут быть использованы нормальные формы.

Теорема 6.5.3. Для того, чтобы ПФ была тождественно истинной, необходимо и достаточно, чтобы в её КНФ каждая элементарная дизъюнкция содержала слагаемыми хотя бы одну переменную вместе с ее отрицанием.

Доказательство. Заметим, что достаточность очевидна: в каждом слагаемом КНФ содержится пара вида – этого достаточно для обращения формулы в единицу независимо от значений переменных.

Необходимость доказывается методом от противного. Если существует слагаемое, не удовлетворяющее условию, то его можно обратить в 0 соответствующим подбором значений переменных. Для этого переменным, входящим в это слагаемое без отрицания, дадим значение 0, а с отрицанием – 1. При этих значениях слагаемое, а следовательно, и КНФ обращается в 0 – это противоречие.

Теорема 6.5.4. Для того, чтобы ПФ была тождественно ложной, необходимо и достаточно, чтобы в ее ДНФ каждая элементарная конъюнкция содержала сомножителями хотя бы одну переменную вместе с ее отрицанием.

Доказательство проводится аналогично, только теперь рассматриваемое слагаемое надо обратить в 1.

Совершенной дизъюнктивной нормальной формой (СДНФ) данной ПФ называется ДНФ, в которой каждая элементарная конъюнкция содержит все переменные – без отрицания или с отрицанием, но не вместе.

Совершенной конъюнктивной нормальной формой (СКНФ) данной ПФ называется КНФ, в которой каждая элементарная дизъюнкция содержит все переменные – без отрицания или с отрицанием, но не вместе.

Существует два способа перехода к совершенным формам табличный и аналитический [2, 3, 4].