Boolean Algebra and Logic Gate - Ajloun National PDF

DIGITAL LOGIC DESIGN Boolean Algebra and Logic Gate Course Instructor Dr. Issa Alsmadi 1 Algebr as What is an algebra? ◦Mathematical system consisting of ◦ Set of elements ◦ Set of operators ◦ Axioms or postu...

DIGITAL LOGIC DESIGN Boolean Algebra and Logic Gate Course Instructor Dr. Issa Alsmadi 1 Algebr as What is an algebra? ◦Mathematical system consisting of ◦ Set of elements ◦ Set of operators ◦ Axioms or postulates Why is it important? ◦Defines rules of “calculations” Example: arithmetic on natural numbers ◦Set of elements: N = {1,2,3,4,…} ◦Operator: +, –, * ◦Axioms: associativity, distributivity, closure, identity elements, etc. Note: operators with two inputs are called binary ◦Does not mean they are restricted to binary numbers! ◦Operator(s) with one input are called unary 2  BASIC DEFINITIONS A set is collection of elements having the same property. ◦ S: set, x and y: element or event ◦ For example: S = {1, 2, 3, 4} ◦ If x = 2, then xS. ◦ If y = 5, then y S. A binary operator defines on a set S of elements is a rule that assigns, to each pair of elements from S, a unique element from S. ◦ For example: given a set S, consider a*b = c and * is a binary operator. ◦ If (a, b) through * get c and a, b, cS, then * is a binary operator of S. ◦ On the other hand, if * is not a binary operator of S and a, bS, then c  S. 3  BASIC DEFINITIONS The most common postulates used to formulate various algebraic structures are as follows: 1.Closure: a set S is closed with respect to a binary operator if, for every pair of elements of S, the binary operator specifies a rule for obtaining a unique element of S. ◦ For example, natural numbers N={1,2,3,...} is closed w.r.t. the binary operator + by the rule of arithmetic addition, since, for any a, bN, there is a unique cN such that ◦ a+b = c ◦ But operator – is not closed for N, because 2-3 = -1 and 2, 3 N, but (-1)N. 2.Associative law: a binary operator * on a set S is said to be associative whenever ◦ (x * y) * z = x * (y * z) for all x, y, zS ◦ (x+y)+z = x+(y+z) 3.Commutative law: a binary operator * on a set S is said to be commutative whenever ◦ x * y = y * x for all x, yS ◦ x+y = y+x 4  BASIC DEFINITIONS 4. Identity element: a set S is said to have an identity element with respect to a binary operation * on S if there exists an element eS with the property that ◦ e * x = x * e = x for every xS ◦ 0+x = x+0 =x for every xI. I = {…, -3, -2, -1, 0, 1, 2, 3, …}. ◦ 1*x = x*1 =x for every xI. I = {…, -3, -2, -1, 0, 1, 2, 3, …}. 5. Inverse: a set having the identity element e with respect to the binary operator to have an inverse whenever, for every xS, there exists an element yS such that ◦x * y = e ◦ The operator + over I, with e = 0, the inverse of an element a is (-a), since a+(-a) = 0. 6. Distributive law: if * and ． are two binary operators on a set S, * is said to be distributive over. whenever ◦ x * (y ． z) = (x * y) ． (x * z) 5  Axiomatic Definition of Boolean Algebra We need to define algebra for binary values ◦Developed by George Boole in 1854 Huntington postulates for Boolean algebra (1904): B = {0, 1} and two binary operations, + and · ◦Closure with respect to operator + and operator · ◦Identity element 0 for operator + and 1 for operator · ◦Commutativity with respect to + and · x+y = y+x, x·y = y·x ◦Distributivity of · over +, and + over · x·(y+z) = (x·y)+(x·z) and x+(y·z) = (x+y)·(x+z) ◦ Complement for every element x is x’ with x+x’=1, x·x’=0 7 ◦There are at least two elements x,yB such  Boolean Algebra Terminology: ◦ Literal: A variable or its complement ◦ Product term: literals connected by ◦ Sum term: literals connected by + 8  Postulates of Two-Valued Boolean Algebra B = {0, 1} and two binary operations, + and ． The rules of operations: AND 、 OR and NOT. AND OR NOT x y x．y x y x+y x x' 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1.Closure (+ and‧) 2.The identity elements (1) + : 0 (2) ． : 1 9 Postulates of Two-Valued Boolean 3. The commutative Algebra laws 4. The distributive laws x y z y+z x． x ． y x ． z (x ． y)+(x ． (y+z) z) 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 10 Postulates of Two-Valued Boolean 5. Complement Algebra ◦ x + x'=1 → 0 + 0'=0 + 1=1; 1 + 1'=1 + 0=1 ◦ x. x'=0 → 0. 0'=0. 1=0; 1. 1'=1. 0=0 6. Has two distinct elements 1 and 0, with 0 ≠ 1 Note ◦ A set of two elements ◦ + : OR operation; ． : AND operation ◦ A complement operator: NOT operation ◦ Binary logic is a two-valued Boolean algebra 11  Duality The principle of duality is an important concept. This says that if an expression is valid in Boolean algebra, the dual of that expression is also valid. To form the dual of an expression, replace all + operators with. operators, all. operators with + operators, all ones with zeros, and all zeros with ones. Form the dual of the expression a + (bc) = (a + b)(a + c) Following the replacement rules… a(b + c) = ab + ac Take care not to alter the location of the parentheses if they are present. 12  Basic Theorems 13  Boolean Theorems Huntington’s postulates define some rules Post. 1: closure Post. 2: (a) x+0=x, (b) x·1=x Post. 3: (a) x+y=y+x, (b) x·y=y·x Post. 4: (a) x(y+z) = xy+xz, (b) x+yz = (x+y)(x+z) Need more rules to Post. 5: (a) x+x’=1, (b) x·x’=0 modify algebraic ◦ Theorems that are derived from postulates expressions What is a theorem? ◦A formula or statement that is derived from postulates (or other proven theorems) Basic theorems of Boolean algebra ◦Theorem 1 (a): x + x = x (b): x · x=x ◦Looks straightforward, but needs to be proven ! 14  Proof of x+x=x We can only use Huntington Huntington postulates: postulates: Post. 2: (a) x+0=x, (b) x·1=x Post. 3: (a) x+y=y+x, (b) x·y=y·x Post. 4: (a) x(y+z) = xy+xz, Show that (b) x+yz = (x+y)(x+z) Post. 5: (a) x+x’=1, (b) x·x’=0 x+x=x. x = (x+x)·1 by + 2(b) by x = (x+x) 5(a) (x+x’) by = x+xx’ 4(b) = x+0 by =x 5(b) We can now use Theorem 1(a) Q.E.D. by in future proofs 2(a) 15  Proof of x·x=x Similar to previous proof Huntington postulates: Post. 2: (a) x+0=x, (b) x·1=x Post. 3: (a) x+y=y+x, (b) x·y=y·x Post. 4: (a) x(y+z) = xy+xz, (b) x+yz = (x+y)(x+z) Post. 5: (a) x+x’=1, (b) x·x’=0 Th. 1: (a) x+x=x Show that x·x = x. x·x = by xx+0 2(a) = xx+xx’ by 5(b) = x(x+x’) by 4(a) =Q.E. x·1 by D. 5(a) =x by 2(b) 16  Proof of x+1=1 Theorem 2(a): x + 1 Huntington postulates: =1 Post. 2: (a) x+0=x, (b) x·1=x x+1= =(x1． (x + + + x')(x 1) 5(a) Post. 3: (a) x+y=y+x, (b) x·y=y·x 1) by Post. 4: (a) x(y+z) = xy+xz, = x + x' 1 4(b) 2(b) (b) x+yz = (x+y)(x+z) = x + x' 2(b) Post. 5: (a) x+x’=1, (b) x·x’=0 =1 5(a) Th. 1: (a) x+x=x Theorem 2(b): x ． 0 = 0 by duality Theorem 3: (x')' ◦Postulate 5 defines the complement of x, x + x' = =x 1 and x x' = 0 ◦The complement of x' is x is also (x')' 17  Absorption Property (Covering) The rem 6(a): x = x Huntington postulates: o + xy by 2(b) ◦ x + xy = x ． 1 4(a) Post. 2: (a) x+0=x, (b) x·1=x + xy 3(a) Post. 3: (a) x+y=y+x, (b) x·y=y·x = x (1 + y) = x (y + 1) = x．1 Th 2(a) Post. 4: (a) x(y+z) = xy+xz, =x 2(b) (b) x+yz = (x+y)(x+z) Theorem 6(b): x (x + y) = x by Post. 5: (a) x+x’=1, (b) x·x’=0 duality Th. 1: (a) x+x=x By means of truth table (another way to proof ) x y xy x+xy 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 18  DeMorgan’s Theorem Theorem 5(a): (x + y)’ = x’y’ Theorem 5(b): (xy)’ = x’ + y’ By means of truth table x y x’ y’ x+y (x+y)’ x’y’ xy x’+y' (xy)’ 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 19  Consensus Theorem 1. xy + x’z + yz = xy + x’z 2. (x+y) (x’+z) (y+z) = (x+y) (x’+z) -- (dual) Proof: xy + x’z + yz = xy + x’z + (x+x’)yz = xy + x’z + xyz + x’yz = (xy + xyz) + (x’z + x’zy) = xy + x’z QED (2 true by duality). 20  Operator Precedence The operator precedence for evaluating Boolean Expression is ◦Parentheses ◦NOT ◦AND ◦OR Examples ◦ x y' + z ◦ (x y + z)' 21 Boolean Functions A Boolean function ◦Binary variables ◦Binary operators OR and AND ◦Unary operator NOT ◦Parentheses Examples ◦ F1= x y z' ◦ F2 = x + y'z ◦ F3 = x' y' z + x' y z + x y' ◦ F4 = x y' + x' z 22  Boolean Functions 🞕 The truth table of 2 n entries x y z F1 F2 F3 F4 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 0 Two Boolean expressions may specify the same function ◦ F3 = F4 23  Boolean Functions Implementation with logic gates ◦ F4 is more economical F2 = x + y'z F3 = x' y' z + x' y z + x y' F4 = x y' + x' z 24  Algebraic Manipulation To minimize Boolean expressions ◦Literal: a primed or unprimed variable (an input to a gate) ◦Term: an implementation with a gate ◦The minimization of the number of literals and the number of terms → a circuit with less equipment ◦It is a hard problem (no specific rules to follow) Example 2.1 1.x(x'+y) = xx' + xy = 0+xy = xy 2.x+x'y = (x+x')(x+y) = 1 (x+y) = x+y 3.(x+y)(x+y') = x+xy+xy'+yy' = x(1+y+y') = x 4.xy + x'z + yz = xy + x'z + yz(x+x') = xy + x'z + yzx + yzx' = xy(1+z) + x'z(1+y) = xy +x'z 5.(x+y)(x'+z)(y+z) = (x+y)(x'+z), by duality from function 4. (consensus theorem with duality) 25  Complement of a Function An interchange of 0's for 1's and 1's for 0's in the value ofF ◦By DeMorgan's (A+B+C)' = theorem (A+X)' = A'X' = A'(B+C)' = A'(B'C') = A'B'C' Generalizations: a function is obtained by interchanging AND and OR operators and complementing each literal. ◦(A+B+C+D+... +F)' = A'B'C'D'... F' ◦(ABCD... F)' = A'+ B'+C'+D'... +F' 26  Examples Example 2.2 ◦ F1' = (x'yz' + x'y'z)' = (x'yz')' (x'y'z)' = (x+y'+z) (x+y+z') ◦ F2' = [x(y'z'+yz)]' = x' + (y'z'+yz)' = x' + (y'z')' (yz)‘ = x' + (y+z) (y'+z') = x' + yz‘+y'z Example 2.3: a simpler procedure ◦ Take the dual of the function and complement each literal 1.F1 = x'yz' + x'y'z. The dual of F1 is (x'+y+z') (x'+y'+z). Complement each literal: (x+y'+z)(x+y+z') = F1' 2.F2 = x(y' z' + yz). The dual of F2 is x+(y'+z') (y+z). Complement each literal: x'+(y+z)(y' +z') = F2 ' 27 2.6 Canonical and Standard Forms Minterms and Maxterms A minterm (standard product): an AND term consists of all literals in their normal form or in their complement form. ◦For example, two binary variables x and y, ◦ xy, xy', x'y, x'y' ◦It is also called a standard product. ◦ n variables con be combined to form 2n minterms. A maxterm (standard sums): an OR term ◦ It is also call a standard sum. ◦ 2n maxterms. 28  Minterms and Maxterms 🞕 Each maxterm is the complement of its corresponding minterm, and vice versa. 29  Minterms and Maxterms An Boolean function can be expressed by ◦A truth table ◦Sum of minterms ◦ f1 = x'y'z + xy'z' + xyz = m1 + m4 +m7 (Minterms) ◦ f2 = x'yz+ xy'z + xyz'+xyz = m3 + m5 +m6 + m7 (Minterms) 30  Minterms and Maxterms The complement of a Boolean function ◦The minterms that produce a 0 ◦ f1' = m0 + m2 +m3 + m5 + m6 = x'y'z'+x'yz'+x'yz+xy'z+xyz' ◦ f1 = (f1')' = (x+y+z)(x+y'+z) (x+y'+z') (x'+y+z')(x'+y'+z) = M0 M2 M3 M5 M6 ◦ f2 = (x+y+z)(x+y+z')(x+y'+z)(x'+y+z)=M0M1M2M4 Any Boolean function can be expressed as ◦ A sum of minterms (“sum” meaning the ORing of terms). ◦ A product of maxterms (“product” meaning the ANDing of terms). ◦ Both boolean functions are said to be in Canonical form. 31  Sum of Minterms Sum of minterms: there are 2n minterms and 22n combinations of function with n Boolean variables. Example 2.4: express F = A+BC' as a sum of minterms. ◦ F = A+B'C = A (B+B') + B'C = AB +AB' + B'C = AB(C+C') + AB'(C+C') + (A+A')B'C = ABC+ABC'+AB'C+AB'C'+A'B'C ◦ F = A'B'C +AB'C' +AB'C+ABC'+ ABC = m1 + m4 +m5 + m6 + m7 ◦ F(A, B, C) = (1, 4, 5, 6, 7) ◦ or, built the truth table first 32  Product of Maxterms Product of maxterms: using distributive law to expand. ◦ x + yz = (x + y)(x + z) = (x+y+zz')(x+z+yy') = (x+y+z)(x+y+z')(x+y'+z) Example 2.5: express F = xy + x'z as a product of maxterms. ◦ F = xy + x'z = (xy + x')(xy +z) = (x+x')(y+x')(x+z) (y+z) = (x'+y)(x+z)(y+z) ◦ x'+y = x' + y + zz' = (x'+y+z)(x'+y+z') ◦ F = (x+y+z)(x+y'+z)(x'+y+z)(x'+y+z') = M0M2M4M5 ◦ F(x, y, z) = (0, 2, 4, 5) 33  Conversion between Canonical Forms The complement of a function expressed as the sum of minterms equals the sum of minterms missing from the original function. ◦ F(A, B, C) = (1, 4, 5, 6, 7) ◦ Thus, F'(A, B, C) = (0, 2, 3) ◦ By DeMorgan's theorem F(A, B, C) = (0, 2, 3) F'(A, B, C) = (1, 4, 5, 6, 7) ◦ mj' = Mj ◦ Sum of minterms = product of maxterms ◦ Interchange the symbols  and  and list those numbers missing from the original form ◦  of 1's ◦  of 0's 34 Examp le ◦ F = xy + xz ◦ F(x, y, z) = (1, 3, 6, 7) ◦ F(x, y, z) =  (0, 2, 4, 6) 35  Standard Forms Canonical forms are very seldom the ones with the least number of literals. Standard forms: the terms that form the function may obtain one, two, or any number of literals. ◦Sum of products: F1 = y' + xy+ x'yz' ◦Product of sums: F2 = x(y'+z)(x'+y+z') ◦ F3 = A'B'CD+ABC'D' 36  Implementation Two-level implementation F1 = y' + xy+ x'yz' F2 = x(y'+z)(x'+y+z') Multi-level implementation 37  2.7 Other Logic Operations 2n rows in the truth table of n binary variables. 22n functions for n binary variables. 16 functions of two binary variables. All the new symbols except for the exclusive-OR symbol are not in common use by digital designers. 38 Boolean Expressions 39  2.8 Digital Logic Gates Boolean expression: AND, OR and NOT operations Constructing gates of other logic operations ◦The feasibility and economy; ◦The possibility of extending gate's inputs; ◦The basic properties of the binary operations (commutative and associative); ◦The ability of the gate to implement Boolean functions. 40  Standard Gates Consider the 16 functions in Table 2.8 (slide 33) ◦Two are equal to a constant (F0 and F15). ◦Four are repeated twice (F4, F5, F10 and F11). ◦Inhibition (F2) and implication (F13) are not commutative or associative. ◦The other eight: complement (F12), transfer (F3), AND (F1), OR (F7), NAND (F14), NOR (F8), XOR (F6), and equivalence (XNOR) (F9) are used as standard gates. ◦Complement: inverter. ◦Transfer: buffer (increasing drive strength). ◦Equivalence: XNOR. 41 Summary of Logic Gates Figure 2.5 Digital logic gates 42 Summary of Logic Gates Figure 2.5 Digital logic gates 43  Multiple Inputs Extension to multiple inputs ◦A gate can be extended to multiple inputs. ◦ If its binary operation is commutative and associative. ◦AND and OR are commutative and associative. ◦ OR ◦ x+y = y+x ◦ (x+y)+z = x+(y+z) = x+y+z ◦ AND ◦ xy = yx ◦ (x y)z = x(y z) = x y z 44  Multiple Inputs ◦NAND and NOR are commutative but not associative → they are not extendable. Figure 2.6 Demonstrating the nonassociativity of the NOR operator; (x ↓ y) ↓ z ≠ x ↓(y ↓ z) 45  Multiple Inputs ◦Multiple NOR = a complement of OR gate, Multiple NAND = a complement of AND. ◦The cascaded NAND operations = sum of products. ◦The cascaded NOR operations = product of sums. Figure 2.7 Multiple-input and cascated NOR and NAND gates 46  Multiple Inputs ◦The XOR and XNOR gates are commutative and associative. ◦Multiple-input XOR gates are uncommon? ◦XOR is an odd function: it is equal to 1 if the inputs variables have an odd number of 1's. Figure 2.8 3-input XOR gate 47  Positive and Negative Logic Positive and Negative Logic ◦Two signal values two logic values ◦Positive logic: H=1; L=0 ◦Negative logic: H=0; L=1 Consider a TTL gate ◦A positive logic AND gate ◦A negative logic OR gate ◦The positive logic is used in this book Figure 2.9 Signal assignment and logic polarity 48  Positive and Negative Logic Figure 2.10 Demonstration of positive and negative logic 49