Сложные операции: импликация и эквивалентность

Импликация (следование) – бинарная операция $A \to B$ («если A, то B»), ложная только в одном случае: когда A истинно, а B ложно. Во всех остальных случаях она истинна.

Таблица истинности:

Единственная строка с нулём – вторая. Это стоит запомнить как правило: импликация ложна только на наборе $1 o 0$.

Возвращаемся к разминке: A = «идёт дождь», B = «беру зонт». Если A ложно (дождя нет) – импликация истинна независимо от B, это как раз строки 3 и 4 таблицы. Обещание невозможно нарушить, пока условие не наступило.

Формальная логика доводит это правило до конца: ей всё равно, связаны ли посылка и заключение по смыслу. Отсюда откровенно абсурдные, но формально истинные высказывания:

• «Если $2 \times 2 = 5$, то Луна сделана из сыра» – истинно (строка 4 таблицы: посылка ложна, заключение ложно).
• «Если у меня три руки, то я – чайник» – тоже истинно, по той же причине.

Заключение может быть каким угодно, хоть заведомо бредовым: сделать импликацию ложной способно только сочетание «истинная посылка при ложном заключении». Ложная посылка оправдывает всё.

Это расходится со «здравым смыслом» естественного языка: в речи «если…, то…» подразумевает смысловую связь между частями. В формуле $A \to B$ никакой связи не требуется – операция смотрит только на два значения, 0 и 1. Дальше в курсе мы опираемся именно на это определение.

В записи $A \to B$ высказывание A называют достаточным условием для B – выполнения A хватает, чтобы гарантировать B. А B называют необходимым условием для A – без B не может быть A.

Когда так говорить можно. Не про всякую импликацию. Нужны два признака сразу:

1. В утверждении есть переменная – «любое целое число n», «любой треугольник», «любой ученик». То есть перед нами правило, а не разовое сравнение двух готовых фактов.
2. Импликация истинна при всех значениях этой переменной: не находится ни одного контрпримера, где A выполнено, а B – нет.

Пример: «Если число делится на 4, то оно чётное». Переменная есть – любое целое число; контрпримера нет – не существует числа, которое делится на 4 и при этом нечётно. Значит, делимость на 4 достаточна для чётности, а чётность необходима для делимости на 4. Обратное неверно: 6 чётно, но на 4 не делится – значит, чётности недостаточно.

Когда говорить нельзя. Вернёмся к «Если $2 \times 2 = 5$, то Луна сделана из сыра». Переменной здесь нет: обе части – конкретные высказывания с уже готовыми значениями 0 и 0. Перебирать нечего, зависимости между частями никакой, а импликация истинна только из-за ложной посылки. Это одна строка таблицы истинности, а не правило – слова «необходимое» и «достаточное» к ней неприменимы.

Если верны оба направления. Когда при всех значениях переменной истинны и $A \to B$, и $B \to A$, условие называют необходимым и достаточным (говорят «тогда и только тогда»), а записывают через эквивалентность $A \leftrightarrow B$ – о ней ниже. Пример: «Число чётно тогда и только тогда, когда его последняя цифра чётная».

Импликацию можно выразить через три базовые операции: $A \to B$ равносильно $\lnot A \lor B$ – либо A ложно, либо B истинно, и это ровно то же самое условие. Проверить совпадение можно построчно по таблице истинности, а строго доказать – с помощью законов алгебры логики (3.4).

Практическая ценность этой равносильности в том, что она позволяет избавиться от стрелки: любую формулу с импликацией можно переписать через $\lnot$, $\land$ и $\lor$ – и дальше работать с ней привычными средствами.

Эквивалентность (равнозначность) – бинарная операция $A \leftrightarrow B$, истинная тогда и только тогда, когда A и B имеют одинаковое значение истинности: оба истинны или оба ложны.

Таблица истинности:

Обратите внимание на последнюю строку: два ложных высказывания эквивалентны друг другу – операция сравнивает значения, а не «правдивость» по существу.

Второе название эквивалентности – двойная импликация, и оно не случайно: $A \leftrightarrow B$ равносильно $(A \to B) \land (B \to A)$, то есть выполняется и прямое, и обратное следование одновременно.

Пример: «Треугольник равносторонний тогда и только тогда, когда все его углы равны 60°» – оба направления верны сразу: из равносторонности следуют равные углы, и наоборот. А вот «если число делится на 4, то оно чётное» – только импликация: обратное неверно, и эквивалентности здесь нет.

Теперь операций пять, и порядок их выполнения в формуле без скобок нужно знать целиком:

Так, выражение $A \lor B \to C$ без скобок означает $(A \lor B) \to C$, а не $A \lor (B \to C)$: дизъюнкция выполняется раньше импликации. Это типовая ловушка – прежде чем считать таблицу, полезно расставить скобки явно.