(A·B·C·D)′ — De Morgan's laws
coren-input generalisation
Answer
A′ + B′ + C′ + D′
Why this example is worth doing
The four-input generalisation, included because the two-input statement leaves students unsure whether the law extends. It does, to any arity, by induction on the associativity of AND: the complement of a product of n terms is the sum of the n complements. The page states the general form with an index and then makes the hardware point that a 4-input NAND is one gate, not a chain of 2-input NANDs, so the algebraic flattening corresponds to a real reduction in gate count and delay.
Try your own input in the De Morgan’s laws. Push a negation through any expression and see both forms side by side.
How the answer is reached
Negation pushed inwards
(A · B · C · D)′A′ + B′ + C′ + D′— De Morgan swaps the operator as the bar passes through it.
Truth table
| # | A | B | C | D | F |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 |
| 5 | 0 | 1 | 0 | 1 | 1 |
| 6 | 0 | 1 | 1 | 0 | 1 |
| 7 | 0 | 1 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 1 | 1 |
| 10 | 1 | 0 | 1 | 0 | 1 |
| 11 | 1 | 0 | 1 | 1 | 1 |
| 12 | 1 | 1 | 0 | 0 | 1 |
| 13 | 1 | 1 | 0 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | 1 |
| 15 | 1 | 1 | 1 | 1 | 0 |