Логические задачи и алгебра высказываний

14

Логичские задачи и алгебра высказывания

Л. Л. Цинман

Начнем с формулировок несколько логических задач.

Задача 1. После родительской собраня к учительнице подошел один из родителей.

— Вот вы не назвали моей сына среди хороших учеников — сказал он. — А ведь мой Федя — отличник и к тому же лучший льжник класса.

— Да, вы правы, — ответила учительница. — Но хорошим учеником мы считаем ученика, который хорошо учится, дисциплинован, помогаем в учебе отстающим и, кроме того, указывает в работе научного кружка или занимается спором. А ваш Федя…

Что еще собиралась сказать учительница Фединому пале?

Задача 2. Оdnажды следовательно пришлось одновременно допрашивать трех свидетельей: Клода, Жака и Дика. Их показания промиворечили другие другие, и каждый из них обвинили коо-нибудь во лжи. Клод умерerkдал, что Жак лжет, Жак обвинил во лжи Дика, а Дик уеваривал следовательно не верить ни Клоду, ни Жаку. Но следовательно быстро вывел их на чистую воду, не задав им ни одно вопроса. Кто из свидетельей ответил правду?

Задача 3. Оdnин лоеик попал в плен к дикарам и был заключен в темницу, имеющую два выхода. Вожде дикарей предложил пленнику следующий шанс на спасение: «Оdnин выход ведем на свободу, а другой на верную смерть. Ты можете избрать любой. Сделать выбор мебе помогаем моей свидетелью. Он останется здесь, что

бы ответить на один вопрос — любой, какой мы пожелаем ему задать. Но я предупреждаю мебе: если у этого стражника хорошо нестроение, то он говорит правду, если же у него настроение плохое, то он лжет!»

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

Логичские задачи, подобные перечисленным, часто появляются в научно-популярных изданиях. Для их решения не требуется каких-либо специальных знаний из области логики, требуется лишь достаточно хорошо развитое логическое мышление. Но представьте себе человека, взявшегося за решение какой-либо числовой задачи (на движение, переливание) и не умелошего при этом свободно делать алгебраические преобразования и решать уравнения. Приблизительно в таком же положении вы оказываетеся при решении логических задач без использования вспомогательного аппарата, который носит название алгебры высказывания или алгебры логики (в отличие от алгебры чисел, изучаемой в школе).

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

16

Отрицание высказывания
Обозначение отрицания высказывания $A : \bar{A}$. Отрицание высказывания $A$ соответствует высказыванию «не $A$» («неверно, что $A$»). Поэтому оно определяется такой таблицей истинности:

| $A$ | $\bar{A}$ |
| :— | :— |
| 1 | 0 |
| 0 | 1 |

С помощью введенных операций в алгебре высказывания из отдельных высказываний $A, B, C$… можно строить сложные алгебраические выражения, например: $\bar{A} \vee B; \bar{A} \wedge B; (A \vee \bar{B}) \wedge C$.

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

$((A \wedge B) \vee ((\bar{A} \vee B) \wedge C))$

можно переписать в виде

$A \wedge B \vee (\bar{A} \vee B) \wedge C$.

Если знать значение каждого высказывания, входящero в алгебраческое выражение, то с помощью таблиц истинности можно найти значение этого алгебраческого выражения. Найдем, например, значения алгебраческого выражения $\bar{A} \vee \bar{B}$ при всех возможных значениях его компонент $A$ и $B$:

| $A$ | $B$ | $\bar{A}$ | $\bar{B}$ | $\bar{A} \vee \bar{B}$ |
| :— | :— | :— | :— | :— |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |

Сначала по значениям в первых двух столбцах заполняется третьий и четвертый столбцы, а потом, согласно определению сложения, заполняется последний столбец. Эта таблица называется таблицей истинности для выражения $\bar{A} \vee \bar{B}$.

Тепер построим таблицу истинности для $\bar{A} \wedge \bar{B}$:

| $A$ | $B$ | $\bar{A} \wedge \bar{B}$ |
| :— | :— | :— |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |

Последанные столбцы в приведенных таблицах оказались одинаковыми. Это означает, что при любых значениях высказывания $A$ и $B$ выражения $\bar{A} \vee \bar{B}$ и $\bar{A} \wedge \bar{B}$ принимают одинаковые значения. Такие алгебраические выражения мы будем называть равносильными. Для записи равносильности употребляется знак точдества:

$$\bar{A} \wedge \bar{B} \equiv \bar{A} \vee \bar{B}$$

Эти два равносильных выражения имеют один и тот же содержательный смысл, но выраженный разными словами.

