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

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.

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

Далее, в правом столбце цифрами отмечаем те строки, в которых все четыре посылки принимают значение 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.