PhilosophyDay

Дизъюнктивная нормальная форма. Проблема разрешимости

Другая философия / Логика высказываний / Дизъюнктивная нормальная форма. Проблема разрешимости

Для каждой формулы наряду с конъюнктивной нормальной формой существует дизъюнктивная нормальная форма. Она состоит из дизъюнкции конъюнкций, в которой каждый конъюнктивный член является элементарным высказыванием или его отрицанием.

Преобразование формулы к дизъюнктивной нормальной форме происходит следующим образом: отрицанием первоначальную формулу и приведем ее к конъюнктивной нормальной форме, а затем вновь отрицанием полученное выражение согласно правилу а3).

Например, привести к дизъюнктивной нормальной форме формулу:

р Ù (р®q).

Отрицаем эту формулу и приводим полученное выражение к конъюнктивной нормальной форме:

р Ù (р®q) ≡`рÚ (р ®q) ≡`рÚ (`рÚ q) ≡`рÚ (`рÙ `q) ≡(`рÚ`р) Ù(`р Ú`q) ≡ ≡(`рÚр) Ù(`р Ú`q)

Отрицаем последнее выражение:

_ _ _

(`рÚр) Ù(`р Ú`q) ≡(`рÚр) Ú (`р Ú`q) ≡ (`р Ù`р) Ú (`р Ù`q) ≡(р Ù`р) Ú (р Ùq)

Приведение формулы к нормальной форме дает иной, чем таблицы истинности метод решения проблемы разрешимости.

Чтобы формула была тождественно истинной необходимо и достаточно, чтобы в ее конъюнктивной нормальной форме каждый конъюнктивный член содержал элементарное высказывание вместе со своим отрицанием.

Доказательство получаем из (25)(91) и (15), а также определения конъюнкции. Так формула (р Ú `рÚ q) Ù( р Ú `qÚ q) тождественно истинна.

Чтобы формула была тождественно ложной необходимо и достаточно, чтобы в ее дизъюнктивной нормальной форме каждый дизъюнктивный член содержал элементарное высказывание вместе со своим отрицанием. Так формула:

(р ÙrÙ`р) Ú ( р Ù r Ù`r ) тождественно ложна.

Доказательство получаем из того, что р Ù`р≡0, (16) и определения дизъюнкции.

Формула будет выполнимой, если в ее дизъюнктивной нормальной форме есть хотя бы один дизъюнктивный член, который не содержит элементарное высказывание вместе со своим отрицанием.

В самом деле, если это условие для какой-то формулы выполнено, то для этого дизъюнктивного члена существует такой набор значения переменных, для которого он равен 1. Тогда согласно (18) для этого набора значений переменных формула принимает значение, равное1.

Например, докажем, что формула р≡ q выполнима. Приводим эту формулу к дизъюнктивной нормальной форме:

(р≡ q ) ≡(р® q) Ù(q ®р) ≡ (`р Ú q) Ù(`q Úр) ≡((`р Ú q) Ù`q) Ú((`р Ú q) Ùр) ≡ ≡ (`р Ù`q) Ú (q Ù`q) Ú (`р Ù р) Ú (q Ùр) ≡ (`р Ù`q) Ú (q Ùр) ≡ (q Ùр) Ú(`р Ù`q).

Каждый дизъюнктивный член не содержит элементарное высказывание вместе со своим отрицанием. А значит формула р≡ q выполнима.