有人知道一种简化布尔表达式的算法吗？
我记得布尔代数和卡诺图，但这是为数字硬件设计的，其中一切都是布尔类型。我想要的是考虑到一些子表达式不是布尔类型的东西。
例如：
a == 1 && a == 3
这可以被翻译成一个纯布尔表达式：
a1 && a3
但是这个表达式是不可约的，尽管稍微了解算术的人都可以确定这个表达式只是:
false
有人知道一些链接吗？
简化布尔表达式算法
19
- Olmo
4
5如果在允许使用volatile变量/字段的编程语言/运行时中声明变量a为volatile，则在另一个线程中，该变量的值会在1和3之间波动。我并不是说这是一种好的设计，但在软件开发中，“总是”和“从不”通常是相对的概念。 - Lasse V. Karlsen
这不是问题，实际用途是为了 LINQ 提供程序，实际值是查询被翻译时的值。如果查询再次执行，则会再次运行简化，并使用更新后的值。 - Olmo
5通常情况下是不可能的。例如，“a>0且b>0且n>2且a^n+b^n=c^n”始终为假，但很难证明。这意味着你只能采用特定的简化方法，而没有清晰的答案来回答你的问题（因为答案将取决于你可能遇到的表达式的性质）。 - user97370
你说得对，但由于这只是一个简化算法，我对任何能改进问题的算法都没有意见，即使它并不是最佳解决方案。我的主要场景是针对枚举和引用类型的等式和不同操作符。如果能实现整数的 == >= > < <= != 操作符，那将是很好的补充。 - Olmo
6个回答
6
这个问题有两个部分，逻辑简化和表达式简化。
对于逻辑简化，使用Quine-McCluskey算法。对于表达式简化，使用分配恒等式(0&1|0&2) == 0&(1|2)递归提取项。
我在这里详细说明了这个过程。这给出了仅使用&和|的解释，但它可以修改以包括所有布尔运算符。
对于逻辑简化，使用Quine-McCluskey算法。对于表达式简化，使用分配恒等式(0&1|0&2) == 0&(1|2)递归提取项。
我在这里详细说明了这个过程。这给出了仅使用&和|的解释，但它可以修改以包括所有布尔运算符。
- douggard
3
可能的不同值的数量是有限且已知的吗？如果是，则可以将每个表达式转换为布尔表达式。例如，如果a有3个不同的值，则可以使用变量a1、a2和a3，其中a1为true表示a == 1，依此类推。一旦这样做了，您就可以依赖于Quine-McCluskey算法（对于较大的示例而言，这可能比Karnaugh图更好）。这里是一些关于Quine-McCluskey的Java代码。
我不能确定这种设计是否会真正简化事情或使它们更加复杂，但至少您可能需要考虑一下。
- Michael McGowan
1
没错，这就是我的意思，但是这样算法将不知道，在我的例子中，a1 && a3 实际上是 false。因为 a 不能同时是 1 和 3。我认为我需要将值绑定到变量并在 Karnaught 最小项中找到矛盾。 - Olmo
2
第一次使用谷歌找到了这篇论文：
http://hopper.unco.edu/KARNAUGH/Algorithm.html
当然，这并没有涉及非布尔子表达式的处理。但是后者的通用形式确实很难，因为绝对没有算法可以检查任意算术表达式是否为真、假或其他。你所要求的深入到了编译器优化领域。
- Doc Brown
1
我之前在看论文，但发现论文缺乏细节说明并且没有提供任何代码。 - Olmo
-1
这很难。我找到的最简单的算法是将每个输出组合与每个输入组合进行匹配。但那只是基本算法，不能解决每个表达式。
如果所有输出（q1、q2、q3、q4）与例如输入A组合相同，则化简的结果将为A。
如果不是，则尝试另一个变量/输入依赖关系。
- The Mr. Totardo
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接