Discrete Mathematics

Sets, logic, graphs, counting, and proofs — the grammar that every CS algorithm, database query, network protocol, and correctness proof is written in. If calculus is the math of continuous change, discrete math is the math of things you can point at one by one.

1. Why discrete math

Computers can't really deal with continuous things. A float that looks like $0.1$ is actually one of a finite set of representable patterns. A pixel sits on an integer grid. A database row either exists or it doesn't. Every object a computer touches is discrete — finite, countable, separable from its neighbors by a nonzero gap.

Discrete math is the body of math designed for that world. It's where you learn to:

• Count things precisely — "how many ways can a load balancer assign 100 requests to 5 servers?"
• Reason with truth and falsity — "if the user is logged in and is an admin, then show the button."
• Describe structures made of connections — "who follows whom, what depends on what, which page links to which."
• Prove a program is correct, not just test it on three inputs and hope.

If you've ever felt that programming is unreasonable because everything runs on vibes and test cases, discrete math is the subject that teaches you the alternative. Nothing on this page requires calculus. Nothing requires you to remember trigonometry. You need to know what a variable is and what it means to add and multiply. That's it.

The five movements you'll work through:

• Sets. Collections of things.
• Logic. Rules for combining true/false statements.
• Relations and functions. Ways of pairing things up.
• Counting. How many ways can something happen.
• Graphs. Things connected by lines.

Everything else — recurrences, number theory, Boolean algebra — is built on top of those five.

2. Vocabulary cheat-sheet

Scan this once. Come back to it whenever you see a symbol you don't recognise.

3. Sets

A set is an unordered collection of distinct things. Those things are called its elements. There are two ways to specify a set. By listing:

Or by description (set-builder notation), which you read as "the set of all $x$ such that ...":

Standard number sets

These names recur everywhere. Memorise them once:

• $\mathbb{N}$ — natural numbers. Depending on the author, either $\{0, 1, 2, \ldots\}$ or $\{1, 2, 3, \ldots\}$. In CS we usually include 0.
• $\mathbb{Z}$ — integers. All of $\mathbb{N}$ plus the negatives.
• $\mathbb{Q}$ — rationals. Fractions $p/q$ with $p, q \in \mathbb{Z}$ and $q \neq 0$.
• $\mathbb{R}$ — real numbers. The full number line.
• $\mathbb{C}$ — complex numbers. Of the form $a + bi$ where $i^2 = -1$.

Operations on sets

If there's a fixed universe $U$ that we're working inside of, the complement of $A$ is everything in the universe but not in $A$: $A^c = U \setminus A$.

Subsets and power sets

$A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is also in $B$. The empty set $\emptyset$ is a subset of every set, including itself, and every set is a subset of itself. If $A \subseteq B$ but $A \neq B$, we write $A \subsetneq B$ and call $A$ a proper subset.

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$:

Cartesian product

4. Propositional logic

A proposition is a statement that's either true or false — no in-between. "It's raining." "$2 + 2 = 5$." "The user is logged in." Not propositions: questions, commands, opinions, or anything whose truth isn't well-defined.

We write propositions with lowercase letters: $p$, $q$, $r$. And we combine them with connectives.

The connectives

• Negation: $\neg p$ ("not $p$"). True when $p$ is false.
• Conjunction: $p \wedge q$ ("$p$ and $q$"). True only when both are true.
• Disjunction: $p \vee q$ ("$p$ or $q$"). True when at least one is true. This is inclusive or — if both are true, the result is still true.
• Implication: $p \Rightarrow q$ ("if $p$ then $q$"). False only when $p$ is true and $q$ is false. We'll explain the weird case below.
• Biconditional: $p \Leftrightarrow q$ ("$p$ if and only if $q$," often "$p$ iff $q$"). True when $p$ and $q$ have the same truth value.

Truth tables

The only tool you need to evaluate any logical expression. A truth table lists every combination of truth values for the input propositions, then fills in the output column by column. Here's the full table for the binary connectives:

Most people get tripped up by two rows:

Logical equivalence

