← 返回课程首页

第 7 章　布尔代数与逻辑化简

1. 本章要解决的问题

第 5 章已经能从晶体管网络判断 NAND、NOR 和复合门的逻辑功能，第 6 章又建立了位、编码和真值表的概念。现在需要解决一个直接影响电路规模的问题：同一个逻辑功能可以写成很多种表达式，怎样判断它们是否等价，又怎样找到更简单的实现？

本章建立一套可以手算、可以检查、也能直接连接门电路的方法。核心任务不是背诵公式，而是在真值表、逻辑表达式和门电路之间稳定转换，并用代数法或卡诺图减少冗余逻辑。

2. 与第 6 章的联系

第 6 章中的二进制数由多个 bit 组成，本章先单独研究一个输出 bit 怎样由若干输入 bit 决定。这里的 0 和 1 是逻辑状态，不再承担数值大小。比如输入位模式 10 可以代表无符号数 2，也可以只表示“\(A=1\)、\(B=0\)”这一组逻辑条件。

第 5 章从晶体管连接得到逻辑函数；本章主要工作在门级和逻辑代数层，暂时忽略晶体管尺寸、寄生电容和路径延迟。章末会重新接回电路层，解释为什么逻辑等价并不保证面积、速度和功耗相同。

3. 前置知识快速检查

先尝试回答下面四个问题。

1. 两输入 NAND 门在哪一种输入组合下输出 0？
2. 3 个二值输入一共有多少种输入组合？
3. 真值表中的一行描述了什么？
4. 静态 CMOS 的串联 NMOS 与逻辑 AND 条件有什么关系？

4. 学习目标

学完本章后，你应当能够：

• 解释布尔变量、NOT、AND、OR 和异或的含义；
• 使用基本恒等式和德摩根定律变换逻辑表达式；
• 根据真值表写出最小项之和或最大项之积；
• 使用代数法化简基础逻辑函数；
• 使用卡诺图化简 2～4 变量逻辑函数；
• 正确处理卡诺图的相邻、环绕和无关项；
• 检查化简前后是否逻辑等价；
• 说明两个逻辑等价电路在物理实现上为何仍可能不同。

5. 布尔变量描述“条件是否成立”

布尔代数（Boolean algebra）只处理两个值：0 和 1。一个布尔变量可以理解成一个判断结果：

• \(A=1\)：条件 \(A\) 成立；
• \(A=0\)：条件 \(A\) 不成立。

例如，一个设备的启动条件可以写成：使能信号 \(E\) 有效，并且故障信号 \(F\) 没有出现。若输出 \(Y=1\) 表示允许启动，那么

\[ Y=E\cdot\overline{F}. \]

横线表示 NOT，圆点表示 AND。这个表达式没有说明电压具体是多少，也没有说明由哪一种逻辑门实现；它只规定输入逻辑状态和输出逻辑状态之间的关系。

5.1 三种基本运算

布尔代数中的“\(+\)”是 OR，不是普通加法。于是 \(1+1=1\)。相邻书写或“\(\cdot\)”表示 AND，因此 \(1\cdot1=1\)。

5.2 常用复合运算

NAND 和 NOR 已在第 5 章出现：

\[ Y_{NAND}=\overline{AB},\qquad Y_{NOR}=\overline{A+B}. \]

异或（exclusive OR, XOR）在两个输入不同时输出 1：

\[ A\oplus B=\overline{A}B+A\overline{B}. \]

同或（exclusive NOR, XNOR）在两个输入相同时输出 1：

\[ \overline{A\oplus B}=AB+\overline{A}\,\overline{B}. \]

异或将在第 9 章的加法器中反复出现。本章先把它看成一个可由 AND、OR、NOT 组成的逻辑函数。

6. 同一个功能有三种常见表示

观察图 7-1 时，沿箭头看同一个功能怎样在三种表示之间转换。

图中功能是 \(Y=\overline{A}B\)：只有 \(A=0\) 且 \(B=1\) 时输出 1。真值表适合完整列举行为，表达式适合推导和化简，门电路适合看实现结构。三种表示保留同一个输入—输出映射，但强调的信息不同。

从真值表写表达式时，可以先盯住输出为 1 的行。每一行都能写成一个“只匹配这一行”的乘积项，再把这些乘积项 OR 起来。第 9 节会把这个方法正式化。

