数字逻辑与数字电路_2

1、数字逻辑与数字电路数字逻辑与数字电路作者：徐晓光 l 逻辑函数的化简、优化是一个具有重大实际意义的问题，其应用十分广泛。例如：数字电子电路的优化、可编程逻辑器件的设计、IP路由表化简等，都涉及到逻辑函数的化简问题。因此，长期以来人们对逻辑函数的化简问题进行了深入系统的研究，得到了许多卓有成效的研究成果，产生了许多成熟有效的逻辑函数化简方法；如卡诺图法、 Q-M法、锐积法等。l 近年来，随着电子计算机的普及和应用，使得逻辑函数的化简问题可以在计算机的帮助下得以进行。计算机已经成为解决逻辑函数化简优化问题、进行数字逻辑分析和设计的有力工具。l 下面我们将对逻辑化简的理论和方法进行详细的介绍。2.1

2、 l 2.1.1 有关的专业术语l 1.（Sum Of Products）l 我们将表示为乘积项乘积项之和和形式的逻辑表达式称作积之和积之和（SOP）。 如：f(A,B,C)=ABC+AC+BCl 2.（Product Of Sums）l 我们将表示为和项和项之乘积乘积形式的逻辑表达式称作和之积和之积（POS）。 如：(A,B,C)= f(A,B,C)=(A+B+C)(A+C)(B+C)乘积项的和的形式乘积项的和的形式和项的乘积的形式和项的乘积的形式l 3.最小项l 所谓是由逻辑表达式中所有输入变量字母组成的乘积项，每一个字母至多出现一次。 如逻辑函数为 f(A,B,C,D) ，则ABCD，A

3、BCD等都是最小项。l 4.最大项l 所谓是由逻辑表达式中所有输入变量字母组成的和项，每一个字母至多出现一次。l 如逻辑函数为f(A,B,C,D)，则A+B+C+D， A+B+C+D都是最大项。：任何一个逻辑表达式都可以表示为最小项之和的形式，或者表示为最大项之积的形式。l 例如： f(A,B,C,D)(SOP)=ABC+AC+BC =ABC(D+D)+A(B+B)C(D+D)+(A+A)BC(D+D) =ABCD+ABCD+ABCD+ABCD+ABCD+ABCD +ABCD+ABCD+ABCD+ABCD l 再者： f(A,B,C,D)(POS)=(ABC+AC+BC) =(A+B+C+D)

4、(A+B+C+D)(A+B+C+D)(A+B+C+D) (A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D) (A+B+C+D)(A+B+C+D)l 5.关于最小项和最大项的讨论l （1）我们将逻辑函数的最小项，用mi的形式来表示。其中下标i是区分、表征最小项的10进制数字，我们将某一个最小项按字母顺序从左到右排列，将取的取值 、将取的取值 ，这样就可以得到一个表征该最小项的二进制数。如果将该最小项中的各个字母按这个二进制数取值代入，该最小项恰好取值为1。最后把这个二进制数转换成相应的十进制数，就是i的值。l 例如ABCD= m15 ，ABCD= m10 等。l （2）我们

5、将逻辑函数的最大项，用Mi的形式来表示。其中下标i是区分、表征最大项的10进制数字，我们将某一个最大项按字母顺序从左到右排列，将取的取值 、将取的取值 ，这样就可以得到一个表征该最大项的二进制数。如果将该最大项中的各个字母按这个二进制数取值代入，该最大项恰好取值为0。最后把这个二进制数转换成相应的十进制数，就是i的值。l 例如A+B+C+D= M0 ， A+B+C+D= M5 等。l （3）根据最小项和最大项的定义、狄.摩根定律，有： Mi= (mi )(以POS形式表示)，mi = (Mi) (以SOP形式表示) l （3）定理1 一个逻辑表达式中所有最小项之和恒为1。(含有n个字母的逻辑表

6、达式中共有2n 个最小项) 即 (2-1)l n为逻辑表达式中所含字母的个数。l （4）定理2 一个逻辑表达式中所有最大项之积恒为0。(含有n个字母的逻辑表达式中共有2n 个最大项) 即 (2-2)l n为逻辑表达式中所含字母的个数。2101nkkm2100nkkMl （5）将任一个逻辑表达式表示成“积之和”形式的方法，就是把逻辑函数所包含的最小项找出来，相加即可。l 具体的方法可以按使逻辑表达式取值为1的原则，将对应最小项的二进制数找出来，得到该逻辑函数中所包含的最小项。l 因此，一个逻辑表达式也可以用f(A,B,C)=mi 来表示，如： f(A,B,C)=m0+ m3 + m5 + m6

