Circuit analysis summaryBoolean operations summaryExpression simplificationFormal definition of Boolean algebraComments on the axiomsAre these axioms for real?Proving the rest of the axiomsSimplification with axiomsLet’s compare the resulting circuitsSome more lawsThe complement of a functionComplementing a function algebraicallyStandard forms of expressionsMintermsSum of minterms formThe dual idea: products of sumsMaxtermsProduct of maxterms formMinterms and maxterms are relatedConverting between standard formsSummary so farKarnaugh mapsReview: Standard forms of expressionsTerminology: MintermsTerminology: Sum of minterms formRe-arranging the truth tableKarnaugh map simplificationsMore two-variable examplesA three-variable Karnaugh mapWhy the funny ordering?Example K-map simplificationUnsimplifying expressionsMaking the example K-mapK-maps from truth tablesGrouping the minterms togetherReading the MSP from the K-mapPractice K-map 1Solutions for practice K-map 1Four-variable K-mapsExample: Simplify m0+m2+m5+m8+m10+m13K-maps can be tricky!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 least two 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 any equation 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 xy0 0 00 1 01 0 01 1 1x y x+y0 0 00 1 11 0 11 1 1x x’0 11 0x y x+y0 0 00 1 11 0 11 1 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’0 0 0 1 0 0 1 1 10 1 1 0 0 1 1 0 01 0 1 0 1 0 0 1 01 1 1 0 1 1 0 0 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 equivalent circuits. •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 + y0 0 0 0 00 1 0 1 11 0 1 0 11 1 1 1 1x + x’y = (x + x’)(x + y) [ Distributive ]= 1 - (x + y) [ x + x’ …
View Full Document