数字电路学习笔记（四）：逻辑代数系统

逻辑代数系统由基本公式、常用公式、基本规则三部分构成。掌握了这些，设计出的电路可以尽可能地简单，减少故障几率和元件使用；编程时，如果掌握了逻辑函数化简，也能增加条件判断式的可读性，避免写出垃圾代码。

一、基本公式

正如加减乘除中存在各式运算律一样，逻辑运算也有运算规律。本章中，我们主要考虑与、或、非运算；异或、同或的运算律可以很方便地推导出来。我们从常量的运算开始。

\begin{matrix} 0+0=0,&0+1=1,&1+1=1\\ 0\times 0=0,&0\times 1=0,&1\times 1=1\\ 0'=1,&1'=0 \end{matrix}

以上相当于把真值表重新表达了一遍，比较直观。

接下来，我们开始把式子抽象化，把其中一个常量用变量 $A$ 代替，看看常量与变量的运算（0 律与 1 律）：

\begin{aligned} \begin{matrix} 0+A=A,&1+A=1\\ 0\cdot A=0,&1\cdot A=A \end{matrix} \end{aligned}

这些也很好理解，只要把常量运算公式两两合并就可以得到。时刻要提示自己：变量的值只有 0 与 1 两种情况。

最后，是变量间的运算，即基本运算律：

提示：在布尔运算中，运算优先级是非 > 与 > 或。

（1）交换律、结合律、分配律

这些公式基本和四则运算中的形式一样：

\begin{aligned} \begin{matrix} A+B=B+A,&A\cdot B=B\cdot A\\ (A+B)+C=A+(B+C),&(AB)\cdot C=A\cdot (BC)\\ A(B+C)=AB+AC,&A+BC=(A+B)(A+C) \end{matrix} \end{aligned}

特别的分配律：由于在布尔运算中，与运算和或运算常常处于可以互换的地位，因此，我们也有 $A+BC=(A+B)(A+C)$ 。它和与对或的分配律非常接近，只是“与”和“或”调换了而已。可以证明一下公式的正确性：

\begin{aligned} (A+B)(A+C)&=A\cdot A+AB+AC+BC\\ &=A+AB+AC+BC\\ &=A(1+B+C)+BC\\ &=A+BC \end{aligned}

分别用了：与逻辑分配律；重叠律（见（3））；与逻辑分配律逆命题；1 律。

（2）还原律

\begin{aligned} A''=A \end{aligned}

很直观，变量两次取反后回到它本身。和语言中的“双重否定”是一个概念。

（3）重叠律

\begin{aligned} A+A=A,\,A\cdot A=A \end{aligned}

这两个式子比较难理解一点。但毕竟，布尔运算与四则运算中的“加法”“乘法”不是完全一致的——如果写成 $A\cup A=A,\,A\cap A=A$ ，或者 A || A == A, A && A == A，表达的意思也是一样的。在学习逻辑运算时，有许多迷惑性的符号——比如“0”与“1”，它们并不存在大小关系，而只是“真”与“假”的对应关系，与数字 0 和 1 无关。

一道十分有趣的题目：能否通过 $A + A = A$ 推导出 $A = 0$ ？
不能。由于布尔运算中没有“减法”运算，因此不可以把等式两端同时减去 $A$ 。这告诉我们，虽然乍一看形式十分接近，但仍然不能被算术运算中的思维误导。

（4）互补律

\begin{aligned} A+A'=1,\,A\cdot A'=0 \end{aligned}

因为 $A$ 与 $A'$ 中有且只有一个为 1，因此可以回到 1 与 0 的运算上来理解。

（5）德·摩根定律

迎接逻辑学中最著名、最经典、最实用的定律：

\begin{aligned} (A+B)'=A'B',\,(AB)'=A'+B' \end{aligned}

它如此优美，如此简洁地表明了与逻辑和或逻辑相互转化的关系。用非常数学的话说：

并集的补集是补集的交集，交集的补集是补集的并集

或者，用实际生活中的例子——

一架飞机能成功降落的前提是前后起落架均已放下，缺一不可。所以，飞机不能降落，是因为“没有既放下前起落架又放下后起落架”，或者说是“没有放下前起落架或者没有放下后起落架”。

