Решение логических задач

Основные понятия

Логические задачи обычно формируются на естественном языке. ДЛя решения задачи применяются различные методы: рассуждение, алгебраический, табличный, графический. Рассмотрим некоторые из них.

Алгебраический метод

Задача №1. В школе в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На аудиториях повесили шутливые таблички, про которые известно, что они либо обе истинны, либо обе ложны. На первой аудитории повесили табличку "По крайней мере, в одной из этих аудиторий размещается кабинет информатики", а на второй аудитории - табличку с надписью "Кабинет физики находится в другой аудитории". Определите, какой кабинет размещается в каждой из аудиторий.
Переведем условие задачи на язык алгебры логики. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть:
А - "В первой аудитории находится кабинет информатики";
В - "Во второй аудитории находится кабинет информатики".
Поскольку в каждой аудитории обязательно размещается какой-либо из этих двух кабинетов, отрицания этих выскаэываний будут соответствовать:
А - "В первой аудитории находится кабинет физики";
В - "Во второй аудитории находится кабинет физики".
Высказывание, содержащееся на табличке первой аудитерии, соответствует логическому выражению: Х = А v В.
Высказывание, содержащееся на табличке второй аудитерии, соответствует логическому выражению: Y = ¬А.
Содержашееся в условии задачи утверждение о том, что надписи на табличках либо одновременно истинные, либо одновременно ложные, соответствует истинности функции эквивалентности:
(X & Y) \/ (¬X & ¬Y) = 1.
Подставим вместо Х и Y соответствующие логические выряжения: ((А v В) & ¬A) v (¬(А v В)& ¬¬A) = 1.

Упрощаем выражение и получим: (0 v В & ¬A) v 0 = B & ¬A

Полученное логическое выражение оказалось простым, и поэтому его можно проанализировать без построения таблицы истинности. Для того чтобы выполнялось равенство, обе логические переменные должны быть равны 1, а соответствующие им высказывания истинны:
"Во второй аудитории находится кабинет информатики. В первой аудитории находится кабинет физики".

Метод рассуждения

Задача №2. Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:
А) Макс победит, Билл – второй;
В) Билл – третий, Ник – первый;
С) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс?

Для решения задачи целесообразно составить таблицу:

запишем высказывания трех болельщиков в форме таблицы (заголовок строки обозначает место в турнирной таблице).

Считая, что два человека не могут оказаться на одном месте, начнем "раскручивать" эту таблицу с той строчки, где больше всего информации (в данном случае - с первой)
- Предположим, что Макс действительно занял первое место, как и сказал "A"; в этом случае "C" ошибся, поставив на первое место Джона;
- учитывая, что каждый один раз угадал, а второй ошибся, получается, что "C" угадал, что Макс будет на четвертом месте;
- но мы предположили, что Макс - на первом месте (а не на четвертом), следовательно, получили противоречие; это значит, что Макс все-таки не на первом месте
- таким образом, в первом прогнозе "А" ошибся, это значит, что во втором он угадал, и Билл действительно занял второе место:

так как Билл - второй, он не может быть на третьем месте, поэтому из прогноза "Б" следует, что Ник - первый

- если Ник на первом месте, там не может быть Джон, поэтому из ответов "С" (среди которых должен быть один верный, и один неверный), сразу находим, что Макс занял четвертое место

- осталось только определиться с Джоном - ему досталось единственное "свободное" третье место; окончательный список победителей: 1.Ник 2.Билл 3.Джон 4.Макс

Загадка Эйнштейна

Задача №3. На одной улице стоят в ряд 4 дома, в каждом из них живет по одному человеку. Их зовут Василий, Семен, Геннадий и Иван. Известно, что все они имеют разные профессии: скрипач, столяр, охотник и врач. Известно, что:
(1) Столяр живет правее охотника.
(2) Врач живет левее охотника.
(3) Скрипач живет с краю.
(4) Скрипач живет рядом с врачом.
(5) Семен не скрипач и не живет рядом со скрипачом.
(6) Иван живет рядом с охотником.
(7) Василий живет правее врача.
(8) Василий живет через дом от Ивана.
Определите, кто где живет, и запишите начальные буквы имен жильцов всех домов слева направо.

1) из условий (1) и (2) следует, что охотник живет не с краю, потому что справа от него живет столяр, а слева - врач;
2) скрипач по условию (3) живет с краю, он может жить как слева, так и справа от них:
скрипач?врачохотникстолярскрипач?
3) по условию (4) скрипач живет рядом с врачом, поэтому он занимает крайний дом слева:
1234
скрипачврачохотникстоляр
4) профессии жильцов определили, остается разобраться с именами
5) из условия (5) "Семен не скрипач и не живет рядом со скрипачом" следует, что Семен - охотник или столяр:
1234
скрипачврачохотникстоляр
Семен?Семен?
6) из условия (6) "Иван живет рядом с охотником" следует, что он - врач или столяр:
1234
скрипачврачохотникстоляр
Семен?Семен?
Иван?Иван?
7) из условия (7) "Василий живет правее врача" определяем, что Василий - охотник или столяр
1234
скрипачврачохотникстоляр
Семен?Семен?
Иван?Иван?
Василий?Василий?
8) из условия (8) "Василий живет через дом от Ивана" находим, что Иван - врач, а Василий -столяр:
1234
скрипачврачохотникстоляр
ИванСемен?Василий
9) тогда сразу получается, что Семен - охотник, а Геннадий должен занять оставшееся свободное место, он - скрипач:
1234
скрипачврачохотникстоляр
ГеннадийИванСеменВасилий