电子科技大学-数字电路基础-Chapter 4-1 Switching Algebra

Chapter4

CombinationalLogicDesignPrinciplesLogicCircuitsCombinationallogiccircuitOutputsdependonlyonitscurrentinputsNofeedbackloopSequentiallogiccircuitOutputsdependonitscurrentinputsandpresentstatesFeedbackloopContentsSwitchingAlgebraAxiomsandTheoremsCombinational-CircuitAnalysisCombinational-CircuitSynthesisCombinational-CircuitMinimizationKarnaughMapsTimingHazards4.1SwitchingAlgebraBooleanAlgebra-formulatedbymathematicianGeorgeBoolein1854-basicrelationships&manipulationsforatwo-valuesystemSwitchingAlgebra-

adaptationofBooleanLogictoanalyzeranddescribebehaviorofrelays-ClaudeShannonofBellLabsin1938-thisworksforallswitches(mechanicalorelectrical)-wegenerallyusetheterms"BooleanAlgebra"&"SwitchingAlgebra"interchangeablyBooleanAlgebraWhatisAlgebra

-thebasicsetofrulesthattheelementsandoperatorsinasystemfollow

-theabilitytorepresentunknownsusingvariables

-thesetoftheoremsavailabletomanipulateexpressionsBoolean

-welimitournumbersettotwovalues(0,1)

-welimitouroperatorstoAND,OR,INVAxioms(公理)Axioms

-alsocalled"Postulates"

-minimalsetofbasicdefinitionsthatweassumetobetrue

-allotherderivationsarebasedonthesetruths

