逻辑代数及逻辑函数的.ppt

第二章第二章 逻辑代数及逻辑函数的化简逻辑代数及逻辑函数的化简 221 1 逻辑代数的基本原理逻辑代数的基本原理 222 2 逻辑函数的化简逻辑函数的化简 本章作业： 2.1（3）（4）（7）（8）、2.2（3）、2.3（2） 2.6（5）（6）（7）（8）、2.8、2.11（2）（4）（5） 2.12（1）（2）、2.13（3）（5）、2.14（2）（3） 2.16（1） 221 1 逻辑代数的基本原理逻辑代数的基本原理 逻辑代数中的变量与普通代数中的变量一样， 也是以A、B、C等字母来表示，但这些变量只能取值 为0或1，这里的0或1不表示变量的大小，而表示两种 对立的关系，如低电平、高电平；无信号、有信号； 开关的断、通；灯的熄、亮等。逻辑代数表达的是电 路输入与输出间的逻辑关系，而不是数量关系。 Ff(A，B，C) 其中：A、B、C.为输入逻辑变量，取值是0或l； F为输出逻辑变量，取值是0或l； F称为A、B、C.的输出逻辑函数。 一、逻辑代数的基本运算 1、“与”运算 E A B C F 真值表 设：开关 打开“0” 闭合“1” 灯 灭“0” 亮“1” 00 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A B C F 0 0 0 0 0 0 1 逻辑函数式 F=AB C 逻辑符号 A B C F & A B C F A B C F 2、“或”运算 A E B C F 设：开关 打开“0” 闭合“1” 灯 灭“0” 亮“1” ABCF 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 或逻辑真值表 逻辑函数式 F=A+B+C 逻辑符号 F A B C 1 F A B C + A B C F 3、“非”运算 E F A R AF 0 0 1 1 非逻辑真值表 逻辑函数式 逻辑符号 A F A F A 1 F A B F=AB F=A+B F=A F=A 二、复合逻辑关系 1、“与非” F=AB A B F A B F & F=AB AC ACD BD “与非”表达式 A B C D F 2、“或非” F=A+B+C F A B C + F A B C 1 F=A+B+A+C+D+B+D “或非”表达式 3、“与或非” F=AB+CD 4、“异或” F=AB+AB F + A B C D A B F 1 0 1 0 0 0 0 1 1 1 1 0 =AB A B F =1 A B F 5、“同或” F=AB+AB=A B A B F C D 1& = A B F A B F 关于门电路符号的说明 P C F P C F + P C F + 先“或”后“非”和先“非”后“与”等价 先“与”后“非”和先“非”后“或”等价 P C F 三、逻辑代数的基本公式、规则 1、基本公式 A A=0 A+A=1 互补律 1 A=A 1+A=1 1律 0 A=0 0+A=A 0律 A B=B A A+B=B+A 交换律 A (B C)=(A B) C A+(B+C)=(A+B)+C 结合律 A (B+C)=A B+A C A+B C=(A+B) (A+C) 分配律 吸收律 A+AB=A+B A(A+B)=AB A+AB=A A(A+B)=A 反演律 (德摩根定律) AB=A+B A+B=AB 1 0 0 0 0 1 1 1 A B AB A+B 1 1 1 1 1 1 0 0 证：由分配律 A+AB =(A+A)(A+B) =A+B 摩根定律的应用 、求反函数 F=AB+BC+ACD F=AB+BC+ACD =ABBCACD 、将“与或”表达式 化为“与非”表达式 F=AD+BCD+ABC+CD =ADBCDABCCD 对合律 A=A重叠律 A+A=A AA=A 包含律 (A+B)(A+C)(B+C)=(A+B)(A+C) AB+AC+BC=AB+AC 证：AB+AC+BC =AB+AC+BC(A+A) =AB+AC+ABC+ABC =AB(1+C)+AC(1+B) =AB+AC 推论：AB+AC+BCDEF=AB+AC 2、三个规则 1）代入规则： AB=A+B用A=CD代替A,等式仍成立 CDB=CD+B=C+D+B 2)反演规则： F: 若：“”“+”,“+”“”,“0”“1”,“1”“0” 原变量反变量，反变量原变量 则：FF 【例如】F1=AB+BD+ACD+0 F1=(A+B)(B+D)(A+C+D)1 F2=A+BD+ABCDF2=A(B+D)(A+B+C+D) 3)对偶规则： 若：“”“+”,“+”“”,“0”“1”,“1”“0” F: 则：FFF与F互为对偶函数 如果两个函数相等，则它们的对偶函数也相等 。 1A=A 0+A=A AB+AC+BC=AB+AC (A+B)(A+C) 函数对偶式的对偶式为函数本身。 (A+B)(A+C)(B+C) = 3、“异或”性质 AA=0AA=1A0=AA1=A AB=AB=(AB)1AB=BA A(BC)=(AB)CA(BC)=(AB)(AC) “异或”门电路的用处 (1)可控的数码原/反码输出器 (2)作数码同比较器 (3)求两数码的算术和 A0=A A1=A A B F 1 0 1 0 0 0 0 1 1 1 1 0 222 2 逻辑函数的化简逻辑函数的化简 一、公式法化简逻辑函数 1、“与或”表达式的化简 最简与或表达式： 1、乘积项的个数最少(用门电路实现，用 的与门数最少)。 2、在满足1的条件下，乘积项中的变量最少 (与门的输入端最少)。 省器件：用最少的门，门的输入也最少 【例1】 展开： 合并： 互补律： 互补律： F=A(BC+BC)+ABC+ABC =ABC+ABC+ABC+ABC =(ABC+ABC)+(ABC+ABC) =AC(B+B)+AC(B+B) =AC+AC=A 【例2】F=A(B+C)+BC =ABC+BC =A+BC 反演律 吸收律 【例3】 F=ABC+ABC+CD+BD+ABD =(CD+BD+ABC)+ABC+ABD =CD+BD+ABC+AB包含、吸收律 =CD+BD+ABD+ABC 包含、吸收律 =CD+BD+BC+AB 包含律 =CD+BD+BD+BC+AB =CD+B+BC+AB =CD+B 【例4】 F=AB+ABBC+BC =AB+AB+BC+BC =AB+AB+BC+BC+AC =AB+BC+AC 或 =AB+AB+BC+BC =AB+AB+BC+BC+AC =AB+BC+AC 可见：最简式不唯一 2、“或与”表达式的化简 最简条件： (1)、或项个数最少(或门用的最少) (2)、在满足1的条件下，或项中变量数最少 化简方法： 1、利用对偶规则，将“或与”表达式转换为 “与或”表达式。 2、实际化简“与或”表达式。 3、利用对偶规则将“与或”最简表达式转换 为“或与”最简表达式。 【例】 F=(A+B)(A+C)(B+C)(A+C) F=AB+AC+BC+AC 对偶规则 =AB+AC+AC =AB+C 则：F=(A+B)C 二、图解法化简逻辑函数 1、最小项与最大项 最小项 【例】 n=3，对A、B、C，有8个最小项 乘积项 包含全部变量 以原变量或反变量的 形式只出现一次 CBA CBA CBA CBA CBA CBA CBA CBA 最小项最小项编号 m0 m1 m2 m3 编号 m4 m5 m6 m7 最小项的性质 1)最小项为“1”的取值唯一。 如：最小项ABC,只有ABC取值101时， 才为“1”，其它取值时全为“0”。 2)任意两个最小项之积为“0”。 3)全部最小项之和为“1”。 4)某一个最小项不是包含在函数F中，就包含在反 函数F中。 最小项表达式 全部由最小项构成的“与或”表达式为最小项表 达式(标准“与或”表达式)。 【例1】 F=ABC+BC=ABC+BC(A+A) =ABC+ABC+ABC =m4+m5+m7=m3(4，5，7) 三人表决电路 【例2】 C B AF 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 F=ABC+ABC+ABC+ABC =m3+m5+m6+m7 =m3(3，5，6，7) 最大项 或项 包含全部变量 以原变量或反变量的 形式只出现一次 【例】 n=3，对A、B、C，有8个最大项 CBAMCBAM CBAMCBAM CBAMCBAM CBAMCBAM 76 54 32 10 +=+= +=+= +=+= +=+= 最大项表达式 C B AF 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 F=(A+B+C)(A+B+C)(A+B+C)(A+B+C) =M0M1M2M4 =M3(0，1，2，4) 最大项的性质 1)最大项为“0”的取值唯一。 如：最大项A+B+C,只有ABC取值010时， 才为“0”，其它取值时全为“1”。 2)任意两个最大项之和为“1”。 3)全部最大项之积为“0”。 4)某一个最大项不是包含在函数F中，就包含在反 函数F中。 最小项和最大项的关系 C B AF 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1、相同i的最小项和最大项互补。 Mi=mi mi=Mi m3=ABCM3=A+B+C 2、mi和Mi互为对偶式。 F=m3(3，5，6，7) F=M3(0，1，2，4) =ABC+ABC+ABC+ABC =(A+B+C)(A+B+C)(A+B+C)(A+B+C) 2、卡诺图 卡诺图的构成 (1)、由矩形或正方形组成的图形 (2)、将矩形分成若干小方块，每个小方块对应一 个最小项 2变量卡诺图 一个整体可由代表4个最小项的四个小方格组成： ABAB ABAB 改画成： m0m1 m2m3 A B01 1 0 m0m1 m2m3 3 3变量卡诺图变量卡诺图 一个整体分成8个小方格 B A C 1 0 00110110 m1 m0 m3 m2 m5 m4 m7 m6 注意 ： 上表头编码按00011110 循环 码顺序排列，而不是00011011 4 4变量卡诺图变量卡诺图 B A DC 00110110 00 11 01 10 m1 m0 m3 m2 m5 m4 m7 m6 m13 m12 m15 m14 m9 m8 m11 m10 D C B A 00110110 00 11 01 10 m4 m0 m12 m8 m5 m1 m13 m9 m7 m3 m15 m11 m6 m2 m14 m10 5变量卡诺图 B AE D 000011001010 00 11 01 10 m1 m0 m3 m2 m5 m4 m11 m9 m7 m8 m27 m26 m6 m16 m19 m10 C 110 111 101 100 m12 m13 m14 m15 m17 m18 m20 m21 m22 m23 m24 m25 m28 m29 m30 m31 3、逻辑函数的卡诺图表示 F(A,B,C,D)=m4(0,2,6,8,11,13,14,15) B A DC 00110110 00 11 01 10 11 1 11 111 【例1】 【例2】 F=AB+BC+AC =ABC+ABC+ABC+ABC B A C 1 0 00110110 1 111 【例3】 F=BC+AC+ABD+ABCD B A DC 00110110 00 11 01 10 11 11 11 11 1 1 B A C 1 0 00110110 1 1 11 11 B A C 1 0 00110110 1 1 11 11 4、卡诺图化简 B A C 1 0 00110110 111 111 ABC ABC+=AC ABCABC +=AB ABC ABC+=BC F=AC+AB+BC 两个相邻的最小项可以 合并消去一个变量。 F=AB+BC+AC 逻辑函数的最简式不唯一 卡诺图化简 B A C 1 0 00110110 1 1 11 11 B A C 1 0 00110110 1 1 11 11 F=AC+AB+BC+BC 冗余项 B A C 1 0 00110110 1 1 11 11 F=AB+AB+ABC+ABC ABAB F=B+ AB A 四个相邻的最小项可以 合并消去两个变量。 八个相邻的最小项可以 合并消去三个变量。 不是最简式 B A DC00110110 00 11 01 10 11 11 1 1111 1 【例1】 F=DC+BC+AC 【例2】 F=ABC+ACD+ABD+AD+AC 化简逻辑函数 B A DC00110110 00 11 01 10 1 1 11 1 1 11 11 11 F=BC+AC+AD+BD+ACD 【例3】 Y=(A,B,C,D)=m4(0,2,3,5,6,8,9,10,11,12,13,14,15) 试用卡诺图化简逻辑函数 B A DC00110110 00 11 01 10 111 11 1111 1111 F=D+AB+BC+AC +ABC B AE D 000011001010 00 11 01 10 C 110 111 101 100 【例4】 试用卡诺图化简逻辑函数 Y=(A,B,C,D,E)=m5(1,5,9,13,16,18,20,22,27,31) 1 1 1 1 1 1 111 1 F=ABE+ADE+ABDE 用卡诺图化简遵循的原则： （1）每个圈应包含尽可能多的最小项； B A DC00110110 00 11 01 10 11 11 1 1 1 1 （2）每个圈至少有一个最小项未被其它圈圈过； F=AC+BCD+ABD+ABD +BCD （3）圈的数目应尽可能少； （4）所有等于1的单元都必须被圈过； B A DC00110110 00 11 01 10 1 1 1 1 1 1 1 1 （5）最简“与或”表达式不唯一。 F=AD+AC+BCD+ABCD 三、单输出逻辑函数的表格法化简(QM法) 计算机辅助逻辑设计的方法 1、卡诺图法化简直观方便，过程简单明了，但只 适合于变量数 4的函数。 2、Q-M(Quine-McCluskey) 法和卡诺图法的化简思 路是一致的。 3、Q-M法是用分组表格法，把两相邻与项合成为一 新的与项，从而消去一变量。它适合于变量数 4的函数，化简过程规律性强，适用于计算机 算法实现。 Q-M方法的基本思想 什么情况下会出现“相邻两个最小项中有一个 变量互补”？从最小项的编号上看有什么规律？ 以4变量卡诺图为例 ： m1同m0，m3，m5，m9相邻 下标编号为：0001与0000,0011,0101,1001 m1同m4，m8，m10， m13等不相邻 下标编号为：0001与0100,1000,1010,1101 结论：最小项编号中“1”的个数差0 ，肯定不相邻 最小项编号中“1”的个数差2，肯定不相邻 最小项编号中“1”的个数差1，可能相邻！ 按照最小项 mi 下标编号中二进制数“1”的个数 进 行分组比较，可以化简。 名词解释： B A DC00110110 00 11 01 10 m1m2 m5m7 m8m10 m12m13m15 1、质蕴涵项 是一个积项，它再不能和 其它项合并而形成更简单 的积项。 m(5,7,13,15)m(1,5) m(12,8)m(12,13) m(2,10)m(8,10) 2、实质最小项 如 ： 只被一个质蕴涵项所包含的最小项。 如：m1,m2,m7,m15 3、必要(基本)质蕴涵项 至少包含一个实质 最小项的质蕴涵项 。 如： m(1,5)， m(2,10)， m(5,7,13,15) QM法化简步骤： 最小项 DCBA最小项 DCBA 最小项DCBA 【例】化简F(A,B,C,D)=m4(2,4,6,8,9,10,12,13,15) 1、根据最小项二进制码中“1”的个数，对函数的全 部最小项进行分组排队。 20 0 1 0 40 1 0 0 81 0 0 0 60 1 1 0 91 0 0 1 101 0 1 0 121 1 0 0 131 1 0 1 151 1 1 1 2、在组与组之间逐一搜索相邻项，合并成消去一个 变量的积项。 8,9,12,13 2,60 1 0 2,10 0 1 0 4,6 4,12 8,9 8,10 8,12 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 9,13 12,13 1 0 1 1 1 0 13,15 1 1 1 1 0 PI1 质蕴 涵项 PI2 PI3 PI4 PI5 PI6 PI7 QM法化简步骤：(续 ） 最小项 DCBA最小项 DCBA 最小项DCBA 20 0 1 0 40 1 0 0 81 0 0 0 60 1 1 0 91 0 0 1 101 0 1 0 121 1 0 0 131 1 0 1 151 1 1 1 8,9,12,13 2,60 1 0 2,10 0 1 0 4,6 4,12 8,9 8,10 8,12 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 9,13 12,13 1 0 1 1 1 0 13,15 1 1 1 1 0 PI1 PI2 PI3 PI4 PI5 PI6 PI7 在表中，未打“”的，标以PI1PI7，为质蕴涵 项。全部质蕴涵项，覆盖了F的全部最小项。 用卡诺图画出F的全部质蕴涵项 F(A,B,C,D)=m4(2,4,6,8,9,10,12,13,15) B A DC00110110 00 11 01 10 2 46 8910 12 1315 PI1(8,9,12,13) PI2(2,6) PI2 PI3(2,10) PI3 PI4(4,6) PI4 PI5(4,12) PI1PI5 PI6(8,10) PI6 PI7 PI7(13,15) 可见见，P1 P7中有不必要的质蕴质蕴 涵项项：为为此，下 一步骤骤就要从全部质蕴质蕴 涵项项中选选出必要的质蕴质蕴 涵项项 。 3、列质蕴涵项表，寻找必要的质蕴涵项 2468910121315 PI1 PI2 PI3 PI4 PI5 PI6 PI7 实质 最小项 PI1 PI7 PI1、PI7中包含了实质最小项，为必要质蕴涵 项，化简时必须保留。PI1、PI7中已经包含的最小 项在后面化简时不必再考虑。 4、列简化的质蕴涵项表 24610 PI2 PI3 PI4 PI5 PI6 简化规则： 1、被别的行所覆盖的 行可从表中消去。 2、覆盖了其它列的列 可从表中消去。 F=PI1+PI7+PI3+PI4=BD+ABC+ACD+ACD 用卡诺图化简 B A DC00110110 00 11 01 10 1 11 111 1 11 =BD+ABC+ACD+ACDF 循环PI表的化简 023457 PI1 PI2 PI3 PI4 PI5 PI6 不含必要质蕴涵项 PI1 PI6 PI5 PI4 PI3 PI2 543 7 F=PI1+PI4+PI5 循环PI表的化简(续) 023457 PI1 PI2 PI3 PI4 PI5 PI6 简化PI表 2357 PI1 PI3 PI4 PI5 PI6 PI2 F=PI2+PI3+PI6 可见：最简表达式不唯一。 B A C 1 0 00110110 111 111 四、多输出逻辑函数的表格法化简 多输出逻辑函数：同一组输入变量，有两个以 上的输出。 F1 f1(A,B,C) F2 f2(A,B,C) 化简时，在“与或”表达式中要尽量寻找公 共的“与”项，使公共项为多个函数共享，这时 从单个输出看可能不是最简，但总体是最简。 【例1】 F=AB+BC+AC G=AB+BC F=AB BC AC G=AB BC 共需要七个“与非”门 B A C 1 0 00110110 111 111 1 B A C 1 0 00110110 111 F=AB+BC+AC G=AB+BC F=AB BC AC G=AB BC 只需要五个“与非”门 【例2】 F(A,B,C,D)=m4(1,3,4,5,6,7,15) G(A,B,C,D)=m4(1,3,10,14,15) B A DC00110110 00 11 01 10 11 1111 1 B A DC00110110 00 11 01 10 11 1 1 1 F=ACD+ABCD+CDG=ACD+ABCD+ABD 多输出逻辑函数的表格法化简 特点： 1、每个被列出的最小项后边必须标明它是出 现在哪个函数中的最小项。 2、两项仅当它们都具有至少一个相同的标志时 才能合并。 3、仅当某项所具有的全部标志都出现在合并后的 项时，才能将它打上“ ”号。 【例】 F H FGH GH H GH 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 4 3 5 6 7 F0 0 00 标志CBA 最小项 标志CBA最小项 标志CB A最小项 F(A,B,C)=m3(0,1,3) G(A,B,C)=m3(3,5,7) H(A,B,C)=m3(3,4,5,6,7) 化简 0,10 0 F 1,3 0 1 F 4,51 0 H 4,61 0 H 3,7 1 1 GH 5,71 1 GH 6,7 1 1 H 4,5,6,71 H PI1 PI2 PI3 PI4 PI5 PI6 质蕴涵项表 PI1 H PI2 F PI3 F PI4 GH PI5 GH PI6 FGH FGH 01333455776 简化PI表 PI4 GH PI3 F PI6 FGH F G H 333 F=PI2+PI6=BC+ABC G=PI5+PI6=AC+ABC H=PI1+PI6=C+ABC 可以看出：每一 个输出不是最简，但 总体是最简。 五、包含任意项的逻辑函数的化简 任意项(约束项、无关项、不管项) 包含任意项的逻辑函数：函数F的取值只和一 部分最小项有关，另一部分最小项既可以取“0”，也 可以取“1”，这些最小项称“不管项”或“任意项”。 “任意项”的两种情况： 1. 有些输入变量的取值组合根本不会出现。 2. 所有的输入组合虽能出现，但在某些约束条 件下，这些组合的输出不存在。 【例1】求：8421码中出现 奇数的逻辑函数 。 DCBAF 00000 00011 00100 00111 01000 01011 01100 01111 10000 10011 有 效 状 态 F=ABCD+ABCD+ABCD +ABCD+ABCD 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 无 效 状 态 ABCD+ABCD+ABCD +ABCD+ABCD+ABCD=0 或： F=m4(1,3,5,7,9) 4(10,11,12,13,14,15)=0 或： F=m(1,3,5,7,9) + (10,11,12,13,14,15) 约束方程： 用卡诺图化简包含任意项的逻辑函数 11001 00001 11110 00110 11010 00010 11100 00100 11000 00000 FABCD 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 B A DC00110110 00 11 01 10 11 1 1 1 F=A (10,11,12,13,14,15)