Равносильность логических выражений

Теория

Два логических выражения называют равносильными, если на любом наборе значений переменных они принимают одинаковые значения. Равносильность записывают знаком \(\equiv\), например \(A \to B \equiv \neg A \lor B\). Проверить её проще всего таблицей истинности: если столбцы значений двух выражений совпали во всех строках, выражения равносильны; если нашлась строка с разными значениями, эта строка и есть контрпример.

Равносильные преобразования позволяют упрощать выражения без таблицы истинности — именно на них построены задания «упростите логическое выражение». Основные законы: переместительный, сочетательный и распределительный (те же, что в арифметике), законы де Моргана \(\neg(A \land B) \equiv \neg A \lor \neg B\), идемпотентность \(A \land A \equiv A\), поглощение \(A \lor (A \land B) \equiv A\) и исключение третьего \(A \lor \neg A \equiv 1\).

Значение выражения при заданных значениях переменных считают по действиям: сначала скобки и отрицания, затем конъюнкции, затем дизъюнкции, затем импликации и эквивалентности.

Важно: чтобы доказать неравносильность, достаточно одного набора значений, на котором выражения разошлись. Чтобы доказать равносильность, нужно проверить все \(2^n\) наборов — один удачный пример ничего не доказывает.

Пример с решением

1. Условие. Равносильны ли выражения \(A \land B\) и \(\neg(\neg A \lor \neg B)\)?
2. Переменные. Переменных две — A и B, наборов \(2^2 = 4\).
3. Первая строка. \(A = 0\), \(B = 0\): \(A \land B = 0\); \(\neg A \lor \neg B = 1 \lor 1 = 1\), а \(\neg 1 = 0\). Значения совпали.
4. Третья строка. \(A = 1\), \(B = 0\): \(A \land B = 0\); \(\neg A \lor \neg B = 0 \lor 1 = 1\), а \(\neg 1 = 0\). Значения снова совпали.
5. Последняя строка. \(A = 1\), \(B = 1\): \(A \land B = 1\); \(\neg A \lor \neg B = 0 \lor 0 = 0\), а \(\neg 0 = 1\). Совпадение.
6. Ответ. Выражения равносильны на всех четырёх наборах — это закон де Моргана. Калькулятор в режиме проверки равносильности ответит «выражения равносильны», а для пары \(A \land B\) и \(A \lor B\) укажет контрпример \(A = 0\), \(B = 1\).

Главное

• Равносильность — совпадение значений на всех \(2^n\) наборах переменных.
• Контрпример — один набор, где значения разошлись: его достаточно для ответа «не равносильны».
• Законы де Моргана проносят отрицание внутрь скобок, меняя \(\land\) на \(\lor\).
• Порядок действий: скобки и \(\neg\), затем \(\land\), затем \(\lor\), затем \(\to\), затем \(\equiv\).