2.4 逻辑函数的化简

逻辑函数表达式有各种不同的表示形式，即使同一类型的表达式也可能有繁有简。对于某一个逻辑函数来说，尽管函数表达式的形式不同，但它们所描述的逻辑功能却是相同的。在数字系统中，逻辑函数的表达式和逻辑电路是一一对应的，表达式越简单，用逻辑电路去实现也就越简单。通常，从逻辑问题直接归纳出的逻辑函数表达式不一定是最简单的，为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。

逻辑函数表达式是什么形式才能认为是最简呢？衡量逻辑函数最简表达式的标准是表达式中的项数最少，每项中包含的变量最少。这样用逻辑电路去实现时，用的逻辑门的数量就最少，每个逻辑门的输入端也最少。

逻辑函数化简的方法有很多种，最常用的方法是代数化简法和卡诺图化简法。

2.4.1 代数化简法

代数化简法是利用逻辑代数的公理、定律和规则对逻辑函数表达式进行化简。一个逻辑函数可以有多种表达形式，而最基本的就是与或表达式。如果有了最简与或表达式，通过逻辑函数的基本定律和规则进行变换，就可以得到其他形式的最简表达式。

1．与或表达式的化简

最简的与或表达式应满足两个条件。

1）表达式中的与项个数最少。

2）在满足上述条件的前提下，每个与项中的变量的个数最少。

化简与或表达式的常用方法有：

（1）并项法

利用逻辑代数的并项律，将两个与项合并成一个与项，合并后消去一个变量，例如：。

（2）吸收法

利用逻辑代数的吸收律A+AB=A，消去多余的项，例如：B+ABC=B，（E+F）=。

（3）消去法

利用逻辑代数的消去律=A+B，消去多余的变量，例如：

（4）配项法

利用公理0-1律的A·1=A和公理互补律的，先从函数表达式中选择某些与项，并配上所缺少的一个合适的变量，然后再利用并项法、吸收法和消去法等方法进行化简。例如：

（5）冗余法

利用逻辑代数的冗余律，消去多余的变量，例如：

上面介绍的例子比较简单，而实际中遇到的逻辑函数往往比较复杂，化简时应灵活地使用逻辑代数的公理、定律和规则，综合运用各种方法。下面给出几个相对复杂一些的例子。

【例2-12】化简逻辑函数。

解：

【例2-13】化简逻辑函数。

解：

【例2-14】化简逻辑函数。

解：

2．或与表达式的化简

同与或表达式的化简类似，最简的或与表达式也应满足两个条件。

1）表达式中的或项个数最少。

2）在满足上述条件的前提下，每个或项的变量个数最少。

用代数化简法化简或与表达式可直接运用公理、定律中的或与形式，并综合运用前面介绍的与或表达式化简时提出的各种方法进行化简。但是如果对于公理、定律中的或与形式不太熟悉，也可以利用对偶规则对逻辑函数两次求对偶的方法来化简，即首先对逻辑函数的或与表达式求对偶，得到其对偶函数的与或表达式，再按与或表达式化简的方法求出对偶函数的最简与或表达式，最后对最简的对偶函数再求对偶，即可得到逻辑函数的最简的或与表达式。

【例2-15】化简逻辑函数F=（A+B）（A+）（B+C）（A+C+D）。

解：逻辑函数F的对偶函数为

再对F′求对偶，可得F=A（B+C）。

2.4.2 卡诺图化简法

卡诺图是美国工程师Karnaugh于20世纪50年代提出的。卡诺图是逻辑函数真值表的一种图形表示。

1．卡诺图的结构

卡诺图是由2ⁿ个小方格构成的正方形或长方形的图形，其中，n表示变量的个数。每个小方格对应一个最小项，并按照在逻辑上相邻的最小项在几何上也相邻的原则进行排列。两个最小项的逻辑相邻是指这两个最小项只有一个变量互为反变量，其余变量都完全相同，因此要实现逻辑相邻的最小项在几何上也相邻，就需要卡诺图上的变量按照格雷码的顺序排列。

