Simplifying logic: truth tables and K-maps
Turn a rule (a porch light that comes on when the door is open and it is dark, or when the override is on) into a truth table, then into a sum of products, and build it from gates: 9 of them. Then shrink it to 2 gates, first with a few Boolean algebra rules and then with a Karnaugh map, and see why fewer gates are cheaper, faster and use less power.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01A rule has three inputs. How many rows does its truth table have?
Each input can be 0 or 1, so there are 2 × 2 × 2 = 8 combinations, one row each.
02In a sum of products built from a truth table, what does each AND term stand for?
Each AND term is true in exactly one row, a row that should give 1. ORing them gives 1 in all those rows and 0 everywhere else.
03What does D'N'O + D'NO simplify to?
The two terms differ only in N. D'O(N' + N) = D'O · 1 = D'O: when two terms differ in one input, that input drops out.
04Why do the columns of a K-map go 00, 01, 11, 10 instead of 00, 01, 10, 11?
This order (a Gray code) makes neighbours differ in one bit, even the two end columns. Then a group of neighbouring 1s is exactly a set of terms that can merge.
05The light circuit shrank from 9 gates to 2. Which is NOT a benefit of that?
Simplifying never changes the answer: L = DN + O gives the same output as the big formula on all 8 rows. It only does the job with less.
Glossary
- Truth table
- A list of every combination of input bits and the output wanted for each one.
- Boolean algebra
- Algebra on 0 and 1 with AND (written · or nothing), OR (+) and NOT (written ', so D' is NOT D).
- Term (product)
- Inputs or their opposites joined by AND, such as DN or D'N'O.
- Sum of products
- Terms joined by OR, such as DN + O. Writing one term per 1-row of a truth table always gives a correct one.
- Absorption
- The rule A + A·B = A: if A alone already makes the result 1, the term A·B adds nothing.
- Karnaugh map (K-map)
- A truth table drawn as a grid whose neighbouring cells differ in one input, so mergeable 1s sit next to each other.
- Gray code
- An order of binary numbers, such as 00, 01, 11, 10, in which each step changes exactly one bit.
- Gate count
- How many gates a circuit needs; fewer gates means less area, less power and usually less delay.
Notes and sources
- A sum of products is an OR of AND terms. Writing one AND term (a minterm) for every row whose output is 1 always works, but it is rarely the smallest circuit (Harris and Harris, Digital Design and Computer Architecture, sections 2.2 and 2.3).
- The rules used here: A·A' = 0 and A + A' = 1 (complements), A + A·B = A (absorption, also called covering) and A·B + A·B' = A (combining). Each can be checked with a 4-row truth table.
- Maurice Karnaugh published the map method in 1953. Its columns follow Gray code, 00, 01, 11, 10, so cells side by side, and the two end columns, differ in one input; groups are rectangles of 1, 2, 4 or 8 cells.
- Transistor counts are for static CMOS: NOT 2, a k-input NAND or NOR 2k, and a k-input AND or OR 2k + 2 (a NAND or NOR plus a NOT). From the table: 3 × 2 + 5 × 8 + 12 = 58. Simplified: 6 + 6 = 12.
- Why it matters: a chip's switching power grows with the capacitance it charges each clock tick (P = α·C·V²·f), and delay adds up along the chain of gates a signal passes (Harris and Harris, sections 1.8 and 2.9).
- Lamps show bits: a glowing lamp is 1, a dark one 0. A lit wire with moving dashes carries a 1.
- Harris and Harris, Digital Design and Computer Architecture (chapter 2: Boolean equations, Boolean algebra, Karnaugh maps)
- Karnaugh, The Map Method for Synthesis of Combinational Logic Circuits (Trans. AIEE, 1953)
- Shannon, A Symbolic Analysis of Relay and Switching Circuits (MIT, 1937)
- MIT OpenCourseWare 6.004 Computation Structures
- Python reference: Boolean operations (and, or, not)
- Python itertools.product
Quiz Unlocks after the last step.