Применение нормальных форм.

18. Найдите наипростейшую формулу от трех переменных среди равносильных формул от трех переменных, последний столбец истинности которых имеет следующий вид:

а) 00001111;

б) 01010101;

в) 00100100;

г) 01011110;

д) 11000100;

Решение: а) Для нахождения формулы можно воспользоваться как СДНФ, так и СКНФ. Используем, например, СКНФ. Выделяем те наборы значений переменных, для которых формула обращается в 0.

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

Выписываем СКНФ, удовлетворяющую этим условиям, и затем упрощаем ее с помощью равносильных преобразований:

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

19. Найдите наипростейшую из равносильных формул от трех переменных, которая принимает значение 1 тогда и только тогда, когда точно две ее переменные принимают значение 1.

20. Найдите такую формулу от трех переменных, которая всегда принимает то же значение, что и ее второй аргумент.

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

22. Найдите такую формулу от трех переменных, которая принимает значение 1 тогда и только тогда, когда точно две ее переменные принимают значение 0.

23. Найдите формулу F(X,Y) от двух переменных, такую, что бы следующая формула была тождественно истинной.

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

б) ((FY)X)((XY)F).

Указание. Придавая всевозможные значения переменным данной формулы, выясните сначала, какие значения должна принимать искомая формула F(X,Y) на каждом из четырех возможных значений ее переменных. Затем напишите саму формулу F(X,Y), используя СДНФ или СКНФ.

Нахождение следствий из посылок.

24. Найдите все неравносильные между собой и не тождественно истинные формулы алгебры высказываний, являющиеся логическими следствиями следующих формул (посылок):

а) X(YZ) и ZY;

б) XY и X;

в) XY и Y;

г) XY и X;

д) XY, X и Y;

е) XY и YZ;

ж) XY и YZ;

з) (XY)Z и XY;

и) (XY)Z и YX;

к) XY, YZ и (XY)Z;

и) (XY)Z, Y и Z.

Решение: а) Составляем конъюнкцию посылок и равносильными преобразованиями приводим ее к совершенной конъюнктивной нормальной форме:

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

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

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

XYZX(YZ) (первая посылка);

XYZZ(XY);

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

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

(XYZ)(XYZ)(XY)(ZZ)XY0XYXY;

(XYZ)(XYZ)ZY (вторая посылка);

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

25. Найдите формулу F(X,Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

а) XZ, ZY, YV и ZV;

б) XZ и YZ;

в) XZ, ZY и YX;

г) XZ, YV и ZV;

д) XYZ, XV, ZY и XZ;

е) XZ, YZ, V(YZ) и VX.

Решение: а) Составляем таблицы истинности для формул, являющихся посылками:

X	Y	Z	V	XZ	ZY	YV	ZV
0	0	0	0	1	1	1	0
0	0	0	1	1	1	1	1	2
0	0	1	0	1	1	1	0
0	0	1	1	1	1	1	0
0	1	0	0	1	0	0	0
0	1	0	1	1	0	1	1
0	1	1	0	1	1	0	0
0	1	1	1	1	1	1	0
1	0	0	0	0	1	1	0
1	0	0	1	0	1	1	1
1	0	1	0	1	1	1	0
1	0	1	1	1	1	1	0
1	1	0	0	0	0	0	0
1	1	0	1	0	0	1	1
1	1	1	0	1	1	0	0
1	1	1	1	1	1	1	0

Далее, в правом столбце цифрами отмечаем те строки, в которых все четыре посылки принимают значение 1. Этому требованию удовлетворяет лишь вторая строка, в которой X=0 и Y=0. Следовательно, если мы найдем такую формулу F(X,Y), для которой F(0,0)=1, то такая формула будет логическим следствием четырех данных посылок. Ищем формулу, используя СДНФ и считая, что на всех других наборах значений переменных искомая формула обращается в 0:

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

Получаем F(X,Y)XY.

