8.2.3　逻辑函数的卡诺图化简法

用公式法化简逻辑函数要求熟练地掌握公式，并具备一定的化简技巧，而且，有时化简的结果是否为最简形式也不好确定，下面介绍另一种化简方法，即卡诺图化简法。它是由美国工程师卡诺（Aarnaugh）首先提出来的，所以把这种图形叫作卡诺图。卡诺图比较直观简捷，利用它可以方便地化简逻辑函数。

1.逻辑函数的最小项

（1）最小项的定义。

在逻辑函数表达式中，如果一个乘积项包含了所有的输入变量，而且每个变量都是以原变量或反变量的形式出现一次，且仅出现一次，该乘积项就称为最小项。

例如，ABC三变量的最小项共有8个，分别是。它们都含三个变量，而每个变量都以原变量或反变量形式在一个乘积项中出现一次，故共有23=8个。同理，四变量的最小项有24=16个，n变量的最小项有2n个。

（2）最小项的编号。

为了表示方便，常常对最小项进行编号。例如三变量最小项，我们把它的值为1所对应的变量取值组合000看作二进制数，相当于十进制数0，作为该最小项的编号，记作m0。以此类推，。表8-7已列出了各最小项的编号。

表8-7　三变量逻辑函数的最小项及其相应编号

（3）最小项的性质。

根据最小项的定义，不难证明最小项具有以下性质：

① 每一个最小项都对应了一组变量取值，只有该组取值出现时其值才会为1。

② 任意两个不同的最小项乘积恒为0。

③ 全部最小项之和恒为1。

（4）最小项表达式。

任何一个逻辑函数均可以表示成若干个最小项之和的形式，这样的逻辑函数表达式称为最小项表达式。

【例8-10】将逻辑函数 展开成最小项之和的形式。

解：在和AC中分别乘以可得到

式中求和符号Σ表示括号中指定最小项的或运算。

【例8-11】将 化为最小项表达式。

2.逻辑函数的卡诺图

（1）卡诺图的画法规则。

n个逻辑变量可以组成2n个最小项。在这些最小项中，如果两个最小项仅有一个因子不同，而其余因子均相同，则称这两个最小项为逻辑相邻项。为表示最小项之间的逻辑相邻关系，美国工程师卡诺设计了一种最小项方格图。他把逻辑相邻项安排在相邻的方格中，按此规律排列起来的最小项方格图称为卡诺图。

n个变量的逻辑函数由2n个小方格组成。图8-5给出了二变量、三变量和四变量卡诺图的画法。

图8-5　卡诺图画法

在画卡诺图时，应遵循如下规定：

① 将n变量函数填入一个分割成2n个小方格的矩形图中，每个最小项占一格，方格的序号和最小项的序号一致，由方格左边和上边二进制代码的数值确定。

② 卡诺图要求上下、左右相对的边界、四角等相邻格只允许一个变量发生变化（即相邻最小项只有一个变量取值不同）。

（2）用卡诺图表示逻辑函数。

既然任何一个逻辑函数都可以表示为若干个最小项之和的形式，那么也就可以用卡诺图来表示逻辑函数。实现用卡诺图来表示逻辑函数的一般步骤是：

① 先将逻辑函数化成最小项表达式。

② 在相应变量卡诺图中标出最小项，把式中所包含的最小项在卡诺图相应小方格中填1，其余的方格填上0（或不填）。

【例8-12】画出函数Y=AB+CA的卡诺图。

解：首先将Y化成最小项表达式：

把Y的最小项用1填入三变量卡诺图中，其余填0（或不填）便可得如图8-6所示的卡诺图。

图8-6　例2-16函数的卡诺图

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

（1）最小项的几何相邻和逻辑相邻。

卡诺图的最大特点是用几何相邻形象地表示了变量各个最小项之间在逻辑上的相邻性。凡是在图中几何相邻的最小项，在逻辑上都是相邻的。

逻辑相邻就是指两个最小项中除一个变量的形式不同外，其他变量都相同。例如图8-7（a）中，与m1=ABC ，只有B不同，由公式法化简可知， 。把m0、m1用一个圈圈起来，合并成一项AC，可以消去变量B，这个圈称为卡诺圈。同样，图8-7（b）、（c）也可进行相应化简，消去变量B和A。(www.xing528.com)

图8-7　两个相邻最小项的合并举例

图8-8给出了三变量和四变量函数中，4个相邻项用卡诺圈合并为一项，消去两个变量的例子。

图8-8　4个相邻最小项的合并举例

由图可知，用卡诺圈圈起来的4个方格能组成一个方格群[图8-8（a）、（c）、（e）、（f）]（如把卡诺图“绕卷”成圆柱面，可以看出两侧或者是四角实际上也是逻辑相邻的），或者组成一行[图8-8（b）、（d）]。

