第三章组合逻辑原理

第三章组合逻辑原理第一页，共94页。组合逻辑的定义逻辑电路中没有从输出到输入的反馈，且由功能完全的门系列构成，就称为组合逻辑电路。InputsOutputsCombinationalLogicFunctions······2第二页，共94页。Content真值表问题1开关方程与标准形式2卡诺图3多变量卡诺图化简4混合逻辑组合电路5多输出函数6第三页，共94页。例：一个由电动马达带动的输送原料的传输装置，如果有原料要传送且保护联合开关没有打开，两个操作人员之一在位时可被启动。请设计出该问题的逻辑图表达式。4第四页，共94页。问题描述输入：令a,b分别表示两个操作人员1和操作人员2，操作人员在位用逻辑1表示，不在位则相应变量为逻辑0； 令s表示联合开关，开关闭合用逻辑1表示，开关断开为0； 令m表示原料的存在状态，有原料用逻辑1表示，无原料用0表示； 令M表示马达的状态，马达转动用逻辑1表示，停止转动用逻辑0表示。 构造真值表5第五页，共94页。将一个书面问题描述转换成真值表的过程确定所包含的输入、输出变量分析所给实际逻辑问题的因果关系，将引起事件的原因确定为输入变量，将事件所产生的结果作为输出函数。为每个变量分配助记符或字母或标识确定真值表的大小；看看有多少个输入组合y=2x其中，x=输入变量数，y=组合数构造一个包含所有输入变量组合的真值表仔细研究问题描述，确定使给定输出为真的输入组合6第六页，共94页。例3-4：一个传输系统从三个不同来源运输原材料，三个源汇集为一个单输出传输装置。四个传输装置有分离的马达，可分开控制。输出物品速度必须与源流速吻合。要实现这些，必须具备下列条件：如果源1有物品，源2和源3要关闭；如果源1空，则源2和源3或者两者都可开启。在不能从三个源获得物品的情况下，输出传输装置要关闭，如果没有物品，相应源传输装置应关闭。S3S1S2m3m1m2m47第七页，共94页。s1,s2,s3：源1，源2，源3，有物品为1，无物品为0m1,m2,m3,m4:四个马达，开启为1，关闭为0。S3S1S2m3m1m2m48第八页，共94页。练习1：某产品有A、B、C、D四项质量指标，其中A为主要指标，产品检验标准规定：当主要指标及两项次要指标都合格时，产品定为合格品，否则定为不合格品。对该问题（1）设定输入输出变量及其取值；（2）列出真值表。（1）输入：各项质量指标A,B,C,D； 该项指标合格则等于1，否则等于0； 输出：S：产品合格等于1，否则等于0.9第九页，共94页。ABCD0000000100100011010001010110011110001001101010111100110111101111S000000000001011110第十页，共94页。Content真值表问题1开关方程与标准形式2卡诺图3多变量卡诺图化简4混合逻辑组合电路5多输出函数6第十一页，共94页。列出真值表后，找出那些使函数值为1的变量取值组合，变量值为1的写成原变量，为0的写成反变量，这样对应于使函数值为1的每一个组合就可以写出一个乘积项，把这些乘积项加起来，可以得到函数的标准积之和。12第十二页，共94页。m7=a’bms m11=ab’ms m15=abms 写成积之和：

M=a’bms+ab’ms+abms化简后也可写作 M=bms+ab’ms 真值表注意：积项的下标与输入变量组合的关系13第十三页，共94页。m7=a’bms m11=ab’ms m15=abms

M=a’bms+ab’ms+abms M=bms+ab’ms

乘积项：一个与门实现的项bms,ab’ms

积之和：一个或门及两个或更多的与门实现M=bms+ab’ms

最小项：特殊情况的乘积项 m7，m11，m15

标准积之和：M=m7+m11+m15

(1)每个乘积项都包含了全部输入变量

(2)每个乘积项中的输入变量可以是原变量，或者反变量

(3)同一输入变量的原变量和反变量不同时出现在同一乘积项中。

