Quick Revision

Sets & Venn Diagrams

• Symbols:

  • A ∪ B : Union (A or B)
  • A ∩ B : Intersection (A and B)
  • A − B : Difference (A but not B)
  • Aᶜ : Complement
  • A ⊆ B : Subset
  • ∈ : Element of
  • U : Universal Set

• Formulas:

  • n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
  • Only A = n(A) − n(A ∩ B)
  • Neither = Total − n(A ∪ B)
  • At least one = n(A ∪ B)
  • Exactly one = Only A + Only B

• Three sets:

  • n(A ∪ B ∪ C) = n(A)+n(B)+n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C)
  • Only A = n(A) − [n(A∩B only) + n(A∩C only) + n(A∩B∩C)]
  • Exactly two = (A∩B only) + (A∩C only) + (B∩C only)

• Power set:

  • If n(A) = k, total subsets = 2^k

Mathematical Induction

• Steps:

  • 1. Base Case (check n = 0 or n = 1)
  • 2. Inductive Hypothesis: Assume true for n = k
  • 3. Inductive Step: Prove true for n = k + 1
  • If both hold → formula true for all natural numbers

• Useful formulas:

  • 1 + 2 + ... + n = n(n+1)/2
  • 1² + 2² + ... + n² = n(n+1)(2n+1)/6
  • 1³ + 2³ + ... + n³ = [n(n+1)/2]²
  • 1 + 3 + 5 + ... + (2n−1) = n²
  • 0! = 1
  • Fibonacci: F0 = 0, F1 = 1

Relations & Functions

• Properties:
  • Reflexive: (a,a)
  • Symmetric: (a,b) → (b,a)
  • Transitive: (a,b),(b,c) → (a,c)

If all three → Equivalence Relation

• Function:
  • Every input has exactly one output
  • Injective: no repeated outputs
  • Surjective: covers full target set

Logic & Proofs

• Operators:

  • ¬p : NOT
  • p ∧ q : AND (both true)
  • p ∨ q : OR (at least one true)
  • p → q : If p then q (implication)
  • p ↔ q : p if and only if q (biconditional)
  • p ⊕ q : XOR (exactly one true) = (p ∨ q) ∧ ¬(p ∧ q)

• Proposition:

  • Declarative statement with TRUE/FALSE value
  • Not propositions: questions, commands, exclamations, variables

• Types:

  • Tautology: Always TRUE
  • Contradiction: Always FALSE
  • Contingency: Sometimes TRUE, sometimes FALSE

• Equivalences:

  • p → q ≡ ¬p ∨ q
  • p ↔ q ≡ (p → q) ∧ (q → p)
  • ¬(p ∨ q) ≡ ¬p ∧ ¬q (De Morgan's)
  • ¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan's)
  • p ∨ ¬p ≡ Tautology
  • p ∧ ¬p ≡ Contradiction

• Expression Trees:

  • Show operator hierarchy/precedence
  • Root = main operator
  • Leaves = variables

• Combinational Circuits:

  • AND gate: ∧
  • OR gate: ∨
  • NOT gate: ¬
  • Translate logical expressions to circuits

Counting (P & C)

• Order matters:

  • nPr = n!/(n-r)!

• Order doesn’t matter:

  • nCr = n!/(r!(n-r)!)

• Repetition allowed:

  • n^r

• Circular permutations:

  • (n−1)!

Graph Theory

• Sum of degrees:

  • Sum deg(v) = 2E

• Trees:

  • Edges = n − 1

• Complete graph:

  • Edges in Kn = n(n−1)/2

• Odd-degree rule:

  • Odd-degree vertices always even in number

• TSP (Travelling Salesman Problem):

  • Find minimum cost Hamiltonian cycle
  • Visit each vertex exactly once
  • Return to starting vertex
  • Use greedy approach or full enumeration

Pigeonhole Principle

• Basic: If n+1 objects in n boxes → at least one box has 2+ objects
• Generalized: To guarantee k+1 objects in one of n boxes:
  • Minimum = k × n + 1
  • Example: 5 balls of same color from 3 colors → 4×3+1 = 13 draws

---

IUS Preps - Your Academic Success Partner