图2-6所示为2变量的卡诺图，它由2²=4个方格组成。每一列和每一行上的0和1分别代表变量A和B的值。

类似地，可以画出3变量、4变量和5变量的卡诺图，分别如图2-7～图2-9所示。

2．卡诺图的表示

卡诺图实际上是由真值表变换而来的，真值表有多少行，卡诺图就有多少个小方格，而卡诺图上的每个小方格就代表着真值表上的一行，也代表着一个最小项或最大项。将逻辑函数用卡诺图表示，需分以下4种情况。

（1）最小项表达式

因为构成逻辑函数的每一个最小项，其逻辑取值都是使函数值为1的最小项，所以填写卡诺图时，在构成函数的每个最小项相应的小方格中填上1，而在其他方格中填入0即可。也就是说，任何一个逻辑函数都等于它的卡诺图中填1的那些最小项之和。

【例2-16】画出逻辑函数F（A，B，C，D）=∑m（1，3，6，7）的卡诺图。

解：先画一个4变量的卡诺图，在对应最小项m₁、m₃、m₆和m₇的位置填入1，其余小方格中填入0，得到逻辑函数F（A，B，C，D）=∑m（1，3，6，7）的卡诺图如图2-10所示。

（2）最大项表达式

因为相同编号的最小项和最大项之间存在互补关系，所以使逻辑函数值为0的那些最小项的编号与构成函数的最大项表达式中的那些最大项编号相同，按这些最大项的编号在卡诺图的相应小方格中填入0，其余方格中填入1即可。

【例2-17】画出逻辑函数F（A，B，C，D）=∏M（3，4，8，9，11，15）的卡诺图。

解：先画一个4变量的卡诺图，在对应最大项M₃、M₄、M₈、M₉、M₁₁和M₁₅的位置填入0，其余小方格中填入1，得到逻辑函数F（A，B，C，D）=∏M（3，4，8，9，11，15）的卡诺图如图2-11所示。

（3）任意与或表达式

对于任意的与或表达式，可以先将其转换为标准的与或表达式，再按最小项表达式的方法填入卡诺图。另外，也可以不经转换直接填写。任意的与或表达式填入卡诺图的方法是：首先分别将每个与项的原变量用1表示，反变量用0表示，在卡诺图上找出交叉的小方格并填入1，在没有交叉点的小方格中填入0。

【例2-18】画出逻辑函数F（A，B，C，D）=AB+BC+CD的卡诺图。

解：先画一个4变量的卡诺图，与项AB用11表示，对应的最小项为m₁₂、m₁₃、m₁₄和m₁₅，在卡诺图对应小方格中填入1。与项BC用11表示，对应的最小项为m₆、m₇、m₁₄和m₁₅，在卡诺图对应小方格中填入1。与项CD用11表示，对应的最小项为m₃、m₇、m₁₁和m₁₅，在卡诺图对应小方格中填入1。

所以，逻辑函数F（A，B，C，D）=AB+BC+CD的最小项包含m₃、m₆、m₇、m₁₁、m₁₂、m₁₃、m₁₄和m₁₅，其卡诺图如图2-12所示。

（4）任意或与表达式

与任意的与或表达式类似，对于任意的或与表达式只要当任意一项的或项为0时，函数的取值就为0。要使或项为0，只需将组成该或项的原变量用0、反变量用1代入即可。故任意或与表达式对应的卡诺图的填入方法是：首先将每个或项的原变量用0、反变量用1代入，在卡诺图上找出交叉的小方格并填入0，然后在其余小方格中填入1即可。

【例2-19】画出逻辑函数的卡诺图。

