《组合逻辑原理》PPT课件.ppt

《《组合逻辑原理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《组合逻辑原理》PPT课件.ppt（94页珍藏版）》请在装配图网上搜索。

1、1,第三章 组合逻辑原理,计算机学院陈媛媛,2,组合逻辑的定义,逻辑电路中没有从输出到输入的反馈，且由功能完全的门系列构成，就称为组合逻辑电路。,Inputs,Outputs,Combinational Logic Functions,Content,卡诺图,3,混合逻辑组合电路,5,4,例：一个由电动马达带动的输送原料的传输装置，如果有原料要传送且保护联合开关没有打开，两个操作人员之一在位时可被启动。请设计出该问题的逻辑图表达式。,5,问题描述 输入：令a,b分别表示两个操作人员1和操作人员2，操作人员在位用逻辑1表示，不在位则相应变量为逻辑0； 令s表示联合开关，开关闭合用逻辑1表示，开关

2、断开为0； 令m表示原料的存在状态，有原料用逻辑1表示，无原料用0表示； 令M表示马达的状态，马达转动用逻辑1表示，停止转动用逻辑0表示。,构造真值表,6,将一个书面问题描述转换成真值表的过程 确定所包含的输入、输出变量 分析所给实际逻辑问题的因果关系，将引起事件的原因确定为输入变量，将事件所产生的结果作为输出函数。 为每个变量分配助记符或字母或标识 确定真值表的大小；看看有多少个输入组合y=2x 其中，x=输入变量数，y=组合数 构造一个包含所有输入变量组合的真值表 仔细研究问题描述，确定使给定输出为真的输入组合,7,例3-4：一个传输系统从三个不同来源运输原材料，三个源汇集为一个单输出传输

3、装置。四个传输装置有分离的马达，可分开控制。输出物品速度必须与源流速吻合。要实现这些，必须具备下列条件：如果源1有物品，源2和源3要关闭；如果源1空，则源2和源3或者两者都可开启。在不能从三个源获得物品的情况下，输出传输装置要关闭，如果没有物品，相应源传输装置应关闭。,8,s1,s2,s3：源1，源2，源3，有物品为1，无物品为0 m1,m2,m3,m4:四个马达，开启为1，关闭为0。,9,练习1：某产品有A、B、C、D四项质量指标，其中A为主要指标，产品检验标准规定：当主要指标及两项次要指标都合格时，产品定为合格品，否则定为不合格品。对该问题（1）设定输入输出变量及其取值；（2）列出真值表。

4、 （1）输入：各项质量指标A,B,C,D； 该项指标合格则等于1，否则等于0； 输出：S：产品合格等于1，否则等于0.,10,Content,卡诺图,3,混合逻辑组合电路,5,12,列出真值表后，找出那些使函数值为 1 的变量取值组合，变量值为 1 的写成原变量，为0的写成反变量，这样对应于使函数值为1的每一个组合就可以写出一个乘积项，把这些乘积项加起来，可以得到函数的标准积之和。,13,m7= abms m11=abms m15=abms 写成积之和： M=abms+abms+abms 化简后也可写作 M=bms+abms,真值表,注意：积项的下标与输入变量组合的关系,14,m7= abms

5、 m11=abms m15=abms M=abms+abms+abms M=bms+abms 乘积项：一个与门实现的项 bms, abms 积之和：一个或门及两个或更多的与门实现 M=bms+abms 最小项：特殊情况的乘积项 m7，m11，m15 标准积之和：M=m7+m11+m15,(1)每个乘积项都包含了全部输入变量(2)每个乘积项中的输入变量可以是原变量，或者反变量 (3)同一输入变量的原变量和反变量不同时出现在同一乘积项中。这样的乘积项我们称为最小项。,15,列出真值表后，找出那些使函数值为 0 的变量取值组合，变量值为0的写成原变量，为1的写成反变量，这样对应于使函数值为0的每一个

