Импликация и эквивалентность

Две операции, на которых держится почти вся логика рассуждений: «если … то …» и «тогда и только тогда».

Вы уже знаете «И», «ИЛИ» и «НЕ». Этого хватает, чтобы описать комбинации фактов, но не хватает, чтобы описать рассуждение. Когда мы говорим «если пойдёт дождь, то асфальт намокнет» или «число делится на 6 тогда и только тогда, когда оно делится на 2 и на 3», мы пользуемся двумя особыми связками — импликацией и эквивалентностью. Разберём их так, чтобы они перестали путаться.

Импликация A → B («из A следует B», «если A, то B») ложна в одном-единственном случае: когда посылка A истинна, а следствие B ложно. Во всех остальных случаях импликация истинна.

Эквивалентность A ≡ B («A равносильно B», «A тогда и только тогда, когда B») истинна, когда значения A и B совпадают, и ложна, когда они различаются.

Импликация: обещание, которое можно нарушить

Самый надёжный способ почувствовать импликацию — представить её как обещание. Друг говорит: «Если будет солнце, я приду на пробежку». Здесь A = «будет солнце», B = «я приду». Спросим в каждом случае: соврал ли он?

• Солнце есть, друг пришёл (A=1, B=1) — обещание сдержано, всё честно. Истина.
• Солнце есть, а друг не пришёл (A=1, B=0) — вот это обман! Единственный случай лжи.
• Солнца нет, друг всё равно пришёл (A=0, B=1) — он ничего не обещал на такой случай, значит и не соврал. Истина.
• Солнца нет, друг не пришёл (A=0, B=0) — тоже никакого нарушения. Истина.

Отсюда правило, которое сначала кажется странным: из ложной посылки следует что угодно. Если A ложно, обещание просто не вступает в силу, поэтому нарушить его невозможно — импликация автоматически истинна. Математики говорят: «из лжи следует всё».

Полная таблица истинности импликации

Запомните эту таблицу как «три единицы и один ноль», причём ноль стоит ровно там, где «правда → ложь».

Эквивалентность: совпадают или нет

Эквивалентность A ≡ B устроена проще: она проверяет, одинаковы ли значения. Истина, когда оба истинны или оба ложны; ложь, когда они разные. По-человечески это «A и B всегда вместе»: либо оба верны, либо оба нет.

Полезная связь: A ≡ B истинна тогда и только тогда, когда обе импликации A → B и B → A истинны одновременно. Поэтому эквивалентность и читают как «тогда и только тогда».

Проверяем таблицы кодом

Лучший способ убедиться, что вы поняли формулы, — заставить компьютер построить обе таблицы. В Python импликацию удобно выразить как (not a) or b, а эквивалентность — как a == b. Запустите код и сравните вывод с таблицами выше — они должны совпасть строка в строку.

print("Импликация A -> B  =  (not A) or B")
print("A B | A->B")
for a in (0, 1):
    for b in (0, 1):
        impl = (not a) or b
        print(a, b, "|", int(impl))

print()
print("Эквивалентность A == B")
print("A B | A=B")
for a in (0, 1):
    for b in (0, 1):
        eq = (a == b)
        print(a, b, "|", int(eq))

Программа выведет:

Импликация A -> B  =  (not A) or B
A B | A->B
0 0 | 1
0 1 | 1
1 0 | 0
1 1 | 1

Эквивалентность A == B
A B | A=B
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 1

Обратите внимание: у импликации единственный ноль — в строке 1 0, а у эквивалентности нули стоят там, где значения A и B различаются. Ровно то, что мы и обсуждали.

Главная формула: замена импликации

Импликации нет в большинстве калькуляторов и почти нет в языках программирования — зато везде есть «НЕ», «И», «ИЛИ». Поэтому импликацию всегда можно переписать:

A → B = ¬A ∨ B

То есть «из A следует B» равносильно «не A, или B».

Проверим по таблице, что ¬A ∨ B даёт ровно те же значения, что и A → B:

Два последних столбца совпадают — формула верна. Эта замена — рабочая лошадка: с её помощью импликацию загоняют в выражения из ¬, ∧, ∨, которые уже умеют упрощать.

Связь с задачами ЕГЭ

В ЕГЭ по информатике импликация — частый гость. Типичная задача: «Для какого наименьшего числа x выражение истинно при всех значениях переменных?» Почти всегда первый шаг — избавиться от импликации по формуле A → B = ¬A ∨ B, а дальше упрощать.

Ещё одна ловушка ЕГЭ — цепочка импликаций вида A → B → C. Импликация правоассоциативна, то есть читается как A → (B → C). Помните, что вся цепочка ложна только тогда, когда удаётся «дойти» до пары «истина → ложь».

Полезно держать в голове и приоритет операций (от старшего к младшему): ¬, затем ∧, затем ∨, затем → и в самом конце ≡. Поэтому A ∨ B → C означает (A ∨ B) → C, а вовсе не A ∨ (B → C).

Частые ошибки

• Считают, что A → B ложна при ложной посылке. Нет: при A = 0 импликация всегда истинна.
• Путают импликацию с эквивалентностью. A → B несимметрична: A → B и B → A — разные вещи, а A ≡ B симметрична.
• Неверно заменяют импликацию: правильно ¬A ∨ B, а не A ∨ ¬B и не ¬A ∧ B.
• Забывают про приоритет: → слабее ∨ и ∧, поэтому скобки в (A ∨ B) → C подразумеваются.

Коротко

• A → B ложна только при A = 1, B = 0; в остальных трёх случаях — истинна.
• Из ложной посылки следует что угодно: при A = 0 импликация истинна.
• A ≡ B истинна, когда значения совпадают, и равна паре импликаций A → B и B → A.
• Ключевая замена: A → B = ¬A ∨ B — первый шаг почти любой задачи ЕГЭ.
• Приоритет: ¬ > ∧ > ∨ > → > ≡.