7. 基本恒等式：化简时可以使用的工具

恒等式表示左右两边对全部输入组合都有相同输出。它不是某一组输入下碰巧相等。

7.1 常量律与互补律

\[ \begin{aligned} A+0&=A, & A\cdot1&=A,\\ A+1&=1, & A\cdot0&=0,\\ A+\overline{A}&=1, & A\overline{A}&=0. \end{aligned} \]

前两行说明常量输入怎样影响 OR 和 AND；最后一行说明一个条件和它的反条件不可能同时成立，但至少有一个成立。

7.2 幂等律与双重否定

\[ A+A=A,\qquad A\cdot A=A,\qquad \overline{\overline{A}}=A. \]

重复同一个逻辑条件不会增加信息。两个连续的逻辑取反恢复原值。

7.3 交换律、结合律与分配律

\[ \begin{aligned} 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). \end{aligned} \]

最后一个式子和普通代数的直觉不同，但它是布尔代数的合法分配律。可以用真值表逐行检查，也可以展开右边：

\[ (A+B)(A+C)=A+AC+AB+BC=A+BC. \]

这里使用了 \(A+AX=A\)。这条关系称为吸收律。

7.4 吸收律

\[ A+AB=A,qquad A(A+B)=A. \]

理解第一式可以从条件关系入手：只要 \(AB=1\)，必有 \(A=1\)；因此 \(AB\) 覆盖的情况已经包含在 \(A\) 中，重复加入不会改变结果。

一个常用变形是：

\[ A+\overline{A}B=(A+\overline{A})(A+B)=A+B. \]

8. 德摩根定律：把“整体取反”推入括号

德摩根定律（De Morgan’s laws）是连接表达式和 CMOS 互补网络的核心关系：

\[ \overline{AB}=\overline{A}+\overline{B}, \]

\[ \overline{A+B}=\overline{A}\,\overline{B}. \]

读法很有规律：取反穿过运算符时，AND 与 OR 互换，每个输入也取反。图 7-2 用逻辑门连接展示这种变换。

图的上下两行分别是两条德摩根定律。每一行左右电路的真值表相同。第 5 章构造互补 CMOS 网络时，“NMOS 串并联互换、PMOS 与 NMOS 互换”的逻辑基础正是这里的德摩根关系。

处理长表达式时，先确认横线覆盖的范围。例如

\[ \overline{A(B+C)}=\overline{A}+\overline{B+C} =\overline{A}+\overline{B}\,\overline{C}. \]

第一步把最外层 AND 变成 OR；第二步再处理括号中的 OR。

9. 最小项：只匹配真值表中的一行

对 \(N\) 个变量，一个包含全部 \(N\) 个变量的 AND 项称为最小项（minterm）。每个变量只出现一次，取原变量还是反变量由目标行决定：

• 该行变量为 1，写原变量；
• 该行变量为 0，写反变量。

例如，对变量顺序 \(A,B,C\)，输入 \(101\) 对应

\[ m_5=A\overline{B}C. \]

下标 5 来自二进制 101 的无符号值。这个最小项只在 \(A=1,B=0,C=1\) 时等于 1。

图 7-3 展示三变量输入行、二进制编号和最小项之间的对应关系。

若函数在第 1、3、5、7 行输出 1，就可以写成最小项之和：

\[ F(A,B,C)=\Sigma m(1,3,5,7). \]

把各项展开：

\[ F=\overline{A}\,\overline{B}C+\overline{A}BC+A\overline{B}C+ABC. \]

这个写法称为标准与或式（canonical sum of products, canonical SOP）。它一定能从真值表直接得到，但通常不是最简单的式子。本例的四项都含有 \(C\)，实际可化为 \(F=C\)。

10. 最大项与标准或与式

最大项（maxterm）是包含全部变量的 OR 项，并且只在对应输入行等于 0。写最大项时规则与最小项相反：

• 该行变量为 0，写原变量；
• 该行变量为 1，写反变量。

输入 \(A,B,C=1,0,1\) 对应最大项

\[ M_5=\overline{A}+B+\overline{C}. \]