7、等。l （6）将任一个逻辑表达式表示成“和之积”形式的方法，就是把逻辑函数所包含的最大项找出来，相乘即可。l 具体的方法可以按使逻辑表达式取值为0的原则，将对应最大项的二进制数找出来，得到该逻辑函数中所包含的最大项。l 因此，一个逻辑表达式也可以用 f(A,B,C)=Mj来表示，如： f(A,B,C)=M0 M3 M5 M10等。l (7)另外根据定理1，我们得到： 即mi +mj= 1 （2-3）l 式中i为逻辑表达式中最小项的下标，j为所有下标中除最小项之外其余的下标。l 由逻辑代数运算的公式（1-21）可知， mj= (mi) （2-4）l 再由f(A,B,C)=mi =Mj ，得：Mj

8、 =(mi)。 由式（2-4）得：Mj= (mj) = mj ， 也即Mj = mj 。l 因此有结论如下：。1120nkkjimmml 例1： f(A,B,C)(SOP)= ABC+AC+BC =ABCD+ABCD+ABCD+ABCD+ABCD +ABCD+ABCD+ABCD+ABCD+ABCD =m15+ m14 + m7 + m6 + m3 + m2 + m13 + m12 + m5 + m4 l 则同时有： f(A,B,C)(POS)=M0M1M8M9M10M11 =(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D) (A+B+C+D) (A+B+C+D) 例2：

9、 Y =m(1,5,7,8,12,15) =M(0,2,3,4,6,9,10,11,13,14) 是一个表示逻辑函数的表格。将输入变量横向与纵向排列，便可画出表格，如右图所示。l 三、四变量卡诺图中输入变量横向与纵向排列的规律，是相邻两行（列）之间仅有一个变量的取值不同。2.1.2 ABC00 01 11 10010 1 3 24 5 7 6十进制数值a) 3变量的卡诺图ABCD00 01 11 1000011110b) 4变量的卡诺图0 1 3 24 5 7 612 13 15 148 9 11 10十进制数值l 表格中的每一个小格子，对应于一个最小项或最大项。l 根据逻辑表达式，将各个格子

10、填入数值：对于SOP形式的表达式，若包含该最小项，则在相应格子中填入“1”；若不包含该最小项，就填入“0”（或者空白也可）。l 或者对于POS形式的表达式，若包含该最大项，则在相应格子中填入“0” （或者空白也可）；若不包含该最大项，就填入“1”。l 这样就得到了表示该逻辑函数的卡诺图。l 例如Y=ABC+AC+BCD的卡诺图如图2-2所示。图2-2 卡诺图的填写CDAB00 01 11 100001 11100 1 3 24 5 7 68 9 11 1012 13 15 140 1 1 10 0 1 10 0 1 10 1 0 0Y=ABC+AC+BCDl 1.合并最小项（最大项）的规律l

11、由于三、四变量卡诺图中相邻两行（列）之间仅有一个变量 的 取 值 不 同 ， 根 据 逻 辑 代 数 的 公 式 A + A = 1 、AB+AC=A(B+C)和AA=0、(A+B)(A+C)=A+BC知：卡诺图中横向或纵向的最小项或最大项可以合并成一项。进而，卡诺图中的的或小方块可以合并成一项。l 为了看清楚最小项（最大项）之间的合并关系，我们将能够合并成一项的小方块圈在一个圈内。l 2.1.3 l 应当注意：处于一行（列）的两端时，相当于相邻。排成一行（列）的四个小方块等价于相邻的大方块。l 上述情形如图2-3、2-4和2-5所示。图2-5 八个最小项的合并l 2.l （1）（Implic

12、ant）l 在逻辑函数中，如果若干个最小项（最大项）能够合并成一项，则称这些最小项（最大项）构成了一个。如：卡诺图中任意2个相邻的最小项、任意相邻的4个最小项、任意相邻的8个最小项等。l 最小项（最大项）本身也是一个蕴涵，它是最小的蕴涵。l （2）蕴涵的关系l 在逻辑函数中，根据逻辑代数的吸收律，如果一个蕴涵X能够被另一个蕴涵Y所吸收掉，则称“蕴涵X于蕴涵Y”。l 如：ABCD和ABCD 皆包含于AD 中。l 在卡诺图中，如果蕴涵X包含于蕴涵Y，则蕴涵X的方块就被包含于蕴涵Y的方块之中，如图2-6所示。l 在一个逻辑函数中，如果某个蕴涵是不能被其它任何蕴涵所包含的，则称该蕴涵为，简称PI。l

13、例如在图2-7中，存在4个蕴涵：ABCD、ABCD、ABCD和BCD，以及2个质蕴涵：BCD 和 ABCD 。l （3）（Prime Implicant）l 例如在下图中，存在5个质蕴涵：ABC、ACD、ABC、ACD和BD，但仅有4个必要质蕴涵：ABC、ACD、ABC和ACD。组成质蕴涵 BD的4个最小项，全部被其它的PI所包含，故它不是EPI。l（4）（Essential Prime Implicant）l在一个逻辑函数中，如果某个质蕴涵（PI）中包含有至少一个其它质蕴涵所不包含的最小项（最大项），则称该质蕴涵为，简称EPI。l 3.3.（Dont care terms）l 这种情况下，在

