Microsoft PowerPoint - STU_EC_Ch04.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - STU_EC_Ch04.ppt"

峻危
6 years ago
Views:

1 樹德科技大學資訊工程系 Chapter 4: Boolean Algebra and Logic Simplification Shi-Huang Chen Fall 200 Outline Boolean Operations and Expressions Laws and Rules of Boolean Algebra DeMorgan's Theorems Boolean Analysis of Logic Circuit Simplification using Boolean Algebra Standard forms of Boolean Expression Boolean Expression and Truth Table The Karnaugh Map 2

Each literal must = 0; therefore A =, B = 0 and C =.

2 Boolean Addition The OR gate is a Boolean adder Determine the values of A, B, and C that make the sum term of the expression A + B + C = 0? Each literal must = 0; therefore A =, B = 0 and C =. 3 Boolean Multiplication The AND gate is a Boolean multiplier What are the values of the A, B and C if the product term of A. B. C =? Each literal must = ; therefore A =, B = 0 and C =

rules in Boolean Algebra Boolean Addition is the logical OR function X=A + B Boolean Multiplication is the logical AND

3 Laws and rules of Boolean Algebra In 860 George Boole developed Boolean Algebra that is used in Digital electronics. The Boolean Algebra laws and rules are similar to the Algebra but only or 0 is allowed for the variables Three Laws and 2 rules in Boolean Algebra Boolean Addition is the logical OR function X=A + B Boolean Multiplication is the logical AND function X = AB 5 Law a: Commutative law of addition Commutative law of addition A+B = B+A the order of ORing does not matter. 6 3

7 Law 2a: Associative law of addition Associative law of addition

4 Law b: Commutative law of Multiplication Commutative law of Multiplication AB = BA the order of ANDing does not matter. 7 Law 2a: Associative law of addition Associative law of addition A + (B + C) = (A + B) + C The grouping of ORed variables does not matter 8 4

5 Law 2b: Associative law of multiplication Associative law of multiplication A(BC) = (AB)C The grouping of ANDed variables does not matter 9 Law 3: Distributive Law A(B + C) = AB + AC 0 5

6 Basic rules of Boolean algebra. A + 0 = A 2. A + = 3. A. 0 = 0 4. A. = A 5. A + A = A 6. A + A = 7. A. A = A 8. A. A = 0 = 9. A = A 0. A + AB = A. A + AB = A + B 2. (A + B)(A + C) = A + BC Rule : A+0=A In math if you add 0 you have changed nothing in Boolean Algebra ORing with 0 changes nothing 2 6

7 Rule 2: A+= ORing with must give a since if any input is an OR gate will give a 3 Rule 3: A 0=0 In math if 0 is multiplied with anything you get 0. If you AND anything with 0 you get 0 4 7

8 Rule 4: A =A ANDing anything with will yield the anything 5 Rule 5: A+A = A ORing with itself will give the same result 6 8

9 Rule 6: A+A= Either A or A must be so A + A = 7 Rule 7: A A = A ANDing with itself will give the same result 8 9

10 Rule 8: A A =0 In digital Logic =0 and 0 =, so AA=0 since one of the inputs must be 0. 9 Rule 9: A = A If you not something twice you are back to the beginning 20 0

11 Rule 0: A + AB = A AAA B AB AB = AA 2 Rule : A + AB = A + B A + AB = A + B A A AB BA 22

Theorem The complement of a product of variables is equal to the sum of the complemented variables.

12 Rule 2:(A + B)(A + C) = A + BC (A + B)(A + C) = AA + AC + AB + BC = A + AC + AB + BC = A( + C + B) + BC = A. + BC = A + BC A B A + B A + C = C (A + B)(A + C) A + BC A B BC C 23 DeMorgan s Theorems () DeMorgan s st Theorem The complement of a product of variables is equal to the sum of the complemented variables. AB = A + B Applying DeMorgan s first theorem to gates: A B NAND AB A B Negative-OR A + B Inputs Output A B AB A + B

