Page 2 :
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

Page 3 :
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

Page 4 :
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

Page 5 :
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

Page 7 :
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

Page 8 :
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

Page 9 :
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

Page 10 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Some Important Theorems of Boolean Algebra, , Sr., No., , Theorems/, Identities, , Dual Theorems/, Identities, , 1, , x+x=x, , x⋅x=x, , 2, , x+1=1, , x⋅0=0, , 3, , x+x⋅y=x, , x⋅x+y=x, , 4, , x, , 5, , x⋅x +y=x⋅y, , 6, , x+y, , Ref. Page 63, , =x, , = x y⋅, , Name, (if any), Idempotent Law, , Absorption Law, Involution Law, , x +x ⋅ y = x + y, , x⋅y, , = x y+, , De Morgan’s, Law, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 10/78

Page 11 :
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

Page 12 :
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., =, =, =, =, =, =, =, , Ref. Page 64, , x+x⋅y, x⋅1+x⋅y, x ⋅ (1 + y), x ⋅ (y + 1), x⋅1, x, R.H.S., , by, by, by, by, by, , postulate 2(b), postulate 5(a), postulate 3(a), theorem 2(a), postulate 2(b), , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 12/78

Page 13 :
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, =, , Ref. Page 64, , x, , y, , x⋅y, , x+x⋅y, , 0, , 0, , 0, , 0, , 0, , 1, , 0, , 0, , 1, , 0, , 0, , 1, , 1, , 1, , 1, , 1, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 13/78

Page 14 :
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, = (x + x) ⋅ (x + X), = x + x ⋅X, =x+0, =x, = R.H.S., , by, by, by, by, by, , postulate, postulate, postulate, postulate, postulate, , 2(b), 6(a), 5(b), 6(b), 2(a), , (Continued on next slide), , Ref. Page 63, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 14/78

Page 15 :
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, = x ⋅ x+ x⋅X, = x ⋅ (x + X ), =x⋅1, =x, = R.H.S., , Ref. Page 63, , by, by, by, by, by, , postulate, postulate, postulate, postulate, postulate, , 2(a), 6(b), 5(a), 6(a), 2(b), , Notice that each step of, the proof of the dual, theorem is derived from, the proof of its, corresponding pair in, the original theorem, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 15/78

Page 16 :
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

Page 17 :
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

Page 18 :
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

Page 19 :
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

Page 20 :
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

Page 21 :
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

Page 22 :
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

Page 23 :
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), , Ref. Page 69, , ( x + y ) ⋅ ( x + z ) ⋅ ( y +z ), , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 23/78

Page 24 :
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, A ⋅ A ⋅ A ⋅...⋅ A = A +A +A +...+A, 1, , 1, , Ref. Page 70, , 2, , 2, , 3, , 3, , n, , n, , 1, , 1, , 2, , 2, , 3, , 3, , Chapter 6: Boolean Algebra and Logic Circuits, , n, , n, , Slide 24/78

Page 25 :
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

Page 27 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Minterms and Maxterms for three Variables, Variables, x, , y, , z, , 0, , 0, , 0, , 0, , 0, , 1, , 0, , 1, , 0, , Minterms, Term, , Maxterms, , Designation, , m, , 0, , x+y+z, , M, , 0, , x ⋅y ⋅z, , m, , 1, , x+y+z, , M, , 1, , x ⋅y ⋅z, , m, , 2, , x+y+z, , M, , 2, , x+y+z, , M, , 3, , x+y+z, , M, , 4, , x+y+z, , M, , 5, , x+ y+z, , M, , 6, , x+y+z, , M, , 7, , 1, , 1, , x ⋅y ⋅z, , m, , 3, , 1, , 0, , 0, , x ⋅y ⋅z, , m, , 4, , x ⋅y ⋅z, , m, , 5, , x ⋅y ⋅z, x ⋅y ⋅z, , m, , 6, , m, , 7, , 1, 1, , 0, 1, 1, , 1, 0, 1, , Designation, , x ⋅y ⋅z, , 0, , 1, , Term, , 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

Page 28 :
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 ⋅ z, x⋅y + x⋅y, , Ref. Page 72, , x+ y, x ⋅ y+z, x⋅y + x⋅ y⋅z, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 28/78

Page 29 :
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

Page 30 :
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

Page 31 :
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

Page 32 :
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 ) ⋅ z, , Ref. Page 74, , ( x+ y )⋅( x+ y )⋅( x+ y ), ( x + y )⋅( x+ y+z ), ( x+ y )⋅( x+ y ), , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 32/78

Page 33 :
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