这样的乘积项我们称为最小项。14第十四页，共94页。列出真值表后，找出那些使函数值为0的变量取值组合，变量值为0的写成原变量，为1的写成反变量，这样对应于使函数值为0的每一个组合就可以写出一个和项，把这些和项相乘，可以得到函数的标准和之积。15第十五页，共94页。由真值表导出开关方程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) 构造真值表注意：和项的下标与输入变量组合的关系16第十六页，共94页。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)(a’+m)(a’+m’+s)

最大项：特殊情况的和项：M0，M1，……

标准积之和：M=M0M1M2M3M4M5M6M8M9M10M12M13M14

(1)每一个和项中包含全部变量；

(2)和项中的变量可以原变量形式出现，也可以反变量形式出现；

(3)原、反变量不能同时出现在同一个和项中。这样的和项我们称为最大项。

17第十七页，共94页。标准形式简化形式标准积之和：当输出变量为逻辑1时定义的最小项的完整系列M=a’bms+ab’ms+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’)(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)18第十八页，共94页。ABCDS00000000100010000110010000101001100011101000010010101001011111000110111110111111练习：从真值表中生成开关方程，分别写出方程的积之和标准形式和和之积标准形式。开关方程的积之和标准形式为

S=m11+m13+m14+m15

=ab’cd+abc’d+abcd’+abcd开关方程的和之积标准形式为

S=M0•M1•M2•M3•M4•M5•M6•M7•M8•M9•M10•M1219第十九页，共94页。将一个积之和方程转换成标准形式的方法：

step1：在每个乘积项中标明所缺少的变量；

step2：将缺少变量及其反变量之和同相应的乘积项相与：xy(z+z’)； step3：应用分配律展开该项：xyz+xyz’.将一个和之积方程转换成标准形式的方法：

step1：在每个和项中标明所缺少的变量；

step2：将缺少变量及其反变量之积同相应的和项相或：x+y+zz’； step3：应用分配律展开该项：(x+y+z)(x+y+z’).20第二十页，共94页。最小项与最大项的数字表示最小项：

1)令正变量为1，反变量为0，写出每个乘积项的二进制表达式：ab’cd’:1010 2)将该二进制数转换为十进制数：(1010)2=(10)10 3)用mk(k为上述转换的十进制数)表示该最小项。最大项：

1)令正变量为0，反变量为1，写出每个和项的二进制表达式：x+y’+z’:011 2)将该二进制数转换为十进制数：(011)2=(3)10 3)用Mk(k为上述转换的十进制数)表示该最大项。最小项为最大项之反21第二十一页，共94页。例：将下列方程转换成相应的标准形式：

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= ab’c+ab’c’+abc’+ab’c’+abc+a’bc

step4:P=m5+m4+m6+m7+m3

=∑m(3,4,5,6,7)22第二十二页，共94页。

2.Y(a,b,c,d)=ab’c’d+bcd+a’d(积之和) step1:ab’c’d:无缺少项;bcd:缺少a;a’d:缺少b,c项 step2:Y=ab’c’d+(a+a’)bcd+a’(b+b’)(c+c’)d step3: Y=ab’c’d+abcd+a’bcd+a’bcd+a’b’cd+ab’c’d+abc’d

step4:Y=m9+m15+m7+m3+m13

=∑m(3,7,9,13,15)23第二十三页，共94页。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)

step3：T=(a+b’+c)(a+b’+c’)(a+b’+c)(a’+b’+c) step4：T=M2M3M6=∏M(2,3,6)24第二十四页，共94页。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)25第二十五页，共94页。练习:将下列布尔函数分别化为标准积之和与标准和之积 P=f(w,x,y,z)=w’x+yz’ T=f(a,b,c,d)=(a+b’+c)(a’+d)Ans:

P=f(w,x,y,z)=wxyz’+wx’yz’+w’xyz+w’x’yz’+w’xy’z +w’xy’z’+w’xyz’

=∑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)26第二十六页，共94页。最小项与最大项的相互转换step1：计算乘积项之和表达式中的每一个乘积项，即确定表示乘积项的二进制数；step2：确定step1中没有包含的所有二进制数；step3：为从step2得到的每一个二进制数写出相应的和项，并以和项之乘积形式表达。27第二十七页，共94页。例：把该最小项之和转换为最大项之积

