Universal gate: meaning and examples

Q: Why tie both inputs of a NAND together to get NOT?

Because NAND(A, A) is NOT (A AND A), and A AND A is A by idempotence, so the gate outputs NOT A. The table on this page shows exactly that column, true for A = FALSE and false for A = TRUE.

A universal gate is one from which every Boolean function can be built using no other kind of gate. NAND and NOR are the two universal gates; AND, OR and NOT are not universal on their own.

A gate type is universal, or functionally complete, when NOT, AND and OR can each be assembled from it, since every formula reduces to those three. NAND qualifies: NAND(A, A) is NOT A, NAND(NAND(A, B), NAND(A, B)) is A AND B, and NAND(NAND(A, A), NAND(B, B)) is A OR B by De Morgan. NOR works the same way with the roles of AND and OR exchanged. AND and OR alone cannot produce a negation, which is why neither is universal.

The artefact on this page is the first of those constructions, NAND(A, A), named not_a. Its 2-row table reads true, false, the column of NOT A. The tautology check is violated with the counterexample A = TRUE, where both inputs of the gate are true and NAND gives false, and the satisfiable check holds with the witness A = FALSE. The engine's reading says that not_a is true exactly when A and A are not both true, which is a roundabout way of saying when A is false.

Universality is why real chips are built almost entirely from NAND or NOR: one well-characterised cell type is cheaper to manufacture and verify than seven. The engine's NAND-only and NOR-only converter performs the rewrite and reports how many gates the result uses; the laws it applies are listed under NAND and NOR elimination. The term is confused with a gate that merely has many inputs, and “universal” is sometimes misread as “the one you should use”, which it does not mean.

Example

not_a := NAND(A, A) · output

Exact checks

Always true (tautology)? No Counterexample: A = T · Exhaustively checked and solver cross-checked · 2 rows

Always false (contradiction)? No Counterexample: A = F · Exhaustively checked and solver cross-checked · 1 rows

Can be true? Yes Example assignment: A = F · Exhaustively checked and solver cross-checked · 1 rows

Truth table (2 rows)

Universal gate: meaning and examples
#	A	not_a
0	FALSE	TRUE
1	TRUE	FALSE

Plain-language reading

Beginnernot_a is true exactly when A and A are not both true.
In every other case, not_a is false.
About the operators:
- NAND (“not and”) is false only when both parts are true.

Intermediatenot_a is true exactly when A and A are not both true.
In every other case, not_a is false.

Advancednot_a is true exactly when A and A are not both true [Sheffer stroke ↑ (NAND)].
In every other case, not_a is false.
Formal notation: NAND(A, A)

The common slip

Assuming XOR is universal because it looks powerful. XOR with constants gives NOT, but no combination of XOR gates produces AND, so XOR alone cannot build every function. Only NAND and NOR, among the two-input gates, are universal.

Questions

Why tie both inputs of a NAND together to get NOT?

Because NAND(A, A) is NOT (A AND A), and A AND A is A by idempotence, so the gate outputs NOT A. The table on this page shows exactly that column, true for A = FALSE and false for A = TRUE.

Guides

What is a logic gate?

Practice

NAND-only and NOR-only design exercises with answers

Glossary

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. 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.