6、组合就可以写出一个和项，把这些和项相乘，可以得到函数的标准和之积。,16,由真值表导出开关方程,M0=a+b+m+s; M1=a+b+m+s; M2=a+b+m+s; M3=a+b+m+s; M4=a+b+m+s; M5=a+b+m+s; M6=a+b+m+s;M8=a+b+m+s; M9=a+b+m+s; M10=a+b+m+s; M12=a+b+m+s；M13=a+b+m+s; M14=a+b+m+s; M=M0M1M2M3M4M5M6M8M9M10M12M13M14 化简后也可写作 M=(a+b)(a+b+m)(a+b+m+s)(a+m)(a+m+s),构造真值表,注意：和项的下标与输入

7、变量组合的关系,17,M0=a+b+m+s; M1=a+b+m+s; M2=a+b+m+s; M3=a+b+m+s; M4=a+b+m+s; M5=a+b+m+s; M6=a+b+m+s;M8=a+b+m+s; M9=a+b+m+s; M10=a+b+m+s; M12=a+b+m+s；M13=a+b+m+s; M14=a+b+m+s; M=M0M1M2M3M4M5M6M8M9M10M12M13M14 M=(a+b)(a+b+m)(a+b+m+s)(a+m)(a+m+s) 和项：一个或门实现的项 a+b, a+b+m 和之积：一个与门及两个或多个或门实现(a+b)(a+b+m)(a+b+m+s)

8、(a+m)(a+m+s) 最大项：特殊情况的和项：M0，M1， 标准积之和：M=M0M1M2M3M4M5M6M8M9M10M12M13M14,(1)每一个和项中包含全部变量；(2)和项中的变量可以原变量形式出现，也可以反变量形式出现；(3)原、反变量不能同时出现在同一个和项中。 这样的和项我们称为最大项。,18,标准形式 简化形式 标准积之和：当输出变量为逻辑1时定义的最小项的完整系列 M=abms+abms+abms=m7+m11+m15 =m(7,11,15) 标准和之积：当输出变量为逻辑0时定义的最大项的完整系列 M=(a+b+m+s)(a+b+m+s)(a+b+m+s)(a+b+m+s

9、)(a+b+m+s)(a+b+m+s)(a+b+m+s)(a+b+m+s)(a+b+m+s)(a+b+m+s)(a+b+m+s) (a+b+m+s)(a+b+m+s) =M0M1M2M3M4M5M6M8M9M10M12M13M14 =M(0,1,2,3,4,5,6,8,9,10,12,13,14),19,练习：从真值表中生成开关方程，分别写出方程的积之和标准形式和和之积标准形式。 开关方程的积之和标准形式为S=m11+m13 + m14 + m15 = abcd+abcd+abcd+abcd 开关方程的和之积标准形式为S=M0M1M2M3M4M5M6M7M8M9M10M12,20,将一个积之和

10、方程转换成标准形式的方法： step1：在每个乘积项中标明所缺少的变量； step2：将缺少变量及其反变量之和同相应的乘积项相与：xy(z+z)； step3：应用分配律展开该项：xyz+xyz. 将一个和之积方程转换成标准形式的方法： step1：在每个和项中标明所缺少的变量； step2：将缺少变量及其反变量之积同相应的和项相或：x+y+zz； step3：应用分配律展开该项：(x+y+z)(x+y+z).,21,最小项与最大项的数字表示 最小项： 1)令正变量为1，反变量为0，写出每个乘积项的二进制表达式：abcd:1010 2)将该二进制数转换为十进制数：(1010)2=(10)10

11、3)用mk(k为上述转换的十进制数)表示该最小项。 最大项： 1)令正变量为0，反变量为1，写出每个和项的二进制表达式：x+y+z:011 2)将该二进制数转换为十进制数：(011)2=(3)10 3)用Mk(k为上述转换的十进制数)表示该最大项。,最小项为最大项之反,22,例：将下列方程转换成相应的标准形式： 1.P=f(a,b,c)=ab+ac+bc (积之和) step1: ab:缺少c; ac:缺少b; bc:缺少a step2: P=ab(c+c)+a(b+b)c+(a+a)bc step3: P=abc+abc+abc+abc+abc+abc step4: P=m5+m4+m6+m

