2.4 逻辑函数的简化法

在现代数字电路或系统的设计过程中，设计优化是一个重要的技术指标。设计优化主要包括面积优化和时间优化两个方面，面积优化是指设计的电路或系统占用的逻辑资源的数量越少越好；时间优化是指设计电路或系统的输入信号到达输出路程越短越好，使输入信号经历最短的时间到达输出端。逻辑函数的简化是实现面积优化的一种举措。但随着电子设计自动化技术（EDA）的出现，设计优化过程由EDA工具软件自动完成，一般不需要设计者介入。本书介绍的逻辑函数简化内容，主要让读者了解简化的意义，并掌握一些简单电路的简化方法。

2.4.1 逻辑函数简化的意义

在进行逻辑运算时常常会看到，同一个逻辑函数可以写成不同的逻辑式，而这些逻辑式的繁简程度又相差甚远。逻辑式越简单，它所表示的逻辑关系越明显，同时也有利于用最少的电子器件实现这个逻辑函数，因此经常需要通过化简的手段找出逻辑函数的最简形式。

例如在例2.2中，直接由真值表推导出的3人表决电路最小项表达式为：

其对应的逻辑图如图2.17（a）所示，由图可以看出，式（2.40）需要4个与逻辑、3个非逻辑和1个或逻辑器件来实现。

将式（2.40）化简后得到：

其对应的逻辑图如图2.17（b）所示，由图可以看出，式（2.41）需要3个与逻辑和1个或逻辑器件来实现。显然，图2.17（b）比图2.17（a）要简单得多。

在与或表达式中，若其中包含的乘积项数最少，而且每个乘积项中的因子也不能再减少时，则称此逻辑函数为最简与或式。例如，式（2.41）就是最简与或表达式。在逻辑函数化简中，可以用不同的方法简化函数，得到最简表达式。

2.4.2 逻辑函数的公式简化法

逻辑函数的公式简化法的原理就是反复使用逻辑代数的基本公式、基本定理和常用公式，消去函数中多余的乘积项和多余的因子，以求得函数式的最简形式。

公式简化法没有固定的步骤。下面通过举例说明公式简化法的过程。

【例2.9】 化简

解：

【例2.10】 化简

解：

【例2.11】 化简

解：此例化简的对象是我们不太熟悉的或与表达式，可以先用对偶定理将其化为与或式后再化简，然后对简化后的逻辑式再求一次对偶，可得到原函数的最简表达式。

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

在传统数字电路的设计中，卡诺图是一种表示、化简和设计逻辑电路的重要工具，但它具有局限性，只能化简或设计输入变量少的简单数字逻辑电路。

1. 卡诺图的概念

（1）什么是卡诺图

将n变量的全部最小项各用一个小方块表示，并使具有逻辑相邻性的最小项，在几何位置上也相邻地排列起来，所得到的图形叫做n变量卡诺图。因为这种方法是由美国工程师卡诺（Karnaugh）首先提出来的，所以把这种图形叫做卡诺图。卡诺图也是逻辑函数的一种表示方法。

图2.18中画出了三到五变量最小项卡诺图。由图可以看出卡诺图画法的规律，即将n变量分成两组，如果是三变量，则分成 A 一组，BC 一组；如果是四变量，则分成 AB 一组，CD 一组。每一组的变量取值组合按循环码的规律排列。所谓循环码，是指相邻的两组之间只有一个变量取值不同的编码。例如，两个变量的取值组合按00→01→11→10排列；三个变量的取值组合按000→001→011→010→110→111→101→100排列。必须注意，这里的相邻，包含头、尾两组，即00与10或000与100也是相邻的。正是由于这种变量取值排列的规律，才能使得卡诺图中，代表最小项的两个相邻的小方块，具有逻辑相邻性。

（2）用卡诺图表示逻辑函数的方法

