数字电路英文版第四单元.pptx

《数字电路英文版第四单元.pptx》由会员分享，可在线阅读，更多相关《数字电路英文版第四单元.pptx（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 CHAPTER 4 Adjacency (相邻)Karnaugh map (卡诺图)Associative law (结合律)Cell (单元)Boolean expression(布尔表达式)Commutative law(交换律)Distributive law (分配律)Domain (定义域)“Dont care“(无关项)Literal (变量)Product-of-sums(POS)(和项之积)Product term (积项)Sum-of-products(SOP)(积项之和)Sum term (和项)Variable (变量)第1页/共135页KEY TERMSAdjacen

2、cy Characteristic of cells in a Karnaugh map in which there is a single-variable change from one cell to another cell next to it on any of its four sides.Associative law In addition(ORing)and multiplication(ANDing)of three or more variables,the order in which the variables are grouped makes no diffe

3、nce.第2页/共135页Boolean expression An arrangement of variables and logical operators used to express the operation of a logic circuit.Cell An area on a Karnaugh map that represents a unique combination of variables in product form.第3页/共135页Commutative law In addition(ORing)and multiplication(ANDing)of

4、two variables,the order in which the variables are ORed orANDed makes no diffence.Domain All of the variables in a Boolean expression.第4页/共135页Distributive law ORing several variables and then ANDing the result with a single variable is equivalent to ANDing the single variable with each of the sever

5、al variables and then ORing the products.“Dont care”A combination of input literals that cannot occur and can be used as a 1 or a 0 on a Karnaugh map.第5页/共135页Literal A variable or the complement of a variable.Product-of-sums(POS)A form of Boolean expression that is basically the ANDing of ORed term

6、s.Product term The Boolean product of two or more literals equivalent to an AND operation.第6页/共135页Sums-of-products(SOP)A form of Boolean expression that is basically the ORing of ANDed terms.Sum term The Boolean sum of two or more literals equivalent to an OR operation.Variable A symbol used to rep

7、resent a logical quantity that can have a value of 1 or 0,usually designated by an italic letter.第7页/共135页 Boolean algebra is the mathematics of digital systems.A basic knowledge of Boolean algebra is indispensable to the study and analysis of logical circuits.In the last chapter,Boolean operations

8、and expressions in terms of their relationship to NOT,AND,OR,NAND,and NOR gates were introduced.This section reviews that material and provides additional definitions and information.4.1 BOOLEAN OPERATIONS AND 4.1 BOOLEAN OPERATIONS AND EXPRESSIONS EXPRESSIONS 2.第8页/共135页A variable is a symbol used

9、to represent a logical quantity.The complement is the inverse of a variable.A literal is a variable or the complement of a variable.If A=1,then A=0.If A=1,then A=0.第9页/共135页Boolean Addition is equivalent to the OR operation.0+0=0,0+1=1,1+0=1,1+1=13.Some example:A+B,A+B,A+B+C,and A+B+C+D.第10页/共135页EX

10、AMPLE 41 Determine the values of A,B,C,and D which make the sum term A+B+C+D equal to 0.Solution:if A=0,B=1 so that B=0,C=0,D=1 so that D=0.A+B+C+D=0+1+0+1 =0+0+0+0=0Related Problem Determine the values of A and B which make the sum term A+B equal to 0.第11页/共135页Boolean Multiplication is equivalent

11、to the AND operation.0*0=0,0*1=0,1*0=0,1*1=1Some example:A*B,A*B,A*B*C,and A*B*C*D.第12页/共135页EXAMPLE 42 Determine the values of A,B,C,and D which make the product term A*B*C*D equal to 1.Solution:if A=1,B=0 so that B=1,C=1,D=0 so that D=1.A*B*C*D=1*0*1*0 =1*1*1*1=1Related Problem Determine the value

12、s of A and B which make the product term A*B equal to 1.第13页/共135页As in other areas of mathematics,there are certain well-developed rules and laws that must be followed in order to properly apply Boolean algebra.The most important of these are presented in this section.4.2 LAWS AND RULES OF 4.2 LAWS

13、 AND RULES OF BOOLEAN ALGEBRA BOOLEAN ALGEBRA 4.第14页/共135页Laws of Boolean Algebra1.Commutative Laws This law states that the order in which the variables are ORed makes no difference.Logical Addition A+B=B+AABA+BBAB+A5.第15页/共135页Logical MultiplicationThis law states that the order in which the varia