12、7+m3 =m(3,4,5,6,7),23,2.Y(a,b,c,d)=abcd+bcd+ad (积之和) step1: abcd:无缺少项; bcd:缺少a; ad:缺少b,c项 step2: Y=abcd+(a+a)bcd+a(b+b) (c+c)d step3: Y=abcd+abcd+abcd+abcd+abcd+abcd+abcd step4: Y=m9+m15+m7+m3+m13 =m(3,7,9,13,15),24,3.T=f(a,b,c)=(a+b)(b+c) (和之积) step1： a+b:缺少c项；b+c: 缺少a项； step2: T=(a+b+cc)(aa+b+c) s

13、tep3： T=(a+b+c)(a+b+c)(a+b+c)(a+b+c) step4： T=M2M3M6=M(2,3,6),25,4.Y(a,b,c,d)=(a+b)(b+c+d) (和之积) step1: a+b: 缺少c,d项， b+c+d:缺少a项; step2: T=(a+b+cc+dd)(aa+b+c+d) step3: T=(a+b+c+d)(a+b+c+d)(a+b+c+d)(a+b+c+d)(a+b+c+d)(a+b+c+d) step4: T=M0+M1+M2+M3+M7+M15=M(0,1,2,3,7,15),26,练习:将下列布尔函数分别化为标准积之和与标准和之积 P=f

14、(w,x,y,z)=wx+yz T=f(a,b,c,d)=(a+b+c)(a+d),Ans: P=f(w,x,y,z)=wxyz+wxyz+wxyz+wxyz+wxyz+wxyz+wxyz =m(2,4,5,6,7,10,14) T=f(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) =M(4,5,8,10,12,14),27,最小项与最大项的相互转换 step1：计算乘积项之和表达式中的每一个乘积项，即确定表示乘积项的二进制数； step2：确定step1中没有包含的所有二进制数； step3：为从s

15、tep2得到的每一个二进制数写出相应的和项，并以和项之乘积形式表达。,28,例：把该最小项之和转换为最大项之积f1(a,b,c)= abc + abc + abc + abc = m1 + m2 + m4 + m6 = (1,2,4,6) = (0,3,5,7) = (a+b+c)(a+b+c)(a+b+c)(a+b+c),29,练习：把下面的最小项之和表达式转换为等价的最大项之积表达式：,Content,卡诺图,3,混合逻辑组合电路,5,31,卡诺图提供了简化布尔表达式的一种系统方法，如果正确使用，会得到尽可能简化的积之和或和之积表达式； 卡诺图是用图示方法将各种输入变量取值组合下的输出函数

16、值一一表达出来； 卡诺图和真值表一样可以表示逻辑函数和输入变量之间的逻辑关系，每一个小方格对应着真值表中的一行取值组合； 卡诺图中每一个小方格对应着逻辑函数中的一个最小项或最大项。,32,卡诺图与真值表,0、1方格：对应着输入 A反变量； 0，2方格：对应着输入B的反变量； 1、3方格：对应着输入B的正变量； 2、3方格：对应着输入A的正变量 相邻方格只有一位不同。,33,相邻方格只有一位不同,34,卡诺图与真值表,两个最小项相加可以消去互为反变量的因子,卡诺图形象地表达了变量各个最小项之间在逻辑上的相邻性。 仅有一个变量不同的小方格相邻 有一个以上变量不同的小方格不相邻,35,在卡诺图中，一

17、个最小项对应图中一个变量取值的组合（反映在编号上）的小格子，两个逻辑相邻的最小项对应的小格子位置间有以下三种情况： 相接紧挨 相对各在任一行或一列的两头 相重对折起来位置相重合,36,三变量卡诺图,37,三变量卡诺图与最小项的关系,38,将布尔方程转换为卡诺图 step1：观察变量个数，确定卡诺图中变量个数； step2：确定卡诺图中变量排列格式，以及卡诺图中每一格中变量的取值组合： step3：如方程不是标准形式，将布尔方程转换为积之和标准形式； step4：如标准形式为积之和，找到每一项取值组合在卡诺图中的位置，填1，其余位置填0。 注：如标准形式为和之积，也可直接填入卡诺图中，注意与积之

