学习 › 第 5 讲
奎因-麦克拉斯基（Quine-McCluskey）法分步详解
阅读约 7 分钟 · bitGateLab 团队
卡诺图处理四个变量很快，但它依赖你的眼力，变量达到五个或更多时就不再实用。奎因-麦克拉斯基法用表格和机械的规则完成同样的工作：它不需要直觉，总能找出全部质蕴含项，也是逻辑函数化简程序的基础。本文将带你理解它的两个阶段，学会识别必要质蕴含项，并完整地做一道四变量例题。
术语：蕴含项与质蕴含项
- F 的蕴含项是这样一个乘积项：只要它为 1，就能保证 F 为 1。F 的每个最小项都是蕴含项，卡诺图上任何一个合法的圈也是蕴含项。
- 质蕴含项是不能再扩大的蕴含项；如果再去掉它的一个变量，它就会盖住某个 F 为 0 的行。它相当于卡诺图上的一个最大圈。
- 必要质蕴含项是这样的质蕴含项：它至少覆盖了一个其他质蕴含项都没有覆盖的最小项。它必定出现在任何一个最简解中。
这种方法分两个阶段：首先通过合并各项找出全部质蕴含项；然后选出能覆盖所有最小项的、数量最少的一组质蕴含项。
第 1 阶段：合并各项
每一项都用二进制写出，被消去的变量所在的位置用一条短横线标记。例如，变量为 A、B、C、D 时，0-11 这一项表示 ACD（B 已被消去）。
- 按二进制代码中 1 的个数把最小项分组。
- 把一组中的每一项与下一组中的每一项逐一比较。如果它们只有一位不同，就把它们合并，在那一位上写短横线，并把原来的两项标记为“已使用”。
- 对新得到的列表重复上述过程。只有短横线位置完全相同的项才能合并。
- 当再也无法合并时，那些始终没有被标记的项就是质蕴含项。
第 2 阶段：质蕴含项表
列一张表，每个质蕴含项占一行，函数的每个最小项占一列（无关项不设列）。在表中标出每个质蕴含项覆盖了哪些最小项。然后：
- 找出只有一个标记的列。该标记所在行的质蕴含项是必要的：选中它，并划去它覆盖的所有列。
- 对剩下的列，选出数量最少、能把它们全部覆盖的质蕴含项。如果两个质蕴含项覆盖的列相同，选哪个都行；优先选文字较少的那个。
完整例题。化简 F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15)。
第 1 步：按 1 的个数分组。
| 1 的个数 | 最小项 |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
第 2 步：第一次合并（两两成对）。比较相邻的组。8 不能与 3 或 5 合并，因为它们相差不止一位。
| 组 | 得到的对 |
|---|---|
| 0 和 1 | (0,2) 00-0; (0,8) -000 |
| 1 和 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2 和 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3 和 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
十个最小项全都被标记为已使用；共得到 13 对。
第 3 步：第二次合并（四项一组）。把短横线位置相同且只有一位不同的对合并起来：
- (0,2) 与 (8,10)，或者 (0,8) 与 (2,10)：-0-0，覆盖 0、2、8、10。
- (2,3) 与 (10,11)，或者 (2,10) 与 (3,11)：-01-，覆盖 2、3、10、11。
- (3,7) 与 (11,15)，或者 (3,11) 与 (7,15)：--11，覆盖 3、7、11、15。
- (5,7) 与 (13,15)，或者 (5,13) 与 (7,15)：-1-1，覆盖 5、7、13、15。
13 对都在某个四项组中用到了。这四个四项组彼此之间不能再合并（没有哪两个短横线位置相同且只有一位不同）。因此，质蕴含项为：
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
第 4 步：覆盖表。
| 质蕴含项 | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
第 5 步：必要质蕴含项。第 0 列和第 8 列只在 P1 行有标记，所以 P1 是必要的。第 5 列和第 13 列只在 P4 行有标记，所以 P4 也是必要的。两者合起来覆盖了 0、2、5、7、8、10、13 和 15。
第 6 步：覆盖剩余部分。还剩最小项 3 和 11。P2 能同时覆盖这两个，P3 也能。两者中任选一个都能得到完整的解，文字数相同。
结果：F = BD + BD + BC，或者 F = BD + BD + CD。两者都是三项、六个文字。
如果把这个函数画在卡诺图上，P1 是四个角，P4 是中间的方块，P2 是 00 行和 10 行（通过边界相连）的 11、10 两列，P3 是整个 11 列。列表法不需要看图就得到了同样的结果。
无关项与循环表
无关项 X 在第 1 阶段被当作 1 一并纳入，因为它们可能有助于形成更大的蕴含项。在第 2 阶段则把它们略去：它们不设列，因为并不要求覆盖它们。完全由 X 构成的质蕴含项永远用不上。
有时，在选完必要质蕴含项之后，或者从一开始，每一列就都至少有两个标记，没有明显的办法做出选择。这种情况称为循环表。解决办法是试探：选一个质蕴含项，去掉它覆盖的列，然后重复，再比较得到的各个解。对于大的表，有一种代数方法（Petrick 法）可以列举出所有可能的覆盖。
常见错误
- 合并短横线位置不同的项，例如 0-01 与 00-1。即使它们看起来只差一位，这样做也是不合法的。
- 忘了把每次合并所用的两项标记为已使用，结果把不是质蕴含项的项列成了质蕴含项。
- 在覆盖表中为无关项 X 设列，这会迫使你毫无必要地去覆盖它们。
- 先选非必要的质蕴含项，后选必要的。应当先确定必要质蕴含项，再决定其余的。
- 从代码写出乘积项时出错：在 -0-1 中，B 取反（值为 0），D 不取反（值为 1），A 和 C 则消失。
在模拟器中试一试
模拟器正是用这一类方法来化简函数的，所以你可以用它来核对手算的每个阶段。
- 新建一个四变量真值表，把例题中的各个最小项标为 1。
- 在纸上完成第 1、2 阶段，写下你的结果。
- 观察工具给出的最简表达式及其卡诺图；找出每个质蕴含项对应的是哪个圈。
- 把两个可能的解都在同一画布上转换成电路，改变输入，确认它们的输出始终相同。
练习
- 求 F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15) 的质蕴含项和最简表达式。
答案
质蕴含项：-00-（BC）、-0-1（BD）和 --11（CD）。第 0 列只被 BC 覆盖，第 7 列只被 CD 覆盖：两者都是必要的，并且合起来覆盖了全部最小项。F = BC + CD。质蕴含项 BD 是多余的。
- 求解 F(A, B, C) = Σm(0, 1, 2, 5, 6, 7)。有必要质蕴含项吗？
答案
得到的对是 00-、0-0、-01、-10、1-1 和 11-，其中没有哪两对能合并成四项组：共有六个质蕴含项。每个最小项都恰好被两个质蕴含项覆盖，所以没有必要质蕴含项（循环表）。有两个最简解：AB + BC + AC，或 AC + BC + AB。
- 化简 F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15)。
答案
在第 1 阶段把 X 一并纳入，得到四个质蕴含项：-0-1（BD）、-01-（BC）、--11（CD）和 1--1（AD）。在表中（不为 1、10、15 设列）：2 只被 BC 覆盖，7 只被 CD 覆盖，13 只被 AD 覆盖。三者都是必要的，并且同时覆盖了 3、9 和 11。F = BC + CD + AD。
- 在第 1 阶段，为什么不拿含一个 1 的组去和含三个 1 的组比较？
答案
因为分别含一个 1 和三个 1 的两个代码至少有两位不同，而要合并必须恰好只有一位不同。