De Morgan's Laws
De Morgan's laws convert between AND and OR through inversion, letting any gate be rebuilt from its dual.
The two laws
De Morgan's laws state that the complement of an AND is the OR of the complements, and the complement of an OR is the AND of the complements:
- NOT(A AND B) = NOT A OR NOT B.
- NOT(A OR B) = NOT A AND NOT B.
Verification by truth table
| A | B | NOT(A AND B) | NOT A OR NOT B |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
The two output columns match on every row, which proves the first law. The second follows the same way.
The bubble-pushing rule
In diagrams the laws appear as bubble pushing: an AND gate with a bubble on its output is identical to an OR gate with bubbles on both inputs, and vice versa. Pushing bubbles through a gate flips its shape between AND and OR.
Why they are indispensable
- They let a circuit be rebuilt entirely from NAND or entirely from NOR gates.
- They convert active-high logic to active-low logic cleanly.
- They transform a sum-of-products form into a product-of-sums form.
- They simplify expressions by moving inversions inward or outward.
Generalization
The laws extend to any number of inputs: the complement of a big AND is the OR of all the complemented inputs, and the complement of a big OR is the AND of all of them. This scaling makes De Morgan the most-used identity in gate-level design.