由于任意一个n变量的逻辑函数都可以换成最小项表达式，而n变量的卡诺图包含了n变量的所有最小项，所以n变量卡诺图可以表示n变量的任意一个逻辑函数。具体的方法是，首先把逻辑函数化为最小项表达式，然后在卡诺图上找到这些最小项对应的位置，并填入1，称为“1”格；在其余的位置填入0，称为“0”格。“1”格表示逻辑函数中包含的最小项，“0”格（也可以用“空格”代替）表示逻辑函数中不包含的最小项。也就是说，逻辑函数等于它对应的卡诺图中，由“1”格代表的最小项之和。

【例2.12】 用卡诺图表示逻辑函数

解：首先把F转换为最小项表达式，即将表达式中每个乘积项缺少的变量补上，使它们都成为最小项。具体过程如下

然后画出四变量卡诺图，找到函数式中各最小项的位置并填入1，其余位置填入0，得到F的卡诺图，如图2.19所示。

把逻辑函数换成最小表达式后，再填入卡诺图的方法十分繁琐，实际上可以采用观察法直接填卡诺图。用观察法直接填卡诺图的基本原理是，对于任何一个最小项，可以找到1组变量的组合使其值为1；而对于一个乘积项，则可以能找到一些变量的取值组合使其值为1，这些取值组合代表的最小项就包含在该乘积项中。

【例2.13】 用观察法在卡诺图中表示逻辑函数

解：这是一个4变量A、B、C、D的逻辑函数，乘积项AB CD是最小项，使其为1的变量取值组合是1001，则在m9小方格填入1表示该乘积项。乘积项B不是最小项，但由于该乘积项不包含变量A、C、D，所以A、C、D的取值与该乘积项无关，只要B = 1，就可以使该乘积项的值为1。使B = 1的变量取值组合有0100、0101、0110、0111、1100、1101、1110、1111共8个，对应的最小项为m4、m5、m6、m7、m12、m13、m14、m15。在卡诺图中把这8个最小项对应的方格填入1，即得到乘积项B代表的最小项组。同理，对于乘积项，只要CD的取值是10（与A、B的取值无关），该乘积项的值就为1。使为1的变量取值组合有0010、0110、1010、1110共4个，对应的最小项为m2、m6、m10、m14。在卡诺图中把这4个最小项对应的方格填入1，即得到乘积项代表的最小项组。画出的卡诺图如图2.20所示。

2. 卡诺图简化法

（1）卡诺图合并最小项的规律

在卡诺图中，两个几何位置相邻的“1”格具有逻辑上的相邻性，它们代表的最小项可以合并为一个乘积项，并消去一个取值有变化的变量。例如，在图2.21（a）所示的卡诺图中，7ABC(m )和相邻，故可以合并为，消去一个取值有变化的变量C，保留由没有变化的变量A、B构成的乘积项AB。在卡诺图中，把可以合并的最小项（“1”格）圈起来，一个圈就代表一个乘积项。

在卡诺图中4个相邻的“1”格（最小项）也可以合并为一个乘积项，消去两个取值有变化的变量，保留由没有变化的变量构成的乘积项。例如，在图2.21（b）所示的卡诺图中，画出了4个最小项相邻的几种可能情况，和 相邻，可以合并为一个乘积项B。消去两个有变化的变量A、C。另外，图2.21（c）中四个角上的“1”格也是相邻的，可以合并为乘积项。

在卡诺图中8个相邻的“1”格也可以合并为一个乘积项，消去3个取值有变化的变量，保留由没有变化的变量构成的乘积项。例如，在图2.21（d）所示的卡诺图中，、和 相邻，可以合并为一个乘积项，消去三个有变化的变量B、C、D。

综上所述，卡诺图合并最小项的规律可以归纳为：在卡诺图中，2i（i = 0,1,2,3,…）个相邻的最小项（”1”格），可以合并为一个乘积项，消去i个以原变量和反变量形式出现的变量，保留由没有变化的变量构成的乘积项。

卡诺图简化法就是在卡诺图上按照合并最小项的规律化简逻辑函数。卡诺图简化法具有简单、直观的特点，而且有简化步骤，容易得到最简结果。但它只适合6个变量以下的逻辑函数的简化。