解：先画一个4变量的卡诺图，或项A+C对应的最大项为M₀、M₁、M₄和M₅，在卡诺图对应小方格中填入0。或项对应的最大项为M₅、M₇、M₁₃和M₁₅，在卡诺图对应小方格中填入0。或项C+D对应的最大项为M₀、M₄、M₈和M₁₂，在卡诺图对应小方格中填入0。

所以，逻辑函数的最大项包含M₀、M₁、M₄、M₅、M₇、M₈、M₁₂、M₁₃和M₁₅，其卡诺图如图2-13所示。

3．卡诺图的性质

卡诺图的特点是任意两个逻辑相邻的最小项（或最大项）在几何上也相邻。在卡诺图中，相邻项有以下3种形式。

（1）几何相邻

即几何位置上相邻的最小项，如4变量卡诺图中与m₀的相邻最小项m₁和m₄，这些最小项对应的小方格与m₀对应的小方格分别相连，如图2-14所示。

（2）相对相邻

同一行的两端及同一列的两端为相对相邻，如4变量卡诺图中m₀相对相邻的最小项m₂和m₈，m₀和m₂处于同一行的两端，m₀和m₈处于同一列的两端，如图2-15所示。

（3）重叠相邻

5变量卡诺图中的m₃与m₁、m₂、m₇为几何相邻，与m₁₁相对相邻，与m₁₉则是重叠相邻。对于这种情形，可将卡诺图左右两边的矩形重叠，凡上下重叠的最小项即为重叠相邻。只有5个及其以上变量的卡诺图中可能存在重叠相邻，如图2-16所示。

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

用卡诺图化简逻辑函数的一般步骤：

1）将函数化为基本形式之一（与或表达式、或与表达式）。

2）画出函数对应的卡诺图，在相应的格子里填入0和1。

3）找出可以合并的相邻项。每2^m个相邻项可以合并为一个卡诺图。先画大的卡诺圈，后画小的卡诺圈，每次画圈时尽量圈未被圈过的格子，以提高画圈的效率，至少要圈一个以前没有圈过的格子，以避免重复画圈。如果是求最简与或表达式，则圈为1的格子；如果是求最简或与表达式，则圈为0的格子。

4）检查第3）步画圈的情况，确保每个需要圈的格子至少被圈一次，不要遗漏。

5）根据卡诺图写最简形式。

【例2-20】用卡诺图化简逻辑函数F（A，B，C，D）=ABC+，求出其最简的与或表达式。

解：逻辑函数F（A，B，C，D）=ABC+对应的卡诺图如图2-17a所示。根据卡诺图化简的方法，圈卡诺圈，如图2-17b所示。

因此求得的逻辑函数的最简与或表达式为F（A，B，C，D）=ABC+ABD+CD。

【例2-21】用卡诺图化简逻辑函数F（A，B，C，D）=∑m（3，4，5，6，7，9，11，13，15），求出其最简的与或表达式。

解：逻辑函数F（A，B，C，D）=∑m（3，4，5，6，7，9，11，13，15）对应的卡诺图如图2-18a所示。根据卡诺图化简的方法，圈卡诺圈，如图2-18b所示。

因此求得的逻辑函数的最简与或表达式为F（A，B，C，D）=+AD+CD。

【例2-22】用卡诺图化简逻辑函数F（A，B，C，D）=∏M（3，4，6，7，11，12，13，14，15），求出其最简的与或表达式。

解：逻辑函数F（A，B，C，D）=∏M（3，4，6，7，11，12，13，14，15）对应的卡诺图如图2-19a所示。根据卡诺图化简的方法，圈卡诺圈，如图2-19b所示。

因此求得的逻辑函数的最简与或表达式为。

2.4.3 包含无关项的逻辑函数的化简

