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

Question

У меня есть два логических выражения:

¬aΛ¬b V ¬aΛ¬c V aΛ¬bΛ¬c #1

¬aΛ¬b V ¬aΛ¬c V ¬bΛ¬c #2

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

Вы можете заметить, что ЕДИНСТВЕННАЯ разница между ними состоит в том, что у #1 есть дополнительный "a" в его последнем ИЛИ сроке. Различные методы факторинга, чтобы попытаться избавиться от лишних "а", оказались безуспешными.

Answer 1

Я не знаю точно, что вы подразумеваете под "выражением по выражению", но если вы разобьете их на основании того, является ли a истинным или ложным, это становится легко увидеть.

Если a верно (первые два слагаемых являются ложными как в Eq1, так и в Eq2):
Eq1 => ~b & ~c
Eq2 => ~b & ~c

Если a ложно:
Eq1 => ~b | ~c
Eq2 => ~b | ~c | (~b & ~c) == Уравнение

редактировать: вы можете сделать этот же аргумент более формально, используя логические тождества:

(~a & ~b | ~a & ~c | ~b & ~c) == ((~a & ~b) | (~a & ~c) | (~b & ~c)) & (a | ~a)

поскольку (a | ~a) == 1 а также x & 1 = x

Затем с помощью распределения & над |:

== (((~a & ~b) | (~a & ~c) | (~b & ~c)) & a) | (((~a & ~b) | (~a & ~c) | (~b & ~c)) & ~a)

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

((~a & ~b) | x) & a) == (a & ~a & b) | (a & x) == 0 | (a & x) == a & x

где х два других или выражения. Следование этой стратегии даст вам тот же ответ, что и выше. Если вы застрянете, я отведу вас дальше, но вы сможете забрать это отсюда.

Answer 2

Для этого вам необходимо преобразовать выражения в дизъюнктивную нормальную форму. Чтобы сделать это, вы создаете дизъюнкцию элементарных союзов: для каждого 1 в таблице истинности запишите соответствующее соединение всех переменных или их инверсий, а затем сделайте дизъюнкцию всех этих союзов. Конъюнктивная нормальная форма также существует, но она используется реже.

Дизъюнктивные нормальные формы становятся достаточно большими для выражений многих переменных. В этом случае вы можете захотеть использовать алгоритмы минимизации (например, алгоритм Quine-McCluskey), но это довольно сложный и дорогой вычислительный процесс (проблема минимизации сложна с точки зрения NP, и время выполнения для этих алгоритмов обычно экспоненциально хуже, чем просто вычисление правды Таблица).

Если вам просто нужно универсальное представление для сравнения любых логических выражений тех же переменных, вы можете также сравнить таблицы истинности для этих выражений:

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