布尔代数与组合逻辑

数字逻辑的原料只有两个值：0 与 1。本章从布尔代数的公理出发，经真值表与门电路，搭出半加器、全加器、多位加法器与 ALU——这是从比特到"会算术的机器"的第一步（→ 信息的表示）。

布尔代数

布尔代数定义在 $\{0,1\}$ 上，基本运算为与（ $\land$ ）、或（ $\lor$ ）、非（ $\lnot$ ）。常用的恒等式：

\begin{aligned} &\text{分配律：} && A \land (B \lor C) = (A \land B) \lor (A \land C) \\ &\text{德摩根：} && \lnot(A \land B) = \lnot A \lor \lnot B, \qquad \lnot(A \lor B) = \lnot A \land \lnot B \\ &\text{吸收律：} && A \lor (A \land B) = A \end{aligned}

德摩根定律在工程上的意义：任何布尔函数都能只用 NAND 实现（NAND 是函数完备的），芯片制造因此只需要一种晶体管配置——这是器件层最重要的简化。

从真值表到门电路

任何 $n$ 输入函数都由 $2^n$ 行的真值表完全定义。从真值表到电路的标准路径：

最小项之和：对每个输出为 1 的行写一个乘积项（输入为 1 取原变量，为 0 取反变量），全部求和。
化简：用卡诺图（Karnaugh map）按格雷码排列真值表，使可合并的相邻项可见，消去变化的变量。
映射为门：与或式直接映射为 AND-OR 两级门电路。

卡诺图适合 4–6 个变量；更大规模交给逻辑综合工具（EDA），其本质是同一件事的自动化。

加法器：从半加到 ALU

半加器把两个一位相加：和 $S = A \oplus B$ ，进位 $C = A \land B$ ——两个门。

全加器加入进位输入， $S = A \oplus B \oplus C_{in}$ ， $C_{out}$ 为三者中至少两个为 1。

多位加法器把全加器串联，最低位的进位输入接 0。问题在于进位链：第 $n$ 位必须等第 $n-1$ 位的进位，延迟随位数线性增长，且进位链是加法器延迟的决定因素。**超前进位加法器（carry-lookahead）**先并行算出"生成"（ $G_i = A_i \land B_i$ ，本位必然产生进位）与"传播"（ $P_i = A_i \oplus B_i$ ，把进位传上去）信号，以面积换速度，把延迟从 $O(n)$ 降到 $O(\log n)$ 。

ALU 就是一组功能单元（加法器、逻辑运算、移位器）加一个多路选择器：控制线选择把哪个结果送上输出。减法用补码实现 $A - B = A + \lnot B + 1$ ，与加法共用同一套电路——这是补码（→ 信息的表示）在硬件上的回报。

数据通路的胶水

除加法器外，组合逻辑还有两类通用部件：

多路选择器（MUX）：控制线选择多路输入之一。它是"选择"的物理形态，也是 ALU、寄存器堆读口的构件。
译码器（decoder）： $n$ 位输入激活 $2^n$ 路输出之一。它把地址变成"选中某一行"，是内存寻址的基础。

这些部件都是组合逻辑：输出只依赖当前输入，没有记忆。记忆从何而来是下一章的主题（→ 时序逻辑、时钟与状态机）。

本章要点

任何布尔函数都能只用 NAND 实现，制造因此只需要一种晶体管配置
卡诺图按格雷码排列使相邻项可合并；大规模化简交给逻辑综合
进位链决定加法器延迟，超前进位以面积换速度把延迟降到 $O(\log n)$
ALU 是一组功能单元加一个多路选择器；减法与加法共用电路靠补码