Logic gates and Boolean algebra cheat sheet
Truth tables for every basic gate, what each outputs, which are universal, how each is built, and the Boolean algebra identities for simplifying expressions.
The six basic logic gates are NOT, AND, NAND, OR, NOR, and XOR. Each takes one or two bits in and produces one bit out, fully described by its truth table. NAND and NOR are universal: every other gate can be built from either one alone. Below the gates you will find the Boolean algebra identities (including De Morgan's laws) used to simplify logic.
At a glance
| Gate | Output is 1 when | Expression | Universal? |
|---|---|---|---|
| NOT | the input is 0 | F = NOT A | No |
| AND | both inputs are 1 | F = A AND B | No |
| NAND | not both inputs are 1 | F = NOT (A AND B) | Yes |
| OR | at least one input is 1 | F = A OR B | No |
| NOR | both inputs are 0 | F = NOT (A OR B) | Yes |
| XOR | the inputs differ | F = A XOR B | No |
Each gate in detail
NOT
F = NOT A| A | F |
|---|---|
| 0 | 1 |
| 1 | 0 |
One PMOS over one NMOS sharing the input: the smallest CMOS gate, two transistors.
Full NOT lesson →AND
F = A AND B| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
A NAND followed by a NOT: the double inversion cancels, leaving AND.
Full AND lesson →NAND
F = NOT (A AND B)| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Two NMOS in series (pull-down), two PMOS in parallel (pull-up): four transistors, universal.
Full NAND lesson →OR
F = A OR B| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
A NOR followed by a NOT, mirroring how AND is built from NAND.
Full OR lesson →NOR
F = NOT (A OR B)| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NAND's mirror: two PMOS in series (pull-up), two NMOS in parallel (pull-down). Also universal.
Full NOR lesson →XOR
F = A XOR B| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
No single CMOS gate does it: built from four NAND gates. The sum bit of binary addition.
Full XOR lesson →Boolean algebra identities
The laws for simplifying logic expressions. Notation: · is AND, + is OR, and A' is NOT A. Involution (double negation): (A')' = A.
| Law | AND form | OR form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Null | A · 0 = 0 | A + 1 = 1 |
| Idempotent | A · A = A | A + A = A |
| Complement | A · A' = 0 | A + A' = 1 |
| Absorption | A · (A + B) = A | A + A · B = A |
| Commutative | A · B = B · A | A + B = B + A |
| Associative | (A · B) · C = A · (B · C) | (A + B) + C = A + (B + C) |
| Distributive | A · (B + C) = A·B + A·C | A + B·C = (A + B)·(A + C) |
| De Morgan's | (A · B)' = A' + B' | (A + B)' = A' · B' |