Решение логических задач методами алгебры логики

Схема использования методов алгебры логики для решения логических задач следующая. По условию логической задачи строим некоторую формулу алгебры логики. Потом эквивалентными преобразованиями упрощаем эту формулу. Простейший вид формулы алгебры, как правило, дает ответы на вопросы логической задачи.

Пример 1

Пытаясь вспомнить победителей турнира прошлого года, пять зрителей, присутствующих на турнире, заявили:

1) Антон был вторым, а Борис – пятым;

2) Виктор был вторым, а Денис – третий;

3) Григорий был первым, а Борис – третий;

4) Антон был третий, а Евгений – шестым;

5) Виктор был третий, а Евгений – четвертым.

Впоследствии оказалось, что каждый зритель ошибся в одном из своих высказываний. Как на самом деле распределились места в турнире?

Выполнение. Обозначим высказывания зрителей логическими переменными , где – первая буква имени участника ( для Антона, для Бориса, для Дениса, для Евгения, для Григория, для Виктора), а – место, которое он занял в турнире. Например, высказывание «Антон был третий» обозначается как .

По условию задачи каждый зритель ошибся в одном из своих высказываний, а другое его высказывание – истинно. Поэтому можно записать:

, , , , .

А если это так, то

.

Раскроем скобки, учитывая, что, например, (один участник турнира не может занять два места), (два участника турнира не могут занять одно место):

,

,

,

.

Таким образом

,

А это возможно, если

, , , , .

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

1) Григорий;

2) Виктор;

3) Антон;

4) Евгений;

5) Борис;

6) Денис.∎

Пример 2

Было четыре мальчика: Андрей, Кирилл, Дмитрий, Федор. Их фамилии Андриенко, Карп, Демченко, Федун (какая в какого мальчика неизвестно). Известно, что первая буква имен мальчиков не совпадает с первой буквой их фамилий. Кроме того, фамилия Дмитрия не Андриенко. Необходимо определить фамилию каждого мальчика, если известно, что первая буква имени Федуна есть первая буква фамилии мальчика, первая буква имени которого – первая буква фамилии Кирилла.

Выполнение. Сопоставим каждому мальчику логическую переменную , где первая буква имени мальчика ( для Андрея, для Кирилла, для Дмитрия, для Федора), а первая буква фамилия мальчика ( для Андриенка, для Карпа, для Демченка, для Федуна).

По условию задачи

, , , , , .

Очевидно, что , , ,

Возможны два случаи:

1) , ;

2) , ;

Первый случай, однако, невозможный, потому что при этом , а по условию задачи .

Поэтому имеет место второй случай, при котором . и в результате фамилии мальчиков следующие: Андрей Демченко, Дмитрий Федун, Кирилл Андриенко, Федор Карп.∎

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 2

Упражнение 1. По подозрению в совершении преступления были задержаны Браун, Джон и Смит. Один из них уважаемый в городе старый человек, второй малоизвестный чиновник и третий известный мошенник. В ходе следствия оказалось, что уважаемый человек всегда говорил правду, известный мошенник всегда лгал, а чиновник в одном случаи говорил правду, в другом – обманывал. Задержанные сказали следующие:

Браун: «Я сделал это, Джон не виновен»;

Джон: «Браун не виновен. Преступление совершил Смит»;

Смит: «Я не виновен, виновен Браун».

Необходимо определить имена троих задержанных, и кто с них виновен, если известно, что преступник один.

Выполнение. Высказываниям «Виновен Браун», «Виновен Джон», «Виновен Смит» сопоставим логические переменные , , соответственно. Тогда высказывания задержанных можно записать в виде конъюнкций , , , две из которых, по условию задачи, равны 0, а одна 1. Поэтому можно записать

.

Построим таблицу истинности этой формулы.

Видно, что на словах 001, 011, 100, 101, 110. На словах 011, 101, 110 две с переменных , , равны 1, что противоречит условию задачи (преступник один). На слове 100 две из конъюнкций , , равны 1, что также противоречит условию задачи. Остается только одно слово 001, то есть преступник Смит, а Джон и Браун не виновные. На слове 001 =1, что соответствует высказыванию «Браун не виновен. Преступление совершил Смит». А оно принадлежит Джону, т.е. Джон – уважаемый в городе старый человек. Браун один раз сказал правду (Джон не виноват) и один раз солгал (Я сделал это), поэтому он малоизвестный чиновник.

