布尔代数化简与卡诺图入门-编程阁

06 - 布尔代数化简与卡诺图入门

卡诺图是数字电路设计的瑞士军刀，一图在手，化简无忧。

🎯 本章学习要点

理解卡诺图的结构和布局原理
掌握在卡诺图上标注最小项的方法
能够使用卡诺图进行逻辑函数化简
理解"相邻"的概念及其在化简中的作用

1️⃣ 为什么需要化简？

化简的意义

💡 化简前 vs 化简后 ┌─────────────────────────────────────────────────────────────┐ │ │ │ 【原始表达式】 │ │ Y = AB + AĀB̄ + ĀB │ │ │ │ ┌───────────────────────────────────────────────────┐ │ │ │ 电路示意图 │ │ │ │ │ │ │ │ A ──┐ │ │ │ │ ├──○──┐ │ │ │ │ B ──┘ ├──○──┐ │ │ │ │ │ ├──○──┐ │ │ │ │ A ──┐ │ │ │ │ │ │ │ ├──○──┤ │ ├──○──┐ │ │ │ │ B̄ ──┘ │ │ │ ├──○── Y │ │ │ │ │ │ │ │ │ │ │ │ Ā ──┐ │ │ │ │ │ │ │ │ ├──○──┐ │ │ │ │ │ │ │ │ B ──┘ ├──○──┤ │ │ │ │ │ │ └──○──┴────┴────┘ │ │ │ │ │ │ │ │ 门数量：6个门 + 3个反相器 = 9个门 │ │ │ │ │ │ │ └───────────────────────────────────────────────────┘ │ │ │ │ 【化简后】 │ │ Y = A + B̄ │ │ │ │ ┌───────────────────────────────────────────────────┐ │ │ │ 电路示意图 │ │ │ │ │ │ │ │ A ────────────────────────────○── Y │ │ │ B̄ ──┐ │ │ │ │ ├──○── │ │ │ │ (或门) │ │ │ │ │ │ │ │ 门数量：1个或门 + 1个反相器 = 2个门 │ │ │ │ │ │ │ └───────────────────────────────────────────────────┘ │ │ │ │ 【化简收益】 │ │ ┌─────────────────────────────────────────────────────┐ │ │ │ 门数量：9 → 2，减少 78%！ │ │ │ │ 成本：大幅降低 │ │ │ │ 延迟：路径更短，响应更快 │ │ │ │ 功耗：更少的门意味着更低的功耗 │ │ │ └─────────────────────────────────────────────────────┘ │ │ │ └─────────────────────────────────────────────────────────────┘

2️⃣ 卡诺图（Karnaugh Map）概述

什么是卡诺图？

📐 卡诺图的发明 卡诺图（Karnaugh Map）由贝尔实验室的物理学家莫里斯·卡诺 （Maurice Karnaugh）于1953年发明，是一种可视化逻辑函数化简工具。 ┌─────────────────────────────────────────────────────────────┐ │ │ │ 莫里斯·卡诺 (1924-2024) │ │ 美国工程师、科学家 │ │ 卡诺图发明者 │ │ │ │ 1953年发表论文："The Map Method for Synthesis of │ │ Combinational Logic Circuits" │ │ │ └─────────────────────────────────────────────────────────────┘ 💡 卡诺图的核心思想： - 将真值表的信息重新排列 - 使得"相邻"的最小项在几何上也是相邻的 - 利用相邻项合并消除变量

2变量卡诺图

📊 最简单的卡诺图：2变量卡诺图 ┌─────────────────────────────────────────────────────────────┐ │ │ │ 【结构】 │ │ │ │ ┌─────────────────────────┐ │ │ │ │ B=0 │ B=1 │ │ │ │ ─────┼─────────┼─────────│ │ │ │ A=0 │ m0 │ m1 │ │ │ │ ─────┼─────────┼─────────│ │ │ │ A=1 │ m2 │ m3 │ │ │ └─────────────────────────┘ │ │ │ │ 【变量坐标】 │ │ │ │ ┌─────────────────────────┐ │ │ │ │ 0 │ 1 │ │ │ │ ─────┼─────────┼─────────│ │ │ │ 0 │ 0 │ 1 │ │ │ │ ─────┼─────────┼─────────│ │ │ │ 1 │ 2 │ 3 │ │ │ └─────────────────────────┘ │ │ │ │ 【注意】坐标不是二进制递增，而是遵循格雷码顺序！ │ │ 00 → 01 → 11 → 10 （相邻码只有1位不同） │ │ │ └─────────────────────────────────────────────────────────────┘