Two formulas are logically equivalent, written $\equiv$, if they have the same truth value for every assignment of their variables. You check this by building a truth table for each and comparing columns.

The most useful equivalences — worth memorising — are De Morgan's laws:

Other important equivalences:

• Distributivity: $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$, and symmetrically for $\vee$ over $\wedge$.
• Implication as disjunction: $p \Rightarrow q \equiv \neg p \vee q$. Check it against the truth table — it matches.
• Contrapositive: $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$. This is the single most useful rewriting in proofs.
• Double negation: $\neg \neg p \equiv p$.

Tautologies and contradictions

A formula that's true for every assignment of its variables is a tautology. For example, $p \vee \neg p$ — "either it's raining or it isn't." A formula that's false for every assignment is a contradiction. For example, $p \wedge \neg p$.

A formula that's true under at least one assignment is satisfiable. The problem of "given this formula, is it satisfiable?" is SAT — the original NP-complete problem, and the thing every modern hardware verifier ends up solving internally.

5. Predicate logic

Propositional logic can only talk about whole statements. It can't say "everyone in this room has a laptop" without inventing one proposition per person. That's where predicates and quantifiers come in.

A predicate is a statement with one or more blanks. "$x$ is even" is a predicate, written $E(x)$. Plug in a value and you get a proposition. $E(4)$ is true, $E(5)$ is false.

Quantifiers

A quantifier says how a predicate should be evaluated over a whole set. There are two:

Negation rules

Negating a quantified statement flips the quantifier and negates the predicate:

Worked example

Take the statement "every student passed every exam." With $S$ the set of students and $E$ the set of exams, we'd write:

Order matters with nested quantifiers of different types. "$\forall x,\ \exists y,\ y > x$" says every number has something bigger than it — true in $\mathbb{N}$. "$\exists y,\ \forall x,\ y > x$" says there's a single number bigger than everything — false in $\mathbb{N}$. The words look similar; the meanings are not.

6. Proof techniques

A proof is a chain of logical steps leading from stuff you're given (or stuff you've already proved) to the thing you want. Four patterns do 95% of the work.

Direct proof

Assume the hypothesis, march forward, arrive at the conclusion. "If $n$ is even, then $n^2$ is even." Assume $n$ is even, so $n = 2k$ for some integer $k$. Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, which is twice an integer, hence even. Done.

Contrapositive

To prove $p \Rightarrow q$, prove $\neg q \Rightarrow \neg p$ instead. These are logically equivalent (we saw this earlier), but sometimes the contrapositive is much easier to attack.

"If $n^2$ is even, then $n$ is even." Going direct is awkward. The contrapositive — "if $n$ is odd, then $n^2$ is odd" — is immediate: $n = 2k+1$, so $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, odd. Done.

Proof by contradiction

Assume the opposite of what you want to prove. Derive a contradiction (something both true and false, or something that contradicts a known fact). Conclude that your assumption must have been wrong.

Classic example. $\sqrt{2}$ is irrational. Assume for contradiction that $\sqrt{2} = p/q$ for integers $p$ and $q$ with no common factor. Squaring: $2 = p^2/q^2$, so $p^2 = 2q^2$. That means $p^2$ is even, so $p$ is even (by the previous proof), so $p = 2m$, so $p^2 = 4m^2 = 2q^2$, so $q^2 = 2m^2$, so $q$ is even too. But we said $p$ and $q$ had no common factor, and now they both have 2 as a factor. Contradiction. So $\sqrt{2}$ is not rational.

Proof by induction

The workhorse for any statement about "all natural numbers $n$." Three parts:

1. Base case. Show the statement holds for $n = 0$ (or $n = 1$, whichever is your starting value).
2. Inductive step. Assume it holds for some arbitrary $n = k$. Show it then holds for $n = k+1$.
3. Conclude. Since it holds for the base case, it holds for the next one, and the next one, and so on — it holds for every $n$.

The classic. Prove that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for every positive integer $n$.

Base case ($n=1$). Left side: $1$. Right side: $\dfrac{1 \cdot 2}{2} = 1$. Match.

