引言：组合逻辑电路 (Combinational Circuits)#

在深入学习本章之前，我们先回顾一下上周学习的基础知识：

• 逻辑门：反相器 (Inverter/NOT), 与门 (AND), 或门 (OR), 与非门 (NAND), 或非门 (NOR), 异或门 (XOR), 同或门 (XNOR)。
• 逻辑门相关概念：真值表 (Truth Table), 时序图 (Timing diagram), 逻辑表达式 (Logic expression), 以及不同形状的逻辑门符号。
• 逻辑电平：高电平和低电平的概念，以及抗干扰能力的度量——噪声容限 (Noise Margins)。

本章我们将聚焦于一种重要的逻辑电路——组合逻辑电路。

1. 什么是逻辑电路？

一个逻辑电路系统，无论简单还是复杂，都可以看作一个“黑盒子”，它由四个基本部分组成：

• 输入 (Inputs)：电路接收的信号。
• 输出 (Outputs)：电路根据输入产生的信号。
• 功能规格 (Functional specification)：描述输入和输出之间逻辑关系的规则。例如，“当输入A和输入B都为高电平时，输出Y才为高电平”。
• 时序规格 (Timing specification)：描述电路响应速度的规则。例如，“从输入信号变化到输出信号稳定所需的时间”。

2. 电路的节点与元件

• 节点 (Nodes)：电路中信号的连接点。
  • 输入节点：接收外部输入，如 A, B, C。
  • 输出节点：向外部发送输出，如 Y, Z。
  • 内部节点：连接电路内部元件的点，如 n1。
• 电路元件 (Circuit elements)：构成电路的基本单元，如 E1, E2, E3。每个元件本身也可以看作一个小的逻辑电路。

3. 逻辑电路的两种主要类型

• 组合逻辑 (Combinational Logic) - 第5章内容

  • 特点：无记忆性 (Memoryless)。
  • 工作方式：任意时刻的输出仅仅取决于该时刻的输入值。它不关心过去的输入是什么。我们本章主要讨论的就是这类电路。

• 时序逻辑 (Sequential Logic) - 第6章内容

  • 特点：有记忆性 (Has memory)。
  • 工作方式：任意时刻的输出不仅取决于当前的输入值，还取决于电路过去的状态（即由之前的输入所决定的状态）。

4. 组合逻辑的构成规则

一个电路要被称为“组合逻辑电路”，必须满足以下三个规则：

1. 所有元件都是组合性的：电路中的每一个逻辑门或模块都必须是无记忆的。
2. 每个节点来源唯一：每个节点要么是一个主输入，要么精确地连接到一个元件的输出端。这保证了信号不会发生冲突。
3. 无循环路径 (No cyclic paths)：信号的流向是单向的，从输入到输出，不能形成一个闭环。如果存在循环，电路的行为将变得不稳定，可能会产生振荡，这就变成了时序逻辑的范畴。

第一部分：布尔方程 (Boolean Equations)#

布尔方程是描述组合逻辑电路功能的数学语言。它用代数表达式来精确定义输出和输入之间的关系。

示例：全加器

一个全加器有三个输入 (A, B, Cin) 和两个输出 (S, Cout)。

• 输出 S (和) = A ⊕ B ⊕ Cin (⊕ 代表异或)
• 输出 Cout (进位) = AB + ACin + BCin

这里的 S = F(A, B, Cin) 和 Cout = F(A, B, Cin) 就是布尔方程的通用形式。

如何构建布尔表达式？

我们可以将日常语言描述的逻辑关系转换为布尔方程。

• 例 1: “如果天没下雨 (NOT Raining) 并且 (AND) 我们有三明治 (Sandwiches)，我们就去公园 (Park)。”

  • 设 P=1 代表去公园，R=1 代表下雨，S=1 代表有三明治。
  • “天没下雨” 表示为 R̄ (R的非)。
  • “并且” 对应布尔乘法 (AND)。
  • 布尔方程: P = R̄ • S

• 例 2: “如果我们给你一百万美元 (M) 或者 (OR) 一个小记事本 (N)，你就会被视为赢家 (Winner)。”

  • 设 W=1 代表是赢家，M=1 代表有一百万美元，N=1 代表有记事本。
  • “或者” 对应布尔加法 (OR)。
  • 布尔方程: W = M + N

