《逻辑函数优化》PPT课件.ppt

《《逻辑函数优化》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《逻辑函数优化》PPT课件.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 逻辑函数函数优化化逻辑函数常用的化函数常用的化简方法有：方法有：公式法公式法卡卡诺图法法列表法。列表法。2023/2/111一些概念一些概念因子：因子：与与项中包含的中包含的变量（包括原量（包括原变量和反量和反变量）称作因子。量）称作因子。蕴涵涵项：若某个与若某个与项在其因子的某种取在其因子的某种取值组合合下可以使整个下可以使整个逻辑函数函数输出出为1，则称称该与与项为该函数的函数的蕴涵涵项。质蕴涵涵项：若某个若某个蕴涵涵项不能再不能再进一步合并一步合并为另一个因子数更少的另一个因子数更少的蕴涵涵项，则称称该蕴涵涵项为质蕴涵涵项，即，即质蕴涵涵项中的任意一个因子都是中的任意一个因子

2、都是不能不能删除的除的，否，否则它将不再是有效的它将不再是有效的蕴涵涵项。2023/2/112一些概念一些概念覆盖：覆盖：若若蕴涵涵项的集合能包含使的集合能包含使给定函数等于定函数等于1的所有取的所有取值情况，情况，则称称该蕴涵涵项集合集合为该给定函数的覆盖。很明定函数的覆盖。很明显，函数函数f的所有最小的所有最小项的的集合就是能使集合就是能使f=1的一个覆盖的一个覆盖。一般而言，。一般而言，大大多数函数存在很多个不同的覆盖多数函数存在很多个不同的覆盖。覆盖定。覆盖定义了了一个函数的特定一个函数的特定实现。所有。所有质蕴涵涵项的集合也的集合也是一个覆盖。是一个覆盖。经过分析可以分析可以发现质蕴

3、涵涵项的覆的覆盖是最盖是最简的覆盖的覆盖。实质上，上，逻辑函数函数优化的化的过程就是求程就是求质蕴涵涵项覆盖的覆盖的过程。程。2023/2/113逻辑函数的化简逻辑函数的化简化简的意义化简的意义:节省元器件节省元器件,降低电路成本降低电路成本;提高电路可靠性提高电路可靠性;减少连线减少连线,制作方便。制作方便。最简与或表达式的标准：最简与或表达式的标准：1 1）所得所得与或与或表达式中，表达式中，乘积项乘积项（与项）数目最少；（与项）数目最少；2 2）每个乘积项中所含的每个乘积项中所含的变量数变量数最少。最少。针对某一逻辑式，反复运用逻辑代数公式消去针对某一逻辑式，反复运用逻辑代数公式消去多余

4、的多余的乘积项乘积项和每个乘积项中和每个乘积项中多余的因子，多余的因子，使函数式符合使函数式符合最简最简标准标准。化简中常用方法化简中常用方法:3.1 3.1 公式化简法公式化简法(1)并项法并项法=（A B）C+（AB）C在化简中在化简中注意注意代入规则代入规则的使用的使用(2)吸收法吸收法利用公式利用公式A+AB=A利用公式利用公式AB+AB=A例例:F=ABC+ABC+ABC+ABC=（AB+AB）C+（AB+AB）C=（A B）C+（A B）C=C=A+BC=(A+BC)+(A+BC)B+AC+D例：例：F=A+ABCB+AC+D+BC反演律反演律(3)消项法消项法利用公式利用公式AB

5、+AC+BC=AB+AC例例：F=ABCD+AE+BE+CDE=ABCD+(A+B)E+CDE=ABCD+ABE+CDE=ABCD+(A+B)E=ABCD+AE+BE(4)消因子法消因子法利用公式利用公式A+AB=A+B=AB+C(5)配项法配项法例：例：F=AB+AC+BC=AB+（A+B）C=AB+ABC利用公式利用公式A+A=1；A1=A等等例：例：F=AB+AC+BC=AB+AC+(A+A)BC=AB+AC+ABC+ABC=(AB+ABC)+(AC+ABC)=AB+AC2023/2/119课堂练习课堂练习 3.2 卡诺图化简法卡诺图化简法该方法是将逻辑函数用一种称为该方法是将逻辑函数用

