Упрощение булевых формул без отрицания, просто и / или

Question

Я бы хотел предварительно обработать логические формулы так, чтобы а и (а или б) и с

становится просто а и с

Отрицаний никогда не бывает, поэтому это должна быть простая проблема, но в голову не приходит ничего по-настоящему очевидного (кроме складывания и-в-или,-или-или-дублирования, сортировки). Возможно, я что-то упускаю совершенно очевидное?

Answer 1

У меня был похожий вопрос на CSTheory.stackexchange, я ответил отрицательно здесь .

Проблема, которую вы описываете, является трудной для coNP.Таким образом, если P = NP, вы не найдете эффективный алгоритм для этого.

Преобразование в CNF или DNF приведет к экспоненциальному увеличению некоторых формул.

Answer 2

Из вашего примера не совсем понятно, что вы хотите вообще.

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

A ∨ (A ∧ B) = A 

A ∧ (A ∨ B) = A 

В вашем примере вам просто нужно применить второй закон поглощения один раз.

Answer 3

Используйте K-карту .

По сути, вы создадите график возможных результатов формулы в памяти.Проанализируйте его и сохраните таким образом, чтобы при произвольном вводе для всех переменных вы могли получить результат.Затем создайте массив N-размерности (где N - это число переменных) и попробуйте каждую комбинацию, сохранив результат в массиве.

Как только это будет сделано, выполните действия, описанные в статье выше, чтобы найтиУпрощенное выражение.

Обратите внимание, что это будет работать для выражений, содержащих все типы логических операторов, включая not.

Answer 4

Рассмотрите возможность преобразования в CNF или DNF .

Упростить "нижний уровень" легко - просто удалите дубликаты.Упростить следующий уровень почти так же просто - удалите подмножества или надмножества.

Answer 5

А (А + В) С

AAC + ABC

AC + ABC

A1C + ABC

А (1 + В) С

А (1) С

AC

Это то, что вы искали?