《電子技術(shù)數(shù)字基礎(chǔ) Digital Fundamentals》雙語課件PPT-第04章 Boolean Algebra and Logic Simplification

1、14Boolean Algebra and Logic Simplification2Contentsw Boolean Operations and Expressionsw Law and Rules of Boolean Algebraw DeMorgans Theoremsw Boolean Analysis of Logic Circuitsw Simplification Using Boolean Algebraw Standard Forms of Boolean Expressionsw Boolean Expressions and Truth Tablesw The Ka

2、rnaugh Mapw Karnaugh Map SOP Minimization34-1 Boolean Operations and Expressionsw Boolean algebra (布爾代數(shù)） is the mathematics of digital systems.w Sum term （和的形式）: is a sum of literals (文字) ( a variable or the complement of a variable), produced by an OR gate.w A sum term is equal to 1 when one or mor

3、e of the literals in the term are 1.w A sum term is equal to 0 only if each of the literals is 0.DCBAXBAXBAX,44-1 Boolean Operations and Expressionsw Product term （積的形式）: is the product of literals, produced by an AND gate.DCAXBAXABX,w A product term is equal to 1 only if each of the literals in the

4、 term is 1. A product term is equal to 0 when one or more of the literals are 0.1010DCAXw Ex. Only if A=0,C=1, and D=0, then X=1.54-1 Boolean Operations and ExpressionsFA B C0 0 0 00 1 0 01 0 0 01 1 0 00 0 1 00 1 1 11 0 1 11 1 1 1ABCCBABCAF64-2 Laws and Rules of Boolean Algebra4-2-1 Laws of Boolean

5、Algebra (布爾代數(shù)常用公式）w Commutative laws (交換律）for addition and multiplication A+B=B+A; AB=BAw Associative laws (結(jié)合律） A+(B+C)=(A+B)+C A(BC)=(AB)Cw Distributive Law (分配律） A(B+C)=AB+AC74-2-2 Rules of Boolean Algebra (基本公式）1. A+0= A variable ORed with 0 is always equal to the variable.2. A+1= A variable ORe

6、d with 1 is always equal to 1.3. A0= A variable ANDed with 0 is always equal to 0.4. A1= A variable ANDed with 1 is always equal to the variable.A10A84-2-2 Rules of Boolean Algebra5. A+A= A variable ORed with itself is always equal to the variable.6. AA= A variable ANDed with itself is always equal

7、to the variable.AA94-2-2 Rules of Boolean Algebra7. A variable ORed with its complement is always equal to 1.AA8. A variable ANDed with its complement is always equal to 0.A A10104-2-2 Rules of Boolean Algebra9. The double complement of a variable is always equal to the variable.A10. A+AB=AA114-2-2

8、Rules of Boolean Algebra11. (A+B)(A+C)=A+BCBABAA.12BABAAABAA)(124-2-2 Rules of Boolean AlgebraBCABBCCAAB.13CAABBCACAABCABBCAACAABBCCAAB)(134-3 Basic Theorems1. Replacement theorem (代入定理）Any variable in laws or rules of Boolean expressions can also be replaced with a combination of other variables or

9、 combinations.ABBAACDECDEBBCDE144-3 Basic Theorems2. Demorgans theorem （摩爾定理） ， ， ， , ,For a given expression X, if then (反函數(shù)反函數(shù))got. X XXProcedure: Step 1: Replace OR with AND, AND with OR;Step 2: Complement each literal.DBDCACBAX)( )()(DBDCACBAX154-3 Basic TheoremsYXXYYXYXThe complement of two or

10、more variables ANDed is equal to the OR of the complements of the individual variables.164-3 Basic Theorems3. Duality theorem （對(duì)偶定理）If X=Y, then X=Y X primeThe dualistic expression of X ， ， ， XX then X (對(duì)偶式對(duì)偶式) gotFor a given expression X, if 174-4 Boolean Analysis of Logic Circuits（邏輯電路分析）1. Logic

11、Circuit (邏輯電路圖）2. Boolean Expression （布爾表達(dá)式）)(CDBACDCDBX=A(B+CD)184-4 Boolean Analysis of Logic Circuits4-7 Boolean Expressions and Truth Table3. Truth Table （真值表）wConstructing the truth table from a logic expression. (1) Determine the number of the input and output variables, and the number of the

12、input variable possible combinations.(2) Draw the truth table frame according to the input and output variables194-4 Boolean Analysis of Logic Circuits(3) List all of the input variable combinations of 1s and 0s in a binary sequence (按序）.(4) Fill the truth table. If the input variable combinations m

13、ake the output 1, then place a 1 in the corresponding output column, otherwise place a 0.204-4 Boolean Analysis of Logic CircuitsEx. X=A(B+CD)214-4 Boolean Analysis of Logic Circuits 4-7 Boolean Expressions and Truth Table wDetermining logic expressions from a truth table(1) List the binary values o

14、f the input variables for which the output is 1.(2) Convert each binary value to the corresponding product term by replacing each 1 with the corresponding variable and each 0 with the complement.(3) Get the logic expression by summing all the combinations.224-7 Boolean Expressions and Truth TableA B

15、 CF0 0 0 00 1 0 01 0 0 01 1 0 00 0 1 00 1 1 11 0 1 11 1 1 1 List the binary values where the outputs are “1” Convert each binary value to the corresponding product summing all the combinations.Ex. Truth TableABCCBABCAF234-4 Boolean Analysis of Logic Circuits4. The Karnaugh Map （卡諾圖） The Karnaugh map

16、 is similar to a truth table, it can make the simplification procedure of Boolean expression easy.244-6 Standard Forms of Boolean Expressions1. The SOP Form: (Sum-of-Products) (與或式） The expression is a sum of two or more products of literals.EDCBADCBCBAABCAB()A CB254-6 Standard Forms of Boolean Expr

17、essions2. The Standard SOP Form (標(biāo)準(zhǔn)與或式） (最小項(xiàng)和式） is one in which all the variables in the domain appear in each product term in the expression. is a standard SOP form, isnt a standard SOP formABCDABCDABCDand ABCDBCDA14m as marked isit and 14), (decimal 1110 of uebinary val a has D case, In this 0;D1,

18、C1,B1,A when 1 toequal is DABCABC264-6 Standard Forms of Boolean ExpressionsAny nonstandard (非標(biāo)準(zhǔn)的，也即不是最小項(xiàng)) SOP expression can be converted to the standard form using the equation1 AA274-6 Standard Forms of Boolean Expressions Procedure of converting a SOP to a standard SOP form:wMultiply each nonsta

19、ndard product term by a term made up of the sum of a missing variable and its complement (缺的變量及其反變量).wGet the standard SOP form by using the distributive rules.284-6 Standard Forms of Boolean ExpressionsEx.DCABDBCBAFLack of variables C and D and their complementsLack of variable A and its complement

20、DCABDBCAADDCCBA)()(Expand it using distributive law A(B+C)=AB+AC DCABDBCADABCCDBADCBADCBADCBA)13, 6 ,14,11,10, 9 , 8(m294-6 Standard Forms of Boolean Expressions3. The POS (Product-of-Sums) form (或與式） The expression is a product of two or more sums of literals.)()(DCACBACBABA304-5 Simplification Usi

21、ng Boolean Algebra(用公式法化簡(jiǎn)）用公式法化簡(jiǎn)）w When you design a circuit by a Boolean expression, you have to reduce the expression to the simplest form (for a SOP term, the fewest sums and the fewest variables per sum) to make the circuit simple and easy to be implemented.Boolean AlgebraMapSimplification metho

22、d314-5 Simplification Using Boolean Algebraw The approach is to use the basic laws, rules and theorems of Boolean algebra to process and simplify an expression. w This method depends on a thorough knowledge of Boolean algebra and considerable practice in its application.324-5 Simplification Using Bo

23、olean AlgebraEx. Y=ABC+ABD+ABC+CD+BD Y=ABC+ABC+CD+B(AD+D)= ABC+ABC+CD+B(A+D)= ABC+ABC+CD+BA+BD=AB +ABC+CD+BD=B(A+AC)+CD+BD=B(A+C)+CD+BD=BA+BC+CD+BD=BA+B(C+D)+CD=BA+BCD+CD=BA+B+CD=B(A+1)+CD=B+CD334-5 Simplification Using Boolean AlgebraAs you have seen, the effectiveness of algebraic simplification d

24、epends on your familiarity with all the laws, rules, and theorems of Boolean algebra and on your ability to apply them.344-8 The Karnaugh Map K Map （卡諾圖）A K-map is similar to a truth table because it presents all of the possible values of input variables and the resulting output for each combination

25、. Instead of being organized into columns and rows like a truth table, the K-map is an array of CELLS (單元) in which each cell represents a minterm of the input variables. 354-8 The Karnaugh Map K-MapThe cells are arranged in a way so that simplification of a given expression is simply a matter of pr

26、operly grouping the cells (對(duì)單元分組，圈圈). The number of cells (2n) in a K-map is equal to the total number of possible input variable (n) combinations. K-map can be used for expressions with 2,3,4 and 5 variables, but only K-map of 3-variable and 4-variable are often used.364-8 The Karnaugh Map - 3-Vari

27、able K-MapABC00 01 11 100 10 1 3 24 5 7 6ABC ABC ABC ABCABC ABC ABC ABCNotice the sequence11 and 10 exchange position The value of a given cell is the decimal digit of A at the left in the same row combined with B and C at the top in the same column.The standard product term374-8 The Karnaugh Map -

28、4-Variable K-Map0 1 3 24 5 7 612 13 15 148 9 11 10ABCD00 01 11 1000 01 11 10ABCD ABCD ABCD ABCDABCD ABCD ABCD ABCDABCD ABCD ABCD ABCDABCD ABCD ABCD ABCDw The 4-variable K-map is an array of sixteen cells. Binary values of A and B are along the left side and C and D are across the top.384-8 The Karna

29、ugh Map Cell Adjacency (邏輯相鄰性)w The cells in a K-map are arranged so that there is only a single-variable change ( adjacency 相鄰) between adjacent cells (相鄰單元). w Cell adjacency: cells that differ by only one variable are adjacent. Ex. 010 and 011 are cell adjacency, but 010 and 001 are not.394-8 The

30、 Karnaugh Map Cell Adjacencyw In a K-map, physically, each cell is adjacent to the cells that are immediately next to it on any of its four sides, but not adjacent to its corner cells （四邊相鄰，但對(duì)角不相鄰).404-8 The Karnaugh Map Cell Adjacencyw Wrap-around: in a K-map, the cell is adjacent to its four sides

31、. Also the cells in the top row are adjacent to the corresponding cells in the bottom row (最上一行與最下一行也邏輯相鄰), the cells in the outer left column are adjacent to the corresponding cells in the outer right column (最左行與最右行也邏輯相鄰) .414-9 K-map SOP Minimization (用卡諾圖化簡(jiǎn))1. Mapping a Standard SOP Expression F

32、or an SOP expression in standard form, a 1 is placed on the K-map for each product term in the expression. A 0 is placed for the cells that arent included in the expression. Usually, the 0s are left off the map. (表達(dá)式中含有的最小項(xiàng)在卡諾圖中填入1，不含有的填入0，通常，0會(huì)被省略，而不填入圖中） 424-9 K-map SOP Minimization - ExampleBCCAB

33、XBCAACAB)(BCAABCCAB376mmm376mmmABC00 01 11 100 1Step 2. Draw a 3-variable K-map.Step 1. Convert the expression into a standard SOP.434-9 K-map SOP Minimization - ExampleStep 3. Map the expression (用卡諾圖表示邏輯表達(dá)式）. A 1 is placed on the K-map for each product term in the expression. 0s are placed in the

34、cells that the expression doesnt have the corresponding minterms.ABC00 01 11 100 10 0 00 0ABC00 01 11 100 1376mmmX444-9 K-map SOP Minimization - Example In fact, it isnt necessary to convert a SOP to the standard form. We can fill the map directly. BCAX Step 1. Draw a 3-variable K-map.Step 2. Fill t

35、he map with the first term.For this term, we know that when A=1, and C=0, the term is 1.ABC00 01 11 100 11111.C andA contain that cells twoin the 1sby drepresente is CAB.contain that cellsfour in the 1sby drepresente is B1454-9 K-map SOP Minimization- Rules of Combining Minterms （合并最小項(xiàng)原則）（1）Accordin

36、g to the characteristic of minterm, When the sum of 2 adjacent minterms(cells) is formed, the different variable can be removed.ABC00 01 11 100 11 11 11 law complement theuse AACBAACBCBACBA )( Y464-9 K-map SOP Minimization- Rules of Combining Minterms（2）When the sum of 4 adjacent CELLS is formed, th

37、e 2 different variables can be removed, and only the same variables are left.ABC00 01 11 100 1 1 1 1 1CACCA Y474-9 K-map SOP Minimization- Rules of Combining MintermsABC00 01 11 100 1 1 1 1 1AY ABCD00 01 11 1000 01 11 101111Y= BD484-9 K-map SOP Minimization- Rules of Combining Minterms（3）When the su

38、m of 8 adjacent CELLS is formed, the 3 different variable can be removed, and only the same variables are left.ABCD00 01 11 1000 01 11 101 11 11 11 11 11 11 11 1CY 494-9 K-map SOP Minimization- Rules of Combining MintermsABCD00 01 11 1000 01 11 10Y=AABCD00 01 11 1000 01 11 101 1 1 11 1 1 1DY 504-9 K

39、-map SOP Minimization- Step 1. If the expression isnt in SOP form, convert it by clearing the round-brackets or by applying Demorgans Theorem.Step 2. Draw the necessary -variable K-map.Step 3. Map the expression.514-9 K-map SOP Minimization- Step 4. Grouping the 1s. ( (圈圈）圈圈）1. A group must contain

40、either 1,2,4,8, or 16 (2n) cells, and it must be rectangular (一定為一個(gè)矩一定為一個(gè)矩形圈）形圈）.ABCD00 01 11 1000 01 11 101 11 1WrongRight524-9 K-map SOP Minimization- 2. Always include the largest possible number of 1s in a group. The larger a group, the simpler the resulting term will be (圈要盡量地大）圈要盡量地大）.3. Each

41、1 on the map must be included in at least one group. The 1s already in a map can be included in another group according to A+A=A（每個(gè)最小項(xiàng)都至少被圈（每個(gè)最小項(xiàng)都至少被圈1次）次）.4. Each group must include at least 1 new cell that isnt included by other groups. Otherwise, the product will be redundant （每個(gè)圈中至少有一個(gè)新項(xiàng)）每個(gè)圈中至少有

42、一個(gè)新項(xiàng)）.534-9 K-map SOP Minimization- Step 5. （寫出每個(gè)圈的表達(dá)式）（寫出每個(gè)圈的表達(dá)式）Determining the product term for each group. Each group of cells containing 1s creates one product term composed of all variables that occur in only one form(either uncomplemented or complemented) within the group. Variables that occu

43、r both uncomplemented and complemented within the group are canceled .Step 6. （將每個(gè)圈的表達(dá)式相加）（將每個(gè)圈的表達(dá)式相加）Summing the resulting product terms.544-9 K-map SOP Minimization- Ex. Y(A,B,C,D) = m(0,2,3,5,6,8,9,10,11, 12,13,14,15)ABCD00 01 11 1000 01 11 101 1 11 1 1 1 1 11 1 1 1ACDBCBDBCD：1.Check whether there is any redundant group（冗余項(xiàng)冗余項(xiàng)）.2.The sum form may be not unique.DCBDBCBDCAY: expression minimum The554-9 K-map SOP Minimization- w Dont Care Conditions (無關(guān)項(xiàng)，約束項(xiàng)）無關(guān)項(xiàng)，約束項(xiàng)） Sometimes a situation arises in which some input variable combina