Logic Gates & Boolean Algebra
The 7 Fundamental Gates - Truth Tables & Equations
The Physical Reality — Logic gates are built from transistors - CMOS technology uses PMOS and NMOS transistors as complementary switches. A NAND gate in 28nm CMOS has 4 transistors; a NOT gate has 2. Every Boolean function you write maps directly to physical transistors on silicon.
The 7 Fundamental Gates - Truth Tables & Equations
AND Gate
all
| A | B | Y=A·B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
at least one
| A | B | Y=A+B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NOT Gate (Inverter)
| A | Y=A' |
|---|---|
| 0 | 1 |
| 1 | 0 |
NAND Gate Universal
| A | B | Y=(AB)' |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate Universal
| A | B | Y=(A+B)' |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR Gate (Exclusive OR)
different
| A | B | Y=A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XNOR Gate (Exclusive NOR)
equal
| A | B | Y=(A⊕B)' |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Universal Gates - NAND & NOR Can Build Everything
A gate is called universal if you can construct any other logic function using only that gate. Both NAND and NOR are universal - this is critical in IC design because using fewer gate types reduces fabrication complexity.
Building with NAND only
NOT: Connect both inputs of NAND together → Y = (A·A)' = A'
AND: NAND followed by NOT → Y = ((A·B)')' = A·B
OR: NOT each input, then NAND → Y = (A'·B')' = A+B (De Morgan)
Any Boolean expression can be built with NAND gates alone.
Building with NOR only
NOT: Connect both inputs of NOR together → Y = (A+A)' = A'
OR: NOR followed by NOT → Y = ((A+B)')' = A+B
AND: NOT each input, then NOR → Y = (A'+B')' = A·B (De Morgan)
Any Boolean expression can be built with NOR gates alone.
Boolean Algebra Laws
| Law | AND Form | OR Form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Null (Annulment) | A · 0 = 0 | A + 1 = 1 |
| Idempotent | A · A = A | A + A = A |
| Complement | A · A' = 0 | A + A' = 1 |
| Double Negation | (A')' = A | |
| Commutative | A · B = B · A | A + B = B + A |
| Associative | A(BC) = (AB)C | A+(B+C) = (A+B)+C |
| Distributive | A(B+C) = AB+AC | A+BC = (A+B)(A+C) |
| Absorption | A(A+B) = A | A + AB = A |
| De Morgan's 1 | (A·B)' = A' + B' | |
| De Morgan's 2 | (A+B)' = A' · B' |
De Morgan's Theorem - The Most Used Rule in Digital Design — In words: To complement a function, invert each variable AND swap AND↔OR (or equivalently, break the bar and change the sign). Example 1: (A·B·C)' = A' + B' + C' (NAND = bubbled OR) Example 2: (A+B+C)' = A'·B'·C' (NOR = bubbled AND) This is the mathematical basis for why NAND and NOR are universal gates.
XOR Properties - Especially Important
A ⊕ 0 = A
XOR with 0 leaves the value unchanged - identity property.
A ⊕ 1 = A'
XOR with 1 inverts the value - controllable inverter. Used in encryption and data masking.
A ⊕ A = 0
XOR with itself is always 0. Used to clear registers and detect errors.
A ⊕ B ⊕ B = A
XOR is self-inverse - applying it twice restores the original. Foundation of XOR-based encryption.