代入 \(1,0,1\) 后三个文字都为 0，所以这个 OR 项等于 0。其他任一输入行至少会使其中一个文字为 1。

如果函数在第 0、2、6 行输出 0，可以写成

\[ F(A,B,C)=\Pi M(0,2,6). \]

把这些最大项 AND 起来，得到标准或与式（canonical product of sums, canonical POS）。

标准 SOP 关注输出为 1 的行；标准 POS 关注输出为 0 的行。选择哪一种，通常看 1 较少还是 0 较少，以及目标门结构更适合哪一种形式。

11. 对偶性：一条定律可以得到另一条

把布尔表达式中的 AND 与 OR 互换，同时把 0 与 1 互换，就得到原表达式的对偶式（dual expression）。变量和反变量保持不变。

例如：

\[ A+0=A \]

的对偶式是

\[ A\cdot1=A. \]

吸收律 \(A+AB=A\) 的对偶式是 \(A(A+B)=A\)。对偶性可以帮助记忆成对出现的定律，但它不能代替等价检查：对偶式通常是另一条成立的恒等式，不表示原式和它的对偶式彼此相等。

12. 用代数法化简

代数化简的目标是利用恒等式删除重复条件。建议每一步只做一种变化，并在旁边注明依据。

考虑

\[ F=\overline{A}B+AB+AC. \]

前两项都含有 \(B\)：

\[ \begin{aligned} F&=B(\overline{A}+A)+AC &&\text{分配律}\\ &=B\cdot1+AC &&\text{互补律}\\ &=B+AC. &&\text{恒等律} \end{aligned} \]

这次化简把三个乘积项减少为两个。若每个文字输入都需要一个门端口，文字数量减少通常意味着更少的输入电容和连接，但最终面积与延迟还取决于标准单元库和映射方式。

12.1 怎样判断已经足够简单

代数法没有固定的唯一操作顺序，也不总能让人一眼确认已经得到最简式。对 2～4 变量函数，卡诺图更适合系统地寻找可以合并的项；变量更多时通常交给逻辑综合工具处理。

12.2 选学：共识项

下面的共识定理可以删除某些冗余项：

\[ XY+\overline{X}Z+YZ=XY+\overline{X}Z. \]

\(YZ\) 称为共识项。就稳定逻辑值而言它是冗余的；但第 10 章会看到，在具有传播延迟的真实门电路中，保留某个逻辑冗余项有时能消除静态冒险。因此，“布尔意义上可以删除”与“物理电路中一定应该删除”是两个问题。

13. 卡诺图：把只差一个变量的项放在相邻位置

卡诺图（Karnaugh map, K-map）把真值表重新排列，使横向或纵向相邻格只改变一个变量。这样，相邻的两个最小项可以合并并消去那个发生变化的变量。

例如：

\[ \overline{A}BC+ABC=BC(\overline{A}+A)=BC. \]

卡诺图把这两个最小项放在相邻格中，分组动作直接代表上面的代数合并。

13.1 格雷码顺序不能写成普通二进制顺序

两位坐标使用 00, 01, 11, 10，而不是 00, 01, 10, 11。这个顺序保证相邻列只改变一位。最左列和最右列也相邻，因为 00 与 10 只差第一位。

13.2 SOP 化简的分组规则

化简最小项之和时，在值为 1 的格子上分组：

1. 每组格数必须是 \(1,2,4,8,\ldots\)；
2. 每组必须构成矩形；
3. 分组可以跨越左右边界或上下边界；
4. 每个 1 至少被一组覆盖；
5. 分组可以重叠；
6. 优先使用更大的组，再用尽量少的组完成覆盖。

组内保持不变的变量保留下来，发生变化的变量被消去。若某变量在组内恒为 0，写它的反变量；恒为 1，写原变量。

图 7-4 使用四变量函数说明环绕相邻和分组读法。

蓝色虚线组覆盖四个角。在这些格中 \(B=0,D=0\)，而 \(A,C\) 都发生变化，所以得到 \(\overline{B}\,\overline{D}\)。橙色实线组中 \(B=1,D=1\)，得到 \(BD\)。最终结果是

\[ F=\overline{B}\,\overline{D}+BD, \]

也就是 \(B\) 与 \(D\) 的 XNOR，函数与 \(A,C\) 无关。

