Отыскание нормальных форм формул логики высказываний

Формулы алгебры высказываний могут быть приведены к нормальным формам: дизъюнктивной и конъюнктивной.

Конъюнктивным (дизъюнктивным) одночленом от переменных Х₁, Х₂,…,Х_n называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Дизъюнктивной (конъюнктивной) нормальной формой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Сокращенная запись: ДН-форма (или ДНФ) и КН-форма (или КНФ) соответственно. Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз, со знаком отрицания или без него.

Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных. Сокращенная запись: СДН-форма (или СДНФ) – совершенная дизъюнктивная нормальная форма, СКН-форма (или СКНФ) – совершенная конъюнктивная нормальная форма.

Например, (X₁ ÙØ X₂ Ù Х₃)Ú(Х₁ Ù Х₃)ÚØ Х₂ – дизъюнктивная (но не совершенная) нормальная форма от трех переменных Х₁, Х₂, Х₃, а (Х₁ ÚØ Х₂)Ù(Ø Х₁ Ú Х₂)Ù(Ø Х₁ ÚØ Х₂) – совершенная конъюнктивная нормальная форма от двух переменных Х₁ и Х₂.

Для того чтобы формулу равносильными преобразованиями привести к ДНФ, нужно руководствоваться следующим алгоритмом:

1) избавиться от операции импликации и эквивалентности, выразив их через логические связки Ø, Ù и Ú по законам: X ® Y ºØ X Ú Y, X «Y º (ØX Ú Y)Ù(Ø Y Ú X);

2) довести знаки отрицания до независимых переменных, используя законы де Моргана: Ø(X Ú Y) ºØ X ÙØ Y, Ø(X Ù Y)ºØ X ÚØ Y;

3) применяя закон дистрибутивности (X Ú Y)ÙZº(X Ù Z)Ú(Y ÙZ), преобразовать формулу к дизъюнкции конъюнктивных одночленов;

4) постоянно избавляться от двойных отрицаний: ØØ Х º Х.

Пример 1.1.

Привести равносильными преобразованиями формулу Ø(X Ú Z)Ù(X ® Y) к дизъюнктивной нормальной форме.

Решение. Преобразуем формулу к ДНФ, руководствуясь приведенными правилами:

Ø(Х Ú Z)Ù(X®Y)º (Ø X ÙØ Z)Ù(Ø X Ú Y)ºØ X Ù(ØZÙ(Ø X Ú Y))º Ø X Ù((ØZÙØ X)Ú(ØZÙ Y))º(Ø X ÙØ Z ÙØ X)Ú(Ø X Ù Y ÙØ Z) º(Ø X ÙØ Z)Ú(Ø X Ù Y ÙØ Z).

Пример 1.2.

Привести равносильными преобразованиями формулу примера 1.1 к конъюнктивной нормальной форме.

Решение. Формулу равносильными преобразованиями можно привести к КНФ, руководствуясь приведенными четырьмя правилами, с той лишь разницей, что в правиле 3) следует использовать другой (двойственный) закон дистрибутивности: (X Ù Y)Ú Z º(Х Ú Z)Ù(Y Ú Z).

Преобразуем данную формулу:

Ø(Х Ú Z)Ù(X®Y)º(Ø X ÙØ Z)Ù(Ø X Ú Y)º(Ø X ÙØZ)Ú(Ø X Ù Y ÙØ Z)º((Ø X ÙØ Z)ÚØ X)Ù

Ù((Ø X ÙØ Z)Ú Y)Ù((Ø X ÙØ Z)ÚØZ)ºØ X Ù((Ø X Ú Y)Ù(Ø Z Ú Y))ÙØ Z ºº(Ø X Ù(Ø X Ú Y))Ù((Ø Z Ú Y)ÙØ Z)ºØ X ÙØ Z.

Пример 1.3.

Применяя равносильные преобразования, найти СДНФ для формулы из примера 1.1

Решение. Чтобы привести формулу к СДНФ, нужно сначала равносильными преобразованиями привести ее к какой-нибудь ДНФ (см. пример 1.1). При этом нужно убрать члены дизъюнкции, содержащие переменную вместе с ее отрицанием, а из одинаковых членов дизъюнкции удалить все, кроме одного. Если какой-либо конъюнктивный одночлен в ДНФ содержит не все переменные из числа входящих в исходную формулу, то его умножают на единицы, представляемые в виде дизъюнкций X_i ÚØ X_i каждой недостающей переменной X_i с ее отрицанием Ø X_i (закон исключенного третьего). Затем раскрывают скобки внутри каждого такого конъюнктивного одночлена, применяя закон дистрибутивности конъюнкции относительно дизъюнкции. Наконец, если среди членов полученной дизъюнкции окажутся одинаковые конъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.

Приведем данную формулу к СДНФ, начав преобразования с ДНФ, полученной при решении примера 1.1:

