卡诺图：逻辑相邻与几何相邻的统一

今天是南方小年，春节渐近，提前祝大家新春快乐！

这节内容斟酌再三，今天终于成稿，主要是希望内容既全面又易于理解，可能比通用教材啰嗦，但是讲的更透。卡诺图既是一种图形化方法，也是一种有助于计算机辅助分析的逻辑化简思想，重要性不言而喻。

1.一句话记住卡诺图

卡诺图是化简逻辑函数的重要工具，是一张二维表格，相当于变形的真值表，主要特点是实现了几何相邻和逻辑相邻的统一，能帮助我们直观地表示逻辑函数并写出最简逻辑式，而判断相邻的直观方法就是对折重合。

2.卡诺图的由来、定义和特点

1953年，贝尔实验室的电信工程师莫里斯·卡诺（Maurice Karnaugh）在维奇图（一种逻辑函数的图形表示）的基础上改进发明了卡诺图，使逻辑函数的化简相较代数法变得简单且直观，从而在数字逻辑设计等领域中得到了广泛应用。

卡诺图是按照逻辑相邻性原则组成的二维表格（方格图）。它跟真值表是完全对应的，其中每个方格相当于真值表中的一行，代表一个最小项或最大项，如图1所示为二变量函数的真值表和卡诺图的对应关系。

图1

图1中，卡诺图左上角斜线两侧为函数$Y$的输入变量符号，横边和侧边的数字为相应变量的取值，取值的排列按格雷码分布（详见图3、图4、图5），这是实现逻辑相邻（对应变量组合的取值只有一位不同）与几何相邻相统一的原因；图1中，方格中的数字表示最小项或最大项的序号（变量取值组合对应的十进制数），对一个确定的函数，方格中填写相应的函数输出值，如图2所示。

图2

实际使用中，一般将方格默认为最小项，因此，大部分教材直接用最小项定义卡诺图：

将$\mathbf{n}$变量的全部最小项各用一个小方格表示，并使具有逻辑相邻性的最小项在几何位置上也相邻地排列起来，得到的图形称为$\mathbf{n}$变量最小项的卡诺图。

将卡诺图定义于最小项，主要是基于人们的使用习惯和应用便捷性，因为无论是真值表还是卡诺图，我们最习惯、最容易写的是与或式。但是，我们知道最小项与最大项天然互反，一一对应，逻辑相邻性和几何相邻性也是一样的，所以，如果你更习惯于使用最大项，也可以将每个方格用最大项表达，写出函数的或与式。具体来说，跟真值表一样，函数值为1的所有方格按最小项加起来就是最小项之和式，函数值为0的所有方格按最大项乘起来就是最大项之积式（这些项也可以写成最小项之和式，代表反函数），例如，对图2，有$Y=\Sigma m(1,2,3)$，或$Y=M_0$，或$\overline{Y}=m_0$。

从以上构图和定义可知，$n$变量卡诺图由$2^n$个方格组成，最终，任何两个位置相邻和轴对称的方格均具有逻辑相邻性，所谓轴对称就是对折重合，也就是将卡诺图横向或纵向对折，且可以对折分割后再对折，每次对折后所有重合的方格为逻辑相邻项。有的资料又将几何相邻分为位置相邻、相对相邻和相重相邻三种情况，所谓相对相邻是指每一行（或列）的两端，均在对折重合的范畴之内。

图3、图4、图5分别为用最小项表示的三变量、四变量和五变量卡诺图。

图3

图4

图5

以图5为例，$m_0$分别与$m_1$、$m_8$、$m_4$、$m_2$、$m_{16}$逻辑相邻。

3.填写卡诺图（用卡诺图表示逻辑函数）

⑴根据真值表填写卡诺图

上文图2即是一例，再举一个三变量的例子，逻辑函数$F(A,B,C)$的真值表如表1所示，将每一行的函数值填入三变量卡诺图对应的最小项方格中，得卡诺图如图6所示。

图6

⑵根据最小项（或最大项）填写卡诺图

将函数化为最小项（或最大项）表达式，再将相应的最小项方格填1。

