简化布尔代数表达式

Question

从一个具有三个输入和两个输出的减法器的真值 table 开始，我得到了第二个输出 z2 的以下布尔公式（左侧位的 "loan"） :

z2 = x0'x1'x2 + x0'x1x2' + x0'x1x2 + x0x1x2

（其中 x0' 表示 不是 x0）。

简化它：z2 = x2(x0 ⊕ x1)' + x1(x0 ⊕ x2)' + x1x2

这意味着：z2 = x2(x0 XNOR x1) + x1(x0 XNOR x2) + x1x2

我可以再简化一下吗？我已经尝试过 z2 = (x0 XNOR x1) + (x0 XNOR x2) + x1x2 但它没有成功。

Answer 1

您的原始表达式有 12 个变量引用和 16 个运算符。您的简化有 8 个变量引用和 7 个运算符。这是一个包含 6 个变量引用和 6 个运算符的表达式：

z2 = x0x1x2 + x0'(x1+x2)

我不知道这在任何意义上都是最小的。

你问我是怎么找到那个表情的。我不是从你的简化开始的，我是从你在评论中引用的真相 table 开始的。我在这里复制它：

当我查看 table 寻找模式时，我发现它看起来像一个交叉矩阵或斜对称矩阵：如果我将最后一列倒置，然后取我结束的所有项目的补码与原来的专栏。（我不知道这种对称性的正确术语；这些是我想到的术语。）我试图将这种对称性封装到逻辑表达式中，但失败了。

这让我查看了最后一列的上半部分和下半部分。上半部分主要是 1，下半部分主要是 0。然后令我震惊的是，上半部分看起来像二进制 OR 运算的真值 table，而下半部分看起来像二进制 AND 运算。当然，上半部分用于 x0'，下半部分用于 x0。把这些事实放在一起给了我我的表情。

我通过查看是否可以将原始表达式操纵到我的表达式中来确认该表达式。我可以这样做

z2 = x0'x1'x2 + x0'x1x2' + x0'x1x2 + x0x1x2
   = x0'(x1'x2 + x1x2' + x1x2) + x0x1x2
   = x0'(x1 + x2) + x0x1x2
   = x0x1x2 + x0'(x1 + x2)

从第二行到第三行的过渡，当然就相当于认识了二元或的真实性table，所以这和我实际的发现方法没有太大区别。

后一种方法可能更适用于其他问题：从多个项中分解出一个公因数。我的实际方法更有趣，但不易转移。我最喜欢的数学定义是 "the study of patterns"，它解释了为什么该方法很有趣。

Simplify boolean algebra expression