Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 91Lecture #2 EGR 270 – Fundamentals of Computer EngineeringChapter 2 - Boolean Algebra - comparison to regular algebra Any algebra is built upon:1) A set of elements2) A set of operators3) A set of postulatesBoolean Algebra is built upon:1) A set of elements: {0, 1}2) A set of operators: {+, • } – Define these in class3) A set of postulates: the Huntington Postulates are the most commonHuntington Postulates – The following 6 postulates, along with the set of elements and set of operators shown above, uniquely and completely define Boolean algebra.1) Closure for the operations {+, • } - DiscussReading Assignment: Chapter 2 in Logic and Computer Design Fundamentals, 4th Edition by Mano22) Two identity elements: - Illustrate by considering all possible values for x A) 0: 0 + x = x + 0 = x B) 1: 1 • x = x • 1 = x3) Commutative Laws: - Illustrate by considering all possible values for x and y A) x + y = y + x B) xy = yx4) Distributive Laws: - Prove by truth table A) x • (y + z) = xy + xz B) x + yz = (x + y) • (x + z)Lecture #2 EGR 270 – Fundamentals of Computer Engineering35) Existence of a Complement: - Illustrate by considering all possible values for x Define by the following truth table:x' = x = "the complement of x" = "NOT x"x x’0 11 0 A) x + x’ = 1 B) x • x’ = 06) At least two non-equal elements: {0, 1} - DiscussCommon TheoremsBoolean algebra has already been completely defined. Additional theorems are also often used, not because they are required, but because they are useful. Some of the most common theorems are shown below. Note that each theorem could be formally proven using the postulates.1) Idempotency: (“same power”) A) x + x = x – Prove this using the postulates B) x • x = xExample: Show related examples using this theorem.Lecture #2 EGR 270 – Fundamentals of Computer Engineering42) (no name) – Discuss A) x + 1 = 1 B) x • 0 = 03) Involution: – Discuss x’’ = = x4) Associative Laws: – Discuss (show logic gate application) A) x + (y + z) = (x + y) + z B) x(yz) = (xy)z5) DeMorgan’s Theorems: - Prove 5A by truth table A) B) Example: Show related examples using DeMorgan’s theorem.x + y = x y-x y = xy = x y- Lecture #2 EGR 270 – Fundamentals of Computer Engineering56) Absorption: A) x + xy = x B) x (x+y) = xExample: Show related examples using this theorem.7) (no name) A) x + x’y = x + y B) x (x’ + y) = xy Example: Show related examples using this theorem.8) Concensus: A) xy + x’z + yz = xy + x’z B) (x + y)(x’ + z)( y + z) = (x + y)(x’ + z) Example: Show related examples using this theorem.Lecture #2 EGR 270 – Fundamentals of Computer Engineering6Order of operations Example: f = a-b+c-d Note: spacing is often used to make it clearer: f = ab + cdOperation PrecedenceParentheses HigherNOT -AND -OR LowerBoolean Functions – Simplifying Boolean functions corresponds to minimizing the amount of circuitry (logic gates) to be used.Truth table  Boolean function  minimized with Boolean algebra  implement with logic circuitsMinimizing Boolean functionsNo specific rules. In general we use Boolean algebra (postulates and theorems) to reduce the number of terms, literals, logic gates, or IC’s.Literal – a primed (complemented) or unprimed variable. In counting literals, we count all occurrences of each literal.Example: How many literals are in the expression f = ab + a’c + bc’d ? (Answer: 7)Lecture #2 EGR 270 – Fundamentals of Computer Engineering7Examples – Minimize the following Boolean functions: 1) F = AB + A(B + C) + B(B + C) 2) F = AB’(C + BD) + A’B’3) F(A,B,C,D) = A + A’BC + C’Lecture #2 EGR 270 – Fundamentals of Computer Engineering8Examples – Minimize the following Boolean functions (continued): 4) F = [(x’y)’ + z’]’ 5)CD) ABF)(E (CD AB F Lecture #2 EGR 270 – Fundamentals of Computer Engineering9Examples – Minimize the following Boolean functions (continued): 6) f(x,y,z) = x’y(z + y’x) + y’z 7)ca dcb dcb c)b(aba d)c,b,f(a, Lecture #2 EGR 270 – Fundamentals of Computer