邏輯電路的分析和設計-1

第二章

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

Computer-AidedDesignofLogicCircuits1.布爾代數基礎

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

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

·

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

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

·

(b

·

c)=(a

·

b)

·

c公設3:+與·

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

·

b=b

·

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

基本定理1

FundamentalTheoremsofBooleanAlgebraa+1=1a·0=0對偶規則基本定理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互補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運算符+，或·，與，這個符號也可以被省略⊕，異或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)[“與”對“異或”的分配律]A⊕B⊕C=A⊙B⊙C用文氏圖(vendiagram)

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

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

來理解邏輯定理思考:或對異或是否具有類似的分配律?用文氏圖(vendiagram)

來理解邏輯定理?想一想開關代數(switchingalgebra):當布爾代數中的集合K={0,1}時,又稱為開關代數開關函數(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.開關函數與開關電路開關函數中的3個重要規則（1）代入規則：在任何一個邏輯等式中，如將等式兩邊所有出現某一變量的地方都用同一函數式替代，則等式仍然成立。這個規則就是代入規則。代入規則擴大了邏輯等式的應用范圍。例如：A=(A+B)(A+B)則有：A+B=(A+B+C)(A+B+C)顯然，這是用A+B代替了A,用C代替了B開關函數中的3個重要規則（2）對偶規則(principleofduality)：將某一邏輯表達式中的‘·’換成‘+’、‘+’換成‘·’；0換成1，1換成0，就得到一個新的表達式。這個新的表達式就是原表達式的對偶式。如果兩個邏輯式相等，則它們的對偶式也相等。這就是對偶規則。例如：則左邊的對偶式為：所以有：A+B=A·BA+BA·B

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

編碼

表示ABC010m2

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

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

編碼

表示A+B+C101M5

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

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

whenthesafeismovedandthe