布尔代数与逻辑化简：从定律到卡诺图

更新时间：2026-09-10。本文是「集成电路大类 · 芯片设计」**入门层（beginner）**数字逻辑基础第三篇。建议先读 逻辑门与晶体管直觉。

本文要回答的问题

• 布尔代数有哪些基本定律？德摩根律怎么把"与/非"和"或/非"互相改写？
• 最小项、最大项、SOP（积之和）与 POS（和之积）标准式是什么？
• 卡诺图为什么"圈相邻的 1"就能消变量？怎么圈才最优、怎么用无关项？
• 五变量以上怎么办，为什么真实设计不再手画卡诺图？
• 工程师学化简的真正用处是什么？和"写出可综合 RTL"如何对应？

一、布尔代数基本定律

变量取值只有 0/1，·（与，可省略）、+（或）、上划线（非）。除了类似普通代数的交换律 A+B=B+A、结合律、分配律，几条布尔特有的定律最常用：

定律	形式
0-1 律	A+0=A，A·1=A；A+1=1，A·0=0
互补律	A+Ā=1，A·Ā=0
重叠律	A+A=A，A·A=A
还原律	Ā̄=A
吸收律	A+AB=A；A+ĀB=A+B
合并律	AB+AB̄=A（提公因子后 B+B̄=1）
德摩根律	¬(A·B)=Ā+B̄；¬(A+B)=Ā·B̄

德摩根律是数字逻辑里最重要的一条恒等式，记住口诀"切反号、变与或"：与/或整体取反，等于各变量分别取反后把与或互换。它解释了为什么 NAND/NOR 是通用门、为什么低有效使能那么常见（见 逻辑门与 CMOS），也是 RTL 里改写条件时的常用工具，例如：

!(a && b)   ≡   (!a) || (!b)
!(a || b)   ≡   (!a) && (!b)

Verilog 里把一长串 &&/|| 的取反条件写错（忘了给每一项都取反）是高频 review 缺陷。

二、最小项/最大项与标准式

给定 n 个变量，一个最小项（minterm）是包含全部 n 个变量（原变量或反变量各出现一次）的与项，它在真值表里恰有一行使输出为 1，记作 mᵢ（i 是把原变量当 1、反变量当 0 读出的二进制编号）。例如三变量函数在 ABC=101 时为 1，对应最小项 m₅ = AB̄C。

把所有使输出为 1 的最小项或起来，就得到该函数唯一的积之和标准式 SOP（Sum of Products）：

F(A,B,C) = Σ m(1,3,5)   // 第 1、3、5 行为 1，其余为 0

对偶地，最大项（maxterm）Mᵢ是包含全部变量的或项，恰在第 i 行使输出为 0；把使输出为 0 的最大项与起来得和之积标准式 POS：F = Π M(0,2,4,6,7)。SOP 和 POS 描述同一个真值表，一个按"为 1 的行"、一个按"为 0 的行"组织。标准式的价值是唯一、可机械对照真值表，是化简的起点。

三、卡诺图：用几何相邻消变量

同一个函数，F = AB̄C + ABC 和 F = AC 等价（两项只差一个变量 B，用合并律消掉），但后者门更少。卡诺图（Karnaugh map, K-map）把真值表重新排成二维网格，让"只差一个变量"的最小项在几何上相邻，于是"圈相邻的 1"就等于自动做合并：

• 圈必须是 2ᵏ 个相邻的 1（1、2、4、8… 个），且网格上下、左右边缘也相邻（卷成环面）。
• 每圈一个 2ᵏ 大小的矩形，就消掉 k 个在圈内发生变化的变量，留下圈内取值不变的变量组成一个乘积项。
• 圈越大，消掉的变量越多，乘积项越短。

以四变量为例（AB 为行、CD 为列，行列均按格雷码 00,01,11,10 排列，保证相邻只差 1 位）：

        CD=00  01  11  10
AB=00  [ 0   1   1   0 ]
AB=01  [ 0   1   1   0 ]
AB=11  [ 0   0   0   0 ]
AB=10  [ 0   0   0   0 ]

中间 4 个 1 圈成 2×2 → A 在圈内恒为 0（取 Ā），D 在变、B 在变，
C 在 01/11 两列恒为 1 → F = Ā·C（两项变量 B、D 全消掉）。