26. Найдите следствие из посылок:

(XY)Z, (XY) и Y(XZ), содержащее только переменные:

а) X и Z;

б) Y и Z.

27. Найдите следствие из посылок XY, XZ и YV, содержащее только переменные:

а) X и V;

б) Y, Z, и V.

28. Найдите следствие из посылок задачи 5.25. а, содержащее только переменные X и V.

29. Найдите следствие из посылок:

X(YZ), VY, (XW)V, WX,

зависящее только от переменных V,W и Z.

30. Найдите следствие из посылок:

XY, ZV, VZ, YV,

содержащее только переменные:

а) X и Z;

б) X и V.

31. Найдите все следствия из посылок: «Если сумма цифр целого числа делится на 3, то это число делится на 3 или на 9»; «Если целое число делится на 9, то оно делится на 3». Найденным следствиям придайте содержательный смысл.

Решение: Введем обозначения для простых высказываний:

X: «Сумма цифр целого числа делится на 3»;

Y: «Целое число делится на 3»;

Z: «Целое число делится на 9».

Тогда первая посылка символически запишется в виде формулы X(YZ), а вторая – в виде формулы ZY. Задача сводится к тому, чтобы из этих формул (посылок) получить все формулы, являющиеся их логическим следствиями. Для данных посылок эта задача решена нами в задаче 5.24, а. Остается придать этим формулам содержательный смысл:

X(YZ): «Если сумма цифр числа делится на 3, то число делится на 3 или на 9»;

Z(XY): «Если число делится на 9, то оно делится на 3 или сумма цифр делится на 3»;

(XZ) Y: «Если сумма цифр делится на 3 и число делится на 9, то оно делится на 3»;

(XZ) Y: «Сумма цифр делится на 3, тогда и только тогда, когда число делится на 9 или число делится на 3»;

XY: «Если сумма цифр числа делится на 3, то число делится на 3»;

ZY: «Если число делится на 9, то оно делится на 3»;

(XZ)Y: «Если сумма цифр числа делится на 3 или число делится на 9, то число делится на 3».

32. Найдите все следствия из посылок и выразите их в содержательной форме: «Если последняя цифра целого числа четна, то число делится на 2 или на 4»; «Если целое число делится на 4, то оно делится на 2».

33. Найдите все следствия из посылок: «Если целое число делится на 2 и на 5, то оно делится на 10»; «Целое число делится на 2 и не делится на 5». Выразите полученные следствия в содержательной форме.

Указание: Выразите посылки в виде формул алгебры высказываний и обратитесь задаче 5.24, и.

34. Найдите все следствия из посылок: «Если у четырехугольника две противоположные стороны параллельны и они же равны, то этот четырехугольник – параллелограмм»; «У данного четырехугольника две противоположные стороны равны или параллельны».

Указание: см. задачу 5.24, з.

35. Даны посылки: «Если целое число n больше 1, то оно простое либо составное»; «Если целое число четное, то оно не простое»; «Если целое число больше 1 и не больше 2, то оно четное»; «Если целое число 2, то оно больше 1». Из этих посылок найдите следствие, связывающее высказывания: «Целое число больше 2», «Целое число четное» и «Целое число составное».

Указание: Выразите посылки в виде формул алгебры высказываний и обратитесь к задаче 5.29.

36. Даны посылки: «Если данный четырехугольник – ромб, то его диагонали перпендикулярны»; «Если данный четырехугольник – квадрат, то его диагонали равны»; «Если диагонали данного четырехугольника не равны, то он не квадрат»; «Диагонали данного четырехугольника не перпендикулярны и равны». Найдите следствие из посылок, состоящее из высказываний:

а) «Данный четырехугольник – ромб» и «Данный четырехугольник – квадрат»;

б) «Данный четырехугольник – ромб» и «Диагонали данного четырехугольника равны».

Указание: см. задачу 5.30.