14、对逻辑函数进行化简时，那些在实际问题中根本不会出现的输入状态（也即最小项或最大项），就被称作（有些书上称作）。l 在实际问题中，经常会遇到这样一类情况：逻辑函数的某些特定的输入状态，是肯定不会出现的。或者说为逻辑函数的化简，加上了某种。l 我们在卡诺图对应随意项的小方格中，填入“x”。其意义是既可以取值“1”，也可以取值“0”。l 在用卡诺图化简逻辑函数时，随意项既可以以“1”参与化简，也可以以“0”参与化简。这是由于这些最小项（最大项）是在实际问题中根本不会出现的，所以它们无论取“0”还是取“1”都不会对原问题造成影响。l 究竟随意项取“1”还是取“0”，是以实现逻辑化简结果的最优化来决定的

15、。l 图2-9是考虑随意项时，逻辑函数化简的两个实例。l 随意项在函数中一般用di表示，例如某一带有随意项的逻辑函数表示为： f=(m1+m2+m7+m10)+(d5+ d6+d15)=m(1,2,7,10)+ d(5,6,15)l 4.逻辑函数化简的目标l 用逻辑门电路实现某一逻辑函数时，经常是采用“与非门”电路来实现的。通过分析可知，对于SOP形式的逻辑表达式，可以用2级与非门电路完成其逻辑功能。l 例如：Y=ABC+ABD+BCD=(ABC+ABD+BCD) =(ABC)(ABD)(BCD)l 目前，用2级门电路来实现一个逻辑函数仍然是最为常用的逻辑设计方法。l 由于本书仅局限于用2级逻

16、辑门电路来实现逻辑功能，不讨论用多级门电路实现的逻辑电路的化简问题；因此逻辑函数化简的目标就是：l （1）化简结果所得SOP形式的逻辑表达式中的乘积式项数越少越好。（2）在乘积式项数相同的情况下，各项所包含的字母数目越少越好。l 对于POS形式的逻辑表达式，情况与此类似。l 例如：ABC+ABD+ACD的化简结果，就优于 ABD+ACD+BCD+ABCD的化简结果。l 5. 利用卡诺图手工地化简逻辑表达式，有着以下几种方法：l （1）卡诺图化简算法1 从卡诺图的质蕴涵中，首先选取其中最大的合并项（即卡诺图中最大的圈）。 从未被选取质蕴涵中，选取最大的合并项（即卡诺图中最大的圈）。但要遵循如下的

17、原则：选取的质蕴涵，必须包含至少一个未被已经选取质蕴涵用过的新的最小项（最大项）。 重复步骤，直到卡诺图中的全部最小项（最大项）已经被选取的质蕴涵所用过。也即选取的质蕴涵完成了对逻辑函数的一个。 对选取的质蕴涵进一步分析，去除冗余的项。尽量使化简结果最简最优。l （2）卡诺图化简算法2 在卡诺图中首先选取出所有的。因为必要质蕴涵覆盖了至少一个其它质蕴涵无法覆盖的最小项（最大项），所以它们不可能由其它质蕴涵来替代；即必要质蕴涵是逻辑化简时必须选取的。 对于剩余的非必要质蕴涵，则应当采用尝试尝试、搜索搜索的方法，从中选出一些PI，完成逻辑函数的，达到最优化简的目的。l 显然，卡诺图化简算法2与卡诺

18、图化简算法1相比，是一种十分严谨但更为复杂的算法。l 如果将卡诺图化简算法2与卡诺图化简算法1相结合，就得到卡诺图化简的算法3。l （3）卡诺图化简算法3 在卡诺图中首先选取出所有的。 对于剩余的非必要质蕴涵，选取对应（即卡诺图中最大的圈）的质蕴涵。但要遵循如下的原则：选取的质蕴涵，必须包含至少一个未被已经选取质蕴涵用过的新的最小项（最大项）。 重复步骤，直到卡诺图中的全部最小项（最大项）已经被选取的质蕴涵所用过。也即选取的质蕴涵完成了对逻辑函数的一个覆盖。 对选取的质蕴涵进一步分析，去除冗余的项。尽量使化简结果最简最优。l 卡诺图化简算法3虽然没有第2种方法严谨，但操作起来更为简练。l 例2

