Математическая логика
1. Доказать тождественную истинность или ложность формул:
а) х 
у 
х;
б) х (хÚу);
в) (х 
)) 
((
) (
)).
2. Выразить все основные операции:
а) через конъюнкцию и инверсию;
б) через дизъюнкцию и инверсию.
3. Выразить операцию дизъюнкции через импликацию.
4. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино. а если будет хорошая погода - пойти на реку искупаться. В каком случае можно сказать, что решение мальчика не выполнено? В ответе отрицания должны содержаться лишь в простых высказываниях.
5. Доказать равносильность:
а) х 
у 
;
б) х (x 
) Ú (x 
) Ú (x 
) Ú (
).
6. Упростить формулу:
(x 
y) 
y z 
z x)
7. Постройте с помощью инверсии и дизъюнкции формула, таблица истинности для которой совпадала бы с таблицей для импликации.
8. Известно, что эквивалентность х 
у истинна. Что можно сказать о значении 
у и х 
?
9. Известно, что х имеет значение 1. Что можно сказать о значениях импликации 
у 
z; (y Ú z)?
10. Известно, что х у имеет значение 1. Что можно сказать о значениях z (x 
); 
y; (x ) z?
11. Пусть х=0, у=1, z=1. Определить логические значения сложных высказываний:
х у z; ((хÚу) 
z) ((х z) Ú(у 
))
12. Запишите следующее высказывания в виде логических выражений: «Если учитель на уроке рассказывает интересно, то Маша или Саша не будут смотреть в окно»
13. Составьте таблицу истинности для выражения А→(В→(
В))
14. Докажите, что C ® U = 
15. Дан фрагмент таблицы истинности. Найдите логическое выражение, по которому она составлялась.
| X | Y | Z | ? |
16. Определить истинность логического выражения
F (A,B)= (A B) (BÚAÚB)
17. Записать в виде логической формулы высказывания: Администрация морского порта издала следующий приказ - Если капитан корабля получает специальное указание, то он должен покинуть порт на своем корабле.
18. Записать в виде логической формулы высказывания: Спортсмен подлежит дисквалификации, если он некорректно ведет себя по отношению к сопернику или судье, и если он принимал "допинг".
19. Определить, является ли предложение высказыванием. «В море соленая вода?».
20. Определите значения логических переменных A, B, C, D, если:
а) A и (10<100) - истинное высказывание;
б) B и (10<100) - ложное высказывание;
в) C или (у прямоугольника все стороны равны) - истинное высказывание;
г) D или (у прямоугольника все стороны равны) - ложное высказывание.
21.Составить таблицы истинности для следующих логических выражений:
а) 
Ú (b Ù c);
б) x Ú y Ù 
22. Запишите следующее высказывания в виде логических выражений: «Я поеду в деревню к бабушке и, если встречу там друзей, то интересно проведу время»
23. Четыре брата Коля, Володя, Петя и Юра – учатся в первом, втором, третьем и седьмом классах. Информатику в школе, в которой учатся мальчики, начинают изучать с седьмого класса. Петя учится только на «4» и «5», а младшие братья стараются брать с него пример. Володя уже изучает информатику. Юра помогает решать задачи младшему брату по математике. Кто из братьев учится во втором классе?
24. Инопланетяне сообщили, что в их системе 3 планеты А, Б, В и что они живут на второй планете. Вдруг передатчик испортился и два сообщения: А – не третья, Б – не вторая, - оказались ложными. На какой планете живут разумные существа?
25. Составьте таблицу истинности для выражения AÙ (AÚB)↔A
26. Определить истинность логического выражения F(A,B) = АÙВÚА
27. Жили четыре друга. Звали их Альберт, Карл, Дитрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковыми, кроме того, фамилия Дитриха не Альберт. Определите фамилию и имя каждого мальчика, если дано, что имя мальчика, у которого фамилия Фридрих, есть фамилия того мальчика, имя которого фамилия Карла.
28. После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:
а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;
б) если поедут Арбузов и Вишневский, то поедет и Брюквин.
Требуется установить, кто из перечисленных сотрудников войдет в состав экспедиции.
29. Записать составное высказывание в виде формулы, употребляя булевы переменные для обозначения простых высказываний.
а) если идет дождь, то дует ветер и становится холодно;
б) если дует ветер, идет дождь;
в) ветер дует тогда и только тогда, когда идет дождь;
г) неверно, что ветер дует тогда и только тогда, когда нет дождя.
30. Четыре ученицы: Маша (М), Нина (Н), Ольга (О) и Поля (П) участвовали в соревнованиях и заняли первые 4 места. На вопрос, кто какое место занял, было дано 3 ответа:
1) О – второе, П – третье;
2) О – первое, Н – второе;
3) М – второе, П – четвертое.
В каждом из этих ответов одна часть верна, а другая нет. Какое место заняла каждая девушка?
31. Во время перемены в классе были Аня, Борис, Ваня и Майя. Один из них разбил окно. На вопрос: ”Кто разбил окно?”, были даны ответы:
Аня: 1) Я не разбивала. 2) Я сидела и читала. 3) Майя знает, кто разбил.
Борис: 1) Я этого не делал. 2) С Майей я давно не разговариваю. 3) Это сделал Ваня.
Ваня: 1) Я не виновен. 2) Разбила Майя. 3) Борис лжёт, говоря, что разбил я.
Майя: 1) Я не разбивала. 2) Это вина Ани. 3) Борис знает, что я не виновна, т.е. мы с ним беседовали во время перемены.
Затем каждый признался, что из трёх ответов каждого, два – истинны, а один ложный. Кто разбил окно?
32. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные, а один рыжие волосы, но ни у кого цвет волос не совпадает с фамилией», – заметил черноволосый. «Ты прав», – сказал Белов. Какой цвет волос у художника?
33. На школьную олимпиаду по английскому языку были отправлены четверо лучших учеников из разных классов: Мария, Лариса, Кирилл и Петр. Одноклассники ребят высказали свои предположения о распределении мест между участниками олимпиады:
- «Первые два места займут Мария и Лариса соответственно», - предложил первый;
- «Кирилл может быть не лучший, но второе место – точно его! А самый слабый из четверки - «Петр!», - сказал второй спорщик;
- «третий, подумав, возразил: «Вы недооцениваете Петра, он займет третье место, а Мария будет второй, так как при всем своем уме, она плохо оформляет свои работы».
По завершении олимпиады выяснилось, что пари не выиграл никто, т. к. каждый сделал по одному неверному прогнозу. Какие места на олимпиаде заняли Мария, Лариса, Кирилл и Петр?
34. В педагогическом институте преподаватели Афанасьева, Бирюкова, Климова, Дунин, Исаев и Федоров преподают немецкий язык, английский язык, французский язык, историю, физическое воспитание и математику. Преподаватель немецкого языка и преподаватель математики в студенческие годы занимались танцами. Исаев старше Федорова, но стаж работы у него меньше, чем у преподавателя физкультуры. Будучи студентками, Афанасьева и Бирюкова учились вместе в одном университете. Все остальные окончили педагогический институт. Федоров – отец преподавателя французского языка. Преподаватель английского языка – самый старший из всех по возрасту и имеет самый большой стаж работы. Он работает в этом институте с тех пор, как окончил его. Преподаватели математики и истории - его бывшие студенты. Афанасьева старше преподавателя немецкого языка. Назовите, кто какой предмет преподает?
35. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. В каком сосуде находится квас?
36. В первом туре школьного конкурса «Эрудит» в четверку лучших вошли: Дима, Катя, Миша, и Нина. И, конечно, болельщики высказывали свои предположения о распределении мест во втором, финальном туре.
Один считал, что первым будет Дима, а Миша будет вторым.
Другой болельщик выразил надежду на то, что Катя займет четвертое место, а второе место достанется Нине.
Третий же был уверен в том, что Катя займет третье место, а на втором месте будет Дима.
В результате оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какие места заняли Дима, Катя, Миша, Нина?
37. Как – то случай свел в одном купе известного астронома, поэта, прозаика и драматурга. Это были Алексеев, Борисов, Константинов и Дмитриев. Оказалось, что каждый из них взял с собой книгу, написанную одним из пассажиров купе.
Алексеев и Борисов углубились в чтение, предварительно обменявшись купленными книгами. Поэт читал пьесу.
Прозаик, очень молодой человек, выпустивший свою книгу, говорил, что он никогда ничего не читает по астрономии.
Борисов купил в дорогу одно из произведений Дмитриева.
Никто из пассажиров не покупал и не читал книги, написанные им самим.
Что читал каждый из них? Кто кем был?
38. В семье трое детей. Тоне вдвое больше лет, чем будет Гале тогда, когда Жене исполнится столько же лет, сколько Тоне сейчас. Кто из них самый старший, кто самый младший, кто средний по возрасту?
39. Не самый прилежный ученик подал документы в престижный в уз, рассуждая при этом:
- если я сдам профилирующий экзамен – иностранный язык, - то историю я сдам при условии, что не «завалю» сочинение;
- не может быть, чтобы я «завалил» и сочинение, и иностранный язык;
- достаточным условием «завала» история является двойка по сочинению.
После экзаменов выяснилось, что ученик был достаточно прозорлив, т.к. только одно из его рассуждений оказалось ложным. Как были сданы экзамены?
40. Какие из следующих предложений являются высказываниями? Определите их истинность.
а) Стой! Кто идет?
б) Человек все может.
в) Есть ли жизнь на Марсе?
г) Некоторые рыбы - хищники.
д) Ни один внимательный человек не совершит оплошность.