logo search
методичка мат лог

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

    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).

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

Решение:

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

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

а) (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).

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

а) (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).

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

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

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

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

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

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

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

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

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

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

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

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

    1. Используя СДНФ, найдите формулу, принимающую значение 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)- искомая формула.

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

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

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

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

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

    1. Используя СКНФ, найдите формулу, принимающую значение 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) – искомая формула.

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

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

а) (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).

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

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

    1. Применяя утверждение в задачи 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.

    1. Применяя утверждение задачи 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.