简化布尔表达式算法

问题描述：

任何人都知道简化布尔表达式的算法吗？简化布尔表达式算法

我记得布尔代数和Karnaught地图，但是这是为数字硬件，其中EVERITHING是布尔值。我想要考虑到某些子表达式不是布尔值。

例如：

a == 1 && a == 3

这可以转换为纯布尔表达式：

a1 && a3

但这是表达是不可约的，而具有算术的知识的一点点everibody可以确定该表达式就是：

false

一些机构知道s ome链接？使用谷歌

如果'a'在语言/运行时被声明为volatile变量/字段允许这些变量，并且值在另一个线程上的1和3之间波动？我并不是说这是一个很好的设计，但在软件中，“永远”和“从不”通常是相对的术语。 – 2011-03-15 11:35:29

这不是问题，实际使用的是LINQ Provider，实际值是查询翻译时的值。如果他们的查询再次执行，简化将再次运行，并带有更新的值。 – Olmo 2011-03-15 11:44:09

这是不可能的。例如'a> 0和b> 0和n> 2和a^n + b^n = c^n'总是错误的，但并不容易证明。这意味着你被困在特别的简化中，并且你的问题没有清晰的答案（因为它将取决于你可能会看到的表达的性质）。 – 2011-03-15 11:56:50

答

第一枪发现本文：

http://hopper.unco.edu/KARNAUGH/Algorithm.html

当然，这并不与非布尔子表达式处理。但是后一部分的一般形式确实很难，因为肯定没有算法来检查任意的算术表达式是真的，假的还是其他的。你所要求的是深入到compiler optimization的领域。

我以前正在阅读这篇论文，但是我也发现它很无细节，没有提供任何代码。 – Olmo 2011-03-15 23:53:29

答

您可能感兴趣的K-maps和Quine–McCluskey algorithm。

我觉得SymPy能够解决和简化布尔表达式，查看源可能是有用的。

答

可能的不同值的数量是否有限且已知？如果是这样，你可以将每个表达式转换为布尔表达式。例如，如果a有3个不同的值，那么你可以有变量a1,a2和a3，其中a1为真意味着a == 1等等。一旦你这样做了，你可以依靠Quine-McCluskey算法（这对于更大的例子来说可能更好比卡诺地图）。以下是Quine-McCluskey的Java code。

我无法在这个设计是否会真正简化问题或使其更加复杂说话，但你可能要至少考虑一下。

究竟！，这就是我的意思，但是就像这样，算法将不知道，在我的例子中，a1 && a3实际上是错误的。因为a不能同时为1和3。我认为我需要的是将数值绑定到变量上，并发现卡尔诺指数中的矛盾。 – Olmo 2011-03-15 23:48:39

答

你的特别的例子就是由SMT solver来解决。（它会确定没有变量的设置可以使表达真实的，因此它总是假的更一般的简化是超出范围对于这样求解。）显示一个表达式相当于true或false当然是NP-即使没有将算术带入交易也很困难，所以即使有这么多实用软件也很酷。取决于范围内有多少算术知识，问题may be undecidable。

答

这个问题有两个部分，逻辑简化和表示简化。

为了逻辑简化，Quine-McCluskey。为了简化表示，使用分布标识递归地提取术语（012）。

我详细的过程here。这只给出了使用&和|的解释，但可以修改它以包含所有布尔运算符。

答

这是很难的人。该算法以我找到的最简单的方式匹配每个输入组合的每个输出组合。但这是基本的算法，并没有解决每一个表达式。

如果所有的输出（Q1，Q2，Q3，Q4）一样与即输入的组合则简化的结果将是A.

如果没有，你会尝试另一个variabel /输入依赖。

简化布尔表达式算法

相关推荐