f1(a,b,c)=a’b’c+a’bc’+ab’c’+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’)28第二十八页，共94页。练习：把下面的最小项之和表达式转换为等价的最大项之积表达式：29第二十九页，共94页。Content组合逻辑的定义1标准形式2卡诺图3多变量卡诺图化简4混合逻辑组合电路5多输出函数6第三十页，共94页。卡诺图提供了简化布尔表达式的一种系统方法，如果正确使用，会得到尽可能简化的积之和或和之积表达式；卡诺图是用图示方法将各种输入变量取值组合下的输出函数值一一表达出来；卡诺图和真值表一样可以表示逻辑函数和输入变量之间的逻辑关系，每一个小方格对应着真值表中的一行取值组合；卡诺图中每一个小方格对应着逻辑函数中的一个最小项或最大项。31第三十一页，共94页。卡诺图与真值表0、1方格：对应着输入A反变量；0，2方格：对应着输入B的反变量；1、3方格：对应着输入B的正变量；2、3方格：对应着输入A的正变量相邻方格只有一位不同。32第三十二页，共94页。m0m3m1m20110AB二变量卡诺图m0m1m3m7m5m2m6m40001111001ABC三变量卡诺图m0m1m3m5m13m9m4m12m8m6m14m10m7m15m11m2ABCD0001111000011110四变量卡诺图相邻方格只有一位不同33第三十三页，共94页。卡诺图与真值表10011110AB01230021两个最小项相加可以消去互为反变量的因子卡诺图形象地表达了变量各个最小项之间在逻辑上的相邻性。仅有一个变量不同的小方格相邻有一个以上变量不同的小方格不相邻34第三十四页，共94页。在卡诺图中，一个最小项对应图中一个变量取值的组合（反映在编号上）的小格子，两个逻辑相邻的最小项对应的小格子位置间有以下三种情况：

①相接—紧挨②相对—各在任一行或一列的两头③相重—对折起来位置相重合35第三十五页，共94页。三变量卡诺图36第三十六页，共94页。三变量卡诺图与最小项的关系37第三十七页，共94页。将布尔方程转换为卡诺图step1：观察变量个数，确定卡诺图中变量个数；step2：确定卡诺图中变量排列格式，以及卡诺图中每一格中变量的取值组合：step3：如方程不是标准形式，将布尔方程转换为积之和标准形式；step4：如标准形式为积之和，找到每一项取值组合在卡诺图中的位置，填1，其余位置填0。注：如标准形式为和之积，也可直接填入卡诺图中，注意与积之和标准形式的区别。38第三十八页，共94页。例：根据下面的布尔方程构造卡诺图：解：1.确定变量个数：三变量2.确定卡诺图格式：格式1：ABC00011110011111139第三十九页，共94页。格式2：BCA00011110011111140第四十页，共94页。例：根据下面布尔方程构造卡诺图： f(a,b,c)=ac’+abc+bc’解：step1：观察变量个数：三变量；step2：确定卡诺图格式：abc000111100141第四十一页，共94页。 step3：转换为标准形式： f(a,b,c)=ac’+abc+bc’

=ac’(b+b’)+abc+(a+a’)bc’ =abc’+ab’c’+abc+abc’+a’bc’ =abc’+ab’c’+abc+a’bc’step4:填入卡诺图111abc0001111001142第四十二页，共94页。练习：根据下面布尔方程构造卡诺图：f1(x,y,z)=∑m(2,5,6,7)f2(x,y,z)=∑m(0,1,2,3,6)XYZ00011110011111XYZ00011110011111143第四十三页，共94页。44第四十四页，共94页。例：写出下面卡诺图所表示的标准积之和，并写出其中可消去的项。abc000111100111111标准积之和：可消去的项？相邻项45第四十五页，共94页。最小项两个最小项为一组四个最小项为一组三变量卡诺图中变量的消去只能1，2，4，8个最小项为一组46第四十六页，共94页。四变量卡诺图10110100m10m11m9m8m14m15m13m12m6m7m5m4m2m3m1m010110100WXYZ一个方格表示一个四变量的最小项；若2个相邻方格组成一个长方形表示一个三变量的乘积项；若4个相邻方格组成一个长方形表示一个二变量的乘积项；若8个相邻方格组合成一个长方形，表示一个变量的输入值；将16个方格合成一个，则代表逻辑1.47第四十七页，共94页。ABCD11111111111g(A,B,C,D)=A’+B’D’+BC’D11111111111将下面的布尔方程填入卡诺图中

