数字电路与逻辑设计张俊涛_数字电路学习笔记（四）：逻辑代数系统

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

一、基本公式

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

常量的运算

开始。

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

接下来，我们开始把式子抽象化，把其中一个常量用变量

代替，看看

常量与变量的运算（0律与1律）

：

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

最后，是变量间的运算，即

基本运算律：

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

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

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

特别的分配律：

由于在布尔运算中，与运算和或运算常常处于可以互换的地位，因此，我们也有

。它和与对或的分配律非常接近，只是“与”和“或”调换了而已。可以证明一下公式的正确性：

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

（2）还原律

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

（3）重叠律

这两个式子比较难理解一点。但毕竟，布尔运算与四则运算中的“加法”“乘法”不是完全一致的——如果写成

，或者

A || A == A, A && A == A

，表达的意思也是一样的。在学习逻辑运算时，有许多迷惑性的符号——比如”0”与“1”，它们并不存在大小关系，而只是“真”与“假”的对应关系，与数字0和1无关。

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

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

（4）互补律

因为

与

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

（5）德·摩根定律

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

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

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

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

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

此公式的用途之一是去括号。初学时，常常不自觉地写出

这样的式子。但实际上，去掉带取反的括号时，或要变与，与要变或。

还有一个用处是转换与逻辑和或逻辑。如果在电路设计中只能使用“或”和“非”两种逻辑，我们也照样能表示出与逻辑——

。就比如之前提到过的，Minecraft游戏中便只有“或”和“非”，但能够创造出所有逻辑元件，原理就在于此。

二、常用公式

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

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

（1）吸收公式

两项相加，且其中一项（

）是另一项（

）的因式时，另一项中的

其他因式

就被吸收了。

证明：

。先提取公因式；再运用1律。

这里一系列公式的表达都非常简单抽象，而实际运用时，这两项不一定会长成A与AB的样子，但哪怕是

这种庞大的式子，只要眼光毒辣，也能发现公因式，并化简成

。

（2）消因子公式

两项相加，且其中一项（

）

取反后

是另一项（

）的因式时，另一项中的

这个相反因式

就被消去了。（不要在意“吸收”“消去”这两个词到底有什么区别，只是为了区分这两个公式而已）

证明：

。其中提取公因式一步比较难想到，是证明过程的重点。

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

（3）并项公式

两项相加，部分因子相等（

），剩下的互补（

与

），那么可以合并成一项公有因子。

证明：

。

（4）消项公式

这个较为复杂：三项相加，两项中部分因子互补（

中的

与

中的

），剩下的都是第三项（

）的因式（这两项的乘积不一定要和第三项相同，只需都是第三项的部分因式），那么第三项可以消去。

证明：

这个公式使用频率不算很高，但它的证明用到了一种很有用的思想——引入冗余项，以进行进一步简化。可以看到，证明开头，逆运用并项公式，创造了一个新的项，随后和另外两项分别合并。除了这种用法，还可以利用重叠律

，重复写入一项，再和其他项化简。这种方法很有用，但需要训练才能掌握。

三、基本规则

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

（1）代入规则

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

如果有方程：

，其中

均表示函数，则可以设

，从而得到

。

举个例子，之前提到，常用公式不仅仅局限于两到三个变量的运算，还可以拓展到更多变量，这可以用代入规则解释。以消因子公式为例：如果有

，则可以设

，把式子变形成

，然后运用公式。

（2）反演规则

再看看德·摩根定律：

，它可以同样通过应用代入规则，拓展到多个变量：

。

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

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

比如，

，先变换符号：

，再对变量逐个取反：

，最后检查运算顺序，并通过添加去除括号调整：

。就这样，得到了原函数的反演函数。

（3）对偶规则

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

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

对偶式的性质是：若两个逻辑式

成立，则它们的对偶式

也成立。比如由于

，通过对偶变换就可以得到

。这一套东西其实比较无聊，也没什么用，但挺神奇的。

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

的对偶等式是

；如果不对常数取反，就有

，显然不成立。

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

• 0律：

  

• 1律：

  

• 交换律：

  

• 结合律：

  

• 分配律：

  

• 还原律：

  

• 重叠律：

  

• 互补律：

  

• 德·摩根定律：

  

• 吸收公式：

  

• 消因子公式：

  

• 并项公式：

  

• 消项公式：

  

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

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

   [1]

参考答案：

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

（感谢 @Maxwell的确良 捉虫）

参考

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