Page 34 :
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

Page 35 :
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 ⋅M, ( x,y,z ) = Π( 0,2,3,5,6 ), 0, , F1, Ref. Page 74, , 2, , 3, , 5, , 6, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 35/78

Page 36 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Conversion Between Canonical Forms (Sum-ofProducts 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 ) = Σ (1,4,7 ) = Σ ( 0,2,3,5,6 ), F x,y,z = Π 0,2,4,5 = Σ 1,3,6,7, , Ref. Page 76, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 36/78

Page 37 :
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

Page 38 :
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

Page 39 :
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, , Ref. Page 77, , Output, , A, , B, , C=A⋅B, , 0, , 0, , 0, , 0, , 1, , 0, , 1, , 0, , 0, , 1, , 1, , 1, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 39/78

Page 40 :
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

Page 41 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , OR Gate (Block Diagram Symbol, and Truth Table), A, B, , C=A+B, Inputs, , Ref. Page 78, , Output, , A, , B, , C=A +B, , 0, , 0, , 0, , 0, , 1, , 1, , 1, , 0, , 1, , 1, , 1, , 1, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 41/78

Page 42 :
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

Page 43 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , NOT Gate (Block Diagram Symbol, and Truth Table), A, , Ref. Page 79, , A, Input, , Output, , A, , A, , 0, , 1, , 1, , 0, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 43/78

Page 44 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , NAND Gate, § Complemented AND gate, § Generates an output signal of:, , Ref. Page 79, , §, , 1 if any one of the inputs is a 0, , §, , 0 when all the inputs are 1, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 44/78

Page 45 :
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, , Ref. Page 79, , Output, , A, , B, , C = A +B, , 0, , 0, , 1, , 0, , 1, , 1, , 1, , 0, , 1, , 1, , 1, , 0, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 45/78

Page 46 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , NOR Gate, § Complemented OR gate, § Generates an output signal of:, , Ref. Page 79, , §, , 1 only when all inputs are 0, , §, , 0 if any one of inputs is a 1, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 46/78

Page 47 :
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, , Ref. Page 80, , Output, , A, , B, , C =A ⋅ B, , 0, , 0, , 1, , 0, , 1, , 0, , 1, , 0, , 0, , 1, , 1, , 0, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 47/78

Page 48 :
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

Page 49 :
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+C, , B, C, , AND, , OR, , Ref. Page 80, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 49/78

Page 50 :
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 +B, , A, B, , (, , C= ( A +B ) ⋅ A ⋅ B, A ⋅B, , A ⋅B, AND, , Ref. Page 81, , ), , AND, , NOT, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 50/78

Page 51 :
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

Page 52 :
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 =, , AND, , A ⋅B, , A, B, , NOT, , A ⋅B + C ⋅D + E ⋅F, A ⋅B, AND, , AND, , C ⋅D, , C, D, , A ⋅B + C ⋅D + E ⋅F, AND, , E, F, , Ref. Page 83, , E ⋅F, , E ⋅F, NOT, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 52/78

Page 53 :
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:, , Ref. Page 84, , §, , 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, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 53/78

Page 54 :
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, B, , A ⋅B, , A ⋅ B = A ⋅B, , (b) AND gate implementation., , (Continued on next slide), , Ref. Page 85, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 54/78

Page 55 :
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, B, , A ⋅A = A, A ⋅B = A + B = A + B, B ⋅B = B, (c) OR gate implementation., , Ref. Page 85, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 55/78

Page 56 :
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

Page 57 :
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, B, D, A, C, , A ⋅B, B ⋅D, , A ⋅ B + C ⋅ ( A + B ⋅D ), A ⋅ B + C ⋅ ( A + B ⋅D ), , A +B ⋅D, 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

Page 58 :
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, B, , 1, , A ⋅B, , OR, , 5, , AND, , B, D, , 2, , OR, , B ⋅D, , A+B ⋅D, A ⋅ B + C⋅ ( A+B ⋅D), , 3, , A, , AND, , C, , 4, , C⋅ ( A+B ⋅D), , (b) Step 2: Substituting equivalent NAND functions, (Continued on next slide), , Ref. Page 87, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 58/78

Page 59 :
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, B, D, , 5, , A ⋅ B + C ⋅ ( A +B ⋅D ), , 2, , A, C, , 3, 4, , (c) Step 3: NAND implementation., , Ref. Page 87, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 59/78

Page 60 :
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:, , Ref. Page 89, , §, , 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, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 60/78

Page 61 :
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, B, , A +B, , A + B = A +B, , (b) OR gate implementation., , (Continued on next slide), , Ref. Page 89, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 61/78