13.3 POS 化简怎样分组

若要得到 POS，在值为 0 的格子上分组。一个零组产生一个最大项：

• 变量在组内恒为 0，最大项中写原变量；
• 变量在组内恒为 1，最大项中写反变量；
• 发生变化的变量被消去。

这是最小项分组规则的对偶形式。

14. 无关项：可以按需要取 0 或 1 的输入组合

某些输入组合不会出现，或者出现时输出值不影响系统行为。这些组合可以标为无关项（don’t-care condition），常用 X 或 d 表示。

化简 SOP 时，可以把某个无关项当作 1 来扩大分组，也可以不用它。选择标准是让表达式更简单。无关项不是“输入不确定时输出随便变化”，而是规格已经确认该输入组合无需定义功能。

例如 BCD 只使用 0000 到 1001 表示十进制 0～9；若电路规格保证 1010 到 1111 永远不会送入，设计者可以把这六种组合用作化简无关项。若接口有可能产生非法码，就需要另外定义检测或恢复行为，不能直接把它们当作永远不会发生。

15. 逻辑等价不代表物理实现完全等价

两个表达式对所有输入组合给出相同稳定输出，就称为逻辑等价。图 7-5 中的两种结构都实现

\[ F=AB+AC=A(B+C). \]

左侧与或结构包含两个 AND 和一个 OR；右侧先 OR 后 AND，只需要两个门。它们的稳定真值表相同，但下面这些物理属性可能不同：

• 逻辑级数和传播延迟；
• 每个输入看到的电容；
• 内部节点数量与开关活动；
• 标准单元映射结果；
• 输入变化期间是否产生毛刺。

因此，布尔化简首先减少逻辑冗余，不能单独证明某个实现一定最快或功耗最低。实际设计还要结合第 4 章的负载与功耗、第 5 章的晶体管网络，以及第 10 章的路径延迟和冒险。

16. 完整例题

例题 1：从真值表写标准 SOP 并化简

已知三输入函数在 \(A,B,C=001,010,011,101,111\) 时输出 1。写出标准 SOP，并化简。

第一步：写最小项编号。

这些输入对应十进制编号 \(1,2,3,5,7\)：

\[ F=\Sigma m(1,2,3,5,7). \]

第二步：展开标准 SOP。

\[ F=\overline{A}\,\overline{B}C+\overline{A}B\overline{C} +\overline{A}BC+A\overline{B}C+ABC. \]

第三步：在卡诺图中分组。

\(m_1,m_3,m_5,m_7\) 组成四格组，组内只有 \(C=1\) 保持不变，得到 \(C\)。\(m_2,m_3\) 组成两格组，组内 \(A=0,B=1\)，得到 \(\overline{A}B\)。

\[ \boxed{F=C+\overline{A}B} \]

结果检查： 当 \(C=1\) 时，四种 \(A,B\) 组合都输出 1；当 \(C=0\) 时，只剩 \(A=0,B=1\) 输出 1。这正好覆盖给定五行。

变式： 若再把 \(m_0\) 设为 1，试着在图上重新分组。原来的 \(m_2,m_3\) 仍可保留，也可能出现与 \(m_0\) 相关的新组合；比较不同覆盖的项数和文字数。

例题 2：使用德摩根定律得到 NAND 实现

要求只用 NAND 门实现

\[ F=AB+CD. \]

在整体外加两次取反：

\[ F=\overline{\overline{AB+CD}}. \]

对内层 OR 使用德摩根定律：

\[ F=\overline{\overline{AB}\cdot\overline{CD}}. \]

\(\overline{AB}\) 和 \(\overline{CD}\) 分别由两个 NAND 门产生，最外层再用一个 NAND 门。因此共需三个两输入 NAND 门。

结果检查： 若 \(AB=1\)，第一个 NAND 输出 0，末级 NAND 至少有一个输入 0，因此输出 1；这与原函数一致。

变式： 若目标是 \(F=(A+B)(C+D)\)，使用对偶思路可以得到两级 NOR 结构。

例题 3：四变量卡诺图与环绕分组

给定

\[ F(A,B,C,D)=\Sigma m(0,2,5,7,8,10,13,15). \]

使用图 7-4 的行列顺序填入 1。

