Discrete Mathematics#

Discrete mathematics deals with countable, separated values — the natural habitat of computers, which process distinct symbols, not continuous quantities. Sets, relations, and combinatorics form the theoretical foundation of data structures, databases, and algorithms.

Sets#

A set is an unordered collection of distinct elements.

Notation#

A = {1, 2, 3, 4, 5}           Roster notation
B = {x ∈ ℤ | x > 0 and x ≤ 5}  Set-builder notation
∅ = {}                          Empty set

Set Operations#

Set Properties#

In Programming#

A = {1, 2, 3}
B = {2, 3, 4}

A | B      # {1, 2, 3, 4}  union
A & B      # {2, 3}         intersection
A - B      # {1}            difference
A ^ B      # {1, 4}         symmetric difference
A <= B     # False           subset check

SQL SELECT with UNION, INTERSECT, EXCEPT maps directly to set operations.

Cardinality#

The cardinality |A| of a set is the number of elements in it.

Inclusion-Exclusion Principle:

|A ∪ B| = |A| + |B| - |A ∩ B|

Generalised to three sets:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Application: Counting unique visitors across multiple pages, deduplicating overlapping data sources.

Power Set#

The power set P(A) is the set of all subsets of A, including ∅ and A itself.

A = {1, 2, 3}
P(A) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
|P(A)| = 2^|A| = 2³ = 8

This is why iterating over all subsets is O(2ⁿ) — there are exactly 2ⁿ of them.

Relations#

A relation R from set A to set B is a subset of A × B. If (a, b) ∈ R, we write aRb.

Properties of Relations on a Set#

For a relation R on set A (i.e., R ⊂ A × A):

Equivalence Relations#

A relation that is reflexive, symmetric, and transitive. It partitions the set into equivalence classes — groups of elements that are “the same” under the relation.

Partial Orders#

A relation that is reflexive, antisymmetric, and transitive. Formalises “≤” and dependency relationships.

A partial order where every pair of elements is comparable is a total order (like ≤ on integers). Otherwise, some elements are incomparable (like tasks with no dependency between them — they can run in parallel).

Topological Sort#

Given a partial order (a DAG), a topological sort produces a linear ordering consistent with the partial order. Every build system (Make, Gradle, Terraform) computes a topological sort of dependencies.

Functions as Relations#

A function f: A → B is a special relation where each element of A appears in exactly one pair.

Types of Functions#

Engineering Applications#

Combinatorics#

Counting the number of ways to arrange, select, or combine elements. Essential for probability, algorithm analysis, and understanding search spaces.

The Fundamental Counting Principle#

If task 1 can be done in m ways and task 2 in n ways, then both tasks can be done in m × n ways (assuming independence).

Passwords with 8 lowercase letters: 26⁸ = 208,827,064,576
Passwords with 8 mixed-case + digits: 62⁸ = 218,340,105,584,896

Permutations (Order Matters)#

The number of ways to arrange k items chosen from n distinct items:

P(n, k) = n! / (n - k)!

Combinations (Order Does Not Matter)#

The number of ways to choose k items from n without regard to order:

C(n, k) = n! / (k! × (n - k)!)

Also written as $\binom{n}{k}$ (“n choose k”).

Key Identity: Pascal’s Rule#

C(n, k) = C(n-1, k-1) + C(n-1, k)

This recursive relation generates Pascal’s triangle and is the basis for computing binomial coefficients efficiently.

The Binomial Theorem#

(a + b)ⁿ = Σ_{k=0}^{n} C(n,k) × aⁿ⁻ᵏ × bᵏ

Setting a = b = 1: Σ C(n,k) = 2ⁿ (total number of subsets).

Stars and Bars#

The number of ways to put n identical items into k distinct bins:

C(n + k - 1, k - 1)

Application: Distributing 10 identical tasks across 3 servers = C(12, 2) = 66 ways.

The Pigeonhole Principle#

If n items are placed into m containers and n > m, at least one container has more than one item.

Generalised Form#

If n items go into m containers, at least one container has ⌈n/m⌉ items.

Applications#

Recurrence Relations#

An equation that defines a sequence where each term depends on previous terms. Fundamental for analysing recursive algorithms.

Common Recurrences in CS#

Solving Recurrences#

1. Substitution method: Guess the form, prove by induction.

2. Recursion tree: Visualise the work at each level.

T(n) = 2T(n/2) + n

Level 0:               n           work = n
Level 1:         n/2     n/2       work = n
Level 2:       n/4 n/4 n/4 n/4    work = n
  ...
Level log₂n:  1 1 1 ... 1         work = n

Total: n × log₂(n) levels = O(n log n)

3. Master theorem for recurrences of the form T(n) = aT(n/b) + O(nᵈ):

Example: Merge sort: T(n) = 2T(n/2) + O(n). Here a=2, b=2, d=1. Since d = log₂(2) = 1, we get T(n) = O(n log n). ✓

Modular Arithmetic Revisited#

In the context of discrete math, we can define the set of integers modulo n:

ℤ_n = {0, 1, 2, ..., n-1}

This forms a ring under addition and multiplication modulo n. When n is prime, it forms a field — every nonzero element has a multiplicative inverse. This is the foundation of finite field cryptography (AES, elliptic curves).

Fermat’s Little Theorem#

If p is prime and a is not divisible by p:

a^(p-1) ≡ 1 (mod p)

This is used to compute modular inverses: a⁻¹ ≡ a^(p-2) (mod p).

Applications#

Key Takeaways#

• Sets and their operations are the mathematical model behind database queries, type systems, and access control.
• Relations formalise dependencies — equivalence relations partition data, partial orders enable topological sort.
• Combinatorics (permutations, combinations, pigeonhole) is essential for understanding search spaces, password strength, and hash collision probability.
• Recurrence relations describe recursive algorithms. The Master theorem lets you solve them mechanically.
• Modular arithmetic on prime fields is the foundation of modern cryptography.