Boolean Algebra

Laws, gates, identities & canonical forms

Quick Reference
Identity Laws
AND Identity A · 1 = A
OR Identity A + 0 = A
Null / Domination Laws
AND Null A · 0 = 0
OR Null A + 1 = 1
Idempotent Laws
AND Idempotent A · A = A
OR Idempotent A + A = A
Complement Laws
AND Complement A · A′ = 0
OR Complement A + A′ = 1
Double Negation (A′)′ = A
Commutative Laws
AND A · B = B · A
OR A + B = B + A
Associative Laws
AND (A·B)·C = A·(B·C)
OR (A+B)+C = A+(B+C)
Distributive Laws
AND over OR A·(B+C) = AB+AC
OR over AND A+BC = (A+B)(A+C)
Absorption Laws
Absorb OR A + (A · B) = A
Absorb AND A · (A + B) = A
Duality Principle
Rule Swap · ↔ + and 0 ↔ 1
Example A+0=A  ⟷  A·1=A
Example A+1=1  ⟷  A·0=0
XOR Identities
Identity A ⊕ 0 = A
Self-inverse A ⊕ A = 0
Complement A ⊕ 1 = A′
Commutative A ⊕ B = B ⊕ A
Associative (A⊕B)⊕C = A⊕(B⊕C)
AND Gate A · B
Output is 1 only when ALL inputs are 1
A B A·B
0 0 0
0 1 0
1 0 0
1 1 1
OR Gate A + B
Output is 1 when ANY input is 1
A B A+B
0 0 0
0 1 1
1 0 1
1 1 1
NOT Gate A′
Inverts the input (complement)
A A′
0 1
1 0
NAND Gate (A·B)′
NOT AND — universal gate
A B (A·B)′
0 0 1
0 1 1
1 0 1
1 1 0
NOR Gate (A+B)′
NOT OR — universal gate
A B (A+B)′
0 0 1
0 1 0
1 0 0
1 1 0
XOR Gate A ⊕ B
Output is 1 when inputs DIFFER
A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0
XNOR Gate A ⊙ B
Output is 1 when inputs are EQUAL
A B A⊙B
0 0 1
0 1 0
1 0 0
1 1 1
Buffer A
Output equals input — used for signal driving
A Out
0 0
1 1
De Morgan's Theorems
First Theorem — NAND → NOR of complements
(A · B)′ = A′ + B′
Second Theorem — NOR → NAND of complements
(A + B)′ = A′ · B′
Generalized Form
Complement of AND
(A₁ · A₂ · … · Aₙ)′ = A₁′ + A₂′ + … + Aₙ′
Complement of OR
(A₁ + A₂ + … + Aₙ)′ = A₁′ · A₂′ · … · Aₙ′
Application — Gate Substitution
NAND from NOR (A·B)′ = ((A′+B′)′)′
AND from NAND A·B = ((A·B)′)′
OR from NAND A+B = (A′·B′)′
NOT from NAND A′ = (A·A)′
NOT from NOR A′ = (A+A)′
Sum of Products (SOP)
Structure
F = (A′B′C) + (AB′C) + (ABC)
OR of AND terms (minterms). Each term is a product; the expression is their sum.
Minterm (m)
Row where F = 1
Include the row's AND term in the sum. Complement variables that are 0 in that row.
Σ Notation
F(A,B,C) = Σm(1,3,5,7)
List the row indices (minterms) where F = 1.
Product of Sums (POS)
Structure
F = (A+B+C) · (A′+B+C′)
AND of OR terms (maxterms). Each term is a sum; the expression is their product.
Maxterm (M)
Row where F = 0
Include the row's OR term in the product. Complement variables that are 1 in that row.
Π Notation
F(A,B,C) = ΠM(0,2,4,6)
List the row indices (maxterms) where F = 0.
Minterm / Maxterm Relationship
Complement mᵢ = Mᵢ′
SOP ↔ POS Σm(…) = ΠM(remaining)
Total rows 2ⁿ for n variables
Simplification Steps
Step 1 Build truth table
Step 2 Identify 1-rows (SOP)
Step 3 Write minterms
Step 4 Simplify with K-Map
2-Variable K-Map
B=0 B=1
A=0 0 0
A=1 0 0

Click cells to toggle 0 / 1

3-Variable K-Map
A \ BC 00 01 11 10
0 0 0 0 0
1 0 0 0 0

Gray code ordering: 00 01 11 10

4-Variable K-Map
AB \ CD 00 01 11 10
00 0 0 0 0
01 0 0 0 0
11 0 0 0 0
10 0 0 0 0

Click to fill; group 1s in powers of 2

Grouping Rules
Group size 1, 2, 4, 8, 16 …
Largest first Always use the biggest valid groups
Wrap edges Top ↔ Bottom, Left ↔ Right
Each 1 covered Every 1 must be in ≥1 group
Don't cares (X) Use if it enlarges a group
Eliminated var Var changes in group → drops out
Operator Symbols
′
Operation Math Code / CS Gate shape
AND · && / &
OR + || / |
NOT Ā / A′ ! / ~
XOR ⊕ ^
XNOR ⊙ !(a^b)
NAND (a·b)′ !(a&b)
NOR (a+b)′ !(a|b)
Operator Precedence
1st NOT ( A′ ) Highest — evaluated first
2nd AND ( · ) Like multiplication
3rd XOR ( ⊕ ) After AND, before OR
4th OR ( + ) Lowest — like addition
( ) Parentheses Override any precedence
Quick Facts
Universal gates NAND, NOR
AND gate 3 NAND gates
OR gate 3 NOR gates
XOR from NAND 4 NAND gates
n-var minterms 2ⁿ total