第三章組合邏輯原理

1第三章組合邏輯原理計算機學院

余波2組合邏輯的定義邏輯電路中沒有從輸出到輸入的反饋，且由功能完全的門系列構(gòu)成，就稱為組合邏輯電路。InputsOutputsCombinationalLogicFunctions······Content真值表問題1開關方程與標準形式2卡諾圖3多變量卡諾圖化簡4混合邏輯組合電路5多輸出函數(shù)64例：一個由電動馬達帶動的輸送原料的傳輸裝置，如果有原料要傳送且保護聯(lián)合開關沒有打開，兩個操作人員之一在位時可被啟動。請設計出該問題的邏輯圖表達式。5問題描述輸入：令a,b分別表示兩個操作人員1和操作人員2，操作人員在位用邏輯1表示，不在位則相應變量為邏輯0； 令s表示聯(lián)合開關，開關閉合用邏輯1表示，開關斷開為0； 令m表示原料的存在狀態(tài)，有原料用邏輯1表示，無原料用0表示； 令M表示馬達的狀態(tài)，馬達轉(zhuǎn)動用邏輯1表示，停止轉(zhuǎn)動用邏輯0表示。 構(gòu)造真值表6將一個書面問題描述轉(zhuǎn)換成真值表的過程確定所包含的輸入、輸出變量分析所給實際邏輯問題的因果關系，將引起事件的原因確定為輸入變量，將事件所產(chǎn)生的結(jié)果作為輸出函數(shù)。為每個變量分配助記符或字母或標識確定真值表的大小；看看有多少個輸入組合y=2x其中，x=輸入變量數(shù)，y=組合數(shù)構(gòu)造一個包含所有輸入變量組合的真值表仔細研究問題描述，確定使給定輸出為真的輸入組合7例3-4：一個傳輸系統(tǒng)從三個不同來源運輸原材料，三個源匯集為一個單輸出傳輸裝置。四個傳輸裝置有分離的馬達，可分開控制。輸出物品速度必須與源流速吻合。要實現(xiàn)這些，必須具備下列條件：如果源1有物品，源2和源3要關閉；如果源1空，則源2和源3或者兩者都可開啟。在不能從三個源獲得物品的情況下，輸出傳輸裝置要關閉，如果沒有物品，相應源傳輸裝置應關閉。S3S1S2m3m1m2m48s1,s2,s3：源1，源2，源3，有物品為1，無物品為0m1,m2,m3,m4:四個馬達，開啟為1，關閉為0。S3S1S2m3m1m2m49練習1：某產(chǎn)品有A、B、C、D四項質(zhì)量指標，其中A為主要指標，產(chǎn)品檢驗標準規(guī)定：當主要指標及兩項次要指標都合格時，產(chǎn)品定為合格品，否則定為不合格品。對該問題（1）設定輸入輸出變量及其取值；（2）列出真值表。（1）輸入：各項質(zhì)量指標A,B,C,D； 該項指標合格則等于1，否則等于0； 輸出：S：產(chǎn)品合格等于1，否則等于0.10ABCD0000000100100011010001010110011110001001101010111100110111101111S0000000000010111Content真值表問題1開關方程與標準形式2卡諾圖3多變量卡諾圖化簡4混合邏輯組合電路5多輸出函數(shù)612列出真值表后，找出那些使函數(shù)值為1的變量取值組合，變量值為1的寫成原變量，為0的寫成反變量，這樣對應于使函數(shù)值為1的每一個組合就可以寫出一個乘積項，把這些乘積項加起來，可以得到函數(shù)的標準積之和。13m7=a’bms m11=ab’ms m15=abms 寫成積之和：

M=a’bms+ab’ms+abms化簡后也可寫作 M=bms+ab’ms 真值表注意：積項的下標與輸入變量組合的關系14m7=a’bms m11=ab’ms m15=abms

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

乘積項：一個與門實現(xiàn)的項bms,ab’ms

積之和：一個或門及兩個或更多的與門實現(xiàn)M=bms+ab’ms

最小項：特殊情況的乘積項 m7，m11，m15

標準積之和：M=m7+m11+m15

(1)每個乘積項都包含了全部輸入變量

(2)每個乘積項中的輸入變量可以是原變量，或者反變量

(3)同一輸入變量的原變量和反變量不同時出現(xiàn)在同一乘積項中。

這樣的乘積項我們稱為最小項。15列出真值表后，找出那些使函數(shù)值為0的變量取值組合，變量值為0的寫成原變量，為1的寫成反變量，這樣對應于使函數(shù)值為0的每一個組合就可以寫出一個和項，把這些和項相乘，可以得到函數(shù)的標準和之積。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) 構(gòu)造真值表注意：和項的下標與輸入變量組合的關系17M0=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)

