《数字逻辑设计与计算机组成》一2.4　逻辑化简

本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第2章，第2.4节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.4 逻辑化简

在第1章中已经讨论过，以最少的逻辑门以及每个逻辑门以最少的输入来生成输出信号是非常重要的。最小的SOP或者POS表达式包含了最少数目的逻辑项，每一项都是由最少数目的变量组成。图2-12展示了逻辑化简的优点。在这两个例子中，规范表达式的电路实现需要更多的逻辑门，即需要更多的晶体管和电线来实现。
在图2-12中，SOP规范表达式的电路需要4个三输入的与门、3个非门和1个四输入的或门或者总共需要8个与非门实现，包括非门在内，每一个逻辑门至多有4个输入。另一方面，与其等价的最小SOP表达式只需要2个二输入的与门、1个非门和1个二输入的或门，或者一共需要5个与非门，每一个逻辑门的输入都减少了。类似地，f的规范POS表达式需要一共8个或非门，而其最小表达式只需要5个或非门，每一个逻辑门的输入减少了。

正如之前讨论的，规范SOP表达式或者规范POS表达式分别可以很容易地从最小项或者最大项推导而来。最小/最大项可以直接从真值表得来。我们也可以根据给定的规范SOP表达式或者规范POS表达式写出其对应的真值表。然而，不推荐也不必这样做。
确定给定非规范表达式的最小项或最大项不是一个简单的过程。不推荐通过判定每一个输入信号条件来确定其最小项或最大项。例如，确定表达式的真值表，需要在所有3位输入x、y和z的各种取值组合下计算该表达式的值。例如，由x = 0、y = 1和z = 0可得f = 1，由x = 1、y = 1和z = 0可得f = 0，等等，这样可以确定整个真值表。然后可以从f的真值表得到其最小项和最大项。
还有一种选择是运用布尔代数把一个不规范的表达式转换成规范表达式。若表达式是一个SOP表达式，则直接将规范表达式转换成其最小项；若表达式是一个POS表达式，则直接将规范表达式转换成其最大项。这个过程与逻辑化简步骤相反，如下所示：

使用以下步骤将一个函数f的非规范POS表达式转换成与其对应的规范表达式：
1）使用等式“的SOP表达式= f的POS表达式”将f的非规范POS表达式转换成的非规范SOP表达式。
2）通过的非规范SOP表达式求得其规范SOP表达式。
3）使用等式“f的POS表达式=的SOP表达式”将的规范SOP表达式转换成f的规范POS表达式。

2.4.1 卡诺图

卡诺图（K图）是一种识别和消除规范表达式中冗余项及获得一个或多个等价最小表达式的图形技术。两个用二进制表示仅有一位不相同的最小项或者最大项可以简化一个变量。例如，三个变量x、y、z，两个最小项2 = (010)2和3 = (011)2中z的变量取值是不一样的。此项简化成y的过程如下所示：

类似地，两个用二进制表示仅有一位不相同的最大项可以简化成减少一个变量的逻辑项。考虑以下由最大项2 = (010)2和3 = (011)2组成的规范POS表达式：

在K图中，任何两个用二进制表示仅有一位不相同的逻辑项互相连接，最小/最大项以这种方式来组织，使得定义这些逻辑项更容易。例如，三个变量x、y、z有8种可能的最小/最大项组织成2×4或者4×2的K图，分别如图2-13a和图2-13b所示。K图中的每一个方格表示一个最小/最大项，并且定义为以二进制表示的行标和列标的组合。例如，0行00列的方格定义了值为0的最小/最大项；0行01列的方格定义了值为1的最小/最大项；等等。

在图中，用二进制表示的相邻行标和列标只有一位不同。图2-13a中标记为00和10的两列也被认为是相邻的；所以图2-13b中标记为00和10的两行也是相邻的。这样的定义有助于直观地看出只有一位不相同的最小/最大项。每一个逻辑项都与其上下左右四个方向的逻辑项相邻。例如，在图2-13a中，逻辑项0 = (000)2与其左方的逻辑项2 = (010)2和其右方的逻辑项1= (001)2是相邻的，与其下方的逻辑项4 = (100)2也是相邻的。逻辑项(000)2与(001)2、(010)2和(100)2有一位不相同。图2-14展示了一个四输入的K图。例如逻辑项0，分别与逻辑项1（右方）、2（左方）、4（下方）和8（上方）相邻。

函数g (x, y, z) = Σ (2, 6, 7)的K图如下所示，其中用1表示其每一个最小项。其余的方格对应于其最大项和留空项。

在K图中，最小项2 = (010)2与另一个最小项6 = (110)2相邻，而最小项6与最小项
7 = (111)2相邻。然而最小项2与最小项7并不相邻，二进制表示(010)2与(111)2有两位不同。函数g (x, y, z) = Π (0, 1, 3, 4, 5)的POS表达式的K图如下所示：