3变量卡诺图

📊 3变量卡诺图（最常用） ┌─────────────────────────────────────────────────────────────┐ │ │ │ 【结构】 │ │ │ │ ┌────────────────────────────────────┐ │ │ │ │ BC=00 │ BC=01 │ BC=11 │ BC=10 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ A=0 │ m0 │ m1 │ m3 │ m2 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ A=1 │ m4 │ m5 │ m7 │ m6 │ │ │ └────────────────────────────────────┘ │ │ │ │ 【变量取值】 │ │ │ │ ┌────────────────────────────────────┐ │ │ │ │ 00 │ 01 │ 11 │ 10 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ 0 │ 0 │ 1 │ 3 │ 2 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ 1 │ 4 │ 5 │ 7 │ 6 │ │ │ └────────────────────────────────────┘ │ │ │ │ 【最小项索引】 │ │ m0 = ĀB̄C̄, m1 = ĀB̄C, m2 = ĀBC̄, m3 = ĀBC │ │ m4 = AB̄C̄, m5 = AB̄C, m6 = ABC̄, m7 = ABC │ │ │ └─────────────────────────────────────────────────────────────┘

4变量卡诺图

📊 4变量卡诺图 ┌─────────────────────────────────────────────────────────────┐ │ │ │ ┌──────────────────────────────────────────────┐ │ │ │ │ CD=00 │ CD=01 │ CD=11 │ CD=10 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ AB=00 │ m0 │ m1 │ m3 │ m2 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ AB=01 │ m4 │ m5 │ m7 │ m6 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ AB=11 │ m12 │ m13 │ m15 │ m14 │ │ │ │ ───────┼────────┼────────┼────────┼────────┤ │ │ │ AB=10 │ m8 │ m9 │ m11 │ m10 │ │ │ └──────────────────────────────────────────────┘ │ │ │ │ 💡 4变量卡诺图包含16个格子，每个格子代表一个最小项 │ │ │ └─────────────────────────────────────────────────────────────┘

3️⃣ 卡诺图的"相邻"概念

什么是相邻？

🔗 相邻的定义 两个最小项"相邻"当且仅当它们只有一个变量不同。 ┌─────────────────────────────────────────────────────────────┐ │ │ │ 【几何相邻】 │ │ │ │ ┌───┬───┐ │ │ │ a │ b │ ← a和b相邻（左右） │ │ └───┴───┘ │ │ │ │ ┌───┐ ┌───┐ │ │ │ c │ │ d │ ← c和d不相邻（对角） │ │ └───┘ └───┘ │ │ │ │ 【循环相邻】（卡诺图特殊规则） │ │ │ │ ┌───┬───┬───┐ │ │ │ A │ B │ A │ ← 最左和最右列相邻（循环） │ │ └───┴───┴───┘ │ │ │ │ ┌───┐ │ │ │ C │ ←┐ │ │ ├───┤ │ ← 顶行和底行相邻（循环） │ │ │ D │ ←┘ │ │ └───┘ │ │ │ │ 💡 循环相邻是卡诺图的独特性质！ │ │ │ └─────────────────────────────────────────────────────────────┘

相邻示例

📖 3变量卡诺图中m0的相邻项 ┌────────────────────────────────┐ │ │ 00 │ 01 │ 11 │ 10 │ │ ─────┼──────┼──────┼──────┼─────┤ │ 0 │ m0 │ m1 │ m3 │ m2 │ │ ─────┼──────┼──────┼──────┼─────┤ │ 1 │ m4 │ m5 │ m7 │ m6 │ └────────────────────────────────┘ m0 = ĀB̄C̄ (对应 A=0, B=0, C=0) 相邻项（只有一个变量不同）： ┌─────────────────────────────────────────────────────────────┐ │ │ │ 1. m0 ↔ m1：只改变C (C̄→C) │ │ ĀB̄C̄ → ĀB̄C │ │ 不同变量：C │ │ │ │ 2. m0 ↔ m2：只改变B (B̄→B) │ │ ĀB̄C̄ → ĀBC̄ │ │ 不同变量：B │ │ │ │ 3. m0 ↔ m4：只改变A (Ā→A) │ │ ĀB̄C̄ → AB̄C̄ │ │ 不同变量：A │ │ │ │ 4. m0 ↔ m2 同样相邻（循环） │ │ 左列m0 ↔ 右列m2 │ │ │ └─────────────────────────────────────────────────────────────┘