和項：一個或門實現(xiàn)的項 a+b,a+b’+m

和之積：一個與門及兩個或多個或門實現(xiàn)(a+b)(a+b’+m)(a+b’+m’+s)(a’+m)(a’+m’+s)

最大項：特殊情況的和項：M0，M1，……

標準積之和：M=M0M1M2M3M4M5M6M8M9M10M12M13M14

(1)每一個和項中包含全部變量；

(2)和項中的變量可以原變量形式出現(xiàn)，也可以反變量形式出現(xiàn)；

(3)原、反變量不能同時出現(xiàn)在同一個和項中。這樣的和項我們稱為最大項。

18標準形式簡化形式標準積之和：當輸出變量為邏輯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)19ABCDS00000000100010000110010000101001100011101000010010101001011111000110111110111111練習：從真值表中生成開關方程，分別寫出方程的積之和標準形式和和之積標準形式。開關方程的積之和標準形式為

S=m11+m13+m14+m15

=ab’cd+abc’d+abcd’+abcd開關方程的和之積標準形式為

S=M0?M1?M2?M3?M4?M5?M6?M7?M8?M9?M10?M1220將一個積之和方程轉(zhuǎn)換成標準形式的方法：

step1：在每個乘積項中標明所缺少的變量；

step2：將缺少變量及其反變量之和同相應的乘積項相與：xy(z+z’)； step3：應用分配律展開該項：xyz+xyz’.將一個和之積方程轉(zhuǎn)換成標準形式的方法：

step1：在每個和項中標明所缺少的變量；

step2：將缺少變量及其反變量之積同相應的和項相或：x+y+zz’； step3：應用分配律展開該項：(x+y+z)(x+y+z’).21最小項與最大項的數(shù)字表示最小項：

1)令正變量為1，反變量為0，寫出每個乘積項的二進制表達式：ab’cd’:1010 2)將該二進制數(shù)轉(zhuǎn)換為十進制數(shù)：(1010)2=(10)10 3)用mk(k為上述轉(zhuǎn)換的十進制數(shù))表示該最小項。最大項：

1)令正變量為0，反變量為1，寫出每個和項的二進制表達式：x+y’+z’:011 2)將該二進制數(shù)轉(zhuǎn)換為十進制數(shù)：(011)2=(3)10 3)用Mk(k為上述轉(zhuǎn)換的十進制數(shù))表示該最大項。最小項為最大項之反22例：將下列方程轉(zhuǎn)換成相應的標準形式：

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)23

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)243.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)254.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練習:將下列布爾函數(shù)分別化為標準積之和與標準和之積 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)27最小項與最大項的相互轉(zhuǎn)換step1：計算乘積項之和表達式中的每一個乘積項，即確定表示乘積項的二進制數(shù)；step2：確定step1中沒有包含的所有二進制數(shù)；step3：為從step2得到的每一個二進制數(shù)寫出相應的和項，并以和項之乘積形式表達。28例：把該最小項之和轉(zhuǎn)換為最大項之積

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’)29練習：把下面的最小項之和表達式轉(zhuǎn)換為等價的最大項之積表達式：Content組合邏輯的定義1標準形式2卡諾圖3多變量卡諾圖化簡4混合邏輯組合電路5多輸出函數(shù)631卡諾圖提供了簡化布爾表達式的一種系統(tǒng)方法，如果正確使用，會得到盡可能簡化的積之和或和之積表達式；卡諾圖是用圖示方法將各種輸入變量取值組合下的輸出函數(shù)值一一表達出來；卡諾圖和真值表一樣可以表示邏輯函數(shù)和輸入變量之間的邏輯關系，每一個小方格對應著真值表中的一行取值組合；卡諾圖中每一個小方格對應著邏輯函數(shù)中的一個最小項或最大項。32卡諾圖與真值表0、1方格：對應著輸入A反變量；0，2方格：對應著輸入B的反變量；1、3方格：對應著輸入B的正變量；2、3方格：對應著輸入A的正變量相鄰方格只有一位不同。33m0m3m1m20110AB二變量卡諾圖m0m1m3m7m5m2m6m40001111001ABC三變量卡諾圖m0m1m3m5m13m9m4m12m8m6m14m10m7m15m11m2ABCD0001111000011110四變量卡諾圖相鄰方格只有一位不同34卡諾圖與真值表10011110AB01230021兩個最小項相加可以消去互為反變量的因子卡諾圖形象地表達了變量各個最小項之間在邏輯上的相鄰性。僅有一個變量不同的小方格相鄰有一個以上變量不同的小方格不相鄰35在卡諾圖中，一個最小項對應圖中一個變量取值的組合（反映在編號上）的小格子，兩個邏輯相鄰的最小項對應的小格子位置間有以下三種情況：

