Boolean Algebra computer fundamentals.pdf

Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha...

Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 1/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Learning Objectives In this chapter you will learn about: § Boolean algebra § Fundamental concepts and basic laws of Boolean algebra § Boolean function and minimization § Logic gates § Logic circuits and Boolean expressions § Combinational circuits and design Ref. Page 60 Chapter 6: Boolean Algebra and Logic Circuits Slide 2/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Boolean Algebra § An algebra that deals with binary number system § George Boole (1815-1864), an English mathematician, developed it for: § Simplifying representation § Manipulation of propositional logic § In 1938, Claude E. Shannon proposed using Boolean algebra in design of relay switching circuits § Provides economical and straightforward approach § Used extensively in designing electronic circuits used in computers Ref. Page 60 Chapter 6: Boolean Algebra and Logic Circuits Slide 3/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Fundamental Concepts of Boolean Algebra § Use of Binary Digit § Boolean equations can have either of two possible values, 0 and 1 § Logical Addition § Symbol ‘+’, also known as ‘OR’ operator, used for logical addition. Follows law of binary addition § Logical Multiplication § Symbol ‘.’, also known as ‘AND’ operator, used for logical multiplication. Follows law of binary multiplication § Complementation § Symbol ‘-’, also known as ‘NOT’ operator, used for complementation. Follows law of binary compliment Ref. Page 61 Chapter 6: Boolean Algebra and Logic Circuits Slide 4/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Operator Precedence § Each operator has a precedence level § Higher the operator’s precedence level, earlier it is evaluated § Expression is scanned from left to right § First, expressions enclosed within parentheses are evaluated § Then, all complement (NOT) operations are performed § Then, all ‘⋅’ (AND) operations are performed § Finally, all ‘+’ (OR) operations are performed (Continued on next slide) Ref. Page 62 Chapter 6: Boolean Algebra and Logic Circuits Slide 5/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Operator Precedence (Continued from previous slide..) X + Y ⋅ Z 1st 2nd 3rd Ref. Page 62 Chapter 6: Boolean Algebra and Logic Circuits Slide 6/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Postulates of Boolean Algebra Postulate 1: (a) A = 0, if and only if, A is not equal to 1 (b) A = 1, if and only if, A is not equal to 0 Postulate 2: (a) x + 0 = x (b) x ⋅ 1 = x Postulate 3: Commutative Law (a) x + y = y + x (b) x ⋅ y = y ⋅ x (Continued on next slide) Ref. Page 62 Chapter 6: Boolean Algebra and Logic Circuits Slide 7/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Postulates of Boolean Algebra (Continued from previous slide..) Postulate 4: Associative Law (a) x + (y + z) = (x + y) + z (b) x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z Postulate 5: Distributive Law (a) x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z) (b) x + (y ⋅ z) = (x + y) ⋅ (x + z) Postulate 6: (a) x + x = 1 (b) x ⋅ x = 0 Ref. Page 62 Chapter 6: Boolean Algebra and Logic Circuits Slide 8/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha The Principle of Duality There is a precise duality between the operators. (AND) and + (OR), and the digits 0 and 1. For example, in the table below, the second row is obtained from the first row and vice versa simply by interchanging ‘+’ with ‘.’ and ‘0’ with ‘1’ Column 1 Column 2 Column 3 Row 1 1+1=1 1+0=0+1=1 0+0=0 Row 2 0⋅0=0 0⋅1=1⋅0=0 1⋅1=1 Therefore, if a particular theorem is proved, its dual theorem automatically holds and need not be proved separately Ref. Page 63 Chapter 6: Boolean Algebra and Logic Circuits Slide 9/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Some Important Theorems of Boolean Algebra Sr. Theorems/ Dual Theorems/ Name No. Identities Identities (if any) 1 x+x=x x⋅x=x Idempotent Law 2 x+1=1 x⋅0=0 3 x+x⋅y=x x⋅x+y=x Absorption Law 4 x =x Involution Law 5 x⋅x +y=x⋅y x +x ⋅ y = x + y 6 x+y = x y⋅ x⋅y = x y+ De Morgan’s Law Ref. Page 63 Chapter 6: Boolean Algebra and Logic Circuits Slide 10/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Methods of Proving Theorems The theorems of Boolean algebra may be proved by using one of the following methods: 1. By using postulates to show that L.H.S. = R.H.S 2. By Perfect Induction or Exhaustive Enumeration method where all possible combinations of variables involved in L.H.S. and R.H.S. are checked to yield identical results 3. By the Principle of Duality where the dual of an already proved theorem is derived from the proof of its corresponding pair Ref. Page 63 Chapter 6: Boolean Algebra and Logic Circuits Slide 11/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Proving a Theorem by Using Postulates (Example) Theorem: x+x·y=x Proof: L.H.S. = x+x⋅y = x⋅1+x⋅y by postulate 2(b) = x ⋅ (1 + y) by postulate 5(a) = x ⋅ (y + 1) by postulate 3(a) = x⋅1 by theorem 2(a) = x by postulate 2(b) = R.H.S. Ref. Page 64 Chapter 6: Boolean Algebra and Logic Circuits Slide 12/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Proving a Theorem by Perfect Induction (Example) Theorem: x + x ·y = x = x y x⋅y x+x⋅y 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 Ref. Page 64 Chapter 6: Boolean Algebra and Logic Circuits Slide 13/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Proving a Theorem by the Principle of Duality (Example) Theorem: x+x=x Proof: L.H.S. =x+x = (x + x) ⋅ 1 by postulate 2(b) = (x + x) ⋅ (x + X) by postulate 6(a) = x + x ⋅X by postulate 5(b) =x+0 by postulate 6(b) =x by postulate 2(a) = R.H.S. (Continued on next slide) Ref. Page 63 Chapter 6: Boolean Algebra and Logic Circuits Slide 14/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Proving a Theorem by the Principle of Duality (Example) (Continued from previous slide..) Dual Theorem: x⋅x=x Proof: L.H.S. =x⋅x =x⋅x+0 by postulate 2(a) Notice that each step of the proof of the dual = x ⋅ x+ x⋅X by postulate 6(b) theorem is derived from = x ⋅ (x + X ) by postulate 5(a) the proof of its =x⋅1 by postulate 6(a) corresponding pair in =x by postulate 2(b) the original theorem = R.H.S. Ref. Page 63 Chapter 6: Boolean Algebra and Logic Circuits Slide 15/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Boolean Functions § A Boolean function is an expression formed with: § Binary variables § Operators (OR, AND, and NOT) § Parentheses, and equal sign § The value of a Boolean function can be either 0 or 1 § A Boolean function may be represented as: § An algebraic expression, or § A truth table Ref. Page 67 Chapter 6: Boolean Algebra and Logic Circuits Slide 16/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Representation as an Algebraic Expression W = X + Y ·Z § Variable W is a function of X, Y, and Z, can also be written as W = f (X, Y, Z) § The RHS of the equation is called an expression § The symbols X, Y, Z are the literals of the function § For a given Boolean function, there may be more than one algebraic expressions Ref. Page 67 Chapter 6: Boolean Algebra and Logic Circuits Slide 17/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Representation as a Truth Table X Y Z W 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 (Continued on next slide) Ref. Page 67 Chapter 6: Boolean Algebra and Logic Circuits Slide 18/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Representation as a Truth Table (Continued from previous slide..) § The number of rows in the table is equal to 2n, where n is the number of literals in the function § The combinations of 0s and 1s for rows of this table are obtained from the binary numbers by counting from 0 to 2n - 1 Ref. Page 67 Chapter 6: Boolean Algebra and Logic Circuits Slide 19/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Minimization of Boolean Functions § Minimization of Boolean functions deals with § Reduction in number of literals § Reduction in number of terms § Minimization is achieved through manipulating expression to obtain equal and simpler expression(s) (having fewer literals and/or terms) (Continued on next slide) Ref. Page 68 Chapter 6: Boolean Algebra and Logic Circuits Slide 20/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Minimization of Boolean Functions (Continued from previous slide..) F1 = x ⋅ y ⋅ z + x ⋅ y ⋅ z + x ⋅ y F1 has 3 literals (x, y, z) and 3 terms F2 = x ⋅ y + x ⋅ z F2 has 3 literals (x, y, z) and 2 terms F2 can be realized with fewer electronic components, resulting in a cheaper circuit (Continued on next slide) Ref. Page 68 Chapter 6: Boolean Algebra and Logic Circuits Slide 21/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Minimization of Boolean Functions (Continued from previous slide..) x y z F1 F2 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 Both F1 and F2 produce the same result Ref. Page 68 Chapter 6: Boolean Algebra and Logic Circuits Slide 22/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Try out some Boolean Function Minimization (a ) x + x ⋅ y ( (b ) x ⋅ x + y ) (c) x ⋅ y ⋅ z + x ⋅ y ⋅ z + x ⋅ y (d ) x ⋅ y + x ⋅ z + y ⋅ z (e) ( x + y ) ⋅ ( x + z ) ⋅ ( y +z ) Ref. Page 69 Chapter 6: Boolean Algebra and Logic Circuits Slide 23/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Complement of a Boolean Function § The complement of a Boolean function is obtained by interchanging: § Operators OR and AND § Complementing each literal § This is based on De Morgan’s theorems, whose general form is: A +A +A +...+A = A ⋅ A ⋅ A ⋅...⋅ A 1 2 3 n 1 2 3 n A ⋅ A ⋅ A ⋅...⋅ A = A +A +A +...+A 1 2 3 n 1 2 3 n Ref. Page 70 Chapter 6: Boolean Algebra and Logic Circuits Slide 24/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Complementing a Boolean Function (Example) F = x ⋅ y ⋅ z+ x ⋅ y ⋅ z 1 To obtain F1 , we first interchange the OR and the AND operators giving ( x + y +z ) ⋅ ( x + y + z ) Now we complement each literal giving F = ( x+ y +z) ⋅ ( x+ y+ z ) 1 Ref. Page 71 Chapter 6: Boolean Algebra and Logic Circuits Slide 25/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Canonical Forms of Boolean Functions Minterms : n variables forming an AND term, with each variable being primed or unprimed, provide 2n possible combinations called minterms or standard products Maxterms : n variables forming an OR term, with each variable being primed or unprimed, provide 2n possible combinations called maxterms or standard sums Ref. Page 71 Chapter 6: Boolean Algebra and Logic Circuits Slide 26/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Minterms and Maxterms for three Variables Variables Minterms Maxterms x y z Term Designation Term Designation 0 0 0 x ⋅y ⋅z m 0 x+y+z M 0 0 0 1 x ⋅y ⋅z m 1 x+y+z M 1 0 1 0 x ⋅y ⋅z m 2 x+y+z M 2 0 1 1 x ⋅y ⋅z m 3 x+y+z M 3 1 0 0 x ⋅y ⋅z m 4 x+y+z M 4 1 0 1 x ⋅y ⋅z m 5 x+y+z M 5 1 1 0 x ⋅y ⋅z m 6 x+ y+z M 6 1 1 1 x ⋅y ⋅z m 7 x+y+z M 7 Note that each minterm is the complement of its corresponding maxterm and vice-versa Ref. Page 71 Chapter 6: Boolean Algebra and Logic Circuits Slide 27/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Sum-of-Products (SOP) Expression A sum-of-products (SOP) expression is a product term (minterm) or several product terms (minterms) logically added (ORed) together. Examples are: x x+ y x+ y ⋅ z x ⋅ y+z x⋅y + x⋅y x⋅y + x⋅ y⋅z Ref. Page 72 Chapter 6: Boolean Algebra and Logic Circuits Slide 28/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Steps to Express a Boolean Function in its Sum-of-Products Form 1. Construct a truth table for the given Boolean function 2. Form a minterm for each combination of the variables, which produces a 1 in the function 3. The desired expression is the sum (OR) of all the minterms obtained in Step 2 Ref. Page 72 Chapter 6: Boolean Algebra and Logic Circuits Slide 29/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Expressing a Function in its Sum-of-Products Form (Example) x y z F1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 The following 3 combinations of the variables produce a 1: 001, 100, and 111 (Continued on next slide) Ref. Page 73 Chapter 6: Boolean Algebra and Logic Circuits Slide 30/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Expressing a Function in its Sum-of-Products Form (Example) (Continued from previous slide..) § Their corresponding minterms are: x ⋅ y ⋅ z, x ⋅ y ⋅ z, and x ⋅ y ⋅ z § Taking the OR of these minterms, we get F1 =x ⋅ y ⋅ z+ x ⋅ y ⋅ z+ x ⋅ y ⋅ z=m1+m 4 + m7 F1 ( x ⋅ y ⋅ z ) = ∑ (1,4,7 ) Ref. Page 72 Chapter 6: Boolean Algebra and Logic Circuits Slide 31/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Product-of Sums (POS) Expression A product-of-sums (POS) expression is a sum term (maxterm) or several sum terms (maxterms) logically multiplied (ANDed) together. Examples are: x ( x+ y )⋅( x+ y )⋅( x+ y ) x+ y ( x + y )⋅( x+ y+z ) ( x+ y ) ⋅ z ( x+ y )⋅( x+ y ) Ref. Page 74 Chapter 6: Boolean Algebra and Logic Circuits Slide 32/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Steps to Express a Boolean Function in its Product-of-Sums Form 1. Construct a truth table for the given Boolean function 2. Form a maxterm for each combination of the variables, which produces a 0 in the function 3. The desired expression is the product (AND) of all the maxterms obtained in Step 2 Ref. Page 74 Chapter 6: Boolean Algebra and Logic Circuits Slide 33/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Expressing a Function in its Product-of-Sums Form x y z F1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 § The following 5 combinations of variables produce a 0: 000, 010, 011, 101, and 110 (Continued on next slide) Ref. Page 73 Chapter 6: Boolean Algebra and Logic Circuits Slide 34/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Expressing a Function in its Product-of-Sums Form (Continued from previous slide..) § Their corresponding maxterms are: ( x+y+ z ) , ( x+ y+ z ), ( x+ y+ z ) , ( x+y+ z ) and ( x+ y+ z ) § Taking the AND of these maxterms, we get: F1 = ( x+y+z ) ⋅ ( x+ y+z ) ⋅ ( x+y+z ) ⋅ ( x+ y+z ) ⋅ ( x+ y+z ) =M ⋅M ⋅M ⋅ M ⋅M0 2 3 5 6 F1 ( x,y,z ) = Π( 0,2,3,5,6 ) Ref. Page 74 Chapter 6: Boolean Algebra and Logic Circuits Slide 35/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Conversion Between Canonical Forms (Sum-of- Products and Product-of-Sums) To convert from one canonical form to another, interchange the symbol and list those numbers missing from the original form. Example: ( ) ( ) ( F x,y,z = Π 0,2,4,5 = Σ 1,3,6,7 ) F( x,y,z ) = Σ (1,4,7 ) = Σ ( 0,2,3,5,6 ) Ref. Page 76 Chapter 6: Boolean Algebra and Logic Circuits Slide 36/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Logic Gates § Logic gates are electronic circuits that operate on one or more input signals to produce standard output signal § Are the building blocks of all the circuits in a computer § Some of the most basic and useful logic gates are AND, OR, NOT, NAND and NOR gates Ref. Page 77 Chapter 6: Boolean Algebra and Logic Circuits Slide 37/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha AND Gate § Physical realization of logical multiplication (AND) operation § Generates an output signal of 1 only if all input signals are also 1 Ref. Page 77 Chapter 6: Boolean Algebra and Logic Circuits Slide 38/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha AND Gate (Block Diagram Symbol and Truth Table) A C= A⋅B B Inputs Output A B C=A⋅B 0 0 0 0 1 0 1 0 0 1 1 1 Ref. Page 77 Chapter 6: Boolean Algebra and Logic Circuits Slide 39/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha OR Gate § Physical realization of logical addition (OR) operation § Generates an output signal of 1 if at least one of the input signals is also 1 Ref. Page 77 Chapter 6: Boolean Algebra and Logic Circuits Slide 40/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha OR Gate (Block Diagram Symbol and Truth Table) A C=A+B B Inputs Output A B C=A +B 0 0 0 0 1 1 1 0 1 1 1 1 Ref. Page 78 Chapter 6: Boolean Algebra and Logic Circuits Slide 41/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha NOT Gate § Physical realization of complementation operation § Generates an output signal, which is the reverse of the input signal Ref. Page 78 Chapter 6: Boolean Algebra and Logic Circuits Slide 42/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha NOT Gate (Block Diagram Symbol and Truth Table) A A Input Output A A 0 1 1 0 Ref. Page 79 Chapter 6: Boolean Algebra and Logic Circuits Slide 43/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha NAND Gate § Complemented AND gate § Generates an output signal of: § 1 if any one of the inputs is a 0 § 0 when all the inputs are 1 Ref. Page 79 Chapter 6: Boolean Algebra and Logic Circuits Slide 44/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha NAND Gate (Block Diagram Symbol and Truth Table) A B C= A ↑ B= A ⋅B=A +B Inputs Output A B C = A +B 0 0 1 0 1 1 1 0 1 1 1 0 Ref. Page 79 Chapter 6: Boolean Algebra and Logic Circuits Slide 45/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha NOR Gate § Complemented OR gate § Generates an output signal of: § 1 only when all inputs are 0 § 0 if any one of inputs is a 1 Ref. Page 79 Chapter 6: Boolean Algebra and Logic Circuits Slide 46/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha NOR Gate (Block Diagram Symbol and Truth Table) A B C= A ↓ B=A + B=A ⋅ B Inputs Output A B C =A ⋅ B 0 0 1 0 1 0 1 0 0 1 1 0 Ref. Page 80 Chapter 6: Boolean Algebra and Logic Circuits Slide 47/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Logic Circuits § When logic gates are interconnected to form a gating / logic network, it is known as a combinational logic circuit § The Boolean algebra expression for a given logic circuit can be derived by systematically progressing from input to output on the gates § The three logic gates (AND, OR, and NOT) are logically complete because any Boolean expression can be realized as a logic circuit using only these three gates Ref. Page 80 Chapter 6: Boolean Algebra and Logic Circuits Slide 48/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Finding Boolean Expression of a Logic Circuit (Example 1) A A NOT D= A ⋅ (B + C ) B B+C AND C OR Ref. Page 80 Chapter 6: Boolean Algebra and Logic Circuits Slide 49/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Finding Boolean Expression of a Logic Circuit (Example 2) OR A A +B B ( C= ( A +B ) ⋅ A ⋅ B ) A ⋅B A ⋅B AND AND NOT Ref. Page 81 Chapter 6: Boolean Algebra and Logic Circuits Slide 50/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Constructing a Logic Circuit from a Boolean Expression (Example 1) Boolean Expression = A ⋅B + C AND A A ⋅B B A ⋅B + C C OR Ref. Page 83 Chapter 6: Boolean Algebra and Logic Circuits Slide 51/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Constructing a Logic Circuit from a Boolean Expression (Example 2) Boolean Expression = A ⋅B + C ⋅D + E ⋅F AND NOT A A ⋅B A ⋅B B AND AND C C ⋅D D A ⋅B + C ⋅D + E ⋅F AND E E ⋅F E ⋅F F NOT Ref. Page 83 Chapter 6: Boolean Algebra and Logic Circuits Slide 52/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Universal NAND Gate § NAND gate is an universal gate, it is alone sufficient to implement any Boolean expression § To understand this, consider: § Basic logic gates (AND, OR, and NOT) are logically complete § Sufficient to show that AND, OR, and NOT gates can be implemented with NAND gates Ref. Page 84 Chapter 6: Boolean Algebra and Logic Circuits Slide 53/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementation of NOT, AND and OR Gates by NAND Gates A ⋅A = A + A = A A (a) NOT gate implementation. A A ⋅B A ⋅ B = A ⋅B B (b) AND gate implementation. (Continued on next slide) Ref. Page 85 Chapter 6: Boolean Algebra and Logic Circuits Slide 54/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementation of NOT, AND and OR Gates by NAND Gates (Continued from previous slide..) A ⋅A = A A A ⋅B = A + B = A + B B ⋅B = B B (c) OR gate implementation. Ref. Page 85 Chapter 6: Boolean Algebra and Logic Circuits Slide 55/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Method of Implementing a Boolean Expression with Only NAND Gates Step 1: From the given algebraic expression, draw the logic diagram with AND, OR, and NOT gates. Assume that both the normal (A) and complement (A) inputs are available Step 2: Draw a second logic diagram with the equivalent NAND logic substituted for each AND, OR, and NOT gate Step 3: Remove all pairs of cascaded inverters from the diagram as double inversion does not perform any logical function. Also remove inverters connected to single external inputs and complement the corresponding input variable Ref. Page 85 Chapter 6: Boolean Algebra and Logic Circuits Slide 56/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementing a Boolean Expression with Only NAND Gates (Example) Boolean Expression = A ⋅ B + C ⋅ ( A + B ⋅D ) A A ⋅B A ⋅ B + C ⋅ ( A + B ⋅D ) B B B ⋅D D A +B ⋅D A C C ⋅ ( A +B ⋅D ) (a) Step 1: AND/OR implementation (Continued on next slide) Ref. Page 87 Chapter 6: Boolean Algebra and Logic Circuits Slide 57/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementing a Boolean Expression with Only NAND Gates (Example) (Continued from previous slide..) AND A A ⋅B OR 1 B 5 AND OR B B ⋅D 2 D A+B ⋅D A ⋅ B + C⋅ ( A+B ⋅D) 3 A AND C⋅ ( A+B ⋅D) 4 C (b) Step 2: Substituting equivalent NAND functions (Continued on next slide) Ref. Page 87 Chapter 6: Boolean Algebra and Logic Circuits Slide 58/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementing a Boolean Expression with Only NAND Gates (Example) (Continued from previous slide..) A 1 B A ⋅ B + C ⋅ ( A +B ⋅D ) 5 B 2 D 3 A 4 C (c) Step 3: NAND implementation. Ref. Page 87 Chapter 6: Boolean Algebra and Logic Circuits Slide 59/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Universal NOR Gate § NOR gate is an universal gate, it is alone sufficient to implement any Boolean expression § To understand this, consider: § Basic logic gates (AND, OR, and NOT) are logically complete § Sufficient to show that AND, OR, and NOT gates can be implemented with NOR gates Ref. Page 89 Chapter 6: Boolean Algebra and Logic Circuits Slide 60/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementation of NOT, OR and AND Gates by NOR Gates A + A = A ⋅A = A A (a) NOT gate implementation. A A +B A + B = A +B B (b) OR gate implementation. (Continued on next slide) Ref. Page 89 Chapter 6: Boolean Algebra and Logic Circuits Slide 61/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementation of NOT, OR and AND Gates by NOR Gates (Continued from previous slide..) A A +A=A A + B = A ⋅B = A ⋅B B + B =B B (c) AND gate implementation. Ref. Page 89 Chapter 6: Boolean Algebra and Logic Circuits Slide 62/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Method of Implementing a Boolean Expression with Only NOR Gates Step 1: For the given algebraic expression, draw the logic diagram with AND, OR, and NOT gates. Assume that both the normal ( A ) and complement A inputs are available ( ) Step 2: Draw a second logic diagram with equivalent NOR logic substituted for each AND, OR, and NOT gate Step 3: Remove all parts of cascaded inverters from the diagram as double inversion does not perform any logical function. Also remove inverters connected to single external inputs and complement the corresponding input variable Ref. Page 89 Chapter 6: Boolean Algebra and Logic Circuits Slide 63/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementing a Boolean Expression with Only NOR Gates (Examples) (Continued from previous slide..) Boolean Expression A ⋅ B + C ⋅ ( A +B ⋅D ) = A A ⋅B B A ⋅ B + C ⋅ ( A +B ⋅D ) B B ⋅D D A +B ⋅D A C C ⋅ ( A +B ⋅D ) (a) Step 1: AND/OR implementation. (Continued on next slide) Ref. Page 90 Chapter 6: Boolean Algebra and Logic Circuits Slide 64/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementing a Boolean Expression with Only NOR Gates (Examples) (Continued from previous slide..) AN A D A ⋅B 1 OR A ⋅ B + C ⋅ ( A +B ⋅D ) B 5 6 AN B D B ⋅D 2 D OR AN 3 D A C ⋅ ( A +B ⋅D ) 4 C A +B ⋅D (b) Step 2: Substituting equivalent NOR functions. (Continued on next slide) Ref. Page 90 Chapter 6: Boolean Algebra and Logic Circuits Slide 65/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Implementing a Boolean Expression with Only NOR Gates (Examples) (Continued from previous slide..) A 1 B A ⋅ B + C ⋅ ( A +B ⋅D ) 5 6 B 2 D 3 A 4 C (c) Step 3: NOR implementation. Ref. Page 91 Chapter 6: Boolean Algebra and Logic Circuits Slide 66/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Exclusive-OR Function A ⊕ B =A ⋅ B + A ⋅ B A C = A ⊕ B = A ⋅B+ A ⋅B B A ⊕ C = A ⊕ B = A ⋅B+ A ⋅B B Also, ( A ⊕ B ) ⊕ C = A ⊕ (B ⊕ C ) = A ⊕ B ⊕ C (Continued on next slide) Ref. Page 91 Chapter 6: Boolean Algebra and Logic Circuits Slide 67/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Exclusive-OR Function (Truth Table) (Continued from previous slide..) Inputs Output A B C =A ⊕B 0 0 0 0 1 1 1 0 1 1 1 0 Ref. Page 92 Chapter 6: Boolean Algebra and Logic Circuits Slide 68/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Equivalence Function with Block Diagram Symbol A € B = A ⋅ B+ A ⋅ B A C = A € B = A ⋅B+ A ⋅B B Also, (A € B) € = A € (B € C) = A € B € C (Continued on next slide) Ref. Page 91 Chapter 6: Boolean Algebra and Logic Circuits Slide 69/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Equivalence Function (Truth Table) Inputs Output A B C=A€B 0 0 1 0 1 0 1 0 0 1 1 1 Ref. Page 92 Chapter 6: Boolean Algebra and Logic Circuits Slide 70/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Steps in Designing Combinational Circuits 1. State the given problem completely and exactly 2. Interpret the problem and determine the available input variables and required output variables 3. Assign a letter symbol to each input and output variables 4. Design the truth table that defines the required relations between inputs and outputs 5. Obtain the simplified Boolean function for each output 6. Draw the logic circuit diagram to implement the Boolean function Ref. Page 93 Chapter 6: Boolean Algebra and Logic Circuits Slide 71/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Designing a Combinational Circuit Example 1 – Half-Adder Design Inputs Outputs A B C S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 S = A ⋅B+ A ⋅B Boolean functions for the two outputs. C = A ⋅B Ref. Page 93 Chapter 6: Boolean Algebra and Logic Circuits Slide 72/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Designing a Combinational Circuit Example 1 – Half-Adder Design (Continued from previous slide..) A A ⋅B A S = A ⋅B+ A ⋅B B B A ⋅B A B C = A ⋅B Logic circuit diagram to implement the Boolean functions Ref. Page 94 Chapter 6: Boolean Algebra and Logic Circuits Slide 73/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Designing a Combinational Circuit Example 2 – Full-Adder Design Inputs Outputs A B D C S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Truth table for a full adder (Continued on next slide) Ref. Page 94 Chapter 6: Boolean Algebra and Logic Circuits Slide 74/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Designing a Combinational Circuit Example 2 – Full-Adder Design (Continued from previous slide..) Boolean functions for the two outputs: S = A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D C = A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D+ A ⋅B ⋅D = A ⋅B+ A ⋅D+B ⋅D (when simplified) (Continued on next slide) Ref. Page 95 Chapter 6: Boolean Algebra and Logic Circuits Slide 75/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Designing a Combinational Circuit Example 2 – Full-Adder Design (Continued from previous slide..) A A ⋅B ⋅ D B D A A ⋅B ⋅ D B D S A B A ⋅B ⋅ D D A A ⋅B ⋅ D B D (a) Logic circuit diagram for sums (Continued on next slide) Ref. Page 95 Chapter 6: Boolean Algebra and Logic Circuits Slide 76/78  Computer Computer Fundamentals: Fundamentals: Pradeep Pradeep K. K. Sinha Sinha & & Priti Priti Sinha Sinha Designing a Combinational Circuit Example 2 – Full-Adder Design (Continued from previous slide..) A A ⋅B B A A ⋅D C D B B⋅D D (b) Logic circuit diagram for carry Ref. Page 95 Chapter 6: Boolean Algebra and Logic Circuits Slide 77/78  Computer Computer Fundamentals: