NAND and NOR converter
Rewrite any expression using nothing but NAND gates, or nothing but NOR gates. Both are universal, so every circuit has a version made of one gate repeated.
Input a ∨ b ∧ ¬c 3 gates
NAND only NAND(NAND(a, a), NAND(b, NAND(c, c)))
Gates needed 4 (NAND gates, identical subcircuits counted once; output checked against the original truth table)
Paste into the editor !(!(a && a) && !(b && !(c && c)))
Copy that last line, open the simulator and press ctrl+E to build it from real gates.
The substitution rules
The conversion is mechanical: replace each operator with its equivalent built from the target gate, then repeat until nothing else is left.
| Operation | Becomes |
|---|---|
| ¬a | NAND(a, a) |
| a ∧ b | NAND(NAND(a, b), NAND(a, b)) |
| a ∨ b | NAND(NAND(a, a), NAND(b, b)) |
| a ⊻ b | NAND(NAND(a, c), NAND(b, c)) where c = NAND(a, b) |
The OR rule is De Morgan's law written as gates: inverting both inputs of a NAND turns it into an OR. The AND rule is simpler still, just double negation, since a NAND followed by an inverter is an AND.
What it costs
Rewriting with one gate type is rarely free. These are the counts for the basic operations.
| Operation | NAND gates | NOR gates |
|---|---|---|
| ¬a | 1 | 1 |
| a ∧ b | 2 | 3 |
| a ∨ b | 3 | 2 |
| a ⊻ b | 4 | 5 |
NAND favours AND-heavy logic and NOR favours OR-heavy logic, which is the mirror symmetry you would expect. Simplify the expression before converting: a smaller starting circuit converts into a smaller one.
Why one gate is enough
A set of gates is called functionally complete when every boolean function can be built from it. AND, OR and NOT together are complete, and the interesting fact is that NAND on its own already contains all three. Tie both its inputs together and it is an inverter; follow it with that inverter and it is an AND; invert both inputs first and, by De Morgan's law, it is an OR.
The same argument works for NOR, and those two are the only two input gates with this property. It is not merely a theoretical curiosity: the NAND gate is the fastest and best behaved two input gate in CMOS, because it puts the slow transistors in parallel rather than in series, so real silicon leans on exactly this result. The Apollo Guidance Computer went the other way and was built almost entirely from three input NOR gates.
Questions
Why can NAND build every other gate?
Because NOT, AND and OR can each be made from NAND alone, and those three are enough to express any boolean function. NOT is a NAND with both inputs tied together, AND is a NAND followed by that NOT, and OR is a NAND fed by two inverted inputs, which is De Morgan's law in gate form. NOR is universal for exactly the same reasons.
Why would anyone build a circuit from one kind of gate?
In CMOS a NAND is smaller and faster than the equivalent AND, because AND is physically a NAND with an inverter bolted on. Standardising on one gate also simplifies manufacturing and lets a design use a single part number, which is why NAND dominates real chips.
Is the gate count here the minimum?
It is the count for this particular construction, with identical subcircuits counted once because they would be one shared gate. It is not guaranteed minimal: a smarter factorisation of the original expression can sometimes do better. Simplify the expression first for the best result.
How many NAND gates does XOR need?
Four. The trick is to compute c = NAND(a, b) once and reuse it: XOR is NAND(NAND(a, c), NAND(b, c)). With NOR gates the same shape produces XNOR, so XOR takes five NOR gates because it needs one more to invert the result.