①相接—緊挨②相對—各在任一行或一列的兩頭③相重—對折起來位置相重合36三變量卡諾圖37三變量卡諾圖與最小項的關系38將布爾方程轉(zhuǎn)換為卡諾圖step1：觀察變量個數(shù)，確定卡諾圖中變量個數(shù)；step2：確定卡諾圖中變量排列格式，以及卡諾圖中每一格中變量的取值組合：step3：如方程不是標準形式，將布爾方程轉(zhuǎn)換為積之和標準形式；step4：如標準形式為積之和，找到每一項取值組合在卡諾圖中的位置，填1，其余位置填0。注：如標準形式為和之積，也可直接填入卡諾圖中，注意與積之和標準形式的區(qū)別。39例：根據(jù)下面的布爾方程構(gòu)造卡諾圖：解：1.確定變量個數(shù)：三變量2.確定卡諾圖格式：格式1：ABC00011110011111140格式2：BCA00011110011111141例：根據(jù)下面布爾方程構(gòu)造卡諾圖： f(a,b,c)=ac’+abc+bc’解：step1：觀察變量個數(shù)：三變量；step2：確定卡諾圖格式：abc000111100142 step3：轉(zhuǎn)換為標準形式： 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:填入卡諾圖111abc0001111001143練習：根據(jù)下面布爾方程構(gòu)造卡諾圖：f1(x,y,z)=∑m(2,5,6,7)f2(x,y,z)=∑m(0,1,2,3,6)XYZ00011110011111XYZ0001111001111114445例：寫出下面卡諾圖所表示的標準積之和，并寫出其中可消去的項。abc000111100111111標準積之和：可消去的項？相鄰項46最小項兩個最小項為一組四個最小項為一組三變量卡諾圖中變量的消去只能1，2，4，8個最小項為一組47四變量卡諾圖10110100m10m11m9m8m14m15m13m12m6m7m5m4m2m3m1m010110100WXYZ一個方格表示一個四變量的最小項；若2個相鄰方格組成一個長方形表示一個三變量的乘積項；若4個相鄰方格組成一個長方形表示一個二變量的乘積項；若8個相鄰方格組合成一個長方形，表示一個變量的輸入值；將16個方格合成一個，則代表邏輯1.48ABCD11111111111g(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：構(gòu)造四變量卡諾圖，標注輸入變量 step2：將最小項填入相應位置的方格中0001111000011110A’B’D’BC’D49例：化簡下面的布爾方程: 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，得到ab50abc00011110011例：化簡下面的布爾方程:消去A，C，得到B’消去B，得到A’C111151用卡諾圖化簡布爾方程：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

xyz52化簡時應注意的幾個問題：(1)圈必須覆蓋所有的1。(2)對每一個圈，其中1的個數(shù)必須是2n個相鄰的1。(3)圈的個數(shù)必須最少(乘積項最少)。(4)圈越大越好（消去的變量多）。(5)每個圈至少包含一個新的最小項。11111111111新的最小項新的最小項53蘊含:任何單個最小項或允許的最小項組。

圖中紅色虛線框所示質(zhì)蘊含(PI):

不能與任何其他最小項或最小項組組合的蘊含。

圖中AC’D’是質(zhì)蘊含，A’BC’D,BCD還可以跟其他最小項組組合，所以不是質(zhì)蘊含。必要質(zhì)蘊含(EPI):包含一個或多個唯一的最小項，至少包含一個不被其他任何質(zhì)蘊含所包含的最小項。

ABC’沒有一個不被其他質(zhì)蘊含包含的最小項，所以不是必要質(zhì)蘊含，BD是必要質(zhì)蘊含。111111A’BC’DBCDBDABC’AC’D’0001111000011110ABCD154例：蘊含：a’b’,acd,a’cd’,ad,b’a’b’

不是一個質(zhì)蘊含因為它同時包含在

b’中.acd不是一個質(zhì)蘊含因為它同時包含在ad中.

b’,ad,a’cd’是質(zhì)蘊含b’,ad,a’cd’是必要質(zhì)蘊含.11111111111b’ada’cd’a’b’acd0001111000011110abcd55111111111cdabf2(a,b,c,d),的卡諾圖如下所示，找出其中的必要質(zhì)蘊含。f2的必要質(zhì)蘊含為b’d.0001111000011110質(zhì)蘊含：a’c’db’da’bd’a’bc’bcd’acd’ab’c56111f(a,b,c,d)=∑m(0,1,4,5,8,11,12,13,15).

質(zhì)蘊含個數(shù)：5

必要質(zhì)蘊含：a’c’,c’d’,acd.Ans: f(a,b,c,d)=c’d’+a’c’+bc’+acd111111cdab`a’c’c’d’bc’abdacd57利用卡諾圖化簡下面的布爾方程F(x,y,z)=∑(0,2,3,4,5,7)質(zhì)蘊含個數(shù)：6沒有必要質(zhì)蘊含。Ans:F(x,y,z)=x’z’+yz+xy’F(x,y,z)=y’z’+x’y+xz1010110100111

xyz1111010110100111

xyz111有多于一種的等價化簡結(jié)果58f(a,b,c,d)=∑(0,3,4,5,7,11,13,15)

包含四個質(zhì)蘊含 其中有三個為必要質(zhì)蘊含

Ans: f(a,b,c,d)=a’c’d’+cd+bc11111111cdab59利用卡諾圖化簡下面的布爾方程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)60F(w,x,y,z)=∑(0,1,4,5,9,11,13,15)11111yzwx0001111000011110111ANS:F(w,x,y,z)=w’y’+wz61F(a,b,c,d)=∑(0,1,2,4,5,6,8,9,12,13,14)1cdab00011110000111101111111111F(a,b,c,d)=c’+a’d’+bd’1abcd0001111000011110111111111162F(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’63F(w,x,y,z)=∑(1,5,7,8,9,10,11,13,15)yzwx0001111000011110111111111F(w,x,y,z)=y’z+xz+wx’64不完全確定的函數(shù)(隨意項)

隨意項的產(chǎn)生 由于不可能所有的輸入組合都發(fā)生，所以不可能知道每個輸入變量組合的輸出值。

不用作輸出函數(shù)的一部分出現(xiàn)的最小項或最大項稱為隨意項。65

在存在隨意項的情況下，可以把一個或幾個隨意項寫進邏輯函數(shù)中，也可以把隨意項從函數(shù)式中刪掉，不影響函數(shù)值。因此在邏輯函數(shù)化簡時，利用隨意項有時會給化簡帶來方便。在卡諾圖上，究竟將“d”(隨意項)作為“1”還是“0”對待，應以得到的相鄰最小項矩形組合最大，而且矩形組合數(shù)目最少為原則。66確定和使用隨意項(don’tcareminterms)寫出真值表；確定是否所有輸入組合都用于產(chǎn)生輸出，對于沒有用于確定輸出值的輸入變量組合為隨意項；在卡諾圖中用特寫的標號(d)標識出隨意項；產(chǎn)生盡可能大的包含隨意項與一般最小項組和的必要質(zhì)蘊含；不要將隨意項與它們自己組合。67例：8421BCD碼輸入的四舍五入電路真值表如右圖所示dd1110dddd1111100100000010110100b3b2b1b068A=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)6970A=w+xz+xyB=x’y+x’z+xyz’C=y’z’+yzD=z’71練習：化簡下圖所示的帶隨意項的卡諾圖dd11dd0010111010dd11dd0010111010dd11dd0010111010abcd0001111000011110解：f=a’c’d+ab’+cd’+a’bc’

或 f=a’c’d+ab’+cd’+a’bd’72化簡最大項方程利用卡諾圖化簡最大項方程與化簡最小項方程的過程基本是一致的在化簡最大項方程時，先對0分組產(chǎn)生最小和項對0分組的法則和對1分組的法則是一樣的73和之積與卡諾圖740000110001111111abcd

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

例：依據(jù)右圖所示卡諾圖寫出相應的和之積化簡式

0001111000011110a’+ca’+ba+b’+c’+d75練習：利用卡諾圖對下面的和之積表達式進行化簡F=(C+D)(A+B+D)(A’+B+C)化為標準和之積：CDAB0001111000011110000000A+B+DA’+B+CC+DContent真值表問題1標準形式2卡諾圖3多變量卡諾圖（了解）4混合邏輯組合電路5多輸出函數(shù)677五變量卡諾圖結(jié)構(gòu)相同顏色塊的項為卡諾圖中的相鄰項78五變量卡諾圖結(jié)構(gòu)相同顏色塊的項為卡諾圖中的相鄰項79奎恩－麥克拉斯基法(Quine-Mcluskey)原理：合并兩個相鄰最小項，找出全部質(zhì)蘊含項，再求必要質(zhì)蘊含構(gòu)成最簡表達式。由于其列表過程有嚴