Page 62 :
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

Page 63 :
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

Page 64 :
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, B, , Boolean Expression A ⋅ B + C ⋅ ( A +B ⋅D ), =, A ⋅B, , B, D, A, C, , A ⋅ B + C ⋅ ( A +B ⋅D ), B ⋅D, , A +B ⋅D, 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

Page 65 :
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, D, , A, 1, , A ⋅B, OR, , B, 5, , AN, D, , B, 2, , A ⋅ B + C ⋅ ( A +B ⋅D ), , B ⋅D, , D, A, , 6, , OR, , AN, D, , 3, 4, , C, , C ⋅ ( A +B ⋅D ), , 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

Page 66 :
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, B, , 1, , 5, , B, D, , 6, , A ⋅ B + C ⋅ ( A +B ⋅D ), , 2, , A, C, , 3, 4, , (c) Step 3: NOR implementation., , Ref. Page 91, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 66/78

Page 67 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Exclusive-OR Function, A ⊕ B =A ⋅ B + A ⋅ B, C = A ⊕ B = A ⋅B+ A ⋅B, , A, B, A, B, , ⊕, , C = A ⊕ B = A ⋅B+ A ⋅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

Page 68 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Exclusive-OR Function (Truth Table), (Continued from previous slide..), , Inputs, , Ref. Page 92, , Output, , A, , B, , C =A ⊕B, , 0, , 0, , 0, , 0, , 1, , 1, , 1, , 0, , 1, , 1, , 1, , 0, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 68/78

Page 69 :
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, B, , C = A € B = A ⋅B+ A ⋅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

Page 70 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Equivalence Function (Truth Table), Output, , Inputs, , Ref. Page 92, , C=A€B, , A, , B, , 0, , 0, , 1, , 0, , 1, , 0, , 1, , 0, , 0, , 1, , 1, , 1, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 70/78

Page 71 :
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

Page 72 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Designing a Combinational Circuit, Example 1 – Half-Adder Design, Inputs, 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, C = A ⋅B, Ref. Page 93, , Outputs, , Boolean functions for the two outputs., , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 72/78

Page 73 :
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, , A ⋅B, S = A ⋅B+ A ⋅B, , B, A, B, , 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

Page 74 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Designing a Combinational Circuit, Example 2 – Full-Adder Design, Inputs, A, 0, 0, 0, 0, 1, 1, 1, 1, , B, 0, 0, 1, 1, 0, 0, 1, 1, , Outputs, D, 0, 1, 0, 1, 0, 1, 0, 1, , C, 0, 0, 0, 1, 0, 1, 1, 1, , Truth table for a full adder, , Ref. Page 94, , Chapter 6: Boolean Algebra and Logic Circuits, , S, 0, 1, 1, 0, 1, 0, 0, 1, (Continued on next slide), , Slide 74/78

Page 75 :
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

Page 76 :
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, B, , A ⋅B ⋅ D, , D, , A, B, D, , A ⋅B ⋅ D, , S, A, B, D, , A ⋅B ⋅ D, , A, B, , A ⋅B ⋅ D, , D, , (a) Logic circuit diagram for sums, (Continued on next slide), , Ref. Page 95, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 76/78

Page 77 :
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

Page 78 :
Computer, Computer Fundamentals:, Fundamentals: Pradeep, Pradeep K., K. Sinha, Sinha &, & Priti, Priti Sinha, Sinha, , Key Words/Phrases, §, §, §, §, §, §, §, §, §, §, §, §, §, §, §, , Absorption law, AND gate, Associative law, Boolean algebra, Boolean expression, Boolean functions, Boolean identities, Canonical forms for, Boolean functions, Combination logic, circuits, Cumulative law, Complement of a, function, Complementation, De Morgan’s law, Distributive law, Dual identities, , Ref. Page 97, , § Equivalence function, § Exclusive-OR function, § Exhaustive enumeration, method, § Half-adder, § Idempotent law, § Involution law, § Literal, § Logic circuits, § Logic gates, § Logical addition, § Logical multiplication, § Maxterms, § Minimization of Boolean, functions, § Minterms, § NAND gate, , §, §, §, §, §, §, §, §, §, §, §, §, §, , NOT gate, Operator precedence, OR gate, Parallel Binary Adder, Perfect induction, method, Postulates of Boolean, algebra, Principle of duality, Product-of-Sums, expression, Standard forms, Sum-of Products, expression, Truth table, Universal NAND gate, Universal NOR gate, , Chapter 6: Boolean Algebra and Logic Circuits, , Slide 78/78