• 例 3: “如果你自己做饭 (M) 或者 (OR) 你有一个既有才 (T) 又不贵 (NOT Expensive) 的私人厨师 (C)，你就能吃到美食 (E)。”

  • 设 E=1 代表吃到美食，M=1 代表自己做，C=1 代表有厨师，T=1 代表厨师有才，X=1 代表厨师很贵。
  • “不贵” 表示为 X̄。
  • “既有才又不贵的厨师” 是一个 AND 关系：C • T • X̄
  • 整个逻辑是 OR 关系。
  • 布尔方程: E = M + (C • T • X̄)

第二部分：布尔代数：公理与定理 (Axioms & Theorems)#

布尔代数是简化和处理布尔方程的一套数学工具。它和普通代数相似，但更简单，因为变量只有两个取值：1 (真) 和 0 (假)。

1. 对偶性 (Duality)

这是布尔代数的一个核心特性。对于任何一个布尔表达式，你只要将：

• AND (•) 替换为 OR (+)
• OR (+) 替换为 AND (•)
• 0 替换为 1
• 1 替换为 0 就可以得到它的对偶表达式。如果原表达式成立，其对偶表达式也一定成立。

2. 布尔代数公理 (Axioms)

公理是布尔代数体系的基石，是不证自明的基本规定。

3. 布尔代数运算

• 布尔加法 (Boolean Addition)：等同于 OR 运算。

  • 对于 A + B̄ + C + D̄ = 0，只有当每一项都为0时，表达式才为0。
  • 因此 A=0, B̄=0, C=0, D̄=0，解得 A=0, B=1, C=0, D=1。

• 布尔乘法 (Boolean Multiplication)：等同于 AND 运算。

  • 对于 A • B̄ • C • D̄ = 1，只有当每一项都为1时，表达式才为1。
  • 因此 A=1, B̄=1, C=1, D̄=1，解得 A=1, B=0, C=1, D=0。

4. 布尔代数基本定律与规则 (Theorems)

这些是由公理推导出来的常用定理，是逻辑简化的核心工具。

• 基本定律

  • 交换律 (Commutative): A + B = B + A | AB = BA
  • 结合律 (Associative): A + (B + C) = (A + B) + C | A(BC) = (AB)C
  • 分配律 (Distributive): A(B + C) = AB + AC | A + BC = (A + B)(A + C) (注意这个对偶形式)

• 常用规则

如何证明这些定理？

• 方法一：穷举法/完美归纳法 (Perfect Induction)

  • 也叫“真值表法”。
  • 列出所有可能的输入组合，并计算等式两边的值。
  • 如果对于每一种输入组合，等式两边的值都相等，则定理得证。

• 方法二：代数法

  • 利用已知的公理和其他定理，对等式的一边进行代数运算，直到它变得和另一边完全一样。

示例：证明规则10 (A + AB = A)

• 方法一（穷举法）:

  A	B	AB	A + AB
  0	0	0	0
  0	1	0	0
  1	0	0	1
  1	1	1	1
  观察 A 列和 A+AB 列，对于所有输入组合，值都完全相同。得证。

• 方法二（代数法）:

  1
  A + AB
  2
  = A • 1 + AB     (根据规则4: A = A•1)
  3
  = A(1 + B)       (根据分配律，提取公因式A)
  4
  = A • 1          (根据规则2: 1 + B = 1)
  5
  = A              (根据规则4: A•1 = A)
  

  得证。

第三部分：德摩根定理 (DeMorgan’s Theorems)#

德摩根定理是布尔代数中极其重要的工具，尤其在“与非门”和“或非门”的逻辑转换中。

• 定理1: (XY)̄ = X̄ + Ȳ

  • 文字描述: 乘积的非 等于 非的和。
  • 电路等效: 一个 NAND (与非) 门 等效于 输入端都取反的 OR (或) 门 (也叫 Negative-OR)。

• 定理2: (X + Y)̄ = X̄ • Ȳ

  • 文字描述: 和的非 等于 非的积。
  • 电路等效: 一个 NOR (或非) 门 等效于 输入端都取反的 AND (与) 门 (也叫 Negative-AND)。

应用德摩根定理的例子： 对整个表达式最外层的长横线使用德摩根定理。

