Т. А. Сливина математическая логика и теория алгоритмов

Пример:
Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира, заявили:
1. Антон был вторым, а Борис – пятым.
2. Виктор был вторым, а Денис – третьим.
3. Григорий был первым, а Борис – третьим.
4. Антон был третьим, а Евгений – шестым.
5. Виктор был третьим, а Евгений – четвертым.
Впоследствии выяснилось, что каждый зритель ошибся в одном из двух своих высказываний. Каково было истинное распределение мест в турнире?
Решение: Обозначим высказывания зрителей символом , где Х – первая буква имени участника турнира, а у – номер места, которое он занял в турнире. Согласно условию задачи дизьюнкции высказываний будут истинны
, , , , .
Тогда будет истинной и формула
( )( )( )( )( ).
Путем равносильных преобразований получим
. Но, так как , значит,
, , , , , что и дает ответ на вопрос задачи.


Задачи и упражнения

1. Какие из следующих предложений являются высказываниями:

а) Москва – столица России;
б) студент ФИСУ;
в)
г) а > 0;
д) Сегодня – понедельник.
2. Приведите примеры предложений, а) являющихся высказываниями; б) не являющихся высказываниями.
3. Установите, истинно или ложно следующие высказывания:
а) ;
б) ;
в) ;
г) , где – множество всех подмножеств множества N;
д) Ø Ø;
е) Ø {Ø}.
4. Среди следующих высказываний указать элементарные и составные. В составных высказываниях выделить грамматические связки:
а) число 32 делится на 4;
б) число 28 делится на 4 и на 7;
в) если число 125 делится на 25, то оно делится на 5;
г) число 7 является делителем числа 42;
д) число 1 269 делится на 9 тогда и только тогда, когда 18 делится на 9.
5. Обозначьте элементарные высказывания буквами и запишите следующие высказывания с помощью символов алгебры логики:
а) 27 кратно 3 и 15 кратно 3;
б) 27 кратно 3 и 9 не кратно 3;
в) или ;
г) если число 120 делится на 3 и на 5, то оно делится на 15.
6. Пусть p и q обозначают высказывания:
p – «Я учусь в школе»,
q – «Я люблю математику».
Прочтите следующие сложные высказывания:
а) ; б) ; в) ; г) ; д) ; е) ; ж) .
7. Проверить, не составляя таблиц истинности, являются ли следующие формулы тождественно истинными:
а) ;
б) ;
в) ;
г) ;
д) ;
е) ;
ж) ;
з) ;
и) ;
к) ;
л) ;
м) ;
н) ;
о) .
8. Найдите логические значения x и y, при которых выполняются равенства:
1) ; 2) .
9. Пусть x = 0, y = 1, z = 1. Определить логические значения нижеследующих сложных высказываний:
а) ;
б) ;
в) ;
г) ;
д) ;
е) .
10. а) Постройте с помощью отрицания и дизьюнкции формулу, таблица истинности для которой совпала бы с таблицей для импликации.
б) Аналогично этому постройте с помощью отрицания и импликации формулу, таблица истинности для которой совпадает с таблицей для дизьюнкции, и вторую формулу с таблицей, совпадающей с таблицей для коньюнкции.
11. Составить таблицы истинности для формул:
а) ;
б)
в) ;
г) ;
д) ;
е) ;
ж) .
12. Установить, какие из следующих формул являются тождественно истинными, тождественно ложными:
а) ;
б) ;
в) ;
г) ;
д) .
13. Доказать равносильность:
а) ;
б) ;
в) ;
г) ;
д) ;
е) .
14. Упростить формулу:
а) ;
б) ;
в) ;
г) ;
д) .
15. Доказать тождественную истинность или тождественную ложность формул:
а) ;
б) ;
в) ;
г) ;
д) .
16. Для следующих формул найти СДНФ и СКНФ, каждую двумя способами (путем равносильных преобразований и таблиц истинности):
а) ;
б) ;
в) ;
г) ;
д) .
17. Докажите равносильность формул и сравнением их совершенных нормальных форм (коньюнктивных и дизьюнктивных).
18. Составить РКС для формул, предварительно упростив их:
а) ;
б) .
19. Построить РКС для F(x,y,z), если известно, что
а) F(1,1,0)=F(1,1,1)=1;
б) F(0,0,1)=F(1,0,1)= F(1,0,0)=1.


Глава 2