13 DeMorgan s Theorems (2) DeMorgan s 2 nd Theorem The complement of a sum of variables is equal to the product of the complemented variables. A + B = A. B Applying DeMorgan s second theorem to gates: A B NOR A + B A B Negative-AND AB Inputs Output A B A + B AB Simplification Example Apply DeMorgan s theorem to remove the overbar covering both terms from the expression X = C + D. To apply DeMorgan s theorem to the expression, you can break the overbar covering both terms and change the sign between the terms. This results in = X = C. D. Deleting the double bar gives X = C. D. 26 3

14 Boolean Analysis of Logic Circuits Combinational logic circuits can be analyzed by writing the expression for each gate and combining the expressions according to the rules for Boolean algebra. Apply Boolean algebra to derive the expression for X. Write the expression for each gate: A B C D (A + B ) C (A + B ) X = C (A + B )+ D Applying DeMorgan s theorem and the distribution law: X = C (A B) + D = A B C + D 27 A logic circuit showing the development of the Boolean expression for the output 28 4

15 Example One gate at a time starting with the inputs X= AB+(C+D) X= AB + C+ D 29 Example 2 X = (AB)(CD) X = ABCD 30 5

16 Example 3 (/2) 3 Example 3 (2/2) X = ABCD +A X = A + BCD 32 6

17 Example 4 (/2) 33 Example 4 (2/2) X = (AB+B)BC using distributive law X = ABBC +BBC X = ABC + BBC X = ABC + 0 C X = ABC + O X = ABC 34 7

18 Example 5 (/3) 35 Example 5 (2/3) 36 8

19 Example 5 (3/3) X = (A +AB) +(B(C+D)) X = (A + B) + (B(C + D)) X = (A + B) + (BC + BD) X = A + B + BC + BD X = A + B + C + BD X = A + B + C + BD X = A + B + C + D 37 Example (A + B)(CD) = A + B + CD = A + B + CD 38 9

20 Example 2 AB+AB+AC+BB+BC AB+AC+B+BC (AB+AB=AB, BB = B) AB+AC+B (B+BC = B) B+AC (AB+B = B) 39 Example 3 X = A + B C + CD + B = A + B C CD + B = A + B C (CD + B) = A B C (C +D +B) = A B C C + A B C D +A B B C = A B C D

21 Standard Forms of Boolean Expressions - Implementation of the Sum-of-Product (SOP) expression AB + BCD + AC. 4 Standard Forms of Boolean Expressions -2 Implementation of the Product-of-Sum (POS) expression (A + B)(B + C + D) (A + C). 42 2

22 Boolean Expressions and Truth Tables - SOP Expression: A BC + ABC + ABC 43 Boolean Expressions and Truth Tables -2 POS Expression: ( A + B + C)( A + B + C)( A + B + C) ( A + B + C)( A + B + C) 44 22

23 Boolean Expressions and Truth Tables -3 SOP : X = ABC + ABC + ABC + ABC POS: X = ( A + B + C)( A + B + C)( A + B + C)( A + B + C) 45 Examples of SOP and POS Convert X = A B + A B C to SOP standard form. The first term does not include the variable C. Therefore, multiply it by the (C + C), which = : X = A B (C + C) + A B C = A B C + A B C + A B C Convert X = (A + B)(A + B + C) to POS standard form. The first sum term does not include the variable C. Therefore, add C C and expand the result by rule 2. X = (A + B + C C)(A + B + C) = (A +B + C )(A + B + C)(A + B + C) 46 23

24 The Karnaugh Map (SOP) - The Karnaugh map (K-map) is a tool for simplifying combinational logic with 3 or 4 variables. For 3 variables, 8 cells are required (2 3 ). The map shown is for three variables labeled A, B, and C. Each cell represents one possible product term. Each cell differs from an adjacent cell by only one variable. ABC ABC ABC ABC ABC ABC ABC ABC 47 The Karnaugh Map (SOP) -2 Gray code Cells are usually labeled using 0 s and s to represent the variable and its complement. C AB The numbers are entered in gray code, to force adjacent cells to be different by only one variable. Ones are read as the true variable and zeros are read as the complemented variable

