Законы алгебры логики и упрощение выражений

Как из громоздкого логического выражения сделать короткое и понятное — по строгим правилам.

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

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

Запутанное условие вроде not (a and not b) or (a and b) легко содержит ошибку и тяжело читается. Алгебра логики — это, по сути, «алгебраические» правила, позволяющие переписать выражение в эквивалентное, но более простое. Это и экономия вентилей в микросхеме, и читаемый код, и прямой путь к решению логических заданий ЕГЭ, где требуется упростить выражение или построить схему.

Зачем вообще упрощать, если компьютер посчитает любое выражение? Причин несколько, и все они практические. Во-первых, упрощённое условие быстрее вычисляется и занимает меньше места — в микросхеме это буквально означает меньше транзисторов, меньше энергии, меньше тепла. Во-вторых, короткое выражение легче проверить на правильность: глядя на A, вы сразу видите смысл, а в нагромождении из десятка скобок ошибку не заметить. В-третьих, упрощение — это способ доказать, что два разных на вид условия делают одно и то же; такие доказательства лежат в основе проверки и оптимизации программ. Алгебра логики даёт вам строгий инструмент вместо догадок: не «кажется, это то же самое», а «по таким-то законам это в точности равно».

Аналогия с обычной алгеброй

Многие законы логики похожи на школьную алгебру, если думать про ∧ как про умножение, а про ∨ как про сложение. Например, дистрибутивность A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) — это «раскрытие скобок». Но есть и сюрпризы: в логике работает и «обратная» дистрибутивность через ∨, которой в арифметике нет.

Основные законы

Законы де Моргана — самые полезные

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

def check(f, g):
    # сравниваем две функции по всем комбинациям A, B
    for a in (0, 1):
        for b in (0, 1):
            if bool(f(a, b)) != bool(g(a, b)):
                return False
    return True

# not (A and B) == (not A) or (not B)
law1 = check(lambda a, b: not (a and b),
             lambda a, b: (not a) or (not b))
# not (A or B) == (not A) and (not B)
law2 = check(lambda a, b: not (a or b),
             lambda a, b: (not a) and (not b))
print("Первый закон де Моргана верен:", law1)
print("Второй закон де Моргана верен:", law2)

Вывод:

Первый закон де Моргана верен: True
Второй закон де Моргана верен: True

Упрощаем шаг за шагом

Упростим выражение (A ∧ B) ∨ (A ∧ ¬B). Вынесем A за скобку (дистрибутивность): A ∧ (B ∨ ¬B). По закону дополнения B ∨ ¬B = 1. Значит, всё выражение равно A ∧ 1 = A. Длинное условие свелось к одной переменной! Проверим, что таблицы совпадают:

def original(a, b):
    return (a and b) or (a and not b)

def simplified(a):
    return a

ok = True
for a in (0, 1):
    for b in (0, 1):
        if bool(original(a, b)) != bool(simplified(a)):
            ok = False
        print(f"A={a} B={b}: исходное={int(bool(original(a,b)))}  упрощённое={int(bool(simplified(a)))}")
print("Упрощение корректно:", ok)

Вывод:

A=0 B=0: исходное=0  упрощённое=0
A=0 B=1: исходное=0  упрощённое=0
A=1 B=0: исходное=1  упрощённое=1
A=1 B=1: исходное=1  упрощённое=1
Упрощение корректно: True

Закон поглощения на практике

Поглощение часто прячется в реальном коде. Условие «пользователь админ ИЛИ (пользователь админ И подтверждён)» избыточно: по закону A ∨ (A ∧ B) = A оно равно просто «пользователь админ». Убедимся перебором:

def verbose(admin, confirmed):
    return admin or (admin and confirmed)

for admin in (0, 1):
    for confirmed in (0, 1):
        print(f"admin={admin} confirmed={confirmed}: "
              f"{int(bool(verbose(admin, confirmed)))} (равно admin={admin})")

Вывод:

admin=0 confirmed=0: 0 (равно admin=0)
admin=0 confirmed=1: 0 (равно admin=0)
admin=1 confirmed=0: 1 (равно admin=1)
admin=1 confirmed=1: 1 (равно admin=1)

Попробуй сам

Универсальный «проверятель равносильности» для трёх переменных. Меняйте функции f и g и проверяйте свои упрощения — компьютер не даст ошибиться.

from itertools import product

def equivalent(f, g, nvars=3):
    for values in product((0, 1), repeat=nvars):
        if bool(f(*values)) != bool(g(*values)):
            return False, values   # нашли контрпример
    return True, None

# Проверим: A or (B and C) равно (A or B) and (A or C)
f = lambda a, b, c: a or (b and c)
g = lambda a, b, c: (a or b) and (a or c)
ok, bad = equivalent(f, g)
print("Равносильны:", ok, "" if ok else f"контрпример {bad}")

Вывод:

Равносильны: True 

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

• Неправильно применяют де Моргана. Отрицание вносится внутрь с обязательной заменой ∧ ↔ ∨, а не просто «навешивается» на каждую переменную.
• Забывают про двойное отрицание. ¬¬A = A — два минуса дают плюс, как в алгебре.
• Путают поглощение и идемпотентность. A ∨ (A ∧ B) = A (поглощение), а A ∨ A = A (идемпотентность) — это разные правила.
• Упрощают «на глаз» без проверки. Любое упрощение легко проверить таблицей; не ленитесь это делать.

Итоги

• Равносильные выражения имеют одинаковые таблицы истинности; цель упрощения — сократить запись, сохранив значения.
• Ключевые законы: де Моргана, поглощение, дистрибутивность, дополнение, свойства констант.
• Де Моргана вносит отрицание внутрь скобок, меняя ∧ на ∨ и наоборот.
• Любое упрощение проверяется полным перебором значений — Python делает это мгновенно.