(A,B,C,D)=∑m(0,1,2,3,4,5,6,7,8,10,13). step1：构造四变量卡诺图，标注输入变量 step2：将最小项填入相应位置的方格中0001111000011110A’B’D’BC’D48第四十八页，共94页。例：化简下面的布尔方程: f(a,b,c)=ac’+abc+bc’=a(b+b’)c’+abc+(a+a’)bc’=abc’+ab’c’+abc+abc’+a’bc’=abc’+ab’c’+abc+a’bc’ =ac’+ab+bc’化为标准最小项之和1111abc0001111001消去a，得到bc’消去b，得到ac’消去c，得到ab49第四十九页，共94页。abc00011110011例：化简下面的布尔方程:消去A，C，得到B’消去B，得到A’C111150第五十页，共94页。用卡诺图化简布尔方程：f1(x,y,z)=∑m(2,5,6,7)

f2(x,y,z)=∑m(0,1,2,3,6)

f1(x,y,z)=yz’+xzf2(x,y,z)=x’+yz’

xyz1111110101101001111

xyz51第五十一页，共94页。化简时应注意的几个问题：(1)圈必须覆盖所有的1。(2)对每一个圈，其中1的个数必须是2n个相邻的1。(3)圈的个数必须最少(乘积项最少)。(4)圈越大越好（消去的变量多）。(5)每个圈至少包含一个新的最小项。11111111111新的最小项新的最小项52第五十二页，共94页。蕴含:任何单个最小项或允许的最小项组。

图中红色虚线框所示质蕴含(PI):

不能与任何其他最小项或最小项组组合的蕴含。

图中AC’D’是质蕴含，A’BC’D,BCD还可以跟其他最小项组组合，所以不是质蕴含。必要质蕴含(EPI):包含一个或多个唯一的最小项，至少包含一个不被其他任何质蕴含所包含的最小项。

ABC’没有一个不被其他质蕴含包含的最小项，所以不是必要质蕴含，BD是必要质蕴含。111111A’BC’DBCDBDABC’AC’D’0001111000011110ABCD153第五十三页，共94页。例：蕴含：a’b’,acd,a’cd’,ad,b’a’b’

不是一个质蕴含因为它同时包含在

b’中.acd不是一个质蕴含因为它同时包含在ad中.

b’,ad,a’cd’是质蕴含b’,ad,a’cd’是必要质蕴含.11111111111b’ada’cd’a’b’acd0001111000011110abcd54第五十四页，共94页。111111111cdabf2(a,b,c,d),的卡诺图如下所示，找出其中的必要质蕴含。f2的必要质蕴含为b’d.0001111000011110质蕴含：a’c’db’da’bd’a’bc’bcd’acd’ab’c55第五十五页，共94页。111f(a,b,c,d)=∑m(0,1,4,5,8,11,12,13,15).

质蕴含个数：5

