Решение логических задач с помощью алгебры логики

Пример 1. Четыре ученицы: Маша (М), Нина (Н), Ольга (О) и Поля (П) участвовали в соревнованиях и заняли первые 4 места. На вопрос, кто какое место занял, было дано 3 ответа:

1) О – второе, П – третье;

2) О – первое, Н – второе;

3) М – второе, П – четвертое.

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

Решение. Введем булевы переменные: х – «О – второе», у – «П – третье», z – «О – первое», t – «Н – второе», u – «М – второе», n – «П – четвертое». Получим систему уравнений: так как если x истинно, тогда y ложно, а – истинно и либо Аналогично, Удобнее записать эту систему следующим образом:

Отсюда или окончательно,

Кроме того, так как одна ученица не может занять 2 места и одно место не может быть занято двумя ученицами. В результате в последнем уравнении останется единственный ненулевой член Отсюда или О – первая, М – вторая, П – третья, Н – четвертая.

Пример 2. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные, а один рыжие волосы, но ни у кого цвет волос не совпадает с фамилией», – заметил черноволосый. «Ты прав», – сказал Белов. Какой цвет волос у художника?

Решение. Составим таблицу.

Фамилия Цвет волос	Б	Ч	Р
б
ч
р

Фамилия Цвет волос	Б	Ч	Р
б
ч
р

Невозможное сочетание фамилии и цвета волос будем обозначать 0, возможное 1. Очевидно, что в каждой строке и в каждом столбце должна быть только одна 1. Получим два варианта.

Фамилия Цвет волос	Б	Ч	Р
б
ч
р

Из условия задачи ясно, что черноволосый не Белов, поэтому первый вариант не подходит. Следовательно, Белов – рыжий, Чернов – белый, Рыжов – черный.

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

1. Андреев: «Я убирал 9-ый класс, а Савельев - 7-ой».

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

3. Савельев: «Я убирал 8-ой класс, а Костин - 10-ый».

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

11. Семья, состоящая из отца А, матери В и трех дочерей С, D_, Е купила телевизор. Условились, что в первый вечер будут смотреть передачи в таком порядке:

1. Когда отец А смотрит передачу, то мать В делает то же.

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

3. Из двух членов семьи - мать В и дочь С - смотрят передачу одна и только одна.

4. Дочери С и D или обе смотрят, или обе не смотрят.

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

Кто из членов семьи в этот вечер смотрит передачу?

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

1. Если первый сдал, то и второй сдал.

2. Если второй сдал, то третий сдал или первый не сдал.

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

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

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

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

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

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

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

Список литературы:

1. Л.М. Лихтарников, Т.Г. Сукачева Математическая логика/ Курс лекций/-СПб.: Издательство «Лань», 1998.

2. С.Д. Шапорев Математическая логика. Курс лекций и практических заданий.- СПб. БХВ- Петербург, 2005.

3. В.Ф. Пономарев Математическая логика. часть 1. Логика высказываний. Логика предикатов. Учебное пособие – Калининград: КГТУ, 2001, с.140

Дата добавления: 2014-01-05