From now on:Simplification with axiomsReview of Boolean Algebra AxiomsSlide 4Let’s compare the resulting circuitsSome more lawsProof by casesThe 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 formsSummaryKarnaugh mapsRe-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 1From now on: •Combinatorial Circuits:–Study analyses and design of circuits made up of gates without memory–Design components needed for a simple “Computer”•Sequential Circtuits:–Study basic memory elements–Study Ckts that can be designed using memory elements and gates•Design a computer (and understand design of computers in general)CS231 Boolean Algebra 2Simplification 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) ]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 (lvk) 3Review of Boolean Algebra 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 true•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 4Simplification 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 5Let’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 6Some 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’ = 1 ]= x + y [ Axiom 2 ]CS231 Boolean Algebra (lvk) 7Proof by cases•A variation of the truth table method–Doesn’t require to compute all rows–But uses “simpler” algebraic proofs.Prove x + x’y = x+y For cases: x=1 and x=0If x=1: x + x’y ?= x+y1 + 0.y ?= 1+y1 ?= 1 [Axiom 3]If x= 0: x + x’y ?= x+y0 + 1.y ?= 0 + y0 + y ?= 0 + y[Axiom 2]y ?= y [Axiom 1]CS231 Boolean Algebra 8The complement of a function•The complement of a function always outputs 0 where the original function 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)0 0 0 10 0 1 10 1 0 10 1 1 11 0 0 01 0 1 01 1 0 11 1 1 0x y z f ’(x,y,z)0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 11 0 1 11 1 0 01 1 1 1CS231 Boolean Algebra 9Complementing 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 each literal–If f(x,y,z) = x(y’z’ + yz)…–…the dual of f is x + (y’ + z’)(y + z)…–…then complementing each literal gives x’ + (y + z)(y’ + z’)…–…so f’(x,y,z) = x’ + (y + z)(y’ + z’)f(x,y,z) = x(y’z’ + yz)f’(x,y,z) = ( x(y’z’ + yz) )’ [ complement both sides ]= x’ + (y’z’ + yz)’ [ because (xy)’ = x’ + y’ ]= x’ + (y’z’)’ (yz)’ [ because (x + y)’ = x’ y’ ]= x’ + (y + z)(y’ + z’) [ because (xy)’ = x’ + y’, twice]CS231 Boolean Algebra 10Standard forms of expressions•We can write expressions in many ways, but some ways are more useful than others•A sum of products (SOP) expression contains:–Only OR (sum) operations at the “outermost” level–Each term that is summed must be a product of literals•The advantage is that any sum of products expression can be implemented using a two-level circuit–literals and their complements at the “0th” level–AND gates at the first level–a single OR gate at the second level•This diagram uses some shorthands…–NOT gates are implicit–literals …
View Full Document
Unlocking...