Cheat Sheet — Discrete Math Speedrun

Printing tip: Use your browser's print dialog (Cmd/Ctrl + P). Sidebar and navigation are automatically hidden, two-column layout preserved. Use "More settings → Margins: Minimum" to fit on fewer pages.

1 Logic

Connectives

Symbol	True when
$\lnot p$	$p$ false
$p \land q$	both true
$p \lor q$	at least one true
$p \oplus q$	exactly one true
$p \to q$	except $T \to F$
$p \leftrightarrow q$	same value

Must-know equivalences

$p \to q \;\equiv\; \lnot p \lor q$

$\lnot(p \to q) \;\equiv\; p \land \lnot q$

$p \to q \;\equiv\; \lnot q \to \lnot p$ (contrapositive)

$\lnot(p \land q) \;\equiv\; \lnot p \lor \lnot q$ (De Morgan)

$\lnot(p \lor q) \;\equiv\; \lnot p \land \lnot q$ (De Morgan)

$p \leftrightarrow q \;\equiv\; (p\to q) \land (q\to p)$

Quantifier negation

$\lnot \forall x\,P(x) \;\equiv\; \exists x\, \lnot P(x)$

$\lnot \exists x\,P(x) \;\equiv\; \forall x\, \lnot P(x)$

Push $\lnot$ inward; flip each quantifier; negate body.

English to logic

"$p$ only if $q$" $\Rightarrow$ $p \to q$
"$p$ if $q$" $\Rightarrow$ $q \to p$
"$p$ unless $q$" $\Rightarrow$ $\lnot q \to p \equiv p \lor q$
"All $A$ are $B$" $\Rightarrow$ $\forall x\,(A(x)\to B(x))$
"Some $A$ is $B$" $\Rightarrow$ $\exists x\,(A(x)\land B(x))$

Tautology / Satisfiability

Tautology: true under every assignment
Satisfiable: true under at least one
$\varphi$ unsatisfiable $\iff$ $\lnot\varphi$ tautology

K-maps

Column order: Gray code $00, 01, 11, 10$
Groups are rectangles of $2^k$ cells, all 1s
Group as large as possible, use fewest groups
Edges wrap around (adjacent left↔right, top↔bottom)
Checkerboard 1s pattern $\Rightarrow$ XOR (no reduction)

Bit propositions ($x = x_3 x_2 x_1 x_0$)

$x \geq 8$: $x_3$
$x$ divisible by $2$: $\lnot x_0$
$x$ divisible by $4$: $\lnot x_0 \land \lnot x_1$
$x = y$: $\bigwedge_i (x_i \leftrightarrow y_i)$

2 Proofs

Methods at a glance

Method	Use when
Direct	Hypothesis is concrete
Contrapositive	$\lnot q$ is concrete
Contradiction	$\lnot q$ leads to impossibility
Cases	Universe splits naturally
Induction	Statement about all $n$
Counterex.	Disproving "$\forall$"

Rules of inference (propositional)

MP: $p,\;p\to q \;\therefore\; q$
MT: $\lnot q,\;p\to q \;\therefore\; \lnot p$
HS: $p\to q,\;q\to r \;\therefore\; p\to r$
DS: $p\lor q,\;\lnot p \;\therefore\; q$
Add: $p \;\therefore\; p\lor q$
Simp: $p\land q \;\therefore\; p$
Conj: $p,q \;\therefore\; p\land q$
Resolution: $p\lor q,\;\lnot p\lor r \;\therefore\; q\lor r$

Quantified inference

UI: $\forall x\,P(x) \;\therefore\; P(c)$, any $c$
UG: $P(c)$ for arbitrary $c$ $\;\therefore\; \forall x\,P(x)$
EI: $\exists x\,P(x) \;\therefore\; P(c)$ for a new $c$
EG: $P(c) \;\therefore\; \exists x\,P(x)$