6、一种称为“卡诺图卡诺图”的图形的图形来表示，然后在卡诺图上进行函数的化简的方法。来表示，然后在卡诺图上进行函数的化简的方法。卡诺图是一种包含一些卡诺图是一种包含一些小方块小方块的几何图形，图中每个的几何图形，图中每个小方块小方块称为一个单元，每个单元对应一个称为一个单元，每个单元对应一个最小项。最小项。两个两个相邻相邻的最小项在卡诺图中也必须是的最小项在卡诺图中也必须是相邻相邻的。卡诺图中相的。卡诺图中相邻的含义邻的含义:几何相邻性，几何相邻性，即几何位置上相邻，也就是左右紧即几何位置上相邻，也就是左右紧挨着或者上下相接；挨着或者上下相接；对称相邻性，对称相邻性，即图形中对称位置的单元是相邻的

7、。即图形中对称位置的单元是相邻的。1 卡诺图卡诺图的构成的构成 例例 三变量卡诺图三变量卡诺图ABC0100011110ABCm0ABCm1ABCm2ABCm3ABCm4ABCm5ABCm6ABCm7相邻性规则相邻性规则m1m3m2m7相邻性规则相邻性规则m2m0m1（对称）（对称）m4循环码循环码二、四、五变量卡诺图AB01010 12 3ABCD00011110000111100 1 3 24 5 7 6 8 9 11 1012 13 15 14相邻性规则 m3m5 m7 m6 m15 ABCDE00011110000001 01101001328911102425272611011110

8、11006754141513122223212030312928161719182 逻辑函数的卡诺图表示法逻辑函数的卡诺图表示法用卡诺图表示逻辑函数，只是把各组变量值用卡诺图表示逻辑函数，只是把各组变量值所对应的逻辑函数所对应的逻辑函数F的值，填在对应的小方格的值，填在对应的小方格中。中。（其实卡诺图是真值表的另一种画法）（其实卡诺图是真值表的另一种画法）ABC0100011110m3m5m700000111例：例：F（A，B，C）=ABC+ABC+ABC 用卡诺图表示为：用卡诺图表示为：3 在卡诺图上在卡诺图上合并合并最小项的最小项的规则规则当卡诺图中有最小项相邻时（即：有标当卡诺图中有最小

9、项相邻时（即：有标1的方格相邻的方格相邻)，可利用最小项相邻的性质，对最小项合并。可利用最小项相邻的性质，对最小项合并。规则为：规则为：（1）卡诺图上任何卡诺图上任何两个两个标标1的方格相邻，可以合为的方格相邻，可以合为1 项，并可消去项，并可消去1个变量。个变量。例：例：ABC010001111000000111ABC+ABC=BCABC+ABC=ACABCD00011110000111101111ABD（2）卡诺图上任何四个标）卡诺图上任何四个标1方格相邻，可合并为一项，并方格相邻，可合并为一项，并可消去两个变量。可消去两个变量。四个标四个标1方格相邻的特点：方格相邻的特点：同在一行或一列

10、；同在一行或一列；同在一田字格中。同在一田字格中。ABD例：例：ABCD00011110000111101111111CDABABCD0001111000011110111111111BD同在一行或一列同在一行或一列同在一个田字格中同在一个田字格中BDABCD000111100001111011111111ABCD000111100001111011111111（3）卡诺图上任何八个标）卡诺图上任何八个标1的方格相邻，可以并的方格相邻，可以并为一为一 项，并可消去三个变量。例：项，并可消去三个变量。例：ABCD000111100001111011111111ABCD00011110000111

11、1011111111BAABCD00011110000111101111 1111综上所述，在综上所述，在n个变量的卡诺图中，只有个变量的卡诺图中，只有2的的i次方个相次方个相邻的标邻的标1方格（必须排列成方形格或矩形格的形状）才方格（必须排列成方形格或矩形格的形状）才能圈在一起，合并为一项，该项保留了原来各项中能圈在一起，合并为一项，该项保留了原来各项中n-i个相同的变量，消去个相同的变量，消去i个不同变量。个不同变量。4 用卡诺图化简逻辑函数（化为最简与或式）用卡诺图化简逻辑函数（化为最简与或式）项数最少项数最少，意味着卡诺图中，意味着卡诺图中圈数圈数最最少少；每项中的变量数最少每项中的变

12、量数最少，意味着卡诺图中，意味着卡诺图中的的圈圈尽可能尽可能大大。最简标准：最简标准：例例将将F（A，B，C）=m（3，4，5，6，7）化为化为最简最简与或式。与或式。ABC010001111011111ABC010001111011111F=A+BC（最简）（最简）（非最简）（非最简）F=AB+BC+ABC化简步骤（结合举例说明）化简步骤（结合举例说明）=A(B+BC)+BC=A(B+C)+BC=ABC+BC=A+BC例例将将F（A,B,C,D）=m（0,1,3,7,8,10,13）化为最简与化为最简与 或式。或式。解：解：(1)由表达式填卡诺图由表达式填卡诺图;(2)圈出孤立的标圈出孤立的

