Как преобразовывать логические выражения с помощью законов алгебры логики?

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

Базовые приоритеты

Отрицание обычно выполняется раньше конъюнкции, а конъюнкция — раньше дизъюнкции. Скобки устраняют двусмысленность и важнее привычного порядка. Импликация A → B ложна только при истинном A и ложном B; её удобно заменять выражением ¬A ∨ B.

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

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

Поглощение и распределение

Формула A ∨ (A ∧ B) сокращается до A, потому что второе слагаемое не добавляет новых истинных наборов. Распределительные законы позволяют раскрывать и собирать скобки, как в обычной алгебре, но с двумя взаимно двойственными вариантами. Идемпотентность даёт A ∨ A = A и A ∧ A = A.

Равносильность

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

Разбор без угадывания

Выпишите используемую замену рядом с каждой строкой преобразования. После упрощения проверьте крайние наборы: все нули, все единицы и набор, на котором меняется ключевое условие. Такое оформление помогает на устной части восстановить логику решения, а не только назвать финальную формулу.

Равносильность можно проверить исчерпывающе

Алгебраическое преобразование даёт доказательство, а таблица значений — быстрый способ обнаружить ошибку. Для небольшого числа переменных переберите все наборы и найдите первый контрпример. В Python логическая импликация A→B записывается как not A or B; отдельного оператора для неё нет.

from itertools import product

def left(a: bool, b: bool, c: bool) -> bool:
    return not (a and (b or c))

def right(a: bool, b: bool, c: bool) -> bool:
    return (not a) or ((not b) and (not c))

for values in product((False, True), repeat=3):
    assert left(*values) == right(*values), values
print("Формулы равносильны")

Если проверка прошла, это доказывает равносильность для конечного пространства наборов, но не объясняет цепочку законов. На устном ответе полезно показать оба уровня: преобразовать выражение по де Моргану и затем назвать перебор независимой верификацией.

Практика: контрпример вместо впечатления

Проверьте утверждения A→B = B→A и A→B = ¬B→¬A. Для каждого неверного равенства программа должна напечатать первый набор, где значения различаются; для верного — пройти все строки. После эксперимента перепишите импликации через НЕ и ИЛИ и объясните результат законами. Добавьте третью пару формул с тремя переменными и заранее предскажите, будет ли она равносильной.