邏輯電路的分析和設(shè)計(jì)-1

第二章

邏輯電路中的代數(shù)基礎(chǔ)AlgebraicMethodsfortheAnalysisandSynthesisofLogicCircuitGeorgeBoole喬治·布爾（GeorgeBoole，1815年～1864年）是皮匠的兒子，1815年11月生于英格蘭的林肯郡。由于家境貧寒，布爾不得不在協(xié)助養(yǎng)家的同時(shí)為自己能受教育而奮斗，不管怎么說，他成了19世紀(jì)最重要的數(shù)學(xué)家之一。盡管他考慮過以牧師為業(yè)，但最終還是決定從教，而且不久就開辦了自己的學(xué)校。在備課的時(shí)候，布爾不滿意當(dāng)時(shí)的數(shù)學(xué)課本，便決定閱讀偉大數(shù)學(xué)家的論文。在閱讀偉大的法國(guó)數(shù)學(xué)家拉格朗日的論文時(shí)，布爾有了變分方面的新發(fā)現(xiàn)。變分是數(shù)學(xué)分析的分支，它處理的是尋求優(yōu)化某些參數(shù)的曲線和曲面。1848年，布爾出版了《TheMathematicalAnalysisofLogic》，這是它對(duì)符號(hào)邏輯諸多貢獻(xiàn)中的第一次。1849年。他被任命位于愛爾蘭科克的皇後學(xué)院的數(shù)學(xué)教授。1854年，他出版了《TheLawsofThought》，這是他最著名的著作。在這本書中布爾介紹了現(xiàn)在以他的名字命名的布爾代數(shù)。布爾撰寫了微分方程和差分方程的課本，這些課本在英國(guó)一直使用到19世紀(jì)末。布爾在1855年結(jié)婚，他的妻子使皇後校園一位希臘文教授的侄女。1864年，布爾死于肺炎，肺炎是他在暴風(fēng)雨天氣中盡管已經(jīng)濕淋淋的了仍堅(jiān)持上課引起的。主要內(nèi)容布爾代數(shù)基礎(chǔ)FundamentalsofBooleanAlgebra開關(guān)函數(shù)與開關(guān)電路SwitchingFunctions開關(guān)電路SwitchingCircuits組合電路分析AnalysisofCombinationalCircuits組合邏輯電路綜合SynthesisofCombinationalLogicCircuits應(yīng)用Applications邏輯電路的計(jì)算機(jī)輔助設(shè)計(jì)

Computer-AidedDesignofLogicCircuits1.布爾代數(shù)基礎(chǔ)

FundamentalsofBooleanAlgebra基本定義對(duì)偶規(guī)則反演規(guī)則基本定理一些例子1849,GEORGEBOOLE提出邏輯思維處理的形式描述公設(shè)1定義Postulates1.Definition

布爾代數(shù)是一個(gè)封閉的代數(shù)系統(tǒng),該系統(tǒng)包括一個(gè)由兩個(gè)或兩個(gè)以上的元素組成的集合K,以及兩種操作,‘·’和‘+’:滿足:a,bK有a

·

bK&a+bK.基本公設(shè)BasicPostulatesABooleanalgebraisaclosedalgebraicsystemcontainingasetKoftwoormoreelementsandthetwooperators.And+;alternatively,foreveryaandbinsetK,a·bbelongstoKanda+bbelongstoK(+iscalledORand·iscalledAND)公設(shè)2:1元,0元的存在性(existence):具有唯一的元素1K,0K,使得,aK,(1)a+0=a(2)a·1=a其中,0、1分別稱為或與操作的單位元(identityelement)。公設(shè)4:+與·

滿足結(jié)合律(associativity)：a,b,cK,(1)a+(b+c)=(a+b)+c(2)a

·

(b

·

c)=(a

·

b)

·

c公設(shè)3:+與·

滿足交換律(commutativity)：a,bK,(1)a+b=b+a(2)a

·

b=b

·

