Fundamentals of Logic Design, 7th edition Roth/Kinney UNIT 3 Boolean Algebra (continued) 2014 Cengage Learning Engineering. All Rights Reserved. 1 Fundamentals of Logic Design, 7th edition Roth/Kinney

This chapter includes: 3.1 Multiplying out and Factoring Expressions 3.2 Exclusive-OR and Equivalence Operations 3.3 The Consensus Theorem 3.4 Algebraic Simplification of Switching Expressions 3.5 Proving Validity of an Equation 2014 Cengage Learning Engineering. All Rights Reserved. 2 Fundamentals of Logic Design, 7th edition

Roth/Kinney Learning Objectives 1. Apply the laws and theorems of Boolean algebra to to the manipulation of algebraic expressions to simplifying an expression, finding the complement of an expression and multiplying out and factoring an expression. 2. Prove any of the theorems using a truth table or give an algebraic proof. 3. Define the exclusive-OR and equivalence operations. State, prove, and use the basic theorems that concern these operations. 4. Use the consensus theorem to delete terms from and add terms to a switching algebra expression. 5. Given an equation, prove algebraically that it is valid or show that it is not valid.

2014 Cengage Learning Engineering. All Rights Reserved. 3 Fundamentals of Logic Design, 7th edition Roth/Kinney Multiplying out and Factoring Expressions Given an expression in product-of-sums form, the corresponding sum-of-products expression can be obtained by multiplying out, using the two distributive laws: In addition, the following theorem is very useful

for factoring and multiplying out: 2014 Cengage Learning Engineering. All Rights Reserved. 4 Fundamentals of Logic Design, 7th edition Roth/Kinney Multiplying out and Factoring Expressions In general, when we multiply out an expression, we should use (3-3) along with (3-1) and (3-2). To avoid generating unnecessary terms when multiplying out, (3-2) and (3-3) should generally

be applied before (3-1), and terms should be grouped to expedite their application. 2014 Cengage Learning Engineering. All Rights Reserved. 5 Fundamentals of Logic Design, 7th edition Roth/Kinney Multiplying out and Factoring Expressions Example 1: 2014 Cengage Learning Engineering. All Rights Reserved.

6 Fundamentals of Logic Design, 7th edition Roth/Kinney Multiplying out and Factoring Expressions Example 2: By repeatedly applying (3-1), (3-2), and (3-3), any expression can be converted to a product-of-sums form. 2014 Cengage Learning Engineering. All Rights Reserved.

7 Fundamentals of Logic Design, 7th edition Roth/Kinney Multiplying out and Factoring Expressions Example 2 (continued): 2014 Cengage Learning Engineering. All Rights Reserved. 8 Fundamentals of Logic Design, 7th edition

Roth/Kinney Exclusive-OR and Equivalence Operations Exclusive-OR (XOR) Operation: (a) (c) (b) From left to right, (a) XOR truth table, (b) XOR definition, (c) XOR logic symbol. 2014 Cengage Learning Engineering. All Rights Reserved. 9

Fundamentals of Logic Design, 7th edition Roth/Kinney Exclusive-OR and Equivalence Operations For exclusive-OR, X Y = 1 if and only if (iff) X = 1 or Y = 1, but not both. The ordinary OR operation is sometimes called inclusive-OR because X + Y = 1 iff X = 1 or Y = 1, or both. Exclusive OR can be expressed in terms of AND and OR. Because X Y = 1 iff X is 0 and Y is 1 or X is 1 and Y is 0, we can write X Y = XY + XY (3-6)

Derivation of (3-6) is on page 68. 2014 Cengage Learning Engineering. All Rights Reserved. 10 Fundamentals of Logic Design, 7th edition Roth/Kinney Exclusive-OR and Equivalence Operations Theorems for Exclusive-OR: 2014 Cengage Learning Engineering. All Rights Reserved. 11

Fundamentals of Logic Design, 7th edition Roth/Kinney Exclusive-OR and Equivalence Operations Equivalence Operation: (a) (c) (b) From left to right, (a) Equivalence operation truth table, (b) Definition, (c) Logic symbols, equivalence

and exclusive-NOR gates 2014 Cengage Learning Engineering. All Rights Reserved. 12 Fundamentals of Logic Design, 7th edition Roth/Kinney Exclusive-OR and Equivalence Operations Equivalence Operations: For this operation, the output will be 1 iff X and Y have the same value. So, Equivalence is the complement of the exclusive-OR

operation. 2014 Cengage Learning Engineering. All Rights Reserved. 13 Fundamentals of Logic Design, 7th edition Roth/Kinney The Consensus Theorem Consensus Theorem: The consensus theorem is used to cancel out redundant terms in an expression and is stated below: The term that is eliminated can be called the

