用最少的迭代解决 Java 中的逻辑表达式

Question

我正在解决 Java 中由AND、OR和NOT运算符组成的逻辑表达式。

TRUE如果输入是包含变量的任何布尔值，程序必须输出。我已经成功地做到了，但效率不够。

我目前的解决方案如下：

为表达式中的每个变量制作一个真值表并逐行计算。

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

在上面的示例中，我必须使用 variables 的真值表来评估整个表达式p q r s。

现在，我正在考虑实现一个替代解决方案，如下所示：考虑上面的示例。

我们可以注意到，即使只解决p ∧ ¬q部分，所有的表达式都是TRUE. 这为我们省去了 3 个额外变量的麻烦。

现在，我的问题是这个。如何在 JAVA 中编程？我什至如何知道输入是否具有上述模式？或者它只是我必须为整个真值表评估的表达式？比如下面这张

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

Answer 1

这是一个众所周知的 NP 完全问题，请参阅Boolean Satisfiability Problem。这意味着没有已知的多项式时间解，但有许多 >P 解。您将不得不暴力破解它并在可能的地方短路。（例如：如果所有运算符都是or并且您找到一个true值，您可以停止计算）