Действительно, если $A$ и $B$ — какие-то высказывания, то $\bar{A} \wedge \bar{B}$ выражает сложное высказывание «неверно, что оба данных высказывания истинны», а $\bar{A} \vee \bar{B}$ выражает сложное высказывание «хотя бы одно из данных высказываний ложно».

Аlgебраические выражения, у которых в таблице истинности последний столбец состоит из единиц (из нулей), будем называть тоже逮венно истинными (тожд逮венно ложными) и обозначать буквой $H$ (буквой $J$).

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

Приведем простейшие равносильности, неокторыми из которых мы в

17

дальнейшем будем пользоваться как правилами.

1. $A \wedge B \equiv B \wedge A$.
2. $A \vee B \equiv B \vee A$.
3. $(A \wedge B) \wedge C \equiv A \wedge (B \wedge C)$.
4. $(A \vee B) \vee C \equiv A \vee (B \vee C)$.
5. $A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$.
6. $A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C)$.
7. $A \wedge A \equiv A$.
8. $A \vee A \equiv A$.
9. $\overline{A} \wedge \overline{B} \equiv \overline{A} \vee \overline{B}$.
10. $\overline{A} \vee \overline{B} \equiv \overline{A} \wedge \overline{B}$.
11. $\overline{A} \equiv A$.
12. $A \wedge \overline{A} \equiv \overline{J}$.
13. $A \vee \overline{A} \equiv \overline{H}$.
14. $A \wedge \overline{J} \equiv \overline{J}$.
15. $A \vee \overline{H} \equiv \overline{H}$.
16. $A \wedge \overline{H} \equiv A$.
17. $A \vee \overline{J} \equiv A$.

Если представить себе содержательный смысл правил 1—17 так, как это мы сделали выше с правилом 9, то эти равносильности станут очевидными и легко запоминаемыми.

Некоторые из перечисленных правил, а именно 1—5, аналогичны известным свойством операций сложения и умножения в числовой алгебре. Поэтому в алгебре высказываний мы можем производить алгебраические преобразования подобные тем, которые делаем в числовой алгебре. В частности, мы можем «перемножить» два алгебраических высказения по правилу умножения многочлена на многочлен.

Но в алгебре высказываний имеются и свои специфические правила, например 6.

Решение задачи 1

Введем обозначения для высказывания:

$A$: «Федя хорошего учится»;
$B$: «Федя дисциплинирован»;
$C$: «Федя помогает в учебе отстающим»;
$D$: «Федя участвует в работе научного кружка»;
$E$: «Федя занимается спортом».

Теперь высказывание «Федя — хороший ученик», согласно «определенного» хорошего ученика, данному учению,

тельницей, можно записать так:

$A \cup B \cup C$ ($D \cup E$).

На языке алгебры высказываний это сложное высказывание примет вид алгебраического выражения

$A \wedge B \wedge C \wedge (D \vee E)$.

Учительница утверждает, что «неверно, что (Федя — хороший уче-ник)», то есть

$$\{A \wedge B \wedge C \wedge (D \vee E)\} = 1.$$

Преобразуем теперь алгебраическое выражение в левой части сначала по правилу 9 (правда, в данном случае отрицание стоит над логическим произведением четырех компонентов, но нетрудно убедиться, что равносильность 9 остается справедливой и в этой более общей форме), а потом по правилу 10:

$$\begin{align*} \{A \vee \overline{B} \vee \overline{C} \vee (D \vee E)\} &= 1; \\ \{A \vee \overline{B} \vee \overline{C} \vee \overline{D} \wedge \overline{E}\} &= 1. \end{align*}$$

Федин попау утверждет (и учителица согласилась с ним), что

$$\{A\} = 1$$

(Федя — отличник!), а также

$$\{E\} = 1$$

(Федя — лучший лыжник класса!). Тогда в (1) первого и два последних слагаемых ложны и их можно отбросить по правилам 17 и 14.

Получаем, что

$$\{B \vee \overline{C}\} = 1.$$

Значит, учительница хотела пожаловать с Фединой пале или на то, что Федя — недисциплинирован, или на то, что он не помогает в учебе отстающим (а может быть, Федя став缚ы сразу оба эти недостатка).

Решение задачи 2

Обозначим показания свидетельяя Клода, Жака и Дика соответствующего буквами $K$, $J$, $D$. Мы не знаем, какие из этих показаний истинны, а какие ложны. Но нам известно следующее:

1. либо Клод сказал правду, и тогда Жак солгал, либо Клод солгал, и тогда Жак сказал правду;