consensus term. The dual form of the consensus theorem is: 2014 Cengage Learning Engineering. All Rights Reserved. 14 Fundamentals of Logic Design, 7th edition Roth/Kinney The Consensus Theorem Example 3: 2014 Cengage Learning Engineering. All Rights Reserved.

15 Fundamentals of Logic Design, 7th edition Roth/Kinney The Consensus Theorem Example 3 (continued): 2014 Cengage Learning Engineering. All Rights Reserved. 16 Fundamentals of Logic Design, 7th edition Roth/Kinney

The Consensus Theorem Example 3 (continued): 2014 Cengage Learning Engineering. All Rights Reserved. 17 Fundamentals of Logic Design, 7th edition Roth/Kinney Algebraic Simplification of Switching Expressions Ways to simplify switching expressions:

In addition to multiplying out and factoring, three basic ways of simplifying switching functions are: combining terms eliminating terms eliminating literals 2014 Cengage Learning Engineering. All Rights Reserved. 18 Fundamentals of Logic Design, 7th edition Roth/Kinney Algebraic Simplification of Switching

Expressions Combining Terms: 2014 Cengage Learning Engineering. All Rights Reserved. 19 Fundamentals of Logic Design, 7th edition Roth/Kinney Algebraic Simplification of Switching Expressions Eliminating Terms and Literals: 2014 Cengage Learning Engineering. All Rights Reserved.

20 Fundamentals of Logic Design, 7th edition Roth/Kinney Algebraic Simplification of Switching Expressions Example 4: Example 5- Adding Redundant Terms: 2014 Cengage Learning Engineering. All Rights Reserved. 21

Fundamentals of Logic Design, 7th edition Roth/Kinney Algebraic Simplification of Switching Expressions Example 6: 2014 Cengage Learning Engineering. All Rights Reserved. 22 Fundamentals of Logic Design, 7th edition Roth/Kinney

Algebraic Simplification of Switching Expressions Example 7: For a product-of-sums form instead of a sum-ofproducts form, the duals of the preceding theorems should be applied. 2014 Cengage Learning Engineering. All Rights Reserved. 23 Fundamentals of Logic Design, 7th edition Roth/Kinney

Proving the Validity of an Equation Proving an equation is valid: To determine if an equation is valid, meaning valid for all combinations of values of the variables, several methods can be used: 1. Construct a truth table and evaluate both sides of the equation for all combinations of values of the variables. 2. Manipulate one side of the equation by applying various theorems until it is identical with the other side. 2014 Cengage Learning Engineering. All Rights Reserved. 24

Fundamentals of Logic Design, 7th edition Roth/Kinney Proving the Validity of an Equation Proving an Equation is valid (continued): 3. Reduce both sides of the equation independently to the same expression. 4. It is permissible to perform the same operation on both sides of the equation provided that the operation is reversible. 2014 Cengage Learning Engineering. All Rights Reserved. 25

Fundamentals of Logic Design, 7th edition Roth/Kinney Proving the Validity of an Equation To prove an equation is NOT valid: To prove that an equation is not valid, it is sufficient to show one combination of values of the variables for which the two sides of the equation have different values. 1. First reduce both sides to a sum of products (or a product of sums). 2. Compare the two sides of the equation to see how they differ. 3. Then try to add terms to one side of the equation that are present on the other side.

4. Finally try to eliminate terms from one side that are not present on the other. Whatever method is used, frequently compare both sides of the equation and let the difference between them serve as a guide for what steps to take next. 2014 Cengage Learning Engineering. All Rights Reserved. 26 Fundamentals of Logic Design, 7th edition Roth/Kinney Proving the Validity of an Equation Example 8:

2014 Cengage Learning Engineering. All Rights Reserved. 27 Fundamentals of Logic Design, 7th edition Roth/Kinney Proving the Validity of an Equation Example 9: 2014 Cengage Learning Engineering. All Rights Reserved. 28 Fundamentals of Logic Design, 7th edition

Roth/Kinney Proving the Validity of an Equation Example 9 (continued): 2014 Cengage Learning Engineering. All Rights Reserved. 29 Fundamentals of Logic Design, 7th edition Roth/Kinney Proving the Validity of an Equation Cancellation Laws in Boolean Algebra:

The cancellation law for ordinary algebra, where: If x+y=x+z then y=z Does not hold for Boolean algebra. The cancellation law for multiplication, where: If xy=xz then y=z Does not hold for Boolean algebra. However, the converses of these hold true: 2014 Cengage Learning Engineering. All Rights Reserved. 30