Тавтологии, противоречия и логические эквивалентности

Разбираемся, какие формулы истинны всегда, и учимся преобразовывать логические выражения по законам.

Тавтология — формула, истинная при любых значениях входящих в неё переменных. Противоречие — формула, ложная всегда.

Зачем это нужно

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

Три категории формул

• Тавтология — истинна всегда. Пример: p ∨ ¬p («либо p, либо не p») — закон исключённого третьего.
• Противоречие — ложна всегда. Пример: p ∧ ¬p («p и не p одновременно») — так не бывает.
• Выполнимая (нейтральная) — истинна хотя бы при одном наборе значений, но не всегда. Пример: p ∧ q.

Связь с равносильностью: формулы F и G логически эквивалентны (равносильны), если формула F ↔ G — тавтология. Иначе говоря, у них одинаковые таблицы истинности. Это и есть строгое «эти два условия — одно и то же».

Главные логические законы

Эти равносильности стоит знать наизусть — они рабочий инструмент.

Узнаёте де Моргана и дистрибутивность? Это те же законы, что и в алгебре множеств, — просто в логическом «костюме». «Не (p и q)» = «не p или не q»: чтобы опровергнуть «и», достаточно опровергнуть хоть одну часть. Это самый частый практический закон: правильно отрицать сложные условия умеет далеко не каждый, а ошибка тут стоит дорого.

Контрапозиция — почему это важно для доказательств

Закон контрапозиции p → q ≡ ¬q → ¬p говорит: «если из p следует q, то из неверности q следует неверность p». Пример: «если число делится на 4, то оно чётное» равносильно «если число нечётное, то оно не делится на 4». Этот закон — основа целого метода доказательства (мы разберём его в следующем уроке): иногда доказать «не q ⇒ не p» проще, чем «p ⇒ q» напрямую.

Проверяем равносильность машиной

Раз равносильность — это совпадение таблиц истинности, её можно проверить перебором всех наборов значений. Напишем функцию is_tautology и проверим несколько законов.

from itertools import product

def is_tautology(expr, n):
    # expr — функция от n булевых аргументов; перебираем все наборы
    return all(expr(*bits) for bits in product([False, True], repeat=n))

# Закон де Моргана: ¬(p ∧ q) ≡ ¬p ∨ ¬q
demorgan = lambda p, q: (not (p and q)) == ((not p) or (not q))
print("Де Морган — тавтология:", is_tautology(demorgan, 2))

# Контрапозиция: (p → q) ≡ (¬q → ¬p)
contrapos = lambda p, q: ((not p) or q) == ((not (not q)) or (not p))
print("Контрапозиция — тавтология:", is_tautology(contrapos, 2))

# Закон исключённого третьего: p ∨ ¬p
excluded = lambda p: p or (not p)
print("p ∨ ¬p — тавтология:", is_tautology(excluded, 1))

# А это НЕ тавтология: p → q
weak = lambda p, q: (not p) or q
print("p → q — тавтология:", is_tautology(weak, 2))

Вывод:

Де Морган — тавтология: True
Контрапозиция — тавтология: True
p ∨ ¬p — тавтология: True
p → q — тавтология: False

Функция is_tautology — это, по сути, маленький «решатель»: она строит всю таблицу истинности и проверяет, везде ли стоит True. Заметь последнюю строку: p → q не тавтология (она ложна при p=1, q=0) — и машина это честно показала. Так можно проверять любую гипотезу о равносильности: оборачиваем «F == G» в функцию и спрашиваем, тавтология ли это.

Как упрощать формулы по шагам

Упрощение ¬(p → q):

• ¬(p → q) — по закону импликации это ¬(¬p ∨ q).
• По де Моргану: ¬¬p ∧ ¬q.
• По двойному отрицанию: p ∧ ¬q.

Получили: «не верно, что из p следует q» = «p истинно, а q ложно». Логично: импликация нарушается ровно тогда, когда посылка есть, а следствия нет. Каждый шаг — применение одного известного закона; именно так и преобразуют логику в коде и в доказательствах.

От таблиц истинности к железу: логика внутри процессора

Логические связки — это не только про условия в коде. Они физически реализованы в каждом процессоре в виде логических вентилей (gate): крошечных схем из транзисторов, которые вычисляют И, ИЛИ, НЕ над электрическими сигналами (высокое напряжение — 1, низкое — 0). Когда вы пишете if a and b, и когда сумматор процессора складывает два числа, работает одна и та же булева логика.

Например, чтобы сложить два бита, нужен «полусумматор»: бит суммы — это исключающее ИЛИ входов (a ⊕ b), а бит переноса — это И (a ∧ b). Соединив такие блоки в цепочку, инженеры строят сумматоры на 32 и 64 бита — основу арифметики компьютера. Так таблицы истинности, которые мы заполняем на бумаге, оживают в кремнии. Мы подробно вернёмся к этому в разделе о булевой алгебре, но уже сейчас полезно видеть: логика высказываний — это буквально чертёж вычислительной машины.

Типичные ошибки

• Неправильно отрицать импликацию. ¬(p → q) — это p ∧ ¬q, а вовсе не ¬p → ¬q и не p → ¬q.
• Путать контрапозицию с обратной. Контрапозиция ¬q → ¬p равносильна p → q. А «обратная» q → p — нет! Это другое утверждение.
• Применять де Моргана, забывая поменять связку. При вынесении отрицания «и» становится «или» и наоборот, а каждая часть отрицается.

Итог

• Тавтология истинна всегда, противоречие ложно всегда, выполнимая — иногда.
• Формулы равносильны, если их F ↔ G — тавтология (совпадают таблицы).
• Ключевые законы: де Морган, дистрибутивность, контрапозиция, импликация через ИЛИ.
• Равносильность можно проверить перебором всех 2^n наборов значений.