2. 布尔代数与数字逻辑基础

章节导引

本页从《计算机系统基础讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标

能把逻辑需求写成布尔函数，并用代数或 K-map 做基本化简。

前置知识

命题逻辑、集合/代数基础，以及对 0/1 二值抽象的理解。

建议用时

建议 5–6 小时：门电路 1 小时，布尔代数 2 小时，K-map 与优化 2–3 小时。

练习建议

化简 3 个布尔函数；分别写出 SOP/POS；用 Bubble Pushing 改写一个多级电路。

参考资料与引用边界

• 整理者：Lumner。
• 课程来源：根据 SYS/ 目录下的课件整理；本章对应课件：SYS/Lec02_Boolean Algebra.pptx。
• 原始讲义文件：note/SYS_计算机系统基础讲义.md。
• 引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

2.1 为什么使用数字逻辑

数字系统有意限制设计选择：把连续物理量划分为离散的 0 和 1。这种“数字纪律”带来几个好处：

• 抗噪声能力更强。
• 设计、组合、验证更简单。
• 可以构建大规模复杂系统。
• 适合使用自动化设计工具和标准单元库。

2.2 逻辑变量与基本逻辑运算

二值变量可用多种语义解释：

1 / 0
True / False
On / Off
High / Low
Yes / No

三种基本逻辑运算：

运算	常用符号	含义
AND	· 或省略	全为 1 时输出 1
OR	+	至少一个为 1 时输出 1
NOT	上划线、'、~	取反

常见门包括 NOT、Buffer、AND、OR、NAND、NOR、XOR、XNOR。NAND 和 NOR 是功能完备门，只用其中一种就能实现任意布尔函数。

2.3 晶体管与逻辑门

早期计算机使用继电器和真空管作为开关，现代数字电路主要使用晶体管。CMOS 电路由 NMOS 和 PMOS 晶体管组合而成，常用于实现 NAND、NOR、反相器等逻辑门。

数字电路不是理想数学对象，它受到物理参数影响：

参数	含义
VCC / VDD	电源电压
VIH	输入被识别为高电平的最低电压
VIL	输入被识别为低电平的最高电压
VOH	输出高电平保证值
VOL	输出低电平保证值
噪声容限	高/低电平能承受的噪声范围
传播延迟	输入变化到输出稳定变化的时间
转换时间	输出从低到高或高到低所需时间
功耗	静态功耗和动态功耗
扇入	一个门可接受的输入数量
扇出	一个输出可驱动的输入负载数量

噪声容限：

NMH = VOH - VIH
NML = VIL - VOL

传播延迟可分为：

• tPLH：输出从低到高的延迟。
• tPHL：输出从高到低的延迟。
• tpd = max(tPLH, tPHL)。

延迟模型：

模型	含义
Transport delay	输入变化经过固定延迟后体现在输出
Inertial delay	太窄的脉冲会被电路“过滤”掉，更接近真实电路

动态功耗通常与开关活动、电容、电压和频率相关。CMOS 静态功耗低，但随着工艺缩小，泄漏功耗也变得重要。

2.4 布尔代数基本律

常用恒等式：