a) (A + B) + C -> ( (A+B)̄ ) • C̄ -> (ĀB̄) • C̄ b) (Ā + B) + CD -> ( (Ā+B)̄ ) • (CD)̄ -> (A • B̄) • (C̄ + D̄) c) (A + B̄)CD + E + F -> ( (A+B̄)CD )̄ • (E+F)̄ -> ( (A+B̄)̄ + (CD)̄ ) • (ĒF̄) -> ( (ĀB) + (C̄+D̄) ) • ĒF̄

第四部分：使用布尔代数简化逻辑表达式#

简化的目标是使用最少的逻辑门实现相同的功能，这样可以降低成本、功耗和延迟。

示例 1： Y = ĀB + AB Y = (Ā + A)B (提取公因式 B) Y = (1)B (根据规则 A+Ā=1) Y = B (根据规则 1•B=B)

示例 2： Y = ĀBC̄ + ABC̄ + AB̄C̄ 这个表达式可以重复使用中间项 ABC̄ 来简化： Y = (ĀBC̄ + ABC̄) + (ABC̄ + AB̄C̄) Y = (Ā+A)BC̄ + A(B+B̄)C̄ Y = (1)BC̄ + A(1)C̄ Y = BC̄ + AC̄ Y = (B+A)C̄ (最终简化结果)

常见的简化错误：

• 丢掉反相符号(bar)：书写时一定要对齐，避免看错。
• 用错定理：
  • 错误: ABC + ĀBC = B。正确: ABC + ĀBC = BC。合并项时，只能有一个变量不同。
  • 错误: (A • Ā) = 1。正确: (A • Ā) = 0。
  • 错误: A + C = Ā + C̄。正确 (德摩根): (A + C)̄ = Ā • C̄。

第五部分：SOP 和 POS 范式#

任何布尔表达式都可以被转换成两种标准形式（范式）：SOP (Sum-of-Products，积之和) 和 POS (Product-of-Sums，和之积)。

1. 基本定义

• 文字 (Literal): 一个变量或它的反变量 (如 A, Ā)。
• 积项 / 蕴含项 (Implicant / Product term): 若干文字的“与”(AND) 运算 (如 ABC, ĀC)。
• 和项 (Sum term): 若干文字的“或”(OR) 运算 (如 A+B+C)。
• 最小项 (Minterm): 一种特殊的积项，它包含了所有输入变量。例如，若系统有A,B,C三个输入，则 ĀBC 是一个最小项，但 ĀC 不是。
• 最大项 (Maxterm): 一种特殊的和项，它包含了所有输入变量。例如，A+B̄+C 是一个最大项。

2. SOP (积之和) 形式

• 结构: 多个积项通过“或”(OR) 运算连接起来。Y = AB + BC' + DE
• 特点: 从真值表中，找出所有输出 Y=1 的行。
• 每一行对应一个最小项 (Minterm)。
• 将这些最小项相加 (OR)，就得到了SOP表达式。
• 规则: 在某一行中，如果变量为1，则在最小项中为原变量；如果为0，则为反变量。

3. POS (和之积) 形式

