电子科大数字电路41定理chenyuPPT优秀课件.ppt

c h a p t e r 4 CombinationalLogic Design Principles 2021/5/261v c h a p t e r 4v vSwitching Algebra vCombinational Circuit Analysisv Combinational Circuit Synthesisv Timing Hazards v 2021/5/262Basic Concept (基本概念基本概念)Logic circuits are classified into two types（逻辑电路分为两大类）v combinational logic circuit（组合逻辑电路） A combinational logic circuit is one whose outputs depend only on its current inputs.（任何时刻的输出仅取决与当时的输入） characteristic：：no feedback circuit vsequential logic circuit（时序逻辑电路） The outputs of a sequential logic circuit depend not only on the currentinputs, but also on the past sequence of inputs, possibly arbitrarily far backin time.（（任一时刻的输出不仅取决于当时的输入，还取决于过去的输入顺序）2021/5/2634.1 Switching Algebra 4.1.1 Axioms4.1.1 Axioms（公理（公理 ）） P185 P185v（（A1））X = 0 if X   1, （（A1’）） X = 1 if X   0v（（A2））If X = 0,then X’ = 1（（A2’））If X = 1,then X’ =0v（（A3））0·0 = 0 （（A3’）） 1+1 = 1v（（A4）） 1·1 = 1 （（A4’）） 0+0 = 0v（（A5）） 0·1 = 1·0 = 0 （（A5’）） 1+0 = 0+1 = 1We stated these axioms as a pair, with the only difference between A1 and A1’ being the interchange of the symbols 0 and 1. This is a characteristic of all the axioms of switching algebra . P（185）逻辑乘 logical multiplication dot乘点 multiplication dotLogical addition逻辑加逻辑加Plus sign(+)2021/5/2644.1.2 Single-Variable Theorems (单变量开关代数定理单变量开关代数定理) P188vIdentities (Identities (自等律自等律) )：： (T1) X + 0 = X (T1’) X · 1 = XvNull Elements(0-1Null Elements(0-1律律) )：： (T2) X + 1 = 1 (T2’) X · 0 = 0vIdempotency (Idempotency (同一律同一律): ): (T3) X + X = X (T3’) X · X = XvInvolution (Involution (还原律还原律) )：：(T4) ( X’ )’ = XvComplements (Complements (互补律互补律): ): (T5) X + X’ = 1 (T5’) X · X’ =0 变量和常量的关系变量和其自身的关系2021/5/2654.1.3 Two- and Three-Variable Theorems(1)vCommutativityCommutativity ( (交换律交换律) )› (T6)X + Y = Y + X (T6’) X · Y= Y ·X vAssociativityAssociativity ( (结合律结合律) )› (T7) X·(Y·Z) = (X·Y)·Z (T7’) X+(Y+Z) = (X+Y)+ZvDistributivity (Distributivity (分配律分配律) )› (T8) X·(Y+Z) = X·Y+X·Z (T8’) X+Y·Z = (X+Y)·(X+Z)Each of these theorems is easily proved by perfect induction.(可以利用完备归纳法证明公式和定理可以利用完备归纳法证明公式和定理) P188 Similar Relationship with General Algebra (与普通代数相似的关系与普通代数相似的关系)2021/5/2664.1.3 Two- and Three-VariableTheorems(2)vCovering(Covering(吸收律吸收律) )›(T9) X + X·Y = X (T9’) X·(X+Y) = XvCombining(Combining(合并律合并律) )›(T10) X·Y + X·Y’ = X (T10’) (X+Y)·(X+Y’) = XvConsensusConsensus（添加律（一致性定理））（添加律（一致性定理））›(T11) X·Y + X’·Z + Y·Z = X·Y + X’·Z›(T11’) (X+Y)·(X’+Z)·(Y+Z) = (X+Y)·(X’+Z)2021/5/267Notesvno power of number(没有变量的乘方) A·A·A  A3vcommon factor(允许提取公因子) AB+AC = A(B+C)vno division(没有定义除法) if AB=BC  A=C ?? ®No subtracting(没有定义减法没有定义减法) if A+B=A+C  B=C ??A=1, B=0, C=0AB=BC=0, A CA=1, B=0, C=1错！错！错！错！2021/5/2684.1.4 n-Variable Theorems (n变量定理变量定理)vGeneralized idempotency(广义同一律广义同一律)(T12) X + X + … + X = X (T12’) X · X · … · X = XvDeMorgan’s TheoremsDeMorgan’s Theorems( (德德. .摩根定理摩根定理) )(T13) (X1·X2·……·X n)’=X1’+ X2’ +……+X n’(T13’) (X1+ X2+ ……+X n)’= X1’ · X2’ ·……· X n’vGeneralized DeMorgan’s DeMorgan’s TheoremsTheorems (广广义义德德. .摩摩根根定定理理) ) (T14)[F(X1 ,X2 …,X n,+, ·)]’=F(X1’, X2’,…,X n’, ·,+)Most of these theorems can be proved using a two-step method called finite induction—first proving that the theorem is true for n = 2 (the basis step) and then proving that if the theorem is true for n = i, then it is also true forn = i + 1 (the induction step). P(190)2021/5/269finite induction (P190)vX + X + X + … + X = X + (X + X + …+ X) (i + 1 X’s on either side) = X + (X) (if T12 is true for n = i) = X (according to T3)2021/5/2610vDemorgan’s Theorems(摩根定理) (P191)(A · B)’ = A’ + B’(A + B)’ = A’ · B’2021/5/2611v反演规则(Complement Rules)：›swapping + and . and complementing all variables. · ·  + +，，0 0  1 1，变量取反，变量取反› 遵循原来的运算优先（遵循原来的运算优先（PriorityPriority）次序）次序 › 不属于单个变量上的反号应保留不变不属于单个变量上的反号应保留不变 complement of a logic expression (F)’ (反演定理反演定理) ( P192)2021/5/2612例例1 1：写出下面函数的反函数：写出下面函数的反函数 （（Complement function )Complement function ) F1 = A · (B + C) + C · D F2 = (A · B)’ + C · D · E’例例2 2：证明：证明 (A·B + A’·C)’ = A·B’ + A’·C’® 合理地运用反演定理能够将一些问题简化合理地运用反演定理能够将一些问题简化2021/5/2613合理地运用反演定理能够将一些问题简化合理地运用反演定理能够将一些问题简化(AB + A’C)’AB + A’C + BC = AB + A’C(A’+B’)(A+C’)A’A +A’C’ + AB’ + B’C’A’C’ + AB’ A’C’ + AB’ + B’C’Example 2：：prove (A·B + A’·C)’ = A·B’ + A’·C’2021/5/26144.1.5 duality(对偶定理对偶定理) (P193) FD(X1 , X2 , … , Xn , + , · , ’ ) = F(X1 , X2 , … ,Xn , · , + , ’ ) Principle of Duality Any theorem or identity in switching algebra remains trueif 0 and 1 are swapped and . and + are swapped throughout. the dual of a logic expression [F(X1,X2,…,Xn)]’ = FD(X1’,X2’,…,Xn’)2021/5/26154.1.5 duality(对偶定理对偶定理) (P193)v对偶规则对偶规则›·  +；；0  1›变换时不能破坏原来的运算顺序（优先级）变换时不能破坏原来的运算顺序（优先级）v对偶原理对偶原理 (Principle of Duality) (Principle of Duality)›若两逻辑式相等，则它们的对偶式也相等若两逻辑式相等，则它们的对偶式也相等例：例： 写出下面函数的对偶函数写出下面函数的对偶函数F1 = A + B · (C + D)F2 = ( A’·(B+C’) + (C+D)’ )’X + X · Y = XX · X + Y = X(错错)X · ( X + Y ) = X FD(X1 , X2 , … , Xn , + , · , ’ ) = F(X1 , X2 , … , Xn , · , + , ’ ) 2021/5/2616对偶定理（Duality Theorems）证明公式证明公式：：A+BC = (A+B)(A+C)A(B+C)AB+AC2021/5/2617Duality and Complement (对偶和反演对偶和反演) (P194.P195)对偶对偶(Duality)(Duality)：：FD(X1 , X2 , … , Xn , + , · , ’ ) = F(X1 , X2 , … , Xn , · , + , ’ ) 反演反演(Complement)(Complement)：： [ F(X1 , X2 , … , Xn , + , · ) ]’ = F(X1’ , X2’, … , Xn’ , · , + ) [ F(X1 , X2 , … , Xn) ]’ = FD(X1’ , X2’, … , Xn’ ) 正逻辑约定和负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系2021/5/2618G1ABFA B FL L LL H LH L LH H HElectrical FunctionTable (电气功能表电气功能表)A B F0 0 00 1 01 0 01 1 1Positive-LogicConventionA B F1 1 11 0 10 1 10 0 0Negative-LogicConventionPositive-Logic (正逻辑正逻辑)：： F = A·BNegative-Logic (负逻辑负逻辑)：： F = A+BThe relationship of Positive-Logic Convention and Negative-Logic Convention are Duality (正逻辑约定和负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系)2021/5/26192021/5/2620 Shannon’s expansion theorems(香农展开定理香农展开定理)香农展开定理主要用于证明等式或展开函数香农展开定理主要用于证明等式或展开函数, ,将函数展开一次可以使函数内部的变量数将函数展开一次可以使函数内部的变量数从从n n个减少到个减少到n-1n-1个个. .2021/5/2621Shannon’s expansion theoremsvF=X.Y+Y.Z =X(1.Y+Y.Z)+X’(0.Y+Y.Z)+Y(1.X+1.Z)+Y’(0.X+0.Z)+Z(X.Y+Y.1)+Z’(X.Y+Y.0) =X.Y.Z+X’.Y.Z+X.Y.Z’2021/5/2622举重裁判电路Y = F (A,B,C ) = A·(B+C)ABYCLogic circuit开关开关ABCABC1 1表闭合表闭合指示灯指示灯1 1 表亮表亮0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ABCYTruth table 4.1.6 Standard Representations of Logic Functions(逻辑函数的标准表示方法)&≥1ABCY00000111Logic Functions2021/5/2623 波形图(Wave Form)v将输出与输入信号变化的时间关系用波形的形式描述，就得到了波形图 2021/5/2624vTruth table Truth table 真值表真值表vproduct term 乘积项乘积项 sum term 求和项求和项 vA sum-of-products expression ““积之和积之和””表达式表达式vproduct-of-sums expression ““和之积和之积””表达式表达式vn-variable minterm n n 变量最小项变量最小项vn-variable maxterm n n 变量最大项变量最大项vnormal terms 标准项标准项vcanonical sum 标准和标准和vcanonical product 标准积标准积—— 最小项之和最小项之和—— 最大项之积最大项之积4.1.6 Standard Representations of Logic Functions (P196)2021/5/2625HomeworkP(230-232)v4.6（（a)；；v4.7(b)；；v4.8(ａａ)；；v4.９９(ａ、ａ、b、、e)；；v4.10(d 、、f)；；v4.12v4.34Please hand your home work on this Monday.2021/5/2626部分资料从网络收集整理而来，供大家参考，感谢您的关注！。