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

МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

Для решения логических задач нужно:

1. Внимательно изучить условие.

1. Выделить элементарные (простые) высказывания и обозначить их - как принято-большими латинскими буквами.
2. Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные при помощи логических операций &, V - и т. п.
3. Полученное выражение упростить, используя законы алгебры логики; преобразуя выражение, заменить заведомо истинные или ложные высказывания (в соответствии с условием задачи) их значением.
4. Выбрать решение - набор значений простые высказываний, при котором выражение (п.3) является истинным.
5. Проверить, удовлетворяет ли полученное решение условию задачи.

Рассмотрим несколько задач.

ЗАДАЧА 1

Три друга, Андрей (А), Василий (В) и Степан (С), получили три путевки на три смены в спортивный лагерь. Андрей имеет возможность поехать в лагерь в первую или вторую смену, Василий - в первую или третью, а Степан - во вторую или третью. Можно ли удовлетворить желания всех троих и сколькими способами?

Решение

Рассмотрим простые высказывания:

С₂=(желание Степана поехать во вторую смену),

А₁=(желание Андрея поехать в первую смену) и т.д.

Желания друзей выразятся следующим образом:

А₁ V А₂=1 (желание Андрея),

В₁ V В₃=1 (желание Василия),

С₂ V С₃=1 (желание Степана).

Чтобы определить, как одновременно удовлетворить желания всех троих, образуем конъюнкцию (умножение) написанных выше сумм:

(А₁ V А₂) & (В₁ V В₃) & (С₂ V С₃)=

(А₁ & В₁ V А₁ & В₃ V А₂ & В₁ V А₂ & В₃)*(С₂ V С₃)=

А₁ & В₁ & С₂ V А₁ & В₁ & С₃ V А₁ & В₃ & С₂ V А₁ & В₃ & С₃ V

0 0 1 0

А₂ & В₁ & С₂ V А₂ & В₁ & С₃ V А₂ & В₃ & С₂ V А₂ & В₃ & С₃ =

0 1 0 0

А₁В₃С₂ + А₂В₁С₃.

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

1. Андрею - первая смена, Стеïан - вторая смена, Василию - третья смена;

1. Василий - первая смена, Андрей - вторая смена, Стеïан - третья смена.

ЗАДАЧА 2

Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники скрылись на синем “Бъюике”, Джонс сказал, что это был черный “Крайслер”, а Смит утверждает, что это был “Форд Мустанг” и ни в коем случае не синий. Стало известно, что, желая запутать следствие, каждый из них указал правильно либо только марку машины, либо только её цвет.

Какой марки и цвета был автомобиль?

Решение.

Рассмотрим простые высказывания:

А = (машина синего цвета),

В = (машина марки “Бъюик”),

С = (машина черного цвета),

D = (машина марки “Крайслер”),

Е = (машина марки “Форд Мустанг”).

Так как либо цвет, либо марка машины каждым из соучастников названа верно, то из их слов можно заключить, что:

A V B = 1 (из слов Брауна),

C V D = 1 (из слов Джонса),

A V E = 1 (из слов Смита).

Если все эти истинные высказывания логически перемножить, то получится истинное сложное высказывание:

(A V B) & (C V D) & (A V E) = 1 & 1 & 1 = 1.

По аналогии с алгеброй чисел выполним преобразование левой части этого выражения:

(A&C& A) V (A&C&E) V (A&D& A) V (B&C& A) V (A&D&E) V

0 0 0 1 0

(B&C&E) V(B&D& A) V (B&D&E) = 1

0 0 0

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

Единственное выражение, значение которого может быть истинным это B&C& A =1, т.е. автомобиль был черного цвета марки “Бъюик”.

ЗАДАЧА 3

Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предложения:

Алеша: “Это сосуд греческий и изготовлен в V веке”.

Боря: “Это сосуд финикийский и изготовлен в III веке”.

Гриша: “Это сосуд не греческий и изготовлен в IV веке”.

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

Где и в каком веке изготовлен сосуд?

Решение.

Рассмотрим простые высказывания:

А = (сосуд греческий),

В = (сосуд финикийский),

С = (сосуд изготовлен в III веке),

D = (сосуд изготовлен в IV веке),

Е = (сосуд изготовлен в V веке).

