《《逻辑函数优化》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《逻辑函数优化》PPT课件.ppt（49页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 逻辑函数优化逻辑函数优化逻辑函数常用的化简方法有：逻辑函数常用的化简方法有：公式法公式法卡诺图法卡诺图法列表法。列表法。2024/7/241一些概念一些概念因子：因子：与项中包含的变量（包括原变量和反变与项中包含的变量（包括原变量和反变量）称作因子。量）称作因子。蕴涵项：蕴涵项：若某个与项在其因子的某种取值组合若某个与项在其因子的某种取值组合下可以使整个逻辑函数输出为下可以使整个逻辑函数输出为1 1，则称该与项，则称该与项为该函数的蕴涵项。为该函数的蕴涵项。质蕴涵项：质蕴涵项：若某个蕴涵项不能再进一步合并为若某个蕴涵项不能再进一步合并为另一个因子数更少的蕴涵项，则称该蕴涵项为另一个
2、因子数更少的蕴涵项，则称该蕴涵项为质蕴涵项，即质蕴涵项，即质蕴涵项中的任意一个因子都是质蕴涵项中的任意一个因子都是不能删除的不能删除的，否则它将不再是有效的蕴涵项。，否则它将不再是有效的蕴涵项。2024/7/242一些概念一些概念覆盖：覆盖：若蕴涵项的集合能包含使给定函数等于若蕴涵项的集合能包含使给定函数等于1 1的所有取值情况，则称该蕴涵项集合为该给的所有取值情况，则称该蕴涵项集合为该给定函数的覆盖。很明显，定函数的覆盖。很明显，函数函数f f的所有最小项的所有最小项的集合就是能使的集合就是能使f f= =1 1的一个覆盖的一个覆盖。一般而。一般而言，言，大多数函数存在很多个不同的覆盖大多数
3、函数存在很多个不同的覆盖。覆盖。覆盖定义了一个函数的特定实现。所有质蕴涵项的定义了一个函数的特定实现。所有质蕴涵项的集合也是一个覆盖。经过分析可以发现集合也是一个覆盖。经过分析可以发现质蕴涵质蕴涵项的覆盖是最简的覆盖项的覆盖是最简的覆盖。实质上，实质上，逻辑函数优化的过程就是求质蕴涵项逻辑函数优化的过程就是求质蕴涵项覆盖的过程。覆盖的过程。2024/7/243逻辑函数的化简逻辑函数的化简化简的意义化简的意义: :节省元器件节省元器件, ,降低电路成本降低电路成本; ; 提高电路可靠性提高电路可靠性; ; 减少连线减少连线, ,制作方便。制作方便。最简与或表达式的标准：最简与或表达式的标准：1
4、1） 所得所得与或与或表达式中，表达式中，乘积项乘积项（与项）数目最少；（与项）数目最少；2 2） 每个乘积项中所含的每个乘积项中所含的变量数变量数最少。最少。针对某一逻辑式，反复运用逻辑代数公式消去针对某一逻辑式，反复运用逻辑代数公式消去多余的多余的乘积项乘积项和每个乘积项中和每个乘积项中多余的因子，多余的因子，使函数式符合使函数式符合最简最简标准标准。 化简中常用方法化简中常用方法:3.1 3.1 公式化简法公式化简法(1) 并项法并项法=（A B）C+（AB）C在化简中在化简中注意注意代入规则代入规则的使用的使用(2)吸收法吸收法利用公式利用公式A+AB=A利用公式利用公式AB+AB=A
5、例例: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+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=
6、A等等例：例：F=AB+AC+BC=AB+AC+(A+A)BC=AB+AC+ABC+ABC=(AB+ABC)+(AC+ABC)=AB+AC2024/7/249课堂练习课堂练习 3. 2 卡诺图化简法卡诺图化简法该方法是将逻辑函数用一种称为该方法是将逻辑函数用一种称为“卡诺图卡诺图”的图形的图形来表示，然后在卡诺图上进行函数的化简的方法。来表示，然后在卡诺图上进行函数的化简的方法。卡诺图是一种包含一些卡诺图是一种包含一些小方块小方块的几何图形，图中每个的几何图形，图中每个小方块小方块称为一个单元，每个单元对应一个称为一个单元，每个单元对应一个最小项。最小项。两个两个相邻相邻的最小项在卡诺图中也必
7、须是的最小项在卡诺图中也必须是相邻相邻的。卡诺图中相的。卡诺图中相邻的含义邻的含义: 几何相邻性，几何相邻性，即几何位置上相邻，也就是左右紧即几何位置上相邻，也就是左右紧挨着或者上下相接；挨着或者上下相接； 对称相邻性，对称相邻性，即图形中对称位置的单元是相邻的。即图形中对称位置的单元是相邻的。1 卡诺图卡诺图的构成的构成 例例 三变量卡诺图三变量卡诺图ABC0100011110ABCm0ABCm1ABCm2ABCm3ABCm4ABCm5ABCm6ABCm7相邻性规则相邻性规则m1m3m2m7相邻性规则相邻性规则m2m0m1（对称）（对称）m4循环码循环码二、四、五变量卡诺图AB01010 1
8、2 3ABCD00011110000111100 1 3 24 5 7 6 8 9 11 1012 13 15 14相邻性规则 m3m5 m7 m6 m15 ABCDE00011110000001 0110100132891110242527261101111011006754141513122223212030312928161719182 逻辑函数的卡诺图表示法逻辑函数的卡诺图表示法用卡诺图表示逻辑函数，只是把各组变量值用卡诺图表示逻辑函数，只是把各组变量值所对应的逻辑函数所对应的逻辑函数F的值，填在对应的小方格的值，填在对应的小方格中。中。（其实卡诺图是真值表的另一种画法）（其实卡诺图是
9、真值表的另一种画法）ABC0100011110m3m5m700000111例：例：F（A，B，C）=ABC+ABC+ABC 用卡诺图表示为：用卡诺图表示为：3 在卡诺图上在卡诺图上合并合并最小项的最小项的规则规则当卡诺图中有最小项相邻时（即：有标当卡诺图中有最小项相邻时（即：有标1的方格相邻的方格相邻)，可利用最小项相邻的性质，对最小项合并。可利用最小项相邻的性质，对最小项合并。 规则为：规则为：（1） 卡诺图上任何卡诺图上任何两个两个标标1的方格相邻，可以合为的方格相邻，可以合为1 项，并可消去项，并可消去1个变量。个变量。例：例：ABC010001111000000111ABC+ABC=B
10、CABC+ABC=ACABCD00011110000111101111ABD（2）卡诺图上任何四个标）卡诺图上任何四个标1方格相邻，可合并为一项，并方格相邻，可合并为一项，并可消去两个变量。可消去两个变量。四个标四个标1方格相邻的特点：方格相邻的特点：同在一行或一列；同在一行或一列；同在一田字格中。同在一田字格中。ABD例：例： ABCD00011110000111101111111CDABABCD0001111000011110111111111BD同在一行或一列同在一行或一列同在一个田字格中同在一个田字格中BDABCD000111100001111011111111ABCD00011110
11、0001111011111111（3）卡诺图上任何八个标）卡诺图上任何八个标1的方格相邻，可以并的方格相邻，可以并为一为一 项，并可消去三个变量。例：项，并可消去三个变量。例：ABCD000111100001111011111111ABCD000111100001111011111111BAABCD00011110000111101111 1111综上所述，在综上所述，在n个变量的卡诺图中，只有个变量的卡诺图中，只有2的的i次方个相次方个相邻的标邻的标1方格（必须排列成方形格或矩形格的形状）才方格（必须排列成方形格或矩形格的形状）才能圈在一起，合并为一项，该项保留了原来各项中能圈在一起，合并为
12、一项，该项保留了原来各项中n-i个相同的变量，消去个相同的变量，消去i个不同变量。个不同变量。4 用卡诺图化简逻辑函数（化为最简与或式）用卡诺图化简逻辑函数（化为最简与或式）项数最少项数最少，意味着卡诺图中，意味着卡诺图中圈数圈数最最少少；每项中的变量数最少每项中的变量数最少，意味着卡诺图中，意味着卡诺图中的的圈圈尽可能尽可能大大。最简标准：最简标准：例例将将F（A，B，C）=m（3，4，5，6，7） 化为化为最简最简与或式。与或式。ABC010001111011111ABC010001111011111F=A+BC（最简）（最简）（非最简）（非最简）F=AB+BC+ABC化简步骤（结合举例说
13、明）化简步骤（结合举例说明）=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) 圈出孤立的标圈出孤立的标1方格方格;ABCD00011110000111101111111m13ABCD00011110000111101111111(3) 找出只被一个最大的圈所覆盖的标找出只被一个最大的圈所覆盖的标1方格，并方格，并圈出覆盖该标圈出覆盖该标1方格的最大圈；方格的最大圈；(4) 将剩余的相邻标将剩余的相邻标1方格，圈成尽可能少
14、方格，圈成尽可能少,而且而且 尽可能大的圈尽可能大的圈. ABCDACDABDABCm8,m10m0,m1(5) 将各个对应的乘积项相加，写出最简与或式。将各个对应的乘积项相加，写出最简与或式。例：例：ABCD000111100001111011111111111F(A,B,C,D)=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得到两种化简结果，也都是最简的。得到
15、两种化简结果，也都是最简的。 化简中注意的问题化简中注意的问题(1) 每一个标每一个标1的方格必须至少被圈一次的方格必须至少被圈一次;(2) 每个圈中包含的相邻小方格数，必须为每个圈中包含的相邻小方格数，必须为2的整数次幂的整数次幂;(3) 为了得到尽可能大的圈，圈与圈之间可以重叠为了得到尽可能大的圈，圈与圈之间可以重叠;ABCD000111100001111011111111111ABCD000111100001111011111111蓝色蓝色的圈为多余的的圈为多余的.F=ABC+ACD+ACD+ABC+(BD)例如例如:(4) 若某个圈中的所有标若某个圈中的所有标1方格，已经完全被其方格，
16、已经完全被其它圈所覆盖，则该圈为多余的。它圈所覆盖，则该圈为多余的。方法方法: 在卡诺图中合并标在卡诺图中合并标 0 方格，可得到方格，可得到反函数反函数的最简的最简与或与或式。式。例例:ABC010001111011110000F=AB+BC+AC 用卡诺图求用卡诺图求反函数反函数的最简与或式的最简与或式常利用该法来求逻辑函数常利用该法来求逻辑函数F的最简与或非式的最简与或非式将上式将上式F上上 的非号移到右边，就得到的非号移到右边，就得到F的最简的最简与或非与或非表达式。表达式。F=AB+BC+AC逻辑函数化简的技巧逻辑函数化简的技巧（1 1） 对较为复杂的逻辑函数，可将对较为复杂的逻辑函
17、数，可将函函数分解数分解成多个部分，先将每个部分成多个部分，先将每个部分分别填入各自的卡诺图中，然后通分别填入各自的卡诺图中，然后通过过卡诺图对应方格的运算卡诺图对应方格的运算，求出函，求出函数的卡诺图。数的卡诺图。（2 2）对）对卡诺图进行化简卡诺图进行化简。ABABCDCD000001011111101000000101111110101 11 11 11 11 11 11 11 11 11 11 1ABABCDCD000001011111101000000101111110101 11 11 11 11 11 11 1ABABCDCD000001011111101000000101111
18、110101 11 11 11 11 11 1= =例：化简逻辑函数例：化简逻辑函数在某些实际数字电路中，逻辑函数的输出只在某些实际数字电路中，逻辑函数的输出只和一部分最小项有和一部分最小项有确定确定对应关系，而和余下的最对应关系，而和余下的最小项无关。余下的最小项无论写入逻辑函数式还小项无关。余下的最小项无论写入逻辑函数式还是不写入逻辑函数式，都不影响电路的逻辑功能。是不写入逻辑函数式，都不影响电路的逻辑功能。把这些最小项称为把这些最小项称为无关项无关项。用英文字母。用英文字母d(dond(dont t care)care)表示，对应的函数值记为表示，对应的函数值记为“”。包含无关项的逻辑函
19、数称为不完全确定的逻辑函数包含无关项的逻辑函数称为不完全确定的逻辑函数。不完全确定的逻辑函数及其化简不完全确定的逻辑函数及其化简例例: : 设计一个奇偶判别电路：电路输入为设计一个奇偶判别电路：电路输入为84218421BCD码码, ,当输入为偶数时当输入为偶数时, ,输出为输出为 0 0；当电路输入为奇数；当电路输入为奇数时时, ,输出为输出为1 1 。 由于由于84218421BCD码中无码中无10101111这这6 6个码个码, ,电路禁电路禁止输入这止输入这6 6个码，这个码，这6 6个码对应的最小项为个码对应的最小项为无关项无关项。利用利用不完全确定不完全确定的逻辑函数中的的逻辑函数
20、中的无关无关项项往往可以将函数化得更简单。往往可以将函数化得更简单。ABCDFABCDF00000100000001110011001001010001111011010001100010111101011001110011111111真值表真值表F(A,B,C,D)=m(1,3,5,7,9)+d(1015)F(A,B,C,D)=DABCD00011110000111101111100000若若不利用无关项不利用无关项（即将卡诺（即将卡诺图中的图中的均作均作0 0处理）处理）, ,则化则化简结果为简结果为: :F(A,B,C,D)=AD+BCD若若利用无关项利用无关项( (即将卡诺图中的即将卡
21、诺图中的按化简的需要任意按化简的需要任意处理处理, ,将有些将有些当作当作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例：例：ABCD0001111000011110110001101F(A,B,C,D)=B+AD+AC注意注意: :在无特殊说明的情况下在无特殊说明的情况下, ,为使逻辑函数化为使逻辑函数化的更简单的更简单, ,均应按上述均应按上述第二种第二种方法处理最小项。方法处理最小项。6)6)多输出逻辑函数的化简多输出逻辑
22、函数的化简实际的数字电路，常常是一个多输出电路，即对应实际的数字电路，常常是一个多输出电路，即对应于相同一组输入变量，于相同一组输入变量，存在多个输出函数存在多个输出函数。多输出函数的化简也是多输出函数的化简也是以单个函数的化简方法为基以单个函数的化简方法为基础础，但要考虑到，但要考虑到整体电路最简整体电路最简。例例: :F1(A,B,C)=m(1,4,5)F2(A,B,C)=m(1,3,7)若按单个函数化简方法若按单个函数化简方法ABC0100011110111ABC0100011110111化简的结果为：化简的结果为：F1=AB+BCF2=AC+BC从整体出发，考虑函数的化简从整体出发，考
23、虑函数的化简ABC0100011110111ABC0100011110111化简的结果为：化简的结果为：F1=ABC+ABF2=ABC+BC3.3 列表法化简列表法化简 将函数表示成将函数表示成“最小项之和最小项之和”形式，并用二进制码表示形式，并用二进制码表示每一个最小项。每一个最小项。 找出函数的全部质蕴涵项。找出函数的全部质蕴涵项。 方法：方法：先将先将n n个变量函数中的相邻最小项合并，消去相个变量函数中的相邻最小项合并，消去相异的一个变量，得到（异的一个变量，得到（n-1n-1）个变量的）个变量的“与与”项；再将相项；再将相邻的（邻的（n-1n-1）个变量的）个变量的“与与”项合并，
24、消去相异的变量，项合并，消去相异的变量，得到（得到（n-2n-2）个变量的）个变量的“与与”项项依此类推，直到不能依此类推，直到不能再合并为止。所得到的全部不能再合并的再合并为止。所得到的全部不能再合并的“与与”项（包括项（包括不能合并的最小项），即为所要求的全部质蕴涵项。不能合并的最小项），即为所要求的全部质蕴涵项。 找出函数的必要质蕴涵项。找出函数的必要质蕴涵项。 找出函数的最小覆盖。找出函数的最小覆盖。2024/7/2442例例用列表法化简函数用列表法化简函数 将函数表示成将函数表示成“最小项之和最小项之和”形式，并用二进制码表示每一个最小项。形式，并用二进制码表示每一个最小项。2024/7/24432024/7/2444找出函数的全部质蕴涵项。找出函数的全部质蕴涵项。2024/7/24452024/7/2446找出函数的必要质蕴涵项找出函数的必要质蕴涵项2024/7/2447 找出函数的最小覆盖。找出函数的最小覆盖。2024/7/2448课堂复习课堂复习用卡诺图化简下列逻辑函数。用卡诺图化简下列逻辑函数。2024/7/2449作作 业业12（2）34（2）（）（3）（）（5）（）（6）（）（9）（）（10）（）（12）（）（13）5 （2）（）（3）（）（5）（）（6）（）（7）678