Inductive step. Assume the formula holds for $n = k$:

We want to show the formula holds for $n = k+1$, i.e., that $1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$. Starting from the left:

Combined with the base case, by induction the formula holds for all $n \geq 1$. $\blacksquare$

7. Relations and functions

A relation between two sets $A$ and $B$ is just a subset of $A \times B$ — a set of pairs. The pair $(a,b)$ being in the relation means "$a$ is related to $b$." Written $a \sim b$ or $a R b$.

"$x$ is less than $y$" is a relation on $\mathbb{Z} \times \mathbb{Z}$. "$u$ follows $v$" is a relation on users. "$x$ divides $y$" is a relation on the integers. A database table with two foreign keys is a relation.

Properties of relations on a single set

When $A = B$, we can ask whether a relation has the following properties:

• Reflexive: $a \sim a$ for every $a$. ("Everybody is equal to themselves.")
• Symmetric: if $a \sim b$ then $b \sim a$. ("Friendship on a platform without directed follows.")
• Antisymmetric: if $a \sim b$ and $b \sim a$ then $a = b$. ("Less-than-or-equal: two things only cross each other if they're equal.")
• Transitive: if $a \sim b$ and $b \sim c$ then $a \sim c$. ("Ancestor of" is transitive; "parent of" is not.)

Equivalence relations

A relation that's reflexive, symmetric, and transitive is called an equivalence relation. These are the ones that partition a set into disjoint blocks — each element belongs to exactly one block of things that are equivalent to it.

"Has the same remainder when divided by 5" is an equivalence relation on the integers. It partitions $\mathbb{Z}$ into 5 blocks, one for each possible remainder: $\{\ldots, -10, -5, 0, 5, 10, \ldots\}$, $\{\ldots, -9, -4, 1, 6, 11, \ldots\}$, and so on. This is the basis of modular arithmetic, which we'll get to in §13.

Partial orders

A relation that's reflexive, antisymmetric, and transitive is a partial order. "$\leq$" on $\mathbb{Z}$ is one. "$\subseteq$" on sets is another. It's called partial because two elements might not be comparable at all — for example, $\{1,2\}$ and $\{2,3\}$ can't be put in an order under $\subseteq$, neither is a subset of the other. When every pair is comparable, we call it a total order.

Functions

A function $f: A \to B$ is a special kind of relation: each element of $A$ is related to exactly one element of $B$. We write $f(a) = b$ to mean "the unique $b$ that $a$ maps to."

• $A$ is the domain. Every element of the domain has to map somewhere.
• $B$ is the codomain. Candidates to be mapped to.
• The image (or range) is $\{f(a) \mid a \in A\}$ — the actual outputs that appear. Not always all of $B$.

Three special kinds:

• Injective (one-to-one). Different inputs go to different outputs. $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$. Nothing in $B$ gets hit twice.
• Surjective (onto). Every element of $B$ is hit by something. The image is $B$.
• Bijective. Both injective and surjective. A perfect pairing between $A$ and $B$. This is the rigorous notion of "the two sets have the same size," and it's how we make sense of comparing infinite sets — if there's a bijection from $\mathbb{N}$ to $\mathbb{Q}$ (there is), then $\mathbb{N}$ and $\mathbb{Q}$ have the "same" infinity.

8. Counting & combinatorics

Combinatorics is the subfield of discrete math that asks "how many ways?" It's the foundation of probability, where "how many ways" turns into "what fraction of the possible worlds," and of algorithm analysis, where "how many steps" turns into big-$O$.

Two fundamental rules

