Как проверить, что два логических выражения равны (равносильны)?
Упростил длинное выражение и получил короткое. Но как убедиться, что я нигде не ошибся и они действительно означают одно и то же? Есть надёжный способ проверить, что два разных по виду логических выражения равносильны?
2 ответа
Самый надёжный способ — построить таблицы истинности для обоих выражений и сравнить итоговые столбцы. Если столбцы совпали во всех строках — выражения равносильны (записывают как F₁ ≡ F₂).
Пример. Проверим, верно ли упрощение ¬(¬A ∧ ¬B) = A ∨ B:
| A | B | ¬(¬A∧¬B) | A∨B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Столбцы совпали полностью → выражения равны (это, кстати, де Морган).
Главное — обе таблицы строй с одинаковым порядком строк (комбинаций переменных), иначе сравнение будет бессмысленным.
Есть и второй способ: показать, что F₁ ↔ F₂ — тавтология (эквивалентность истинна во всех строках). Это то же самое, просто записано через эквивалентность: если она всегда 1, значит выражения совпадают везде.
Если переменных немного, можно проверить кодом за секунды:
from itertools import product
f1 = lambda a, b: not(not a and not b)
f2 = lambda a, b: a or b
print(all(f1(a,b)==f2(a,b) for a, b in product([0,1], repeat=2)))
# True → выражения равносильны
Перебрал все комбинации, сравнил — если везде True, упрощение точно верное. Удобно для самопроверки домашки.