第二讲 · 逻辑函数与组合逻辑

对应材料：2025 计组复习提纲“逻辑函数”“组合逻辑”。

组合逻辑电路没有“记忆”：某一时刻的输出只取决于这一时刻的输入。设计它，本质上是在四种表示之间来回转换：

自然语言需求 → 真值表 → 逻辑表达式 → 门电路

这条链也是本讲最重要的解题方法。

1. 基本逻辑运算

$A$	$B$	与 $AB$	或 $A+B$	异或 $A\oplus B$	同或 $A\odot B$
0	0	0	0	0	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	1	0	1

非运算记作 $\overline A$ 。异或可以理解为“两个输入不同”，同或则是“两个输入相同”。

常用定律：

\begin{aligned} A+A&=A, & AA&=A,\\ A+AB&=A, & A(A+B)&=A,\\ \overline{\overline A}&=A,\\ \overline{A+B}&=\overline A\,\overline B, & \overline{AB}&=\overline A+\overline B. \end{aligned}

最后两条是摩根定律。它告诉我们：对整个表达式取反时，“与、或互换，每个变量也取反”。这也是只用 NAND 或只用 NOR 实现任意逻辑函数的基础。

2. 最小项、最大项与标准表达式

2.1 最小项

一个最小项包含所有输入变量，每个变量恰好出现一次。对三变量 $A,B,C$ ，输入 101 对应

m_5=A\overline B C.

一个函数在哪些输入组合上为 1，就把相应最小项相加：

F(A,B,C)=\sum m(3,5,6,7).

2.2 最大项

最大项也是每个变量恰好出现一次，但采用“或”连接，并且在对应输入组合上取 0。函数在哪些行取 0，就把相应最大项相乘：

F(A,B,C)=\prod M(0,1,2,4).

最小项标准式和最大项标准式都不一定最简，却能从真值表机械地得到，适合当作设计的可靠起点。

3. 卡诺图：把相邻输入合并

卡诺图按格雷码排列，相邻格只有一个变量不同。把值为 1 的格子按 $1,2,4,8,\ldots$ 个一组圈起来，每圈消去变化的变量。

必须遵守：

圈尽量大、数量尽量少；
可跨越左右边界、上下边界；
可重叠，但每个 1 至少被覆盖一次；
无关项 X 可按需要当 0 或 1，目的是让圈更大；
不能把对角线当作相邻。

3.1 三人表决器

三人中至少两人同意，输出才为 1：

F(A,B,C)=\sum m(3,5,6,7).

卡诺图化简后：

F=AB+AC+BC.

这不是“凭感觉写公式”，而是完整走过需求抽象、真值表、标准式和化简四步。

4. 组合逻辑的分析与设计

4.1 分析已有电路

从每个门的输出开始写中间变量；
沿信号方向逐层代入，得到最终表达式；
必要时列真值表；
用人话说明电路功能。

4.2 从需求设计电路

确定输入、输出变量以及高低电平的含义；
列出所有输入组合的真值表；
写最小项或最大项标准式；
用代数法或卡诺图化简；
选择门电路或现成组件实现；
检查非法输入、有效电平与时延。

“有效低电平”尤其容易出错。器件引脚上的小圆圈或名称上的横线，表示信号为 0 时才有效，不能按普通正逻辑直接套公式。

5. 加法器：从一位算到多位

5.1 半加器

半加器只计算 $A+B$ ，不接收低位进位：

S=A\oplus B,\qquad C=AB.

5.2 全加器

全加器还接收低位进位 $C_i$ ：

\begin{aligned} S_i&=A_i\oplus B_i\oplus C_i,\\ C_{i+1}&=A_iB_i+(A_i\oplus B_i)C_i. \end{aligned}

把多个全加器首尾相接，就得到行波进位加法器。它结构简单，但高位必须等低位进位一路“爬”上来，位数越多，关键路径越长。

5.3 先行进位

定义生成与传播：