4️⃣ 使用卡诺图化简

化简步骤

🔧 卡诺图化简五步法 ┌─────────────────────────────────────────────────────────────┐ │ │ │ Step 1: 将函数填入卡诺图 │ │ ───────────────────────────────────────────── │ │ 在对应格子中填入1（表示该最小项存在） │ │ │ │ Step 2: 圈1（圈出相邻的1） │ │ ───────────────────────────────────────────── │ │ 1. 圈要"方方正正"，边长必须是2ⁿ (1,2,4,8,16...) │ │ 2. 圈要尽可能大（包含更多1） │ │ 3. 圈可以重叠（一个1可被多个圈共用） │ │ 4. 圈要覆盖所有1 │ │ │ │ Step 3: 读取每个圈对应的乘积项 │ │ ───────────────────────────────────────────── │ │ 圈内不变的变量保留，变化的变量消去 │ │ │ │ Step 4: 将所有乘积项相或 │ │ ───────────────────────────────────────────── │ │ Y = 乘积项1 + 乘积项2 + ... │ │ │ │ Step 5: 检查是否最简 │ │ ───────────────────────────────────────────── │ │ 尝试不同圈法，寻找最优解 │ │ │ └─────────────────────────────────────────────────────────────┘

实例1：2变量化简

📝 例题：用卡诺图化简 Y = Σm(0,1,3) Step 1: 填卡诺图 ┌───────────────┐ │ │ B=0 │ B=1 │ │ ─────┼──────┼──────┤ │ A=0 │ 1 │ 1 │ │ ─────┼──────┼──────┤ │ A=1 │ 0 │ 1 │ └───────────────┘ Step 2: 圈1 ┌───────────────┐ │ │ 0 │ 1 │ │ ─────┼──────┼──────┤ │ 0 │ 1 │ 1 │ ← 圈1（竖着的2个） │ ─────┼──────┼──────┤ │ 1 │ 0 │ 1 │ ← 圈2（单独） └───────────────┘ Step 3: 读取乘积项 圈1（竖着的2个）： - A=0 不变（保持Ā） - B变化（消除） → 乘积项：Ā 圈2（单独的1）： - A变化（消除） - B=1 不变（保持B） → 乘积项：B Step 4: 写结果 Y = Ā + B ✅ 验证： m0(00): Ā+B = 1+0 = 1 ✓ m1(01): Ā+B = 1+1 = 1 ✓ m3(11): Ā+B = 0+1 = 1 ✓

实例2：3变量化简

📝 例题：用卡诺图化简 Y = Σm(0,1,3,4,5,6) Step 1: 填卡诺图 ┌────────────────────────────────┐ │ │ 00 │ 01 │ 11 │ 10 │ │ ─────┼──────┼──────┼──────┼─────┤ │ 0 │ 1 │ 1 │ 1 │ 0 │ │ ─────┼──────┼──────┼──────┼─────┤ │ 1 │ 1 │ 1 │ 1 │ 0 │ └────────────────────────────────┘ Step 2: 圈1 ┌────────────────────────────────┐ │ │ 00 │ 01 │ 11 │ 10 │ │ ─────┼──────┼──────┼──────┼─────┤ │ 0 │ 1 │ 1 │ 1 │ 0 │ │ ─────┼──────┼──────┼──────┼─────┤ │ 1 │ 1 │ 1 │ 1 │ 0 │ └────────────────────────────────┘ ↑ ↑ 圈1(4个) 圈2(2个) Step 3: 读取乘积项 圈1（4个1组成的大方块）： - A变化：0→1（消除） - B变化：0→1（消除） - C=0 不变（保持C̄） → 乘积项：C̄ 圈2（最下面两个1，循环相邻）： - A=1 不变（保持A） - B变化：0→1（消除） - C变化：0→1（消除） → 乘积项：A Step 4: 写结果 Y = C̄ + A

实例3：4变量化简

