如何检查两个布尔表达式是否等效 [英] How to check if two boolean expressions are equivalent

问题描述

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

How can I know if two boolean expresions are equivalent?

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

我认为我应该...

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

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

For example, with the step two I get:

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)

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

Now I have to know if have the same groups. One way can be getting the hash of each group:

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哈希是所有哈希的md5.

I can do the md5 of each group, sort, and the expr hash is the md5 of all hashs.

但是问题是...如何减少exprs?有什么算法吗?表达式仅使用AND和OR运算符.

But the problem is... How can I reduce the exprs? Is there any algorithm? The expressions use only AND and OR operators.

推荐答案

有什么算法吗?

理论答案:

• 您要解决的问题是布尔可满足性问题，也称为SAT.

它是 NP-完成.

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

THAT MEANS, that there are no known algorithms¹ that always find a solution for a SAT problem in polynomial time; i.e. no algorithm that whose worst case is O(N^C) or better, where C is a constant and N is the number of variables in the SAT problem.

有一个显而易见的解决方案，是对解决方案空间进行 O(2 ^ N) ...蛮力搜索.存在更好的算法；参见维基百科文章，但在最坏的情况下它们都是指数级的.

There is an obvious solution that is O(2^N) ... brute-force search of the solution space. Better algorithms exist; see the Wikipedia article but they are all exponential in the worst-case.

实际解决方案:

• 对于很小的 N ，蛮力可能会提供可接受的性能.

• For really small N, brute force may give acceptable performance.

使用现有的SAT解算器，请记住该理论认为在最坏的情况下它具有指数行为.

Use an existing SAT solver, bearing in mind that the theory says that it has exponential behavior in the worst case.

避免大号 N 的问题...或对您的应用程序进行编码，以使求解器具有时间限制"；也就是说，如果在规定的时间内无法解决问题，它将放弃.

Avoid problems with large N ... or code your application so that the solver is "time boxed"; i.e. it gives up if it can't get a solution in a prescribed time.

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

^{1 - If it is ever proven that P == NP, then better algorithms may emerge for this and other NP-complete problems.}

这篇关于如何检查两个布尔表达式是否等效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！