Ø(Х Ú Z)Ù(X ® Y)º(Ø X ÙØ Z) Ú (Ø X Ù Y ÙØ Z)º((Ø X ÙØ Z)Ù(Y ÚØ Y))Ú(Ø X Ù Y ÙØ Z)º º(Ø X ÙØ Z Ù Y)Ú(Ø X ÙØ Z ÙØ Y)Ú(Ø X Ù Y ÙØ Z) º(Ø X Ù Y ÙØ Z)Ú(Ø X ÙØ Z ÙØ Y).

Пример 1.4.

Применяя равносильные преобразования, найти СКНФ для формулы из примера 1.2.

Решение. Правила приведения формулы к СКНФ двойственны соответствующим правилам приведения к СДНФ. Найчав с какой-нибудь КНФ данной формулы, нужно в каждом ее дизъюнктивном одночлене, в котором присутствуют не все переменные из числа входящих в данную формулу, добавить (через дизъюнкцию) нули, представляемые в виде конъюнкции X_i ÙØ X_i каждой недостающей переменной X_i с ееотрицанием Ø X_i. Затем внутри каждого такого дизъюнктивного одночлена раскрыть скобки, используя закон дистрибутивности дизъюнкции относительно конъюнкции. Если среди членов полученной конъюнкции окажутся одинаковые дизъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.

Приведем данную формулу к СКНФ, начав преобразование с КНФ, полученной при решении примера 1.2:

Ø(Х Ú Z)Ù(X ® Y)ºØ X ÙØ Z º(Ø X Ú(Y ÙØ Y))Ù(Ø Z Ú(X ÙØ X))º(Ø X Ú Y)Ù(Ø X ÚØ Y)Ù

Ù(X ÚØ Z)Ù(Ø X ÚØ Z)º(Ø X Ú Y Ú(Z ÙØ Z))Ù(Ø X ÚØ Y Ú(Z ÙØ Z))Ù(X ÚØ Z Ú(Y ÙØ Y))Ù

Ù(Ø X ÚØ Z Ú(Y ÚØ Y))º(Ø X Ú Y Ú Z)Ù(Ø X Ú Y ÚØ Z)Ù(Ø XÚ Ø YÚZ)Ù(Ø X ÚØ Y ÚØ Z)Ù Ù(XÚYÚ Ø Z)Ù(X ÚØ Y ÚØ Z)Ù(Ø X Ú Y ÚØ Z)Ù(Ø XÚ Ø YÚ Ø Z)º º(Ø X Ú Y Ú Z)Ù(Ø X Ú Y ÚØ Z)Ù(Ø X ÚØ Y Ú Z)Ù(Ø XÚ Ø YÚ Ø Z)Ù(XÚYÚ Ø Z)Ù(X ÚØ Y ÚØ Z).

 

1.4. Тождественно истинные и тождественно ложные формулы.
Проблема разрешимости

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

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

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

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

Пример 1.5.

Доказать, что формула F =(P ® Q) ®((R Ú P) ®(R Ú Q)) является тождественно истинной.

Применяя равносильные преобразования, приведем формулу к КНФ:

(P ® Q)®((R Ú P)®(R Ú Q))ºØ(P ® Q)Ú((R Ú P) ®(R Ú Q))º (P ÙØ Q)ÚØ(R Ú P)Ú Ú(R Ú Q) º (P ÙØ Q) Ú(Ø R ÙØ P) Ú(R Ú Q) º (P ÚØ R)Ù (P Ú Ø P) Ù(Ø Q ÚØ R)Ù

Ù(Ø Q ÚØ P)Ú(R Ú Q)º (P ÚØ R)Ù(Ø Q ÚØ R)Ù(Ø Q ÚØ P)Ú(R Ú Q) º º (P ÚØ R Ú R Ú Q)Ù(Ø Q ÚØ R Ú R Ú Q)Ù(Ø Q ÚØ P Ú R Ú Q).

В первую дизъюнкцию входят R и Ø R. Во вторую – Q и Ø Q, R и Ø R. в третью – Q и Ø Q. Следовательно, можно утверждать, что исходная формула является тождественно истинной.

Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Пример 1.6.

Установить, является ли тождественно истинной данная формула логики высказываний: F (P, Q) = (P Ù(P ® Q)) ® Q.

1) Применяя равносильные преобразования, приведем формулу к КНФ:

(P Ù(P ® Q)) ® Q º(P Ù(Ø P Ú Q))® Q ºØ(P Ù(Ø P Ú Q)Ú Q º º Ø P ÚØ(Ø P Ú Q))Ú Q º Ø P Ú(P ÙØ Q)Ú Q º (Ø P Ú Q)Ú(P ÙØ Q)º º (Ø P Ú Q Ú P)Ù(Ø P Ú Q Ú Ø Q).

В первую дизъюнкцию входят P и Ø P. Во вторую – Q и Ø Q, поэтому формула является тождественно истинной, F (P, Q) º 1.

2) Составим таблицу истинности F (P, Q) (таблица 2).

Таблица 2

P	Q	P ® Q	P Ù(P ® Q)	(P Ù(P ® Q))® Q

Из таблицы 2 видно, что F (P, Q) º 1.