卡诺图：把逻辑化简变成圈格子游戏 • Rufus' ink

AI 速读

卡诺图原理与圈组规则：格雷码排布、环绕相邻、无关项利用，三个实例逐步演示。

前一篇把布尔代数的定律推了一遍，这一篇讲它们的图形版——卡诺图。

卡诺图是什么#

卡诺图（Karnaugh Map，K-map）是 1953 年由美国工程师莫里斯·卡诺提出的用图形化简布尔表达式的工具。它的本质，是把真值表重新排列成一张二维表格，让「相邻」的格子之间只差一个变量，从而直观地看出哪些项可以合并、消掉哪些变量。

在《图灵完备》里，关卡经常给你一张真值表，让你用尽量少的逻辑门搭出电路。直接照真值表「抄」出来的电路往往又笨又费门。比如这个表达式：

F = A \cdot B \cdot C + A \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C + A \cdot \overline{B} \cdot \overline{C}

四个乘积项看着吓人，用卡诺图一画就能发现，它其实就是 $F = A$ ——门数量从好几个直接砍到 0，导线直连就行。这就是化简的价值。

卡诺图化简的目标形式是与或式（SOP）：若干个乘积项相或。这也是游戏里元件拼装最常用的形式。

原理：相邻等于可以合并#

卡诺图的理论基础是布尔代数里的这条恒等式：

A \cdot B + A \cdot \overline{B} = A \cdot (B + \overline{B}) = A

如果两个乘积项只有一个变量不同，就能合并，把那个变量消掉。卡诺图把真值表按格雷码排布，保证相邻格子恰好只差一个变量——于是只要看到相邻的 1，就能合并。这就是卡诺图的全部原理。

格雷码（Gray Code）#

格雷码是一种特殊的二进制编码，相邻两个数之间只差 1 位：

十进制   普通二进制   格雷码
0        00          00
1        01          01
2        10          11
3        11          10

text

注意格雷码的 01 → 11 和 11 → 10，每一步都只翻转一位。所以竖着看是 00、01、11、10，而不是 00、01、10、11。

变量越多，图越大#

以 2 变量为例，行和列都按格雷码排， $m$ 后面的数字叫最小项编号（把各变量取值拼成二进制转十进制，如 3 变量下 $ABC = 101 \rightarrow m_5$ ）：

$A$ \ $B$	0	1
0	$m_0$	$m_1$
1	$m_2$	$m_3$

3 变量：行放 $A$ ，列放 $BC$ （格雷码 00、01、11、10）：

$A$ \ $BC$	00	01	11	10
0	$m_0$	$m_1$	$m_3$	$m_2$
1	$m_4$	$m_5$	$m_7$	$m_6$

4 变量：行放 $AB$ ，列放 $CD$ ：

$AB$ \ $CD$	00	01	11	10
00	$m_0$	$m_1$	$m_3$	$m_2$
01	$m_4$	$m_5$	$m_7$	$m_6$
11	$m_{12}$	$m_{13}$	$m_{15}$	$m_{14}$
10	$m_8$	$m_9$	$m_{11}$	$m_{10}$

圈组规则#

拿到真值表后，把输出为 1 的格子标 1，其余标 0，然后开始圈 1。规则五条：

只能圈矩形，格子数必须是 2 的幂（1、2、4、8、16…）；
相邻是循环的：最左和最右相邻、最上和最下相邻，四个角也互相相邻，因为格雷码首尾同样只差一位；
圈越大越好：先圈尽可能大的组，圈越大，消掉的变量越多，结果越简单；
可以重叠：同一个 1 可以同时属于多个圈，因为 $X + X = X$ ，多圈一次不改变逻辑；
只圈 1（和 $X$ ）：圈内不能有任何 0。

圈完之后，每个圈里「保持不变」的变量组成一个乘积项，所有圈的乘积项相或，就是最简表达式。

怎么看圈里的乘积项：圈内变化的变量被消掉，不变的变量留下。变量取值为 1 写原形（ $A$ ），取值为 0 写反形（ $\overline{A}$ ）。

三个实例#

实例一：三变量常规圈组#

$F(A,B,C) = \sum m(0,1,4,5)$ ，即 $m_0, m_1, m_4, m_5$ 输出 1：

$A$ \ $BC$	00	01	11	10
0	1	1	0	0
1	1	1	0	0

四个 1 组成一个 2×2 的圈，覆盖 $BC$ 取 00 和 01 两列。圈内逐个看变量：

$A$ 在变化 → 消掉
$B$ 恒为 0 → 留下 $\overline{B}$
$C$ 在变化 → 消掉

得到 $F = \overline{B}$ 。验证： $m_0, m_1, m_4, m_5$ 里 $B$ 确实都是 0。

实例二：四角环绕#

$F(A,B,C,D) = \sum m(0,2,8,10)$ ，四个 1 恰好落在 4 变量卡诺图的四个角：

$AB$ \ $CD$	00	10
00	1	1
01	0	0
11	0	0
10	1	1

四角虽然「离得远」，但格雷码首尾相连，它们实际相邻，能圈成一组。圈内 $B$ 恒为 0、 $D$ 恒为 0， $A$ 和 $C$ 变化，得到 $F = \overline{B} \cdot \overline{D}$ 。

如果不知道环绕规则，你可能会写出 $\overline{A}\,\overline{B}\,\overline{D} + A\,\overline{B}\,\overline{D}$ 两项，白白多花一个门。

实例三：无关项（Don’t Care）#

有些输入组合根本不会出现，或者出现时输出 0 还是 1 都无所谓，记作 $X$ 。圈组时可以把 $X$ 当成 1 来用，帮我们凑出更大的圈；不想用的时候它就是 0，不碍事。

例如 $m_0, m_1$ 为 1， $m_4, m_5$ 是无关项，其余为 0：

$AB$ \ $CD$	00	01
00	1	1
01	$X$	$X$
11	0	0
10	0	0

不用 $X$ ：只能圈出 $m_0, m_1$ 两个 1，得到 $F = \overline{A} \cdot \overline{B} \cdot \overline{C}$ （3 个变量）；
把 $X$ 当 1：圈成一个 2×2 大方块，消掉 $B$ 和 $D$ ，得到 $F = \overline{A} \cdot \overline{C}$ （2 个变量）。

少一个变量，在游戏里往往就意味着少一两个门。

局限与实战技巧#

5 个及以上变量：表格开始「立体化」，人肉圈组容易看花眼，这时改用奎因-麦克拉斯基算法（Quine-McCluskey）或直接交给软件化简；
最简表达式不等于最省门：卡诺图给的是最简与或式，但《图灵完备》里有些关卡用 NAND/NOR 反而更省——一个与非门就顶「与 + 非」两个门。

游戏里的实用套路：先用卡诺图化简，再把手头的门类型换算成实际成本，最后比一比哪种方案最划算。

至此，《图灵完备》第一阶段的笔记完结：从认识逻辑门，到与非门的万能性，再到布尔代数与卡诺图化简。接下来就可以进游戏，从一颗 NAND 开始搭加法器了。