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

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

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

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

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

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

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

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

Б Ù Ø Д, Ø Б Ù С, Б Ù Ø С,

из которых, по условию задачи, две ложны, а одна ис­тинна. Поэтому будет истинной формула

L = (Б Ù Ø Д) Ú (Ø Б Ù С) Ú (Б Ù Ø С).

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

Из таблицы видно, что формула L истинна в пяти из восьми случаев. Случай, представленный в пятой строке, следует ис­ключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит усло­вию задачи. В строках 4, 6 и 7 оказываются истинными по два высказывания: Д и С, Б и С, Б и Д, соответственно, что также противоречит условию задачи. Следователь­но, справедлив случай 7, то есть преступник – Смит. Он – известный мошенник, и оба его высказывания лож­ны: Б Ù Ø С º 0. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон – уважаемый в городе старик, а Браун – Малоизвестный чиновник.

Date: 2015-04-23; view: 875; Нарушение авторских прав