Fallacies (don't!)

Affirming consequent: $p\to q,\;q \not\Rightarrow p$
Denying antecedent: $p\to q,\;\lnot p \not\Rightarrow \lnot q$

Induction skeleton

Base: Show $P(n_0)$.
Step: Assume $P(k)$ (IH); derive $P(k+1)$.
Cite the induction principle.

Strong induction: assume $P(n_0), \ldots, P(k)$.

Loop invariants — 3 things

Init — invariant holds before loop
Maintenance — preserved per iteration
Termination — exit condition + invariant $\Rightarrow$ postcondition

Pigeonhole

$n$ items in $m$ boxes, $n > m$ $\Rightarrow$ some box has $\geq 2$ items. Generalised: $\geq \lceil n/m \rceil$.

Equivalence chains

To prove $p_1, \ldots, p_n$ equivalent, show cycle $p_1 \to p_2 \to \cdots \to p_n \to p_1$.

3 Set Theory

Notation

$|\mathcal{P}(A)| = 2^{|A|}$ (finite $A$)
$\{x \in A : P(x)\}$ — safe (separation axiom)
$\{x : P(x)\}$ — unsafe (Russell)

Russell's paradox

$R = \{S : S \notin S\}$ — leads to contradiction in both cases $R \in R$ and $R \notin R$.

Inclusion–exclusion (3 sets)

$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$

Countable

$\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{N}^k$ all countable
Subset of countable is countable
Countable union of countable is countable
Finite Cartesian product of countables is countable
Programs / formulas / finite strings over finite Σ — countable

Uncountable

$\mathbb{R}$, $(0,1)$, $\{0,1\}^\mathbb{N}$, $\mathcal{P}(\mathbb{N})$, functions $\mathbb{N}\to\mathbb{N}$
Proof template (Cantor diagonal): assume listed, build new element that differs from $n$-th item in $n$-th position $\Rightarrow$ contradiction

Cantor's theorem

$|\mathcal{P}(S)| > |S|$ for every set $S$.

Computability link

Programs countable; functions $\mathbb{N}\to\{0,1\}$ uncountable
$\Rightarrow$ most functions are uncomputable
Halting problem undecidable (diagonalisation)

Showing countability

Construct (a) bijection $\mathbb{N}\to X$, OR (b) injection $X \to \mathbb{N}$, OR (c) surjection $\mathbb{N} \to X$.

4 Abstract Algebra

Group axioms (CAII)

Closure: $a,b\in G \Rightarrow a*b \in G$
Associativity: $(a*b)*c = a*(b*c)$
Identity: $\exists e,\; e*a = a*e = a$
Inverse: $\forall a,\; \exists a^{-1}$

Abelian: $a*b = b*a$.

Standard groups

Group	Order
$(\mathbb{Z}_n, +_n)$	$n$, abelian, cyclic
$(\mathbb{Z}_n^*, \times_n)$	$\varphi(n)$, abelian
$(\mathbb{Z}_p^*, \times)$	$p-1$, cyclic
$D_n$	$2n$, non-abelian for $n\geq 3$
$S_n$	$n!$, non-abelian for $n\geq 3$

Order facts

In $\mathbb{Z}_n$: $\text{ord}(a) = n/\gcd(a,n)$
$a^m = e \;\Rightarrow\; \text{ord}(a) \mid m$
Lagrange: $|H|$ divides $|G|$
Corollary: $\text{ord}(a) \mid |G|$
If $|G| = p$ prime: $G$ cyclic

Cyclic generators of $\mathbb{Z}_n$

$\{k : \gcd(k,n)=1\}$ — exactly $\varphi(n)$ generators.

Euler's totient $\varphi$

$\varphi(p) = p-1$ for prime $p$
$\varphi(p^k) = p^k - p^{k-1}$
$\varphi(mn) = \varphi(m)\varphi(n)$ if $\gcd(m,n)=1$

Fermat's little theorem

$p$ prime, $\gcd(a,p)=1$: $\; a^{p-1} \equiv 1 \pmod{p}$

Ring / Field

Ring: $(R,+)$ abelian group, $(R,\cdot)$ associative, distributive
Field: commutative ring with $1$; every nonzero has inverse
$\mathbb{Z}_n$ field $\iff$ $n$ prime
$\mathbb{Z}, R[x]$ never fields ($x$ has no inverse in $R[x]$)

Primitive root test (mod $p$)

Factor $p-1 = q_1^{a_1}\cdots q_k^{a_k}$. For each prime $q_i$:

If $g^{(p-1)/q_i} \not\equiv 1 \pmod p$ for all $i$, then $g$ is primitive.

Diffie–Hellman

Public: prime $p$, primitive root $g$
Alice picks $a$, sends $A = g^a \bmod p$
Bob picks $b$, sends $B = g^b \bmod p$
Shared key $K = B^a = A^b = g^{ab} \bmod p$

Security: discrete log (finding $a$ from $g^a$) is hard.

5 Advanced Counting

Linear homogeneous recurrence

$a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$, $\;c_k \neq 0$.

Characteristic equation

$r^k - c_1 r^{k-1} - \cdots - c_k = 0$

Distinct roots $r_1,\ldots,r_k$: $\;a_n = \sum_i \alpha_i r_i^n$
Root $r$ multiplicity $m$: $\;(\alpha_0 + \alpha_1 n + \cdots + \alpha_{m-1} n^{m-1})r^n$

Non-homogeneous particular guess

RHS $F(n)$	Guess
Polynomial deg $d$	Polynomial deg $d$
$\alpha s^n$, $s$ not a root	$q s^n$
$\alpha s^n$, $s$ root mult $m$	$q n^m s^n$

Master Theorem

$T(n) = a T(n/b) + f(n)$, let $c^* = \log_b a$.

Case 1: $f(n) = O(n^{c^*-\epsilon})$ $\;\Rightarrow\; T = \Theta(n^{c^*})$
Case 2: $f(n) = \Theta(n^{c^*})$ $\;\Rightarrow\; T = \Theta(n^{c^*} \log n)$
Case 3: $f(n) = \Omega(n^{c^*+\epsilon})$ + regularity $\;\Rightarrow\; T = \Theta(f(n))$

Algorithmic examples

Merge sort: $T = 2T(n/2)+n \Rightarrow \Theta(n\log n)$
Binary search: $T = T(n/2)+1 \Rightarrow \Theta(\log n)$
Tower of Hanoi: $H_n = 2H_{n-1}+1 \Rightarrow 2^n - 1$

Growth hierarchy

$1 \ll \log\log n \ll \log n \ll n^\epsilon \ll n \ll n\log n \ll n^c \ll c^n \ll n! \ll n^n$

GF dictionary

Sequence	GF
$1, 1, 1, \ldots$	$\dfrac{1}{1-x}$
$1, c, c^2, \ldots$	$\dfrac{1}{1-cx}$
$0, 1, 2, 3, \ldots$	$\dfrac{x}{(1-x)^2}$
$\binom{n}{k}_k$	$(1+x)^n$
$\binom{n+k-1}{k}_k$	$\dfrac{1}{(1-x)^n}$

Counting recipe

Per-object GF $\times$ per-object GF $\times \cdots$ = total GF. Coefficient of $x^n$ = answer.

Solving recurrence via GF

Multiply recurrence by $x^n$, sum over $n$
Express in terms of $G(x) = \sum a_n x^n$
Solve algebraically for $G(x)$
Extract coefficients (partial fractions)

6 Graph Theory

Handshake lemma

$\sum_{v \in V} \deg(v) = 2|E|$

Corollary: #(odd-degree vertices) is even.

Graph families

Graph	$\|V\|$	$\|E\|$	Degree
$K_n$	$n$	$\binom{n}{2}$	$n-1$
$C_n$	$n$	$n$	$2$
$W_n$	$n+1$	$2n$	$n$ / $3$
$Q_n$	$2^n$	$n\cdot 2^{n-1}$	$n$
$K_{m,n}$	$m+n$	$mn$	$n$ / $m$

Bipartite

Bipartite $\iff$ no odd cycle $\iff$ 2-colourable
$K_n$ bipartite $\iff$ $n \leq 2$
$C_n$ bipartite $\iff$ $n$ even
$Q_n$ always bipartite (bit-parity)
$W_n$ never bipartite (triangle through hub)
$K_{m,n}$ always bipartite

Edge bound (bipartite simple)

$e \leq v^2 / 4$

Euler paths/circuits

Connected graph:

Euler circuit iff every vertex has even degree
Euler path (non-circuit) iff exactly 2 vertices have odd degree (start & end)
Königsberg fails: 4 odd-degree vertices

Hamilton paths/cycles

No easy degree test (NP-complete in general)
Dirac: $\deg(v) \geq n/2 \;\forall v,\; n\geq 3 \Rightarrow$ Hamilton cycle
Ore: $\deg(u) + \deg(v) \geq n$ for non-adj. $u,v$ $\Rightarrow$ Hamilton cycle
$K_n$ ($n\geq 3$), $C_n$, $W_n$, $Q_n$ ($n\geq 2$) all Hamiltonian
$K_{m,n}$ Hamilton cycle $\iff$ $m = n$

Hall's marriage theorem

Bipartite $G = V_1 \cup V_2$ has matching saturating $V_1$ iff $|N(S)| \geq |S|$ for every $S \subseteq V_1$.

Connectivity

Cut vertex / bridge: removal disconnects
In a tree, every internal vertex is a cut vertex; every edge a bridge
Strongly connected (directed): path both ways between every pair

Quick-recall mnemonics

The 4 group axioms — "CAII"

Closure, Associativity, Identity, Inverse.

Negating "$\forall \exists$"

$\lnot\forall\exists P \equiv \exists\forall\lnot P$. Flip every quantifier; negate body.

Master Theorem in one breath

Compute $c^* = \log_b a$. If $f$ smaller than $n^{c^*}$ → answer $n^{c^*}$. If equal → multiply by $\log n$. If bigger → answer is $f(n)$.

Euler in 3 words

"Count odd degrees." 0 → circuit, 2 → path, else neither.

Choosing a proof method

$\lnot q$ concrete → contrapositive. $\lnot q$ impossible → contradiction. About all $n$ → induction. Splits naturally → cases.

$\mathbb{Z}_n$ generators

Those $k$ with $\gcd(k,n)=1$. Count = $\varphi(n)$.