四个角 \(m_0,m_2,m_8,m_{10}\) 通过上下、左右边界相邻，形成四格组。组内 \(B=0,D=0\)，得到 \(\overline{B}\,\overline{D}\)。

另外四格 \(m_5,m_7,m_{13},m_{15}\) 中 \(B=1,D=1\)，得到 \(BD\)。

\[ \boxed{F=\overline{B}\,\overline{D}+BD} \]

结果只含 \(B,D\)，说明 \(A,C\) 无论怎样变化都不影响输出。逐项查看原最小项编号，可以确认每一种 \(B=D\) 的组合都被包含。

变式： 把输出要求改成 \(B\ne D\)，所得函数就是 \(\overline{B}D+B\overline{D}=B\oplus D\)。

例题 4：利用无关项化简 BCD 检测函数

设计一个 BCD 输入检测信号 \(Y\)。输入为十进制 8 或 9 时 \(Y=1\)；1010～1111 保证不会出现，可作为无关项。设输入为 \(A,B,C,D\)，\(A\) 是 MSB。

有效的 1 是 \(m_8,m_9\)，无关项是 \(d(10,11,12,13,14,15)\)。在卡诺图中，可以把 \(m_8,m_9\) 与六个无关项一起组成覆盖整个 \(A=1\) 半区的八格组。因此

\[ \boxed{Y=A}. \]

这里的结论依赖输入确实是合法 BCD。若普通四位二进制 1111 也可能进入，\(Y=A\) 会把 10～15 同样判为 1；此时应先检查合法性，再解释数值范围。

17. 常见误区与反例

误区 1：把布尔 OR 当作普通加法

布尔代数中 \(1+1=1\)，因为 OR 只问“是否至少有一个条件成立”。二进制算术中的 \(1+1=10_2\) 属于第 9 章的加法规则。

误区 2：写最小项时把 0 对应成原变量

最小项要在目标行输出 1。目标行中 \(A=0\) 时必须写 \(\overline{A}\)，代入后这个文字才为 1。

误区 3：卡诺图列顺序使用 00,01,10,11

中间的 01 与 10 同时改变两位，不能作为相邻格合并。正确的两位格雷码顺序是 00,01,11,10。

误区 4：认为图的两个边界不相邻

卡诺图的左右边、上下边首尾相接。四个角也可以组成一个四格组。

误区 5：只允许每个 1 进入一个组

分组可以重叠。重复覆盖某个 1 有时能让其他未覆盖项加入更大的组，从而减少文字数量。

误区 6：为了组数少而使用更小的组

先争取更大的 \(2^k\) 格矩形。一个四格组消去两个变量，通常优于两个两格组。

误区 7：把无关项理解成未知值

无关项来自规格：对应输入不发生，或输出不影响后续功能。它可以帮助化简，但必须有接口条件支持。

误区 8：表达式更短就一定更快

表达式文字数只是逻辑复杂度指标之一。门级映射、扇入、负载、逻辑深度和布线都会改变延迟与功耗。

18. 工程中的实际意义

布尔化简直接影响组合逻辑的实现候选方案。更少的逻辑项和文字常常带来更少的门输入、内部节点和布线，但工程流程不会停在手算最简式：

1. 规格或 RTL 给出逻辑行为；
2. 综合工具在工艺库允许的门型中进行逻辑优化与技术映射；
3. 时序、面积和功耗约束决定最终选择；
4. 等价检查确认优化前后逻辑行为一致；
5. 物理实现继续处理真实互连和负载。

手工化简仍然重要，因为它让你能识别冗余条件、检查小模块、理解综合报告，并在电路结果异常时看出问题来自规格、逻辑还是物理实现。

19. 本章知识链

输入条件
   ↓ 枚举全部组合
真值表
   ↓ 取输出为 1 的行             ↓ 取输出为 0 的行
最小项之和（SOP）                最大项之积（POS）
   ↓ 代数恒等式 / 卡诺图          ↓ 代数恒等式 / 零格分组
化简表达式
   ↓ 选择 NAND/NOR/复合门等结构
门级实现
   ↓ 加入延迟、负载、活动率和布线
物理性能

这条链中，真值表、标准式和化简式在稳定逻辑值上等价；进入门级和电路层后，延迟、功耗和毛刺等差异重新出现。