例如函数$F=\Sigma m(1,4,5,6,7)$，只需在卡诺图的$m_1$、$m_4$、$m_5$、$m_6$、$m_7$方格中填写1，其余填0，如图6所示。同理，若$F=\prod M(0,2,3)$，则将卡诺图$m_0$、$m_2$、$m_3$方格填0，其余填1，同图6。

⑶根据函数的与或表达式填写卡诺图

对任何“与或式”函数，只需要将每一个乘积项对应的所有方格填写1即可。对乘积项中的各变量因子，原变量取1，反变量取0，找到相应的行和列并取交集，就是该乘积项对应的方格。例如，分别求$F_1=A+\overline{B}C$和$F_2=\overline{A}C$的卡诺图，方法如下：

①参考图3和图6，设$A$为行，$BC$为列。$F_1$第一个乘积项为$A$，找到$A=1$，即第二行，全部填1，如图7所示。

图7

②$F_1$第二个乘积项为$\overline{B}C$，所以找到$BC=01$的列，全部填1，剩余的方格填0，如图8所示，此即为$F_1$的卡诺图。

图8

③$F_2$只有一个乘积项$\overline{A}C$，找到$A=0$的行和$C=1$的两列，二者交集所在方格填1，其余填0，得$F_2$的卡诺图如图9所示。

图9

4.用卡诺图化简逻辑函数

卡诺图化简的依据：两个相邻最小项可以合并为一个乘积项并消去一个变量因子。

因此，对卡诺图中具有相邻性的项不断合并，可得到函数的最简逻辑式。相邻项合并时，消去取值发生变化的变量因子，保留公共因子，$2^{\mathbf{i}}$个相邻项，可消去$\mathbf{i}$个变量因子。

⑴化简步骤

①画卡诺图；

②圈“1”（求原函数）或者圈“0”（求反函数），合并最小项；

③将每个圈对应的乘积项相加，得最简与或式。

⑵画圈原则

①相邻单元的个数是$2^i$个，并成矩形时，可合并。

②每个圈中所含“1”的个数要尽可能多。

③画圈的个数要尽可能少。

④“1”方格可重复圈定，但每个圈内须有新的“1”。

综合题★★★

题1 用卡诺图化简下列函数：
$$Y=ABC+ABD+A\bar{C}D+\bar{C}\cdot \bar{D}+A\bar{B}C+\bar{A}C\bar{D}$$
解析：首先用卡诺图表示该函数，如图10所示。

图10

圈“1”，如图11所示，得最简逻辑式为
$$Y=A+\bar{D}$$

图11

也可圈“0”，如图12所示，合并最大项结果同上（不推荐），或合并最小项得反函数为
$$\overline{Y}=\overline{A}D$$

图12

题2 化简下列函数为最简与或式：
$$F(A,B,C,D)=\prod M(3,4,6,7,11,12,13,14,15)$$

解析：题目给的是最大项之积式，在卡诺图中将最大项序号对应的方格填0，其余填1，得该函数的卡诺图如图13所示。

图13

在卡诺图中圈“1”，如图14所示，得最简与或式为
$$F(A,B,C,D)=\bar{B}\cdot \bar{C}+\bar{B}\cdot \bar{D}+\bar{A}\cdot \bar{C}D$$

图14

题3 将题2中的函数化简为最简或与式：

解析：卡诺图同题2（图13），求或与式，所以圈“0”，如图15所示，然后写出反函数的最简与或式，再通过反演定理或摩根定理转换得原函数的最简或与式。（也可通过最大项合并直接写出最简或与式，除非对最大项特别熟练，否则不推荐。）

图15

由图15的合并结果，得
$$\bar{F}=AB+B\bar{D}+CD$$
故
$$F=(\bar{A}+\bar{B})(\bar{B}+D)(\bar{C}+\bar{D})$$

后记：关于列表法（Q-M法）

卡诺图对于六变量以上的复杂多变量逻辑函数显得无能为力，但是人们借助于卡诺图化简思想实现了多变量函数的计算机自动优化处理，Q-M法就是一种可通过计算机编程实现的系统化简法，也称为列表法或表格法，若专业从事集成电路底层设计，应予掌握，详情可查阅有关教材或资料。

更多内容，欢迎关注下方公众号！