-sinceweonlyhavetwovaluesinoursystem,wetypicallydefineanaxiomandthenitscomplement(A1&A1')AxiomsAxiom#1"Identity"

-avariableXcanonlytakeon1or2values(0or1)

(A1)X=0,ifX≠1 (A1')X=1,ifX≠0

Axiom#2"Complement"

-aprimefollowingavariabledenotesaninversionfunction

(A2)ifX=0,thenX'=1 (A2')ifX=1,thenX'=0AxiomsAxiom#3"AND"

-alsocalled"LogicalMultiplication"

-adot(·)isusedtorepresentanANDfunction

(A3)0·0=0 (A3')1+1=1Axiom#4"OR"

-alsocalled"LogicalAddition"

-aplus(+)isusedtorepresentanORfunction

(A4)1·1=1 (A4')0+0=0

AxiomsAxiom#5"Precedence"

-multiplicationprecedesaddition (A5)0·1=1·0=0 (A5')0+1=1+0=1

Try F=0+1·(0+1·0’)’=? =0+1·1’=0TheoremsTheoremsuseourAxiomstoformulatemoremeaningfulrelationships&manipulationsatheoremisastatementofTRUTHthesetheoremscanbeprovedusingourAxiomswecanprovemosttheoremsusing“PerfectInduction“(完全归纳法)Single-VariableTheorems"Identity"(自等律)

X+0=X X·1=X"NullElement"(0-1律)

X+1=1 X·0=0"Involution"(还原律)

(X')'=X

"Idempotency"(同一律)

X+X=X X·X=X

"Complements"(互补律)

X+X'=1 X·X'=0VariablewithConstantVariablewithVariableMulti-VariableTheorems"Commutative"(交换律)

X+Y=Y+X X·Y=Y·X“Associative”(结合律) (X+Y)+Z=X+(Y+Z) (X·Y)·Z=X·(Y·Z)

“Distributive”(分配律) X·(Y+Z)=X·Y+X·Z (X+Y)·(X+Z)=X+Y·Z

likeordinaryalgebraProofsbyexhaustion: Letvariablesassumeallpossiblevaluesandshowvalidityofresultinallcases－usingtruthtableValidatetheoremsusingtruthtableX+YZ=(X+Y)(X+Z)XYZYZX+YX+ZG(X,Y,Z)0000010100111001011101110100000000000000011111111111111111111111F(X,Y,Z)NotesNOindexofvariable X·X·XX3NOdivision

ifXY=YZX=Z??NOsubtraction

ifX+Y=X+ZY=Z??X=1,Y=0,Z=0XY=XZ=0,XZX=1,Y=0,Z=1Wrong！Wrong！Multi-VariableTheorems“Covering”

(吸收律)

X+X·Y=X X·(X+Y)=X“Combining”

(组合律)

X·Y+X·Y'=X (X+Y)·(X+Y')=X“Consensus”

(一致性定律) X·Y+X'·Z+Y·Z=X·Y+X'·Z (X+Y)·(X'+Z)·(Y+Z)=(X+Y)·(X'+Z)Prove：X·Y+X’·Z+Y·Z=X·Y+X’·ZY·Z=

1·Y·Z

=

(X+X’)·Y·ZX·Y+X’·Z+(X+X’)·Y·Z=X·Y+X’·Z+X·Y·Z+X’·Y·Z=X·Y·(1+Z)+X’·Z·(1+Y)=X·Y+X’·ZProveConsensus(X+Y)+(X+Y)’=1X+X’=1X·Y+X·Y’=X(X’+Y)·(X·(Y’+Z))+(X’+Y)·(X·(Y’+Z))’=(X’+Y)SubstitutionTheorems

(代入定理)：

AnytheoremoridentitywithvariableXinswitchingalgebraremainstrueifsubstitutingallXwithanothervariableorlogicexpression.

Rememberallabovetheorems,andwecangetmoreusefulformulasbyanalogyTheorem-XOR

(异或)Commutative：XY=YXAssociative：X(YZ)=(XY)ZDistributive：X·(YZ)=(X·Y)(X·Z)

因果互换关系

XY=ZXZ=YYZ=XXYZW=00XYZ=WTheorem-XOR

(异或)VariableandConstant---

XX=0XX’=1X0=XX1=X’Multi-variable---——theresultdependsonthetotalnumberof“1”X0X1…Xn=

1变量为1的个数是奇数0变量为1的个数是偶数Theorem-XNOR

(同或)Commutative：X⊙Y=Y⊙X

Associative：X⊙(Y⊙Z)=(X⊙Y)⊙ZNODistributive：X(Y⊙Z)≠XY⊙XZ因果互换关系

X⊙Y=ZX⊙Z=YY⊙Z=XTheorem-XNOR

(同或)VariableandConstant---X⊙X=1X⊙X’=0X⊙1=XX⊙0=X’Multi-variable---——theresultdependsonthetotalnumberof“0”X0⊙X1⊙…⊙Xn=

1变量为0的个数是偶数0变量为0的个数是奇数XORvs.XNORAB’=A⊙BAB=A⊙B’AB’=A’BA’⊙B=A⊙B’Evenvariables’XORandXNOR---opposite

XY=(X⊙Y)’XYZW=(X⊙Y⊙Z⊙W)’Oddvariables’XORandXNOR---equal

XYZ=X⊙Y⊙Zn-VariableTheoremsGeneralizedidempotency

(广义同一律)X+X+…+X=XX·X·…·X=XShannon’sexpansiontheorems

(香农展开定理)香农展开定理主要用于证明等式或展开函数将函数展开一次可以使函数内部的变量数从n个减少到n-1个Prove:X·W+X’·Z+Z·W+X·Y’·Z·W=X·W+X’·ZX·W+X’·Z+Z·W+X·Y’·Z·W=X·(

1·W+1’·Z+Z·W+1·Y’·Z·W)+ X’·(0·W+0’·Z+Z·W+0·Y’·Z·W)=X·(W+Z·W+Y’·Z·W)+X’·(Z+Z·W)=X·W·(1+Z+Y’·Z)+X’·Z·(1+W)=X·W+X’·ZApplicationofShannon’sexpansiontheoremsn-VariableTheoremsDeMorgan’sTheorems

(摩根定律)——complementofalogicexpression(X·Y)’=X’+Y’(X+Y)’=X’·Y’反演定理Complementofalogicexpression(反演规则)

：ANDOR，01，complementingallvariablesKeeptheoperationorderoftheoriginalfunction(保持运算优先级）DoNOTchangetheprime(’)overmulti-variables(不属于单个变量上的反号应保留不变)Ex1：PerformthecomplementexpressionsF1=X·(Y+Z)+Z·WF2=(X·Y)’+Z·W·E’F1’=(X’+Y’Z’)(Z’+W’)=X’Z’+X’W’+Y’Z’+Y’Z’W’=X’Z’+X’W’+Y’Z’F2’=(X’+Y’)’(Z’+W’+E)Prove：(XY+X’Z)’XY+X’Z+YZ=XY+X’Z=(X’+Y’)(X+Z’)=X’X+X’Z’+XY’+Y’Z’=X’Z’+XY’

=X’Z’+XY’+Y’Z’Ex2：Prove(X·Y+X’·Z)’=X·Y’+X’·Z’DualityTheorems（对偶定理）

DualofalogicexpressionFD(X1,X2,…,Xn,+,·,’)=F(X1,X2,…,Xn,·,+,’)ANDOR；01Keeptheoperationorderoftheoriginalfunction

PrincipleofDualityIfalogicequationistrue,thenitsdualityremainstrue.

X+X·Y=XX·X+Y=XX+Y=XX·(X+Y)=XWrong！ApplicationofdualityProve：X+YZ=(X+Y)(X+Z)X(Y+Z)XY+XZEx：Performthedualities.F1=X+Y·(Z+W)F2=(X’·(Y+Z’)+(Z+W)’)’F1D=X·(Y+Z·W)F2D=(X’+Y·Z’)·(Z·W)’)’Complementvs.DualityDuality：FD(X1,X2,…,Xn,+,·,’)=F(X1,X2,…,Xn,·,+,’)Complement：[F(X1,X2,…,Xn,+,·)]’ =F(X1’

,X2’,…,Xn’

,·,+)[F(X1,X2,…,Xn)]’=FD(X1’

,X2’,…,Xn’

)SourceofDuality:Positive&NegativeLogicsPositive-logicConventionandNegative-logicConventionaredualities.G1XYFXYFLLLLHLHLLHHHfunctiontableXYF000010100111PositiveLogicXYF111101011000NegativeLogicPositive-logic：F=X·YNegative-logic：F=X+YRepresentationsofLogicFunctionsRepresentationsincommonuse:TruthTableLogicExpressionLogicCircuitTimingdiagram(Waveform)F=F(X,Y,Z)=X·(Y+Z)XYFZ&≥1XYZFLogicexpressionLogiccircuitSwitch:XYZ1-ONLampF:1-ON00000111000001010011100101110111XYZFTruthtable举重裁判电路Reallogiccircuitsfunctionhasanotherveryimportantanalogdimension–time.00000111000001010011100101110111ABCFTruthtableTimediagram(Waveform,波形图）TruthTablesRowWeassigna"RowNumber"foreachentrystartingat0VariablesWeenterallinputcombinationsinascendingorder.FunctionWesaytheoutputisafunctionoftheinputvariablesF(A,B,C)Row ABCF

0 00011 00102 01003 01114 10015 10106 11017 1111FormalDefinitionofTruthTablesn=thenumberofinputvariables2n=thenumberofinputcombinationsTruthTablesLet'salsodefinethefollowingterms---Literal(文字),avariableorthecomplementofavariable ex)A,B,C,A',B',C'ProductTerm(乘积项),asingleliteralorLogicalProductoftwoormoreliterals ex)AA·BB'·CSumorProducts(SOP)(积之和),theLogicalSumofProductTerms ex)A+B A·B+B'·CTruthTablesSumTerm(求和项),asingleliteraloraLogicalSumoftwoormoreliterals ex)A A+B'ProductofSums(POS)(和之积),theLogicalProductofSumTerms ex)(A+B)·(B'+C)ConversionsbetweendifferentrepresentationsLogicexpressionTruthtableLogicexpressionLogiccircuitTruthtable

LogicexpressionLogiccircuit

LogicexpressionLogicexpressionTruthtableF=X+Y’·Z+X’·Y·Z’000001010011100101110111XYZY’·ZX’·Y·Z’F110000000111111000000100“Sum-of-products”“AND-OR”LogicexpressionTruthtableF=(Y’+Z)·(X’+Y+Z’)000001010011100101110111XYZY’+ZX’+Y+Z’F001111111111111111110000“Product-of-sums”“OR-AND”LogicexpressionLogiccircuitF=A+BC+ABC+CABCBCTruthtable

LogicexpressionX’·Y·Z00000010010001111000101111011110XYZFX·Y’·ZX·Y·Z’F=X’·Y·Z+X·Y’·Z+X·Y·Z’“Sum-of-products”“AND-OR”Truthtable

Logicexpression00010011010001111000101111011111XYZFX+Y’+ZX’+Y+ZF=(X+Y’+Z)·(X’+Y+Z)“Product-of-sums”“OR-AND”Logiccircuit

LogicexpressionF=[(A+B)’+(A’+B’)’]’=(A+B)(A’+B’)=AB’+A’B=AB(A’+B’)’(A+B)’ABA’B’StandardRepresentationsofLogicFunctionsWhat’sthestandardrepresentations?NormalTerm(标准项),aterminwhichnovariableappearsmorethanonce ex)"Normal"A·BA+B'

ex)"Non-Normal" A·B·B'A+A'Standardrepresentations