19、-1用卡诺图化简逻辑表达式 f(A,B,C,D)=ABCD+ ABCD +ABCD +BCl 解：画出4变量的卡诺图，填入真值为1的最小项，合并化简如图2-10所示。l 化简结果为：f(A,B,C,D)=ABCD+ ABD +BCl 例2-2用卡诺图化简逻辑表达式 f(A,B,C,D)=ABC+ ABCD +ABCD +ABCD+ADl 解：卡诺图化简结果如图2-11a所示。可以看出，2-11b中四个小方块的合并项是冗余的。l 例2-3用卡诺图化简逻辑函数 (A,B,C,D)=m(1,2,3,4,5,6,8,9,11,12,13,14,15,)l 解：化简结果如图2-12所示： f(A,B,C

20、,D)=AC+BD+CD+AD+ABCl 例2-4某逻辑函数的卡诺图见下图a，化简结果如下图b所示。l 什么是SOP和POS?l 什么是最小项和最大项?l 如何找出逻辑函数中所包含的最小项?l 逻辑函数中所包含的最小项和最大项与函数的卡诺图之间存在什么关系？l 3变量和4变量的卡诺图，相邻的两行（列）有什么规律？l 为什么卡诺图中相邻两个小方格中最小项可以合并？l 为什么是相邻的4个、8个最小项能够合并，而不是相邻的6个最小项？l 卡诺图中相邻最小项合并后的结果如何确定?l 卡诺图中为什么看起来不是相邻、分处于一行（列）的两端，或分处于四角的最小项实际上也是相邻的?l 什么是蕴涵？什么是质蕴涵

21、？什么是必要质蕴涵？l 什么是蕴涵的包含关系？l 什么是随意项？它也被称做什么？l 为什么随意项既可以当作真值1？也可以当作真值0?l 在考虑随意项时，EPI的条件是什么？l 什么是逻辑函数的一个“覆盖”？l reducel optimizel Sum Of Productsl Product Of Sumsl canonical forml minterml maxterml Karnaugh mapl cover,minimal coverl dont care termsl Essential Prime Implicantl 2.1.4 l 与四变量的卡诺图类似，我们也可以画出五变量和

22、六变量的卡诺图来。如图2-13和图2-14所示。l 与四变量卡诺图时一样，五、六变量卡诺图中“相邻”的最小项（最大项）也可以合并化简。但五、六变量卡诺图中的“相邻”关系判别要比四变量卡诺图来得复杂。l 实际上，任何卡诺图中最小项（最大项）的“相邻”关系，就是通过它们彼此仅相差一个变量来决定的。如：ABCDE和ABCDE就是相邻的。根据这个原则，我们就容易找出五、六变量卡诺图中的“相邻”关系了。l 通过分析，我们发现可以将五变量卡诺图划分成2个四变量卡诺图。每个四变量卡诺图中的合并化简规律，与前面所述的一样。而这2个四变量卡诺图上，对应位置的小方格是“相邻”关系。如图2-15所示。指逻辑上的相邻

23、，而非几何上的相邻l 图中，字母A、BO、P是用于标示小方格的符号。在2个四变量卡诺图中，写有相同字母的两个小方格是相邻的。l 在划分出的2个四变量卡诺图中，如果具有对应位置相同的质蕴涵(PI)，则它们可以进一步合并化简。如图2-16所示。l 同理，六变量卡诺图也可以划分成为4个四变量卡诺图。而位于行（列）相同、列（行）相应位置上的小方格，彼此两两相邻。Y=BDE+BCEFl 如果在2个或者4个划分出的四变量卡诺图中，具有对应位置相同的质蕴涵(PI)，则它们可以进一步合并化简。如右图所示。l 2.1.5 l 最大项函数是“和之积（POS）”形式的逻辑函数。其特点是各和项取值为0时，函数值为0。

24、各和项对应于卡诺图的最大项。l 所以当应用卡诺图化简最大项函数时，应当对图中真值为0的最大项进行合并化简；并将化简结果中各变量取非后，以POS形式输出即可。l 最大项逻辑函数的化简，如图2-18所示。l 2.2 l 随着逻辑函数的输入变量的增加，卡诺图的尺寸将会随之而增大。为此，MEV卡诺图（Map Entered Variable）技术应运而生。所谓就是将某些输入变量映射到卡诺图的真值中，这样就能够用较小的卡诺图表示和化简较多输入变量的逻辑函数。如：用44的卡诺图来处理5变量或6变量的逻辑函数问题等。因此，MEV卡诺图也被称为。l 下面我们将对MEV卡诺图的理论进行详细深入的分析研究。l M

25、EV卡诺图的真值，就是填写在MEV真值表中的内容。前面我们知道，普通卡诺图中的真值只有3种情况：0、1和x。而在映射变量时，情况就复杂多了。l 1.一个映射变量的情况l 所谓一个映射变量，就是将某一个输入变量作为真值内容的一部分，填写到真值表中；从而使MEV卡诺图的尺寸减小为少去一个变量的卡诺图尺寸的逻辑化简方法。l 为了分析的简单起见，我们以五变量的逻辑函数为例，如图2-19所示。l 分析可知，五变量卡诺图中每2个横向相邻的小方格，映射于MEV卡诺图中的一个小方格。例如：五变量卡诺图中的m0、m1方格，映射到了MEV图中第一行的左数第一个方格；五变量卡诺图中的m4、m5方格，映射到了MEV图

