如何检查两个布尔表达式是否相等

Question

我怎么知道两个布尔表达式是否相等？

String expr1 = "(A or B) and C";
String expr2 = "C and (B or A)";
boolean equals = areExprsEquals(expr1, expr2);

我想我应该...

1. 解析存储在某些结构数据中的表达式
2. 减少 OR 组中的表达式
3. 检查两个表达式是否有相同的组

例如，通过第二步我得到：

Expr1
(A or B) and C
Converted to:
(A and C) or (B and C)

Expr2
C and (B or A)
Converted to:
(C and B) or (C and A)

现在我必须知道是否有相同的组。一种方法是获取每个组的哈希值：

Exp1:

group 1: 
(A and C)
Order:
(A and C)
Hash:
md5("a&c")

group 2:
(B and C)
Order:
(B and C)
Hash:
md5("b&c")

Exp2:

group 1: 
(C and B)
Order:
(B and C)
Hash:
md5("b&c")

group 2:
(C and A)
Order:
(A and C)
Hash:
md5("a&c")

所以：

expr1: md5( sort(md5("a&c"), md5("b&c") ))
expr2: md5( sort(md5("b&c"), md5("a&c") ))

我可以做每组的md5，排序，expr hash就是所有hash的md5

但问题是...我怎样才能减少 exprs？有什么算法吗？表达式仅使用 AND 和 OR 运算符。

Answer 1

Is there any algorithm?

理论答案：

• 您要解决的问题是 Boolean Satisfiability Problem 也称为 SAT。

• 是NP-complete.

• 这意味着，没有已知算法¹ 总能在多项式时间内找到 SAT 问题的解决方案；即没有算法的最坏情况是 O(N^C) 或更好，其中 C 是常数，N 是 SAT 问题中的变量数。

• 有一个明显的解决方案是 O(2^N) ...解决方案 space 的暴力搜索。存在更好的算法；参见the Wikipedia article，但在最坏的情况下它们都是指数级的。

实用解决方案：

• 对于非常小的N，蛮力可能会给出可接受的性能。

• 使用现有的 SAT 求解器，请记住理论表明它在最坏情况下具有指数行为。

• 避免大 N 的问题...或对您的应用程序进行编码，使求解器为 "time boxed"；即如果在规定的时间内不能得到解就放弃

---

^{1 - 如果曾经证明 P == NP，那么针对这个问题和其他 NP 完全问题可能会出现更好的算法。}