卡诺图（K-Map）——化简布尔表达式指南

卡诺图（Karnaugh map），也叫 K-map，是一种用来化简布尔表达式的网格工具，可以减少手工代数推导。你把真值表中的输出值填到网格里，将相邻的 $1$ 分组，然后为每一组写出一个更简单的项。

使用条件很重要：卡诺图最适合较小的函数，通常是两个、三个或四个变量。变量一多，图就会变得难以阅读，这时通常用其他方法更合适。

卡诺图表示的是什么

卡诺图包含的信息与真值表相同，但它不是按普通二进制顺序排列单元格，而是按格雷码顺序排列。这样的排列方式使得相邻单元格恰好只相差一个变量。

这种“只差一个变量”正是关键。如果两个相邻单元格都为 $1$，那么发生变化的那个变量就可以从化简后的项中消去。

分组如何消去变量

这个可视化规则来自布尔恒等式，例如

$$XY + X\overline{Y} = X$$

这两项只在 $Y$ 上不同，所以 $Y$ 被消去，保留下来的公共部分是 $X$。卡诺图让你可以直接在网格上看出这种消去模式。

卡诺图例题

设

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

这表示当最小项为 $1$、$3$、$4$、$5$ 和 $7$ 时，$F=1$。

对于一个 $3$ 变量卡诺图，用 $A$ 表示行，用 $BC$ 表示列，并按格雷码顺序 $00$、$01$、$11$、$10$ 排列：

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

先从最大的有效分组开始。中间两列的四个 $1$ 可以组成一组。在这四个单元格中，$C=1$ 保持不变，而 $A$ 和 $B$ 会变化，所以这一组可化简为

$$C$$

还有一个 $1$ 没有被覆盖：最小项 $4$，即 $(A,B,C)=(1,0,0)$。把它与相邻的最小项 $5$ 配对，后者是 $(1,0,1)$。

在这一对中，$A=1$ 和 $B=0$ 保持不变，而 $C$ 发生变化，所以这一对可化简为

$$A\overline{B}$$

因此，化简后的表达式是

$$F(A,B,C) = C + A\overline{B}$$

这个更短的表达式与原来的最小项列表是等价的。

有效卡诺图分组的规则

分组大小必须是 $2$ 的幂：$1$、$2$、$4$、$8$，依此类推。

尽量使用最大的有效分组。分组越大，通常能消去的变量越多。

要记住卡诺图是首尾相接的。左边缘与右边缘相邻，上边缘与下边缘相邻。

对角线上的单元格不相邻。

当重叠分组有助于形成更大或更简单的分组时，是允许重叠的。

卡诺图中的常见错误

使用普通二进制顺序

如果你把行或列标成 $00$、$01$、$10$、$11$，相邻关系就错了。卡诺图必须使用格雷码顺序，这样相邻单元格才只相差一位。

分成三个单元格一组

三个单元格一组永远无效。分组大小必须是 $2$ 的幂。

忽略首尾相接的相邻关系

很多最优的化简都要用到图两侧边缘上的单元格。如果忘了首尾相接规则，你得到的答案往往会比必要的更长。

强行让每个 $1$ 恰好只属于一个分组

这不是规则。重复使用某个单元格，往往反而是形成更大分组、得到更短最终表达式的最好方法。

什么时候使用卡诺图

卡诺图在数字逻辑和计算机工程入门课程中很常见，因为它把布尔化简变成了一个可视化过程。尤其是在你想先得到一个更简单的与或式，再去绘制或实现逻辑电路时，它非常有用。

它也很适合帮助建立直觉。即使较大的设计通常由软件处理，学习卡诺图仍然能帮助你理解为什么某些布尔项可以合并，而另一些不能。

试一道类似的题

试着自己化简 $F(A,B,C)=\sum m(0,2,4,6,7)$。先画出卡诺图，优先做最大的有效分组，然后只保留每组中保持不变的变量。

如果你想再进一步，可以试试带有 don't-care 值的版本，并且只在它们有助于形成更大有效分组时才使用它们。