CS231 Boolean Algebra 1Circuit analysis summary• After finding the circuit inputs and outputs, you can come up with either an expression or a truth table to describe what the circuit does.• You can easily convert between expressions and truth tables.Find the circuit’sinputs and outputsFind a Booleanexpressionfor the circuitFind a truth tablefor the circuitCS231 Boolean Algebra 2Boolean operations summary• We can interpret high or low voltage as representing true or false.• A variable whose value can be either 1 or 0 is called a Boolean variable.• AND, OR, and NOT are the basic Boolean operations.• We can express Boolean functions with either an expression or a truth table.• Every Boolean expression can be converted to a circuit.• Next time, we’ll look at how Boolean algebra can help simplify expressions, which in turn will lead to simpler circuits.CS231 Boolean Algebra 3Expression simplification• Normal mathematical expressions can be simplified using the laws of algebra• For binary systems, we can use Boolean algebra, which is superficially similar to regular algebra• There are many differences, due to– having only two values (0 and 1) to work with– having a complement operation– the OR operation is not the same as additionCS231 Boolean Algebra 4Formal definition of Boolean algebra• A Boolean algebra requires– A set of elements B, which needs at leasttwo elements (0 and 1)– Two binary (two-argument) operations OR and AND– A unary (one-argument) operation NOT– The axioms below must always be true (textbook, p. 33)• The magenta axioms deal with the complement operation• Blue axioms (especially 15) are different from regular algebra1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sCS231 Boolean Algebra 5Comments on the axioms• The associative laws show that there is no ambiguity about a term such as x + y + z or xyz, so we can introduce multiple-input primitive gates:• The left and right columns of axioms are duals– exchange all ANDs with ORs, and 0s with 1s• The dual of anyequation is always true1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sCS231 Boolean Algebra 6Are these axioms for real?• We can show that these axioms are valid, given the definitions of AND, OR and NOT• The first 11 axioms are easy to see from these truth tables alone. For example, x + x’ = 1 because of the middle two lines below (where y = x’)x y xy00 001 010 011 1x y x+y00 001 110 111 1x x’0110x y x+y00 001 110 111 1CS231 Boolean Algebra 7Proving the rest of the axioms• We can make up truth tables to prove (both parts of) DeMorgan’s law• For (x + y)’ = x’y’, we can make truth tables for (x + y)’ and for x’y’• In each table, the columns on the left (x and y) are the inputs. The columns on the right are outputs.• In this case, we only care about the columns in blue. The other “outputs” are just to help us find the blue columns. • Since both of the columns in blue are the same, this shows that (x + y)’ and x’y’ are equivalentx y x + y (x + y)’ x y x’ y’ x’y’00 0 1 00 1 1 101 1 0 01 10 010 1 0 1001 011 1 0 1100 0CS231 Boolean Algebra 8Simplification with axioms• We can now start doing some simplificationsx’y’ + xyz + x’y= x’(y’ + y) + xyz [ Distributive; x’y’ + x’y = x’(y’ + y) ]= x’•1 + xyz [ Axiom 7; y’ + y = 1 ]= x’ + xyz [ Axiom 2; x’•1 = x’ ]= (x’ + x)(x’ + yz) [ Distributive ]= 1 • (x’ + yz) [ Axiom 7; x’ + x = 1 ]= x’ + yz [ Axiom 2 ]1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sCS231 Boolean Algebra 9Let’s compare the resulting circuits• Here are two different but equivalentcircuits. • In general the one with fewer gates is “better”:– It costs less to build– It requires less power– But we had to do some work to find the second formCS231 Boolean Algebra 10Some more laws• Here are some more useful laws (p. 37). Notice the duals again!• We can prove these laws by either– Making truth tables:– Using the axioms:1. x + xy = x 4. x(x + y) = x2. xy + xy’ = x 5. (x + y)(x + y’) = x3. x + x’y = x + y 6. x(x’ + y) = xyxy + x’z + yz = xy + x’z (x + y)(x’ + z)(y + z) = (x + y)(x’ + z)x y x’ x’y x + x’y x y x + y00 00 001 01 110 10 111 11 1x + x’y = (x + x’)(x + y) [ Distributive ]= 1 • (x + y) [ x + x’ = 1 ]= x + y [ Axiom 2 ]CS231 Boolean Algebra 11The complement of a function• The complement of a function always outputs 0 where the originalfunction outputted 1, and 1 where the original produced 0.• In a truth table, we can just exchange 0s and 1s in the output column(s)f(x,y,z) = x(y’z’ + yz)x y z f(x,y,z)000 1001 1010 1011 1100 0101 0110 1111 0x y z f’(x,y,z)000 0001 0010 0011 0100 1101 1110 0111 1CS231 Boolean Algebra 12Complementing a function algebraically• You can use DeMorgan’s law to keep “pushing” the complements inwards• You can also take the dual of the function, and then complement …
View Full Document