此公式的用途之一是去括号。初学时，常常不自觉地写出 $(AB)'=A'B'$ 这样的式子。但实际上，去掉带取反的括号时，或要变与，与要变或。

还有一个用处是转换与逻辑和或逻辑。如果在电路设计中只能使用“或”和“非”两种逻辑，我们也照样能表示出与逻辑—— $AB=(A'+B')'$ 。就比如之前提到过的，Minecraft 游戏中便只有“或”和“非”，但能够创造出所有逻辑元件，原理就在于此。

二、常用公式

以上公式都比较简单，使用时局限性也比较大。所以，我们还推导出了一系列常用公式。它们的使用频率要高得多（基础公式中的德·摩根定律除外）。

注意：在之前的描述中，尽量避免了出现“相加”“乘积”这样的字眼，以防造成误会；但为了叙述方便，接下来会经常出现这些词汇，它们不是一般意义上的“加法”“乘法”，请务必注意。

（1）吸收公式

\begin{aligned} A+AB=A \end{aligned}

两项相加，且其中一项（ $A$ ）是另一项（ $AB$ ）的因式时，另一项中的其他因式就被吸收了。

证明： $A+AB=A(1+B)=A$ 。先提取公因式；再运用 1 律。

这里一系列公式的表达都非常简单抽象，而实际运用时，这两项不一定会长成 $A$ 与 $AB$ 的样子，但哪怕是 $A(X+Y)M'+A(X+Y)(B+C'+D)M'E'F'G$ 这种庞大的式子，只要眼光毒辣，也能发现公因式，并化简成 $A(X+Y)M'$ 。

（2）消因子公式

\begin{aligned} A+A'B=A+B \end{aligned}

两项相加，且其中一项（ $A$ ）取反后是另一项（ $A'B$ ）的因式时，另一项中的这个相反因式就被消去了。（不要在意“吸收”“消去”这两个词到底有什么区别，只是为了区分这两个公式而已）

证明： $A+A'B=(A+A')(A+B)=1\cdot (A+B)=A+B$ 。其中提取公因式一步比较难想到，是证明过程的重点。

要注意区分吸收公式和消因子公式：一个是相同的因式，一个是相反的因式；一个直接消去两项中较大的一项，一个仅仅去除部分因式。

（3）并项公式

\begin{aligned} AB+AB'=A \end{aligned}

两项相加，部分因子相等（ $A$ ），剩下的互补（ $B$ 与 $B'$ ），那么可以合并成一项公有因子。

证明： $AB+AB'=A(B+B')=A\cdot 1=A$ 。

（4）消项公式

\begin{aligned} AB+A'C+BC=AB+A'C \end{aligned}

这个较为复杂：三项相加，两项中部分因子互补（ $AB$ 中的 $A$ 与 $A'C$ 中的 $A'$ ），剩下的都是第三项（ $BC$ ）的因式（这两项的乘积不一定要和第三项相同，只需都是第三项的部分因式），那么第三项可以消去。

证明：