a基本公設(shè)BasicPostulates公設(shè)5:滿足+對(duì)·以及·對(duì)+的分配律(distributivity):a,b,cK,(1)a+(b·c)=(a+b)·(a+c)(2)a·(b+c)=a·b+a·c基本公設(shè)BasicPostulates公設(shè)6:補(bǔ)元(complement)的存在性：aK,唯一的aK,使得:a+a=1a·a=0對(duì)偶原理DualityTheprincipleofdualityisaveryimportantconceptinBooleanalgebra.Brieflystated,theprincipleofdualitypronouncesthat,ifanexpressionisvalidinBooleanalgebra,thedualoftheexpressionisalsovalid.Thedualexpresionisfound(建立)byreplacingall+operatorswith·,all·operatorwith+,alloneswithzeros,andallzeroswithones.對(duì)偶原理(FF’)對(duì)偶規(guī)則F:01+·F’:10·+對(duì)偶原理舉例a+(bc)=(a+b)(a+c)a·(b+c)=a·b+a·c邏輯表達(dá)式:由邏輯變量,邏輯值與邏輯操作(‘+’,‘·’)組成的表達(dá)式.對(duì)偶原理Duality邏輯表達(dá)式F成立F’成立操作的順序a+a=aa.a=a1.重疊律證明:a+a=(a+a).1=(a+a).(a+a)=a+a.a=a+0=a對(duì)偶規(guī)則證明:a.a=a.a+0=a.a+a.a=a.(a+a)=a.1=a

基本定理1

FundamentalTheoremsofBooleanAlgebraa+1=1a·0=0對(duì)偶規(guī)則基本定理2證明:a+1=(a+1)·1=1·(a+1)=(a+a)·(a+1)=a+a·1=a+a=1證明:a·0=a·(a·a)=(a·a)·a=a·a=0a+ab=aa(a+b)=a證明:a+ab=a.1+ab=a.(1+b)=a.1=aa(a+b)=(a+0)(a+b)=a+0.b=a+0=a基本定理3、4、5a=aa與a互補(bǔ)a·a=0a+a=1證明:a+ab=(a+a)(a+b)=1(a+b)=a+ba(a+b)=aa+ab=0+ab=aba+ab=a+ba(a+b)=abab+ab=a(a+b)(a+b)=a證明:ab+ab=a(b+b)=a.1=a(a+b)(a+b)=a+(bb)=a+0=aab+abc=ab+ac(a+b)(a+b+c)=(a+b)(a+c)證明:ab+abc=(ab+abc)+abc=ab+(abc+abc)=ab+ac(a+b)(a+b+c)=[(a+b)(a+b+c)](a+b+c)=(a+b)[(a+b+c)(a+b+c)]=(a+b)[(a+c)(b+b)]=(a+b)(a+c)基本定理6、7DeMorgan定理:(1)a+b=a.b(2)a.b=a+b(a+b)(a.b)=0(a+b)+a.b=1a+b=a.b基本定理8?想一想，為什么(a+b)(a.b)=0(a+b)+a.b=1a+b=a.babcd...z=a+b+c+d+...za+b+c+d+...+z=a.b.c.d....z基本定理?想一想，為什么基本定理9(a+b)(a+c)(b+c)=(a+b)(a+c)(b+c+aa)=(a+b)(a+c)(b+c+a)(b+c+a)ab+ac+bc=ab+ac(a+b)(a+c)(b+c)=(a+b)(a+c)ab+ac+bc=ab+ac+(a+a)bc=ab+ac+abc+abc運(yùn)算符+，或·，與，這個(gè)符號(hào)也可以被省略⊕，異或A⊕B=AB+AB⊙，同或A⊙B=AB+A·BA⊕B=A⊙B異或⊕的定理A⊕A=0A⊕A=1A⊕0=AA⊕1=AA⊕B=A⊙B=A⊕B⊕1A⊕B=B⊕AA⊕(B⊕C)=(A⊕B)⊕CA·(B⊕C)=(A·B)⊕(A·C)[“與”對(duì)“異或”的分配律]A⊕B⊕C=A⊙B⊙C用文氏圖(vendiagram)

來理解邏輯定理與邏輯或邏輯非邏輯異或邏輯A⊕B=AB+AB用文氏圖(vendiagram)

