電子科技大學(xué)-數(shù)字電路基礎(chǔ)-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"(互補(bǔ)律)

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

X+Y=Y+X X·Y=Y·X“Associative”(結(jié)合律) (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)

因果互換關(guān)系

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

(異或)VariableandConstant---

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

1變量為1的個(gè)數(shù)是奇數(shù)0變量為1的個(gè)數(shù)是偶數(shù)Theorem-XNOR

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

Associative：X⊙(Y⊙Z)=(X⊙Y)⊙ZNODistributive：X(Y⊙Z)≠XY⊙XZ因果互換關(guān)系

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的個(gè)數(shù)是偶數(shù)0變量為0的個(gè)數(shù)是奇數(shù)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óng)展開(kāi)定理)香農(nóng)展開(kāi)定理主要用于證明等式或展開(kāi)函數(shù)將函數(shù)展開(kāi)一次可以使函數(shù)內(nèi)部的變量數(shù)從n個(gè)減少到n-1個(gè)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(反演規(guī)則)

：ANDOR，01，complementingallvariablesKeeptheoperationorderoftheoriginalfunction(保持運(yùn)算優(yōu)先級(jí)）DoNOTchangetheprime(’)overmulti-variables(不屬于單個(gè)變量上的反號(hào)應(yīng)保留不變)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（對(duì)偶定理）

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(乘積項(xiàng)),asingleliteralorLogicalProductoftwoormoreliterals ex)AA·BB'·CSumorProducts(SOP)(積之和),theLogicalSumofProductTerms ex)A+B A·B+B'·CTruthTablesSumTerm(求和項(xiàng)),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(標(biāo)準(zhǔn)項(xiàng)),aterminwhichnovariableappearsmorethanonce ex)"Normal"A·BA+B'

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

Canonicalsum

(標(biāo)準(zhǔn)和)

Canonicalproduct

(標(biāo)準(zhǔn)積)－Minterm－MaxtermMinterm

(最小項(xiàng))Minterm——anormalproducttermwithn-literalsthereare2nMintermsforagiventruthtable全體最小項(xiàng)之和為1任意兩個(gè)最小項(xiàng)的乘積為0輸入變量的每一組取值都使一個(gè)對(duì)應(yīng)的最小項(xiàng)的值為1注意：XY不是最小項(xiàng)X’·Y’·Z’X’·Y’·ZX’·Y·Z’X’·Y·ZX·Y’·Z’X·Y’·ZX·Y·Z’X·Y·Z000001010011100101110111XYZMintermMaxterm

(最大項(xiàng))Maxterm——anormalsumtermwithn-literalsthereare2nMaxtermsforagiventruthtable全體最大項(xiàng)之積為0任意兩個(gè)最大項(xiàng)的和為1輸入變量的每一組取值都使一個(gè)對(duì)應(yīng)的最大項(xiàng)的值為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

(標(biāo)準(zhǔn)和) ---Asumofthemintermscorrespondingtotruth-tablerowsforwhichthefunctionproducesa1outputCanonicalproduct

(標(biāo)準(zhǔn)積) ---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(開(kāi)集)Off-Set(閉集)Row XYZF

0 00011 00102 01003