Lecture 2 EGR 270 Fundamentals of Computer Engineering Reading Assignment Chapter 2 in Logic and Computer Design Fundamentals 4th Edition by Mano Chapter 2 Boolean Algebra comparison to regular algebra Any algebra is built upon 1 A set of elements 2 A set of operators 3 A set of postulates Boolean Algebra is built upon 1 A set of elements 0 1 2 A set of operators Define these in class 3 A set of postulates the Huntington Postulates are the most common Huntington 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 Discuss 1 Lecture 2 EGR 270 Fundamentals of Computer Engineering 2 Two identity elements Illustrate by considering all possible values for x A 0 0 x x 0 x B 1 1 x x 1 x 3 Commutative Laws Illustrate by considering all possible values for x and y A x y y x B xy yx 4 Distributive Laws Prove by truth table A x y z xy xz B x yz x y x z 2 Lecture 2 EGR 270 Fundamentals of Computer Engineering 5 Existence of a Complement Illustrate by considering all possible values for x Define x x the complement of x NOT x by the following truth table x x A x x 1 0 1 B x x 0 1 0 6 At least two non equal elements 0 1 Discuss Common Theorems Boolean 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 x Example Show related examples using this theorem 3 Lecture 2 EGR 270 Fundamentals of Computer Engineering 2 no name Discuss A x 1 1 B x 0 0 3 Involution Discuss x x 4 Associative Laws Discuss show logic gate application A x y z x y z B x yz xy z 5 DeMorgan s Theorems Prove 5A by truth table A x y x y B x y xy x y Example Show related examples using DeMorgan s theorem 4 Lecture 2 EGR 270 Fundamentals of Computer Engineering 6 Absorption A x xy x B x x y x Example Show related examples using this theorem 7 no name Example Show related examples using this theorem A x x y x y B x x y xy 8 Concensus Example Show related examples using this theorem A xy x z yz xy x z B x y x z y z x y x z 5 Lecture 2 EGR 270 Fundamentals of Computer Engineering Order of operations Operation Precedence Parentheses Higher NOT AND OR Lower Example f a b c d Note spacing is often used to make it clearer f ab cd Boolean 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 circuits Minimizing Boolean functions No 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 6 Answer 7 Lecture 2 EGR 270 Fundamentals of Computer Engineering Examples 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 7 Lecture 2 EGR 270 Fundamentals of Computer Engineering Examples Minimize the following Boolean functions continued 4 F x y z 5 F AB CD EF AB CD 8 Lecture 2 EGR 270 Fundamentals of Computer Engineering Examples Minimize the following Boolean functions continued 6 f x y z x y z y x y z 7 f a b c d a b a b c b c d b c d a c 9