Day 16: Boolean algebra, De Morgan’s laws, and the logic gates
The algebra of logic
Every combinational circuit is a Boolean function: outputs are AND (·), OR (+), and NOT (') of inputs. The gate zoo — AND, OR, NOT, NAND, NOR, XOR, XNOR — is just these operations packaged. Boolean *algebra* gives you identities to rewrite an expression into an equivalent but cheaper one, which is exactly what logic synthesis (Stage 5) automates.
Identity A + 0 = A A * 1 = A
Null A + 1 = 1 A * 0 = 0
Idempotent A + A = A A * A = A
Complement A + A' = 1 A * A' = 0
Absorption A + A*B = A A * (A + B) = A
Distributive A*(B+C) = A*B + A*C
De Morgan (A * B)' = A' + B' (A + B)' = A' * B'De Morgan's laws and bubble-pushing
De Morgan's laws are the workhorses: *the complement of an AND is the OR of the complements*, and vice-versa. Practically, this is bubble-pushing — a NAND is an OR with inverted inputs, a NOR is an AND with inverted inputs. It's why NAND and NOR are each universal: any logic function can be built from NAND gates alone (or NOR alone), which is why libraries lean on them.
Two ways to say the same thing
'Neither it's raining nor it's cold' (NOR) is the same as 'it's not raining AND it's not cold' (AND of complements). De Morgan just formalizes that everyday equivalence — and lets a tool freely swap between the two forms to pick whichever maps to cheaper gates.
Key terms
- Boolean function
- A mapping from binary inputs to binary outputs, expressed with AND/OR/NOT.
- De Morgan's laws
- (A·B)' = A' + B' and (A+B)' = A'·B' — complementing distributes over AND/OR by swapping the operator.
- Universal gate
- A gate (NAND or NOR) from which any Boolean function can be built.
- XOR / XNOR
- Exclusive-OR (1 when inputs differ) and its complement; the heart of adders and parity.
- Bubble-pushing
- Applying De Morgan graphically by moving inversion bubbles through gates to change their form.
Before moving on, you should be able to
Using De Morgan's law, (A + B)' is equivalent to which expression?