Rule of sum. If there are $m$ ways to do thing A and $n$ ways to do thing B, and you must do exactly one of them, there are $m + n$ ways total (assuming the options don't overlap).

Rule of product. If there are $m$ ways to do A and $n$ ways to do B, and you do both independently, there are $m \cdot n$ ways in sequence.

Example: picking a password with one letter (26 options) followed by one digit (10 options) gives $26 \cdot 10 = 260$ possibilities. Picking either a letter or a digit gives $26 + 10 = 36$.

Permutations

A permutation of a set is an ordering of its elements. The number of ways to arrange all $n$ elements in a line is $n$ factorial:

If you only want to pick and arrange $k$ out of $n$, you get the partial permutation count:

Combinations

When order does not matter — you just want to pick $k$ items out of $n$ as an unordered set — you get combinations:

Combinations satisfy a simple symmetry: $\binom{n}{k} = \binom{n}{n-k}$ — picking what to include is the same as picking what to exclude. And they obey Pascal's identity:

The binomial theorem

Combinations show up as the coefficients when you expand $(x+y)^n$:

Pigeonhole principle

The silliest-looking theorem in math, and one of the most useful:

It sounds like a tautology. It is. But it's shocking how often it's the argument you need. Examples: in any group of 367 people, at least two share a birthday (366 possible birthdays). Any list of $n+1$ distinct integers from $\{1, 2, \ldots, 2n\}$ contains two that sum to $2n+1$. Any sequence of $n^2 + 1$ distinct numbers has a monotonic subsequence of length $n+1$ (harder — Erdős-Szekeres).

Inclusion-exclusion

To count the size of a union, you add the parts and subtract the double-counted overlaps:

9. Interactive combinatorics lab

Drag the sliders to vary $n$ and $k$. The figure draws a tiny Pascal's triangle with the current entry highlighted, and reports $P(n,k)$, $C(n,k)$, and $n!$. Use it to see how fast these numbers grow.

10. Graph theory

A graph is a set of things with lines between some of them. Formally:

Variants

• Undirected. Edges are symmetric. Friendship.
• Directed. Edges have a direction. Who follows whom. Web links.
• Weighted. Each edge has a number attached — a distance, cost, or capacity. Road distance. Network latency.
• Simple. No self-loops (edges from a vertex to itself) and no duplicate edges.
• Multigraph. Loops and duplicates allowed.

Representations

Two standard ways to store a graph in memory:

Adjacency matrix. An $n \times n$ matrix $M$ with $M_{ij} = 1$ if there's an edge from vertex $i$ to vertex $j$, and $0$ otherwise (or the edge weight instead of 1). Cost: $O(n^2)$ memory, even for sparse graphs. Lookup of a single edge is $O(1)$. Great when $n$ is small and the graph is dense.

Adjacency list. For each vertex $v$, a list of its neighbours. Cost: $O(|V| + |E|)$ memory. Iterating the neighbours of $v$ is $O(\deg(v))$. Great when $n$ is big and the graph is sparse — almost always the right choice in practice.

Basic vocabulary

• Degree of vertex $v$, written $\deg(v)$: the number of edges touching $v$. In a directed graph you split into $\deg^-(v)$ (in-degree) and $\deg^+(v)$ (out-degree).
• Path: a sequence of vertices where consecutive ones are connected by edges. A simple path has no repeated vertices.
• Cycle: a path that starts and ends at the same vertex.
• Connected: there's a path between every pair of vertices (in the undirected case). A disconnected graph splits into connected components.
• Tree: a connected, acyclic undirected graph.
• Bipartite: vertices split into two groups $U$ and $W$, with all edges going between $U$ and $W$ (never within). Models two-sided matching — students and schools, jobs and machines.

Trees

Trees are a special case of graphs so important that we give them their own name and theorems. A rooted tree picks one vertex as the root; the rest hang down in parent-child relationships. Every file system you've ever used is a rooted tree. Every DOM tree. Every AST in a compiler. Every HuffMan code.

A tree on $n$ vertices has exactly $n-1$ edges. Add one more edge and you must create a cycle. Remove one edge and the tree disconnects. That's the "just barely connected" characterisation.

11. Important graph facts

Handshake lemma

Trees have $n-1$ edges

Any tree on $n$ vertices has $n - 1$ edges. The proof is a one-liner by induction on $n$: the base case is trivial, and removing a leaf (a degree-1 vertex) of a tree on $n$ vertices leaves a tree on $n - 1$ vertices. By the inductive hypothesis that smaller tree has $n - 2$ edges; we removed 1, so the original had $n - 1$.

Euler's formula for planar graphs

A graph is planar if you can draw it on paper without any edges crossing. For a connected planar graph:

12. Recurrence relations

A recurrence relation defines a sequence by saying what each term is in terms of earlier ones. You've seen this every time you've written a recursive function.

The most famous recurrence:

Linear homogeneous recurrences

Fibonacci is a special case of a general pattern. A linear homogeneous recurrence with constant coefficients of order $k$ looks like:

Divide-and-conquer recurrences

Recurrences also show up in algorithm analysis, where they describe the running time of divide-and-conquer algorithms. A classic form:

13. Number theory basics

Number theory is the study of the integers — their divisibility, factorizations, primes, and modular behaviour. It looks very "pure" until you realise it's the mathematical foundation of every cryptosystem your browser uses to talk to banks.

Divisibility

We say $a$ divides $b$, written $a \mid b$, if $b = ak$ for some integer $k$. So $3 \mid 12$ (because $12 = 3 \cdot 4$), but $5 \nmid 12$. "Divides" is a relation on $\mathbb{Z}$, and on the positive integers it's a partial order.

GCD and the Euclidean algorithm

The greatest common divisor $\gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$. Every first-year student is taught to find it by factoring both numbers — which doesn't scale past small numbers. The algorithm that does scale is over 2000 years old:

Primes

A prime is a positive integer $p > 1$ whose only positive divisors are $1$ and $p$ itself. Primes are the multiplicative atoms of the integers — the Fundamental Theorem of Arithmetic says every integer $n > 1$ has a unique factorisation into primes (up to order). There are infinitely many primes (Euclid's proof: if only finitely many, multiply them all together and add 1 — the result has no prime factor on your list).

Modular arithmetic

Arithmetic "mod $n$" throws away multiples of $n$:

The integers modulo $n$ form a finite set $\{0, 1, 2, \ldots, n-1\}$. You can add, subtract, and multiply within this set. When $n$ is prime, you can also divide — every non-zero element has a multiplicative inverse. This is the core fact that makes modular arithmetic into a field, and fields are where cryptography lives.

Tiny intro to RSA

RSA, the public-key cryptosystem at the heart of HTTPS, TLS, and PGP, works like this (very simplified):

1. Pick two huge primes $p$ and $q$ — say, 1024 bits each. Let $n = pq$.
2. Pick a small exponent $e$ (often 65537). Compute $d$ such that $ed \equiv 1 \pmod{(p-1)(q-1)}$ using the extended Euclidean algorithm.
3. Publish $(n, e)$. Keep $d$ secret.
4. To encrypt a message $m$: send $c = m^e \bmod n$. To decrypt: compute $c^d \bmod n = m$.

The security rests on one conjecture: factoring $n$ back into $p$ and $q$ is hard for numbers that big. Every theorem used in RSA — Fermat's little theorem, Euler's totient — is elementary discrete math you could prove in a weekend. The whole internet's secure channels are secured by theorems that were pure curiosities in 1640.

14. Boolean algebra

Propositional logic, rewritten in the language of algebra — with $0$ for false, $1$ for true, $+$ for OR, $\cdot$ for AND, and overline for NOT. George Boole introduced this in 1854. Claude Shannon noticed in his 1937 master's thesis that switches in an electrical circuit obeyed exactly these rules, and the entire field of digital logic design was born.

The laws you already know, in the new notation:

• Commutative: $a + b = b + a$, $\ a \cdot b = b \cdot a$.
• Associative: $(a + b) + c = a + (b + c)$, and the same for $\cdot$.
• Distributive: $a \cdot (b + c) = a \cdot b + a \cdot c$, and — this one is new if you're coming from regular algebra — $a + (b \cdot c) = (a+b) \cdot (a+c)$.
• Identity: $a + 0 = a$, $\ a \cdot 1 = a$.
• Complement: $a + \bar a = 1$, $\ a \cdot \bar a = 0$.
• De Morgan: $\overline{a + b} = \bar a \cdot \bar b$, $\ \overline{a \cdot b} = \bar a + \bar b$.

Every digital circuit you've ever touched — the ALU in your CPU, the address decoder in your RAM, the carry logic in your adder — is a Boolean expression rendered in silicon. Simplifying that expression using the laws above literally saves transistors, which saves area, heat, and cost. Tools like Karnaugh maps and Quine-McCluskey minimisation automate this, but they're mechanical rewrites using the identities above.

15. Code

A tour of the standard discrete-math building blocks in Python: a graph class, breadth-first and depth-first traversal, the Euclidean GCD, and a few combinatorial helpers. Everything here is stdlib-only.

from collections import defaultdict, deque

class Graph:
    # Adjacency-list representation — cheap for sparse graphs.
    def __init__(self, directed=False):
        self.adj = defaultdict(set)
        self.directed = directed

    def add_edge(self, u, v):
        self.adj[u].add(v)
        if not self.directed:
            self.adj[v].add(u)

    def neighbors(self, u):
        return sorted(self.adj[u])

    def bfs(self, start):
        # Breadth-first: visits by distance from start. O(V + E).
        seen = {start}
        order = []
        q = deque([start])
        while q:
            u = q.popleft()
            order.append(u)
            for v in self.neighbors(u):
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        return order

    def dfs(self, start):
        # Depth-first: dives as deep as it can before backtracking. O(V + E).
        seen, order = set(), []
        def visit(u):
            if u in seen: return
            seen.add(u)
            order.append(u)
            for v in self.neighbors(u):
                visit(v)
        visit(start)
        return order

# Example: a small social graph
g = Graph()
for u, v in [("a","b"), ("a","c"), ("b","d"),
               ("c","d"), ("d","e"), ("e","f")]:
    g.add_edge(u, v)

print(g.bfs("a"))  # → ['a', 'b', 'c', 'd', 'e', 'f']
print(g.dfs("a"))  # → ['a', 'b', 'd', 'c', 'e', 'f']

def gcd(a, b):
    # Euclidean algorithm — the original asymptotically fast algorithm, ~300 BCE.
    while b:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    # Returns (g, x, y) where g = gcd(a,b) and a*x + b*y = g.
    # The x is what you need to invert a modulo b — the RSA key-generation step.
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def modinv(a, n):
    # Modular inverse: the x such that a*x ≡ 1 (mod n). Exists iff gcd(a,n) = 1.
    g, x, _ = extended_gcd(a, n)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {n}")
    return x % n

def is_prime(n):
    # Trial division — fine up to ~10^12. For real crypto, use Miller-Rabin.
    if n < 2: return False
    if n % 2 == 0: return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0: return False
        i += 2
    return True

print(gcd(48, 18))              # 6
print(modinv(3, 11))            # 4  (because 3*4 = 12 ≡ 1 mod 11)
print([p for p in range(2, 30) if is_prime(p)])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

from math import factorial

def perm(n, k):
    # Ordered arrangements: P(n, k) = n! / (n-k)!
    return factorial(n) // factorial(n - k)

def comb(n, k):
    # Unordered choices: C(n, k) = n! / (k! (n-k)!)
    return factorial(n) // (factorial(k) * factorial(n - k))

def pascal_row(n):
    # nth row of Pascal's triangle via Pascal's identity — no factorials needed.
    row = [1]
    for k in range(n):
        row.append(row[-1] * (n - k) // (k + 1))
    return row

def subsets(xs):
    # Yield every subset of xs — there are 2^|xs| of them.
    if not xs:
        yield []
        return
    head, *tail = xs
    for s in subsets(tail):
        yield s
        yield [head] + s

print(perm(8, 3))            # 336
print(comb(5, 2))            # 10
print(pascal_row(6))        # [1, 6, 15, 20, 15, 6, 1]
print(list(subsets(["a","b","c"])))
# every subset of {a,b,c}

16. Connections to everything else

Discrete math isn't a subject you learn and put down. It's the language that every CS and ML page on this site is written in. The bridges worth walking:

17. Further reading