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} )