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