Решение логических задач с помощью алгебры логики является мощным средством.
Алгоритм решения логических задач с помощью алгебры логики
-
изучение условия;
-
выделение простых высказываний, которым даются имена;
-
запись условия задачи языком алгебры логики;
-
составление конечной формулы, для чего объединяются формулы каждого утверждения с помощью логического умножения и приравнивается полученная формула единице;
-
упрощение формулы, анализ полученного результата или составление таблицы истинности, нахождение по таблице значения переменных, для которых $F=1$, анализ результатов.
Законы алгебры логики
Рисунок 1.
Примеры решения логических задач с помощью алгебры логики
Задача «Кто преступник»
Определить участника преступления, зная, что:
-
«Если Иван не участвовал или Петр участвовал, то Семен участвовал»;
-
«Если Иван не участвовал, то Семен не участвовал».
Решим задачу с помощью таблиц истинности и с помощью алгебры логики.
Решение:
Решение с помощью таблицы истинности
Пусть:
$I$ -- «Иван участвовал в преступлении»;
$P$ -- «Петр участвовал в преступлении»;
$S$ -- «Семен участвовал в преступлении».
Запишем условия задачи в виде формул:
$\overline{I}\vee P\to S$ и $\overline{I}\vee P\to \overline{S}$
Построим таблицу истинности для всех возможных наборов:
Рисунок 2.
Из таблицы видно, что преступление совершил Иван.
Решение с помощью алгебры логики
\[F\left(I,P,S\right)=\left(\overline{I}\vee P\to S\right)\wedge \left(\overline{I}\to \overline{S}\right)=\left(\left(\overline{\overline{I}\vee P}\right)\vee S\right)\wedge \left(I\vee \overline{S}\right)=\] \[=\left(I\wedge \overline{P}\vee S\right)\wedge \left(I\vee \overline{S}\right)=I\wedge \overline{P}\vee I\wedge S\vee I\wedge \overline{P}\wedge \overline{S}\vee 0=I\wedge \overline{P}\vee I\wedge S=\] \[=I\wedge \left(\overline{P}\vee S\right)\]Из получившегося выражения получаем, что выражение верно, когда $I=1$. Таким образом, преступник -- Иван.
Задача о погоде
Определить погоду на завтра, если синоптик сказал, что:
-
Если не будет ветра, то будет пасмурная погода и не будет дождя.
-
Если будет дождь, то будет пасмурно и не будет ветра.
-
Если будет пасмурная погода, то будет дождь и не будет ветра.
Решим эту задачу средствами алгебры логики.
Решение:
-
Пусть:
$A$ -- «Не будет ветра»;
$B$ -- «Пасмурно»;
$C$ -- «Дождь».
-
Запишем с помощью переменных $A$, $B$, $C$ высказывания синоптика:
Если не будет ветра, то будет пасмурная погода и не будет дождя:
\[A\to B\wedge \overline{C}\]Если будет дождь, то будет пасмурно и не будет ветра:
\[C\to B\wedge A\]Если будет пасмурная погода, то будет дождь и не будет ветра
\[B\to C\wedge A\]Составим конъюнкцию указанных функций:
\[F=\left(A\to B\wedge \overline{C}\right)\wedge \left(C\to B\wedge A\right)\wedge \left(B\to C\wedge A\right)\]Используя законы алгебры логики(закон де Моргана, переместительный закон, закон противоречия), упростим формулу:
\[F=\left(A\to B\wedge \overline{C}\right)\wedge \left(C\to B\wedge A\right)\wedge \left(B\to C\wedge A\right)=\] \[=\left(\overline{A}\vee B\wedge \overline{C}\right)\wedge \left(\overline{C}\vee B\wedge A\right)\wedge \left(\overline{B}\vee C\wedge A\right)=\] \[=\left(\overline{A}\vee B\wedge \overline{C}\right)\wedge \left(\overline{B}\vee C\wedge A\right)\wedge \left(\overline{C}\vee B\wedge A\right)=\] \[=\left(\overline{A}\wedge \overline{B}\vee B\wedge \overline{C}\wedge \overline{B}\vee \overline{A}\wedge C\wedge A\vee B\wedge \overline{C}\wedge C\wedge A\right)\wedge \left(\overline{C}\vee B\wedge A\right)=\] \[=\overline{A}\wedge \overline{B}\wedge \left(C\vee B\wedge \overline{A}\right)=\overline{A}\wedge \overline{B}\wedge C\vee \overline{A}\wedge \overline{B}\wedge B\wedge \overline{A}=\overline{A}\wedge \overline{B}\wedge \overline{C}\] -
Приравниваем результат к единице, т.е. проверяем, при каких условиях выражение будет истинным:
\[F=\overline{A}\wedge \overline{B}\wedge \overline{C}=1.\]Проанализируем полученный результат:
Функция будет истинной, если каждый множитель будет истинным, т.е. $\overline{A}=1$, $\overline{B}=1$, $\overline{C}=1$. Отсюда следует, что $A=0$, $B=0$, $C=0$.
Ответ: погода будет без ветра, ясная и без дождя.
История с амфорой
Антон, Борис и Григорий нашли в земле сосуд, о котором каждый высказал по два предположения:
-
Антон: «Сосуд греческий и изготовлен в V столетии»;
-
Борис: «Сосуд финикийский и изготовлен в III столетии»;
-
Григорий: «Сосуд не греческий и изготовлен в IV столетии».
Специалист сказал ученикам, что каждый из них не ошибся только в одном из двух предположений. Определить место и столетие изготовления сосуда.
Решение:
Введем следующие обозначения:
$G$ -- «Сосуд греческий»;
$F$ -- «Сосуд финикийский»;
$S_3$ -- «Сосуд изготовлен в $III$ столетии»;
$S_4$ -- «Сосуд изготовлен в $IV$ столетии»;
$S_5$ -- «Сосуд изготовлен в $V$ столетии».
Запишем условие задачи с помощью обозначений:
Антон прав только в одном предположении: $G = 1$ или $S_5 = 1$. Тогда $G\overline{S_5}\vee \overline{G}S_5=1$.
Аналогично для слов Бориса: $F\overline{S_3}\vee \overline{F}S_3=1$.
Для слов Григория: $\overline{G}\overline{S_4}\vee GS_4=1$.
Т.к. сосуд может быть изготовлен только в одном из столетий и только в одной из стран, запишем условия:
\[S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5=1,\] \[F\overline{G}\vee \overline{F}G=1.\]Применим операцию логического умножения к полученным тождественно истинным высказываниям, результат которого также должен быть тождественно истинным:
\[\left(G\overline{S_5}\vee \overline{G}S_5\right)\wedge \left(F\overline{S_3}\vee \overline{F}S_3\right)\wedge \left(\overline{G}\overline{S_4}\vee GS_4\right)\wedge \left(F\overline{G}\vee \overline{F}G\right)\wedge \] \[\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]Перемножим первую на третью скобку и вторую на четвертую:
\[=\left(G\overline{S_5}\overline{G}\overline{S_4}\vee \overline{G}S_5\overline{G}\overline{S_4}\vee G\overline{S_5}GS_4\vee \overline{G}S_5GS_4\right)\wedge \] \[\wedge \left(F\overline{S_3}F\overline{G}\vee \overline{F}S_3F\overline{G}\vee F\overline{S_3}\overline{F}G\vee \overline{F}S_3\overline{F}G\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]Т.к. $G\overline{G}=0$, $GG=G$, $\overline{G}\overline{G}=\overline{G}$, упростим выражения:
\[=\left(\overline{G}S_5\overline{S_4}\vee G\overline{S_5}S_4\right)\wedge \left(F\overline{S_3}\overline{G}\vee \overline{F}S_3G\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]Перемножим первые две скобки и упростим выражение:
\[=\left(\overline{G}S_5\overline{S_4}\overline{F}S_3G\vee G\overline{S_5}S_4\overline{F}S_3G\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\overline{G}\vee G\overline{S_5}S_4F\overline{S_3}\overline{G}\right)\wedge \] \[\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\] \[=\left(G\overline{S_5}S_4\overline{F}S_3\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\] \[=\left(G\overline{S_5}S_4\overline{F}S_3\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\overline{G}S_5\overline{S_4}F\overline{S_3};\]$\overline{G}S_5\overline{S_4}F\overline{S_3}=1$, что возможно только в случае:
\[\overline{G}=1, S_5=1, \overline{S_4}=1, F=1, \overline{S_3}=1.\]Ответ: сосуд финикийский и изготовлен в $V$ столетии.