圈法求最优的规则：先找本质质蕴含项（essential prime implicant）——某个 1 只被一个圈覆盖时，那个圈必选；再用尽量少、尽量大的圈覆盖其余所有 1。目标是"乘积项数最少 + 每项变量数最少"（两级 AND-OR 实现时即门数、输入数最少）。

四、无关项（don't care）

某些输入组合在系统里永远不会出现（如 BCD 码的 1010~1111），或出现了输出取什么都无所谓，记为无关项 d（K-map 里画 ×）。化简时可自由选择把某个 × 当 0 还是当 1，唯一目标是让圈更大、更少。善用无关项常能显著减少逻辑——这也是为什么 RTL 里 case 应写 default（见 组合与时序逻辑）：显式告诉综合器"未列输入怎么处理"，等于给了它优化自由；留空则可能逼出锁存器。

五、化简与冒险的伏笔（连接进阶）

卡诺图还能静态判断竞争冒险（hazard）：如果两个相邻的"1 格"分别由两个互不搭接的圈覆盖，那么输入在这两格之间切换、且其它路径延迟不一致时，输出可能瞬间出现一个不该有的毛刺（glitch）。把这两格再用一个冗余圈搭接起来即可消除。这一现象的成因与"冗余项 / 选通 / 打拍"三种消除手法，在进阶 组合逻辑竞争与冒险 里展开。

六、完整走查：从需求到最简电路

把前面的工具串成一条完整流水线。需求：设计一个"一位十进制数是否落在合法区间 2~7"的判断电路（BCD 输入 DCBA，D 是 8 的位），合法输出 F=1。

第一步写真值表：0（0000）、1（0001）为 0；2~7（0010~0111）为 1；8、9（1000、1001）为 0；1010~1111 在 BCD 中不出现，记为无关项 ×。即 F = Σm(2,3,4,5,6,7) + Σd(10,11,12,13,14,15)。

第二步画四变量卡诺图（行 DC，列 BA，均按格雷码）：

        BA=00  01  11  10
DC=00   [ 0   0   1   1 ]   数值 0,1,3,2
DC=01   [ 1   1   1   1 ]   数值 4,5,7,6
DC=11   [ ×   ×   ×   × ]   12..15（无关）
DC=10   [ 0   0   ×   × ]   8,9 为 0；10,11 无关

第三步圈：中间一行 4 个 1 直接成圈，得 C̄·... 与相邻无关项合并——把 DC=11 那 4 个 × 当 1，可与 DC=01 行圈成 2×4 的大方块，D 在这两行一为 1 一为 0 被消掉，留下 C=1 一个变量！再补左下角：DCBA=0100,0101 已被覆盖，检查 m2,m3（右上两格）与 m6,m7 同处 BA=11/10、DC=00/01 的 2×2 圈，得 B·C̄。最终 F = C + B·C̄ = C + B（再用吸收律 C + C̄B = C + B）。

结论：这个"2~7 判断"只要 F = B + C（即输入的 4 位、2 位任一位为 1 且数字 ≤ 7，由 D=0 被无关项化简吸收）。8 个最小项的逻辑被化到两个变量的一个或门，这就是极小化的威力；而敢于把 6 个非法码当无关项，是面积大减的关键——前提是你确信系统真的不会喂进非法输入，否则应把 × 当 0 以策安全。

七、五个变量以上：Quine–McCluskey 与为什么放弃手算

卡诺图靠人眼识别相邻，四变量已是舒适区上限，五变量要叠两张图找"跨层相邻"、六变量基本不可行。Quine–McCluskey（Q-M，列表化简法）把这件事变成可机械执行的算法：① 把为 1 的最小项按含 1 的个数分组；② 反复比较、合并"仅差一位"的两项（消去该位，用 - 标记），直到不能再合并，得到全部质蕴含项；③ 建立"质蕴含项—最小项"覆盖表，先用本质质蕴含项、再求最少覆盖（这一步本质是集合覆盖，是 NP 难的）。

Q-M 的价值不在让人算得更快，而在于：它揭示了化简的真正难点不是"合并相邻项"（那步很机械），而是"如何在指数多的质蕴含项里挑出最小覆盖"。真实函数有几十上百个输入，连显式列出真值表都不可能（n 输入有 2ⁿ 行），工具改用隐式表示：

• BDD（二元决策图）：把布尔函数表示成带共享的有向无环图，变量排序合理时规模远小于真值表，便于做等价性检查（LEC）；
• AIG/SAT（与非图、布尔可满足性）：综合与验证的现代底座，优化和"两个电路是否等价"都转成 SAT 求解；
• 多级逻辑综合：不追求两级 SOP 的"字面最简"，而是提取公因子、复用中间节点（factoring / kernel），在真实门延迟与面积上更优。