图8-9所示为8个相邻项的合并举例。它们可以是两个相邻行、相邻列，或者对称的两行或两列。

图8-9　8个相邻项合并举例

由上述可知，卡诺圈所圈方格的个数为2n，即2个、4个、8个……所圈图形构成方形（或矩形）。2n个最小项合并成一项时可以消去n个变量。如22=4个小方格合并时可消去2个变量；23=8个小方格合并成一项时可消去3个变量；若将卡诺图中所有的小方格都用卡诺圈圈起来，则化简结果为1。

（2）用卡诺图化简逻辑函数的步骤。

① 画（逻辑函数的）卡诺图。

② 画卡诺圈，即用卡诺圈包围2n个为1的方格群，合并最小项，写出乘积项。

③ 写表达式。先按照留同去异原则写出每个卡诺圈的乘积项，再将所有卡诺圈的乘积项加起来，即为化简后的与或表达式。

利用卡诺图进行逻辑函数化简时，应遵循以下原则：

① 卡诺圈越大越好。合并最小项时，包围的最小项越多，消去的变量就越多，化简结果就越简单。

② 卡诺圈的个数越少越好，这样化简后的乘积项就少。

③ 不能漏项。必须把组成函数的全部最小项都圈完。

【例8-13】用卡诺图化简函数Y（A，B，C，D）=∑m（1，5，6，7，11，12，13，15）。

解：（1）先将函数Y填入四变量卡诺图中，如图8-10所示。

图8-10　例8-13的卡诺图化简

（2）画卡诺圈，从图8-10中看出，包含m5、m7、m13、m15的卡诺圈虽然最大，但它不是独立的，这4个最小项已被其他4个卡诺圈圈过了。

（3）提取每个卡诺圈的公因子构成乘积项，然后将这些乘积项相加，得到化简后的逻辑函数为

【例8-14】用卡诺图化简函数

解：（1）先将函数Y填入四变量卡诺图，如图8-11所示。

图8-11　例8-14的卡诺图化简

（2）画卡诺圈。

（3）提取每个卡诺圈的公因子作乘积项，将这些乘积项相加，就可得到化简后的逻辑函数为

4.具有无关项的逻辑函数的化简

实际的数字系统中，有的输出逻辑函数只和一部分有对应关系，而和余下的最小项无关。余下的最小项无论写入函数式还是不写入函数式，都无关紧要，不影响系统的逻辑功能。我们把这些最小项称为无关项。

无关项包含两种情况：一是由于逻辑变量之间具有一定的约束关系，使有些变量的取值不可能出现，它所对应的最小项恒等于0，通常称为约束项；另一种是在某些变量取值下，函数值是1还是0皆可，并不影响电路的功能，这些变量取值下所对应的最小项称为任意项。本节重点讨论由于约束关系而形成的无关项，即约束项。

【例8-15】一个计算机操作码形成电路，三个输入信号为A、B、C，输出操作码为Y1、Y0。当A=1时，输出加法操作码01；当B=1时，输出减法操作码10；当C=1时，输出乘法操作码11；当A=B=C=0，输出停机码00。要求电路在任何时刻只产生一种操作码，所以不允许输入信号A、B、C中有两个或两个以上同时为1，即ABC取值只可能是000、001、010、100中的一种，不能出现其他取值。可见，A、B、C是一组具有约束的变量，后面四种最小项不允许出现，因此约束条件他可以写为

这些恒等于0的最小项即为约束项。

既然约束项的值恒等于0，所以在输出函数表达式中，既可以写入约束项，也可以不写入约束项，都不影响函数值。如果用卡诺图表示该逻辑函数，则在约束项对应的方格中，既可填入1，也可填入0。为此，通常填入“×”来表示约束项。

为简化逻辑函数最小项表达式，最小项可用编号来表示，因此约束项也可用相应的编号来表示。如上例，约束项可写为∑d（3，5，6，7）=0。

化简具有约束项的函数，关键是如何利用约束项。约束项对应的函数值既可视为1，也可视为0，可根据需要将“×”看作0或1，力求使卡诺圈最大，从而结果最简。

【例8-16】化简逻辑函数Y=∑m（1，7，8）+ ∑d（3，5，9，10，12，14，15）

解：（1）画出函数Y的卡诺图，如图8-12所示。

（2）画卡诺圈。画卡诺圈时可以把“×”包括在里面，但并不需要把所有的“×”全部用卡诺圈圈起来。

图8-12　例8-16的卡诺图

（3）提取公因子，写出最简与或表达式为

由此例可以看出，利用无关项以后，可以使逻辑函数得到进一步的化简。