Logic Gates & Boolean Algebra
The seven fundamental logic gates with truth tables and equations, how they map to CMOS transistors, and the Boolean algebra that simplifies them.
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
Y is 1 only when all inputs are 1.
| 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 | (A·B)' = A' + B' | (A+B)' = A' · B' |
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.
Finished reading?
Mark it complete to track your progress through the path.
Go further
New to VLSI? Get the 6-month fresher roadmap and a 16-week study plan.
Get new lessons by email
New lessons, interview prep and real EDA tool workflows. No spam.