Discrete Mathematics

Discrete mathematics supplies the language used to reason about programs and algorithms. The durable sequence is:

1. propositions, predicates, and proof techniques;
2. sets, functions, and relations;
3. induction and recursion;
4. counting and combinatorial proofs;
5. graphs and trees;
6. discrete probability.

This page is a starting reference for proofs and finite structures, not a complete course in combinatorics or graph theory. Berkeley CS 70 develops the proof and probability sequence; concrete algorithm notes live in Computer Science.

Statements and proofs

A proposition is true or false; a predicate such as $P(n)$ becomes a proposition once its variable is specified or quantified. A universal claim $\forall n\,P(n)$ needs an argument covering every allowed $n$; one counterexample disproves it. An existential claim $\exists n\,P(n)$ needs only one witness. The domain matters: “every number has a multiplicative inverse” is false for the reals because of zero, but true for nonzero reals.

An implication $P\Rightarrow Q$ does not imply its converse $Q\Rightarrow P$. Its contrapositive $\neg Q\Rightarrow\neg P$ is equivalent. For integer $n$, “$n$ is even implies $n^2$ is even” follows by writing $n=2k$, giving $n^2=2(2k^2)$. Testing several even numbers would illustrate, not prove, the claim.

Induction proves $P(n)$ for all integers $n\ge n_0$ by proving a base case and showing that $P(n)$ implies $P(n+1)$. For $1+\cdots+n=n(n+1)/2$, the base $n=1$ holds. Adding $n+1$ to the assumed sum gives $(n+1)(n+2)/2$, establishing the next case. A loop invariant uses the same pattern: initialization, preservation by one iteration, then a conclusion on exit. Termination still requires a separate argument, such as a nonnegative integer measure that strictly decreases.

Count the objects you actually mean

A set has distinct, unordered members. A function assigns each input exactly one output; a relation is a set of pairs and need not do so. Counting depends on whether order and repetition matter:

Choosing $r$ items from $n$ distinct items	Number
Ordered, repetition allowed	$n^r$
Ordered, without repetition	$n!/(n-r)!$
Unordered, without repetition	$\binom nr=n!/[r!(n-r)!]$

Here $n,r$ are nonnegative integers, with $r\le n$ for choices without repetition, and $0!=1$. The empty choice counts once; in this counting formula, $0^0=1$. Choosing two distinct people from five gives 20 assignments to two distinct roles, but only 10 two-person committees: each committee was counted in both orders. Counts become probabilities by dividing by the total only when the elementary outcomes are equally likely.

Graphs, trees, and finite games

A graph $G=(V,E)$ consists of vertices and edges. State whether edges are directed and whether loops or repeated edges are allowed. A finite simple undirected tree is connected and has no cycles; with $n\ge1$ vertices it has $n-1$ edges and a unique simple path between any two vertices. The edge count alone does not prove a graph is a tree: a triangle plus an isolated vertex has four vertices and three edges but is disconnected.

A game tree represents histories, not merely distinct board positions: different histories may reach the same position. Winning strategies in finite games uses induction, invariants, and trees to distinguish proving that a strategy exists from constructing and executing it.

My reading · Opened notes are remembered in this browser.