Discrete Mathematics

The reasoning toolkit the rest of computer science quietly assumes: logic, proof, sets and relations, counting, recurrences and the number theory behind cryptography.

If you remember nothing else

The contrapositive of p → q is ¬q → ¬p, and it is logically equivalent; the converse q → p is not.
p → q is false in exactly one case: p true and q false. A false premise makes the implication vacuously true.
An equivalence relation is reflexive, symmetric and transitive, and it partitions its set into disjoint classes.
Permutations count arrangements (order matters), combinations count selections (order does not): C(n,r) = P(n,r)/r!.
The pigeonhole principle: n+1 items in n boxes force some box to hold at least two — the basis of most 'prove there exist two…' questions.
The handshake lemma: the sum of all vertex degrees equals twice the number of edges, so the count of odd-degree vertices is always even.

8 chapters

1Propositional logic
2Predicate logic and quantifiers
3Proof techniques
4Sets, relations and functions
5Counting and combinatorics
6Graph theory
7Recurrence relations
8Number theory essentials

Propositional logic

A proposition is a declarative statement with a definite truth value. Connectives build compound propositions, and a truth table settles any question about them mechanically.

Connective	Symbol	Read as	True when
Negation	$\neg p$	not p	p is false
Conjunction	$p \land q$	p and q	both are true
Disjunction	$p \lor q$	p or q	at least one is true
Exclusive or	$p \oplus q$	p xor q	exactly one is true
Implication	$p \to q$	if p then q	always, except when p is true and q is false
Biconditional	$p \leftrightarrow q$	p if and only if q	both have the same truth value

