1、Chapter Chapter 4 4 Combinational Logic Combinational Logic Design PrinciplesDesign Principles(组合逻辑设计原理组合逻辑设计原理)Basic Logic Algebra (逻辑代数基础逻辑代数基础)Combinational-Circuit Analysis (组合电路分析组合电路分析)Combinational-Circuit Synthesis (组合电路综合组合电路综合)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)1 1Digi
2、tal Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)Review of 4.1 Switching Algebra(开关代数内容回顾)1、Axioms(公理)2、Single-Variable Theorems (单变量开关代数定理)3、Two-and Three-Variable Theorems (二变量或三变量开关代数定理)需要特别记忆：A+BC=(A+B)(A+C)AB+AC+BC=AB+AC 补充：代入定理2 24、n-Variable Theorems(n变量定理变量定理)Generalized Idempotency (广义同一
3、律广义同一律)Shannons Expansion Theorems (香农展开定理香农展开定理)Demorgans Theorems 摩根定理（反演）摩根定理（反演）Duality(对偶对偶)X+X+X=XX X X=X),(F21nXXX),1(21nXXFX ),0(21nXXFX Review of 4.1 Switching AlgebraReview of 4.1 Switching Algebra(开关代数内容回顾开关代数内容回顾)3 3Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)与与或，或，0 1变量取反变量取
4、反 F(X1,X2,Xn)=FD(X1,X2,Xn)与与或，或，0 1Review of 4.1 Switching AlgebraReview of 4.1 Switching Algebra(开关代数内容回顾开关代数内容回顾)n-Variable Theorems(n变量定理变量定理)Generalized Idempotency (广义同一律广义同一律)Shannons Expansion Theorems (香农展开定理香农展开定理)Demorgans Theorems 摩根定理（反演）摩根定理（反演）Duality(对偶对偶)4 4Digital Logic Design and A
5、pplication(数字逻辑设计及应用数字逻辑设计及应用)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=ABNegative-Logic (负逻辑负逻辑)：F=A+BThe relationship of Positive-Logic Convention and
6、 Negative-Logic Convention are Duality(正逻辑约定和负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系)5 5Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)举重裁判电路举重裁判电路Y=F(A,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真值表真值表补充：逻辑函数及其表示方法补充：逻辑函数及其表示方法&
7、1ABCY000001116 67Gates vs.switchesGates vs.switchesNotice Boolean algebra enables easy capture as equation and conversion to circuitHow design with switches?7 78Gates vs.switchesGates vs.switchesOf course,logic gates are built from switches,but we think at level of logic gates,not switchesw=NOT(s)AN
8、D kakswBelt WarnSeatbeltBelt Warnw1001sk8 89Some Gate-Based Circuit Drawing Some Gate-Based Circuit Drawing ConventionsConventionsnoyesnot okokxyFnoyes9 910Boolean AlgebraBoolean AlgebraBy defining logic gates based on Boolean algebra,we can use algebraic methods to manipulate circuitsNotation:Writi
9、ng a AND b,a OR b,NOT(a)is cumbersomeUse symbols:a*b(or just ab),a+b,and a2.5101011Boolean AlgebraBoolean AlgebraOriginal:w=(p AND NOT(s)AND k)OR 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 a
10、lgebra,dont say“times”or“plus”lproduct and sum are OK and commonly used2.511 1112Boolean AlgebraBoolean AlgebraBoolean algebra precedence,highest precedence first.Symbol Name Description ()Parentheses Evaluate expressions nested in parentheses first NOT Evaluate from left to right *AND Evaluate from
11、 left to right +OR Evaluate from left to right 2.5121213Boolean Algebra TerminologyBoolean Algebra TerminologyExample equation:F(a,b,c)=abc+abc+ab+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
12、 c131314Boolean Algebra TerminologyBoolean Algebra TerminologyProduct termProduct of literalsFour product terms:abc,abc,ab,cSum-of-productsEquation written as OR of product terms onlyAbove equation is in sum-of-products form.“F=(a+b)c+d”is not.1414Combinational logic The output is determined only by
13、 its input.Output can be changed when input changed.151516Representations of Boolean FunctionsRepresentations of Boolean Functions2.6aFCircuit 2(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)a0011b0101F1100abFC
14、ircuit 1(c)The function FTruth tableEquation 2:F(a,b)=a Equation 1:F(a,b)=a b +a b161617Representations of Boolean FunctionsRepresentations of Boolean FunctionsA function can be represented in different waysAbove shows seven representations of the same functions F(a,b),using four different methods:E
15、nglish Equation Circuit and Truth Table2.6a1717Representations of logic functionsTruth tableTiming diagramLogic equationsLogic circuits1818Truth tableLeft:the input combinations in binary order Right:the output for the input1919Logic design:Construct a Truth table A device with majority judge functi
16、on output the majority input state.2020 Full adder add three input numbers to get their sum.Logic design:Construct a Truth table2121 4-bits prime-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 table2222 4-bit Binary to Gray cod
17、e converter change binary input to Gray code output.Logic design:Construct a Truth table232324Converting among RepresentationsConverting among RepresentationsCan convert from any representation to anotherCommon conversionsEquation to circuit Circuit to equationStart at inputs,write expression of eac
18、h gate outputcchF=c(h+p)ph+pCircuitsEquationsTruth table341265242425Converting among RepresentationsConverting among RepresentationsMore common conversionsTruth table to equation(which we can then convert to circuit)Easyjust OR each input term that should output 1Equation to truth tableEasyjust eval
19、uate equation for each input combination(row)Creating intermediate columns helpsaCircuitsEquationsTruth table341265252526Example:Converting from Circuit to Example:Converting from Circuit to Truth TableTruth TableFirst convert to circuit to equation,then equation to tableFacbabc(ab)(ab)ca00001111c01
20、010101b00110011F10101000ab00000011(ab)11111100c10101010InputsOutputs262627Standard Representation:Truth TableStandard Representation:Truth TableHow 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
21、equal?No.Solution:Convert to truth tables Only ONE truth table representation of a given functionStandard representationfor given function,only one version in standard form exists272728Standard 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
22、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 b+a b+ab,by converting each to truth table firstSame2828Logic Expression to Truth TableLogic Expression to Truth Table(逻辑表达式逻辑表达式 真值表真值表)Y=(B+C)(A+B+C)0 0
23、 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 Design and Application(数字逻辑设计及应用数字逻辑设计及应用)2929Truth Table to Logic Expression Truth Table to Logic Expression(真值表真值表 逻辑表达式逻辑表达式)ABC0 0 0 00 0 1 00 1 0 00 1 1 11
24、 0 0 01 0 1 11 1 0 11 1 1 0A B CF真真值值表表ABCABCF=ABC+ABC+ABC0 0 反变量反变量1 1 原变量原变量乘积项：乘积项：Sum-of-Products “积之和积之和”表达式表达式“与与-或或”式式Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3030Truth Table to Logic ExpressionTruth Table to Logic Expression(真值表真值表 逻辑表达式逻辑表达式)11101111G0 0 0 00 0 1 00 1 0 00 1
25、1 11 0 0 01 0 1 01 1 0 01 1 1 0A B CF真真值值表表(ABC)=A+B+CF=ABCG=(A+B+C)0 0 原变量原变量1 1 反变量反变量Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3131Truth Table to Logic ExpressionTruth Table to Logic Expression(真值表真值表 逻辑表达式逻辑表达式)0 0 0 10 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1A B CF真真值值表表A+B
26、+CA+B+CF=(A+B+C)(A+B+C)0 0 原变量原变量1 1 反变量反变量求和项求和项“和之积和之积”表达式表达式“或或-与与”式式Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)32324.1.6 Standard Representations of Logic 4.1.6 Standard Representations of Logic Functions(Functions(逻辑函数的标准表示法逻辑函数的标准表示法)Minterms(最小项最小项)An n-variable Minterm is a norm
27、al product term with n literals(n个因子的标准乘积项个因子的标准乘积项)There are 2n such product terms (n变量函数具有变量函数具有2n个最小项个最小项)Any two different product terms produce 0.(任意两个不同最小项的乘积为任意两个不同最小项的乘积为0)ABCABCABCABCABCABCABCABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1A B CProduct Term(乘积项乘积项)3333Properties of mintermFor an
28、y input combinations,there is one and only one minterm will be 1;The sum of all the minterm must be 1;The product of any two different minterm must be 0.3434Maxterms(最大项最大项)An n-variable maxterm is a normal sum term with n literals.(n变量最大项是具有变量最大项是具有n个因子的标准求和项个因子的标准求和项)There are 2n such sum terms.(n
29、变量函数具有变量函数具有2n个最大项个最大项)Product of all maxterms is 0.(全体最大项之积为全体最大项之积为0)Any two different sum terms produce 1.(任意两个最大项的和为任意两个最大项的和为1)A+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1A B CSum Term(求和项求和项)4.1.6 Standard Representations of Logic 4.1.6 Standard Representati
30、ons of Logic Functions(Functions(逻辑函数的标准表示法逻辑函数的标准表示法)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3535Properties of maxtermFor any input combinations,there is one and only one maxterm will be 0;The product of all the maxterm must be 0;The sum of any two different maxterm must be 1.3636Pr
31、operties of maxtermFor any input combinations,there is one and only one maxterm will be 0;The product of all the maxterm must be 0;The sum of any two different maxterm must be 1.3737ABCABCABCABCABCABCABCABCm0m1m2m3m4m5m6m7Minterms(最小项最小项)0 0 0 00 0 1 10 1 0 20 1 1 31 0 0 41 0 1 51 1 0 61 1 1 7AB C编号
32、编号A+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CM0M1M2M3M4M5M6M7Maxterms(最大项最大项)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3838Relationship of Relationship of MaxtermsMaxterms and and MintermsMinterms(最大项与最小项之间的关系最大项与最小项之间的关系)11101001G0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0A
33、B CF(ABC)=A+B+C(ABC)=A+B+C(ABC)=A+B+CMi=mi)6,5,3(,CBAF )7,4,2,1,0(,CBAF mi=Mi)6,5,3(,FGCBA 标号互补标号互补Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)3939、Mi=mi ；mi=Mi ；、一个、一个n n变量函数，既可用变量函数，既可用最小项之和最小项之和表示，表示，也可用也可用最大项之积最大项之积表示。两者下标互补。表示。两者下标互补。、某逻辑函数、某逻辑函数 F，若用若用 P项最小项之和表示，项最小项之和表示，则其反函数则其反函数
34、 F 可用可用 P 项最大项之积表示，项最大项之积表示，两者标号完全一致。两者标号完全一致。Relationship of Relationship of MaxtermsMaxterms and and MintermsMinterms(最大项与最小项之间的关系最大项与最小项之间的关系)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)4040Truth Table(真值表真值表)Product Term,Sum Term(乘积项、求和项乘积项、求和项)Sum-of-Products Expression(“积之和积之和”表达式表
35、达式)Product-of-Sum Expression(“和之积和之积”表达式表达式)Canonical Sum and Product(标准和与标准积标准和与标准积)N-variable Minterm(n 变量最小项变量最小项)N-variable Maxterm(n 变量最大项变量最大项)(4.1.6)最小项之和最小项之和 最大项之积最大项之积标准和标准和标准积标准积4.1.6 Standard Representations of Logic 4.1.6 Standard Representations of Logic Functions(Functions(逻辑函数的标准表示法逻
36、辑函数的标准表示法)Normal Term(标准项）标准项）Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)41410 0 0 00 0 1 00 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1A B CF课堂练习：分别写出下面逻辑函数的课堂练习：分别写出下面逻辑函数的 Canonical Sum (标准和标准和)Canonical Product (标准积标准积)的表示。的表示。)7,4,2(,CBAF )6,5,3,1,0(,CBA On-Set(开集开集)Off-Set(闭集闭集)Digit
37、al Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)4242用标准和用标准和(Canonical Sum)的形式表示函数：的形式表示函数：F(A,B,C)=AB+AC利用基本公式利用基本公式 A+A=1F(A,B,C)=AB+AC =AB(C+C)+AC(B+B)=ABC+ABC+ABC+ABC1 1 11 1 00 1 10 0 1=A,B,C(1,3,6,7)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)4343G(A,B,C)=(A+B)(A+C)=(A+B+CC)(A+C
38、+BB)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)0 0 00 0 11 0 01 1 0=A,B,C(0,1,4,6)Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)用标准积用标准积(Canonical Product)的形式表示函数的形式表示函数：4444Standard logic equationMinterm list(Canonical sum):list of“1”ZYXZYXZYXmmmZYXFXYZ7,6,1,7614545Maxterm list(Canonical product):list
39、of“0”543205,4,3,2,0,MMMMMZYXFXYZStandard logic equation4646Any logic can be realized in two level circuit:Minterm list,Canonical sum,sum of product;Maxterm list,Canonical product,product of sum;xyzxyzzyxmmmXYZ7617,6,1zyxzyxMMXYZ424,2Standard logic equation4747Any logic can be realized in two level c
40、ircuit:XYZXYZZYXF5,4,3,2,07,6,1,XYZXYZZYXF7,6,15,4,3,2,0,Standard logic equation4848From logic equation to logic circuit131175321mmmmmmmF4949Example that Applies Boolean Algebra Example that Applies Boolean Algebra PropertiesPropertiesWant automatic door opener circuit(e.g.,for grocery store)Output:
41、f=1 opens doorInputs:p=1:person detectedh=1:switch forcing hold openc=1:key forcing closedWant open door whenh=1 and c=0,orh=0 and p=1 and c=0Equation:f=hc+hpcfhcpDoorOpener505051Example that Applies Boolean Algebra Example that Applies Boolean Algebra PropertiesPropertiesCan the circuit be simplifi
42、ed?f=hc+hpcf=ch+chp (by the commutative property)f=c(h+hp)(by the first distrib.property)f=c(h+h)*(h+p)(2nd distrib.prop.;tricky one)f=c(1)*(h+p)(by the complement property)f=c(h+p)(by the identity property)Simplified circuitaaDoorOpenerchfp5151How to make a circuit better?xyzzxyzyxFXYZ7,5,1xyzzyxyz
43、zxyzyxFzxyzxyyF52524.2 4.2 Combinational-Circuit AnalysisCombinational-Circuit Analysis(组合电路分析组合电路分析)给出组合电路的逻辑图，分析电路的功能给出组合电路的逻辑图，分析电路的功能 通过获得逻辑函数的形式来分析通过获得逻辑函数的形式来分析ABFAB(AB)(AB)F=(AB)(AB)=AB+AB=ABDigital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)5353第第4 4章作业章作业（P230P230）Digital Logic Design
44、and Application(数字逻辑设计及应用数字逻辑设计及应用)4.9 (a)(b)4.10(c)(f)4.12 5454A Class Problem (A Class Problem (每课一题每课一题 )Corresponding the right Truth Table，write the Canonical Sum（标准和）（标准和）and Canonical Product（标准积）。（标准积）。Digital Logic Design and Application(数字逻辑设计及应用数字逻辑设计及应用)0 0 0 10 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 0 1 1 1 1A B CF真真值值表表5555
