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

Алгебра логики живёт по тем же правилам, что и обычная алгебра — её законы позволяют упрощать громоздкие выражения до короткой и понятной формы.

Алгебра логики — это раздел математики, изучающий логические высказывания и операции над ними (И, ИЛИ, НЕ). Её законы — это тождества, то есть равенства, верные при любых значениях входящих переменных. Они позволяют преобразовывать одно логическое выражение в равносильное, но более простое.

Зачем вообще упрощать

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

Упрощение нужно по трём причинам:

• Меньше кода и условий. Короткое выражение легче читать и труднее ошибиться.
• Дешевле «железо». В цифровых схемах каждая операция — это логический вентиль. Меньше операций — меньше транзисторов, меньше энергии.
• Быстрее вычисления. Программа проверяет меньше условий.

Обозначения

Будем использовать привычные значки: ∧ — конъюнкция (И, AND), ∨ — дизъюнкция (ИЛИ, OR), ¬ — отрицание (НЕ, NOT). Истину обозначим 1, ложь — 0. Переменные принимают только два значения: 0 или 1.

Таблица основных законов

Каждый закон — это тождество. Слева громоздкая форма, справа равносильная ей. Эти равенства можно проверить перебором всех значений переменных (мы сделаем это ниже кодом).

Отдельно стоит закон двойного отрицания: ¬(¬A) = A. Дважды сказать «неправда, что не A» — это просто сказать «A».

На что обратить внимание

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

Законы де Моргана подробно

Отрицание «И» превращается в «ИЛИ» отрицаний, а отрицание «ИЛИ» — в «И» отрицаний. Знак отрицания «вносится внутрь», а операция меняется на противоположную.

Пример из жизни. Фраза «неправда, что я голоден И устал» означает «я не голоден ИЛИ не устал» — достаточно, чтобы не выполнялось хотя бы одно из условий. Проверим это тождество строго, перебрав все четыре набора значений A и B.

Запустите код ниже. Он перебирает все комбинации A и B, сравнивает левую часть ¬(A ∧ B) с правой ¬A ∨ ¬B и печатает таблицу. Если части совпали на всех наборах — тождество верно.

def check_de_morgan():
    print("A B | not(A and B) | (not A) or (not B)")
    print("-" * 40)
    all_equal = True
    for A in (0, 1):
        for B in (0, 1):
            left = int(not (A and B))
            right = int((not A) or (not B))
            if left != right:
                all_equal = False
            print(A, B, "|     ", left, "      |        ", right)
    print("-" * 40)
    if all_equal:
        print("тождество верно")
    else:
        print("тождество НЕ верно")

check_de_morgan()

В колонках «левая» и «правая» значения совпадают строка в строку, поэтому программа печатает «тождество верно». Точно так же можно проверить любой закон из таблицы — достаточно подставить нужные формулы.

A B | not(A and B) | (not A) or (not B)
----------------------------------------
0 0 |      1       |         1
0 1 |      1       |         1
1 0 |      1       |         1
1 1 |      0       |         0
----------------------------------------
тождество верно

Упрощаем выражения шаг за шагом

Пример 1: поглощение

Упростим A ∨ (A ∧ B).

• Вынесем A за скобку через дистрибутивность: A ∨ (A ∧ B) = (A ∧ 1) ∨ (A ∧ B), ведь A = A ∧ 1.
• Получаем A ∧ (1 ∨ B) по дистрибутивности.
• По закону единицы 1 ∨ B = 1.
• Значит A ∧ 1 = A.

Итог: A ∨ (A ∧ B) = A. Это и есть закон поглощения — мы вывели его из более простых законов.

Пример 2: де Морган плюс дополнение

Упростим ¬(¬A ∧ B) ∨ B.

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

Итог: всё выражение равно 1 — оно истинно при любых A и B. Такие выражения называют тавтологиями.

Пример 3: вынесение общего множителя

Упростим (A ∧ B) ∨ (A ∧ ¬B).

• Вынесем общий множитель A по дистрибутивности: A ∧ (B ∨ ¬B).
• Исключённое третье: B ∨ ¬B = 1.
• Закон единицы: A ∧ 1 = A.

Итог: (A ∧ B) ∨ (A ∧ ¬B) = A. Два условия схлопнулись в одно — переменная B вообще не влияет на результат.

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

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

Коротко

• Законы алгебры логики — это тождества, верные при всех значениях переменных.
• Главные инструменты упрощения: де Моргана, дистрибутивность, поглощение, дополнения (A ∨ ¬A = 1, A ∧ ¬A = 0).
• Любой закон можно проверить перебором всех наборов значений.
• Упрощение даёт более короткий код, экономит вентили в схемах и ускоряет вычисления.