卡诺图

1. 什么是卡诺图

卡诺图就是把真值表重新画成网格。莫里斯·卡诺 1953 年在贝尔实验室提出它，用来一眼看出开关电路的化简方法；直到今天，它仍是手工化简小型布尔函数最快的办法：不用代数，不用记公式，只要画长方形。

图中的每一格对应真值表的一行。真正让它不只是重新排列的，是这些行的排列顺序：相邻的两格恰好只有一个变量不同。

这一条性质就完成了全部工作。如果相邻两格都为真，那么它们之间变化的那个变量就不可能是使表达式为真的原因，于是它被消去，一个项同时覆盖这两格。化简由此变成：尽量画出最大的长方形。

2. 为什么列的顺序看起来不对

卡诺图的列不是按 00、01、10、11 数下去的，而是 00、01、11、10 —— 反射格雷码，一种相邻取值只差一个比特的排序。若按二进制顺序，01 会挨着 10，而它们相差两个比特，相邻格子也就说明不了任何问题。

边缘同样相邻。最左列与最右列只差一个变量，最上行与最下行也是如此，因此一个分组可以从一边越出、在另一边接着算——四变量图的四个角因此构成一个分组。卡诺图其实画在一个环面上，平铺的纸面只是方便而已。

3. 圈出 1

要从图上读出最简的积之和，就用矩形分组覆盖每一个为 1 的格子，遵守四条规则：

• 分组是 1、2、4、8 …… 个格子的矩形——每条边都是 2 的幂。
• 分组可以横向、纵向或同时越过图的边缘绕回。
• 分组之间可以重叠。一个格子被覆盖两次没有代价；漏掉一个格子却会改变函数。
• 每个分组都尽量圈到最大，然后用尽量少的分组覆盖所有的 1。

每个分组对应一个项。读法是看哪些变量在整个分组中保持不变：这些变量出现在项里——取值为 1 时原样写出，为 0 时取反——而发生变化的变量全部消去。两格的分组少一个变量，四格的少两个，八格的少三个。最简表达式就是这些项的析取。

4. 一个完整的例子

取 (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D)。它的卡诺图有四个变量：A 和 B 在行，C 和 D 在列。

两个分组覆盖了全部的 1。一个是 A = 0 的两行与 C = 1 的两列交叉处的四格：其中 B 和 D 都在变化，因此被消去，该项为 ¬A ∧ C。另一个是 A 和 B 同时为 1 的整整一行，横跨四列：C 和 D 沿行变化，剩下 A ∧ B。

所以最简形式是 (¬A ∧ C) ∨ (A ∧ B)。原式的第三项 B ∧ C ∧ D 消失了：它覆盖的每一格早已被那两个分组覆盖。这就是吸收律画出来的样子。

5. 质蕴涵项与必要质蕴涵项

无法再扩大的分组称为质蕴涵项。列出所有质蕴涵项是问题中容易的一半；挑选保留哪些才是容易出错的一半。

如果某一格只被一个质蕴涵项覆盖，那么这个蕴涵项就是必要的：任何最简形式都不能少了它，因为没有别的分组覆盖那一格。先取必要质蕴涵项，再用尽可能少的其余分组覆盖剩下的格子。

贪心做法——每次都取当前最大的分组——很诱人，却并不总是奏效。在循环覆盖表上，没有一个蕴涵项是必要的，每一格都被覆盖两次，贪心的选择可能比最优解多出一项。本站的卡诺图会穷举剩下的所有选择，而在四个变量的规模下，这几乎不花什么代价。

6. 改为圈 0

上面的一切对 0 同样适用。用同样的矩形覆盖它们，读每个分组时把文字取反——在整组中为 1 的变量写成取反，为 0 的变量原样写出——再用 ∧ 而不是 ∨ 把各组连接起来。

结果是和之积：一个析取式的合取，恰好在表达式为假的那些格子上为假，因而在其余各处为真。哪种形式更短取决于函数本身——1 很少的公式积之和短，0 很少的公式和之积短——所以选定之前，值得把两种形式都从图上读一遍。

7. 更大的图与无关项

五个和六个变量可以画成两张或四张四变量图叠在一起，相邻层中位置相同的格子算作相邻。这样可行，但让方法变得直观的相邻关系，如今要靠记忆而不是靠眼睛。再往上，奎因-麦克拉斯基算法以表格形式完成同样的工作：它正是这种分组的机械化形式，也正是本站卡诺图背后运行的算法。

硬件设计还多出一个概念。有些输入组合永远不会出现——二进制编码的十进制数字不会是 1010——设计者并不在意电路对它们的输出。这些格子标为 X，可以按任一取值来读，哪个能让分组更大就取哪个。本计算器的卡诺图由公式生成，每种赋值都有确定的值，因此没有任何一格是无关项。

8. 自己动手试试

在计算器中输入两到四个变量的表达式，卡诺图就会画在真值表下方，每个分组用各自的颜色圈出，最简形式写在下面。切换到和之积，即可看到圈出的是 0。