Решение логических выражений в Java с минимальными итерациями

Question

Я работаю над решением логических выражений в Java, состоящих из AND , OR и NOT операторов.

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

Мое текущее решение выглядит следующим образом:

Создайте таблицу истинности для каждой переменной в выражении и оценивайте строку за строкой.

(p ∧ ¬q) ∨ (r ∧ s) ∨ (¬p ∨ u)

В приведенном выше примере мне придется оценивать все выражение с помощью таблицы истинных переменных p q r s.

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

Мы можем заметить, что даже если просто решить часть p ∧ ¬q, все выражение получится равным TRUE.Это спасает нас от лишних 3 переменных.

Теперь мой вопрос таков.Как запрограммировать это в JAVA?Как мне узнать, есть ли на входе шаблон, подобный описанному выше?Или это просто выражение, которое я должен оценить для всей Таблицы правды?Как показано ниже

(p ∨ ¬q) ∧ (r ∨ (s ∧ (¬p ∨ u)))

Answer 1

Это хорошо известная NP-полная проблема, см. Булева проблема удовлетворенности .

Это означает, что не существует известного решения за полиномиальное время, но существует множество решений> P.

Вам придется использовать грубую силу и короткое замыкание, где это возможно.(например: если все операторы or и вы нашли значение true, вы можете остановить вычисление)