4.2. Решение логических задач с помощью алгебры логики.
Условие логической задачи с помощью соответствующих обозначений записывают в виде формулы алгебры логики. После равносильных преобразований формулы получают ответ на все вопросы задачи.
Обычно используется следующая схема решения:
изучается условие задачи;
вводится система обозначений для логических высказываний;
конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
определяются значения истинности этой логической формулы;
из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.
Пример 4.4.После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:1) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;2) если поедут Арбузов и Вишневский, то поедет и Брюквин. Требуется:
а) ввести краткие обозначения для сформулированных условий и составить логическую формулу, выражающую принятое решение в символической форме;
б) для полученной формулы найти возможно более простую равносильную формулу;
в) пользуясь найденной более простой формулой, дать новую и более простую словесную формулировку принятого решения о составе участников экспедиции.
Решение.
а)Нам даны сложные
высказывания .Выделим из них простые
высказывания. Назначение в экспедицию
Арбузова, Брюквина и Вишневского
обозначим буквами А,
Б,В соответственно.
Тогда условие 1) можно записать в виде
,
а условие 2) в виде
.
Так как оба условия должны выполняться
одновременно, то они должны быть
соединены логической связкой «и».
Поэтому принятое решение можно записать
в виде следующей символической формулы:
.
б)Упростив, полученную
формулу ,получим более простую
равносильную формулу:
в)Символическую формулу читаем так: «Если поедет Арбузов, то поедет и Брюквин». Это и есть наиболее простая словесная формулировка принятого решения о составе экспедиции.
Пример 4.5.Определить истинность высказывания: За окном светит солнце и нет дождя.
Решение.
Нам дано сложные
высказывания. Выделим из них простые
высказывания: A-
за окном светит солнце, B-
за окном дождь. Составим логическую
формулу соответствующую данному
высказыванию
.Построим
таблицу истинности для данной логической
функции:
|
|
|
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
Логическое выражение
принимает значение истина только на
наборе
данное
нам высказывание истинно, тогда и только
тогда, когда первое простое высказывание
истинно, а второе ложно.
Пример 4.6.На языке алгебры логике составьте истинное тождество, соответствующее заданному условию задачи: Школьник Миша, оставшийся в классе на перемене был вызван к директору по поводу разбитого в это время окна в кабинете. На вопрос директора :Кто это сделал, мальчик ответил: «Я не бил окно и Коля тоже». Известно, что он либо скажет чистую правду, либо в одной части заявления соврал, а другое его высказывание истинно, либо оба факта исказил.
Решение.
Составим простые высказывания: К – Коля разбил окно; М- Миша разбил окно.
Запишем формулы соответствующие сложным высказываниям:
-Я
не бил окно и Коля тоже (сказал чистую
правду);
-
Миша не бил окно, Коля разбил окно или
Миша разбил окно , а Коля не бил окно(
либо в одной части заявления соврал, а
другое его высказывание истинно);
-
Коля разбил окно и Миша разбил окно (оба
факта исказил).
Все три факта
истинны по условию
,
,
Составим истинное тождество, соответствующему заданному условию задачи:
.
Пример 4.7. По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом ложь. Вот, что они утверждали:
Браун: «Я совершил это. Джон не виноват».
Джон: «Браун не виноват. Преступление совершил Смит».
Смит: «Я не виноват, виновен Браун».
Определите имя старика, мошенника, чиновника и кто из них виноват, если известно, что преступник один.
Решение.
Обозначим
буквами Б,
Д,
С
высказывания: виноват Браун, виноват
Джон, виноват Смит соответственно.
Утверждения задержанных можно записать
в виде конъюнкций:
,
,
,
из которых по условию задачи, две ложны,
а одна истинна. Поэтому будет истинной
формула Ф =
.
Таблица истинности этой формулы:
Б |
Д |
С |
|
|
|
Ф |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Формула Ф истинна в пяти из восьми случаев. Случай 5 следует исключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит условию задачи. В случаях 4, 6, 7 оказываются истинными по два высказывания Д и С, Б и С, Б и Д соответственно, что также противоречит условию задачи. Следовательно справедлив случай 2, то есть преступник Смит. Он известный мошенник, оба его высказывания ложны: . При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон уважаемый в городе старик, а Браун малоизвестный чиновник.