Boolean Algebra  and Logic circuits

Boolean Algebra and Logic circuits

Project Type: Presentation (pptx)

Downloads: 0 - 10 Wednesday 12th April 2017 Report

Boolean Algebra and Logic circuits - Overview

------------ PAGE 1 ------------ Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 18 Boo l ea n A lge bra a n d '=' Lo gi c circuits Compu te r Fu n da me n t a ls ------------ PAGE 2 ------------ Computer Fundamentals: A. H. M. Saiful Islam Learning Objectives In this chapter you will learn about: Boolean algebra Fundamental concepts and basic laws algebra Boolean function and minimization Logic gates • • of Boolean • • • • Logic circuits and Boolean expressions Combinational circuits and design 60 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 2/ 78 ------------ PAGE 3 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 60 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 3/ 78 ------------ PAGE 4 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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. multiplication • Complementation Follows law of binary • Symbol ‘ - ’ , also known as ‘ NOT ’ operator, used for complementation. Follows law of binary compliment 61 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 4/ 78 ------------ PAGE 5 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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) 62 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 5/ 78 ------------ PAGE 6 ------------ Computer Fundamentals: A. H. M. Saiful Islam Precedence Operator ( Continued from previous slide..) 1 st 2 nd 3 rd 62 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 6/ 78 X Y Z ------------ PAGE 7 ------------ Computer Fundamentals: A. H. M. Saiful Islam Postulates of Boolean Algebra Postulate 1: ( a) ( b) A = 0, if and only if, A is not A = 1, if and only if, A is not equal equal to to 1 0 Postulate 2: 0 = x 1 = x ( a) ( b) x x Postulate 3: Commutative Law ( a) ( b) x x y = y y = y x x ( Continued on next slide) 62 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 7/ 78 ------------ PAGE 8 ------------ Computer Fundamentals: A. H. M. Saiful Islam Postulates of Boolean Algebra ( Continued from previous slide..) Postulate 4: Associative Law ( a) ( b) x x ( y ( y z) = ( x z) = ( x y) z z y) Postulate 5: Distributive Law ( x ( x ( a) ( b) x x ( y ( y z) = z) = ( x ( x y) y) z) z) Postulate 6: x ( a) ( b) x x = 1 = 0 x 62 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 8/ 78 ------------ PAGE 9 ------------ Computer Fundamentals: A. H. M. Saiful Islam The Principle of Duality There is a precise duality between the operators ( OR), and the digits 0 and 1. . ( AND) and For example, in the table below, the second row is obtained from the and first row and ‘ 0 ’ wit h ‘ 1’ vice versa simply by interchanging ‘ ’ with ‘.’ Therefore, if a particular theorem is proved, its dual theorem automatically holds and need not be proved separately 63 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 9/ 78 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 ------------ PAGE 10 ------------ Computer Fundamentals: A. H. M. Saiful Islam Some Important Theorems of Boolean Algebra 63 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 10/ 78 Sr. No. Theorems/ Identities Dual Theorems/ Identities Name ( 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 ------------ PAGE 11 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 proof already proved theorem is derived from the of its corresponding pair 63 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 11/ 78 ------------ PAGE 12 ------------ Computer Fundamentals: A. H. M. Saiful Islam Proving a Theorem ( Example) by Using Postulates Theorem: x x · y = x Proof: L. H. S. = = = = = = = x x x x x x x 1 ( 1 ( y 1 y x y) 1) y by by by by by postulate postulate postulate 2( b) 5( a) 3( a) theorem 2( a) postulate 2( b) R. H. S. 64 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 12/ 78 ------------ PAGE 13 ------------ Computer Fundamentals: A. H. M. Saiful Islam Proving a Theorem ( Example) Theorem: by Perfect Induction x x · y = x = 64 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 13/ 78 x y x · y x x · y 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 ------------ PAGE 14 ------------ Computer Fundamentals: A. H. M. Saiful Islam by the ( Example) Proving a Theorem Principle of Duality Theorem: x x = x Proof: L. H. S. = = = = = = = x ( x ( x x x x x x) x) 1 ( x by by by by by postulate postulate postulate postulate postulate 2( b) 6( a) 5( b) 6( b) 2( a) X ) x 0 X R. H. S. ( Continued on next slide) 63 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 14/ 78 ------------ PAGE 15 ------------ Computer Fundamentals: A. H. M. Saiful Islam by the ( Example) Proving a Theorem Principle of Duality ( Continued from previous slide..) Dual Theorem: x x = x Proof: L. H. S. = = = = = = = x x x x x x x x x ( x 1 Notice that each step of the proof of the dual theorem is derived from the proof of its corresponding pair in the original theorem 0 x by by by by by postulate postulate postulate postulate postulate 2( a) 6( b) 5( a) 6( a) 2( b) X X ) R. H. S. 63 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 15/ 78 ------------ PAGE 16 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 • 67 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 16/ 78 ------------ PAGE 17 ------------ Computer Representation as an Algebraic Expression Fundamentals: A. H. M. Saiful Islam 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 one a given Boolean function, algebraic expressions there may be more than 67 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 17/ 78 ------------ PAGE 18 ------------ Computer Fundamentals: A. H. M. Saiful Islam Representation as a Truth Table ( Continued on next slide) 67 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 18/ 78 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 ------------ PAGE 19 ------------ Computer Fundamentals: A. H. M. Saiful Islam Representation as a Truth Table ( Continued from previous slide..) • The n is number of rows in the table is equal to 2 n , where the number of literals in the function • The are combinations of 0s and 1s for rows of this table obtained from 1 the binary numbers by counting from 0 to 2 n - 67 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 19/ 78 ------------ PAGE 20 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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) 68 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 20/ 78 ------------ PAGE 21 ------------ Computer Fundamentals: A. H. M. Saiful Islam Minimization of Boolean ( Continued from previous slide..) Functions F 1 = x y z x y z x y F 1 has 3 literals ( x, y, z) and 3 terms F = x y x z 2 F 2 has 3 literals ( x, y, z) and 2 terms F 2 can be realized with fewer electronic components, resulting in a cheaper circuit ( Continued on next slide) 68 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 21/ 78 ------------ PAGE 22 ------------ Computer Fundamentals: A. H. M. Saiful Islam Minimization ( Continued from previous slide..) of Boolean Functions Both F 1 and F 2 produce the same result 68 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 22/ 78 x y z F 1 F 2 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 ------------ PAGE 23 ------------ Computer Fundamentals: A. H. M. Saiful Islam Try out some Minimization Boolean Function ( a ) ( b ) ( c ) ( d ) ( e ) x x x y y x x x x y y z x z y z x y x y z z y x y z 69 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 23/ 78 ------------ PAGE 24 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 1 A 2 A 3 ... A n = A 1 A 2 A 3 ... A n A 1 A 2 A 3 ... A n = A 1 A 2 A 3 ... A n 70 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 24/ 78 ------------ PAGE 25 ------------ Computer Fundamentals: A. H. M. Saiful Islam Complementing a Boolean Function ( Example) F 1 = x y z x y z To obtain F 1 , we first interchange the OR and the AND operators giving x y z x y z Now we complement each literal giving F 1 = x y z x y z 71 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 25/ 78 ------------ PAGE 26 ------------ Computer Fundamentals: A. H. M. Saiful Islam Canonical Forms of Boolean Functions Minterms : n variables forming an AND term, with each variable being primed or unprimed, provide 2 n possible combinations called minterms or standard products Maxterms : n variables forming an OR term, with each variable being primed or unprimed, provide 2 n possible combinations called maxterms or standard sums 71 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 26/ 78 ------------ PAGE 27 ------------ Computer Fundamentals: A. H. M. Saiful Islam Minterms and Maxterms for three Variables 7 7 Note that each minterm is the complement of its corresponding maxterm and vice- versa 71 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 27/ 78 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 x y z M ------------ PAGE 28 ------------ Computer Fundamentals: A. H. M. Saiful Islam Sum- of- Products ( SOP) Expression A sum- of- products ( SOP) expression is a product term ( minterm) or several product terms ( minterms) are: logically added ( ORed) together. Examples x x y x y z x x y z x y x y y x y z 72 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 28/ 78 ------------ PAGE 29 ------------ Computer Fundamentals: A. H. M. Saiful Islam Steps to Express a Boolean Function in its Sum- of- Products Form 1. Construct a function truth table for the given Boolean 2. Form a minterm for each combination of the variables, which produces a 1 in the function 3. The desired expression is the 2 sum ( OR) of all the minterms obtained in Step 72 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 29/ 78 ------------ PAGE 30 ------------ Computer Fundamentals: A. H. M. Saiful Islam Expressing a Function in its Sum- of- Products Form ( Example) The following 001, 3 combinations of the variables produce a 1: 100, and 111 ( Continued on next slide) 73 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 30/ 78 x y z F 1 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 ------------ PAGE 31 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 F 1 = x y z x y z x y z = m 1 m 4 m 7 F 1 x y z = 1, 4,7 72 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 31/ 78 ------------ PAGE 32 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 y x y x y x x y x y x y z x y z x y x y 74 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 32/ 78 ------------ PAGE 33 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 which produces a 0 in the function of the variables, 3. The desired expression is the product ( AND) of all the maxterms obtained in Step 2 74 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 33/ 78 ------------ PAGE 34 ------------ Computer Fundamentals: A. H. M. Saiful Islam Expressing a Function in its Product- of- Sums Form The following 5 combinations of variables produce a 0: • 000, 010, 011, 101, and 110 ( Continued on next slide) 73 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 34/ 78 x y z F 1 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 ------------ PAGE 35 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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: • F 1 = x y z x y z x y z x y z x y z = M 0 M 2 M 3 M 5 M 6 F 1 x, y, z = Ð 0,2,3,5,6 74 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 35/ 78 ------------ PAGE 36 ------------ = Ó Computer Fundamentals: A. H. M. Saiful Islam Conversion Between Canonical Forms ( Sum- of- Products and Product- of- Sums) To convert from one canonical form to another, missing interchange the symbol and from the original form. list those numbers 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 76 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 36/ 78 ------------ PAGE 37 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 77 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 37/ 78 ------------ PAGE 38 ------------ Computer Fundamentals: A. H. M. Saiful Islam AND Gate • Physical operation realization of logical multiplication ( AND) • Generates an also output 1 signal of 1 only if all input signals are 77 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 38/ 78 ------------ PAGE 39 ------------ Computer Fundamentals: A. H. M. Saiful Islam AND Gate ( Block Table) Diagram Symbol and Truth A B C = A B 77 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 39/ 78 Inputs Output A B C = A B 0 0 0 0 1 0 1 0 0 1 1 1 ------------ PAGE 40 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 77 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 40/ 78 ------------ PAGE 41 ------------ Computer Fundamentals: A. H. M. Saiful Islam OR Gate ( Block Diagram Symbol and Truth Table) A B C = A B 78 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 41/ 78 Inputs Output A B C = A B 0 0 0 0 1 1 1 0 1 1 1 1 ------------ PAGE 42 ------------ Computer Fundamentals: A. H. M. Saiful Islam NOT Gate • Physical realization of complementation operation • Generates an output signal, which is the reverse of the input signal 78 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 42/ 78 ------------ PAGE 43 ------------ Computer Fundamentals: A. H. M. Saiful Islam NOT Gate ( Block Diagram Symbol and Truth Table) A A 79 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 43/ 78 Input Output A A 0 1 1 0 ------------ PAGE 44 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 • 79 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 44/ 78 ------------ PAGE 45 ------------ Computer Fundamentals: A. H. M. Saiful Islam NAND Gate ( Block Diagram Symbol and Truth Table) A B C= A B = A B = A B 79 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 45/ 78 Inputs Output A B C = A B 0 0 1 0 1 1 1 0 1 1 1 0 ------------ PAGE 46 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 • 79 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 46/ 78 ------------ PAGE 47 ------------ Computer Fundamentals: A. H. M. Saiful Islam NOR Gate ( Block Table) Diagram Symbol and Truth A B C= A B = A B = A B 80 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 47/ 78 Inputs Output A B C = A B 0 0 1 0 1 0 1 0 0 1 1 0 ------------ PAGE 48 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 gates be realized as a logic circuit using only these three 80 Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 48/ 78 ------------ PAGE 49 ------------ Computer Fundamentals: A. H. M. Saiful Islam Finding Boolean Expression of a Logic Circuit ( Example 1) A A NOT D= A. B C AND B C OR Ref. Page 80 Chapter 6: Boolean Algebra and Logic Circuits Slide 49/ 78 B C ------------ PAGE 50 ------------ Computer Fundamentals: A. H. M. Saiful Islam Finding Boolean Expression of a Logic Circuit ( Example 2) OR A B A B C= A B A B AND A B NOT AND Ref. Page 81 Chapter 6: Boolean Algebra and Logic Circuits Slide 50/ 78 A B ------------ PAGE 51 ------------ Computer Fundamentals: A. H. M. Saiful Islam Constructing a Logic Circuit from Expression ( Example 1) a Boolean A B C Boolean Expression = AND A B A B A B C C OR Ref. Page 83 Chapter 6: Boolean Algebra and Logic Circuits Slide 51/ 78 ------------ PAGE 52 ------------ Computer Fundamentals: A. H. M. Saiful Islam Constructing a Logic Circuit from a Boolean Expression ( Example 2) Boolean Expression = A B C D E F AND NOT A B A B A B AND AND C D C D A B C D E F AND E F E F E F NOT Ref. Page 83 Chapter 6: Boolean Algebra and Logic Circuits Slide 52/ 78 ------------ PAGE 53 ------------ Computer Fundamentals: A. H. M. Saiful Islam Universal NAND Gate NAND gate is to an universal gate, it any is alone • sufficient expression implement Boolean To understand this, consider: • Basic logic gates ( AND, OR, and logically complete NOT) are • Sufficient to show that AND, OR, and NOT • gates gates can be implemented with NAND Ref. Page 84 Chapter 6: Boolean Algebra and Logic Circuits Slide 53/ 78 ------------ PAGE 54 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 Fundamentals: A. H. M. Saiful Islam Implementation of NOT, NAND Gates ( Continued from previous slide..) AND and OR Gates by A A = A A A B A B A B B ( c) OR gate implementation. Ref. Page 85 Chapter 6: Boolean Algebra and Logic Circuits Slide 55/ 78 B B = B ------------ PAGE 56 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 available ( A) and complement ( A ) inputs are Step 2: Draw a second logic diagram with the equivalent NAND logic substituted for each AND, OR, and NOT gate Step 3: Remove diagram all as pairs double of cascaded inverters from the any inversion does not perform logical single function. Also remove inverters connected to the external inputs and complement corresponding input variable Ref. Page 85 Chapter 6: Boolean Algebra and Logic Circuits Slide 56/ 78 ------------ PAGE 57 ------------ Computer Fundamentals: A. H. M. Saiful Islam Implementing a Boolean NAND Gates ( Example) Expression with Only A B C A B D Boolean Expression = A A B A B C A B D B B D A C 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 Fundamentals: A. H. M. Saiful Islam Implementing a Boolean NAND Gates ( Example) ( Continued from previous slide..) Expression with Only AND OR A B B D A B C A B D A 4 C 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 2 A 1 A B 5 AND OR BD 3 AND A BD ------------ PAGE 59 ------------ Computer Fundamentals: A. H. M. Saiful Islam Implementing a Boolean Expression with Only NAND Gates ( Continued from previous slide..) ( Example) A 1 B A B C A B D 5 B D 2 3 A C 4 ( c) Step 3: NAND implementation. Ref. Page 87 Chapter 6: Boolean Algebra and Logic Circuits Slide 59/ 78 ------------ PAGE 60 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 ------------ PAGE 61 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 Fundamentals: A. H. M. Saiful Islam Implementation of NOT, NOR Gates ( Continued from previous slide..) OR and AND Gates by A A = A A A B A B A B B ( c) AND gate implementation. Ref. Page 89 Chapter 6: Boolean Algebra and Logic Circuits Slide 62/ 78 B B = B ------------ PAGE 63 ------------ Computer Fundamentals: A. H. M. Saiful Islam Method of Implementing a Boolean Expression with Only NOR Gates Step 1: For the given algebraic expression, draw the logic diagram both the available with AND, OR, and NOT gates. Assume that normal and complement A inputs are A Step 2: Draw a second logic substituted for each diagram with equivalent NOR logic AND, OR, and NOT gate Step 3: Remove diagram all parts of cascaded inverters from the any as double inversion does not perform logical single function. Also remove inverters connected to the external inputs and complement corresponding input variable Ref. Page 89 Chapter 6: Boolean Algebra and Logic Circuits Slide 63/ 78 ------------ PAGE 64 ------------ Computer Fundamentals: A. H. M. Saiful Islam Implementing a Boolean Expression NOR Gates ( Examples) ( Continued from previous slide..) with Only A B C A B D Boolean Expression = A A B B A B C A B D B D A C 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 Fundamentals: A. H. M. Saiful Islam Implementing a Boolean Expression with Only NOR Gates ( Continued from previous slide..) ( Examples) AN D A A B 1 OR B A B C A B D 5 6 AN D B B D 2 D OR AN D A 4 C A B D C A B D Substituting equivalent ( b) Step 2: NOR functions. ( Continued on next slide) Ref. Page 90 Chapter 6: Boolean Algebra and Logic Circuits Slide 65/ 78 3 ------------ PAGE 66 ------------ Computer Fundamentals: A. H. M. Saiful Islam Implementing a Boolean Expression with Only NOR Gates ( Continued from previous slide..) ( Examples) A B 1 A B C A B D 6 5 B D A 2 3 4 C ( c) Step 3: NOR implementation. Ref. Page 91 Chapter 6: Boolean Algebra and Logic Circuits Slide 66/ 78 ------------ PAGE 67 ------------ Computer Fundamentals: A. H. M. Saiful Islam Exclusive- OR Function A B = A B A B A B C = 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 Fundamentals: A. H. M. Saiful Islam Exclusive- OR ( Continued from previous slide..) Function ( Truth Table) Ref. Page 92 Chapter 6: Boolean Algebra and Logic Circuits Slide 68/ 78 Inputs Output A B C = A B 0 0 0 0 1 1 1 0 1 1 1 0 ------------ PAGE 69 ------------ ƒn ƒn Computer Fundamentals: A. H. M. Saiful Islam Equivalence Function Symbol with Block Diagram 0 A B = A B A B A B A B A B C = A 0 B = Also, ( A 0 B) 0 = A 0 ( B 0 C) = A 0 B 0 C ( Continued on next slide) Ref. Page 91 Chapter 6: Boolean Algebra and Logic Circuits Slide 69/ 78 ------------ PAGE 70 ------------ Computer Fundamentals: A. H. M. Saiful Islam Equivalence Function ( Truth Table) Ref. Page 92 Chapter 6: Boolean Algebra and Logic Circuits Slide 70/ 78 Inputs Output A B C = A 0 B 0 0 1 0 1 0 1 0 0 1 1 1 ------------ PAGE 71 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 Fundamentals: A. H. M. Saiful Islam Designing a Combinational Circuit Example 1 – Half- Adder Design S = A B A B C = A B Boolean functions for the two outputs. Ref. Page 93 Chapter 6: Boolean Algebra and Logic Circuits Slide 72/ 78 Inputs Outputs A B C S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 ------------ PAGE 73 ------------ Computer Fundamentals: A. H. M. Saiful Islam Designing a Combinational Circuit Example 1 ( Continued from previous slide..) – Half- Adder Design 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 ------------ PAGE 74 ------------ Computer Fundamentals: A. H. M. Saiful Islam Designing a Combinational Circuit Example 2 – Full- Adder Design Truth table for a full adder ( Continued on next slide) Ref. Page 94 Chapter 6: Boolean Algebra and Logic Circuits Slide 74/ 78 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 ------------ PAGE 75 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 = A B D A B D A B D A B D 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 Fundamentals: A. H. M. Saiful Islam Designing a Combinational Circuit Example 2 ( Continued from previous slide..) – Full- Adder Design A A B D B D A B D S A B D A 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 A B D A B D A B D ------------ PAGE 77 ------------ Computer Fundamentals: A. H. M. Saiful Islam Designing a Combinational Circuit Example 2 ( Continued from previous slide..) – Full- Adder Design A B A B A D C A D B D ( b) Logic circuit diagram for carry Ref. Page 95 Chapter 6: Boolean Algebra and Logic Circuits Slide 77/ 78 B D ------------ PAGE 78 ------------ Computer Fundamentals: A. H. M. Saiful Islam 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 • • • 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 • • • • • • • • • • • • • • • • • • • • • • • • • • • Ref. Page 97 Chapter 6: Boolean Algebra and Logic Circuits Slide 78/ 78
Back to top of page