26、中第一行的右数第一个方格。其它以此类推。l 由于表示逻辑函数时，五变量卡诺图中每个小方格都有3种可能的取值： 、 和 ；所以映像到MEV图中后，MEV图中小方格的取值就有9种情况(33=9)。分析后我们知道，这9 种情况为：0、1、x、E、E、xE、xE、E+xE、E+xE。l 也就是说，此时MEV卡诺图中所填写的真值，应当为：0、1、x、E、 xE、xE、E+xE、E+xE 这9种值中的某一个。l 这里取值x表示真值可以取：0、1、E、 E这4种值的任意之一。取值xE表示真值可以任意取：0、E这2者之一。取值xE表示真值可以任意取：0、E这2者之一。l 其他情况以此类推。l 例2-5画出五变

27、量逻辑函数 f =m(7,10,16,17) +d(23)的四变量MEV图。图2-20 例2-5的图l 2.2.2 l 1.MEV卡诺图化简的法则l 除了随意项之外，以SOP形式的逻辑函数，MEV卡诺图中所有填写不为0真值（对于POS形式的逻辑函数，则是不为1真值）的方格，均对应原卡诺图中的一个最小项（最大项），必须在化简过程中被覆盖掉。l 填写有相同真值的相邻小方格可以合并化简。小方格的相邻关系与普通卡诺图的完全一致。l 填写为1真值的方格，在合并化简时，可以视为E+E ，或 F+F ，或EF+EF+EF+EF参与化简。l 在合并化简POS形式的逻辑函数时，填写为0真值的方格，可以视为EE，

28、或FF，或(E+F)(E+F)(E+F)(E+F)参与化简。l 2.一个映射变量MEV卡诺图化简的步骤l 对含有真值E的方格进行合并化简。l SOP函数时，填写1真值的方格，可以参与合并（相当于随意项）。合并化简的结果为f(A,B,C,D) E形式。f(A,B,C,D)为仅含字母A、B、C、D的积项，如：ABCD等。 l POS函数时，填写0真值的方格，可以参与合并（相当于随意项）。合并化简的结果为g(A,B,C,D)+E形式。 g(A,B,C,D)为仅含字母A、B、C、D的和项，如：A+B+C+D等。l 对含有真值E的方格进行合并化简。l SOP函数时，填写1真值的方格，可以参与合并（相当于

29、随意项）。合并化简的结果为f(A,B,C,D) E形式。f(A,B,C,D)为仅含字母A、B、C、D的积项，如：ABCD等。l POS函数时，填写0真值的方格，可以参与合并（相当于随意项）。合并化简的结果为g(A,B,C,D)+E形式。g(A,B,C,D)为仅含字母A、B、C、D的和项，如：A+B+C+D等。l 对填写1（或0）真值的方格进行合并化简。l 如果填写1（或0）真值的方格，已经被充当E和E各用过了至少一次，则该方格就是已经被覆盖了；这时该方格相当于随意项。否则，最后该方格还必须以真值1（或0）用至少一次。l 对于SOP函数，E+xE、E+xE可以作为1真值参与化简。如果它们已经作为

30、E、E用过了，则此时它们相当于随意项；否则，它们必须作为真值1参与化简。l 对于POS函数，xE、xE可以作为0真值参与化简。如果它们已经作为E、E 用过了，则此时它们相当于随意项；否则，它们必须作为真值0参与化简。l 实际上合并化简步骤中、的顺序是可以交换的，不同的次序可以导致优化结果的不同。l 例2-6用MEV图化简逻辑函数 Y=m(7,10,16,17,25,26,27)+d(23)l 解：画出逻辑函数的MEV图如图2-23所示。 l 我们首先对真值为E的方格化简，将与之相邻的、1真值的方格充当E参与化简，得BCDE。l 而后对真值为E的方格化简。与之相邻的、1真值的方格又充当E参与化简

31、，得ABCE。另一个真值为E的方格与真值为xE的方格合并，得BCDE。l 对于那个既作为E用过、又作为E用过的真值为1的方格，就不必再考虑了。l 而另一个未用过、真值为1的方格,直接写出得ABCD。l 当输入变量数目较多时，采用卡诺图法对逻辑函数进行化简就不太实用了。因为当输入变量数目较多时，通过卡诺图来寻找PI和EPI就不再容易了。而Q-M(Quine-McClusky)法却能够很好地解决任意多个输入变量的逻辑函数化简问题；同时Q-M法还是一种适宜于用计算机程序实现的逻辑函数化简法。因此在逻辑函数化简技术领域中，Q-M法占有着十分重要的地位。l2.3 l Quine-McClusky法通过一

32、系列的步骤，最终求得函数的最优化简结果。其程序流程如图2-28所示。l 2.3.1 l 1.使用Q-M法时蕴涵和质蕴涵的表示方法l 当使用Q-M法化简逻辑函数时，我们用一个二进制数(字符串)来表示最小项（或最大项）。如：将ABCDEFG表示为1101011、ABCDEFG表示为0101010等。l 如果两个表示最小项（最大项）的字符串仅在某一位上数值相异，而其它各位数值都相同；则这两个最小项（或最大项）可以合并成一个蕴涵。我们用x替换掉相异的那一位，就得到了表示该蕴涵的字符串。例如：11011001与11001001合并的结果为110 x1001。l 同理，两个表示蕴涵的字符串如果仅在某一位上