14、bles are ANDed makes no difference.A*B=B*AABA*BBAB*A6.第16页/共135页2.Associative Laws This law states that when ORing more than two variables,the result is the same regardless of the grouping of the variables.A+(B+C )=(A+B)+CABABCCB+CA+B(A+B)+CA+(B+C)7.第17页/共135页A(B C )=(A B)CABCB CA BA(B C)ABC(A B)C8.

15、This law states that it makes no difference in what order the variables are grouped when ANDing more than two variables.第18页/共135页3.Distributive Law This law states that ORing two or more variables and then ANDing the result with a single variable is equivalent to ANDing the single variable with eac

16、h of the two or more variables and then ORing the products.A(B+C )=A B+A C9.第19页/共135页BCAB+CXABACABXACX=A(B+C)X=A B+A C10.第20页/共135页Rules of Boolean Algebra1.A+0=A2.A+1=13.A*0=04.A*1=A5.A+A=A6.A+A=17.A*A =A8.A*A=09.A=A10.A+AB=A 11.A+A B=A+B12.(A+B)(A+C)=A+BC11.第21页/共135页11.A+AB=A+B This rule can be

17、proved as follows:A+AB=(A+AB)+AB rule 10:A=A+AB =(AA+AB)+AB rule 7:A=AA =AA+AB+AA+AB rule 8:AA=0 =(A+A)(A+B)factoring =1*(A+B)rule 6:A+A=1 =A+B rule 4:drop the 112.第22页/共135页A B AB A+AB A+B 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 equalAABB13.A+AB =A+B第23页/共135页12.(A+B)(A+C)=A+BC This rule can be pro

18、ved as follows:(A+B)(A+C)=AA+AC+AB+BC distributive =A+AC+AB+BC AA=A =A(1+C)+AB+BC factoring =A*1+AB+BC 1+C=1 =A(1+B)+BC factoring =A*1+BC 1+B=1 =A+BC A*1=A14.第24页/共135页A B C A+B A+C (A+B)(A+C)BC A+BC 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1

19、0 1 1 1 0 1 1 1 1 1 1 1 1 1 equal15.第25页/共135页ABCABC16.(A+B)(A+C)=A+BC第26页/共135页Another formula:AB+AC+BC=AB+ACAB+AC+BC=AB+AC+(A+A)BC A+A=1 =AB+AC+ABC+ABC Distributive =AB(1+C)+AC(1+B)factoring =AB+AC 1+C=1,1+B=1,How about:AB+AC+BCD=?第27页/共135页DeMorgan,a mathematician who know Boole,proposed two theo

20、rems that are an important part of Boolean algebra.In practical terms,DeMorgans theorems provide mathematical verification of the equivalency of the NAND and negative-OR gates and the equivalency of the NOR and negative-AND gates,which were discussed in Chapter 3.4.3 DEMORGANS THEOREMS 4.3 DEMORGANS

21、 THEOREMS 17.第28页/共135页DeMorgans First theoremThe complement of a product of variables is equal to the sum of the complements of the variables.XY=X+Y18.第29页/共135页The complement of a sum of variables is equal to the product of the complements of the variables.X+Y=X Y19.第30页/共135页 NAND Negative-OR Inp

22、ut OutputX Y XY X+Y 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0XYXYX YXY+20.第31页/共135页 NOR Negative-AND Input OutputX Y X+Y XY 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0XYXYX+YX Y21.第32页/共135页Applying DeMorgans TheoremsA+BC +D(E+F)=A+BCD(E+F)=A+BCD(E+F)=A+BCD+(E+F)=(A+BC)(D+E+F)22.第33页/共135页The Duality Theorema.First,chan

23、ge each OR symbol to an AND symbol and each AND symbol to an OR symbol.b.Second,change each 0 to a 1 and 1 to a 0 Example:Original Rule A+1=1 Dual Rule A*0=0 Original Equation:A*(B+C)=(A*B)+(A*C)Dual Equation:A+(B*C)=(A+B)(A+C)23.第34页/共135页1.Commutative Law A+B=B+A AB=BA2.Associative Law A(BC)=(AB)C

24、 A+(B+C)=A+B+C3.Distributive Law A+(BC)=(A+B)(A+C)A(B+C)=AB+AC4.OR-AND Rules A+0=A A*1=A A+A=A A*A=A A+1=1 A*0=0 A+A=1 A*A=05.DeMorgans Laws A*B=A+B A+B=A*B ORIGINAL EQUATION DUAL EQUATION24.第35页/共135页Boolean algebra provides a concise way to express the operation of a logic circuit formed by a comb