來理解邏輯定理與對(duì)異或的分配律成立用文氏圖(vendiagram)

來理解邏輯定理思考:或?qū)Ξ惢蚴欠窬哂蓄愃频姆峙渎?用文氏圖(vendiagram)

來理解邏輯定理?想一想開關(guān)代數(shù)(switchingalgebra):當(dāng)布爾代數(shù)中的集合K={0,1}時(shí),又稱為開關(guān)代數(shù)開關(guān)函數(shù)(switchingfunction):F(X1,X2,X3,...,Xn),其定義域和值域={0,1}.F1(X1,X2,X3,...,Xn)=F2(X1,X2,X3,...,Xn)X1,X2,X3,...,Xn

{0,1}的一組值,都有F1=F22.開關(guān)函數(shù)與開關(guān)電路開關(guān)函數(shù)中的3個(gè)重要規(guī)則（1）代入規(guī)則：在任何一個(gè)邏輯等式中，如將等式兩邊所有出現(xiàn)某一變量的地方都用同一函數(shù)式替代，則等式仍然成立。這個(gè)規(guī)則就是代入規(guī)則。代入規(guī)則擴(kuò)大了邏輯等式的應(yīng)用范圍。例如：A=(A+B)(A+B)則有：A+B=(A+B+C)(A+B+C)顯然，這是用A+B代替了A,用C代替了B開關(guān)函數(shù)中的3個(gè)重要規(guī)則（2）對(duì)偶規(guī)則(principleofduality)：將某一邏輯表達(dá)式中的‘·’換成‘+’、‘+’換成‘·’；0換成1，1換成0，就得到一個(gè)新的表達(dá)式。這個(gè)新的表達(dá)式就是原表達(dá)式的對(duì)偶式。如果兩個(gè)邏輯式相等，則它們的對(duì)偶式也相等。這就是對(duì)偶規(guī)則。例如：則左邊的對(duì)偶式為：所以有：A+B=A·BA+BA·B

右邊的對(duì)偶式為：A·B=A+B開關(guān)函數(shù)中的3個(gè)重要規(guī)則（3）反演規(guī)則(又稱為香農(nóng)定理)(Shannon’sTheorem)：如將某一邏輯式中的‘·’換成‘+’、‘+’換成‘·’；0換成1，1換成0；原變量換成反變量，反變量換成原變量，則所得到的邏輯表達(dá)式稱為原式的反演式。這種變換方法稱為反演規(guī)則。利用反演規(guī)則可以比較容易地求出一個(gè)函數(shù)的反函數(shù)。例如：其反演式為：A·B=A+BA+B=A·B開關(guān)函數(shù)中的3個(gè)重要規(guī)則注意(1)在運(yùn)用反演規(guī)則或?qū)ε家?guī)則的時(shí)候，要保持運(yùn)算的優(yōu)先級(jí)一致性。(2)在運(yùn)用反演規(guī)則（香農(nóng)定理）時(shí)，不是一個(gè)變量上的反號(hào)不能變動(dòng)。也就是，只改變單個(gè)變量。原變反，反變?cè)?。例如：其左邊的?duì)偶式為：A+BC=(A+B)(A+C)A(B+C)而非：AB+C對(duì)所有可能的輸入組合,求出其相應(yīng)的函數(shù)值.將所有可能的輸入組合與其對(duì)應(yīng)的函數(shù)值用表格的形式表現(xiàn)出來.該表稱為真值表.真值表(TruthTable)表示ABCF(A,B,C)00000010010001111000101011011111F(A,B,C)=AB+AC+AC書中P93,Table2.4(b)有錯(cuò)誤?。≌嬷当鞹ruthTables表示開關(guān)函數(shù)的真值表表示舉例F(a,b,c)=abc+abc+abc+abcSOP：SumOfProducts積之和POS：PruductOfSums和之積2.2.2開關(guān)函數(shù)的代數(shù)形式F(A,B,C)=AB+AC+BC積之和(SOP)積(與)項(xiàng)和之積(POS)F(A,B,C)=(A+B)(A+C)(B+C)和(或)項(xiàng)開關(guān)函數(shù)的代數(shù)形式范式CanonicalForms1,分為SOP和POS兩種2,對(duì)于其中的每一種,范式的意義是使得任何一個(gè)邏輯表達(dá)式都有唯一的標(biāo)準(zhǔn)形式.3,對(duì)于SOP而言,范式由若干個(gè)最小項(xiàng)之和形成4,同理,對(duì)于POS而言,范式由若干個(gè)最大項(xiàng)之積形成什么是最小項(xiàng)?最小項(xiàng)(min-terms):Forafunctionofnvariables,ifaproducttermcontainseachofthenvariablesexactlyonetimeincomplementedofun-complementedform.Thistermiscalledminterm(1)對(duì)于任一個(gè)最小項(xiàng),只有唯一的一組變量取值使其為1;(2)對(duì)于任兩個(gè)最小項(xiàng),其積為0;(3)所有最小項(xiàng)之和為1;(4)將最小項(xiàng)對(duì)應(yīng)的n位二進(jìn)制的數(shù)值(原變量為1,非變量為0)記作其下標(biāo)i,該項(xiàng)記作mi;(5)清一色由最小項(xiàng)之和組成的范式稱為積之和范式(canonicalsumofproducts)(canonicalSOP)最小項(xiàng)的性質(zhì)最小項(xiàng)范式一個(gè)積項(xiàng)稱為一個(gè)最小項(xiàng):若對(duì)于每個(gè)函數(shù)變量,該積項(xiàng)或者包含該變量或者包含改變量的反變量.若一個(gè)布爾函數(shù)表示為最小項(xiàng)之和的形式,成為最小項(xiàng)范式.每個(gè)最小項(xiàng)表示為一個(gè)二進(jìn)制數(shù):原變量表示為1,補(bǔ)變量表示為0.最小項(xiàng)

