Логика высказываний: таблицы истинности, импликация и законы

Каждая строчка кода в итоге сводится к вопросу «истина или ложь»: if (пароль верный) и (админ) — открыть доступ. Компьютер живёт в мире, где у утверждений всего два значения, и в этом мире есть точная грамматика — алгебра логики. Разберём её так, чтобы таблицы истинности перестали быть скучными сетками, а импликация — главной ловушкой семинара.

Высказывание и пять операций#

Высказывание — повествовательное предложение, про которое осмысленно спрашивать «истина или ложь». «Дважды два четыре» — высказывание (истинно). «Который час?» — нет: у вопроса нет истинностного значения. «$x>5$» — тоже не высказывание: без указания $x$ судить не о чем; такие заготовки станут предикатами в уроке о логике предикатов. Обозначают высказывания латинскими буквами $A$, $B$, $C$, а истину и ложь — $1$ и $0$ (или И/Л).

Из простых высказываний строят сложные пятью операциями. Приоритет: сначала отрицание $\neg$, потом $\wedge$, потом $\vee$, импликация $\to$ и эквивалентность $\leftrightarrow$ — последними. Скобки всё решают, но без них порядок надо помнить.

Импликация заслуживает отдельного разговора, потому что интуиция на ней ломается. Фраза «если идёт дождь, то асфальт мокрый» ложна только в одном случае: дождь идёт, а асфальт сухой. А если дождя нет? Обещание не нарушено — значение истинно, хоть асфальт хоть залейся. Отсюда табличка импликации: $1\to 1=1$, $0\to 1=1$, $0\to 0=1$, и лишь $1\to 0=0$. Из лжи следует что угодно — это не парадокс, а правило игры.

Формулы, тавтологии и законы#

Формула алгебры логики — высказывательные переменные, соединённые операциями. У формулы с $n$ переменными таблица истинности содержит $2^n$ строк: для трёх переменных — 8, для десяти — уже 1024. Формула, истинная при любых значениях переменных, называется тавтологией (закон логики), ложная всегда — противоречием. Проверка: $A\vee \neg A$ истинно всегда — закон исключённого третьего, а $A\wedge \neg A$ ложно всегда — закон противоречия.

Формулы называются равносильными, если их столбцы в таблице истинности совпадают. Равносильности — рабочие лошадки упрощения:

• законы де Моргана: $\neg (A\wedge B)=\neg A\vee \neg B$ и $\neg (A\vee B)=\neg A\wedge \neg B$ — отрицание переворачивает операцию
• контрапозиция: $A\to B=\neg B\to \neg A$ — «если дождь, то мокро» равносильно «если сухо, то дождя нет»
• разворачивание импликации: $A\to B=\neg A\vee B$ — спасает, когда хочется убрать стрелку
• поглощение: $A\vee (A\wedge B)=A$ и $A\wedge (A\vee B)=A$
• идемпотентность: $A\wedge A=A$, $A\vee A=A$ — повторение ничего не добавляет

Откуда брать законы? Из таблиц истинности — но лучше из здравого смысла. Де Моргана на русском: «неверно, что (сдал и матан, и физику)» означает «(матан не сдал) или (физику не сдал)». Контрапозиция: «если число делится на 4, то оно чётно» — то же самое, что «если число нечётно, то оно не делится на 4». Обе переформулировки безошибочны, и в доказательствах вы будете менять одну на другую постоянно.

Как упрощают формулы: разбор на шагах#

Типичная задача семинара: доказать равносильность или упростить формулу. Стратегия такая: 1) убрать импликации через $A\to B=\neg A\vee B$; 2) протащить отрицания внутрь по де Моргану; 3) применить поглощение и дистрибутивность. Пройдём на живом примере: упростим $\neg (A\vee \neg B)$.

Ещё один частый тип задачи — перевод с русского языка. «Неверно, что турист взял с собой зонт или карту» превращается в $\neg (З\vee К)=\neg З\wedge \neg К$: ни зонта, ни карты. Заметьте, как «или» превратилось в «и» — без де Моргана такие переводы постоянно путают.

Выполнимость: где логика встречается с алгоритмами