Canonicalsum

(标准和)

Canonicalproduct

(标准积)－Minterm－MaxtermMinterm

(最小项)Minterm——anormalproducttermwithn-literalsthereare2nMintermsforagiventruthtable全体最小项之和为1任意两个最小项的乘积为0输入变量的每一组取值都使一个对应的最小项的值为1注意：XY不是最小项X’·Y’·Z’X’·Y’·ZX’·Y·Z’X’·Y·ZX·Y’·Z’X·Y’·ZX·Y·Z’X·Y·Z000001010011100101110111XYZMintermMaxterm

(最大项)Maxterm——anormalsumtermwithn-literalsthereare2nMaxtermsforagiventruthtable全体最大项之积为0任意两个最大项的和为1输入变量的每一组取值都使一个对应的最大项的值为0X+Y+ZX+Y+Z’X+Y’+ZX+Y’+Z’X’+Y+ZX’+Y+Z’X’+Y’+ZX’+Y’+Z’000001010011100101110111XYZMaxtermX’·Y’·Z’X’·Y’·ZX’·Y·Z’X’·Y·ZX·Y’·Z’X·Y’·ZX·Y·Z’X·Y·ZMintermm0m1m2m3m4m5m6m700000011010201131004101511061117XYZROWX+Y+ZX+Y+Z’X+Y’+ZX+Y’+Z’X’+Y+ZX’+Y+Z’X’+Y’+ZX’+Y’+Z’M0M1M2M3M4M5M6M7MaxtermStandardRepresentationsofLogicFunctionsStandardrepresentations---Canonicalsum

(标准和) ---Asumofthemintermscorrespondingtotruth-tablerowsforwhichthefunctionproducesa1outputCanonicalproduct

(标准积) ---Aproductofthemaxtermscorrespondingtotruth-tablerowsforwhichthefunctionproducesa0outputStandardRepresentationsofLogicFunctionsCanonicalsumofF

F=X'Y’Z’+X’YZ+XY’Z’+XYZ’+XYZ =∑X,Y,Z(0,3,4,6,7)CanonicalproductofF

F=(X+Y+Z’)(X+Y’+Z)(X’+Y+Z’)

=∏X,Y,Z(1,2,5)On-Set(开集)Off-Set(闭集)Row XYZF

0 00011 00102 01003