📝 例题：用卡诺图化简 Y = Σm(0,2,3,4,5,6,7,8,10,11,14,15) Step 1: 填卡诺图 ┌────────────────────────────────────────────┐ │ │ CD=00 │ CD=01 │ CD=11 │ CD=10 │ │ ─────┼────────┼────────┼────────┼────────┤ │ AB=00 │ 1 │ 0 │ 0 │ 1 │ │ ─────┼────────┼────────┼────────┼────────┤ │ AB=01 │ 1 │ 1 │ 1 │ 1 │ │ ─────┼────────┼────────┼────────┼────────┤ │ AB=11 │ 0 │ 0 │ 1 │ 1 │ │ ─────┼────────┼────────┼────────┼────────┤ │ AB=10 │ 1 │ 0 │ 0 │ 1 │ └────────────────────────────────────────────┘ Step 2: 圈1 可以画出多个圈，包括8格圈和4格圈 Step 3: 读取乘积项 圈1(8格)：D̄ → 消除3个变量 圈2(4格)：B̄C̄ → 消除2个变量 圈3(4格)：B̄D → 消除2个变量 圈4(4格)：C̄D̄ → 消除2个变量 Step 4: 写结果 Y = D̄ + B̄C̄ + B̄D + C̄D̄

5️⃣ 卡诺图化简的技巧

技巧一：优先圈唯一的大圈

💡 优先圈唯一的大圈 如果某个1只能被一个圈覆盖，必须先圈它！ ┌─────────────────────────────────────────┐ │ │ │ ┌────────┬────────┬────────┬────────┐ │ │ │ 1 │ 1 │ 1 │ 1 │ │ │ ├────────┼────────┼────────┼────────┤ │ │ │ 1 │ 0 │ 1 │ 1 │ │ │ └────────┴────────┴────────┴────────┘ │ │ ↑ ↑ ↑ ↑ │ │ 唯一1 必须用 必须用 唯一1 │ │ 圈覆盖 圈1 圈2 圈覆盖 │ │ │ └─────────────────────────────────────────┘

技巧二：利用"无所谓"条件

💡 Don't Care（无关项）条件 某些输入组合在实际中不会出现，可以标记为X， 卡诺图化简时可以把X当作1或0来用（哪个更有利用哪个） ┌─────────────────────────────────────────────────────────────┐ │ │ │ 示例：设计BCD码的7段译码器 │ │ │ │ BCD码范围是0000~1001 │ │ 1010~1111这6个输入永远不会出现 │ │ │ │ ┌─────────────────────────────────────────┐ │ │ │ │ CD=00 │ CD=01 │ CD=11 │ CD=10 │ │ │ │ ─────┼────────┼────────┼────────┼────────┤ │ │ │ AB=00 │ 1 │ 1 │ 1 │ 1 │ │ │ │ ─────┼────────┼────────┼────────┼────────┤ │ │ │ AB=01 │ 1 │ 1 │ X │ X │ ← X可当1 │ │ │ ─────┼────────┼────────┼────────┼────────┤ │ │ │ AB=11 │ X │ X │ X │ X │ ← X全可当1│ │ │ ─────┼────────┼────────┼────────┼────────┤ │ │ │ AB=10 │ 1 │ 1 │ X │ X │ ← X可当1 │ │ └─────────────────────────────────────────┘ │ │ │ │ 把X当作1可以圈出更大的圈，大大简化逻辑！ │ │ │ └─────────────────────────────────────────────────────────────┘

📝 本章小结

✅ 卡诺图化简要领 ┌─────────────────────────────────────────────────────────────┐ │ 【卡诺图结构】 │ │ - 2变量：2×2=4格 │ │ - 3变量：2×4=8格 │ │ - 4变量：4×4=16格 │ │ - 坐标遵循格雷码（相邻码只有1位不同） │ │ │ │ 【化简步骤】 │ │ 1. 填卡诺图（1表示存在，0表示不存在） │ │ 2. 圈1：边长为2ⁿ (1,2,4,8...)，圈尽可能大 │ │ 3. 读乘积项：圈内不变保留，变化消除 │ │ 4. 相或得到最终结果 │ │ │ │ 【重要技巧】 │ │ - 唯一圈优先 │ │ - 利用Don't Care条件 │ │ - 循环相邻：最左↔最右，顶行↔底行 │ │ - 圈可重叠 │ │ │ └─────────────────────────────────────────────────────────────┘