名称	表达式
恒等律	X + 0 = X，X·1 = X
零一律	X + 1 = 1，X·0 = 0
幂等律	X + X = X，X·X = X
互补律	X + X' = 1，X·X' = 0
双重否定	(X')' = X
交换律	X + Y = Y + X，XY = YX
结合律	(X+Y)+Z = X+(Y+Z)，(XY)Z = X(YZ)
分配律	X(Y+Z)=XY+XZ，X+YZ=(X+Y)(X+Z)
吸收律	X + XY = X，X(X+Y)=X
合并律	XY + XY' = X
共识定理	AB + A'C + BC = AB + A'C
De Morgan	(XY)' = X' + Y'，(X+Y)' = X'Y'

运算优先级：

括号 > NOT > AND > OR

2.5 对偶性

对偶表达式通过交换 + 与 ·、交换 0 与 1 得到。如果一个布尔代数公式成立，则它的对偶公式也成立。对偶性可以减少证明工作。

例：

X + XY = X

其对偶为：

X(X + Y) = X

2.6 逻辑函数表示

逻辑函数描述输入变量与输出变量之间的关系。常见表示：

表示	特点
真值表	唯一、直观，但变量多时指数级增长
波形图	适合描述随时间变化的输入输出
布尔表达式	不唯一，适合代数变换
电路图	对应实际实现
HDL	适合仿真、综合和工程实现

如果两个函数的真值表完全相同，则两个函数等价。

2.7 最小项、最大项与标准形式

定义：

• Literal：变量或变量的反。
• Product term：若干 literal 通过 AND 连接。
• Sum term：若干 literal 通过 OR 连接。
• Minterm：包含所有变量且每个变量出现一次的乘积项。
• Maxterm：包含所有变量且每个变量出现一次的和项。

最小项 m_j 对应真值表中编号为 j 的一行，且只在该行取 1。最大项 M_j 对应真值表中编号为 j 的一行，且只在该行取 0。

规范形式：

F = Σm(函数取 1 的行号)
F = ΠM(函数取 0 的行号)

规范形式在变量顺序固定时唯一。标准 SOP/POS 形式不要求每个项都包含所有变量，因此不唯一。

2.8 化简目标与代价

电路优化目标是以更低成本实现同一逻辑函数。常见代价：

代价	含义
Literal cost L	表达式中 literal 出现次数
Gate input cost G	门输入数量，不计反相器
Gate input cost with NOTs GN	门输入数量，计入反相器

更少的门输入通常意味着更小面积、更低功耗、更短延迟，但实际工程还要考虑扇入、扇出、布线、标准单元库和时序约束。

2.9 Karnaugh Map

K-map 是小变量数布尔函数的图形化化简工具。每个格子对应一个最小项，相邻格子只相差一个变量。

K-map 化简规则：

1. 每个函数值为 1 的格子必须至少被圈一次。
2. 每个圈的格子数必须是 2 的幂。
3. 圈应尽可能大。
4. 圈可以跨越边界，因为 K-map 边界相邻。
5. don't care 只在有助于化简时圈入。
6. 最后选择尽量少、尽量大的 prime implicants。

术语：

名称	含义
Implicant	能覆盖某些 1 的乘积项
Prime implicant	不能再扩大的 implicant
Essential prime implicant	覆盖了某些只被它覆盖的 1

化简结果可能不唯一。不同结果可能逻辑等价，但成本、延迟、布局效果不同。

2.10 Bubble Pushing 与多级优化

Bubble pushing 使用 De Morgan 定理在电路图上移动反相气泡：

• 门体类型在 AND 与 OR 之间转换。
• 输入或输出端添加/取消反相气泡。
• 相邻气泡相遇时可以抵消。

它常用于把电路转换成更适合 NAND/NOR 标准单元库的形式。

多级优化不同于两级 SOP/POS。通过提取公共因子、共享中间信号，可以降低门输入成本。例如：

AB + AC = A(B + C)

多级电路通常面积更小，但延迟分析和毛刺分析更复杂。

2.11 XOR、奇偶校验与三态逻辑

XOR 表示“不同为 1”：

X ⊕ Y = X'Y + XY'

性质：

X ⊕ 0 = X
X ⊕ 1 = X'
X ⊕ X = 0
X ⊕ X' = 1

XOR 常用于：

• 加法器。
• 减法器。
• 乘法器。
• 计数器。
• 奇偶校验生成与检查。

奇偶校验通过添加一位 parity bit，让整个码字中 1 的个数为奇数或偶数。它能检测单比特错误，但不能纠正错误，也不能可靠检测所有多比特错误。

三态输出除了 0 和 1，还有 Hi-Z 高阻态。高阻态相当于输出断开，常用于多设备共享总线。三态缓冲器：

EN	IN	OUT
0	X	Hi-Z
1	0	0
1	1	1

传输门也是一种电子开关，可在控制信号作用下连接或断开两个节点。

---