§5 Нормальные формы для формул алгебры высказываний.

Конъюнктивным (дизъюнктивным) одночленом от переменных X₁, X₂, …, X_n называются конъюнкция (дизъюнкция) этих переменных или их отрицаний. Например, X₁X₂X₃, X­₁X₂, X₁ – конъюнктивные одночлены; X₁X₃, X₁X₂, X₃ – дизъюнктивные одночлены.

Дизъюнктивной (конъюнктивной) нормальной формой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Например, (Х₁X₂)(Х₁Х₂) – дизъюнктивная нормальная форма; (Х₁Х₂Х₃)(Х₁Х₂)Х₃ – конъюнктивная нормальная форма.

Сокращенная запись: ДН – форма и КН – форма соответственно.

Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз со знаком отрицания или без знака отрицания.

Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в неё одночлен является совершенным одночленом от тех же самых переменных.

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

Например, (Х₁Х₂)(Х₁Х₂)(Х₁Х₂) – совершенная конъюнктивная нормальная форма от двух переменных X₁ и X₂;

(Х₁Х₂Х₃)(Х₁Х₂Х₃) – совершенная дизъюнктивная нормальная форма от трёх переменных X₁, X₂, X₃.

Теорема 1: Всякая формула алгебры высказываний, отличная от тождественно ложной, имеет единственную совершенную дизъюнктивную нормальную форму. Тождественно ложная формула СДНФ не имеет.

Теорема 2: Всякая формула алгебры высказываний, отличная от тождественно истинной, имеет единственную совершенную конъюнктивную нормальную форму. Тождественно истинная формула СКНФ не имеет.

Отыскание нормальных форм Упражнения.

1. Приведите равносильными преобразованиями каждую из следующих формул к дизъюнктивной нормальной форме:

а) (XZ)(X→Y);

б) (XY)(Z→T);

в) (X(YZ))(XZ);

г) ((X→Y)→(Z→X))→(Y→Z);

д) (X→(Y→Z))→((X→Z)→(X→Y)).

Решение:

а)(XZ)(X→Y)(XZ)(XY)XZ(XY)(XZX)(XZY)(XZ)(XYZ).

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

Решение:

а) (XZ)(X→Y)(XZ)(XY)ZX(XY)ZX.

3. Равносильными преобразованиями приведите каждую из следующих формул к СДН – форме:

а) (XZ)(YZ);

б) (XY)(YZ);

в) X(YZ);

г) (XY)(ZT);

д) ((XY)Z)(XZ);

е) ((XY)(XZ))(Y(ZY));

ж) XYZ;

з) (XYZ)(XT)(ZT);

и) (XY)(XY)(XZ)(XZ)(YZ)( YZ);

к) X(XY)(YZ)(ZT);

л) XYZST.

Решение:

а) Сначала приводим формулу к ДНФ

(XZ)(YZ)(XY)Z

Конъюнктивный одночлен XY не является совершенным от трех переменных X, Y, Z т.к. в него не входит переменная Z. Введение её осуществляется следующим образом:

XYXY1XY(ZZ)(XYZ)(XYZ).

Далее, в одночлене Z отсутствуют две переменные X и Y. Введем сначала в этот одночлен переменную Y:

ZZ1Z(YY)(YZ)(YZ)

Наконец, в каждый из конъюнктивных одночленов YZ и YZ введем отсутствующую в них переменную Х:

Z(YZ)(YZ)(YZ1)(YZ1)(YZ(XX))(YZ(XX))(YZX)(YZX)(YZX)(YZX)(XYZ)(XYZ)(XYZ)(XYZ)

Итак, данная формула имеет следующую СДНФ:

(XZ)(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).

4. Равносильными преобразованиями приведите каждую из следующих формул к СКН – форме:

а) (XZ)(YZ);

б) (XY)Z;

в) (XY)(XZ);

г) (XY)(ZT);

д) (XYZ)T;