13、标1方格方格;ABCD00011110000111101111111m13ABCD00011110000111101111111(3)找出只被一个最大的圈所覆盖的标找出只被一个最大的圈所覆盖的标1方格，并方格，并圈出覆盖该标圈出覆盖该标1方格的最大圈；方格的最大圈；(4)将剩余的相邻标将剩余的相邻标1方格，圈成尽可能少方格，圈成尽可能少,而且而且 尽可能大的圈尽可能大的圈.ABCDACDABDABCm8,m10m0,m1(5)将各个对应的乘积项相加，写出最简与或式。将各个对应的乘积项相加，写出最简与或式。例：例：ABCD000111100001111011111111111F(A,B,C,D)

14、=ABD+BD+AD+CDF(A,B,C,D)=ABCD+ACD+ABD+ABCF(A,B,C,D)=AC+ACD+ABD+BC+BCD一种特殊情况：一种特殊情况：ABC0001111001111111ABC0001111001111111F=AB+BC+ACF=AB+BC+AC得到两种化简结果，也都是最简的。得到两种化简结果，也都是最简的。化简中注意的问题化简中注意的问题(1)每一个标每一个标1的方格必须至少被圈一次的方格必须至少被圈一次;(2)每个圈中包含的相邻小方格数，必须为每个圈中包含的相邻小方格数，必须为2的整数次幂的整数次幂;(3)为了得到尽可能大的圈，圈与圈之间可以重叠为了得到尽

15、可能大的圈，圈与圈之间可以重叠;ABCD000111100001111011111111111ABCD000111100001111011111111蓝色蓝色的圈为多余的的圈为多余的.F=ABC+ACD+ACD+ABC+(BD)例如例如:(4)若某个圈中的所有标若某个圈中的所有标1方格，已经完全被其方格，已经完全被其它圈所覆盖，则该圈为多余的。它圈所覆盖，则该圈为多余的。方法方法:在卡诺图中合并标在卡诺图中合并标 0 方格，可得到方格，可得到反函数反函数的最简的最简与或与或式。式。例例:ABC010001111011110000F=AB+BC+AC 用卡诺图求用卡诺图求反函数反函数的最简与或式

16、的最简与或式常利用该法来求逻辑函数常利用该法来求逻辑函数F的最简与或非式的最简与或非式将上式将上式F上上 的非号移到右边，就得到的非号移到右边，就得到F的最简的最简与或非与或非表达式。表达式。F=AB+BC+AC逻辑函数化简的技巧逻辑函数化简的技巧（1 1）对较为复杂的逻辑函数，可将对较为复杂的逻辑函数，可将函函数分解数分解成多个部分，先将每个部分成多个部分，先将每个部分分别填入各自的卡诺图中，然后通分别填入各自的卡诺图中，然后通过过卡诺图对应方格的运算卡诺图对应方格的运算，求出函，求出函数的卡诺图。数的卡诺图。（2 2）对）对卡诺图进行化简卡诺图进行化简。ABABCDCD0000010111

17、11101000000101111110101 11 11 11 11 11 11 11 11 11 11 1ABABCDCD000001011111101000000101111110101 11 11 11 11 11 11 1ABABCDCD000001011111101000000101111110101 11 11 11 11 11 1=例：化简逻辑函数例：化简逻辑函数在某些实际数字电路中，逻辑函数的输出只在某些实际数字电路中，逻辑函数的输出只和一部分最小项有和一部分最小项有确定确定对应关系，而和余下的最对应关系，而和余下的最小项无关。余下的最小项无论写入逻辑函数式还小项无关。余下的

18、最小项无论写入逻辑函数式还是不写入逻辑函数式，都不影响电路的逻辑功能。是不写入逻辑函数式，都不影响电路的逻辑功能。把这些最小项称为把这些最小项称为无关项无关项。用英文字母。用英文字母d(dont d(dont care)care)表示，对应的函数值记为表示，对应的函数值记为“”。包含无关项的逻辑函数称为不完全确定的逻辑函数包含无关项的逻辑函数称为不完全确定的逻辑函数。不完全确定的逻辑函数及其化简不完全确定的逻辑函数及其化简例例:设计一个奇偶判别电路：电路输入为设计一个奇偶判别电路：电路输入为84218421BCD码码,当输入为偶数时当输入为偶数时,输出为输出为 0 0；当电路输入为奇数；当电路

