Импликация (Логическое следование): таблица истинности и свойства
В математической логике и дискретной математике импликация (от лат. implicatio — сплетение, связь) или логическое следование — это сложная бинарная логическая операция, которая связывает два высказывания в виде условия и следствия.
В естественном языке эта операция лучше всего описывается словесной конструкцией «ЕСЛИ …, ТО …».
Первый операнд (условие) называется посылкой (или антецедентом), а второй операнд (результат) — следствием (или консеквентом).
Главное и единственное правило импликации: результат операции ложен (0) только в одном-единственном случае — когда посылка истинна (1), а следствие ложно (0). Во всех остальных случаях импликация истинна. Иными словами, «из истины не может следовать ложь».
Обозначения импликации
Поскольку операнды в импликации неравноправны (порядок имеет значение), в качестве символа чаще всего используются стрелки, указывающие направление от посылки к следствию:
- $A \rightarrow B$ (стандартное математическое обозначение, стрелка вправо);
- $A \Rightarrow B$ (двойная стрелка вправо, часто используется в математических доказательствах);
- $A \supset B$ (символ, больше характерный для теории множеств, но встречающийся в старой литературе);
A IMP BилиA IMPLIES B(текстовое обозначение в информатике).
Пример из реальной жизни (простыми словами)
Чтобы легко запомнить таблицу истинности импликации, представьте, что начальник дает вам обещание: «ЕСЛИ ты выполнишь план продаж ($A$), ТО я выпишу тебе премию ($B$)».
Импликация — это ответ на вопрос: «Сдержал ли начальник свое обещание (не солгал ли он)?»
- Ты выполнил план ($A=1$), и начальник выписал премию ($B=1$). Начальник сдержал обещание. Импликация истинна (1).
- Ты выполнил план ($A=1$), но начальник НЕ выписал премию ($B=0$). Начальник нарушил обещание (солгал). Импликация ложна (0). Это тот самый единственный случай лжи.
- Ты НЕ выполнил план ($A=0$), но начальник все равно выписал премию ($B=1$). Начальник не нарушал обещания (он не говорил, что будет, если план не выполнить, возможно, премия была за выслугу лет). Импликация истинна (1).
- Ты НЕ выполнил план ($A=0$), и начальник НЕ выписал премию ($B=0$). Всё честно, обещание не нарушено. Импликация истинна (1).
Таблица истинности для импликации
Таблица наглядно демонстрирует правило: 0 получается только тогда, когда $1 \rightarrow 0$.
Для двух переменных ($A \rightarrow B$)
| $A$ (Посылка) | $B$ (Следствие) | $A \rightarrow B$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Для трех переменных ($A \rightarrow B \rightarrow C$)
В отличие от других операций, при расчете цепочки импликаций действия выполняются строго последовательно слева направо: сначала вычисляется $(A \rightarrow B)$, а затем результат этой операции становится посылкой для $\rightarrow C$.
| $A$ | $B$ | $C$ | $A \rightarrow B$ | $(A \rightarrow B) \rightarrow C$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
(Воспользуйтесь нашим интерактивным калькулятором, чтобы автоматически построить таблицы для 4 и 5 переменных!)
Основные свойства и законы импликации
Импликация — «капризная» операция. Она не обладает многими привычными нам свойствами.
1. Отсутствие коммутативности (непереместимость): От перемены мест операндов результат меняется!
$$A \rightarrow B \neq B \rightarrow A$$
(Пример: «Если идет дождь, то асфальт мокрый» — это истина. Но обратное утверждение «Если асфальт мокрый, то идет дождь» — не обязательно истинно, асфальт могла полить поливальная машина).
2. Отсутствие ассоциативности (несочетательность): Порядок расстановки скобок имеет значение.
$$(A \rightarrow B) \rightarrow C \neq A \rightarrow (B \rightarrow C)$$
3. Выражение через базовые операции (И, ИЛИ, НЕ): Это самое важное свойство импликации в алгебре логики. Любую импликацию можно (и нужно при упрощении выражений) заменить на дизъюнкцию с инверсией посылки.
$$A \rightarrow B = \neg A \lor B$$
4. Взаимодействие с константами (0 и 1):
- Импликация из лжи всегда дает истину: $0 \rightarrow A = 1$
- Импликация в истину всегда дает истину: $A \rightarrow 1 = 1$
- Истина не меняет следствие: $1 \rightarrow A = A$
- Импликация в ложь работает как инверсия: $A \rightarrow 0 = \neg A$
5. Контрапозиция: Утверждение «Из A следует B» равносильно утверждению «Из НЕ B следует НЕ A».
$$A \rightarrow B = \neg B \rightarrow \neg A$$
Попробуйте понажимать кнопки в нашем интерактивном тренажере выше, чтобы закрепить понимание того, как работает логическое следование!