NAND and NOR gate converter

To build a Boolean expression from NAND gates only, write it as a minimal sum of products and turn every AND and the final OR into NAND gates; for NOR gates only, start from the minimal product of sums and turn every OR and the final AND into NOR gates. Type an expression below and the converter does both: it finds the minimal form, draws the circuit from 2-input NAND (or NOR) gates, and shows it live once the simulator has checked it on every row of the truth table.

How the conversion works

NAND gates only. Start from the minimal sum of products, for example F = AB + CD. By De Morgan's law, NAND(NAND(A, B), NAND(C, D)) = AB + CD: the inversion at the output of each first-level NAND and the inversion at the input of the second-level NAND cancel, so an AND-OR circuit becomes NAND-NAND gate for gate. Three details complete the method:

• A complemented input such as A' is one NAND with both inputs tied: NAND(A, A) = A'. Every A' shares the same one.
• A product with a single literal, like the C in AB + C, goes into the output NAND inverted: AB + C = NAND(NAND(A, B), C').
• A gate with more than two inputs is a small tree of 2-input gates: a 3-input NAND is NAND(AND(A, B), C), and that AND is a NAND followed by an inverter.

NOR gates only is the dual. Start from the minimal product of sums, for example F = (A + B)(C + D), and NOR(NOR(A, B), NOR(C, D)) = (A + B)(C + D), an OR-AND circuit drawn NOR-NOR. The minimal sums come from the zeros of the truth table, the same groups a Karnaugh map circles around the 0s. Both minimal forms are found with the Quine-McCluskey method.

Gate counts from the converter

Every count below comes from the converter itself, counting 2-input gates and the inverters made from them. The NAND form follows the sum of products and the NOR form the product of sums, so a function that is short as a product of sums is cheaper in NOR gates, and the other way round.

Worked example: F = AB + C with NAND gates

The expression is already a minimal sum of products with two terms. The term AB becomes NAND(A, B). The single-literal term C enters the output gate inverted, so it needs one inverter, C' = NAND(C, C). The output is NAND(NAND(A, B), C'), three NAND gates in all. Check one row: with A = B = 1 and C = 0, NAND(A, B) = 0, so the output NAND gives 1, as AB + C = 1 should. With NOR gates the same function is (A + C)(B + C): NOR(NOR(A, C), NOR(B, C)), also three gates.

Why NAND and NOR are enough

NAND and NOR are universal gates: each one alone can make NOT, AND and OR, and therefore any logic function. That is why a whole design can be built from one gate type; in CMOS a NAND gate is four transistors, see the CMOS NAND gate and the CMOS NOR gate. The single gates are built live in NOT, AND and OR from NAND and from NOR, and bigger circuits such as the half adder, the full adder from NAND gates and the 2-to-4 decoder from NOR gates show where a hand-made multi-level design beats the two-level form.

Frequently asked

How do you implement a Boolean expression using only NAND gates?

Write the expression as a minimal sum of products, then replace every AND gate and the final OR gate with NAND gates. A product with one literal needs that literal inverted, and an inverted input is a NAND with both inputs tied together. The result is a two-level NAND-NAND circuit with the same truth table.

How do you implement a Boolean expression using only NOR gates?

Write it as a minimal product of sums, then replace every OR gate and the final AND gate with NOR gates. A sum with one literal needs that literal inverted, and an inverted input is a NOR with both inputs tied together. The result is a two-level NOR-NOR circuit.

Why does NAND-NAND equal AND-OR?

By De Morgan's law, NAND(X', Y') = X + Y, and a NAND of literals is the complement of their product. So NAND(NAND(A, B), NAND(C, D)) = AB + CD: the two inversions on each wire cancel.

Why does the NOR version start from a product of sums?

Because NOR-NOR is the dual of NAND-NAND: NOR(NOR(A, B), NOR(C, D)) = (A + B)(C + D). A NOR circuit naturally builds an AND of ORs, so the minimal product of sums gives the smallest two-level NOR circuit.

How many NAND gates does an XOR need?

Five in the two-level NAND-NAND form this converter draws for A'B + AB': two inverters and three NANDs. A cleverer multi-level design shares one gate and needs only four NANDs.

Can every Boolean function be built from NAND gates only?

Yes. NAND is a universal gate: NOT, AND and OR can all be made from it, and any function can be written with those three. The same is true of NOR.