From rule to formula
A porch light L should turn on when the door is open (D) and it is dark (N), or when the override switch (O) is on. Each input is a bit: 1 means yes, 0 means no.
A truth table lists every input combination and the output we want. Three inputs give 2 × 2 × 2 = 8 rows. The light is on in five: the four rows with O = 1, plus D = 1, N = 1.
For each row with a 1, write an AND term that is true only in that row, then OR the terms together: a sum of products. We write AND as a dot or nothing, OR as +, and NOT D as D'.
Simplify with algebra
Built exactly as written, the formula needs 3 NOT gates, 5 AND gates with three inputs each and one OR gate with five inputs: 9 gates. It gives the right answer for every row, but it is big.
Boolean algebra has rules for making formulas shorter. A AND NOT A is always 0: nothing is both. A OR NOT A is always 1. And A OR (A AND B) is just A. A and B stand for any input or term.
D'N'O and D'NO differ only in N. Together they say D is 0 and O is 1, whatever N is, because N' + N = 1. So they merge into D'O. DN'O and DNO merge into DO. 9 gates become 6.
Now D'O and DO differ only in D, so they merge into O: if the override is on, the light is on. The formula is O + DNO'. 6 gates become 3.
The last term still checks that O is 0. It does not need to: when O is 1 the light is on anyway. The rule A OR (A AND B) = A makes this exact. L = DN + O: just 2 gates.
Simplify with a K-map
A Karnaugh map, or K-map, holds the same 8 outputs in a grid: one row for each value of O, one column for each pair D N. The columns go 00, 01, 11, 10, so neighbours differ in one input.
Circle neighbouring 1s in blocks of 1, 2, 4 or 8, as big as possible; blocks may overlap. Keep only the inputs that stay the same in a block: the row of four gives O, the pair gives DN. Same answer, no algebra.
Why it matters
9 gates became 2, and 58 transistors became 12. Fewer gates take less chip space, so they cost less. They switch less, so they use less power. Signals pass fewer gates, so the answer comes sooner.
The working
;; step 1/11 · the-problem ;; about: Door open (D), Dark (N), Override (O), Light (L), Formula D door is open 1 yes · 0 no N it is dark (night) 1 yes · 0 no O override is on 1 yes · 0 no L light is on (the output) The rule in words: (door open AND dark) OR override
Lamps show bits: a glowing lamp is 1, a dark one 0. A lit wire with moving dashes carries a 1. 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.