\begin{aligned} AB+A'C+BC&=AB+A'C+(A+A')BC\\ &=AB+A'C+ABC+A'BC\\ &=(AB+ABC)+(A'C+A'BC)\\ &=AB(1+C)+A'C(1+B)\\ &=AB+A'C \end{aligned}

这个公式使用频率不算很高，但它的证明用到了一种很有用的思想——引入冗余项，以进行进一步简化。可以看到，证明开头，逆运用并项公式，创造了一个新的项，随后和另外两项分别合并。除了这种用法，还可以利用重叠律 $A=A+A$ ，重复写入一项，再和其他项化简。这种方法很有用，但需要训练才能掌握。

三、基本规则

何谓基本规则？很难说清楚。但大概地讲，它描述了对等式进行恒等变形的一些方法。

（1）代入规则

将逻辑函数式中任一变量（或函数）用另一变量（或函数）替换，等式仍成立。这类似方程化简中的“换元法”思想。

如果有方程： $F(M(X,Y,Z),B,C,...)=G(M(X,Y,Z),B,C,...)$ ，其中 $F,\,G,\,M$ 均表示函数，则可以设 $A=M(X,Y,Z)$ ，从而得到 $F(A,B,C,\dots)=G(A,B,C,\dots)$ 。

举个例子，之前提到，常用公式不仅仅局限于两到三个变量的运算，还可以拓展到更多变量，这可以用代入规则解释。以消因子公式为例：如果有 $(M+N)'+(M+N)XY$ ，则可以设 $A=(M+N)',\,B=XY$ ，把式子变形成 $A+A'B$ ，然后运用公式。

（2）反演规则

再看看德·摩根定律： $(AB)'=A'+B',\,(A+B)'=A'B'$ ，它可以同样通过应用代入规则，拓展到多个变量： $(ABC\dots)'=A'+B'+C'+\dots,\,(A+B+C+\dots)'=A'B'C'\dots$ 。

注意到，等式的左边是一系列项的积或和，并进行了取反，而等式的右边则是这个反函数的展开。由此，我们可以推导出化简一个函数的反函数——或者叫反演——的规则。这个规则就是反演规则。得到函数的反演式有两步：

加变乘，乘变加——对应德·摩根定律中与和或的转换，并保证运算顺序不变；
对每个量取反（包括变量变为反变量和 0 变 1，1 变 0），但保留非单变量的非号。

比如， $((A+B)C+0)D'\cdot 1$ ，先变换符号： $((AB)+C\cdot0)+D'+1$ ，再对变量逐个取反： $((A'B')+C'\cdot1)+D+0$ ，最后检查运算顺序，并通过添加去除括号调整： $(A'B'+C')\cdot1+D+0$ 。就这样，得到了原函数的反演函数。

（3）对偶规则

这个规则便是之前提到的“与逻辑和或逻辑常常可以互换”的一个严谨定义。对偶式的得到也有两步:

加变乘，乘变加，保证运算顺序不变；
0 变 1，1 变 0。

对偶式的性质是：若两个逻辑式 $F_1=F_2$ 成立，则它们的对偶式 $F_1^D=F_2^D$ 也成立。比如由于 $A(B+C)=AB+AC$ ，通过对偶变换就可以得到 $A+BC=(A+B)(A+C)$ 。这一套东西其实比较无聊，也没什么用，但挺神奇的。

对偶规则也是由德·摩根定律推导而来的，具体证明过程比较 trivial，不再赘述。其实，对偶式和反演式的本质区别就是没有了“对所有量取反”这一步。但为什么要保留“对常数取反”呢？如果没有这一步——比如， $0+A=A$ 的对偶等式是 $1\cdot A=A$ ；如果不对常数取反，就有 $0\cdot A=A$ ，显然不成立。

第三、四章一开始非常难理解，总结一下公式：

0 律： $0+A=A,\,0\cdot A=0$
1 律： $1+A=1,\,1\cdot A=A$
交换律： $A+B=B+A,\,A\cdot B=B\cdot A$
结合律： $A+(B+C)=(A+B)+C,\,A\cdot(B+C)=(AB)\cdot C$
分配律： $A(B+C)=AB+AC,\,A+BC=(A+B)(A+C)$
还原律： $A''=A$
重叠律： $A+A=A,\,A\cdot A=A$
互补律： $A+A'=1,\,A\cdot A'=0$
德·摩根定律： $(A'B')=A'+B',\,(A+B)'=A'B'$
吸收公式： $A+AB=A$
消因子公式： $A+A'B=A+B$
并项公式： $AB+AB'=A$
消项公式： $AB+A'C+BC=AB+A'C$

为了加深理解，可以尝试一下用公式化简这些逻辑函数式。化简要求：写成若干乘积项相加的形式，没有括号，乘积项数量最少，每个乘积项中因子最少。如果思路受阻，可以随时查看上面的公式。

$AB(A+BC)$
$A'BC(B+C')$
$(AB+A'B'+A'B+AB')'$
$(A+B+C')(A+B+C)$
$AC+A'BC+B'C+ABC'$
$ABD+AB'CD'+AC'DE+AD$
$(A'B+AB')C+ABC+A'B'C$
$A'(C'D+CD')+BC'D+ACD'+AB'C'D$
$(A+A'C)(A+CD+D)$ ¹

参考答案：

$AB$
$A'BC$
$0$
$A+B$
$AB+C$
$AD+AB'C$
$C$
$CD'+C'D$
$A+CD$

参考

¹ 题目来源：数字电路与逻辑设计，张俊涛著，清华大学出版社 2017 版

一、基本公式​

二、常用公式​

三、基本规则​

参考​

一、基本公式

二、常用公式

三、基本规则

参考