Одно и то же условие можно записать десятком разных формул. Часть из них короткая и понятная, часть – громоздкая, с лишними скобками и отрицаниями. Чтобы переходить от второй к первой не наугад, а по правилам, нужны законы алгебры логики.
Разминка. Что следует из фразы «Неверно, что сегодня дождь и холодно»? Скорее всего, интуиция подсказывает: либо дождя нет, либо не холодно (а может, и то и другое сразу) – но точно не «и дождь есть, и холодно», раз мы это отрицаем. Обратите внимание: отрицание союза «И» превратилось в союз «ИЛИ» с отрицанием каждой части. Это не случайность.
В этом уроке: что такое закон алгебры логики, законы двойного отрицания, идемпотентности и де Моргана, строгая проверка равносильности по таблице истинности, справочник остальных законов и два разобранных примера упрощения.
Закон алгебры логики – равносильность (тождество) вида $F_1 \equiv F_2$, верная при любых значениях входящих переменных.
Ключевое слово здесь – «при любых». Совпадения на одном удачном примере недостаточно: закон обязан выполняться на всех наборах значений без исключения. Зато, будучи доказанным один раз, он позволяет заменять одну формулу другой, не пересчитывая таблицу истинности каждый раз заново.
Если высказывание отрицать дважды, получаем исходное: внешнее «неверно, что» гасит внутреннее. Пример: «неверно, что я не дома» означает «я дома».
Повторить высказывание через «И» или «ИЛИ» с самим собой – всё равно что не повторять вовсе.
Стоит предупредить: в обычной арифметике $A \cdot A$ обычно не равно $A$ (кроме 0 и 1) – но в логике всего два значения, и это тождество верно всегда, без исключений.
Два самых полезных закона блока – они описывают, что происходит с отрицанием, когда его «вносят» внутрь скобок (сами формулы – в рамке ниже).
Правило запоминается одной фразой: отрицание вносится в скобки, а знак операции при этом меняется на противоположный – «И» становится «ИЛИ» и наоборот.
Возврат к разминке: именно это мы интуитивно применили в начале урока – отрицание «дождь И холодно» превратилось в «не дождь ИЛИ не холодно».
Историческая справка: законы названы в честь британского математика Огастеса де Моргана (XIX век, сформулировал их в книге Formal Logic, 1847), хотя сама идея встречалась в логике и раньше – де Морган первым чётко записал её в алгебраической форме.
Строгое доказательство закона – не «интуитивно понятно», а полная таблица истинности для всех 4 комбинаций $A$ и $B$, где столбцы $\lnot(A \land B)$ и $\lnot A \lor \lnot B$ должны совпасть строка в строку:
| $A$ | $B$ | $A \land B$ | $\lnot(A \land B)$ | $\lnot A$ | $\lnot B$ | $\lnot A \lor \lnot B$ |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Последние два столбца совпадают в каждой строке – значит, равносильность доказана для всех вариантов значений $A$ и $B$, а не только для «правдоподобного» примера с дождём. Точно так же проверяется любая другая равносильность: выписать все $2^n$ строк и сравнить два итоговых столбца.
Ассоциативность – результат не зависит от того, как расставлены скобки при группировке одинаковой операции:
Практический смысл: раз скобки роли не играют, для длинной цепочки одинаковых операций ($A \land B \land C \land D$) их можно вообще не писать – неоднозначности не возникает.
Дистрибутивность – здесь у логики есть особенность, которой нет в обычной арифметике: работают обе формы одновременно.
Первая форма – «И» распределяется по «ИЛИ», прямая аналогия со школьной алгеброй ($a \cdot (b + c) = a \cdot b + a \cdot c$):
$A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$
Пример: «(сегодня суббота или воскресенье) и я свободен» равносильно «(суббота и я свободен) или (воскресенье и я свободен)».
Вторая форма – «ИЛИ» распределяется по «И», и вот это уже не имеет аналога в обычной арифметике: $a + b \cdot c \ne (a + b) \cdot (a + c)$ для чисел (подставьте $a=1$, $b=2$, $c=3$, чтобы убедиться), а в логике это верно всегда:
$A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$
Пример: «я свободен или (суббота и солнечно)» равносильно «(я свободен или суббота) и (я свободен или солнечно)».
Остальные законы, которые понадобятся в примерах ниже, – справочно:
| Закон | Запись |
|---|---|
| Поглощение | $A \lor (A \land B) \equiv A$, $A \land (A \lor B) \equiv A$ |
| Действия с константами | $A \land 1 \equiv A$, $A \lor 0 \equiv A$, $A \land 0 \equiv 0$, $A \lor 1 \equiv 1$ |
| Противоречие | $A \land \lnot A \equiv 0$ |
| Исключённое третье | $A \lor \lnot A \equiv 1$ |
Порядок действий, который почти всегда работает:
Ниже – два примера, где этот порядок виден пошагово: слева выражение после очередного шага, справа – закон, по которому этот шаг сделан.
Упрощаем $\lnot(A \lor \lnot B) \lor B$.
| Шаг | Выражение | По какому закону |
|---|---|---|
| – | $\lnot(A \lor \lnot B) \lor B$ | исходная формула |
| 1 | $(\lnot A \land \lnot(\lnot B)) \lor B$ | де Моргана |
| 2 | $(\lnot A \land B) \lor B$ | двойного отрицания |
| 3 | $B$ | поглощения |
Итог: вся громоздкая формула равносильна просто $B$ – значение $A$ на результат не влияет вообще.
Упрощаем $\lnot(A \land B) \land B$.
| Шаг | Выражение | По какому закону |
|---|---|---|
| – | $\lnot(A \land B) \land B$ | исходная формула |
| 1 | $(\lnot A \lor \lnot B) \land B$ | де Моргана |
| 2 | $(\lnot A \land B) \lor (\lnot B \land B)$ | дистрибутивности |
| 3 | $(\lnot A \land B) \lor 0$ | противоречия ($\lnot B \land B \equiv 0$) |
| 4 | $\lnot A \land B$ | действий с константами |
Итог: $\lnot A \land B$.
Короткие вопросы по теме урока. Попыток сколько угодно, на прохождение блока они не влияют – это проверка для себя.