（2）卡诺图简化法的步骤

用卡诺图化简逻辑函数时可以按如下步骤进行。

（1）画出表示该逻辑函数的卡诺图，并将函数填入卡诺图中。

（2）按合并最小项的规律圈出可以合并的最小项。

（3）选取化简后的乘积项。选取的原则是：

① 乘积项应包括函数式中所有的最小项，即应覆盖卡诺图中所有的”1”格。

② 合并最小项的圈中应包含尽量多的最小项，这样可以使乘积项的因子最少。

③ 合并后最小项的圈数最少，这样可以使化简后的逻辑函数的乘积项数最少。

④ 合并后的乘积项应是必要项（即至少可以找到一个只被圈过1次的”1”格的乘积项），避免多余项（即每个”1”格至少被圈2次或2次以上的乘积项）。

【例2.14】 用卡诺图化简法将下式化简为最简与或式

F(A,B,C,D) = m∑ (0,2,5,6,7,8,10,14,15)

解：首先，画出表示该逻辑函数的卡诺图，并将函数填入卡诺图中。然后，按合并最小项的规律将可以合并的最小项圈出，如图2.22所示。最后按选取乘积项的原则选取乘积项，并写出简化结果为

【例2.15】 用卡诺图化简法将下式化简为最简与或式

F(A,B,C,D) = m∑ (3,4,6,7,10,13,14,15)

解：根据逻辑函数画出的卡诺图，以及合并的最小项的圈如图2.23（a）所示，简化结果为

在本例中，如果按图2.23（b）所示的圈法，则在简化结果中多出一个多余项BC。

3. 具有约束的卡诺图的化简

在逻辑电路的设计过程中，对于输入变量的取值组合，常常会遇到有些取值组合不允许出现，而有些取值组合不会出现，还有些取值组合出现或不出现对输出均无影响等情况。这类取值组合就是约束，其代表的最小项称为约束项或任意项、无关项，记作“x”或“Φ”、“d”。

例如，一个简单的行车控制电路的设计示意图如图2.24所示。图中的A、B分别表示电路的红灯信号输入和绿灯信号输入，并用1表示灯亮，0表示灯灭；F是输出信号，F = 0表示停车，F = 1表示行车。这样，AB输入组合中的“00”和“11”是不允许出现的，即红、绿灯不允许同时灭或同时亮。这种不允许出现的输入组合代表的最小项，就称为约束或约束项。

由于约束项是不允许出现、不会出现、出现或不出现对输出均无影响的最小项，所以可以对它们做任意处理。在卡诺图化简时，可以把它们合并在最小项的圈中，也可以不圈。正确处理约束项，可以使函数得到最简的结果。

【例2.16】 设计一位十进制数（采用8421BCD）的四舍五入电路。

解：四舍五入电路设计示意图如图2.25所示。图中的D、C、B、A表示一位十进制数的8421BCD编码输入，D的权值是8（最高），A的权值是1（最低）。由于8421BCD用0000～1001这10组组合代表十进制数的0～9，1010～1111这6组组合没有使用。没有使用的组合不会出现在输入端，因此1010～1111对应的最小项都是约束项。依题意列出的真值表如表2.13所示，其中“x”表示约束项。

由真值表推出的函数表达式为

F(D,C,B,A) = m∑ (5,6,7,8,9) + x∑ (10,11,12,13,14,15)

式中，x∑ (10,11,12,13,14,15)表示约束条件。约束条件也可以写成

∑d(10,11,12,13,14,15)

或用表达式形式写成

m10+m11+m12+m13+m14+m15 = 0

在用卡诺图化简时，如果不利用约束项，即只圈卡诺图中的”1”格，如图2.26所示，得到的简化与或表达式为

如果正确利用约束项，即可以将可利用的约束项圈入合并最小项的圈中，如图2.27所示，得到的简化与或式

比较式（2.42）和式（2.43）不难发现，正确利用约束项，可以使函数结果更简化。