25、ination of logic gates so that the output can be determined for various combinations of input values.4.4 BOOLEAN ANALYSIS OF 4.4 BOOLEAN ANALYSIS OF LOGIC CIRCUIT LOGIC CIRCUIT 25.第36页/共135页The Boolean Expression for a logic CircuitDCB+CDA(B+CD)BADC26.第37页/共135页The Truth Table for a Logic Circuit In

26、put A B C D Output A(B+CD)0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 127.第38页/共135页Many times in the application of Boolean algebra,you have to reduce a particular expression to its sim

27、plest form or change its form to a more convenient one to implement the expression most efficiently.4.5 SIMPLIFICATION USING 4.5 SIMPLIFICATION USING BOOLEAN ALGEBRA BOOLEAN ALGEBRA 28.第39页/共135页The approach taken in this section is to use the basic laws,rules,and theorems of Boolean algebra to mani

28、pulate and simplify an expression.This method depends on a through knowledge of Boolean algebra and considerable practice in its application,not to mention a little ingenuity and cleverness.29.第40页/共135页EXAMPLE 48 simplify this expressionAB+A(B+C)+B(B+C)=AB+AB+AC+BB+BC =AB+AC+B+BC =AB+AC+B =B+AC30.第

29、41页/共135页ABCACBB+ACAB+A(B+C)+B(B+C)Equivalent31.第42页/共135页All Boolean expressions,regardless of their form,can be converted into either of two standard forms:the sum-of-products form or the product-of-sums form.Standardization makes the evaluation,simplification,and implementation of Boolean express

30、ions much more systematic and easier.4.6 STANDARD FORMS OF 4.6 STANDARD FORMS OF BOOLEAN EXPRESSIONS BOOLEAN EXPRESSIONS 32.第43页/共135页The Sum-of-Products(SOP)FormAB+ABCABC+CDE+BCDAB+ABC+AC A Boolean expression that describe the ORing of two or more AND function.33.第44页/共135页ABBCDACImplementation of

31、an SOP Expression AB+BCD+ACX=AB+BCD+AC34.第45页/共135页The Standard SOP Form A standard SOP expression is one in which all the variables in the domain appear in each product term in the expression.For example:ABCD+ABCD+ABCD is a standard SOP expression.35.第46页/共135页EXAMPLE 413 Convert the following Bool

32、ean expression into standard SOP form:ABC+AB+ABCD Solution:ABC=ABC(D+D)=ABCD+ABCD AB=AB(C+C)=ABC+A B C =ABC(D+D)+ABC(D+D)=ABCD+ABCD+A B CD+A B C D 36.第47页/共135页The standard SOP form of the original expression is as follows:ABC+AB+ABCD=ABCD+ABCD +ABCD+ABCD+A B CD+A B C D +ABCD Binary Representation o

33、f a Standard Product TermABCD=1*0*1*0=1*1*1*1=137.第48页/共135页The Products-of-Sums(POS)Form(A+B)(A+B+C)(A+B+C)(C+D+E)(B+C+D)(A+B)(A+B+C)(A+C)A Boolean expression that describe the ANDing of two or more OR function.38.第49页/共135页ABBCDACImplementation of an POS Expression (A+B)(B+C+D)(A+C)X=(A+B)(B+C+D)(

34、A+C)39.第50页/共135页The Standard POS Form A standard POS expression is one in which all the variables in the domain appear in each sum term in the expression.For example:(A+B+C+D)(A+B+C+D)(A+B+C+D)is a standard POS expression.40.第51页/共135页EXAMPLE 415 Convert the following Boolean expression into standa

35、rd POS form:(A+B+C)(B+C+D)(A+B+C+D)Solution:A+B+C=A+B+C+DD (rule 12)=(A+B+C+D)(A+B+C+D)B+C+D=B+C+D+AA =(A+B+C+D)(A+B+C+D)41.第52页/共135页The standard POS form of the original expression is as follows:Binary Representation of a Standard Sum TermA+B+C+D=0+1+0+1=0+0+0+0=0(A+B+C)(B+C+D)(A+B+C+D)=(A+B+C+D)(

36、A+B+C+D)+(A+B+C+D)(A+B+C+D)+(A+B+C+D)42.第53页/共135页A POS expression is equal to 0 only if one or more of the terms in the expression is equal to 0.EXAMPLE 416 Determine the binary values of the variables for which the following standard POS expression is equal to 0:(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D

37、)=0+0+0+0=0 (A+B+C+D)=0+1+1+0=0+0+0+0=0 (A+B+C+D)=1+1+1+1=0+0+0+0=0 The POS expression is equals 0 when any of the three sum terms equals 0.43.第54页/共135页Converting Standard SOP to Standard POSEXAMPLE 417 Convert the following SOP expression to an equivalent POS expression:ABC+ABC+ABC +ABC+ABC Soluti