20. 本章小结

1. 布尔变量表示二值逻辑条件，NOT、AND、OR 是三种基本运算。
2. 真值表、逻辑表达式和门电路可以描述同一个组合逻辑功能。
3. 布尔恒等式必须对全部输入组合成立；吸收律和德摩根定律是常用化简工具。
4. 最小项只在一行取 1，最大项只在一行取 0。
5. 标准 SOP 可由输出为 1 的行直接得到，标准 POS 可由输出为 0 的行直接得到。
6. 卡诺图利用格雷码相邻关系，把只差一个变量的项合并。
7. 卡诺图分组大小必须是 2 的整数次幂，可以环绕、重叠并使用无关项。
8. 布尔等价保证稳定输入—输出关系相同，不保证门数、延迟、功耗和毛刺相同。

21. 练习

先独立完成，再展开答案。题目 1～6 检查基本概念，7～12 训练计算与化简，13～15 连接设计和物理实现。

21.1 基础题

1. 分别写出 NOT、AND、OR 在什么条件下输出 1。
2. 用真值表验证 \(A+\overline{A}B=A+B\)。
3. 写出 \(\overline{A+B+C}\) 的德摩根展开式。
4. 对变量顺序 \(A,B,C\)，写出输入 010 对应的最小项和最大项。
5. 函数 \(F=\Sigma m(0,2,6,7)\) 在哪些输入行输出 1？
6. 写出恒等式 \(A+0=A\) 的对偶式。

21.2 计算与分析题

7. 化简 \(F=AB+A\overline{B}+\overline{A}BC\)。
8. 化简 \(F=(A+B)(A+\overline{B})\)。
9. 把 \(F=A+BC\) 变换为 POS。
10. 只用两输入 NAND 门实现 \(F=AB+C\)，写出变换后的表达式并说明需要几个 NAND 门。允许用 NAND 的两个输入并接实现反相。
11. 用卡诺图化简 \(F(A,B,C)=\Sigma m(1,2,3,5,7)\)。
12. 用卡诺图化简 \(F(A,B,C,D)=\Sigma m(0,1,2,3,8,9,10,11)\)，并指出输出与哪些变量无关。

21.3 综合题

13. 一个安全输出 \(Y\) 只有在“授权 \(A=1\)”且“门已关闭 \(D=1\)”时允许为 1；维护模式 \(M=1\) 时，无论授权状态如何，只要门已关闭也允许输出。先写表达式 \(Y=AD+MD\)，再化简并画出所需门级结构。
14. BCD 输入 \(A,B,C,D\) 中，设计一个信号 \(Y\)，当十进制数为偶数时输出 1。把非法 BCD 码 10～15 作为无关项，使用卡诺图化简。
15. 两个电路分别实现 \(F_1=AB+AC\) 和 \(F_2=A(B+C)\)。
    1. 说明怎样证明它们逻辑等价；
    2. 比较门数和逻辑深度；
    3. 说明为什么仅凭表达式不能断言哪一个实际延迟更小。

22. 练习答案

23. 自测清单

不看正文，逐项判断自己能否做到：

• 我能解释布尔 \(+\) 为什么不是普通加法。
• 我能用真值表检查两个表达式是否等价。
• 我能正确展开两条德摩根定律。
• 我能根据输入行写最小项和最大项。
• 我能从输出为 1 的行写标准 SOP。
• 我能使用吸收律和分配律完成基础代数化简。
• 我能按格雷码顺序填写 3 变量或 4 变量卡诺图。
• 我知道卡诺图边界相邻，并能解释一个分组消去了哪些变量。
• 我能说明无关项的来源和使用条件。
• 我能区分逻辑等价与物理实现等价。

若第 4～8 项仍不稳定，建议重新手画例题 1 和例题 3 的卡诺图，并逐组写出“保持不变的变量”。

24. 下一章衔接

本章已经能把一个小型逻辑规格化成较简单的表达式。第 8 章将把这些函数封装成可重复使用的组合逻辑模块，包括译码器、编码器、优先编码器、多路选择器、解复用器和比较器。届时关注点会从“单个表达式怎样化简”转向“怎样用模块连接完成更大的功能”。

课程首页 · 数字集成电路基础