33、数值相异，而其它各位数值都相同；则这两个蕴涵可以合并化简成另一个新的蕴涵。我们用x替换掉相异的那一位，就得到了表示化简结果的字符串。如：110 x1001与110 x1000合并的结果为110 x100 x。l 也就是说，在使用Q-M法时，我们可以用由0、1和x组成的字符串来表示函数的蕴涵和质蕴涵。l 2.用Q-M法求PI和EPI的步骤如下：l 求出逻辑函数所有的最小项（最大项）。l 将逻辑函数的最小项（最大项）用相应的二进制数（字符串）表示。l 分组：将表示逻辑函数最小项（最大项）的二进制数，按它们中所含1的数目分别放置在不同的组中。l 如：第0组中是不含1的二进制数、第1组中是含有一个1的

34、二进制数、第2组中是含有两个1的二进制数对放在相邻两个组中的字符串逐位比较。如果它们除了在某一位数值不同外、其它各位数值均相同，则它们就能够合并成一个新的蕴涵。l 对于能够合并的最小项（最大项）做上标记（一般是用打勾表示）。l 第一次生成的分组表称为第1级分组表。l 将第1级分组表中所有带标记字符串的合并结果放入第2级分组表中：l 分属于第1级分组表中两个相邻组、且两个字符串仅有某一位相异时，用x将相异的那一位替换掉，即得到表示两个最小项（最大项）合并结果的蕴涵的字符串。并对该蕴涵所覆盖的最小项（最大项）进行记录。l 然后将新产生的字符串按照所含1的数目分组放入第2级分组表。l 如果属于前一级

35、分组表的某些字符串不带标记，则也将它放入到后一级分组表中。l 对放在相邻两个组中的字符串逐位比较。如果它们能够进一步合并成新的蕴涵，则为它们加上标记。l 按照步骤中的方法，由前一级分组表的合并结果得到后一级分组表，第n次生成的称为第n级分组表。如此进行，直到所有字符串全都无法进一步化简为止。l 此时表中存放的字符串就是函数的质蕴涵PI了。l 对已经获得的质蕴涵PI进行检查。如果一个PI中所覆盖的某个最小项或最大项（必须不是随意项），是其它PI所没有覆盖的；也即存在着由该PI单独覆盖的某个最小项（最大项）时，这个PI就是必要质蕴涵，即EPI。l 在分组表中将找出的EPI做上标记（一般是用*号将单

36、独覆盖的最小项或最大项标出）。l 至此，逻辑函数的EPI的求解完成。l 例2-8求逻辑函数f=m(9,10,11,14,15,25,26,27,30,41,57,61)的全部PI和EPI。l 解：如图2-26b所示，将真值表中的二进制数分组得第1级分组表。l 第1级分组表中的内容合并、分组后得第2级分组表，如2-26c所示。l 如：001001与001011合并得0010 x1, 001001与011001合并得0 x1001, 001001与101001合并得x01001,001010与001011合并得00101x, 001010与001110合并得001x10, 001010与01101

37、0合并得0 x1010, 101001与111001合并得1x1001, 111001与111101合并得111x01等。l 第2级分组表中的内容合并、分组后得第3级分组表，如2-29d所示。l 如：0 x1001与1x1001合并得xx1001, 0010 x1与0110 x1合并得0 x10 x1, 00101x与01101x合并得0 x101x, 001x10与011x10合并得0 x1x10, 001x10与001x11合并得001x1x等。l 列出质蕴涵表，即将每个PI所覆盖的最小项情况用表格显示出来，如图2-27所示。l 检查质蕴涵表，找出被某个PI单独覆盖的最小项，为它们打上*号

38、。表中凡是有*号的就是必要质蕴涵EPI。现在EPI为：xx1001,0 x1x10,001x1x和111x01。l 2.3.2 l 所谓函数的，就是用最少的PI来覆盖该函数所有的最小项（最大项）。l 分析可知：必要质蕴涵EPI是必须选择的PI；而对于剩下的非必要质蕴涵，选择哪些PI能够构成函数的最优覆盖，则不是十分明显的。l Q-M化简法提供了求解函数最优覆盖的一套完整方案，为实现函数的最优化简提出了行之有效的方法。l Q-M化简法的算法流程如下：l 步骤1：从质蕴涵表生成简化质蕴涵表l 从质蕴涵表将EPI放入到中，把剩余的非必要质蕴涵PI放入到中。l 从简化质蕴涵表中，将被化简结果表中PI所