38、on The evaluation is as follows:000+010+011+101+111 The equivalent POS expression is (A+B+C)(A+B+C)(A+B+C)001,100,11044.第55页/共135页All standard Boolean expressions can be easily converted into truth table format using binary values for each term in the expression.The truth table is a common way of pr

39、esenting,in a concise format,the logical operation of a circuit.4.7 BOOLEAN EXPRESSION 4.7 BOOLEAN EXPRESSION AND TRUTH TABLES AND TRUTH TABLES 45.第56页/共135页 Also,standard SOP or POS expressions can be determined form a truth table.You will find truth tables in data sheets and other literature relat

40、ed to the operation of digital circuits.Converting SOP Expressions to Truth table Format46.第57页/共135页EXAMPLE 418 Develop a truth table for the standard SOP expression ABC+ABC+ABC Input OutputA B C X 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 147.第58页/共135页Converting POS Expression

41、s to Truth table Format Input OutputA B C X 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1EXAMPLE 419 Determine a truth table for the standard POS expression (A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C)48第59页/共135页The K-map provides a systematic method for simplifying Boolean expressions and

42、,if properly used,will produce the simplest SOP or POS expression possible.4.8 THE KARNAUGH MAP 4.8 THE KARNAUGH MAP 49.第60页/共135页As you have seen,the effectiveness of algebraic simplification depends on your familiarity with all the laws,rules,and theorems of Boolean algebra and on your ability to

43、apply them.The K-map,on the other hand,basically provides a“cookbook”method for simplification.50.第61页/共135页ABCABCABCABCABCABCABCABC ABC000111100 1ABCABCABCABCABCABCABCABCABC0001111001The 3-Variable K-map012367450123456751.第62页/共135页The 4-Variable K-mapABCDABCDABCD ABCDABCDABCDABCDABCD0001111000 01A

44、BCDABCD ABCDABCDABCDABCDABCDABCD 11 10 AB CD012345678910111213141552.第63页/共135页 4.9 K-MAP SOP MINIMIZATION 4.9 K-MAP SOP MINIMIZATION As stated in the last section,the K-map is used for simplifying Boolean expressions to their minimum form.A minimized SOP expression contains the fewest possible term

45、s with the fewest possible variables per term.53.第64页/共135页Generally,a minimum SOP expression can be implemented with fewer logic gates than a standard expression and this is the basic purpose in the simplification process.54.第65页/共135页C000111100 1 1 1 1 1ABC+ABC+ABC+ABC 000 001 110 100 AB+AC ABMapp

46、ing a Standard SOP Expression55.第66页/共135页EXAMPLE 421 Map the following standard SOP expression on a Kmap:ABC+ABC+ABC+ABC 001 010 110 111C000111100 1 1 1 1 1 ABAB+BC+ABC56.第67页/共135页EXAMPLE 422 Map the following standard SOP expression on a Kmap:ABCD+ABC D+ABCD+ABCD+ABCD+ABC D+ABCD 0011 0100 1101 11

47、11 1100 0001 1010111111100011110AB00011110CD3141210151357.第68页/共135页Mapping a Nonstandard SOP ExpressionEXAMPLE 423 Map the following SOP expression on a K-map:A+AB +ABC 000 100 110 001 101 010 011 C000111100 1 1 1 1 1 AB 1 1 158.第69页/共135页EXAMPLE 424 Map the following SOP expression on a K-map:BC+A

48、B+ABC+ABCD+ABCD+ABCD0000 1000 1100 1010 0001 10110001 1001 11011000 10101001 1011111111110000010110101111ABCD59.第70页/共135页K-map Simplification of SOP ExpressionsGrouping the 1s1.A group must contain either 1,2,4,8,or 16 cells.2.Each cell in a group must be adjacent to one or more cells in that same

49、group.3.Always include the largest possible number of 1s in a group in accordance with rule 1.4.Each 1 on the map must be included in at least one group.60.第71页/共135页EXAMPLE 4-25(27)1111111111ABABCC00000101111110100011ABCBCABACACB61.第72页/共135页1111111111111111111ABABCDCD000000000101010111111111101010

50、10Wrap-around adjacencyACABABDDBCABC62.第73页/共135页Mapping Directly from a Truth Table Input OutputA B C X 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 11111ABC0001111001 1 1 0 1X=AB+BC?63.第74页/共135页“Dont Care”Conditions Input OutputA B C D Y0 0 0 0 00 0 0 1 00 0 1 0 00 0 1 1 00 1 0 0 00 1 0