編碼

表示ABC010m2

ABC100m4開關(guān)函數(shù)的代數(shù)形式:范式CanonicalFormsF(A,B,Q,Z)=ABQZ+ABQZ+ABQZ+ABQZf(A,B,C)=ABC+ABC+ABC+ABC=m1+m3+m5+m6

例:將下列函數(shù)表示為最小項(xiàng)形式最小項(xiàng)范式CanonicalSOP舉例最大項(xiàng)(max-terms):Forafunctionofnvariables,ifasumtermcontainseachofthenvariablesexactlyonetimeincomplementedofun-complementedform.Thissumtermiscalledmaxterm什么是最大項(xiàng)?(1)對(duì)于任一個(gè)最大項(xiàng),只有唯一的一組變量取值使其為0;(2)對(duì)于任兩個(gè)最大項(xiàng),其和為1;(3)所有最大項(xiàng)之積為0;(4)將最大項(xiàng)對(duì)應(yīng)的n位二進(jìn)制(原變量為0,非變量為1)的數(shù)值記作其下標(biāo)i,該項(xiàng)記作Mi(5)清一色由最大項(xiàng)之積組成的范式稱為和之積范式(canonicalproductofsums)(canonicalPOS)最大項(xiàng)的性質(zhì)若一個(gè)布爾函數(shù)表示為最大項(xiàng)之和的形式,稱為最大項(xiàng)范式.每個(gè)最大項(xiàng)表示為一個(gè)二進(jìn)制數(shù):原變量表示為0,反變量表示為1.最大項(xiàng)

編碼

表示A+B+C101M5

A+B+C011M3最大項(xiàng)范式CanonicalPOS最大項(xiàng)范式一個(gè)和項(xiàng)稱為一個(gè)最大項(xiàng):若對(duì)于每個(gè)函數(shù)變量,該和項(xiàng)或者包含該變量或者包含改變量的反變量.最大項(xiàng)范式舉例!小提示最小項(xiàng)用的是m,原變量為1;最大項(xiàng)用的是M,原變量為0F(A,B,C)=(A+B+C)(A+B+C)(A+B+C)=M1·M3·M5

