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

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

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

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

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

(ùXÙY)ÚZ, ù(XÙY) и Y®(XÚùZ), содержащее только переменные:

а) X и Z;

б) Y и Z.

5.27. Найдите следствие из посылок XÚY, X®Z и Y«V, содержащее только переменные:

а) X и V;

б) Y, Z, и V.

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

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

X®(YÚZ), V®ùY, (XÙùW)®V, W®X,

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

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

X®Y, Z®V, ùV®ùZ, ùYÙV,

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

а) X и Z;

б) X и V.

5.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».

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

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

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

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

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

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

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

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

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

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

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