19、输入为奇数时时,输出为输出为1 1。由于由于84218421BCD码中无码中无10101111这这6 6个码个码,电路禁电路禁止输入这止输入这6 6个码，这个码，这6 6个码对应的最小项为个码对应的最小项为无关项无关项。利用利用不完全确定不完全确定的逻辑函数中的的逻辑函数中的无关无关项项往往可以将函数化得更简单。往往可以将函数化得更简单。ABCDFABCDF00000100000001110011001001010001111011010001100010111101011001110011111111真值表真值表F(A,B,C,D)=m(1,3,5,7,9)+d(1015)F(A,B,C,D

20、)=DABCD00011110000111101111100000若若不利用无关项不利用无关项（即将卡诺（即将卡诺图中的图中的均作均作0 0处理）处理）,则化则化简结果为简结果为:F(A,B,C,D)=AD+BCD若若利用无关项利用无关项(即将卡诺图中的即将卡诺图中的按化简的需要任意按化简的需要任意处理处理,将有些将有些当作当作0 0,有些有些当作当作1 1),),则化简结果为则化简结果为:F(A,B,C,D)=m(1,3,5,7,9)+d(1015)完整地将函数写为：完整地将函数写为：F(A,B,C,D)=Dd(1015)=0例：例：ABCD0001111000011110110001101

21、F(A,B,C,D)=B+AD+AC注意注意:在无特殊说明的情况下在无特殊说明的情况下,为使逻辑函数化为使逻辑函数化的更简单的更简单,均应按上述均应按上述第二种第二种方法处理最小项。方法处理最小项。6)6)多输出逻辑函数的化简多输出逻辑函数的化简实际的数字电路，常常是一个多输出电路，即对应实际的数字电路，常常是一个多输出电路，即对应于相同一组输入变量，于相同一组输入变量，存在多个输出函数存在多个输出函数。多输出函数的化简也是多输出函数的化简也是以单个函数的化简方法为基以单个函数的化简方法为基础础，但要考虑到，但要考虑到整体电路最简整体电路最简。例例:F1(A,B,C)=m(1,4,5)F2(A

22、,B,C)=m(1,3,7)若按单个函数化简方法若按单个函数化简方法ABC0100011110111ABC0100011110111化简的结果为：化简的结果为：F1=AB+BCF2=AC+BC从整体出发，考虑函数的化简从整体出发，考虑函数的化简ABC0100011110111ABC0100011110111化简的结果为：化简的结果为：F1=ABC+ABF2=ABC+BC3.3 列表法化列表法化简 将函数表示成将函数表示成“最小最小项之和之和”形式，并用二形式，并用二进制制码表示每表示每一个最小一个最小项。找出函数的全部找出函数的全部质蕴涵涵项。方法：方法：先将先将n个个变量函数中的相量函数中的

23、相邻最小最小项合并，消去相异合并，消去相异的一个的一个变量，得到（量，得到（n-1）个）个变量的量的“与与”项；再将相；再将相邻的的（n-1）个）个变量的量的“与与”项合并，消去相异的合并，消去相异的变量，得到（量，得到（n-2）个）个变量的量的“与与”项依此依此类推，直到不能再合并推，直到不能再合并为止。止。所得到的全部不能再合并的所得到的全部不能再合并的“与与”项（包括不能合并的最小（包括不能合并的最小项），即），即为所要求的全部所要求的全部质蕴涵涵项。找出函数的必要找出函数的必要质蕴涵涵项。找出函数的最小覆盖。找出函数的最小覆盖。2023/2/1142例例用列表法化用列表法化简函数函数

24、将函数表示成将函数表示成“最小最小项之和之和”形式，并用二形式，并用二进制制码表示每一个最小表示每一个最小项。2023/2/11432023/2/1144找出函数的全部质蕴涵项。找出函数的全部质蕴涵项。2023/2/11452023/2/1146找出函数的必要质蕴涵项找出函数的必要质蕴涵项2023/2/1147 找出函数的最小覆盖。找出函数的最小覆盖。2023/2/1148课堂复习课堂复习用卡诺图化简下列逻辑函数。用卡诺图化简下列逻辑函数。2023/2/1149作作 业业12（2）34（2）（）（3）（）（5）（）（6）（）（9）（）（10）（）（12）（）（13）5（2）（）（3）（）（5）（）（6）（）（7）678