理解这一层，你就明白为什么"我手工把表达式化简得很巧"在工程里价值有限——综合器在多变量、多级、带具体工艺延迟的规模上远超人力，人该负责的是表达意图与约束。

八、POS 与卡诺图圈 0：什么时候该圈 0

大多数教程只讲圈 1 得 SOP（与-或），但对称地圈 0 可以直接得 POS（或-与）。当函数输出里 0 很少、1 很多时，圈 0 更省：

• 圈 0 读出的是 F̄ 的 SOP，再整体取反、用德摩根律展开，即得 F 的"和之积" F = Π(...)；
• 读圈规则相反：圈内某变量恒为 0 就写原变量、恒为 1 写反变量（因为你读的是"使输出为 0"的条件）。

例如"多数表决"函数（三输入两票及以上赞成）有 4 个 1、4 个 0，两种圈法相当；但某些控制信号（如"仅在极少数组合下关断"的使能）0 格稀疏，圈 0 得 POS 门数更少。物理实现上，SOP 对应 AND 接 OR（NAND-NAND 两层即可实现），POS 对应 OR 接 AND（NOR-NOR）；由于 CMOS 里 NAND/NOR 比 AND/OR 更原生，两种标准式最终都能落到两层通用门上。综合器会根据函数形态和库里 cell 自动选边，你只需知道"1 多圈 0、0 多圈 1"这条直觉。

九、布尔恒等式在 RTL review 里的高频用法

学定律的实际回报集中在 code review 和调试，而不是纸面化简：

1. 德摩根拆条件：if (!(en && ready)) 与 if (!en || !ready) 等价，写"等待条件"时一种形式更容易看懂，可大胆互换；但漏改一边（只反 en 不反 ready、或忘了 &&→||）是真实缺陷高发点。
2. 消冗余判断：if (a && b || a && !b) 可化为 if (a)；(x==A) ? 1 : (x!=A ? 0 : ...) 这类手写嵌套常含可消项，也常是 priority-case 误写的信号。
3. 异或的切换作用：Y = A ⊕ inv，inv=0 时 Y=A、inv=1 时 Y=Ā——一个 XOR 就是"可选反相器"，加减法器里 B 端取反、可配置极性、CRC/LFSR 全靠它（见 加法器、计数器与移位寄存器）。
4. 公式改写影响时序：A·B + A·C = A·(B+C) 表面等价，但前者是两个与门并联、后者先或再与，关键路径和可共享程度不同；宽与项拆成"先平衡成树"能降延迟，这类改写要交给综合器但要看得懂它做了什么。
5. XOR 与"奇偶"：n 个信号 XOR 即奇偶性，级联成树做奇偶校验/校验位生成，天然对应 LFSR 与 CRC（见 数制与编码）。

一条经验：凡是你靠"想一下才敢确信等价"的布尔改写，都值得在 review 时显式注明依据的定律，既防自己写错，也方便后续做 LEC/形式验证时对照。

十、多级逻辑与公因子提取：为什么最简 SOP 不一定最优

卡诺图给出的最简是针对两级 AND-OR 结构的最优（第一级与门、第二级或门），但真实电路允许多级，提取公共子表达式往往比最简 SOP 还省。经典例子是全加器进位链之外的一个函数：

F = AB + AC + AD + AE + ...          （两级：很多 2 输入与门 + 一个大或门）
F = A(B + C + D + E + ...)           （提公因子 A：一个大或门 + 一个与门）

两级形式要 k 个与门，提因子后只要 1 个与门（共享了"A 为 1"这个条件）。这就是因子化（factoring）：允许"先或后与再或"的多级结构，用更少的门、更小的扇入实现同一函数，代价是逻辑层级可能增加（延迟换面积）。对偶还有"除法式"分解（decomposition）和"代回公共节点"的提取（extraction）：

• 若两个输出函数 F₁=AB+AC、F₂=DE+DC 共享结构，可抽出公共因子 X=...，或识别出二者都含"A/D 与一组括号"的形态让综合器共享内部节点；
• **核（kernel）**理论用来系统地找这种可共享的子表达式，是 SIS/ABC 一类学术综合工具和商用综合器的核心算法之一。