39、覆盖的最小项（最大项）全部除去。这时简化质蕴涵表存放的是尚未被化简结果覆盖的最小项（最大项）的情况。l 步骤2：从简化质蕴涵表中除去劣势PIl 在简化质蕴涵表中，如果存在某一PIi ，（将被化简结果表中PI所覆盖的最小项或最大项除去后）其所覆盖的最小项（最大项）在另一个PIj中全部能够找到、且PIj中最小项（最大项）的数目多于PIi ；则PIi 相对于PIj就是PI。l 由于PIj覆盖的结果也一定会覆盖PIi ，所以PIi 可以被PIj 取代。故我们找到劣势PI后，把它们从简化质蕴涵表中除去。l 步骤3：循环操作l 当除去劣势PI后，就可能会有“某个PI中所覆盖的某些最小项（最大项），没有被其

40、它PI所覆盖”的情况出现；也即这个PI为EPI。l 将找到的新的EPI放入到化简结果表中，余下的PI留在简化质蕴涵表中。然后跳转至步骤1的处。l 如此循环工作，直到简化质蕴涵表为空，完成函数的化简为止。l 这样的化简过程实现了函数的最优化简，化简结果存放在化简结果表中。l 步骤4：从简化质蕴涵表中选取最低价格PI l 在上述的化简过程中，如果某一次循环时EPI不存在、或者找不到劣势PI，化简工作就无法继续下去了。这时可以采用选取最低价格PI的方法解决之。l 所谓PI，就是指在物理实现上价格最低的PI，也即字符串中包含x数目最多的PI。l 如果出现了多个字符串中x数目相同的情况，则可以任意选择其

41、一，作为最低价格PI。l 将选取的最低价格PI放入到化简结果表中，更新简化质蕴涵表。然后跳转至步骤1的处。l 如此循环工作，直到简化质蕴涵表为空，完成函数的化简为止。l 应当指出，选择最低价格PI的方法，不能保证一定会得到最优的函数覆盖，只能保证得到较优的化简结果。如果要得到最优的函数覆盖，就要使用搜索的方法，这样显然会增加解决问题的难度。例2-9已知质蕴涵表如图2-29所示，求函数的最优化简结果。图2-29 例2-9的质蕴涵表EPIl 解：图2-30、图2-31、图2-32是利用Q-M法求最优覆盖的过程。l 1）首先将EPI放入化简结果表中，求得简化质蕴涵表，如图2-30所示。l 2）然后，

42、检查简化质蕴涵表中是否存在劣势PI，若有则消去之。由于现在不存在劣势PI，所以选择一个最低价格PI，放入化简结果表中；再从余下的PI中消去被该最低价格PI所覆盖的最小项，如图2-31所示。l 3）从简化质蕴涵表中消去劣势PI：xx001。l 4）从简化质蕴涵表中查找EPI，如图2-32所示。除去除去1x00 x中所中所包含的最小项包含的最小项化简结果1x00 x选取的最低价格PI化简结果除去除去x100 x中所中所包含的最小项包含的最小项劣势PI找到EPIl 5）将EPI放入化简结果表中，更新简化质蕴涵表，如图2-33所示。l 6）从简化质蕴涵表中消去劣势PI：0001x和1x0 x1。l 7

43、）从简化质蕴涵表中查找EPI，如图2-34所示。l 8）将EPI放入化简结果表中，更新简化质蕴涵表。此时化简结果表中的PI已经完成了函数的覆盖，所以函数的优化过程到此结束，化简结果为1x00 x、x100 x、x00 x1、0 x010和110 xx。劣势PI劣势PI被0 x010和110 xx覆盖l 在实际工作中，除了单输出函数外，还会遇到多输出函数化简的情况。所谓，就是在一组输入变量的情况下，同时存在多个函数输出的问题。这时某些逻辑门电路可以被多个输出函数所共享，整个电路的化简工作应当针对所有的输出来进行。电路的化简优化应当是一个，这时电路的最小实现是指用最少的物理电路来实现多个输出函数的

44、逻辑功能。2.6l 例如图2-41是3个输出函数的卡诺图，其全局优化的结果应为：Yc=ACD，Yb=ACD+ABC，Ya=ACD+ACDl （其他内容略去）l 2.7 是由作者本人研制编写的、专门用于逻辑函数化简优化的计算机软件。l 卡诺图软件具有优异的性能，目前国内尚未见有同类软件的报导。l 卡诺图软件具有功能完备、使用方便等许多优点，它既能够用于解决逻辑设计的实际问题，也能够用于数字逻辑课程的辅助教学。在电脑日益普及的今天，卡诺图软件为读者学习、应用数字逻辑知识提供了极好的帮助。l 在本书中附带有卡诺图软件2.0光盘，以供安装使用。l 2.7.1 l 卡诺图软件的主要功能有：l 1）可以进

45、行3、4、5、6变量逻辑函数的卡诺图化简。l 2）具有MEV卡诺图化简功能。l 3）提供Q-M(奎因表)化简功能l 4）具有锐积法、相容法化简功能。l 5）可以对“多输出函数”进行化简。l 6）具有多种输入功能，包括真值表、最小项、最大项和表达式输入功能等。l 其中表达式输入功能，允许用户直接用逻辑表达式，来输入待优化的逻辑函数。l 7）支持POS、SOP、正函数和反函数（有时采用正函数比采用反函数化简结果更优，有时则正好相反）等各种函数形式。l 8）单步操作模式，能够清楚地显示出逻辑化简的每一中间步骤。l 图2-42是卡诺图软件的操作界面图。l 2.7.2 l 如图2-43所示，卡诺图软件的