G_i=A_iB_i,\qquad P_i=A_i\oplus B_i.

则

C_{i+1}=G_i+P_iC_i.

展开可得：

C_2=G_1+P_1G_0+P_1P_0C_0.

这样可以用组合逻辑并行算出多级进位，用更多硬件换更短延迟。

6. 减法、比较与溢出

补码减法转为加法：

A-B=A+\overline B+1.

硬件可以在 $B$ 输入前放异或门，并把最低位进位设为 1：控制信号为 0 时做加法，为 1 时同时取反 $B$ 、加 1，完成减法。

判断 $A=B$ 可先计算 $A-B$ ，再检测结果是否全 0。判断有符号 $A<B$ 时，不能只看差的符号位；若减法溢出，需要用

\mathrm{less}=\mathrm{sign}(A-B)\oplus\mathrm{overflow}

修正。

7. ALU：把多个运算共用一条数据通路

课件从 1 位 ALU 扩展到 32 位 ALU。每一位都能算与、或、加减；控制信号通过多路选择器选出最终结果。最高位额外产生溢出和 set，最低位接收 less，从而支持 slt。

典型控制可理解为：

控制	运算
`AND`	按位与
`OR`	按位或
`ADD`	加法
`SUB`	减法、相等判断
`SLT`	小于则低位置 1

ALU 的关键思想是复用：减法复用加法器，相等判断复用减法，比较又复用减法的结果。后面的 CPU 数据通路会继续沿用这个思路。

8. 编码器、译码器与多路选择器

8.1 编码器

$2^n$ 线到 $n$ 线编码器把“哪一路有效”编码为 $n$ 位编号。普通编码器要求任一时刻最多一路有效；若多路可能同时有效，需要优先编码器明确优先级。

8.2 译码器

$n$ 线到 $2^n$ 线译码器做相反的事：输入一个 $n$ 位编号，只激活对应的一路输出。译码器可以：

产生最小项；
选择寄存器或存储芯片；
实现任意 $n$ 变量逻辑函数。

例如 3-8 译码器的 8 个输出恰好对应三变量的 8 个最小项。

8.3 多路选择器

$2^n$ 选 1 MUX 用 $n$ 位选择信号，从多路输入中选一路输出。以 2 选 1 为例：

Y=\overline S D_0+SD_1.

MUX 不只是“开关”，也是数据通路里落实控制策略的基本组件：同一个 ALU 输入端可能来自寄存器或立即数，同一个寄存器写回值可能来自 ALU、主存或 PC，都是由 MUX 选择。

9. 竞争与冒险

逻辑等价不代表动态过程完全一样。由于不同路径延迟不同，输入变化时，理论上应保持 1 的输出可能短暂掉到 0，这就是静态冒险。

若函数中同时出现

AB+\overline A C,

当 $B=C=1$ 、 $A$ 翻转时，两条路径可能短暂都为 0。加入一致项 $BC$ ：

F=AB+\overline A C+BC

可消除这类冒险。课件还给出三种工程方法：增加冗余项、引入采样脉冲、在输出端并联电容。第一种从逻辑上消除，后两种从时间或滤波角度避开毛刺。

10. Verilog 在本讲里的位置

课件给全加器、编码器、译码器和 MUX 配了 Verilog 描述。要抓住的不是语法细节，而是两种层次：

结构/数据流描述：把已经推导出的逻辑表达式写出来；
行为描述：用 case、if 直接描述真值表或功能。

无论采用哪种写法，组合逻辑都必须覆盖所有输入情况，否则综合工具可能推断出锁存器，电路就不再是纯组合逻辑。

11. 本讲检查表

遇到组合逻辑题，先检查：

输入输出的高低电平含义是否明确；
真值表有没有漏行；
最小项编号是否按正确变量顺序；
卡诺图是否按格雷码、是否允许跨边界；
进位、溢出和比较是否混淆；
器件是否低有效；
静态真值正确后，动态路径是否还可能冒险。