Quick Revision

Sets & Venn Diagrams

• Symbols:

  • $A \cup B$ : Union ($A$ or $B$)
  • $A \cap B$ : Intersection ($A$ and $B$)
  • $A - B$ : Difference ($A$ but not $B$)
  • $A^c$ : Complement
  • $A \subseteq B$ : Subset
  • $x \in A$ : Element of
  • $U$ : Universal Set

• Formulas:

  • $n(A \cup B) = n(A) + n(B) - n(A \cap B)$
  • Only $A = n(A) - n(A \cap B)$
  • Neither $= \text{Total} - n(A \cup B)$
  • At least one $= n(A \cup B)$
  • Exactly one $=$ Only $A +$ Only $B$

• Three sets:

  • $n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)$
  • Only $A = n(A) - [n(A \cap B\ \text{only}) + n(A \cap C\ \text{only}) + n(A \cap B \cap C)]$
  • Exactly two $= (A \cap B\ \text{only}) + (A \cap C\ \text{only}) + (B \cap C\ \text{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 $\to$ formula true for all natural numbers

• Useful formulas:

  • $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$
  • $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$
  • $1^3 + 2^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2$
  • $1 + 3 + 5 + \cdots + (2n-1) = n^2$
  • $0! = 1$
  • Fibonacci: $F_0 = 0$, $F_1 = 1$

Relations & Functions

• Properties:
  • Reflexive: $(a,a)$
  • Symmetric: $(a,b) \to (b,a)$
  • Transitive: $(a,b),(b,c) \to (a,c)$

If all three $\to$ Equivalence Relation

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

Logic & Proofs

• Operators:

  • $\neg p$ : NOT
  • $p \wedge q$ : AND (both true)
  • $p \vee q$ : OR (at least one true)
  • $p \to q$ : If $p$ then $q$ (implication)
  • $p \leftrightarrow q$ : $p$ if and only if $q$ (biconditional)
  • $p \oplus q$ : XOR (exactly one true) $= (p \vee q) \wedge \neg(p \wedge 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 \to q \equiv \neg p \vee q$
  • $p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)$
  • $\neg(p \vee q) \equiv \neg p \wedge \neg q$ (De Morgan's)
  • $\neg(p \wedge q) \equiv \neg p \vee \neg q$ (De Morgan's)
  • $p \vee \neg p \equiv$ Tautology
  • $p \wedge \neg p \equiv$ Contradiction

• Expression Trees:

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

• Combinational Circuits:

  • AND gate: $\wedge$
  • OR gate: $\vee$
  • NOT gate: $\neg$
  • Translate logical expressions to circuits

Counting (P & C)

• Order matters:

  • $nPr = \frac{n!}{(n-r)!}$

• Order doesn't matter:

  • $nCr = \frac{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 $K_n = \frac{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 $\to$ at least one box has $2+$ objects
• Generalized: To guarantee $k+1$ objects in one of $n$ boxes:
  • Minimum $= k \times n + 1$
  • Example: 5 balls of same color from 3 colors $\to 4 \times 3 + 1 = 13$ draws

---

IUS Preps - Your Academic Success Partner