关键直觉：优化目标不是"字面门最少"，而是在具体工艺库上面积、延迟、功耗的综合最优。一个抽象上更简的两级式，可能因为需要一个 8 输入或门（库里没有，要拆树）反而更慢更大；多级式虽然层数多，却全是 2 输入门、还能和相邻逻辑共享。所以综合器内部会先做技术无关的多级优化（factoring/kernel），再做技术相关的工艺映射（mapping）——把抽象节点网络"盖"到库中真实 cell（NAND/AOI/DFF）上，映射时连一个 AOI 复合门能替代几个分立门都在计算之内。

十一、约束与 don't care：除了输入不会出现，还有"输出怎么都行"

前面第四节把无关项理解成"不会出现的输入组合"，工程上无关项有更丰富的来源，善用它们等于给综合器让出优化空间：

1. 外部无关项（输入不可能）：BCD 的 1010~1111、一段编码里未分配的操作码、一个 FSM 不可达状态下的输入——这些组合永不到达。
2. 可观察无关项（输出不被使用）：在某些输入下，该输出不会被任何后续逻辑采样（例如某条 select 信号决定这个值根本不被选中），那么这一拍算成什么都无所谓。
3. 时序无关（多周期/路径豁免）：某些路径不需要在一个周期内稳定（multicycle path），约束上放宽后综合器不必为它花面积。

RTL 层面表达这些"自由"的方式：case 写 default（哪怕 default 里随便给值，也比留空逼出 latch 强）、明确标注不可达状态的处理、在 SDC 里写 set_false_path/set_multicycle_path（见 SDC 约束实战）。反模式是把所有输入都当成可能、把所有输出都当成关键——逻辑会为永不到达的情况付出真实的门和面积。当然这种"自由"必须建立在对系统契约的确信上：一旦上游真的喂来"不可能"的输入（协议违例、软错误），基于无关项优化的电路会产生未定义行为，安全攸关模块反而会显式覆盖全部输入并报错。

十二、工程视角：今天为什么交给综合器

手画卡诺图只适合 2~4 个变量；5 个变量的图就需要两个 4 变量图叠放、相邻关系难辨，真实 RTL 一个函数动辄几十上百个输入，根本不可能手算。逻辑综合工具用更系统的算法完成等价工作（见 逻辑综合入门、逻辑综合）：

• 多维表示与极小化：类似 Quine–McCluskey 的精确法、二进制决策图（BDD）、布尔可满足性（SAT）等；
• 因子化（factoring）：多级逻辑共享公共子表达式，比单纯两级 SOP 面积更小；
• 工艺映射（technology mapping）：不是追求抽象"最少门"，而是映射到具体工艺库的 NAND/AOI/DFF 等真实 cell，综合考虑每个 cell 的延迟、面积、驱动强度；
• 还在时序、面积、功耗多目标间权衡，甚至为满足关键路径时序而有意增加面积。

所以工程师学化简不是为了和工具比快，而是为了：① 建立"逻辑可被等价极小化"的直觉，看得懂综合日志里 optimized/mapped 后面积为何下降；② code review 时能判断两段布尔表达式是否等价、德摩根改写是否改变了逻辑；③ 知道写清晰、直白、可综合、无锁存器的 RTL 比手写"省门技巧"更重要——把意图表达清楚，让综合器在完整的工艺与约束信息下做它擅长的全局优化（见 可综合 RTL 编码规范）。

十三、综合器内部：从与或图到技术映射，手算今天还有什么用

既然化简都交给工具，理解它内部的处理链条仍然重要，因为工具的"性格"决定了你写 RTL 的方式。一次典型综合分四层：

1. 编译与展平（elaboration）：把 always/case/运算符翻译成一张通用布尔网表，先做语言层面的优化，比如常量传播（x & 1'b0 直接接地）、死代码消除、相同子表达式共享。你在 RTL 里多写的冗余判断，大部分在这一层就消失了，所以不必为了"省逻辑"把代码写得晦涩。
2. 与无环图（AIG）上的逻辑优化：所有逻辑被归一化为"两输入与 + 反相器"的图，工具在图上做局部改写（rewrite/refactor）、跨层级重构成平衡树、用 SAT 方法证明两个节点功能等价后合并（SAT sweeping）、传播和利用无关项。多输出共享是它相对手画卡诺图的最大优势——人工化简各输出各自为战，工具能让多个输出共用同一中间项。
3. 技术映射（technology mapping）：把通用模式匹配到具体库单元（NAND/NOR/复合门/AOI/OAI/MUX），在 DAG 上做"模式覆盖"求面积或延迟最优；这一步才出现 X1/X2 之类的真实门。
4. 物理驱动的再优化：结合布局布线后的真实线载、单元位置做缓冲插入、尺寸调整、门控时钟聚合，甚至局部重映射。线延迟在先进工艺占主导后，这一步对最终频率的影响往往超过前面的布尔优化。

