Тема 10.Применение аппарата алгебры логики к решению содержательных задач.

▪ Перевод выражений естественного языка на язык алгебры логики.

▪ Решение простейших задач.

▪ Задачи, решение которых сводиться к поиску минимальной ДНФ или минимальной КНФ.

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

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

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

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

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

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

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

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

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

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

А₂ ˅ Б₅ = 1, В₂ ˅ Д₃ = 1, Г₁ ˅ Б₃ = 1, А₃ ˅ Е₆ = 1, В₃ ˅ Е₄ = 1.

Но тогда будет истинной и формула L = (А₂ ˅ Б₅ )˄( В₂ ˅ Д₃ ) ˄( Г₁ ˅ Б₃ ) ˄( А₃ ˅ Е₆ ) ˄( В₃ ˅ Е₄).

Путем простых равносильных преобразований легко показать, что L = А₃˄Б₅˄В₂˄Г₁˄Е₄ . Но L = 1 и, зна­чит, А₃ = 1, Б₅ = 1, В₂ = 1, Г₁ = l, Е₄ = 1, что и дает от­вет на вопрос задачи.

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

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

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

А_А, К_к, Д_д, Ф_ф, Д_Д, но есть мальчик Y_x такой, что истинна конъюнкция

Х_Ф ˄Y_x˄ К_Y .

Очевидно, что X ≠ Ф, X ≠ К, Y ≠ Ф, Y ≠ К.

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

1) Х = А и Y = Д,

2)Х = ДиY = А.

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

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

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

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

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

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

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

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

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

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

Б	Д	С	Б ˄	Б ˄ С&Б	˄	L
1	1	1	0	0	0	0
1	1	0	0	1	0	1
1	0	1	1	0	0	1
1	0	0	1	1	0	1
0	1	1	0	0	1	1
0	1	0	0	0	0	0
0	0	1	0	0	1	1
0	0	0	0	0	0	0

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