18、和标准形式的区别。,39,例：根据下面的布尔方程构造卡诺图： 解：1.确定变量个数：三变量 2.确定卡诺图格式： 格式1：,1,1,1,1,1,40,格式2：,1,1,1,1,1,41,例：根据下面布尔方程构造卡诺图： f(a,b,c) = ac + abc + bc 解： step1：观察变量个数：三变量； step2：确定卡诺图格式：,42,step3：转换为标准形式： f(a,b,c) = ac + abc + bc =ac(b+b)+abc+(a+a)bc =abc+abc+abc+abc+abc =abc+abc+abc+abc step4: 填入卡诺图,1,1,1,1,43,练习：

19、根据下面布尔方程构造卡诺图： f1(x,y,z)= m(2,5,6,7) f2(x, y, z)=m(0,1,2,3,6),44,45,例：写出下面卡诺图所表示的标准积之和，并写出其中可消去的项。,1,1,1,1,1,标准积之和：,可消去的项？,相邻项,46,最小项,四个最小项为一组,三变量卡诺图中变量的消去,只能1，2，4，8个最小项为一组,47,四变量卡诺图,一个方格表示一个四变量的最小项； 若2个相邻方格组成一个长方形表示一个三变量的乘积项； 若4个相邻方格组成一个长方形表示一个二变量的乘积项； 若8个相邻方格组合成一个长方形，表示一个变量的输入值； 将16个方格合成一个，则代表逻辑1.

20、,48,AB,CD,1,1,1,1,1,1,1,1,1,1,1,g(A,B,C,D) = A+BD+BCD,将下面的布尔方程填入卡诺图中 (A,B,C,D) = m(0,1,2,3,4,5,6,7,8,10,13). step1：构造四变量卡诺图，标注输入变量 step2：将最小项填入相应位置的方格中,00,01,11,10,00,01,11,10,A,BD,BCD,49,例：化简下面的布尔方程: f(a,b,c) = ac + abc + bc =a(b+b)c+abc+(a+a)bc =abc+abc+abc+abc+abc =abc+abc+abc+abc = ac+ab+bc,化为标准

21、最小项之和,消去a，得到bc,消去b，得到ac,消去c，得到ab,50,1,例：化简下面的布尔方程:,消去A，C，得到B,消去B，得到AC,1,1,1,1,51,用卡诺图化简布尔方程：f1(x,y,z)= m(2,5,6,7) f2(x, y, z)=m(0,1,2,3,6),f1(x, y, z) = yz + xz,f2(x, y, z) = x+yz,52,化简时应注意的几个问题： (1) 圈必须覆盖所有的1。 (2) 对每一个圈，其中1的个数必须是2n个相邻的1。 (3) 圈的个数必须最少 (乘积项最少) 。 (4) 圈越大越好（消去的变量多）。 (5) 每个圈至少包含一个新的最小项。

22、,53,蕴含: 任何单个最小项或允许的最小项组 。 图中红色虚线框所示 质蕴含 (PI): 不能与任何其他最小项或最小项组组合的蕴含。 图中ACD是质蕴含，ABCD,BCD还可以跟其他最小项组组合，所以不是质蕴含。 必要质蕴含 (EPI): 包含一个或多个唯一的最小项，至少包含一个不被其他任何质蕴含所包含的最小项。 ABC没有一个不被其他质蕴含包含的最小项，所以不是必要质蕴含，BD是必要质蕴含。,1,1,1,1,1,1,ABCD,BCD,BD,ABC,ACD,00,01,11,10,00,01,11,10,AB,CD,1,54,例：蕴含：ab,acd,acd,ad,b ab 不是一个质蕴含因为

