computer-science - 如何减少逻辑语句？

Question

我很确定我记得在我的一门大学类(class)中做过这样的事情，并且有某种公式可以解决，但我的想法让我失望。

给定语句:( a OR b OR d ) AND ( a OR c )

我很确定这可以简化为:( a OR b OR d OR c )

但我不记得我将如何证明它。

也许这是一系列逻辑表？

Answer 1

你不能将“( a OR b OR d ) AND ( a OR c ) ”简化为“( a OR b OR d OR c )”，因为前者不满足于“c=true, a,b,d=false” ，而后者是。所以你也不能证明减少是正确的:)

一般来说，有很多方法可以减少 bool 公式的大小，这也是一个你想要优化的问题(总大小？条件评估的平均次数？)。卡诺图仅适用于少数变量。将大的 bool 公式化简为较小的公式是一个高级主题，例如自动逻辑电路设计。