1、1 1Chapter Chapter 4 4 Combinational Logic Combinational Logic Design PrinciplesDesign Principles(组合逻辑设计原理组合逻辑设计原理)Basic Logic Algebra (逻辑代数基础逻辑代数基础)Combinational-Circuit Analysis (组合电路分析组合电路分析)Combinational-Circuit Synthesis (组合电路综合组合电路综合)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)2 2R
2、eview of Chapter 3Review of Chapter 3Electronic Behavior of CMOS CircuitsLogic Voltage Levels (逻辑电压电平逻辑电压电平)DC Noise Margins (直流噪声容限直流噪声容限)Fan-In（扇入（扇入）Fun-Out(扇出扇出)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3 3Review of Chapter 3Review of Chapter 3Transmission Gates(传输门传输门)Schmitt-Trig
3、ger Inputs（Hysteresis）Three-State Outputs(Tri-State output)Open-Drain Outputs (Open-Collector Gate)ENEN_LABAENOUT逻辑符号逻辑符号ABZDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)4 4Review of Chapter 3Review of Chapter 3Logic LevelsCMOS(0-1.5V,3.5-5V)TTL(0-0.8V,2-5V)ECL(L=-1.8V,H=-0.9V)(L=3.6V,H=4.
4、4V)HIGH(高态高态)ABNOMAL(不正常状态不正常状态)LOW(低态低态)VOLmaxVILmaxVIHminVOHminDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)5 5Review of Chapter 3Review of Chapter 3Wired AND(线与线与)Open-Drain Outputs (Open-Collector Gate)Wired OR(线或线或)Emitter-Coupled Logic Gate （ECL,发射极耦合逻辑门发射极耦合逻辑门）ABZDigital Logic Des
5、ign and Application(数字逻辑设计及应用数字逻辑设计及应用)6 6Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)Review of Chapter 3Review of Chapter 3Positive Logic and Negative Logic(正逻辑和负逻辑正逻辑和负逻辑)Three basic logic functions:AND,OR,and NOT(三种基本逻辑：与、三种基本逻辑：与、或、非或、非)VOUTVINVccR获得高、低电平的基本原理获得高、低电平的基本原理7 7Review of
6、 Chapter 3(Review of Chapter 3(第三章内容回顾第三章内容回顾)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)Three kinds of Description Method (三种描述方法三种描述方法)：Truth Table(真值表真值表)Logic Expression(逻辑表达式逻辑表达式)Logic Circuit(逻辑符号逻辑符号)NAND and NOR(与非和或非与非和或非)8 88IntroductionIntroductionLets learn to design digita
7、l circuits,starting with a simple form of circuit:Combinational circuitOutputs depend solely on the present combination of the circuit inputs values2.1DigitalSystemb=0F=0DigitalSystemif b=0,then F=0if b=1,then F=1b=1F=1DigitalSystemb=0F=0(a)DigitalSystemb=1F=1 Vs.sequential circuit:Has“memory”that i
8、mpacts outputs tooDigitalSystemb=0F=1Cannot determine value of F solely from present input value(b)9 9Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)Basic Concepts(Basic Concepts(基本概念基本概念)Two Types of Logic Circuits(逻辑电路分为两大类逻辑电路分为两大类):Combinational Logic Circuit（组合逻辑电路组合逻辑电路）Sequential Log
9、ic Circuit（时序逻辑电路时序逻辑电路）Outputs depend only on its Current Inputs.(任何时刻的输出仅取决与当时的输入任何时刻的输出仅取决与当时的输入)Outputs depends not only on the current Inputs but also on the Past sequence of Inputs.(任一时刻的输出不仅取决与当时的输入，任一时刻的输出不仅取决与当时的输入，还取决于过去的输入序列还取决于过去的输入序列)电路特点：无反馈回路、无记忆元件电路特点：无反馈回路、无记忆元件1010Digital Logic Des
10、ign and Application(数字逻辑设计及应用数字逻辑设计及应用)4.1 4.1 Switching Algebra(Switching Algebra(开关代数开关代数)4.1.1 Axioms(公理公理)X=0,if X 1 X=1,if X 0 0=1 1=0 00=0 1+1=1 11=1 0+0=0 01=10=0 1+0=0+1=1F=0+1 (0+1 0)=0+1 111 114.1.2 Single-Variable Theorems4.1.2 Single-Variable Theorems(单变量开关代数定理单变量开关代数定理)Identities(自等律自等律
11、)：X+0=X X 1=XNull Elements(0-1律律)：X+1=1 X 0=0Involution(还原律还原律)：(X)=XIdempotency(同一律同一律)：X+X=X X X=XComplements(互补律互补律)：X+X=1 X X=0变量和变量和常量的常量的关系关系变量和变量和其自身其自身的关系的关系Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)1212Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)4.1.3 Two-and Three
12、-Variable Theorems(4.1.3 Two-and Three-Variable Theorems(二变二变量或三变量开关代数定理量或三变量开关代数定理)Similar Relationship with General Algebra (与普通代数相似的关系与普通代数相似的关系)Commutativity(交换律交换律)A B=B A A+B=B+AAssociativity(结合律结合律)A(BC)=(AB)C A+(B+C)=(A+B)+CDistributivity(分配律分配律)A(B+C)=AB+AC A+BC=(A+B)(A+C)可以利用真值表证明公式和定理可以利用
13、真值表证明公式和定理1313Perfect induction of the theoremUse the truth table to prove the functions on both side are same!zxyxzyzxyxTo prove,just evaluate all possibilities141414Example uses of the propertiesExample uses of the propertiesShow abc equivalent to cba.Use commutative property:a*b*c=a*c*b=c*a*b=c*b
14、*aShow abc+abc=ab.Use first distributive propertyabc+abc=ab(c+c).Complement property Replace c+c by 1:ab(c+c)=ab(1).Identity property ab(1)=ab*1=ab.a151515Example uses of the propertiesExample uses of the propertiesShow x+xz equivalent to x+z.Second distributive property Replace x+xz by(x+x)*(x+z).C
15、omplement property Replace(x+x)by 1,Identity property replace 1*(x+z)by x+z.a1616Notes(Notes(几点注意几点注意)不存在变量的指数不存在变量的指数 AAA A3允许提取公因子允许提取公因子 AB+AC=A(B+C)没有定义除法没有定义除法 if AB=BC A=C?没有定义减法没有定义减法 if A+B=A+C B=C?A=1,B=0,C=0AB=AC=0,A CA=1,B=0,C=1错！错！错！错！Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及
16、应用)1717Some Special RelationshipsSome Special Relationships(一些特殊的关系一些特殊的关系)Covering(吸收律吸收律)X+XY=X X(X+Y)=XCombining(组合律组合律)XY+XY=X (X+Y)(X+Y)=XConsensus 添加律（一致性定理）添加律（一致性定理）XY+XZ+YZ=XY+XZ(X+Y)(X+Z)(Y+Z)=(X+Y)(X+Z)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)1818对上述的公式、定理要熟记，做到举一反三对上述的公式、定
17、理要熟记，做到举一反三(X+Y)+(X+Y)=1A+A=1XY+XY=X(A+B)(A(B+C)+(A+B)(A(B+C)=(A+B)代入定理：代入定理：在含有变量在含有变量 X X 的逻辑等式中，如果将式中的逻辑等式中，如果将式中所有出现所有出现 X X 的地方都用另一个函数的地方都用另一个函数 F F 来代替，来代替，则等式仍然成立。则等式仍然成立。Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)1919Prove(证明证明)：XY+XZ+YZ=XY+XZYZ=1YZ =(X+X)YZXY+XZ+(X+X)YZ=XY+XZ+X
18、YZ+XYZ=XY(1+Z)+XZ(1+Y)=XY+XZDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)20204.1.4 n-Variable Theorems 4.1.4 n-Variable Theorems(n(n变量定理变量定理)Generalized idempotency theorem (广义同一律广义同一律)X+X+X=X X X X=XShannons expansion theorems (香农展开定理香农展开定理),0(),1(),(F212121nnnXXFXXXFXXXX),1(),0(),(F2121
19、21nnnXXFXXXFXXXXDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)2121Prove(证明证明)：AD+AC+CD+ABCD=AD+AC=A (1D+1C+CD+1BCD)+A (0D+0C+CD+0BCD)=A (D+CD+BCD)+A (C+CD)=AD(1+C+BC)+AC(1+D)=AD+ACDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)22224.1.4 n-Variable Theorems 4.1.4 n-Variable Theorem
20、s(n(n变量定理变量定理 )Demorgans Theorems(摩根定理摩根定理)2121)(nnXXXXXX 2121)(nnXXXXXX ),(),(2121 nnXXXFXXXF Complement Theorems(反演定理反演定理)(A B)=A+B(A+B)=A BDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)2323Complement Rules(反演规则反演规则)：+，0 1，Complementing Variables (变量取反变量取反)Follow the Priority Sequence as
21、 Before (遵循原来的运算优先次序遵循原来的运算优先次序)Keep the complement Symbol of Non-single variables(不属于单个变量上的反号应保留不变不属于单个变量上的反号应保留不变)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)2424Example 1：Write the Complement function for each of The Following Logic functions.(写出下面函数的反函数写出下面函数的反函数)F1=A (B+C)+C D F2=(A
22、 B)+C D EExample 2：Prove(AB+AC)=AB+AC 合理地运用反演定理能够将一些问题简化合理地运用反演定理能够将一些问题简化2525合理地运用反演定理能够将一些问题简化合理地运用反演定理能够将一些问题简化Prove：AB+AC=AB+ACAB+AC+BC=AB+AC(A+B)(A+C)AA+AC+AB+BCAC+AB AC+AB+BCDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)26264.1.5 Duality(4.1.5 Duality(对偶性对偶性)Duality Rule(对偶规则对偶规则)+；0
23、 1变换时不能破坏原来的运算顺序（优先级）变换时不能破坏原来的运算顺序（优先级）Principle of Duality(对偶原理对偶原理)若两逻辑式相等，则它们的对偶式也相等若两逻辑式相等，则它们的对偶式也相等例：例：Write the Duality function for each of the following Logic functions.(写出下面函数的对偶函数写出下面函数的对偶函数)F1=A+B (C+D)F2=(A(B+C)+(C+D)X+X Y=XX X+Y=XX+Y=XX (X+Y)=X FD(X1,X2,Xn,+,)=F(X1,X2,Xn,+,)Digital Lo
24、gic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)27274.1.5 Duality(4.1.5 Duality(对偶性对偶性)证明公式：证明公式：A+BC=(A+B)(A+C)A(B+C)AB+ACDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)Duality Rule(对偶规则对偶规则)+；0 1变换时不能破坏原来的运算顺序（优先级）变换时不能破坏原来的运算顺序（优先级）Principle of Duality(对偶原理对偶原理)若两逻辑式相等，则它们的对偶式也相等若两逻辑式相等，则它
25、们的对偶式也相等2828Two kind of logic Positive logic:1(high level)0(low level)Negative logic:0(high level)1(low level)If a logic relation exist in positive logic,it must be exist in negative logic.Both logic are duality for each other.Positive-Logic Convention and Negative-Logic ConventionAre Duality(正逻辑约定和
26、负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系)2929Duality and ComplementDuality and Complement(对偶和反演对偶和反演)Duality(对偶对偶)：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)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3030第第4 4章作业章作业（P230P230）Digital Logic Des
27、ign and Application(数字逻辑设计及应用数字逻辑设计及应用)4.4 T84.54.6 4.7(d)(i)4.8 (c)(h)补充：写出补充：写出 4.7(c)4.8(g)的对偶式和的对偶式和反演式反演式3131A Class Problem (A Class Problem (每课一题每课一题 )Write the Duality and Complement function for each of the following Logic functions.(分别写出下面函数的对偶函数和反函数分别写出下面函数的对偶函数和反函数)F1=A (B+C)+C DF2=(A(B+
28、C)+(C+D)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3232Chapter Chapter 4 4 Combinational Logic Combinational Logic Design PrinciplesDesign Principles(组合逻辑设计原理组合逻辑设计原理)Basic Logic Algebra (逻辑代数基础逻辑代数基础)Combinational-Circuit Analysis (组合电路分析组合电路分析)Combinational-Circuit Synthesis (组合电路综合组合
29、电路综合)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3333Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)Review of 4.1 Switching AlgebraReview of 4.1 Switching Algebra(开关代数内容回顾开关代数内容回顾)1、Axioms(公理公理)2、Single-Variable Theorems (单变量开关代数定理单变量开关代数定理)3、Two-and Three-Variable Theorems (二变量
30、或三变量开关代数定理二变量或三变量开关代数定理)需要特别记忆需要特别记忆：A+BC=(A+B)(A+C)AB+AC+BC=AB+AC 补充：代入定理补充：代入定理34344、n-Variable Theorems(n变量定理变量定理)Generalized Idempotency (广义同一律广义同一律)Shannons Expansion Theorems (香农展开定理香农展开定理)Demorgans Theorems 摩根定理（反演）摩根定理（反演）Duality(对偶对偶)X+X+X=XX X X=X),(F21nXXX),1(21nXXFX ),0(21nXXFX Review of
31、 4.1 Switching AlgebraReview of 4.1 Switching Algebra(开关代数内容回顾开关代数内容回顾)3535Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)与与或，或，0 1变量取反变量取反 F(X1,X2,Xn)=FD(X1,X2,Xn)与与或，或，0 1Review of 4.1 Switching AlgebraReview of 4.1 Switching Algebra(开关代数内容回顾开关代数内容回顾)n-Variable Theorems(n变量定理变量定理)Generali
32、zed Idempotency (广义同一律广义同一律)Shannons Expansion Theorems (香农展开定理香农展开定理)Demorgans Theorems 摩根定理（反演）摩根定理（反演）Duality(对偶对偶)3636Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)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
33、1 11 0 10 1 10 0 0Negative-LogicConventionPositive-Logic (正逻辑正逻辑)：F=ABNegative-Logic (负逻辑负逻辑)：F=A+BThe relationship of Positive-Logic Convention and Negative-Logic Convention are Duality(正逻辑约定和负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系)3737Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)举重裁判电路举重裁判电路Y=F(A,
34、B,C)=A(B+C)ABYC逻逻辑辑函函数数逻辑图逻辑图开关开关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 A B CY真值表真值表补充：逻辑函数及其表示方法补充：逻辑函数及其表示方法&1ABCY00000111383838Gates vs.switchesGates vs.switchesNotice Boolean algebra enables easy capture as equation and conversion to circuitHow design with s
35、witches?393939Gates vs.switchesGates vs.switchesOf course,logic gates are built from switches,but we think at level of logic gates,not switchesw=NOT(s)AND kakswBelt WarnSeatbeltBelt Warnw1001sk404040Some Gate-Based Circuit Drawing Some Gate-Based Circuit Drawing ConventionsConventionsnoyesnot okokxy
36、Fnoyes414141Boolean AlgebraBoolean AlgebraBy defining logic gates based on Boolean algebra,we can use algebraic methods to manipulate circuitsNotation:Writing a AND b,a OR b,NOT(a)is cumbersomeUse symbols:a*b(or just ab),a+b,and a2.5424242Boolean AlgebraBoolean AlgebraOriginal:w=(p AND NOT(s)AND k)O
37、R t New:w=psk+tlSpoken as“w equals p and s prime and k,or t”lOr just“w equals p s prime k,or t”ls known as“complement of s”While symbols come from regular algebra,dont say“times”or“plus”lproduct and sum are OK and commonly used2.5434343Boolean AlgebraBoolean AlgebraBoolean algebra precedence,highest
38、 precedence first.Symbol Name Description ()Parentheses Evaluate expressions nested in parentheses first NOT Evaluate from left to right *AND Evaluate from left to right +OR Evaluate from left to right 2.5444444Boolean Algebra TerminologyBoolean Algebra TerminologyExample equation:F(a,b,c)=abc+abc+a
39、b+cVariableRepresents a value(0 or 1)Three variables:a,b,and cLiteralAppearance of a variable,in true or complemented formNine literals:a,b,c,a,b,c,a,b,and c454545Boolean Algebra TerminologyBoolean Algebra TerminologyProduct termProduct of literalsFour product terms:abc,abc,ab,cSum-of-productsEquati
40、on written as OR of product terms onlyAbove equation is in sum-of-products form.“F=(a+b)c+d”is not.4646Combinational logic The output is determined only by its input.Output can be changed when input changed.474747Representations of Boolean FunctionsRepresentations of Boolean Functions2.6aFCircuit 2(
41、d)English 1:F outputs 1 when a is 0 and b is 0,or when a is 0 and b is 1.English 2:F outputs 1 when a is 0,regardless of b s value(a)(b)a0011b0101F1100abFCircuit 1(c)The function FTruth tableEquation 2:F(a,b)=a Equation 1:F(a,b)=a b +a b484848Representations of Boolean FunctionsRepresentations of Bo
42、olean FunctionsA function can be represented in different waysAbove shows seven representations of the same functions F(a,b),using four different methods:English Equation Circuit and Truth Table2.6a4949Representations of logic functionsTruth tableTiming diagramLogic equationsLogic circuits5050Truth
43、tableLeft:the input combinations in binary order Right:the output for the input5151Logic design:Construct a Truth table A device with majority judge function output the majority input state.5252 Full adder add three input numbers to get their sum.Logic design:Construct a Truth table5353 4-bits prime
44、-number detector when input is(1,2,3,5,7,11,13),the output is 1,otherwise the output is 0.Logic design:Construct a Truth table5454 4-bit Binary to Gray code converter change binary input to Gray code output.Logic design:Construct a Truth table555555Converting among RepresentationsConverting among Re
45、presentationsCan convert from any representation to anotherCommon conversionsEquation to circuit Circuit to equationStart at inputs,write expression of each gate outputcchF=c(h+p)ph+pCircuitsEquationsTruth table341265565656Converting among RepresentationsConverting among RepresentationsMore common c
46、onversionsTruth table to equation(which we can then convert to circuit)Easyjust OR each input term that should output 1Equation to truth tableEasyjust evaluate equation for each input combination(row)Creating intermediate columns helpsaCircuitsEquationsTruth table341265575757Example:Converting from
47、Circuit to Example:Converting from Circuit to Truth TableTruth TableFirst convert to circuit to equation,then equation to tableFacbabc(ab)(ab)ca00001111c01010101b00110011F10101000ab00000011(ab)11111100c10101010InputsOutputs585858Standard Representation:Truth TableStandard Representation:Truth TableH
48、ow can we determine if two functions are the same?Recall automatic door exampleSame as f=hc+hpc?Used algebraic methodsBut if we failed,does that prove not equal?No.Solution:Convert to truth tables Only ONE truth table representation of a given functionStandard representationfor given function,only o
49、ne version in standard form exists595959Standard Representation:Truth TableStandard Representation:Truth Tablef=c hp+c hp +c h f=c h(p+p)+c h p f=c h(1)+c h p f=c h+c h p(what if we stopped here?)f=hc +h pc a0011b0101F1101F=ab+aa0011b0101F1101F=a b +a b+abQ:Determine if F=ab+a is samefunction as F=a
50、 b+a b+ab,by converting each to truth table firstSame6060Logic Expression to Truth TableLogic Expression to Truth Table(逻辑表达式逻辑表达式 真值表真值表)Y=(B+C)(A+B+C)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCB+C A+B+CY001111110111111111110000 Product-of-Sums Expression(“和之积和之积”表达式表达式“或或-与与”式式)Digital Logic Desig
