8.2. Решение логических задач с помощью теории булевых функций

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

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

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

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

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

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

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

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

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

Решение. Будем обозначать высказывания зрителей Х_k , где Х – первая буква имени участника турнира, а k – номер места, которое он занял в турнире. В высказываниях зрителей одно высказывание может быть ложным, поэтому будут истинными дизъюнкции этих высказываний А₂ Б₅, В₂  Д₃ , Г₁ Б₃ , А₃  Е₆ , В₃ Е₄. Но тогда истинной будет конъюнкция : K= (А₂ Б₅)(В₂ Д₃)(Г₁ Б₃ )(А₃  Е₆)(В₃ Е₄ ) = 1.

Учитывая, что Х_k Х_п = 0 при k  п и Х_kY_k = 0 при X Y, получаем путем последовательного раскрытия скобок в К:

К = (А₂Д₃ Б₅В₂ Б₅Д₃)( Г₁А₃ Г₁Е₆ Б₃Е₆)(В₃ Е₄) =

= (А₂Д₃Г₁Е₆ Б₅В₂Г₁А₃  Б₅В₂Г₁Е₆  Б₅Д₃Г₁Е₆)(В₃ Е₄) =  А₃Б₅В₂Г₁Е₄ = 1

Полученное соотношение дает распределение первых 5 мест и автоматически получаем, что Денис был шестым т. е. Д₆ = 1.

Пример 2. По подозрению в совершении преступления задержали Брауна, Джонса и Смита. Вот что они показали:

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

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

Смит: Я не виноват. Виновен Браун.

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

Решение. Обозначим буквами B, D, C высказывания: виноват Браун, виноват Джонс, виноват Смит соответственно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций  , из которых по условию задачи, две ложны, а одна истинна. Истинной будет формула ,  но из этой формулы решение получится только дополнительным рассуждением: пусть B = 1, тогда по условию C = 0 и D = 0. Но тогда из трех конъюнкций, составляющих К две будут верны:  , а это противоречит условию. Значит В=0. Видно, что C=1 удовлетворяет условию задачи, и это решение единственно, так как если предположить, что D = 1, то это будет означать, что  , а значит, что либо В, либо С равно 1, но это противоречит тому, что преступник только один.

Таким образом, преступник – Смит, оба его высказывания ложны, у Брауна одно высказывание ложно, одно нет, а Джонс сказал правду.

Все эти рассуждения используются не только для решения логических задач (которые действительно приходится решать следователям), но и для составления игровых программ (компьютерная игра ШЕРЛОК, содержащая больше 60 тыс. логических задач, составлена с использованием тех же самых конъюнкций, дизъюнкций и отрицаний).