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

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

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

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

1. Антон был вторым, а Борис - пятым.

2. Виктор был вторым, а Денис - третьим.

3. Григорий был первым, а Борис - третьим.

4. Антон был третьим, а Евгений - шестым.

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

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

Решение. Будем обозначать высказывания зрителей символом Х_у, где X - первая буква имени участника турнира, а у - номер места, которое он занял в турнире. Так как в паре высказываний каждого зрителя одно истинно, а второе ложно, то будут истинными дизъюнк­ции этих высказываний

.

Но тогда будет истинной и формула

.

Путем простых равносильных преобразований легко показать, что . Но L l и, зна­чит, , что и дает от­вет на вопрос задачи.

Пример 2. Жили четыре мальчика: Альберт, Карл, Дидрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковы. Кроме того, фамилия Дидриха не была Аль­берт. Требуется определить фамилию каждого из мальчи­ков, если известно, что имя мальчика, у которого фами­лия Фридрих, есть фамилия того мальчика, имя которо­го - фамилия Карла.

Решение. Поставим в соответствие каждому маль­чику символ , где Х - имя, а У - фамилия мальчика.

Тогда по условию задачи ложны высказывания:

,

но есть мальчик У_Х такой, что истинна конъюнкция

.

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

Х не равносильно Ф

Х не равносильно К

У не равносильно Ф

У не равносильно К.

Тогда возможны два случая:

1) Х А и У Д,

2) X Д и У А

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

Следовательно, имеет место второй случай. Значит, Дидрих имеет фамилию Фридрих, Альберт имеет фами­лию Дидрих, Карл имеет фамилию Альберт, а Фридрих имеет фамилию Карл.

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

Браун: «Я совершил это. Джон не виноват».

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

Смит».

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

Определите имя старика, мошенника и чиновника и кто из них виноват, если известно, что преступник один.

Решение. Обозначим буквами Б, Д и С высказывания: виноват Браун, виноват Джон, виноват Смит соответст­венно. Тогда утверждения, высказанные задержанными,

можно записать в виде конъюнкций: , , , из которых, по условию задачи, две ложны, а одна ис­тинна.

Поэтому будет истинной формула

.

Таблица истинности этой формулы имеет вид:

Б	Д	C				L

Отсюда видно, что формула L истинна в пяти из восьми занумерованных случаев. Случай 4 следует ис­ключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит усло­вию задачи. В случаях 2, 3 и 5 оказываются истинными по два высказывания: Б и Д, Б и С, Д и С соответственно, что также противоречит условию задачи. Следователь­но, справедлив случай 7, то есть преступник - Смит. Он - известный мошенник, и оба его высказывания лож­ны: . При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон - уважаемый в городе старик, а Браун - малоизвестный чиновник.

Часть II

Задачник-практикум

По математической

логике
ГЛАВА I

АЛГЕБРА ЛОГИКИ