逻辑电路的分析和设计-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