Form	Statement	Equivalent to the original?
Original	$p \to q$	—
Converse	$q \to p$	No
Inverse	$\neg p \to \neg q$	No (it is the converse's contrapositive)
Contrapositive	$\neg q \to \neg p$	Yes — always

"If it rains, the ground is wet" does not mean "if the ground is wet, it rained" (converse). It does mean "if the ground is not wet, it did not rain" (contrapositive).

Equivalences worth memorising

Law	Form
De Morgan	$\neg (p \land q) \equiv \neg p \lor \neg q$ and $\neg (p \lor q) \equiv \neg p \land \neg q$
Distributive	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
Implication	$p \to q \equiv \neg p \lor q$
Contrapositive	$p \to q \equiv \neg q \to \neg p$
Absorption	$p \lor (p \land q) \equiv p$
Double negation	$\neg (\neg p) \equiv p$

Predicate logic and quantifiers

Propositional logic cannot express "every student passed" — it has no way to talk about individuals. Predicate logic adds predicates $P (x)$ and quantifiers over a domain.

Universal $\forall x P (x)$ — P holds for every element. A single counterexample makes it false.
Existential $\exists x P (x)$ — P holds for at least one element. One witness makes it true.
Negation rules: $\neg\forall x P (x) \equiv \exists x \neg P (x)$ , and $\neg\exists x P (x) \equiv \forall x \neg P (x)$ . Pushing a negation inward flips the quantifier.

Rule of inference	Form	Name
From $p \to q$ and $p$ , infer $q$	Affirm the premise	Modus ponens
From $p \to q$ and $\neg q$ , infer $\neg p$	Deny the conclusion	Modus tollens
From $p \to q$ and $q \to r$ , infer $p \to r$	Chain	Hypothetical syllogism
From $p \lor q$ and $\neg p$ , infer $q$	Eliminate	Disjunctive syllogism

Proof techniques

Technique	To prove	Method	Use when
Direct	$p \to q$	Assume p, derive q	The implication is straightforward
Contraposition	$p \to q$	Assume $\neg q$ , derive $\neg p$	The negation is easier to work with
Contradiction	Any statement s	Assume $\neg s$ , derive an absurdity	Proving something does not exist
Induction	$P (n)$ for all $n \geq n_{0}$	Base case, then $P (k) \Rightarrow P (k + 1)$	The claim is indexed by a natural number
Strong induction	$P (n)$ for all n	Assume $P (1) \dots P (k)$ , prove $P (k + 1)$	The step needs more than the previous case
Counterexample	$\neg\forall x P (x)$	Exhibit one x with $\neg P (x)$	Disproving a universal claim

Sets, relations and functions

The power set of a set with n elements has $2^{n}$ elements — including the empty set and the set itself.
Cardinality of a union: $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ (inclusion-exclusion).
The Cartesian product $A \times B$ has $∣ A ∣ \cdot ∣ B ∣$ ordered pairs.
A relation on A is any subset of $A \times A$ ; with n elements there are $2^{n^{2}}$ possible relations.

Property	Definition	Example
Reflexive	$\forall a$ , $(a, a) \in R$	"is equal to", "divides"
Symmetric	$(a, b) \in R \Rightarrow (b, a) \in R$	"is a sibling of"
Antisymmetric	$(a, b)$ and $(b, a)$ both in R $\Rightarrow a = b$	" $\leq$ ", "is a subset of"
Transitive	$(a, b)$ and $(b, c)$ in R $\Rightarrow (a, c) \in R$	" $<$ ", "is an ancestor of"

Function type	Condition	Consequence
Injective (one-to-one)	Distinct inputs give distinct outputs	$∣ A ∣ \leq ∣ B ∣$
Surjective (onto)	Every element of the codomain is hit	$∣ A ∣ \geq ∣ B ∣$
Bijective	Both	$∣ A ∣ = ∣ B ∣$ ; an inverse exists

Counting and combinatorics

Rule	Formula	Use
Product rule	$n_{1} \times n_{2}$	Independent sequential choices
Sum rule	$n_{1} + n_{2}$	Mutually exclusive alternatives
Permutation	$P (n, r) = \frac{n !}{( n - r )!}$	Arrange r of n — order matters
Combination	$C (n, r) = \frac{n !}{r ! ( n - r )!}$	Choose r of n — order does not matter
With repetition (arrange)	$n^{r}$	r positions, n choices each
With repetition (choose)	$C (n + r - 1, r)$	r items from n types, repeats allowed
Circular permutation	$(n - 1)!$	Seat n people around a table

Two principles that carry whole questions

Pigeonhole principle — placing $n + 1$ objects into $n$ boxes forces some box to contain at least two. Generalised: $n$ objects in $k$ boxes force some box to hold at least $⌈ n / k ⌉$ . Standard use: among any 13 people, two share a birth month.
Inclusion-exclusion — $∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣$ . Add the singles, subtract the pairs, add the triples, alternating.

Graph theory

Handshake lemma — $\sum_{v} de g (v) = 2∣ E ∣$ . Every edge contributes 2 to the total degree, so the number of odd-degree vertices is always even.
A complete graph $K_{n}$ has $n (n - 1) /2$ edges. A tree on n vertices has exactly $n - 1$ edges and is connected and acyclic — any two of those three properties imply the third.
A bipartite graph has no odd-length cycle; equivalently, it is 2-colourable.
A graph is planar if it can be drawn without crossings. Euler's formula: $V - E + F = 2$ for a connected planar graph. By Kuratowski's theorem, a graph is planar iff it contains no subdivision of $K_{5}$ or $K_{3, 3}$ .
By the four colour theorem, every planar graph is 4-colourable.

Recurrence relations

A recurrence defines a term from earlier terms. Solving it means finding a closed form — which for algorithm analysis is exactly the running time.

Substitution (iteration)
Expand the recurrence repeatedly until the pattern is visible, then apply the base case. $T (n) = T (n - 1) + n$ expands to $n + (n - 1) + \dots + 1 = n (n + 1) /2 = O (n^{2})$ .
Characteristic equation
For a linear homogeneous recurrence such as $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ , substitute $a_{n} = r^{n}$ to get $r^{2} - 5 r + 6 = 0$ , giving roots 2 and 3, so $a_{n} = A \cdot 2^{n} + B \cdot 3^{n}$ with A and B fixed by the initial conditions.
Master theorem
For divide-and-conquer recurrences $T (n) = a T (n / b) + f (n)$ , compare $f (n)$ against $n^{l o g_{b} a}$ and read off the case. Covered in full in the Data Structures & Algorithms subject.

Recurrence	Closed form	Arises in
$T (n) = T (n - 1) + 1$	$O (n)$	Linear search
$T (n) = T (n - 1) + n$	$O (n^{2})$	Bubble sort, insertion sort worst case
$T (n) = T (n /2) + 1$	$O (lo g n)$	Binary search
$T (n) = 2 T (n /2) + n$	$O (n lo g n)$	Mergesort
$T (n) = 2 T (n - 1) + 1$	$O (2^{n})$	Towers of Hanoi

Number theory essentials

$a \equiv b (mod m)$ means m divides $a - b$ . Congruences may be added and multiplied, but not divided freely.
Euclid's algorithm: $g cd (a, b) = g cd (b, a mod b)$ , terminating when the remainder is 0. It runs in $O (lo g min (a, b))$ .
$g cd (a, b) \times lcm (a, b) = a \times b$ .
Euler's totient $ϕ (n)$ counts integers in $1.. n$ coprime to n. For a prime p, $ϕ (p) = p - 1$ ; for distinct primes p and q, $ϕ (pq) = (p - 1) (q - 1)$ .
Fermat's little theorem: if p is prime and p does not divide a, then $a^{p - 1} \equiv 1 (mod p)$ .
A modular inverse of a mod m exists iff $g cd (a, m) = 1$ ; the extended Euclidean algorithm finds it.

CEuclid, both ways

int gcd(int a, int b) {              // iterative
    while (b) { int t = b; b = a % b; a = t; }
    return a;
}

int gcd_rec(int a, int b) {          // recursive - the definition itself
    return b == 0 ? a : gcd_rec(b, a % b);
}
// gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6

Discrete Mathematics

If you remember nothing else

1Propositional logic

Equivalences worth memorising

2Predicate logic and quantifiers

3Proof techniques

4Sets, relations and functions

5Counting and combinatorics