• 结构: 多个和项通过“与”(AND) 运算连接起来。Y = (A+B)(C+D)(E'+F)
• 特点: 从真值表中，找出所有输出 Y=0 的行。
• 每一行对应一个最大项 (Maxterm)。
• 将这些最大项相乘 (AND)，就得到了POS表达式。
• 规则: 在某一行中，如果变量为0，则在最大项中为原变量；如果为1，则为反变量。（与最小项规则相反）

示例：SOP与POS转换 假设一个真值表，我们通过两种方法得到的表达式功能是完全等价的。 比如，从SOP得到的 E = CM 和从POS得到的 E = (C+M)(C+M̄)(C̄+M̄)，后者化简后也会等于 CM。

4. 标准 (Standard) SOP/POS 形式

• 标准SOP: SOP表达式中的每一个积项都是最小项（包含所有变量）。
• 标准POS: POS表达式中的每一个和项都是最大项（包含所有变量）。

我们可以通过乘以 (D+D̄) 或加上 DD̄ (它们分别为1和0) 来将一个普通表达式补充为标准形式。

第六部分：卡诺图 (Karnaugh Maps, K-Map)#

卡诺图是一种图形化的逻辑简化工具，它将真值表用一种巧妙的方式排列，使得相邻的项可以被直观地合并简化。

1. 卡诺图结构

• 单元格 (Cells): 每个单元格代表一个最小项（即真值表的一行）。
• 单元格数量: 对于 n 个变量，卡诺图有 2^n 个单元格。
• 排列方式: 卡诺图的行列索引采用格雷码 (Gray code) 排列。格雷码的特点是任意两个相邻编码只有一位不同。这保证了在图中物理上相邻的单元格，其对应的最小项在逻辑上也只有一个变量不同，因此可以合并。

2. 卡诺图简化规则 (SOP - 圈1)

1. 目标: 用最大、最少的圈来框住图中所有的 “1”。
2. 圈的形状: 只能是矩形，不能是L形或对角线。
3. 圈的大小: 圈住的 “1” 的数量必须是 2的幂 (1, 2, 4, 8, …)。
4. 圈的原则:
   • 每个 “1” 都必须至少被圈一次。
   • 圈要尽可能大。一个大圈代表消去更多的变量。
   • 圈的总数要尽可能少。
5. 循环相邻: 卡诺图的上下边界和左右边界是相邻的。可以画出跨越边界的圈。

3. 从圈到表达式 每个圈对应SOP表达式中的一个积项。在一个圈内，如果某个变量既出现了0又出现了1，说明这个变量是多余的，可以被消去。只保留那些在圈内保持不变的变量。

示例（4变量卡诺图）: 一个覆盖了 AB=00, CD=00 和 AB=00, CD=10 两个单元格的圈，其对应的最小项是 ĀB̄C̄D̄ 和 ĀB̄CD̄。在这个圈内，A, B, D 的值都保持不变 (0, 0, 0)，而 C 的值变化了 (0 -> 1)，所以C被消去。这个圈代表的积项就是 ĀB̄D̄。

4. POS 简化 (圈0) POS简化的过程与SOP类似，但目标是圈住所有的 “0”。

• 圈 “0” 的规则与圈 “1” 完全相同。
• 每个圈对应最终POS表达式中的一个和项。
• 在一个圈内，保留不变的变量，但取值规则与最大项相同：0代表原变量，1代表反变量。

5. 无关项 (Don’t Cares, X) 在某些实际电路中，某些输入组合是永远不会出现的，或者出现了我们也不关心其输出是什么。这些情况称为无关项，在卡诺图中用 “X” 表示。

• 简化规则: “X” 可以根据需要被当作 “1”（如果它能帮助我们画一个更大的圈）或者被当作 “0”（如果不圈它对结果更有利）。我们没有义务去圈所有的 “X”。

章节复习与测验#

本章核心知识点回顾

• 组合电路的定义与规则。
• 布尔方程的建立。
• 布尔代数的公理、定理（交换律、结合律、分配律等）。
• 德摩根定理及其应用。
• 使用布尔代数化简表达式。
• SOP和POS范式，最小项与最大项。
• 卡诺图的原理与使用方法（包括无关项）。

随堂测验：判断正误

1. 变量(Variable)、补码(complement)和文字(literal)都是布尔代数中使用的术语。

   • 正确 (✓)。

2. 布尔代数中的加法等同于或非(NOR)功能。

   • 错误 (✗)。布尔加法等同于 或(OR) 功能。

3. 布尔代数中的乘法等同于与(AND)功能。

   • 正确 (✓)。

4. 交换律、结合律和分配律都是布尔代数的定律。

   • 正确 (✓)。

5. 0的补码是0本身。

   • 错误 (✗)。根据公理A2，0的补码是 1。

6. 当一个布尔变量与它的补码相乘时，结果是该变量本身。

   • 错误 (✗)。根据互补律 A • Ā = 0，结果恒为 0。

7. “变量乘积的补码等于各自变量补码的和” 是德摩根定理的陈述。

   • 正确 (✓)。这是 (XY)̄ = X̄ + Ȳ 的文字描述。

8. SOP代表“积之和”(sum-of-products)。

   • 正确 (✓)。

9. 卡诺图可以用来简化布尔表达式。

   • 正确 (✓)。这是它的主要用途。

10. 一个三变量卡诺图有六个单元格。

    • 错误 (✗)。一个 n 变量卡诺图有 2^n 个单元格，所以三变量卡诺图有 2^3 = 8 个单元格。