=ΠM(1,3,5)001011101例：將下列函數(shù)式轉(zhuǎn)換成最小項(xiàng)范式和最大項(xiàng)范式。最小項(xiàng)范式最大項(xiàng)范式范式CanonicalForms舉例最小項(xiàng)范式的生成列出真值表取出值為1的行原始表達(dá)式F(A,B,C)F(A,B,C)=Σm(0,2,4)最大項(xiàng)范式與最小項(xiàng)范式的關(guān)系最大項(xiàng)范式的生成列出真值表取出值為0的行原始表達(dá)式F(A,B,C)F(A,B,C)=ΠM(1,3,5,6,7)最大項(xiàng)范式與最小項(xiàng)范式的關(guān)系最大項(xiàng)范式與最小項(xiàng)范式的關(guān)系F(A,B,C)=ΠM(1,3,5,6,7)可見：F(A,B,C)=Σm(0,2,4)=ABC+ABC+ABC=(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C)結(jié)論：邏輯代數(shù)式F的最大項(xiàng)范式與最小項(xiàng)范式的下標(biāo)“互補(bǔ)”。最大項(xiàng)范式與最小項(xiàng)范式舉例已知函數(shù)F(A,B,C)=AB+BC+ABC，求F,F的最小項(xiàng)表達(dá)式和最大項(xiàng)表達(dá)式兩個(gè)思路：代數(shù)式法；真值表法答案：F=Σm(2,3,5,6)=ΠM(0,1,4,7)F=Σm(0,1,4,7)=ΠM(2,3,5,6)結(jié)論：邏輯代數(shù)式F的最大項(xiàng)范式與(F非)的最小項(xiàng)范式下標(biāo)相同；同理，F(xiàn)的最小項(xiàng)范式與(F非)的最大項(xiàng)范式下標(biāo)相同最大項(xiàng)與最小項(xiàng)關(guān)系總結(jié)（1）構(gòu)成最小項(xiàng)時(shí)，1代表原變量，0代表反變量。（2）構(gòu)成最大項(xiàng)時(shí)，0代表原變量，1代表反變量。（3）一個(gè)邏輯表達(dá)式的最小項(xiàng)范式的下標(biāo)和最大項(xiàng)范式的下標(biāo)互補(bǔ)。（4）對(duì)某一個(gè)下標(biāo)（任意一個(gè)），其最小項(xiàng)和最大項(xiàng)互補(bǔ)。最大項(xiàng)范式與最小項(xiàng)范式代數(shù)式法常見的擴(kuò)展思路：（1）A=A·1=A(B+B)=AB+AB（2）A=A+0=A+BB=(A+B)(A+B)P1682.20,2.21課堂練習(xí)：范式的推導(dǎo)Applications-1Aburglar(盜竊)alarmforabankisdesignedsothatitsensesfourinputsignallines.LineAisfromthesecretcontrolswitch,lineBisfromapressuresensorunderasteelsafe(保險(xiǎn)箱)inalockedcloset(櫥柜),lineCisfromabattery-poweredclock,andlineDisconnectedtoaswitchonthelockedclosetdoor.Thefollowingconditionsproducealogic1voltageoneachline:ABCD保險(xiǎn)箱控制開關(guān)有鎖櫥柜內(nèi)保險(xiǎn)箱下的壓力感應(yīng)器電子鐘櫥柜的鎖ABCD保險(xiǎn)箱控制開關(guān)有鎖櫥柜內(nèi)保險(xiǎn)箱下的壓力感應(yīng)器電子鐘櫥柜的鎖Applications-1Thefollowingconditionsproducealogic1voltageoneachline:A:Thecontrolswitchisclosed.B:Thesafeisinitsnormalpositioninthecloset.C:Theclockisbetween1000and1400hoursD:Theclosetdoorisclosed.A:保險(xiǎn)箱開關(guān)關(guān)上是1,打開是0B:保險(xiǎn)箱在原有位置的時(shí)候是1,被移走是0.C:電子鐘在工作時(shí)間(1000-1400hours)是1,在非工作時(shí)間是0D:櫥柜的門被關(guān)上是1.打開是0Applications-1Writetheequationsofthecontrollogicfortheburglaralarmthatproucesalogic1(ringsabell)

whenthesafeismovedandthe