1

假设您有一个像这样的布尔规则/表达式

(A OR B) AND (D OR E) AND F

您想将其转换为尽可能多的 AND 表达式，就像这样

A AND D AND F
A AND E AND F
B AND D AND F
B AND E AND F

你只是在减少 OR，所以它变成了

(A AND D AND F) OR (A AND E AND F) OR (...)

布尔代数中是否有可以做到这一点的属性？

4

6 回答 6

5

看看德摩根定理。该链接指向与电子门有关的文档，但理论保持不变。

它说任何逻辑二进制表达式保持不变，如果我们

  1. 将所有变量更改为它们的补码。
  2. 将所有 AND 操作更改为 OR。
  3. 将所有 OR 操作更改为 AND。
  4. 取整个表达式的补码。

（引用上述链接文件）

于 2009-05-31T15:30:25.563 回答
3

您的示例正在利用 AND 对 OR 的分布性，如此处所示。

您需要做的就是依次应用它。例如，使用x*(y+z) = (x*y)+(x*z)（其中 * 表示 AND，+ 表示 OR）：

0. (A + B) * (D + E) * F
1. Apply to the first 2 brackets results in ((A+B)*D)+((A+B)*E)
2. Apply to content of each bracket results in (A*D+B*D)+(A*E+B*E)
3. So now you have ((A*D+B*D)+(A*E+B*E))*F
4. Applying the law again results in (A*D+B*D)*F+(A*E+B*E)*F
5. Apply one more time results in A*D*F+B*D*F+A*E*F+B*E*F, QED
于 2009-05-31T15:56:28.220 回答
2

您可能有兴趣阅读有关卡诺图的内容。它们是简化布尔表达式的工具，但您也可以使用它们来确定所有单独的表达式。我不确定您如何将其概括为可以编写程序的算法。

于 2009-05-31T17:02:04.983 回答
2

您可能对Conjunctive Normal form或其兄弟Disjunctive normal form感兴趣。

于 2009-05-31T18:39:20.797 回答
0

据我所知，布尔代数不能仅使用 AND 和 OR 运算来构建。如果您只有这两个操作，您将无法接收 NOT 操作。

您可以将任何表达式转换为完整的布尔运算集。

这是一些完整的套装：

  • 与与非
  • OR 和 NOT
于 2009-05-31T15:34:20.983 回答
0

假设您可以使用 NOT 操作，您可以仅使用 AND 或仅使用 OR 来重写任何布尔表达式。在你的情况下：

(A OR B) AND (D OR E) AND F

我倾向于对上述内容使用工程速记并写道：

  • 并且作为产品（。或什么都没有）；
  • 或作为总和 (+)；和
  • 不作为单引号 (')。

所以：

(A+B)(D+E)F

算术的推论实际上对于分解项非常有用。

根据德摩根定律：

(A+B) => (A'B')'

因此，您可以将表达式重写为：

(A+B)(D+E)F
(A'B')'(D'E')'F
于 2009-05-31T15:46:18.923 回答