DerivativeCalculus.com

Boolean Algebra Cheat Sheet

Complete reference for Computer Science, Digital Logic, and Discrete Mathematics

📚 Fundamental Laws & Identities

De Morgan's Laws
¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬B

Remember: Break the line, change the sign

Basic Identities
A ∧ 1 ≡ A
A ∨ 0 ≡ A
A ∧ 0 ≡ 0
A ∨ 1 ≡ 1
A ∧ ¬A ≡ 0
A ∨ ¬A ≡ 1
Idempotent Laws
A ∧ A ≡ A
A ∨ A ≡ A

Same variable AND/OR itself equals itself

Commutative Laws
A ∧ B ≡ B ∧ A
A ∨ B ≡ B ∨ A
Associative Laws
(A ∧ B) ∧ C ≡ A ∧ (B ∧ C)
(A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
Distributive Laws
A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
Absorption Laws
A ∨ (A ∧ B) ≡ A
A ∧ (A ∨ B) ≡ A
Double Negation
¬(¬A) ≡ A

⚡ Logic Gates Reference

AND Gate (∧)
A ∧ B
A ⋅ B
A & B

Output is 1 only if ALL inputs are 1

Truth Table:
ABA ∧ B
000
010
100
111
OR Gate (∨)
A ∨ B
A + B

Output is 1 if ANY input is 1

Truth Table:
ABA ∨ B
000
011
101
111
NOT Gate (¬)
¬A
A'
!A

Output is the opposite (complement)

Truth Table:
A¬A
01
10
NAND Gate
¬(A ∧ B)

AND followed by NOT

Truth Table:
AB¬(A ∧ B)
001
011
101
110
NOR Gate
¬(A ∨ B)

OR followed by NOT

Truth Table:
AB¬(A ∨ B)
001
010
100
110
XOR Gate (Exclusive OR)
A ⊕ B

Output is 1 if inputs are DIFFERENT

Truth Table:
ABA ⊕ B
000
011
101
110

🎯 Practical Examples & Simplification

Example 1: Simplify using De Morgan's Law

Original: ¬(P ∧ Q) ∨ ¬(¬R)

Step 1: Apply De Morgan's: (¬P ∨ ¬Q) ∨ R

Step 2: Remove double negation: (¬P ∨ ¬Q) ∨ R

Step 3: Simplify (Associative): ¬P ∨ ¬Q ∨ R

Simplified: ¬P ∨ ¬Q ∨ R

Example 2: Circuit Simplification

Circuit: (A ∧ B) ∨ (A ∧ ¬B) ∨ (¬A ∧ B)

Step 1: Factor A: A ∧ (B ∨ ¬B) ∨ (¬A ∧ B)

Step 2: B ∨ ¬B = 1: A ∧ 1 ∨ (¬A ∧ B)

Step 3: A ∧ 1 = A: A ∨ (¬A ∧ B)

Step 4: Apply Absorption: A ∨ B

Simplified Circuit: A ∨ B (Just an OR gate!)

💡 Pro Tips for Boolean Algebra
  1. Always check for common terms to factor first
  2. Use De Morgan's Laws to simplify negated expressions
  3. Look for XOR patterns: A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)
  4. Verify with truth tables when unsure about simplification
  5. Remember absorption laws can eliminate redundant terms
Useful Conversions
A → B ≡ ¬A ∨ B
A ↔ B ≡ (A → B) ∧ (B → A)
A ⊕ B ≡ (A ∨ B) ∧ ¬(A ∧ B)
A ⊕ B ≡ (A ∧ ¬B) ∨ (¬A ∧ B)