Boolean Algebra PDF

BOOLEAN ALGEBRA BY: ENGR. ABDUL JALIL CHAPTER OUTLINES Boolean Operations and Expressions Laws and Rules of Boolean Algebra DeMorgans Theorems Boolean Analysis of Logic Circuit Simplification using Boolean Algebra Standard Form of Boolean Expressions Boolean Expressions...

BOOLEAN ALGEBRA BY: ENGR. ABDUL JALIL CHAPTER OUTLINES Boolean Operations and Expressions Laws and Rules of Boolean Algebra DeMorgans Theorems Boolean Analysis of Logic Circuit Simplification using Boolean Algebra Standard Form of Boolean Expressions Boolean Expressions and Truth Tables The Karnaugh Map  INTRODUCTION 1854: George Boole was published a work titled by An Investigation of the laws of Thoughts from which he founded the mathematical theories of Logic and Probabilities → It was in this publication “Logical Algebra” known today as “Boolean Algebra” It’s a convenient way and systematic way of expressing and analyzing the operation of logic circuits. 1938: Claude Shannon was the first to apply Boole’s work to the analysis and design of logic circuits. BOOLEAN OPERATIONS & EXPRESSIONS Variable – a symbol used to represent a logical quantity. Complement – the inverse of a variable and is indicated by a bar over the variable. For. Example, the complement of variable A is If =0 then A=1. If A=0 then = 1 Literal – a variable or the complement of a variable. BOOLEAN ADDITION Boolean addition is equivalent to the OR operation 0+0 = 0 0+1 = 1 1+0 = 1 1+1 = 1 In Boolean Algebra, the sum term is produced by an OR operation with no AND operation involved. i.e. A + B, A + B , A + B + C , A + B + C + D A sum term is equal to 1 when one or more of the literals in the term are 1. A sum term is equal to 0 only if each of the literals is 0. BOOLEAN MULTIPLICATION Boolean multiplication is equivalent to the AND operation 0·0 = 0 0·1 = 0 1·0 = 0 1·1 = 1 In Boolean Algebra, the product term is produced by an AND operation with no OR operation involved. i.e. AB, AB A product , ABisCequal term , A BCtoD1 only if each of the literals in the term is 1. A product term is equal to 0 when one or more of the literals are 0. LAWS & RULES OF BOOLEAN ALGEBRA The basic laws of Boolean algebra: The commutative laws () The associative laws () The distributive laws () COMMUTATIVE LAWS The commutative law of addition for two variables is written as: A+B = B+A A B A+B  B A B+A The commutative law of multiplication for two variables is written as: AB = BA A B AB  B A B+A ASSOCIATIVE LAWS The associative law of addition for 3 variables is written as: A+(B+C) = (A+B)+C  A A A+B B A+(B+C) B (A+B)+C C C B+C The associative law of multiplication for 3 variables is written as: A(BC) = (AB)C  A A AB A(BC) B B (AB)C C BC C DISTRIBUTIVE LAWS The distributive law is written for 3 variables as follows: A(B+C) = AB + AC B A AB B+C  C B X X A A C AC X=A(B+C) X=AB+AC RULES OF BOOLEAN ALGEBRA 1. A + 0 = A 7. A A = A 2. A + 1 = 1 8. A A = 0 3. A 0 = 0 9. A = A 4. A 1 = A 10. A + AB = A 5. A + A = A 11. A + A B = A + B 6. A + A = 1 12.( A + B)( A + C ) = A + BC ___________________________________________________________ A, B, and C can represent a single variable or a combination of variables. RULES OF BOOLEAN ALGEBRA RULES OF BOOLEAN ALGEBRA RULES OF BOOLEAN ALGEBRA RULES OF BOOLEAN ALGEBRA RULES OF BOOLEAN ALGEBRA RULES OF BOOLEAN ALGEBRA GATE CIRCUIT FOR EXAMPLE 4-8 APPLY LAWS AND RULES OF BOOLEAN ALGEBRA DEMORGAN’S THEOREMS DeMorgan’s theorems provide mathematical verification of: the equivalency of the NAND and negative-OR gates the equivalency of the NOR and negative-AND gates. DEMORGAN’S THEOREMS The complement of two or NAND Negative-OR more ANDed variables is equivalent to the OR of the complements of the individual X Y = X + Y variables. The complement of two or NOR Negative-AND more ORed variables is equivalent to the AND of the X + Y = X Y complements of the individual variables. DEMORGAN’S THEOREMS (EXERCISES) Apply DeMorgan’s theorems to the expressions: X Y Z X +Y + Z X +Y + Z W X Y Z DEMORGAN’S THEOREMS (EXERCISES) Apply DeMorgan’s theorems to the expressions: ( A + B + C)D ABC + DEF AB + C D + EF A + BC + D( E + F ) BOOLEAN ANALYSIS OF LOGIC CIRCUITS Boolean algebra provides a concise way to express the operation of a logic circuit formed by a combination of logic gates so that the output can be determined for various combinations of input values. BOOLEAN EXPRESSION FOR A LOGIC CIRCUIT To derive the Boolean expression for a given logic circuit, begin at the left-most inputs and work toward the final output, writing the expression for each gate. C CD D B+CD B A(B+CD) A CONSTRUCTING A TRUTH TABLE FOR A LOGIC CIRCUIT Once the Boolean expression for a given logic circuit has been determined, a truth table that shows the output for all possible values of the input variables can be developed. Let’s take the previous circuit as the example: A(B+CD) There are four variables, hence 16 (24) combinations of values are possible. CONSTRUCTING A TRUTH TABLE FOR A LOGIC CIRCUIT Evaluating the expression To evaluate the expression A(B+CD), first find the values of the variables that make the expression equal to 1 (using the rules for Boolean add & mult). In this case, the expression equals 1 only if A=1 and B+CD=1 because A(B+CD) = 1·1 = 1 CONSTRUCTING A TRUTH TABLE FOR A LOGIC CIRCUIT Evaluating the expression (cont’) Now, determine when B+CD term equals 1. The term B+CD=1 if either B=1 or CD=1 or if both B and CD equal 1 because B+CD = 1+0 = 1 B+CD = 0+1 = 1 B+CD = 1+1 = 1 The term CD=1 only if C=1 and D=1 CONSTRUCTING A TRUTH TABLE FOR A LOGIC CIRCUIT Evaluating the expression (cont’) Summary: A(B+CD)=1 When A=1 and B=1 regardless of the values of C and D When A=1 and C=1 and D=1 regardless of the value of B The expression A(B+CD)=0 for all other value combinations of the variables. CONSTRUCTING A TRUTH TABLE FOR A LOGIC CIRCUIT Putting the results in truth INPUTS OUTPUT A B C D A(B+CD) 0 0 0 0 0 table format 0 0 0 1 0 A(B+CD)=1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 When A=1 and 0 1 0 1 0 B=1 regardless 0 1 1 0 0 of the values 0 1 1 1 0 1 0 0 0 0 of C and D 1 0 0 1 0 When A=1 and C=1 1 0 1 0 0 and D=1 regardless of 1 0 1 1 1 1 1 0 0 1 the value of B 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 STANDARD FORMS OF BOOLEAN EXPRESSIONS  SOP AND POS FORMS Boolean expressions can be written in the sum-of-products form (SOP) or in the product-of-sums form (POS). These forms can simplify the implementation of combinational logic, particularly with PLDs. An expression is in SOP form when two or more product terms are summed by Boolean addition, then the resulting expression is a sum-of-products form as in the following examples: An expression is in POS form when two or more sum terms are multiplied, , then the resulting expression is a product-of-sums (POS) as in the following examples: SOP STANDARD FORM PRODUCT-OF-SUM FORM(POS) STEPS FOR CONVERSION OF SUM-TERMS TO STANDARD POS FORM CONVERTING SOP EXPRESSIONS INTO A TRUTH TABLE FORMAT The first step in converting SOP expression into a truth table format is to construct a truth table that list all possible combinations of binary values of the variables in the expressions For an expression with a domain of two variables, there are four different combinations of those variables Next, convert the SOP expression to standard form Finally, place a 1 in the output column (x) for each binary value that makes the standard SOP expression a 1 and place 0 for all remaining binary values CONVERTING POS EXPRESSIONS INTO A TRUTH TABLE FORMAT The first step in converting POS expression into a truth table format is to construct a truth table that list all possible combinations of binary values of the variables in the expressions For an expression with a domain of two variables, there are four different combinations of those variables Next, convert the POS expression to standard form Finally, place a “0” in the output column (x) for each binary value that makes the standard POS expression a 0 and place 1 for all remaining binary values