樹德科技大學資訊工程系 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
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 = 0. 4 2
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
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
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
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
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
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
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
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
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
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 0 0 0 0 0 0 24 2
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 0 0 0 0 0 0 0 0 0 0 25 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
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
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
Example 3 (/2) 3 Example 3 (2/2) X = ABCD +A X = A + BCD 32 6
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
Example 5 (/3) 35 Example 5 (2/3) 36 8
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
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 0 40 20
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
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
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
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 00 0 0 0 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. 48 24
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. 50 25
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 00 0 0. 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
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
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 00 0 0 AB 00 0 0 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
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
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
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
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
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
The Karnaugh Map (SOP) -2 Don t care conditions 67 5-variable Karnaugh map - 68 34
5-variable Karnaugh map -2 69 Simplify using Karnaugh map First we need to change the circuit to a SOP 70 35
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 = 00 0 0 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