В результате:

Смит – известный махинатор и совершил преступление;

Джон – уважаемый в городе старый человек;

Браун – малоизвестный чиновник.

УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. В школе старшеклассникам Андриенку, Константинову, Савину и Давыдову поручили убрать 7-й, 8-й, 9-й, 10-й классы. После проверки оказалось, что 10-й класс убран плохо. Оставшиеся в школе ученики, сообщили:

· Андриенко: «Я прибирал 9-й класс, а Савин – 7-й»;

· Константинов: «Я убирал 9-й класс, а Андриенко – 8-й»;

· Савин: «Я убирал 8-й, Константинов – 10-й».

Давыдов ничего не сказал, так как ушел домой до проверки. В дальнейшем оказалось, что каждый ученик в одном из двух высказываний сказал правду, а в другом – солгал.

Кто какой класс убирал?

2. На вопрос «Кто с трех студентов изучал математическую логику?» получен верный ответ: «Если изучал первый, то изучал и третий, не верно, что если изучал второй, то изучал и третий». Кто изучал математическую логику?

3. Определить, кто с четырех студентов сдал экзамен, если известно:

· если первый сдал, то и второй сдал;

· если второй сдал, то третий сдал или первый не сдал;

· если четвертый не сдал, то первый сдал, а третий не сдал;

· если четвертый сдал, то сдал и первый.

4. Известно, что:

· если Петр не видел Николая на улице, то или Николай ходил в кино, или Петр сказал правду;

· если Николай не ходил в кино, то Петр не видел Николая на улице, и Николай сказал правду;

· если Николай сказал правду, то он или ходил в кино, или Петр солгал.

Так ходил ли в кино Николай, или нет?

5. Студентки Валентина, Елена, Светлана, Виктория посещают институт по очереди и ведут общий конспект лекций. Необходимо составить график посещения института на следующую неделю, если:

· Понедельник – день самостоятельной работы, в институт не ходит никто, а в субботу необходимо быть всем.

· Светлана и Виктория не могут посетить занятия во вторник, через большую загруженность в понедельник.

· Если Светлана выйдет в среду, или Виктория – в четверг, то Елена согласится посетить занятие в пятницу.

· Если Валентина не пойдет в институт в четверг, то Лена разрешит себе пойти туда в среду.

· Если Валентина или Виктория будут в институте в середу, то Светлана сможет пойти в пятницу.

· Если Виктория в пятницу пойдет на свадьбу подруги, то Валентина будет вынуждена пойти в институт во вторник, а Светлана – в четверг.

6. Однажды следователю пришлось допрашивать одновременно трех свидетелей: Клода, Жака и Дика. Их показания противоречили одно другому, и каждый из них обвинял кого-то во лжи.

· Клод утверждал, что Жак обманывает.

· Жак обвинил во лжи Дика.

· Дик умолял не верить ни Клоду, ни Жаку.

Но следователь быстро вывел свидетелей на чистую воду, не задав при этом ни одного вопроса. Кто из свидетелей говорил правду?

7. Четверо друзей – Антонов, Вехов, Сомов и Деев решили провести каникулы в четырех разных городах – Одессе, Киеве, Ташкенте, Москве. Определить, в какой город должен поехать каждый, при следующих ограничениях.

Если Антонов не едет в Москву, то Сомов не едет в Одессу.

Если Вехов не едет ни в Москву, ни в Ташкент, то Антонов едет в Москву.

Если Сомов не едет в Ташкент, то Вехов едет в Киев.

Если Деев не едет в Москву, то и Вехов не едет в Москву.

Если Деев не едет в Одессу, то Вехов не едет в Москву.

8. Семья, состоящая с отца, матери и трех дочек – Светланы, Дианы и Елены, купила телевизор. Договорились еще с первого вечера смотреть передачи в соответствии с условиями.

Если отец смотрит передачу, то мать делает, то же самое.

Дочери Диана и Елена, обе или одна с них смотрит передачу.

С двух членов семьи – мать и дочка Светлана – смотрит передачу одна и только одна с них.

Дочери Светлана и Диана или обе смотрят телевизор, или не смотрит никто.

Если дочь Елена смотрит передачу, то отец и дочь Диана делают то же самое.

В каком порядке семья смотрела телевизор?