对于一个逻辑函数来说，如果针对逻辑变量的每一组取值，逻辑函数都有一个确定的值相对应，则这类逻辑函数称为完全描述逻辑函数。但是，在某些实际问题中，其输出并不是与2ⁿ种输入组合都有关，而是仅与其中的一部分输入组合有关，而与另一部分的输入组合无关。例如，一个电路输入为8421BCD码，则其输入变量中的16种组合中1010～1111不会出现。当函数输出与某些输入组合无关时，这些输入组合就称无关项，又称任意项或约束项。这里的“无关”有两个含义：一是这些输入组合在正常操作中不会出现；二是即使这些输入组合可能出现，但输出实质上与它们无关。换句话说，当输入出现这些组合时，其所对应的输出值可以为0，也可以为1。

与无关项相关的函数就称为包含无关项的逻辑函数，或称为具有约束条件的逻辑函数。若以d_i表示无关项，则约束条件（或称约束方程）表示为∑d_i=0。所以，无关最小项可以随意加到函数表达式中或不加到函数表达式中，而且并不影响函数的实际逻辑功能。根据这一特点，化简含有无关项的逻辑函数时，只要使得表达式最简，无关项可以取0，也可以取1。

【例2-23】用卡诺图化简逻辑函数F（A，B，C，D）=∑m（0，1，5，7）+∑d（4，6），求出其最简的与或表达式。

解：逻辑函数F（A，B，C，D）=∑m（0，1，5，7）+∑d（4，6）对应的卡诺图如图2-20a所示。根据卡诺图化简的方法，圈卡诺圈，如图2-20b所示。

因此求得的逻辑函数的最简与或表达式为F（A，B，C，D）=。

2.4.4 多输出逻辑函数的化简

单个逻辑函数的化简问题，前面已经进行了系统讨论。但在实际问题中，存在着根据一组相同输入变量产生多个输出函数的情况。对于一个具有相同输入变量的多输出逻辑电路，如果只是孤立地将单个输出函数一一化简，然后直接拼接在一起，通常并不能保证整个电路最简，因为各输出函数之间往往存在可共享的部分，这就要求在化简时把多个输出函数当作一个整体考虑，以整体最简为目标。下面以与或表达式为例来介绍多输出函数的化简。

衡量多输出函数最简的标准如下。

1）所有逻辑表达式中包含的不同与项总数最少。

2）在满足上述条件的前提下，各不同与项中所含的变量总数最少。

多输出函数化简的关键是充分利用各函数之间可供共享的部分（公共项）。例如，某逻辑电路有两个输出函数：

其对应的卡诺图如图2-21所示。从卡诺图可以看出，就单个函数而言，F₁和F₂均已达到最简。此时，两个函数表达式共含4个不同的与项，4个不同的与项所包含的变量总数为8个。

假如按图2-22所示的卡诺图化简上述函数，则可得到函数表达式为：

这样处理后，尽管从单个函数来看，上述两个表达式均未达到最简。但从整体来说，由于恰当地利用了两个函数的共享部分，使两个函数表达式中不同与项总数由原来的4个减少为3个，各不同与项中包含变量总数由8个减少为7个，从而使整体得到了进一步简化。

用卡诺图化简多输出函数，一般分两步进行。首先按单个函数的化简方法用卡诺图对各函数逐个进行化简。然后，在卡诺图上比较两个以上函数的相同1方格部分，看是否能够通过改变卡诺图的画法找出公共项。在进行后一步时要注意：第一，卡诺圈的变动必须在两个或多个卡诺图的相同1方格部分进行，只有这样，对应的项才能供两个或多个函数共享；第二，卡诺圈的变动必须以使整体得到进一步简化为原则。

【例2-24】用卡诺图化简多输出函数

F₁（A，B，C，D）=∑m（2，3，5，7，8，9，10，11，13，15）

F₂（A，B，C，D）=∑m（2，3，5，6，7，10，11，14，15）

F₃（A，B，C，D）=∑m（6，7，8，9，13，14，15）

解：画出3个函数的卡诺图，如图2-23所示。

考虑到各函数的共享问题，可按图2-23所示的卡诺圈的画法，使函数从整体上得到进一步简化，化简结果为