2.4.2 K图化简

K图可以产生化简后的表达式。一个函数可以有多个化简后的表达式，它们之间是等价的。一对相邻的逻辑项可以化简成减少一个变量的逻辑项，多个相邻的逻辑项可以化简成减少更多变量的逻辑项。如图2-15所示，K图中有4个最小项，分别为2、3、6和7。

最小项(010)2与最小项(011)2和(110)2相邻，最小项(011)2与最小项(010)2和(111)2相邻，最小项(110)2与(010)2和(111)2相邻。运用布尔代数，这些最小项可以化简为y，如下所示：

例如公式（2-6）和图2-15的化简，运用K图化简步骤如下：
1）比较两个列标11和10，其中与其有联系的是最小项组(010)2、(011)2、(110)2和(111)2。代表变量z的位标记改变了，而代表变量y的位标记没有变化；这样变量z可以消掉。（在代数运算中，较小项y和xy被提出来，从而消掉z。）
2）比较两个行标，信号x变化了，而与其有位联系的y（剩下的变量）没有变化；这样，x可以被消掉。（在代数运算中，y可以被提取出来从而消掉x。）
3）写下没有被消掉的变量（在这个例子中只有y）作为前面第1）和第2）步的化简结果，当位标记为0时信号为，当位标记为1时信号为y。这个例子中y为最小项组的最终化简结果，在公式（2-6）中也有相应的代数运算。
运用K图，无需进行布尔运算就可以求出与规范表达式等价的最小化简的表达式。考虑下列有最小项1、2、3、6和7的K图：

相邻的最小项组2、3、6和7可以被化简为y。对于最小项1 = (001)2来说，唯一与其相邻的最小项是3 = (011)2。比较两个列标01和11，变量y有改变，所以可以被消掉，得到结果逻辑项为z，对应为x = 0和z = 1。这样，最小项1、2、3、6和7最终的最小项化简表达式为

注意到最小项3运用了两次，一次是在最小项组2、3、6和7中，一次在最小项组1和3中。这个重复运用的依据是布尔代数中的规则x = x + x（或者对于最大项，x•x = x）。在逻辑表达式中重复使用逻辑项并不会改变其真值表，但是却可以帮助相邻逻辑项组成更大的逻辑项组，从而在最终的化简表达式中消掉更多的变量。下列布尔运算展示了这一点：
给定一个规范的SOP表达式，重复使用对应于最小项3的逻辑项yz：

使用相邻的原则重组逻辑项：

化简每一组逻辑项，最终得到化简的最小SOP表达式。
如果没有K图，决定一个逻辑项需要重复几次是非常困难的。最小表达式是通过K图中每一组相邻的逻辑项的最大数目得来的。K图的化简规则总结如下。
1.K图化简规则
1）我们把只有一位不同的最小/最大项称为是相邻的，并且它们被认为形成一个蕴含。我们假定K图是两侧都可以环绕的，即00列和10列也相邻。
2）一组蕴含可以组合起来形成一个称为素蕴含的大组。每一个组包含的逻辑项数目都是2的幂，即一个组可能含有一个逻辑项、两个逻辑项、4个逻辑项或者8个逻辑项。
3）每一个素蕴含必须至少包含一个不属于其他任何素蕴含的单独的逻辑项（例如无冗余组）。符合这个规则的素蕴含被称为基本素蕴含（EPI）。最终的最小表达式必须包含所有基本素蕴含的逻辑项。
4）所有逻辑项都必须分组。
例2-3 化简表达式。
解：f的K图如下：

最小项1、3、6和7组成了三个而不止一个素蕴含，如K图所示。这是因为最小项1 = (001)2和6 = (110)2都只与其他一个逻辑项相邻。由最小项3 = (011)2和7 = (111)2组成的素蕴含不是一个EPI。因为有一个素蕴含包含了最小项1和3 = (011)2，变量y的列标改变了，得到逻辑项z。由最小项6和7组成的素蕴含，变量z的列标改变了，得到逻辑项xy。即最终的最小SOP表达式为：

例2-4 化简表达式。

4个角的最小项0、2、4和6与第一行的最小项0、1、2和3组成了两个EPI。由于由最小项0、1、2和3组成的素蕴含中变量y和z改变了，所以消掉这两个变量得到逻辑项。类似地，由于由最小项0、2、4和6组成的素蕴含中变量x和y改变了，所以得到逻辑项。最终的最小SOP表达式为：

例2-5 化简表达式。
解：

图中有5个素蕴含和它们对应的最小项列表。只有标记为a、d和e的素蕴含为EPI。因为素蕴含a、d和e都只包含了素蕴含b、c和f中的部分最小项。

对于素蕴含a，变量x和z的标记是有变化的，所以得到最小项y；对于素蕴含d，变量w和z的标记是有变化的，所以得到x；对于蕴含e，变量w和y的标记有变化，所以得到。最后得到的最小SOP表达式为：