25 The Karnaugh Map (SOP) -3 A 3-variable Karnaugh map showing product terms. Gray code 49 The Karnaugh Map (SOP) -4 A 4-variable Karnaugh map

26 The Karnaugh Map (SOP) -5 The interesting about the map is that to go from one cell of the map to an adjacent cell will only require on variable to change. When moving on the map only go right or left, up or down, never go on a diagonal. For example from an A to an A. Also the map folds around its self so the going from a cell on the top right to one on the bottom right only changes one variable. 5 The Karnaugh Map (SOP) -6 K-maps can simplify combinational logic by grouping cells and eliminating variables that change. Group the s on the map and read the minimum logic. B changes across this boundary AB C Group the s into two overlapping groups as indicated. 2. Read each group by eliminating any variable that changes across a boundary. 0 C changes across this boundary 3. The vertical group is read AC. 4. The horizontal group is read AB. X = AC +AB 52 26

27 The Karnaugh Map (SOP) -7 Example of mapping a standard SOP expression 53 The Karnaugh Map (SOP) -8 A 4-variable map has an adjacent cell on each of its four boundaries as shown. AB AB AB AB CD CD CD CD Each cell is different only by one variable from an adjacent cell. Grouping follows the rules given in the text. The following slide shows an example of reading a four variable map using binary numbers for the variables 54 27

28 The Karnaugh Map (SOP) -9 A BCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD 55 The Karnaugh Map (SOP) -0 Group the s on the map and read the minimum logic. B changes B changes C changes across outer boundary CD AB C changes X. Group the s into two separate groups as indicated. 2. Read each group by eliminating any variable that changes across a boundary. 3. The upper (yellow) group is read as AD. 4. The lower (green) group is read as AD. X = AD +AD 56 28

29 The Karnaugh Map (SOP) - Group the s in the Karnaugh Map 57 The Karnaugh Map (SOP) -2 Group the s in the Karnaugh Map 58 29

30 The Karnaugh Map (SOP) -3 Group the s in the Karnaugh Map 59 The Karnaugh Map (SOP) -4 Group the s in the Karnaugh Map 60 30

31 The Karnaugh Map (SOP) -5 Determine the product terms for the Karnaugh map and write the resulting minimum SOP expression B + AC + ACD 6 The Karnaugh Map (SOP) -6 AB + BC + ABC B + AC + AC 62 3

32 The Karnaugh Map (SOP) -7 A B + AC + ABD D + ABC + BC 63 The Karnaugh Map (SOP) -8 Use a Karnaugh map to minimize the following standard SOP expression A BC + ABC + ABC + ABC + ABC Ans : B + AC 64 32

ABCD ABCD + ABCD + ABCD + ABCD Ans : D + BC 65 The Karnaugh Map

33 The Karnaugh Map (SOP) -9 Use a Karnaugh map to minimize the following standard SOP expression BCD + ABCD + ABCD + ABCD + ABCD ABCD + ABCD + ABCD + ABCD Ans : D + BC 65 The Karnaugh Map (SOP) -20 Mapping directly from a truth table to a Karnaugh map 66 33

34 The Karnaugh Map (SOP) -2 Don t care conditions 67 5-variable Karnaugh map

5-variable Karnaugh map -2 69 Simplify using Karnaugh

35 5-variable Karnaugh map Simplify using Karnaugh map First we need to change the circuit to a SOP 70 35

36 Y= A + B + B C + ( A + B ) ( C + D) Y = A B + B C + A B ( C + D ) Y = A B + B C + A B C + A B D Y = A B + B C + A B C A B D Y = A B + B C + (A + B + C ) ( A + B + D) Y = A B + B C + A + A B + A D + B + B D + C D 7 Gray Code 00 A B 0 A B A B 0 A B Z = C D C D C D C D X X X X X X X X X X X X X X X X The logic analyzer next 72 36

PowerPoint Presentation

PowerPoint Presentation ITM omputer and ommunication Technologies Lecture #4 Part I: Introduction to omputer Technologies Logic ircuit Design & Simplification ITM 計算機與通訊技術 2 23 香港中文大學電子工程學系 Logic function implementation Logic