从真值表到逻辑表达式

复习

1. 第七章：认识了与、或、非三个基本逻辑门，它们是搭建一切电路的积木

TL;DR

• 复杂的逻辑功能，本质上都是基本逻辑门组合出来的
• 任何一张真值表，都能机械地写成一个“与或式“：找出输出为 1 的行，写成一个个“与“项，再全部“或“起来
• 写出来的表达式往往可以化简，门用得更少，电路更快更省

正文

引言

　　有了与、或、非三个基本门，理论上就能搭出任何逻辑功能。但问题是：给你一个需求，你怎么知道该用哪些门、怎么接？

　　比如“设计一个电路，两个输入不同时输出 1，相同时输出 0“。光靠直觉硬试，容易越试越乱。

　　幸运的是，存在一套通用的、机械的方法：先把需求列成真值表，再从真值表写出表达式，最后按表达式拼接逻辑门。这一章就把这套方法讲清楚。

布尔表达式的记法

　　这套方法用到的表达式，和初高中多项式长得很像，只是一套符号换了意思：

• 与写成乘法（可以省略乘号）：AB 表示“ A 与 B “
• 或写成加法：A + B 表示“ A 或 B “
• 非在字母上加一横（本文用 A 表示 A 取反，也可以写成 ~A）

　　例如 Y = AB + CD（Y 是输出，A、B、C、D 是输入）读作：

• 只要 AB 为 1，或者 CD 为 1，Y 就为 1
• 而 AB 要整体为 1，必须 A = 1 且 B = 1

　　带非号的 Y = A<span style="text-decoration: overline">B</span> + <span style="text-decoration: overline">C</span>D 同理：

• A<span style="text-decoration: overline">B</span> 要整体为 1，必须 A = 1 且 B = 0
• <span style="text-decoration: overline">C</span>D 要整体为 1，必须 C = 0 且 D = 1

从真值表写表达式

　　方法是固定的三步：

1. 找出所有输出为 1 的输入组合
2. 每个组合写成一个“与“项，然后把它们全部用“或“连接起来
3. 对每个“与“项，若某个输入在该组合里是 0，就给这个输入加非号

　　来看一个例子。

例子：两个输入“不同则真“

　　先列出真值表：

1. 输出为 1 的行：(A=0, B=1) 和 (A=1, B=0)
2. 写成与项再或起来：Y = AB + AB
3. 有输入为 0 的就加非号：第一项 B=1、A=0 → A 取反；第二项 A=1、B=0 → B 取反

　　于是得到：

Y = A̅B + AB̅

　　看不懂这个式子也没关系，它只是忠实地描述了那张真值表。有了表达式，接电路就是下一步的事了。

从表达式拼接逻辑门

　　拿到表达式后，同样是机械的三步：

1. 如果会化简（见下一节），先化简
2. 每个“与“项，用一个与门把它的输入接起来；某个输入带非号，就先过一遍非门
3. 把所有与门的输出，接进一个或门

　　以上面的 Y = A̅B + AB̅ 为例：两个与门分别算 A̅B 和 AB̅，它们的输出再进一个或门，Y 就出来了。

化简：让它更省

　　上面写出的表达式叫“与或式“，它一定能用，但往往不是最简的。表达式能化简，就能少用门，电路也就更快、更省、更可靠。

　　化简靠的是一条朴素的规律：一个信号和它的反相“或“起来，永远是 1。

B + B̅ = 1

　　因为 B 要么是 0、要么是 1，不管哪种，B + B̅ 里总有一个是 1。

　　来看一个更有代表性的例子——多数表决器：三个输入 A、B、C，只要有两个及以上为 1，输出就为 1。它的真值表里输出为 1 的行是 011、101、110、111，照方法写出：

Y = A̅BC + AB̅C + ABC̅ + ABC

　　直接拼电路要用 4 个与门、1 个或门。但我们可以把其中两项配对，各提出公因式：

A̅BC + ABC = (A̅ + A)BC = 1·BC = BC
AB̅C + ABC = AC
ABC̅ + ABC = AB

　　于是：

Y = AB + AC + BC

　　只需 3 个与门、1 个或门，输入也少了很多。这就是化简的价值。（更系统的化简方法属于数字电路和离散数学，本指南不深入。）

思考题

　　试着为“三个输入全为 1 时才输出 1“写表达式，并想一想：它还能再化简吗？

小结

知识点

• 布尔表达式的记法：与是乘、或是加、非是加横
• 从真值表写“与或式“的三步法
• 从表达式拼接逻辑门
• 用“提取公因式 + B + B̅ = 1“进行化简
• 多数表决器的例子

参考资料

1. Wikipedia(zh)：布尔代数：布尔逻辑的基本运算
2. Wikipedia(zh)：逻辑代数：表达式的化简
3. 《编码：隐匿在计算机软硬件背后的语言》第 10~11 章

思考题答案（仅供参考）

　　真值表里只有 (1,1,1) 输出为 1，写成表达式就是：

Y = ABC

　　它已经是最简形式，无法再化简——三项都是 1 才成立，一个条件都不能少。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