例2-6 化简表达式。
解：

素蕴含有：

素蕴含a、b以及c或d中的一个为EPI。EPI a、b和c化简后可得到下列最小SOP表达式：

两个最小表达式是等价的，因为它们的真值表是一样的，拥有相同的最小/最大项。
例2-7 化简表达式
解：

POS表达式的素蕴含和SOP表达式的素蕴含作用是一样的，然而在这个例子中，表达式g的K图中的0，等价于表达式的K图中的1，这些0可以组成逻辑项组，使用之前讨论的方法（f的POS表达式=的SOP表达式）决定g的POS表达式。在此例中，与
例2-6相似，表达式g的SOP素蕴含有和。这样，可以得到表达式g的POS素蕴含为：

类似地，表达式g有两个最小POS表达式：1）使用EPI a、b和c；2）使用EPI a、b和d。使用2）可得到下列POS表达式：

例2-8 化简表达式。
解：

素蕴含有：

这些素蕴含都是基本素蕴含，且它们对应的最小POS表达式如下：
a:变量w和z的标记有改变，得到(x + y)。
b:变量y的标记有改变，得到(w + x + z)。
c:变量x的标记有改变，得到(w + y + )。
d:此蕴含只包含一个逻辑项，得到( + + + z)。
所以最终的最小表达式为：

![image](https://yqfile.alicdn.com/316b1c88ff6a578c9274952f10cc8a0c9b1bef6c.png)

2.无关项
在极少一些情况下，输出可能只由当前输入条件的一个子集决定，而其他的输入条件是不确定的。例如，考虑图2-16中的7段显示单元（7SDU）及其转换模块。假设转换器用于显示0～9的二-十进制编码数字（BCD）。给定4位输入，范围为0 = (0000)2到9 = (1001)2，转换器生成了7个信号，从fa到fg：一个信号可以使得a到g的7段中的一段显示管开启，使其对应0～9的数字。

例如，要显示数字0，除了g段所有的显示管都必须开启；这样，除了信号fg，所有的信号值都必须为1（假设使用高电平输出）。如果要显示数字9，除了信号ff，所有的信号必须开启，除了ff，所有信号值必须为1。当输入信号为4位0～9的数字时，BCD到7SDU转换器用于正确输出fa到fg信号。当输入信号为10～15时，输出是没有定义的，可以被认为是无关的，在真值表中以d表示。
一个无关的最小/最大项可以用“通配符”表示，根据K图的需要可以表示为0或者1。这样，无关项就可以用于帮助消掉变量和化简最终的表达式。考虑表达式=
，其中，用于表示表达式f的最小项中的无关项。类似地，符号用于表示函数中最大项中的无关项。如下所示，其中一个基本蕴含包含了两个无关项，只有无关项被用到来化简表达式。无关项变成的最小项3和11和最小项1和9一起生成了基本蕴含z。最小项7，不是一个无关项，不需要用到。所以最后最小化简的SOP表达式为f。

《数字逻辑设计与计算机组成》一 2.5 逻辑化简算法 本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第2章，第2.5节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《数字逻辑设计与计算机组成》一2.7 其他逻辑门 本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第2章，第2.7节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《数字逻辑设计与计算机组成》一 2.2 逻辑表达式 本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第2章，第2.2节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《数字逻辑设计与计算机组成》一3.3 加法器 本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第3章，第3.3节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《逻辑与计算机设计基础（原书第5版）》——2.1 二值逻辑和逻辑门 本节书摘来自华章计算机《逻辑与计算机设计基础（原书第5版）》一书中的第2章，第2.1节，作者：（美）M.莫里斯·马诺（M. Morris Mano）著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《逻辑与计算机设计基础（原书第5版）》——2.5 卡诺图的化简 本节书摘来自华章计算机《逻辑与计算机设计基础（原书第5版）》一书中的第2章，第2.5节，作者：（美）M.莫里斯·马诺（M. Morris Mano）著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《逻辑与计算机设计基础（原书第5版）》——3.8 迭代组合电路 本节书摘来自华章计算机《逻辑与计算机设计基础（原书第5版）》一书中的第3章，第3.8节，作者：（美）M.莫里斯·马诺（M. Morris Mano）著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《数字逻辑设计与计算机组成》一 导读 本书内容包括存储器组织、处理器核心和处理器组织结构，以及硬件支持的计算机安全等。由于技术的进步以及对高速和低功耗设计的需求改变了计算机组织结构的基础，因此本书尝试不仅提供简单的实例用于展示基本的设计概念，而且揭示对现代计算机设计目标的理解。
《数字逻辑设计与计算机组成》一 3.4 减法器 本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第3章，第3.4节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
《数字逻辑设计与计算机组成》一练习 本节书摘来自华章出版社《数字逻辑设计与计算机组成》一 书中的第3章，练习章节，作者：［美］尼克罗斯·法拉菲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。