Формула называется выполнимой, если хотя бы на одном наборе значений она истинна. Вопрос «существует ли набор, делающий формулу истинной?» — знаменитая задача SAT, базовая NP-полная задача: для $n$ переменных в худшем случае надо просмотреть $2^n$ строк. Отсюда и практический интерес: современные SAT-решатели проверяют микросхемы и расписания, а сама задача — эталон сложности в теории алгоритмов.

Операции-экзоты: XOR, штрих Шеффера, стрелка Пирса#

Кроме пятёрки базовых операций в задачах встречаются ещё три. Исключающее ИЛИ $A\oplus B$ истинно, когда значения различны: честный перевод бытового «либо одно, либо другое». В электронике это сумма по модулю 2 — главный ингредиент сумматоров и шифрования. Штрих Шеффера $A\uparrow B$ — отрицание конъюнкции («не оба сразу»), стрелка Пирса $A\downarrow B$ — отрицание дизъюнкции («оба ложны»). Все три выражаются через базовые: $A\oplus B=(A\vee B)\wedge \neg (A\wedge B)$, $A\uparrow B=\neg (A\wedge B)$, $A\downarrow B=\neg (A\vee B)$.

Чем они интересны? Полотой системы. Система вентилей называется полной, если через неё можно выразить любую формулу. Стандартная тройка $\{\neg ,\wedge ,\vee \}$ полна; но и одинокий штрих Шеффера полон: $\neg A=A\uparrow A$, а конъюнкция собирается как $A\wedge B=(A\uparrow B)\uparrow (A\uparrow B)$. То же верно для стрелки Пирса. В микросхемах это буквально экономит деньги: производить один тип вентиля проще, чем три.

Пример на чтение формул со скобками. Дана запись $\neg A\vee B\wedge C\to B$. По приоритету отрицание сильнее конъюнкции, конъюнкция сильнее импликации: читается как $(\neg A\vee (B\wedge C))\to B$. Забыли приоритет — восстанавливайте скобками на черновике; потеря одной пары скобок меняет всю таблицу истинности.

Соберём всё в одну задачу, которую дают на контрольных в середине семестра: доказать равносильность $(A\to B)\to B=A\vee B$. Слева — двойная импликация, справа — простая дизъюнкция; с виду они не похожи. Решайте по шагам, потом открывайте проверку.

1. 1
   Убираем внешнюю импликацию: $(A\to B)\to B=\neg (A\to B)\vee B$.
2. 2
   Убираем внутреннюю: $\neg (\neg A\vee B)\vee B$.
3. 3
   Де Морган: $\neg \neg A\wedge \neg B\vee B$, после снятия двойного отрицания: $(A\wedge \neg B)\vee B$.
4. 4
   Дистрибутивность наоборот: $(A\vee B)\wedge (\neg B\vee B)$, а вторая скобка — тавтология.
5. 5
   Итог: $(A\vee B)\wedge 1=A\vee B$. Равносильность доказана.

• Таблица с $n$ переменными — $2^n$ строк; не ленитесь выписывать наборы в порядке двоичного счёта от 0 до $2^n-1$, так ни одна строка не потеряется.
• Импликация — обещание: ложна ровно в одной строке $1\to 0$.
• Де Морган — «переворот»: отрицание меняет операцию и инвертирует оба слагаемых.
• Любую импликацию можно убрать: $A\to B=\neg A\vee B$ — если стрелка мешает, превращайте её.
• Проверка равносильности одним набором не доказывается, но один удачный набор может опровергнуть — пользуйтесь для быстрого отсева.
• Формулы со скобками читайте по приоритету: ¬, затем ∧, затем ∨, и только потом стрелки — сомневаетесь, ставьте скобки.

Кстати, вся эта алгебра живёт внутри языков программирования. Логическое «и» в коде вычисляется с коротким замыканием: если левая часть конъюнкции ложна, правая даже не вычисляется — поэтому проверка if (s != null && s.length > 0) безопасна, а переставленная в обратный порядок упадёт с ошибкой. Компиляторы применяют де Моргана буквально: условие !(a && b) превращается в !a || !b. А таблица истинности XOR — это бит сложения по модулю два, на котором стоит вся криптография с одноразовым блокнотом.