有人知道简化布尔表达式的算法吗？
我记得布尔代数和卡诺特图，但这适用于所有都是布尔值的数字硬件。我想要一些考虑到某些子表达式不是布尔值的东西。
例如：
a == 1 && a == 3
这可以转换为纯布尔表达式：
a1 && a3
但这是表达式是不可约的，而只要有一点算术知识，每个人都可以确定表达式是正确的：
false
有人知道一些链接吗？
问问题
15991 次
6 回答
10
您可能对K-map和Quine-McCluskey 算法感兴趣。
我认为 SymPy 能够解决和简化布尔表达式，查看源代码可能很有用。
于 2011-03-15T14:10:06.600 回答
7
您的特定示例将由SMT solver 解决。（它会确定没有任何变量设置可以使表达式为真；因此它总是错误的。更一般的简化超出了此类求解器的范围。）表明表达式等于true或false当然是 NP 难的没有将算术纳入交易，所以即使有这么多的实用软件也很酷。根据范围内有多少算术知识，问题可能是不可判定的。
于 2011-03-15T23:35:53.370 回答
5
这个问题有两个部分，逻辑简化和表示简化。
为简化逻辑，Quine-McCluskey。为了简化表示，使用分布恒等式 (0&1|0&2) == 0&(1|2) 递归提取术语。
我在这里详细介绍了这个过程。这给出了仅使用 & 和 | 的解释，但可以对其进行修改以包括所有布尔运算符。
于 2014-03-05T18:50:53.553 回答
3
可能的不同值的数量是有限且已知的吗？如果是这样，您可以将每个表达式转换为布尔表达式。例如，如果 a 有 3 个不同的值，那么你可以有变量a1,a2和a3wherea1是 true 意味着a == 1等等。一旦你这样做了，你可以依赖 Quine-McCluskey 算法（这对于更大的例子可能比卡诺图更好）。这是 Quine-McCluskey 的一些Java 代码。
我不能说这种设计是否真的会简化事情或让事情变得更复杂，但你可能至少想考虑一下。
于 2011-03-15T14:33:36.407 回答
2
第一次使用谷歌发现这篇论文：
http://hopper.unco.edu/KARNAUGH/Algorithm.html
当然，这不涉及非布尔子表达式。但是一般形式的后半部分确实很难，因为绝对没有算法来检查任意算术表达式是真、假还是什么。您所要求的内容深入到编译器优化领域。
于 2011-03-15T12:03:48.873 回答
-1
这是个硬汉。我发现的最简单的算法是将每个输出组合与每个输入组合匹配。但这是基本算法，并没有解决每个表达式。
如果所有输出 (q1,q2,q3,q4) 与输入 A 组合相同，则简化结果将为 A。
如果没有，您将尝试另一个变量/输入依赖项。
于 2015-03-24T13:39:40.327 回答