46、操作界面包括菜单栏、工具条、真值输入区、化简图示区、化简结果输出文本框、公式输入文本框、函数形式选择框等。 l 卡诺图软件的各种控件功能如下：l 1.菜单栏l 文件：可执行装入逻辑化简的例子、结束程序等操作。l 设置：可选择程序工作于三元变量、四元变量、五元变量、六元变量、多输出函数、奎因表和锐积/相容法等不同的工作状态。l 输入输出：可执行表达式输入、选择SOP或POS函数形式和执行全1真值输入、全0真输入等操作。l 运行：可执行函数化简、单步化简和清除等操作。l 帮助：可查看软件的帮助文件、获取软件的版本信息和作者信息等。l 2.工具条l 工具条提供了软件各种操作的快捷手段，工具条中各按钮

47、的功能如图2-44所示。l 3.真值输入区l 卡诺图软件提供有多种方法来完成真值输入的任务。利用鼠标直接点击真值输入区中的真值方格，就是一种常用的真值输入方法。此时，用鼠标左键点击某一真值方格，就可以改变方格中的值，从空(代表0值)变到1，从1变到0，从0变到x(当“带约束条件”被选中时)。l 当按下Ctrl+Z键后，可以直接查看到各个方格所对应最小项(最大项)的数值。因而能够按逻辑函数的最小项(最大项)形式来输入该函数。l 4.化简图示区l 当函数输入完毕后进行逻辑化简时，在化简图示区我们可以看到函数的化简结果图。化简结果中的每一个质蕴涵PI，都被一个彩色图元所表示了。加上软件具有查看化简结

48、果的单步功能，因此软件显示的化简结果具有非常直观、生动的效果。l 5.化简结果输出文本框和表达式输入文本框l 化简结果输出文本框用于显示化简结果的逻辑表达式。卡诺图软件支持SOP和POS的函数形式。在逻辑表达式中，卡诺图软件“!”来表示逻辑函数的“非”逻辑。l 利用表达式输入文本框可以直接输入函数的逻辑表达式。表达式输入时允许使用多重小括号。输入完毕后回车即提交输入的内容。l 例如可以输入：ABCD+(!A!C+CD)(!B+D)等。其中!X表示 X。l 6.函数形式选择框l 卡诺图软件不但支持SOP和POS函数形式，还支持正函数和反函数形式。当选择反函数形式时，软件按输入真值表的反函数形式来

49、进行逻辑化简。l 2.7.3 l 例2-10 化简逻辑函数f(A,B,C,D)=ABC+ACD+ABCD+ABCD 。l 分析可知函数由最小项ABCD、ABCD、ABCD、ABCD、ABCD和ABCD组成。l 用鼠标点击真值输入区中相应的方格，完成函数输入工作。然后按“化简”按钮，化简图示区中就会显示出化简结果图，同时从化简结果文本框中读到化简结果的逻辑表达式：!B!C+!CD。l 以上化简过程，如图所示。l 例2-11 化简逻辑函数f(A,B,C,D)=m(1,3,4,6,7,8,15)+ d(0,5)l 首先按下ctrl+z键，真值输入区将显示出各个方格的最小(大)项数值。选择“带约束条件

50、”选项，点击鼠标使m0、m5方格中的值为x，使m1、m3、m4、m6、m7、m8和m15方格中的值为1。然后按“化简”按钮，即可完成函数化简，结果为：!AB+!AD+BCD+!B!C!D。l 以上化简过程，如图2-46 和图2-47所示。图2-46 查看最小项（最大项）图2-47 例2-11中的图l 例2-12 化简逻辑函数f(A,B,C,D)=A+B(ACD+D(A+BC)l 点击工具条上的“表达式输入”按钮，公式输入文本框将显示出来。将光标置于公式输入文本框中，用键盘输入A+B(!A!CD+!D(A+!BC)后，按回车即可。得到的化简结果为：A+B!CD。l 以上化简过程，如图2-48所示。图2-48 例2-12的图l 五变量和六变量的卡诺图是如何画出的? 图中相邻的两行(列)之间仍然是只有一个变量相异吗?l 五变量和六变量卡诺图逻辑化简时的“相邻”关系，是如何确定的?l 逻辑函数按最大项化简时与按最小项时的异同何在?l 什么是MEV？对于1个变量的MEV，1个小方格对应于普通卡诺图中的几个方格？l MEV化简的步骤是怎么样的？l 当变量数目较多时，应当采用何种方法进行逻辑化简？l 什么是劣势PI? 什么是最低价格PI？l 多输出逻辑函数逻辑化简时，应当按什么原则进行?l 卡诺图软件的