Boolean algebra Last time we talked about Boolean functions Boolean expressions and truth tables Today we ll learn how to how use Boolean algebra to simplify Booleans expressions Last time we saw this expression and converted it to a circuit x y z x June 11 2002 2000 2002 Howard Huang 1 Simplifying circuits The expression and circuit on the previous page are actually equivalent to the simplified ones below x z Simpler hardware is always better In many cases the simpler circuit is also faster Less hardware means smaller size which also reduces costs Simpler circuits draw less power How do we know this circuit is the same as the one on the last page June 11 2002 Boolean algebra 2 Boolean algebra is special Boolean algebra gives us a way to simplify Boolean functions much like regular algebra allows us to simplify mathematical functions The AND and OR operations are similar to multiplication and addition AND is the same as multiplication for the values 0 and 1 OR is almost the same as addition except for 1 1 x y xy x y x y 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 But there are important differences to watch out for too Boolean algebra uses are only two values OR is not quite the same as addition and NOT is a new operation June 11 2002 Boolean algebra 3 Formal definition of Boolean algebra A Boolean algebra requires A set of values B which contains at least two elements 0 and 1 Two 2 argument operations and A one argument operation The values and operations must satisfy the axioms below 1 3 5 7 9 10 12 14 16 x 0 x x 1 1 x x x x x 1 x x x y y x x y z x y z x y z xy xz x y x y June 11 2002 2 4 6 8 11 13 15 17 x x x x 1 x 0 0 x x x 0 xy yx x yz xy z x yz x y x z xy x y Boolean algebra Commutative Associative Distributive DeMorgan s 4 Satisfying the axioms The operations we chose do satisfy all of the axioms We can show this by looking at the definitions of our operations x y xy 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 For example the axiom x x 1 is satisfied because We have only two possible values for x 0 and 1 The complement of these values are 1 and 0 respectively 0 1 1 and 1 0 1 x x x x June 11 2002 0 1 1 1 0 1 Boolean algebra 5 Proofs with truth tables We can always prove equivalences using truth tables to explicitly show that two expressions always produce the same results Let s use truth tables to prove DeMorgan s law x y x y The columns on the left in each table are the inputs We have two inputs x and y so there are four possible input combinations The columns on the right in blue are outputs Intermediate columns can be useful in deriving the outputs x y x y x y x y x y x y 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 0 0 Since both of the columns in blue are the same this shows that x y and x y really are equivalent June 11 2002 Boolean algebra 6 Similarities with regular algebra Several of the axioms in blue look just like regular algebraic rules The associative laws show that there is no ambiguity in a term such as xyz or x y z so we can use multiple input primitive gates 1 3 5 7 9 10 12 14 16 x 0 x x 1 1 x x x x x 1 x x x y y x x y z x y z x y z xy xz x y x y June 11 2002 2 4 6 8 11 13 15 17 x x x x 1 x 0 0 x x x 0 xy yx x yz xy z x yz x y x z xy x y Boolean algebra Commutative Associative Distributive DeMorgan s 7 The complement operation The magenta axioms deal with the complement operation which doesn t exist in normal algebra Most of them almost make sense if you translate them into English It is raining or it is not raining is always true x x 1 It is raining and it is not raining can never be true x x 0 I am not not handsome means I am handsome x x 1 3 5 7 9 10 12 14 16 x 0 x x 1 1 x x x x x 1 x x x y y x x y z x y z x y z xy xz x y x y June 11 2002 2 4 6 8 11 13 15 17 x x x x 1 x 0 0 x x x 0 xy yx x yz xy z x yz x y x z xy x y Boolean algebra Commutative Associative Distributive DeMorgan s 8 DeMorgan s DeMorgan s axioms are especially important for circuit design x y x y xy x y We ve already proved one of these axioms but here are some rough examples in English I am not rich or famous This is the same as I am not rich and I am not famous In other words I am nothing I am not old and bald This is equivalent to I am not old or I am not bald I could still be one of the other three possibilities young and bald old and hairy or young and hairy June 11 2002 Boolean algebra 9 Other differences with regular algebra Finally the red axioms are completely different from regular algebra The first three make sense if you think about it logically Blah or true is always true even if blah is false x 1 1 I am handsome or I am handsome is redundant x x x I am handsome and I am handsome is redundant x x x The last one x yz x y x z is the trickiest one of the bunch 1 x 0 x 2 x 1 x 3 5 7 9 10 12 14 16 x 1 1 x x x x x 1 x x x y y x x y z x y z x y z xy xz x y x y June 11 2002 4 x 0 0 6 x x x 8 x x 0 11 13 15 17 xy yx x yz xy z x yz x y x z xy …
View Full Document
Unlocking...