从真值表到逻辑表达式
复习
- 文字与编码：文字靠字符编码表示，ASCII、Unicode 和 UTF-8 解决了编号与存储等系列问题
- 小数与浮点数：二进制小数可用定点或浮点表示，浮点数范围大但精度有限
- 简单逻辑门：与、或、非是处理二进制信号的基本逻辑门
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 = AB̅ + C̅D 同理：
AB̅要整体为 1，必须 A = 1 且 B = 0C̅D要整体为 1，必须 C = 0 且 D = 1
从真值表写表达式
方法是固定的三步：
- 找出所有 输出为 1 的输入组合
- 每个组合写成一个“与”项，然后把它们全部用“或”连接起来
- 对每个“与”项，若某个输入在该组合里是 0，就给这个输入加非号
来看一个例子：搭建两个输入“不同则真”的数字电路图。
先列出真值表：
| 输入 A | 输入 B | 输出 Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- 输出为 1 的行：
(A=0, B=1)和(A=1, B=0) - 写成与项再或起来：
Y = AB + AB - 有输入为 0 的就加非号：
Y = A̅B + AB̅（第一项 B=1、A=0 →A取反；第二项 A=1、B=0 →B取反）
注意，图跟文本两种描述，在加非号时，顺序不太一样，这个不关键，可以先写出与项，再加非号或起来，也可以先写出与项再或起来之后加非号，性质一样。只要别忘了加非号就行。
看不懂 Y = A̅B + AB̅ 这种式子也没关系，它只是一种简单的符号描述，跟真值表等效。有了表达式，接电路就是下一步的事了。
从表达式拼接逻辑门
拿到表达式后，同样是机械的三步：
- 如果会化简（见下一节），先化简
- 每个“与”项，用一个 与门 把它的输入接起来；某个输入带非号，就先过一遍 非门
- 把所有与门的输出，接进一个 或门
以上面的 Y = A̅B + AB̅ 为例：两个与门分别算 A̅B 和 AB̅，它们的输出再进一个或门，Y 就出来了。
表达式化简
上面写出的表达式叫“与或式”，它一定能用，但往往不是最简的。表达式能化简，就能少用门，电路也就更快、更省、更可靠。
化简靠的是一条朴素的规律：一个信号和它的反相“或”起来，永远是 1。也即 B + B̅ 恒为 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 个或门、3 个非门。
但布尔代数中有一个幂等律：A + A = A。也就是说，上面的表达式可以写成：
Y = A̅BC + AB̅C + ABC̅ + ABC + ABC + ABC
我们可以把其中两项配对，各提出公因式：
A̅BC + ABC = (A̅ + A)BC = 1·BC = BC
AB̅C + ABC = AC
ABC̅ + ABC = AB
于是：
Y
= A̅BC + AB̅C + ABC̅ + ABC
= A̅BC + AB̅C + ABC̅ + ABC + ABC + ABC
= (ABC̅ + ABC) + (AB̅C + ABC) + (A̅BC + ABC)
= (C + C̅)AB + (B + B̅)AC + (A + A̅)BC
= 1·AB + 1·AC + 1·BC
= AB + AC + BC
只需 3 个与门、1 个或门，输入也少了很多。这就是化简的价值。（更系统的化简方法属于数字电路、离散数学和布尔代数，本指南不深入。）
思考题
试着为“三个输入全为 1 时才输出 1”写表达式。然后想一想：它还能再化简吗？
小结
知识点
- 布尔表达式的记法：与是乘、或是加、非是加横
- 从真值表写“与或式”的三步法
- 从表达式拼接逻辑门
- 用数字电路、离散数学和布尔代数进行化简
- 多数表决器的例子
参考资料
- Wikipedia(zh)：布尔代数：布尔逻辑的基本运算
- Wikipedia(zh)：逻辑代数：表达式的化简
- 《编码：隐匿在计算机软硬件背后的语言》第 10~11 章
思考题答案（仅供参考）
真值表里只有 (1,1,1) 输出为 1，写成表达式就是：
Y = ABC
它已经是最简形式，无法再化简——三项都是 1 才成立，一个条件都不能少。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