НАХОЖДЕНИЕ СЛЕДСТВИЙ ИЗ ПОСЫЛОК

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

а) и ;

б) и Х;

в) и ;

г) и ;

д) и ;

е) и ;

ж) и ;

з) и ;

и) и ;

к) и ;

л) и Z.

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

.

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

1) (первая посылка);

2) ;

3) ;

4) ;

5) ;

6) (вторая посылка);

7) .

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

а) и

б) и

в) и

г) и

д) и

е) и

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

X	Y	Z	V

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

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

Получаем .

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

и

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

а) X и Z;

б) Y и Z.

1.25. Найдите следствие из посылок и , содержащее только переменные:

а) X и V;

б) Y, Z и V.

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

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

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

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

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

а) X и Z;

б) X и V.

1.29. Докажите, что описанный в решении задачи 1.23 а) способ отыскания логического следствия из данных посылок, содержащего только заданные пропозициональные переменные, позволяет найти самое сильное из следствий, т. е. такое следствие, что все другие следствия, связывающие указанные переменные, сами из него следуют.

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

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

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

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

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

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

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

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

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

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

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

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

: «Если сумма цифр числа делится на 3 или число делится на 9, то число делится на 3».

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

Указание. Запишите посылки в виде формул алгебры высказываний и сравните их с посылками предыдущей задачи.

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

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

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

Указание. См. задачу 1.22, з.

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

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

X: «Четырехугольник — ромб»;

Y: «Четырехугольник — квадрат»;

Z: «Диагонали четырехугольника взаимно перпендикулярны»;

V: «Четырехугольник можно вписать в окружность».

Тогда посылки можно записать символически следующим образом:

Последняя посылка равносильна такой: и поэтому задача сводится к тому, чтобы из данных посылок получить следствие, зависящее лишь от переменных X и Y. Эта задача решена нами в задаче 1.23, а. Остается придать полученной формуле содержательный смысл: «Четырехугольник не является ни ромбом, ни квадратом».

1.35. Из посылок предыдущей задачи найдите правильное заключение о связи между высказываниями: «Данный четырехугольник - ромб» и «Данный четырехугольник можно вписать в окружность».

Указание.См. задачу 1.26.

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

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

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

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

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

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

12
• Далее ⇒