简化布尔表达式算法
有人知道简化布尔表达式的算法吗？
我记得布尔代数和卡诺图，但这适用于数字硬件，其中一切都是布尔值。我想要一些考虑到某些子表达式不是布尔值的东西。
例如：
a == 1 && a == 3
这可以翻译为纯布尔表达式：
a1 && a3
但这表达式是不可约的，而只要有一点算术知识，每个人都可以确定该表达式只是：
false
有人知道一些链接吗？
Anybody knows of an algorithm to simplify boolean expressions?
I remember the boolean algebra and Karnaught maps, but this is meant for digital hardware where EVERITHING is boolean. I would like something that takes into account that some sub-expressions are not boolean.
For example:
a == 1 && a == 3
this could be translated to a pure boolean expression:
a1 && a3
but this is expression is irreducible, while with a little bit of knowledge of arithmetics everibody can determine that the expression is just:
false
Some body knows some links?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您可能对K-maps 和Quine–McCluskey 算法。
我认为 SymPy 能够解决和简化布尔表达式，查看源代码可能会有用。
You might be interested in K-maps and the Quine–McCluskey algorithm.
I think SymPy is able to solve and simplify boolean expressions, looking at the source might be useful.
您的特定示例将由 SMT 求解器 求解。 （它会确定任何变量设置都不能使表达式为真；因此它始终为假。更一般的简化超出了此类求解器的范围。）表明表达式等效于
true或者false当然是 NP 困难的，即使没有将算术引入到交易中，所以即使有这么多的实用软件也是非常酷的。根据范围内算术知识的多少，问题可能是不可判定的 。Your particular example would be solved by an SMT solver. (It'd determine that no setting of the variables could make the expression true; therefore it's always false. More-general simplification is out of scope for such solvers.) Showing that an expression is equivalent to
trueorfalseis of course NP-hard even without bringing arithmetic into the deal, so it's pretty cool that there's practical software for even this much. Depending on how much arithmetic knowledge is in scope, the problem may be undecidable.这个问题有两个部分，逻辑简化和表示简化。
为了逻辑简化，Quine-McCluskey。为了简化表示，使用分布恒等式 (0&1|0&2) == 0&(1|2) 递归提取项。
我在此处详细介绍了该过程。仅使用 & 给出了解释和 |，但可以修改它以包含所有布尔运算符。
There are two parts to this problem, logical simplification and representation simplification.
For logical simplification, Quine-McCluskey. For simplification of the representation, recursively extract terms using the distribution identity (0&1|0&2) == 0&(1|2).
I detailed the process here. That gives the explanation using only & and |, but it can be modified to include all boolean operators.
可能的不同值的数量是否有限且已知？如果是这样，您可以将每个表达式转换为布尔表达式。例如，如果 a 有 3 个不同的值，那么您可以使用变量
a1、a2和a3，其中a1为true 意味着a == 1等。一旦你这样做了，你就可以依赖 Quine-McCluskey 算法（对于更大的例子来说，这可能比卡诺图更好）。以下是 Quine-McCluskey 的一些 Java 代码。我不能说这个设计是否真的会简化事情或使事情变得更加复杂，但你可能至少要考虑一下。
Is the number of possible distinct values finite and known? If so you could convert each expression into a boolean expression. For instance if a has 3 distinct values then you could have variables
a1,a2, anda3wherea1being true means thata == 1, etc. Once you did that you could rely on the Quine-McCluskey algorithm (which is probably better for larger examples than Karnaugh maps). Here is some Java code for Quine-McCluskey.I can't speak to whether this design would actually simplify things or make them more complicated, but you might want to consider it at least.
使用 Google 第一次发现这篇论文：
http://hopper.unco.edu/KARNAUGH/Algorithm.html
当然，这不处理非布尔子表达式。但后一部分的一般形式确实很难，因为绝对没有算法来检查任意算术表达式是真、假还是其他。您所要求的内容深入到编译器优化领域。
First shot using Google found this paper:
http://hopper.unco.edu/KARNAUGH/Algorithm.html
Of course, that does not deal with non-boolean subexpressions. But this latter part in its general form is really hard, since there is definitely no algorithm to check if an arbitrary arithmetic expression is true, false or whatever. What you are asking for goes deeply into the field of compiler optimization.
这是一个很难的人。我发现的最简单的算法是将每个输出组合与每个输入组合进行匹配。但这是基本算法，并没有解决每个表达式。
如果所有输出（q1，q2，q3，q4）与即输入A组合相同，则简化的结果将为A。
如果不是，您将尝试另一个变量/输入依赖项。
This is hard man. The algorithm in the simplest way that I found was match every output combination with each input each combination. But that's the basic algorithm, didn't solve every expression.
If all output (q1,q2,q3,q4) is same with for i.e input A combination then the result of simplification will be A.
If not, you will try another variabel / input dependency.