02. 布尔代数与逻辑函数化简

2.1 布尔代数基础 (Boolean Algebra Fundamentals)

布尔代数是分析和简化数字逻辑电路的数学工具。它由一组元素、一组运算符和若干公理/定理构成。

• 元素 (Elements): 二值变量，取值为 或 。
• 运算符 (Operators):
  • 与 (AND): 逻辑乘，用 表示（常省略）。
  • 或 (OR): 逻辑加，用 表示。
  • 非 (NOT): 逻辑反，用 或 表示。
• 运算优先级 (Operator Precedence): 括号 > 非 (NOT) > 与 (AND) > 或 (OR)

2.1.1 公理与定理 (Axioms and Theorems)

公理和定理是进行逻辑表达式化简的基础。一个重要的性质是对偶性 (Duality)：将表达式中的 与 互换， 与 互换，等式依然成立。

单变量定理

定理	表达式	对偶形式	名称
1			恒等律 (Identity)
2			零一律 (Null Element)
3			等幂律 (Idempotency)
4			反演律 (Involution)
5			互补律 (Complements)

多变量定理

定理	表达式	对偶形式	名称
6			交换律 (Commutativity)
7			结合律 (Associativity)
8			分配律 (Distributivity)
9			吸收律 (Absorption)
10			合并律 (Combining)
11			化简律 (Simplification)
12			共识律 (Consensus)
13			德摩根定律 (DeMorgan's Law)

---

重点与难点解释

• 分配律的对偶形式: 是布尔代数独有的，区别于普通代数，非常重要且常用。它常用于将“与或”式转换为“或与”式。
• 德摩根定律 (DeMorgan's Law): 这是最重要的定理之一，用于求函数的反函数以及在不同逻辑门（如与非门、或非门）之间进行转换。
  • 口诀: “长线变短线，符号（ 和 ）互换”。
  • 用例: 化简
    1. 将整个表达式看作 ，其中 。
    2. 应用德摩根定律得 ，即 。
    3. 对 再次应用德摩根定律，得 ，即 。
    4. 最终结果为 。

2.2 布尔函数 (Boolean Functions)

布尔函数由布尔变量、运算符和括号组成。它可以有多种表现形式，但其逻辑功能是唯一的。

• 文字 (Literal): 一个变量的原变量或反变量（如 或 ）。
• 乘积项 (Product term): 由“与”运算连接的若干文字（如 ）。
• 和项 (Sum term): 由“或”运算连接的若干文字（如 ）。

核心结论: 一个布尔函数有唯一的真值表 (Truth Table) 表达，但可以有多种代数表达式和逻辑门电路实现。

用例: 函数 和 尽管它们的代数表达式不同，但它们的真值表是完全相同的。通过代数化简可以证明 ：

的表达式更简单，意味着实现它所需的逻辑门更少，成本更低。因此，函数化简是数字逻辑设计的核心目标之一。

2.2.1 函数的补函数 (Complement of a Function)

求一个函数 的补函数 ，最系统的方法是反复应用德摩根定律。一个更快捷的技巧是：

1. 求对偶式 (Dual): 将原始表达式中的 和 互换。
2. 反转每个文字 (Complement each literal): 将表达式中的每个原变量变为反变量，反之亦然。

用例: 求 的补函数 。

1. 原始函数:
2. 步骤 1：求对偶式: 将 换成 ，将 换成 。 注意: 此时得到的并不是 ，这只是一个中间步骤。
3. 步骤 2：反转每个文字: 将 换成 ， 换成 ， 换成 ， 换成 。 这就是最终结果。

2.3 范式与标准式 (Canonical and Standard Forms)

2.3.1 最小项与最大项 (Minterms and Maxterms)

对于一个 变量的函数，其真值表有 行。每一行都对应一个最小项和一个最大项。

• 最小项 (Minterm, ): 一个包含全部 个变量的乘积项。如果变量在对应行中的值为 ，则取反形式；如果为 ，则取原形式。
• 最大项 (Maxterm, ): 一个包含全部 个变量的和项。如果变量在对应行中的值为 ，则取原形式；如果为 ，则取反形式。

重要关系: 同一行的最小项和最大项互为反函数，即 。

3 变量 (x, y, z) 的最小项与最大项表示

行号	x	y	z	最小项 ()	最大项 ()
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

2.3.2 范式 (Canonical Forms)

范式是函数的唯一、标准化的表达形式。

1. 最小项之和 (Sum-of-Minterms, SoM)

   • 定义: 将真值表中函数值为 的所有行对应的最小项相“或”。
   • 表示法: ，其中 是函数值为 的行号。
   • 用例: 若某函数在行 1, 3, 6, 7 处值为 1，则其 SoM 形式为：

2. 最大项之积 (Product-of-Maxterms, PoM)

   • 定义: 将真值表中函数值为 的所有行对应的最大项相“与”。
   • 表示法: ，其中 是函数值为 的行号。
   • 用例: 若某函数在行 0, 2, 4, 5 处值为 0，则其 PoM 形式为：

范式间的转换 SoM 和 PoM 可以相互转换。如果已知一个，另一个就由原形式中未包含的行号决定。 推导: 根据德摩根定律， 因为 ，所以

2.3.3 函数到范式的转换

将一个普通布尔表达式转换为范式，需要将每个项都补充完整，使其包含所有变量。

• 转为 SoM (最小项之和): 对每个乘积项，乘以 形式的缺失变量项。
  • 用例: 将 转换为 SoM (假设为 3 变量 A, B, C)。
• 转为 PoM (最大项之积): 先用分配律 将函数转为“和之积”形式，再对每个和项，加上 形式的缺失变量项。
  • 用例: 将 转换为 PoM。

2.3.4 标准式与范式对比

标准式 (Standard Form) 是比范式更普遍的表达，其项中不要求包含所有变量。

• 与或式 (Sum-of-Products, SoP): 如
• 或与式 (Product-of-Sums, PoS): 如

特性	范式 (Canonical Form)	标准式 (Standard Form)
唯一性	是。一个函数只有一种 SoM 和一种 PoM。	否。一个函数可以有多种 SoP 和 PoS 形式。
变量要求	每个项（最小项/最大项）必须包含所有输入变量。	项中可以不包含所有输入变量。
表达式长度	通常较长，文字和项较多。	通常更短，是化简后的结果。
与真值表关系	直接对应，可从真值表直接读出。	不直接对应，是化简后的结果。
用途	提供唯一的、标准化的函数描述。	提供更简洁、电路实现成本更低的方案。

2.4 其他逻辑运算与逻辑门

除了基本的 AND, OR, NOT，还有其他常用的逻辑运算和门电路。

运算	名称	表达式	描述
NAND	与非		AND 后取反
NOR	或非		OR 后取反
XOR	异或		输入相异时输出 1
XNOR	同或		输入相同时输出 1
Buffer	缓冲器		信号增强，不改变逻辑

2.4.1 多输入逻辑门 (Multiple-Input Gates)

• AND, OR, XOR, XNOR: 具有交换律和结合律，可以直接扩展到多输入。

  • 多输入异或门 (XOR): 当输入中有奇数个 1 时，输出为 1。

• NAND, NOR: 具有交换律，但不具有结合律。

  • 因此，多输入 NAND 门被定义为所有输入先“与”再“非”，即 。
  • 多输入 NOR 门被定义为所有输入先“或”再“非”，即 。