23、它同时包含在 b中. acd不是一个质蕴含因为它同时包含在 ad中. b, ad, acd 是质蕴含 b, ad, acd 是必要质蕴含.,55,1,1,1,1,1,1,1,1,1,cd,ab,f2(a,b,c,d),的卡诺图如下所示，找出其中的必要质蕴含。 f2的必要质蕴含为bd.,00,01,11,10,00,01,11,10,质蕴含： acd bd abd abc bcd acd abc,56,1,1,1,f(a,b,c,d) = m(0,1,4,5,8,11,12,13,15). 质蕴含个数：5 必要质蕴含：ac,cd,acd. Ans: f(a,b,c,d) = cd + ac +

24、bc + acd,1,1,1,1,1,1,cd,ab,ac,cd,bc,abd,acd,57,利用卡诺图化简下面的布尔方程 F(x,y,z)=(0,2,3,4,5,7) 质蕴含个数：6 没有必要质蕴含。 Ans: F(x,y,z)=xz+yz+xy F(x,y,z)=yz+xy+xz,1,0,10,11,01,00,1,1,1,xy z,1,1,1,有多于一种的等价化简结果,58,f(a,b,c,d) = (0,3,4,5,7,11,13,15) 包含四个质蕴含 其中有三个为必要质蕴含 Ans: f(a,b,c,d) =acd+cd+bc,1,1,1,1,1,1,1,1,cd,ab,59,利用

25、卡诺图化简下面的布尔方程 F(w,x,y,z)=(0,1,4,5,9,11,13,15) F(a,b,c,d)=(0,1,2,4,5,6,8,9,12,13,14) F(a,b,c,d)=(1,3,4,5,7,8,9,11,15) F(w,x,y,z)=(1,5,7,8,9,10,11,13,15),60,F(w,x,y,z)=(0,1,4,5,9,11,13,15),1,1,1,1,1,yz,wx,00,01,11,10,00,01,11,10,1,1,1,ANS:F(w,x,y,z)=wy+wz,61,F(a,b,c,d)=(0,1,2,4,5,6,8,9,12,13,14),1,1,1,

26、1,1,1,1,1,1,1,1,F(a,b,c,d)=c+ad+bd,1,1,1,1,1,1,1,1,1,1,1,62,F(a,b,c,d)=(1,3,4,5,7,8,9,11,15),1,1,1,1,1,1,1,1,1,ANS:F(a,b,c,d)=cd+ad+abc+abc,63,F(w,x,y,z)=(1,5,7,8,9,10,11,13,15),1,1,1,1,1,1,1,1,1,F(w,x,y,z)=yz+xz+wx,64,不完全确定的函数(随意项) 随意项的产生 由于不可能所有的输入组合都发生，所以不可能知道每个输入变量组合的输出值。 不用作输出函数的一部分出现的最小项或最大项称为

27、随意项。,65,在存在随意项的情况下，可以把一个或几个随意项写进逻辑函数中，也可以把随意项从函数式中删掉，不影响函数值。因此在逻辑函数化简时，利用随意项有时会给化简带来方便。 在卡诺图上，究竟将“d”(随意项)作为“1”还是“0”对待，应以得到的相邻最小项矩形组合最大，而且矩形组合数目最少为原则。,66,确定和使用随意项(dont care minterms) 写出真值表； 确定是否所有输入组合都用于产生输出，对于没有用于确定输出值的输入变量组合为随意项； 在卡诺图中用特写的标号(d)标识出随意项； 产生尽可能大的包含随意项与一般最小项组和的必要质蕴含； 不要将随意项与它们自己组合。,67,例

28、：8421BCD码输入的四舍五入电路,真值表如右图所示,68,A=f(w,x,y,z)=(5,6,7,8,9)+ d(10,11,12,13,14,15),B=f(w,x,y,z)=(1,2,3,4,9)+ d(10,11,12,13,14,15),C=f(w,x,y,z)=(0,3,4,7,8)+ d(10,11,12,13,14,15),D=f(w,x,y,z)=(0,2,4,6,8)+ d(10,11,12,13,14,15),69,70,A=w+xz+xy B=xy+xz+xyz C=yz+yz D=z,71,练习：化简下图所示的带随意项的卡诺图,解：f = acd+ab+cd+abc