明白这条链条后，"手算卡诺图/布尔律"的价值就清楚了：它不是为了和工具抢工作，而是为了建立三样东西——判断 RTL 会被映射成大概多少硬件的直觉（看到多层嵌套 case 能想到级联 MUX 多深、关键路径在哪）；理解哪些事情工具不敢替你做（跨时钟域加同步器、把组合译码改成格雷计数、识别该寄存的控制输出，这些涉及设计意图的结构性变换必须人来决定）；以及在 review、面试和波形调试时有共同语言。工具负责算得快，人负责选对结构。

留三道自测，能流畅答出就算本篇过关：①用四变量卡诺图化简一个带三个无关项的函数，并指出哪些无关项不该圈；②给一个 SOP 表达式找出全部静态 1 冒险并写冗余项（答案见 竞争与冒险）；③说明为什么同样功能的两段 case，一个综合出并行 MUX、一个综合出优先级链，对应语句和编码该怎么写（提示：分支是否互斥、是否写 default）。

十四、把一篇 RTL 的组合逻辑"读薄"：面试与 review 的推演法

最后给一个可以反复使用的实战动作：面对一段不熟悉的组合逻辑，怎么快速确认它对不对、简不简、险不险。分四步。

第一步，列输入输出和每个输出的真值表骨架：输入不超过 4 个就直接画卡诺图（输入多就抓关键控制位，把数据位整体当一路）。这一步强迫你回答"每个最小项到底有没有定义"——多数 bug 都藏在没人想过的输入组合里。第二步，把 RTL 表达式展开成与或形式：if/case 先翻译成"每个输出在哪些条件下为 1"的条件和（条件就是乘积项），再和卡诺图的圈对照。若 RTL 的乘积项比最简式多，别急着判冗余——多出来的项可能是为冒险搭接的冗余项（见 竞争与冒险）、为跨模块预留的使能、或是综合器会自动消掉的保守写法；但如果多出来的项覆盖了不该为 1 的格子，那就是功能错误。第三步，查相邻 1 格是否都有公共项：这一遍同时回答最简性和静态冒险两个问题。第四步，看无关项的处理是否写明意图：综合属性、default、casez 通配三处的 don't care 要能在需求里找到依据，而不是"顺手不关心"。

面试里"用最少的门实现函数""判断这个电路有没有毛刺""化简并说明竞争冒险"是同一类题的三种问法，全部用上面四步走。工程里真正的差别只是：手算换成让工具算，但列真值表骨架、确认每个输入组合有定义、区分冗余是为面积还是为冒险这三件事，工具不会替你负责。带着这套眼光再回头读自己写的译码器、仲裁器、ALU 控制逻辑，你会明显感觉到"看代码"变成了"看电路"。

与现有篇目的衔接

• 前置：逻辑门与晶体管直觉
• 下一篇：编码器、译码器与多路选择器
• 工程承接：从代码到门电路、逻辑综合入门、可综合 RTL 编码规范
• 化简不当的物理后果：进阶 组合逻辑竞争与冒险、静态时序分析入门

总结

一句话总结：布尔代数是拼装与化简逻辑的数学，除交换/结合/分配律外，最常用的是吸收律、合并律和"切反号、变与或"的德摩根律（它同时解释了通用门、低有效逻辑和取反条件的改写）；任何真值表都能唯一地写成按"为 1 行"组织的最小项之或（SOP）或按"为 0 行"组织的最大项之与（POS）；卡诺图把"只差一个变量"的最小项排成几何相邻，圈 2ᵏ 个相邻的 1 就消掉 k 个变量，圈越大越简、先选本质质蕴含项再求最少覆盖，无关项 × 可视需要当 0/1 以扩大圈；相邻 1 若被互不搭接的圈覆盖会埋下竞争冒险；而五变量以上和真实设计无法手算，逻辑极小化、因子化与工艺映射都由综合器完成——工程师学化简是为建立等价直觉、看懂综合结果、写出清晰可综合的 RTL，而不是手工和工具比省门。