必要质蕴含：a’c’,c’d’,acd.Ans: f(a,b,c,d)=c’d’+a’c’+bc’+acd111111cdab`a’c’c’d’bc’abdacd56第五十六页，共94页。利用卡诺图化简下面的布尔方程F(x,y,z)=∑(0,2,3,4,5,7)质蕴含个数：6没有必要质蕴含。Ans:F(x,y,z)=x’z’+yz+xy’F(x,y,z)=y’z’+x’y+xz1010110100111

xyz1111010110100111

xyz111有多于一种的等价化简结果57第五十七页，共94页。f(a,b,c,d)=∑(0,3,4,5,7,11,13,15)

包含四个质蕴含 其中有三个为必要质蕴含

Ans: f(a,b,c,d)=a’c’d’+cd+bc11111111cdab58第五十八页，共94页。利用卡诺图化简下面的布尔方程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)59第五十九页，共94页。F(w,x,y,z)=∑(0,1,4,5,9,11,13,15)11111yzwx0001111000011110111ANS:F(w,x,y,z)=w’y’+wz60第六十页，共94页。F(a,b,c,d)=∑(0,1,2,4,5,6,8,9,12,13,14)1cdab00011110000111101111111111F(a,b,c,d)=c’+a’d’+bd’1abcd0001111000011110111111111161第六十一页，共94页。F(a,b,c,d)=∑(1,3,4,5,7,8,9,11,15)cdab0001111000011110111111111ANS:F(a,b,c,d)=cd+a’d+a’bc’+ab’c’62第六十二页，共94页。F(w,x,y,z)=∑(1,5,7,8,9,10,11,13,15)yzwx0001111000011110111111111F(w,x,y,z)=y’z+xz+wx’63第六十三页，共94页。不完全确定的函数(随意项)

随意项的产生 由于不可能所有的输入组合都发生，所以不可能知道每个输入变量组合的输出值。

不用作输出函数的一部分出现的最小项或最大项称为随意项。64第六十四页，共94页。

在存在随意项的情况下，可以把一个或几个随意项写进逻辑函数中，也可以把随意项从函数式中删掉，不影响函数值。因此在逻辑函数化简时，利用随意项有时会给化简带来方便。在卡诺图上，究竟将“d”(随意项)作为“1”还是“0”对待，应以得到的相邻最小项矩形组合最大，而且矩形组合数目最少为原则。65第六十五页，共94页。确定和使用随意项(don’tcareminterms)写出真值表；确定是否所有输入组合都用于产生输出，对于没有用于确定输出值的输入变量组合为随意项；在卡诺图中用特写的标号(d)标识出随意项；产生尽可能大的包含随意项与一般最小项组和的必要质蕴含；不要将随意项与它们自己组合。66第六十六页，共94页。例：8421BCD码输入的四舍五入电路真值表如右图所示dd1110dddd1111100100000010110100b3b2b1b067第六十七页，共94页。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)68第六十八页，共94页。69第六十九页，共94页。A=w+xz+xyB=x’y+x’z+xyz’C=y’z’+yzD=z’70第七十页，共94页。练习：化简下图所示的带随意项的卡诺图dd11dd0010111010dd11dd0010111010dd11dd0010111010abcd0001111000011110解：f=a’c’d+ab’+cd’+a’bc’

或 f=a’c’d+ab’+cd’+a’bd’71第七十一页，共94页。化简最大项方程利用卡诺图化简最大项方程与化简最小项方程的过程基本是一致的在化简最大项方程时，先对0分组产生最小和项对0分组的法则和对1分组的法则是一样的72第七十二页，共94页。和之积与卡诺图73第七十三页，共94页。0000110001111111abcd

F=(a’+b)(a’+c)(a+b’+c’+d)

例：依据右图所示卡诺图写出相应的和之积化简式

0001111000011110a’+ca’+ba+b’+c’+d74第七十四页，共94页。练习：利用卡诺图对下面的和之积表达式进行化简F=(C+D)(A+B+D)(A’+B+C)化为标准和之积：CDAB0001111000011110000000A+B+DA’+B+CC+D75第七十五页，共94页。Content真值表问题1标准形式2卡诺图3多变量卡诺图（了解）4混合逻辑组合电路5多输出函数6第七十六页，共94页。五变量卡诺图结构相同颜色块的项为卡诺图中的相邻项77第七十七页，共94页。五变量卡诺图结构相同颜色块的项为卡诺图中的相邻项78第七十八页，共94页。奎恩－麦克拉斯基法(Quine-Mcluskey)原理：合并两个相邻最小项，找出全部质蕴含项，再求必要质蕴含构成最简表达式。由于其列表过程有严格的算法，便于编制计算机解题程序由计算机完成逻辑函数的化简。79第七十九页，共94页。