29、 或 f = acd+ab+cd+abd,72,化简最大项方程 利用卡诺图化简最大项方程与化简最小项方程的过程基本是一致的 在化简最大项方程时，先对0分组产生最小和项 对0分组的法则和对1分组的法则是一样的,73,和之积与卡诺图,74,0,0,0,0,1,1,0,0,0,1,1,1,1,1,1,1,ab,cd,F = (a+b)(a+c)(a+b+c+d),例：依据右图所示卡诺图写 出相应的和之积化简式,00,01,11,10,00,01,11,10,a+c,a+b,a+b+c+d,75,练习：利用卡诺图对下面的和之积表达式进行化简,F=(C+D)(A+B+D)(A+B+C),化为标准和之积：

30、,A+B+D,A+B+C,C+D,Content,卡诺图,3,混合逻辑组合电路,5,77,五变量卡诺图结构,相同颜色块的项为卡诺图中的相邻项,78,五变量卡诺图结构,相同颜色块的项为卡诺图中的相邻项,79,奎恩麦克拉斯基法(Quine-Mcluskey) 原理：合并两个相邻最小项，找出全部质蕴含项，再求必要质蕴含构成最简表达式。由于其列表过程有严格的算法，便于编制计算机解题程序由计算机完成逻辑函数的化简。,Content,卡诺图,3,混合逻辑组合电路,5,81,断言状态 断言状态也称为有效状态。断言状态指设计者认为逻辑门应该处于的逻辑状态或电平（高或低）。 例：假定使用非门的输出来驱动LED，

31、而且为了点亮LED，需要输出低电平。因此，低电平就是非门输出的断言状态。为了得到低电平输出，非门的输入必须是高电平，因此高电平是非门输入的断言状态。这样，小圆圈应该位于非门的输出端，当输入为低电平时，输出为非断言状态，LED熄灭。,82,L:低电平 H:高电平,大多数系统中均采用正逻辑，有些复杂系统中为分析方便将正、负逻辑混合使用，称为混合逻辑系统,83,正逻辑体制到负逻辑体制的变换规则为： step1:在门电路的输入端加小圆圈。 step2:在门电路符号的输出端加小圆圈。但该处若已有小圆圈，则不加小圆圈且去掉原有的小圆圈。 step3:将与门变成或门，反之亦然。,84,例：与门的正负逻辑转换

32、,85,例：或门的正负逻辑转换,86,例：与非门的正负逻辑转换,87,例：或非门的正负逻辑转换,88,圆圈逻辑的转换 step1: 从输出门开始，转换任何不匹配逻辑电平的输出门； step2：为适应转换重画输出门（利用正负逻辑转换）； step3：继续转换下一级，直到所有不匹配电平都被转换为止。 目的：在任何情况下都将一个圆圈输出同一个圆圈输入连接起来，这样可以直接从逻辑图确定逻辑输出函数。,低有效输出接低有效输入， 高有效输出接高有效输入,89,3一端消去或加上小圆圈，同时将相应变量取反，其逻辑关系不变。,2任一条线一端上的小圆圈移到另一端，其逻辑关系不变。,1逻辑图中任一条线的两端同时加上或消去小圆圈，其逻辑关系不变。,混合逻辑中逻辑符号的变换,90,例：将下面电路逻辑电路转换为圆圈逻辑,H,H,H,H=D+C(A+B),Content,卡诺图,3,混合逻辑组合电路,5,92,多输出函数 利用卡诺图单独地化简每个输出函数 注意其中的共享项,93,例：画出下面多输出函数的逻辑图. F1=f(a,b,c)=(2,6,7) F2=f(a,b,c)=(1,3,7),F1=ac+bc,F2=bc+ab,F1=ac+abc,F2=bc+abc,94,F1=ac+bc,F2=bc+ab,F1=ac+abc,F2=bc+abc,