奎因-麦克拉斯基法：让化简可以交给计算机
更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」进阶层（intermediate）数字逻辑基础第二十六篇。布尔代数与卡诺图给了直观的图形化简法，但它依赖人眼、变量一多就失效。这一篇讲把同一原理算法化的经典方法——奎因-麦克拉斯基法。
本文要回答的问题
- 卡诺图好用，为什么变量一多（≥5）就不行了？
- Q-M 法怎么把「相邻两项消去一个变量」变成可列表执行的步骤？
- 什么是质蕴含、本质质蕴含？怎么用覆盖表选出最简与或式？
- 无关项（don't care）在列表法里怎么处理？
- 既然 Q-M 精确，为什么综合工具实际用 Espresso 之类的启发式？
一、卡诺图的边界
卡诺图靠「几何相邻 = 只差一个变量」让人眼圈组。但：①变量超过 4~5 个，格子和相邻关系画不清（5 变量要两张 4 变量图、6 变量几乎不可读）；②圈组是否最优靠经验，无法保证；③整个过程靠人，无法写成程序让 EDA 跑。而真实设计的函数动辄几十上百个变量。需要一套纯符号、可机械执行、且能保证最优的步骤，这就是 Q-M 列表法。它和卡诺图数学上完全等价——都是反复使用 AB + A B̄ = A 合并相邻最小项，只是一个用图、一个用表。
二、第一步：求全部质蕴含
质蕴含（prime implicant，PI）：不能再和别的项合并消变量的蕴含项（对应卡诺图里「不能再扩大的最大圈」）。Q-M 用逐级合并求它们。
(1) 列出最小项并按含 1 个数分组。 设要化简 F = Σm(0,1,2,5,6,7)（3 变量），把各最小项的二进制码写出来，按其中 1 的个数排序：
| 组(含1数) | 最小项 | 二进制 ABC |
|---|---|---|
| 0 | m0 | 000 |
| 1 | m1,m2 | 001,010 |
| 2 | m5,m6 | 101,110 |
| 3 | m7 | 111 |
(2) 只在相邻组之间逐项比较（含 1 数差 1 才可能只差一位）。两项若恰有一位不同就合并，消去该位用「−」标记，并给参与合并的两项打勾（它们已不是质蕴含，被更大的项吸收）：
m0(000)+m1(001) → 00- （消去 C，= ĀB̄）
m0(000)+m2(010) → 0-0 （消去 B，= ĀC̄）
m1(001)+m5(101) → -01 （消去 A，= B̄C）
m2(010)+m6(110) → -10 （消去 A，= BC̄）
m5(101)+m7(111) → 1-1 （消去 B，= AC）
m6(110)+m7(111) → 11- （消去 C，= AB）(3) 对新产生的带「−」项再做一遍同样的相邻组比较，能合并继续打勾、消去更多变量，直到某一列里再没有两项可合并。本例第二轮合并不出新东西。最终所有没被打勾的项就是质蕴含。这里得到 ĀB̄, ĀC̄, B̄C, BC̄, AC, AB 六个 PI（随函数不同，部分会在第二轮继续合并）。
要点：「−」在比较时当作固定位置，两项的「−」必须落在相同位置才允许合并；每合并一次项数翻倍（蕴含的最小项数 ×2）、文字数减 1，这与卡诺图圈从 1 格→2 格→4 格一一对应。
三、第二步：用质蕴含表选最小覆盖
质蕴含通常有冗余，要选一个最小集合覆盖函数所有最小项。建一张覆盖表：行是质蕴含，列是函数最小项，该 PI 覆盖该最小项就在交叉处打 ×：
| 质蕴含 | 覆盖的最小项 | m0 | m1 | m2 | m5 | m6 | m7 |
|---|---|---|---|---|---|---|---|
| P1=ĀB̄ (00-) | 0,1 | × | × | ||||
| P2=ĀC̄ (0-0) | 0,2 | × | × | ||||
| P3=B̄C (-01) | 1,5 | × | × | ||||
| P4=BC̄ (-10) | 2,6 | × | × | ||||
| P5=AC (1-1) | 5,7 | × | × | ||||
| P6=AB (11-) | 6,7 | × | × |
然后按三条规则化简：
- 本质质蕴含（essential prime implicant, EPI）：若某列（最小项）只被唯一一个 PI 覆盖，则该 PI 必选。例中 m0 只被 P1、P2 覆盖……逐个找「独占列」，被独占的 PI 无条件选入，连同它覆盖的列一起划掉。
- 行支配（dominance）：若 PIᵢ 覆盖的列包含 PIⱼ 的全部列且代价不更高，则 j 被支配、可删（i 干得更多）。
- 列支配：对偶地消去被支配列。
- 反复套用直到没有可消；若仍剩未覆盖列（形成循环表/cyclic），说明存在多个等价最优解，任选一个 PI 分支求解、再比较代价取最小（这步可能指数展开）。
本例选 P1（盖 0,1）后，m0、m1 已盖；m2 需 P2 或 P4，m5 需 P3 或 P5，m6 需 P4 或 P6，m7 需 P5 或 P6。可找到一个最简解 F = ĀB̄ + BC̄ + AC（3 项、6 文字），与卡诺图结果一致。「代价」通常按「项数（门数）+ 文字数（门输入数）」算。
四、无关项怎么进来
卡诺图里的 don't care（不可能出现或不关心的输入）在 Q-M 里分两处处理：①第一阶段求质蕴含时，无关项当作普通最小项参与合并（借它们可以消去更多变量、得到更大的组）；②第二阶段覆盖表里，不为无关项建列——即最终只需覆盖真正的函数最小项，无关项「可用但不必盖」。这与卡诺图「X 可圈可不圈，有利才圈」完全同义。
五、精确性与代价：为什么工具用 Espresso
Q-M 保证找到全局最简两级与或式，但它的中间项数随输入变量数指数增长（最坏情况质蕴含本身就有 3ⁿ/n 量级），几十个变量的实际函数根本跑不动。因此工业逻辑最小化（如经典 Espresso、现代综合器的 optimize 阶段）改用启发式：不枚举全部质蕴含，而是反复做「展开（expand）→ 冗余移除（irredundant）→ 收缩（reduce）」的迭代，在多值/共享逻辑层面快速逼近最小，虽不数学保证全局最优，但对百万门级设计足够好。理解 Q-M 的价值不在手算大函数，而在于：①建立「逻辑优化 = 产生候选蕴含 + 解覆盖问题」的精确框架，这正是综合工具内部语言；②看懂 EPI/PI/最小覆盖这些术语；③明白两级最小化（积之和 SOP）只是起点，真实优化还要考虑多级逻辑、共享、单元库中实际有的门和延迟（见 RTL 到门电路、综合是什么）。
与现有篇目的衔接
- 直接前置：布尔代数与卡诺图（相邻合并、无关项）
- 工具视角：RTL 到门电路、综合是什么
- 化简对象的描述：组合与时序逻辑
- 相关：MUX/LUT 实现任意函数（不化简也能实现，但优化省资源）
总结
一句话总结：卡诺图靠几何相邻让人眼圈组，变量超过 4~5 个就不可读、依赖经验且无法自动化，Q-M 列表法把完全相同的合并原理 AB+A B̄=A 变成可机械执行、保证最优的算法：第一步把最小项写成二进制并按含 1 的个数分组，只在相邻组间逐项比较，恰差一位就合并、用「−」标记消去位并给原项打勾，对新项反复迭代直到无可合并，所有未打勾的项即质蕴含（对应最大的、不能再扩的卡诺圈）；第二步建质蕴含覆盖表（行=质蕴含、列=最小项），用本质质蕴含（独占某列者必选）、行支配、列支配三条规则反复化简，剩余循环表则分支取最小代价解，得到项数与文字数最少的与或式；无关项在求质蕴含阶段当普通项参与合并、但在覆盖阶段不必被覆盖，等价于卡诺图里有利才圈的 X。Q-M 数学上与卡诺图等价且保证两级 SOP 全局最简，但中间项随变量指数增长，无法应对真实大函数，故工业逻辑最小化用 Espresso 一类「展开—去冗余—收缩」启发式快速逼近最优；学它的意义是建立「逻辑优化 = 产生候选蕴含 + 解覆盖问题」的框架、读懂 EPI/PI 术语，并理解最小化之后还要做多级逻辑、资源共享和库单元/延迟层面的综合优化。