е) XYZ;

ж) (XY)(YZ)(ZT);

з) XY(ZT);

и) (XY)Z;

к) XYZT;

л) (XY)(XYZ)Z.

Решение:

а) Сначала приводим формулу к КНФ:

(XZ)(YZ)Z(XY).

Дизъюнктивный одночлен XY не является совершенным, т.к. в него не входит переменная Z. Введение этой переменной осуществляется следующим образом:

XYXY0XY(ZZ)(XYZ)(XYZ).

Далее, в одночлене Z отсутствуют две переменные X и Y. Введем сначала переменную Y:

ZZ0Z(YY)(YZ)(YZ).

Наконец, в каждый из дизъюнктивных одночленов YZ и (YZ) введем отсутствующую в них переменную Х:

Z(YZ)(YZ)(YZ0)(YZ0)(YZ(XX))(YZ(XX))(XYZ)(XYZ)(XYZ)(XYZ).

Подставляя полученные выражения в данную формулу и выбрасывая повторяющийся дизъюнктивный одночлен (на основании закона идемпотентности), получаем СКНФ для данной формулы:

(XZ)(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).

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

е) (XY)(YZT)(XYZT);

ж) ((X→Y)→Y)→(X→(YX));

з) (XY→X)((XY)→Y).

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

е) (XY)(YZ)(ZT);

ж) X(YZ)(XYZ);

з) (X(YZ))→((XY)Z).

7. По данному набору значений переменных постройте конъюнктивный одночлен, принимающий значение 1 только на этом наборе значений переменных:

а) (0;0); г) (0, 1, 1);

б) (0;1); д) (1, 0, 0);

в) (1;1); е) (1, 0, 1, 1).

8. Используя СДНФ, найдите формулу, принимающую значение 1 на следующих наборах значений переменных, и только на них:

а) F(0;0)=F(1;1)=1;

б) F(1;0)=1;

в) F(0,1,0)=F(1,0,1)=F(1,1,1)=1;

г) F(0,1,1)=F(1,1,0)=1;

д) F(1,0,0)=F(0,1,0)=F(0,0,1)=1;

е) F(0,1,1)=F(1,0,1)=F(1,1,0)=F(1,1,1)=1;

ж) F(0,0,0)=F(0,1,0)=F(1,1,1)=1;

з) F(0,1,0,1)=F(1,0,1,0)=F(1,0,0,0)=F(1,1,1,0)=F(1,1,1,1)=1.

Решение: ж) Первому условию удовлетворяет лишь конъюнктивный одночлен

XYZ, второму - XYZ, третьему – XYZ.

Тогда формула F(X,Y,Z)=(XYZ)(XYZ)(XYZ) обращается в 1, если и только если XYZ обращается в 1, или XYZ обращается в 1, или XYZ обращается в 1, т.е. если и только если (X,Y,Z)=(0,0,0), или (X,Y,Z)=(0,1,0), или (X,Y,Z)=(1,1,1). Следовательно, F(X,Y,Z)- искомая формула.

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

10. По данному набору значений переменных постройте дизъюнктивный одночлен, принимающий значения 0 только на этом наборе значений переменных:

а) (0,0); г) (0,1,1);

б) (1,0); д) (1,0,1);

в) (1,1); е) (1,0,0,1).

11. Используя СКНФ, найдите формулу, принимающую значение 0 на следующих наборах значений переменных, и только на них:

а) F(0, 1) = F(1, 1) = 0;

б) F (0, 1) = 0;

в) F(0, 1, 1) = 0;

г) F(1, 0, 0) = F(1, 0, 1) = 0;

д) F(0, 1, 1) = F(0, 0, 0) = F(0, 1, 0) = 0;

е) F(1, 1, 1) = F(0, 0, 1)= F(1, 1, 0) = F(1, 0, 0)= 0;

ж) F(0, 0, 0) = F(0, 1, 0) = F(1, 1, 1) =0;

