🧠 Logic & Proofs
💡 TRUTH TABLE TRICKS:
TRICK 1: n variables = 2ⁿ rows (3 vars = 8 rows)
TRICK 2: Fill columns left to right, simplest first
TRICK 3: For p→q: only FALSE when T→F
TRICK 4: For p↔q: TRUE when both match
TRICK 5: Double-check your final column twice!
Logical Connectives:
| Symbol |
Name |
When TRUE? |
| ¬p |
NOT |
When p is false |
| p ∧ q |
AND |
Both p and q true |
| p ∨ q |
OR |
At least one true |
| p → q |
IF-THEN |
Always, EXCEPT when p=T and q=F |
| p ↔ q |
IFF |
Both same truth value |
🔥 PROVING TAUTOLOGIES (Exam Method):
STEPS:
1. Convert p→q to ¬p∨q (implication law)
2. Apply De Morgan's to break ¬(...)
3. Use Associative/Commutative to rearrange
4. Find p∨¬p or q∨¬q (always = T)
5. Apply T∨anything = T (domination)
⚡ ALWAYS write which law you used!
Key Rules of Inference (MEMORIZE!):
| Rule |
Form |
Remember as... |
| Modus Ponens |
p→q, p ∴ q |
"If p then q, p is true, so q" |
| Modus Tollens |
p→q, ¬q ∴ ¬p |
"If p then q, not q, so not p" |
| Hypothetical Syllogism |
p→q, q→r ∴ p→r |
"Chain implications" |
| Disjunctive Syllogism |
p∨q, ¬p ∴ q |
"p or q, not p, so q" |
| Simplification |
p∧q ∴ p |
"If both, then either" |
De Morgan's Laws (USE CONSTANTLY!):
¬(p ∧ q) ≡ ¬p ∨ ¬q (break AND → OR)
¬(p ∨ q) ≡ ¬p ∧ ¬q (break OR → AND)
🎯 QUANTIFIER TRANSLATION TRICKS:
"All" → ∀ (for all)
"Some/There exists" → ∃ (exists)
"No/None" → ∀ ¬ or ¬∃
Negation Shortcuts:
¬(∀x P(x)) = ∃x ¬P(x) "Not all → Some not"
¬(∃x P(x)) = ∀x ¬P(x) "None → All not"
Exam Examples:
• "All students did not go" → ∀x ¬P(x)
• "Some students do not know" → ∃x ¬Q(x)
• "Some are BOTH studying AND didn't go" → ∃x (R(x) ∧ ¬P(x))
📦 Sets
🎯 IMPORTANT SETS (MEMORIZE!):
N = Natural numbers = {0, 1, 2, 3, ...}
Z = Integers = {..., −3, −2, −1, 0, 1, 2, 3, ...}
Z⁺ = Positive integers = {1, 2, 3, ...}
Q = Rational numbers (fractions p/q)
R = Real numbers (all decimals, √2, π, e)
R⁺ = Positive real numbers
C = Complex numbers {a + bi}
Set Operations:
- A ∪ B - union (all elements from either)
- A ∩ B - intersection (common elements only)
- A − B - difference (in A but NOT in B)
- Ā - complement (everything NOT in A)
- A × B - Cartesian product (ordered pairs)
💡 TRICK: Finding A and B from parts:
Given: A − B, B − A, A ∩ B
TRICK:
• A = (A − B) ∪ (A ∩ B) — everything in A!
• B = (B − A) ∪ (A ∩ B) — everything in B!
Exam Example:
A − B = {2, 4, 8}
B − A = {5, 10, 15}
A ∩ B = {3, 6, 9}
→ A = {2, 4, 8, 3, 6, 9}
→ B = {5, 10, 15, 3, 6, 9}
Power Set TRICK: P(A) = set of all subsets
If |A| = n, then |P(A)| = 2ⁿ
Example: A = {1, 2} → P(A) = {∅, {1}, {2}, {1,2}} → |P(A)| = 2² = 4
Set Identities (for proofs):
A ∪ ∅ = A, A ∩ U = A (Identity)
A ∪ U = U, A ∩ ∅ = ∅ (Domination)
A ∪ A = A, A ∩ A = A (Idempotent)
A ∪ B = B ∪ A (Commutative)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (Distributive)
⚡ QUICK TRICK - Inclusion-Exclusion:
|A ∪ B| = |A| + |B| − |A ∩ B|
Add both, subtract what you counted twice!
🔢 Number Theory
🔥 Prime Factorization Cheat Sheet:
✓ How to factor a number
- Divide by 2 until it no longer works
- Then divide by 3 until it stops
- Then 5, 7, 11, 13, ... (primes only)
- Stop when the last number is prime
⭐ For GCD and LCM:
GCD (greatest common divisor):
Take smallest exponents of shared primes.
LCM (least common multiple):
Take largest exponents of all primes.
Example from Exam:
753 = 3 × 251
45 = 3² × 5
GCD(753, 45) = 3¹ (smallest of shared)
LCM(753, 45) = 3² × 5 × 251 (largest of all)
Relatively Prime:
Two numbers are relatively prime if GCD = 1
(They share NO common prime factors)
Example: (100, 213)
100 = 2² × 5²
213 = 3 × 71
No shared primes → Relatively prime ✓
Division Algorithm:
a = bq + r, where 0 ≤ r < b
Modular Arithmetic:
a ≡ b (mod n) means n | (a − b)
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n
Caesar/Shift Cipher:
Encryption: f(x) = (x + k) mod 26
Decryption: f⁻¹(x) = (x − k) mod 26
Example from Exam:
Plain: "I am done..."
Cipher: "W oa rcbs..."
k = 14 (shift by 14 letters)
🎯 Mathematical Induction
🎯 THE 4-STEP FORMULA (ALWAYS!):
- Base Case: Prove P(1) or P(starting value) is true
- Inductive Hypothesis: ASSUME P(k) is true
- Inductive Step: PROVE P(k+1) is true using P(k)
- Conclusion: "Therefore P(n) is true for all n ≥ [base]"
💡 INDUCTION TRICKS:
TRICK 1: In step 3, write out P(k+1) completely first
TRICK 2: Look for P(k) hiding inside P(k+1)
TRICK 3: Factor or simplify to match the formula
TRICK 4: Always show algebra step-by-step in exams!
Example Pattern:
Want to prove: 1 + 2 + ... + n = n(n+1)/2
• Base: n=1 → 1 = 1(2)/2 = 1 ✓
• Assume: 1 + 2 + ... + k = k(k+1)/2
• Prove: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2
• [1 + 2 + ... + k] + (k+1) = k(k+1)/2 + (k+1)
• = (k+1)[k/2 + 1] = (k+1)(k+2)/2 ✓
Common Formulas to Prove:
1 + 2 + ... + n = n(n+1)/2
1² + 2² + ... + n² = n(n+1)(2n+1)/6
1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ − 1
1 + 3 + 5 + ... + (2n−1) = n²
⚡ QUICK TIP:
If stuck on inductive step, try:
1. Substitute P(k) immediately
2. Get common denominator
3. Factor out (k+1)
4. Simplify to match P(k+1)
🎲 Counting
Basic Rules:
- Sum Rule: n₁ ways OR n₂ ways → n₁ + n₂
- Product Rule: n₁ ways AND n₂ ways → n₁ × n₂
Permutations vs Combinations:
P(n,r) = n!/(n−r)! → Order MATTERS
C(n,r) = n!/(r!(n−r)!) → Order doesn't matter
When to use which?
• Arranging people in line? Permutation
• Selecting committee members? Combination
• Passwords/codes where ABC ≠ CAB? Permutation
• Choosing pizza toppings? Combination
• Exam: "sequence of best 5 parts" → Use Combination (11C5)
Password/Counting with Restrictions:
Exam Example: Password with:
• 1 special char (9 options)
• 1 capital letter (26 options)
• 1 small letter (26 options)
• 1 digit (10 options)
• Then 4 more from remaining 67 chars
• NO repetition allowed
Answer: 9 × 26 × 26 × 10 × 67 × 66 × 65 × 64
(Multiply because it's position 1 AND 2 AND 3...)
Binomial Theorem:
(x + y)ⁿ = Σ C(n,k) · xⁿ⁻ᵏ · yᵏ
Exam Example: (−3x + 2y)³
= 3C0(−3x)³(2y)⁰ + 3C1(−3x)²(2y)¹ + 3C2(−3x)¹(2y)² + 3C3(−3x)⁰(2y)³
= −27x³ + 54x²y − 36xy² + 8y³
🔁 Recurrence Relations
❤️ HOW TO IDENTIFY (MEMORIZE THIS!):
Linear?
Must look like a sum of c·aₙ₋ₖ
NO powers, NO products of a's, NO functions.
Homogeneous?
NO constant term.
Every term involves some previous a.
Constant Coefficients?
All coefficients are plain numbers (not depending on n).
Degree:
Largest subscript gap (n − k).
Examples from Exam:
| Recurrence |
Linear? |
Homogeneous? |
Degree |
| aₙ = 5aₙ₋₁₀ |
✓ YES |
✓ YES |
10 |
| aₙ = 17aₙ₋₃ + 39n |
✓ YES |
✗ NO (has 39n) |
3 |
| aₙ = −6aₙ₋₁ − 9aₙ₋₂ |
✓ YES |
✓ YES |
2 |
| aₙ = 7aₙ₋₁aₙ₋₂ |
✗ NO (product) |
✓ YES |
2 |
| aₙ = 4aₙ₋₁ + 5aₙ₋₅ + 7aₙ₋₇ |
✓ YES |
✓ YES |
7 |
Solving Linear Homogeneous (Degree 2):
Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂
- Write characteristic equation: r² − c₁r − c₂ = 0
- Solve for roots r₁, r₂
- If r₁ ≠ r₂: aₙ = α₁r₁ⁿ + α₂r₂ⁿ
- If r₁ = r₂ = r: aₙ = α₁rⁿ + α₂nrⁿ
- Use initial conditions to find α₁, α₂
Nonhomogeneous:
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + F(n)
Solution = aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾
If F(n) is linear (cn + d): Try aₙ⁽ᵖ⁾ = An + B
If F(n) is exponential (c·sⁿ): Try aₙ⁽ᵖ⁾ = A·sⁿ
Verifying a Solution:
Given: aₙ = −2ⁿ⁺¹ for aₙ = 3aₙ₋₁ + 2ⁿ
1. Find aₙ₋₁ = −2ⁿ
2. Substitute: −2ⁿ⁺¹ = 3(−2ⁿ) + 2ⁿ
3. Simplify: −2ⁿ⁺¹ = −3·2ⁿ + 2ⁿ = 2ⁿ(−3 + 1) = −2·2ⁿ = −2ⁿ⁺¹ ✓
🔗 Relations
Properties (R on set A):
- Reflexive: (a,a) ∈ R for all a ∈ A
All diagonal entries in matrix = 1, all loops in graph
- Irreflexive: (a,a) ∉ R for all a ∈ A
No diagonal entries = 1, no loops
- Symmetric: (a,b) ∈ R → (b,a) ∈ R
Matrix = Matrix transpose, edges go both ways
- Antisymmetric: (a,b) ∈ R and (b,a) ∈ R → a = b
No two-way edges between DIFFERENT vertices
- Transitive: (a,b), (b,c) ∈ R → (a,c) ∈ R
If path a→b→c exists, direct edge a→c must exist
Equivalence Relation:
Must be Reflexive + Symmetric + Transitive
Exam Example - Checking Properties:
Given graph: R = {(a,b), (b,e), (c,c), (c,b), (c,d), (d,c), (e,e), (e,d), (e,a)}
Reflexive? NO - (a,a), (b,b), (d,d) missing
Irreflexive? NO - (c,c), (e,e) exist
Symmetric? NO - (a,b) exists but (b,a) doesn't
Antisymmetric? NO - both (c,d) and (d,c) exist
Transitive? NO - (a,b) and (b,e) exist but (a,e) doesn't
Matrix Representation:
- M[i][j] = 1 if (aᵢ, aⱼ) ∈ R, else 0
- Rows = from vertices, Columns = to vertices
- Reflexive: All diagonal = 1
- Symmetric: M = Mᵀ
Composition (Q ∘ R):
(a,c) ∈ Q ∘ R if ∃b: (a,b) ∈ R AND (b,c) ∈ Q
Exam Example:
Q = {(1,2), (2,3), (3,2), (3,3)}
R = {(1,1), (2,3), (3,2), (1,2), (2,2)}
Find pairs where R connects to Q:
(1,2)∈R and (2,3)∈Q → (1,3)∈Q∘R
Result: {(1,2), (2,2), (2,3), (3,3), (1,3)}
Closures:
- Reflexive Closure: Add (a,a) for all a not already there
- Symmetric Closure: Add (b,a) for every (a,b)
- Transitive Closure: Keep adding (a,c) whenever (a,b) and (b,c) exist until no more can be added
⚡ Quick Reference & Formulas
Important Sequences & Summations:
Σ(k=1 to n) k = n(n+1)/2
Σ(k=1 to n) k² = n(n+1)(2n+1)/6
Σ(k=0 to n) rᵏ = (rⁿ⁺¹ − 1)/(r − 1), r ≠ 1
Σ(k=0 to n) 2ᵏ = 2ⁿ⁺¹ − 1
Exam-Style Summation:
Example: Σ(i=0 to 8, i even) 2·(−3)ⁱ
= 2·[(−3)⁰ + (−3)² + (−3)⁴ + (−3)⁶ + (−3)⁸]
= 2·[1 + 9 + 81 + 729 + 6561]
= 2·7381 = 14,762
Matrix Multiplication:
For A(m×n) · B(n×p) = C(m×p)
C[i][j] = Σ A[i][k] · B[k][j]
Example from Exam:
[3 5] [6 7 0] [38 11 0]
[0 9] · [4 -2 0] = [36 -18 0]
[-8 1] [-44 -58 0]
Floor & Ceiling:
⌊x⌋ = largest integer ≤ x
⌈x⌉ = smallest integer ≥ x
Example: ⌊−3.1⌋ + ⌈1.3⌉ = −4 + 2 = −2
Special Values:
0! = 1
C(n,0) = C(n,n) = 1
C(n,1) = C(n,n−1) = n
C(n,k) = C(n, n−k)
Cartesian Product:
A × B × C = all ordered triples (a,b,c)
If |A|=3, |B|=2, |C|=2 → |A×B×C| = 3·2·2 = 12 elements
Example: {C1,C2,C3} × {M1,M2} × {AI1,AI2}
= {(C1,M1,AI1), (C1,M1,AI2), (C1,M2,AI1), ...}
❌ Common Mistakes to Avoid:
- ❌ Using P(n,r) when order doesn't matter → use C(n,r)
- ❌ Forgetting to check ALL vertices for reflexive/irreflexive
- ❌ Thinking symmetric = not antisymmetric (WRONG! Can be both, neither, or one)
- ❌ ¬(p → q) ≠ ¬p → ¬q (correct: ¬(p → q) ≡ p ∧ ¬q)
- ❌ |A ∪ B| ≠ |A| + |B| (must subtract |A ∩ B|)
- ❌ Confusing "homogeneous" with "has constant coefficients"
- ❌ In proofs: not stating which inference rule you used
- ❌ For composition: wrong order matters! Q∘R ≠ R∘Q