NAND-only and NOR-only design exercises with answers
Ten functions to rebuild from a single gate type, NAND or NOR, as the prompt says. Write the formula in the engine's function form, NAND(…, …) or NOR(…, …) with exactly two operands per gate, and count the gates. Each answer is verified equivalent to the function; the solution gives one hand design and its gate count.
Three identities do all the work for NAND: NOT A is NAND(A, A); A AND B is NAND(NAND(A, B), NAND(A, B)), a NAND followed by an inverter; A OR B is NAND(NAND(A, A), NAND(B, B)), by De Morgan. The NOR versions are the duals: NOT A is NOR(A, A), A OR B is NOR(NOR(A, B), NOR(A, B)), and A AND B is NOR(NOR(A, A), NOR(B, B)). Build from the inside out and look for inverters that cancel in pairs.
The gate counts in the solutions are for the design shown, and a cleverer design may use fewer: A XOR B takes four NANDs when the shared NAND(A, B) is reused, but five if it is built twice. The truth table under each problem is the function's own; the equivalence of your formula is the thing to check, and any formula with the same table passes, whatever its count.
1. Build NOT A with NAND gates only. NOT A
| # | A | f |
|---|---|---|
| 0 | FALSE | TRUE |
| 1 | TRUE | FALSE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
NOT A Classification: contingent
NAND(A, A): a NAND with both inputs tied is an inverter. One gate.
2. Build A AND B with NAND gates only. A AND B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | FALSE |
| 2 | TRUE | FALSE | FALSE |
| 3 | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A AND B Classification: contingent
NAND(NAND(A, B), NAND(A, B)): the NAND of A and B followed by an inverter made of a second NAND. Two gates.
3. Build A OR B with NAND gates only. A OR B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | TRUE |
| 2 | TRUE | FALSE | TRUE |
| 3 | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A OR B Classification: contingent
By De Morgan, A OR B is NOT (NOT A AND NOT B), that is a NAND of the two inverted inputs: NAND(NAND(A, A), NAND(B, B)). Three gates.
4. Build A XOR B with NAND gates only. A XOR B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | TRUE |
| 2 | TRUE | FALSE | TRUE |
| 3 | TRUE | TRUE | FALSE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A XOR B Classification: contingent
Let n = NAND(A, B), shared by both branches: NAND(A, n) is NOT A OR B and NAND(B, n) is A OR NOT B; their NAND negates the biconditional, which is XOR. Four gates: NAND(NAND(A, NAND(A, B)), NAND(B, NAND(A, B))).
5. Build A AND B with NOR gates only. A AND B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | FALSE |
| 2 | TRUE | FALSE | FALSE |
| 3 | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A AND B Classification: contingent
By De Morgan, A AND B is NOT (NOT A OR NOT B), a NOR of the two inverted inputs: NOR(NOR(A, A), NOR(B, B)). Three gates.
6. Build A OR B with NOR gates only. A OR B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | TRUE |
| 2 | TRUE | FALSE | TRUE |
| 3 | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A OR B Classification: contingent
A NOR followed by a NOR inverter: NOR(NOR(A, B), NOR(A, B)). Two gates, the dual of the NAND construction of AND.
7. Build A -> B with NAND gates only. A -> B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | TRUE |
| 1 | FALSE | TRUE | TRUE |
| 2 | TRUE | FALSE | FALSE |
| 3 | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A -> B Classification: contingent
A -> B is NOT A OR B, which is NOT (A AND NOT B), a NAND of A and the inverted B: NAND(A, NAND(B, B)). Two gates.
8. Build (A AND B) OR C with NAND gates only. (A AND B) OR C
| # | A | B | C | f |
|---|---|---|---|---|
| 0 | FALSE | FALSE | FALSE | FALSE |
| 1 | FALSE | FALSE | TRUE | TRUE |
| 2 | FALSE | TRUE | FALSE | FALSE |
| 3 | FALSE | TRUE | TRUE | TRUE |
| 4 | TRUE | FALSE | FALSE | FALSE |
| 5 | TRUE | FALSE | TRUE | TRUE |
| 6 | TRUE | TRUE | FALSE | TRUE |
| 7 | TRUE | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
(A AND B) OR C Classification: contingent
A sum of products maps to two levels of NAND: (A AND B) OR C is NOT (NOT (A AND B) AND NOT C), so NAND(NAND(A, B), NAND(C, C)), where the inverter on C is a NAND with tied inputs. Three gates.
9. Build the multiplexer (A AND B) OR (NOT A AND C) with NAND gates only. (A AND B) OR (NOT A AND C)
| # | A | B | C | f |
|---|---|---|---|---|
| 0 | FALSE | FALSE | FALSE | FALSE |
| 1 | FALSE | FALSE | TRUE | TRUE |
| 2 | FALSE | TRUE | FALSE | FALSE |
| 3 | FALSE | TRUE | TRUE | TRUE |
| 4 | TRUE | FALSE | FALSE | FALSE |
| 5 | TRUE | FALSE | TRUE | FALSE |
| 6 | TRUE | TRUE | FALSE | TRUE |
| 7 | TRUE | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
(A AND B) OR (NOT A AND C) Classification: contingent
Two product terms into a NAND of NANDs: NAND(NAND(A, B), NAND(NAND(A, A), C)), where NAND(A, A) is the inverter on the select input. Four gates.
10. Build A <-> B with NOR gates only. A <-> B
| # | A | B | f |
|---|---|---|---|
| 0 | FALSE | FALSE | TRUE |
| 1 | FALSE | TRUE | FALSE |
| 2 | TRUE | FALSE | FALSE |
| 3 | TRUE | TRUE | TRUE |
The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.
A <-> B Classification: contingent
Let n = NOR(A, B): NOR(A, n) is NOT A AND B and NOR(B, n) is A AND NOT B; their NOR negates the XOR, which is the biconditional. Four gates: NOR(NOR(A, NOR(A, B)), NOR(B, NOR(A, B))), the dual of the NAND design of XOR.
Questions
Why does the engine accept a formula with more gates than mine?
Because the check is about the function, not the cost: an answer passes when it is equivalent on every row. Gate count is a design quality that you judge by hand, and the solutions give one count for comparison, without claiming it cannot be beaten.
Related
Laws
- AND from NAND gates: A AND B = NAND(NAND(A, B), NAND(A, B))
- NOT from NOR: NOT A = NOR(A, A)
- OR from NOR gates: A OR B = NOR(NOR(A, B), NOR(A, B))
Operators and gates
- NAND gate: truth table for 2, 3 and 4 inputs, universal gate
- NOR gate: truth table for 2, 3 and 4 inputs, universal gate
Worked examples
- XOR with four NAND gates, verified equivalent
- AND with NOR gates only
- Majority of three with NAND gates only
Compare
See also
- NOT from NAND: NOT A = NAND(A, A)
- OR from NAND gates: A OR B = NAND(NAND(A, A), NAND(B, B))
- AND from NOR gates: A AND B = NOR(NOR(A, A), NOR(B, B))
- Universal gate: meaning and examples
- NAND-only and NOR-only converter with equivalence proof
Practice
Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build . Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.