з) F(1, 1, 0, 1) = F(0, 0, 1, 0) = F(1, 0, 1, 0)= F(0, 0, 1, 1) =0;

Решение: ж) Первому условию удовлетворяет лишь следующий дизъюнктивный одночлен X v Y v Z, второму - X v Y v Z, третьему - X v Y v Z. Тогда следующая формула F(X, Y, Z) = (X v Y v Z)  (X v Y v Z)  (X v Y v Z) обращается в 0, если и только если X v Y v Z обращается в 0, или X v Y v Z обращается в 0, или X v Y v Z обращается в 0, т.е. если и только если (X, Y, Z) = (0, 0, 0), или (X, Y, Z) = (0, 1, 0), или (X, Y, Z) = (1, 1, 1) следовательно F(X, Y, Z) – искомая формула.

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

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

а) (X  Y)  (X v Y);

б) X  Y;

в) (X  Y) v Z;

г) (X  Z)  (X  Y);

д) X v (Y  (Z  (X  Y)));

е) ((X  Y) v Z)  T;

ж) (X  ((Y  Z) v T)) v T;

з) X  Y;

и) (X v Y)  Z;

к) (X  Y  Z) v T;

л) (X v Y)  (X  (Y  Z));

м) X  Y  ((Z  (X  Y));

н) (X  Y) v (Y  Z) v (Z  T).

Решение: Составим сначала таблицу истинности этой формулы:

X	Y	(XY)	(XY)	(XY)(XY)
0	0	1	1	1
0	1	1	0	0
1	0	1	0	0
1	1	0	0	1

Для нахождения СДНФ выбираем наборы значений переменных, на которых формула обращается в 1, подобно тому как это делалось в задаче 5.8, записываем совершенную дизъюнктивную нормальную форму для данной формулы:

(XY)(XY)(XY)(XY).

Для нахождения СКНФ выбираем наборы значений переменных, на которых формула обращается в 0, подобно тому как это делалось в задаче 5.11, записываем совершенную конъюнктивную нормальную форму для данной формулы:

(XY)(XY)(XY)  (X v Y).

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

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

16. Применяя утверждение в задачи 5.14, перейдите от СДНФ к СКНФ:

а) F = (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z);

б) F = (X  Y) v (X  Y);

в) F = (X  Y) v (X  Y);

г) F = (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z);

д) F = (X  Y  Z) v (X  Y  Z);

е) F = (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z) v (X  Y  Z);

ж) F = (X  Y  Z  T) v (X  Y  Z  T) v (X  Y  Z  T) v (X  Y  Z  T) v (X  Y  Z  T) v (X  Y  Z  T);

Решение: а) Согласно задаче 5.14. имеем: отрицание формулы имеет следующую СДНФ:

F  (X  Y  Z) v (X  Y  Z) v (X  Y  Z).

Теперь находим отрицание этой формулы:

F   F  ((X  Y  Z) v (X  Y  Z) v (X  Y  Z))  (X  Y  Z)  (X  Y  Z)  (X  Y  Z).

Это и есть СКНФ данной формулы F.

17. Применяя утверждение задачи 5.15., перейдите от СКНФ к СДНФ:

а) F = (X v Y v Z)  (X v Y v Z)  (X v Y v Z)  (X v Y v Z);

б) F = (X v Y)  (X v Y);

в) F = (X v Y)  (X v Y);

г) F = (X v Y)  (X v Y)  (X v Y)  (X v Y);

д) F = (X v Y v Z)  (X v Y v Z)  (X v Y v Z)  (X v Y v Z);

е) F = (X v Y v Z)  (X v Y v Z)  (X v Y v Z);

ж) F = (X v Y v Z v T)  (X v Y v Z v T)  (X v Y v Z v T)  (X v Y v Z v T)  (X v Y v Z v T)  (X v Y v Z v T);

Решение подобно №5.16.