Other Logic Operations
Beyond AND/OR/NOT: the full set of two-variable functions, including XOR and NAND.
Description
The complete catalog of the sixteen possible functions of two binary variables. It shows which operations exist and which (NAND/NOR) are universal. Enumerate all 2^(2²) = 16 output patterns and name the useful ones.
- Two variables have 4 input rows, so 2⁴ = 16 distinct output columns.
- Named members include AND, OR, NAND, NOR, XOR, XNOR, and implication.
- NAND and NOR are each functionally complete (universal).
- What: The complete catalog of the sixteen possible functions of two binary variables.
- Why: It shows which operations exist and which (NAND/NOR) are universal.
- How: Enumerate all 2^(2²) = 16 output patterns and name the useful ones.
- Where: Choosing gate primitives and understanding universality.
- When: When selecting a minimal or convenient gate set for a technology.
- Analogy — Like discovering that out of 16 possible handshakes between two people, just one move (NAND) can be repeated to mimic all the others — a single universal gesture.
At a glance
What
The complete catalog of the sixteen possible functions of two binary variables.
Why
It shows which operations exist and which (NAND/NOR) are universal.
How
Enumerate all 2^(2²) = 16 output patterns and name the useful ones.
Where
Choosing gate primitives and understanding universality.
When
When selecting a minimal or convenient gate set for a technology.
Think of it like…
Like discovering that out of 16 possible handshakes between two people, just one move (NAND) can be repeated to mimic all the others — a single universal gesture.
Sixteen functions
- Two variables have 4 input rows, so 2⁴ = 16 distinct output columns.
- Named members include AND, OR, NAND, NOR, XOR, XNOR, and implication.
- NAND and NOR are each functionally complete (universal).
Key 2-variable functions
| Function | Expression | Note |
|---|---|---|
| AND | AB | both 1 |
| OR | A + B | any 1 |
| NAND | (AB)′ | universal |
| NOR | (A + B)′ | universal |
| XOR | A ⊕ B | inequality |
| XNOR | (A ⊕ B)′ | equality |
| Implication | A′ + B | if A then B |
Try every named gate
▶ live simulatorClick a terminal (A/B) to toggle it · glowing wires carry a logic 1 · the lamp is output Y
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The 5 Whys
- 1
Why study all 16 functions? To know the full design space for two inputs.
- 2
Why highlight NAND/NOR? Each can build every other function.
- 3
Why does universality matter? A library can standardize on one cell type.
- 4
Why standardize cells? It simplifies fabrication and optimization.
- 5
Root cause: enumerating the space reveals the minimal primitives hardware actually needs.
Cheat sheet
Working principle
- Enumerate all 2^(2²) = 16 output patterns and name the useful ones.
- The complete catalog of the sixteen possible functions of two binary variables.
Formulas & Boolean expressions
- Two variables have 4 input rows, so 2⁴ = 16 distinct output columns.
Key facts
- Two variables have 4 input rows, so 2⁴ = 16 distinct output columns.
Why it exists
- Root cause: enumerating the space reveals the minimal primitives hardware actually needs.