跳到主要内容

数字电路学习笔记(四):逻辑代数系统

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

一、基本公式

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

0+0=0,0+1=1,1+1=10×0=0,0×1=0,1×1=10=1,1=0\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}

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

接下来,我们开始把式子抽象化,把其中一个常量用变量AA代替,看看常量与变量的运算(0 律与 1 律)

0+A=A,1+A=10A=0,1A=A\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)交换律、结合律、分配律

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

A+B=B+A,AB=BA(A+B)+C=A+(B+C),(AB)C=A(BC)A(B+C)=AB+AC,A+BC=(A+B)(A+C)\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)A+BC=(A+B)(A+C)。它和与对或的分配律非常接近,只是“与”和“或”调换了而已。可以证明一下公式的正确性:

(A+B)(A+C)=AA+AB+AC+BC=A+AB+AC+BC=A(1+B+C)+BC=A+BC\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)还原律

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

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

(3)重叠律

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

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

一道十分有趣的题目:能否通过A+A=AA + A = A推导出A=0A = 0

不能。由于布尔运算中没有“减法”运算,因此不可以把等式两端同时减去AA。这告诉我们,虽然乍一看形式十分接近,但仍然不能被算术运算中的思维误导。

(4)互补律

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

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

(5)德·摩根定律

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

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

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

并集的补集是补集的交集,交集的补集是补集的并集

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

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

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

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

二、常用公式

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

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

(1)吸收公式

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

两项相加,且其中一项(AA)是另一项(ABAB)的因式时,另一项中的其他因式就被吸收了。

证明:A+AB=A(1+B)=AA+AB=A(1+B)=A。先提取公因式;再运用 1 律。

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

(2)消因子公式

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

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

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

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

(3)并项公式

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

两项相加,部分因子相等(AA),剩下的互补(BBBB'),那么可以合并成一项公有因子。

证明:AB+AB=A(B+B)=A1=AAB+AB'=A(B+B')=A\cdot 1=A

(4)消项公式

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

这个较为复杂:三项相加,两项中部分因子互补(ABAB中的AAACA'C中的AA'),剩下的都是第三项(BCBC)的因式(这两项的乘积不一定要和第三项相同,只需都是第三项的部分因式),那么第三项可以消去。

证明:

AB+AC+BC=AB+AC+(A+A)BC=AB+AC+ABC+ABC=(AB+ABC)+(AC+ABC)=AB(1+C)+AC(1+B)=AB+AC\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+AA=A+A,重复写入一项,再和其他项化简。这种方法很有用,但需要训练才能掌握。

三、基本规则

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

(1)代入规则

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

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

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

(2)反演规则

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

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

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

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

(3)对偶规则

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

  • 加变乘,乘变加,保证运算顺序不变;
  • 0 变 1,1 变 0。

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

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


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

  • 0 律:0+A=A,0A=00+A=A,\,0\cdot A=0
  • 1 律:1+A=1,1A=A1+A=1,\,1\cdot A=A
  • 交换律:A+B=B+A,AB=BAA+B=B+A,\,A\cdot B=B\cdot A
  • 结合律:A+(B+C)=(A+B)+C,A(B+C)=(AB)CA+(B+C)=(A+B)+C,\,A\cdot(B+C)=(AB)\cdot C
  • 分配律:A(B+C)=AB+AC,A+BC=(A+B)(A+C)A(B+C)=AB+AC,\,A+BC=(A+B)(A+C)
  • 还原律:A=AA''=A
  • 重叠律:A+A=A,AA=AA+A=A,\,A\cdot A=A
  • 互补律:A+A=1,AA=0A+A'=1,\,A\cdot A'=0
  • 德·摩根定律:(AB)=A+B,(A+B)=AB(A'B')=A'+B',\,(A+B)'=A'B'
  • 吸收公式:A+AB=AA+AB=A
  • 消因子公式:A+AB=A+BA+A'B=A+B
  • 并项公式:AB+AB=AAB+AB'=A
  • 消项公式:AB+AC+BC=AB+ACAB+A'C+BC=AB+A'C

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

  1. AB(A+BC)AB(A+BC)
  2. ABC(B+C)A'BC(B+C')
  3. (AB+AB+AB+AB)(AB+A'B'+A'B+AB')'
  4. (A+B+C)(A+B+C)(A+B+C')(A+B+C)
  5. AC+ABC+BC+ABCAC+A'BC+B'C+ABC'
  6. ABD+ABCD+ACDE+ADABD+AB'CD'+AC'DE+AD
  7. (AB+AB)C+ABC+ABC(A'B+AB')C+ABC+A'B'C
  8. A(CD+CD)+BCD+ACD+ABCDA'(C'D+CD')+BC'D+ACD'+AB'C'D
  9. (A+AC)(A+CD+D)(A+A'C)(A+CD+D)1

参考答案:

  1. ABAB
  2. ABCA'BC
  3. 00
  4. A+BA+B
  5. AB+CAB+C
  6. AD+ABCAD+AB'C
  7. CC
  8. CD+CDCD'+C'D
  9. A+CDA+CD

参考

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