Запишем предположения школьников на языке алгебры логики.

А V Е = 1 (слова Алеша),

В V С = 1 (слова Бори),

А V D = 1 (слова Гриши).

Если все эти высказывания логически перемножить, то получится истинное сложное высказывание:

(A V E)&(B V C)&(A V D) = 1

Раскроем скобки:

A&B &A V A&B&E V A&A&C V A&E&C V D&A&B V

0 1 0 0 0

D&B&E V D&A&C V D&E&C.

0 0 0

Исходя из того, что сосуд мог быть изготовлен только в одной стране и в одном веке, нули в равенстве означают, что получились несовместимые условия.

Единственное выражение, значение которого может быть истинным это E&B& A = 1.

Мы установили, что сосуд финикийский и изготовлен в V веке, что удовлетворяет условию задачи.

ЗАДАЧА 4

Виктор, Роман, Леонид и Сергей заняли на математической олимпиаде четыре первых места. Когда их спросили о распределении мест, они дали три таких ответа:

1. Сергей -первый, Роман - второй;

2. Сергей - второй, Виктор - третий;

3. Леонид - второй, Виктор - четвертый.

Известно, что в каждом ответе только одно утверждение истинно.

Как распределились места?

Решение.

Рассмотрим простые высказывания:

С₁ = (Сергей занял первое место),

Р₂ = (Роман занял второе место),

С₂ = (Сергей занял второе место),

В₃ = (Виктор занял третье),

Л₂ = (Леонид занял второе место),

В₄ = (Виктор занял четвертое место).

На языке алгебры логики ответы ребят можно записать следующим образом:

С₁ V Р₂ = 1,

С₂ V В₃ = 1,

Л₂ V В₄ = 1.

Конъюнкция истинных высказываний истинна. Следовательно, имеет место равенство:

(С₁ V Р₂) & (С₂ V В₃) & (Л₂ V В₄ ) = 1.

Раскроем скобки:

С₁&С₂&Л ₂ V C₂&Р₂&Л₂ V С ₁&В₃&Л₂ V Р₂&В₃&Л₂ V С₁&С₂&В₄ V

0 0 1 0 0

V С₂&Р₂&В₄ V С₁&В₃&В₄ V Р₂&В₃&В₄

0 0 0

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

Единственное выражение, значение которого может быть истинным это

С₁&В₃&Л₂ = 1.

Другими словами, места на олимпиаде распределились так:

Сергей - 1-е место,

Леонид - 2-е место,

Виктор - 3-е место,

Роман - 4-е место.

ЗАДАЧА 5

“КОМИССАР МЕГРЭ”

Мегрэ, вернувшись домой, позвонил на набережную Орфевр.

— Говорит Мегрэ. Есть новости?

— Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян, и убийство произошло после полуночи. Инспектор Люка просил передать вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила…

— Все. Спасибо. Этого достаточно. — Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.

Решение

Рассмотрим следующие простые высказывания:

А= {Франсуа был пьян},

В= {Этьен убийца},

С= {Франсуа лжет},

D= {убийство произошло после полуночи}.

Перепишем на языке алгебры логики условие задачи. Инспектора комиссара Мегрэ установили, что

А (ВV С)=1,

В V (А& D)=1,

D (ВV С)=1.

Сам Мегрэ знает, что

А & С=1.

Истинной будет и конъюнкция четырех высказываний:

(A (B V C) & (B V (A & D)) & (D (B V C)) & (A & C).

(Ответ: Франсуа был пьян, Этьен убийца, Франсуа лжет, убийство произошло после полуночи.)

ЗАДАЧА 6.

По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:

1. Если Иванов не виновен или Петров виновен, то Сидоров виновен.

1. Если Иванов не виновен, то Сидоров не виновен.

Виновен ли Иванов?

Решение

Рассмотрим простые высказывания:

А= Иванов виновен,

В= Петров виновен.

С= Сидоров виновен.

Запишем на языке алгебры логики факты, установленные следствием:

(A V B) C и A C.

Пусть F(A,B,C)= ((A V B) C) & (A C).

Решить задачу — это значит указать, при каких значениях А это сложное высказывание истинно. Сложное высказывание истинно только когда А — истинно, т.е. Иванов виновен в ограблении.