# Discrete Mathematics — Master Cheat Sheet

Logic, Proofs, Set Theory, Functions & Relations, Number Theory, etc

Technology: **Mathematics**

---

# Discrete Mathematics — Master Cheat Sheet

---

## 1. Mathematical Notation & Logic

### Common Sets

- \( \mathbb{N} \): naturals {0,1,2,…}
- \( \mathbb{Z} \): integers
- \( \mathbb{Q} \): rationals
- \( \mathbb{R} \): reals
- \( \mathbb{C} \): complex numbers

### Logical Connectives

- \( \land \): AND
- \( \lor \): OR
- \( \lnot \): NOT
- \( \implies \): implies
- \( \iff \): if and only if

### Quantifiers

- \( \forall \): for all
- \( \exists \): there exists

---

## 2. Proof Techniques

### Direct Proof

Assume hypothesis, apply definitions/theorems, conclude.

### Contrapositive

Prove \( \neg Q \implies \neg P \) instead of \( P \implies Q \).

### Contradiction

Assume statement is false, reach contradiction.

### Induction

- Base case
- Inductive step: Assume \( P(k) \), prove \( P(k+1) \).

---

## 3. Set Theory

- **Subset:** \( A \subseteq B \iff \forall x (x \in A \implies x \in B) \)
- **Union:** \( A \cup B = \{ x : x \in A \lor x \in B \} \)
- **Intersection:** \( A \cap B = \{ x : x \in A \land x \in B \} \)
- **Complement:** \( \overline{A} = \{ x : x \notin A \} \)
- **Difference:** \( A \setminus B = \{ x : x \in A \land x \notin B \} \)
- **Cartesian Product:** \( A \times B = \{ (a,b) : a \in A, b \in B \} \)
- **Power Set:** \( \mathcal{P}(A) \)

**Laws:** Commutative, associative, distributive, De Morgan’s:

\( \overline{A \cup B} = \overline{A} \cap \overline{B} \)

---

## 4. Functions & Relations

- Function: \( f: A \to B \), \( f(a) \) well-defined for all \( a \in A \)
- **Injective (1–1):** \( f(a)=f(b) \implies a=b \)
- **Surjective (onto):** \( \forall b \in B, \exists a \in A: f(a)=b \)
- **Bijective:** injective + surjective

**Relations:**

- Reflexive: \( aRa \)
- Symmetric: \( aRb \implies bRa \)
- Transitive: \( aRb \land bRc \implies aRc \)
- **Equivalence relation:** reflexive + symmetric + transitive

---

## 5. Number Theory

- **Division Algorithm:** \( \forall a,b>0, \exists! q,r \) with \( a=bq+r, 0 \le r < b \)
- **Modular Arithmetic:** \( a \equiv b \pmod{m} \iff m \mid (a−b) \)
- **GCD & LCM:** \( \gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab \)
- **Euclidean Algorithm:** \( \gcd(a,b) = \gcd(b, a \bmod b) \)
- **CRT:** solve systems of congruences with coprime moduli

---

## 6. Counting & Combinatorics

- **Permutations:** \( P(n,k) = \frac{n!}{(n-k)!} \)
- **Combinations:** \( \binom{n}{k} = \frac{n!}{k!(n-k)!} \)
- **Binomial Theorem:** \( (x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k} \)
- **Inclusion–Exclusion:** \( \|A \cup B\| = \|A\| + \|B\| - \|A \cap B\| \)

---

## 7. Graph Theory

- **Graph:** \( G=(V,E) \), \( V \) = vertices, \( E \) = edges
- **Degree:** \( \deg(v) = # \text{ edges incident to } v \)
- **Handshaking Lemma:** \( \sum_{v \in V} \deg(v) = 2\|E\| \)
- **Complete Graph:** \( K_n \), edges between every vertex pair
- **Cycle:** \( C_n \), **Path:** \( P_n \), **Tree:** connected + acyclic
- **Bipartite:** vertices split into \( U,W \), no edges inside \( U \) or \( W \)
  - **Test:** No odd cycles
- **Eulerian Path:** visits every edge exactly once
  - Exists iff connected & exactly 0 or 2 odd-degree vertices
- **Eulerian Circuit:** all degrees even

---

## 8. Asymptotics

**Definitions:**

- \( O(g(n)) \): \( f(n) \) grows ≤ const × \( g(n) \)
- \( \Omega(g(n)) \): \( f(n) \) grows ≥ const × \( g(n) \)
- \( \Theta(g(n)) \): both \( O \) and \( \Omega \)
- \( o(g(n)) \): grows strictly slower
- \( \omega(g(n)) \): grows strictly faster

**Common growth rates:**

\( 1 \ll \log n \ll n^a \ll n^k \ll c^n \ll n! \)

---

## 9. Invariants & Monovariants

- **Invariant:** Property unchanged by operations (e.g., parity)
- **Monovariant:** Quantity that always increases or decreases until stopping

**Example Invariant:** Domino tiling — difference between black/white squares stays constant.

---

## 10. Proof Templates

### Direct

1. State assumptions
2. Apply definitions/theorems
3. Conclude result

### Contradiction

1. Assume negation
2. Derive impossibility

### Induction

1. Base case true
2. Assume \( P(k) \)
3. Prove \( P(k+1) \)

---

## 11. Common Pitfalls to Avoid

- Forgetting to state base case in induction
- Misusing \( \implies \) vs. \( \iff \)
- Ignoring domain restrictions in quantifiers
- Forgetting to prove both directions for \( \iff \)

---

## 12. Quick Reference Equations

- \( \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)
- \( \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \)
- \( \sum_{i=1}^{n} i^3 = \left[\frac{n(n+1)}{2}\right]^2 \)
- \( \gcd(a,b) = \gcd(b, a \bmod b) \)
- \( \|E(K_n)\| = \frac{n(n-1)}{2} \)

---