Discrete mathematics studies mathematical structures that are fundamentally discrete rather than continuous. It forms the theoretical foundation for computer science, cryptography, and algorithm design.
Logic
Propositional Logic
Propositions are declarative statements that are either true or false:
- “The sky is blue” (true)
- “2 + 2 = 5” (false)
Logical connectives combine propositions:
| Symbol | Name | Meaning |
|---|---|---|
| ∧ | AND | Both true |
| ∨ | OR | At least one true |
| ¬ | NOT | Negation |
| → | IMPLIES | If…then |
| ↔ | IFF | If and only if |
Truth tables enumerate all possible truth values for compound propositions.
Logical equivalences are fundamental identities:
- De Morgan’s Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q
- Double negation: ¬(¬p) ≡ p
- Contrapositive: (p → q) ≡ (¬q → ¬p)
A tautology is always true (e.g., p ∨ ¬p). A contradiction is always false (e.g., p ∧ ¬p).
Predicate Logic
Predicates are statements containing variables: P(x) = “x is even”
Quantifiers express scope:
- Universal (∀): “for all” — ∀x P(x) means P(x) is true for every x
- Existential (∃): “there exists” — ∃x P(x) means P(x) is true for at least one x
Nested quantifiers combine multiple quantifiers:
- ∀x ∃y (x + y = 0) — for every x, there exists a y such that x + y = 0
Negating quantified statements:
- ¬(∀x P(x)) ≡ ∃x ¬P(x)
- ¬(∃x P(x)) ≡ ∀x ¬P(x)
Proof Methods
See Mathematical Proofs for detailed coverage of:
- Direct proof
- Proof by contradiction
- Proof by contrapositive
- Mathematical induction
Set Theory
Basic Concepts
A set is an unordered collection of distinct objects (elements).
Notation:
- Set membership: x ∈ A (x is in A), x ∉ A (x is not in A)
- Roster notation: A = {1, 2, 3}
- Set-builder notation: A = {x | x is a positive integer less than 4}
Special sets:
- Empty set: ∅ or {}
- Universal set: U (contains all elements under consideration)
Subsets: A ⊆ B means every element of A is in B. A ⊂ B denotes a proper subset (A ⊆ B and A ≠ B).
Set Operations
| Operation | Symbol | Definition |
|---|---|---|
| Union | A ∪ B | {x | x ∈ A or x ∈ B} |
| Intersection | A ∩ B | {x | x ∈ A and x ∈ B} |
| Difference | A − B | {x | x ∈ A and x ∉ B} |
| Complement | A’ or Ā | {x ∈ U | x ∉ A} |
Cartesian product: A × B = {(a, b) | a ∈ A and b ∈ B}
Power set: P(A) is the set of all subsets of A. If |A| = n, then |P(A)| = 2ⁿ.
Cardinality
The cardinality |A| of a set is the number of elements it contains.
- Finite sets have a natural number as cardinality
- Countably infinite sets can be put in one-to-one correspondence with ℕ (e.g., ℤ, ℚ)
- Uncountable sets cannot (e.g., ℝ)
Functions and Relations
Relations
A relation R from set A to set B is a subset of A × B. We write aRb or (a, b) ∈ R.
Properties of relations on a set A:
| Property | Definition |
|---|---|
| Reflexive | ∀a ∈ A: aRa |
| Symmetric | ∀a,b ∈ A: aRb → bRa |
| Transitive | ∀a,b,c ∈ A: (aRb ∧ bRc) → aRc |
| Antisymmetric | ∀a,b ∈ A: (aRb ∧ bRa) → a = b |
An equivalence relation is reflexive, symmetric, and transitive. It partitions a set into equivalence classes.
A partial order is reflexive, antisymmetric, and transitive (e.g., ≤ on integers, ⊆ on sets).
Functions
A function f: A → B assigns exactly one element of B to each element of A.
Types of functions:
- Injective (one-to-one): f(a₁) = f(a₂) implies a₁ = a₂
- Surjective (onto): every element of B is mapped to by some element of A
- Bijective: both injective and surjective
Composition: (g ∘ f)(x) = g(f(x))
Inverse: f⁻¹ exists if and only if f is bijective.
Combinatorics
Counting Principles
Sum rule: If task A can be done in m ways and task B in n ways, and they cannot be done simultaneously, then A or B can be done in m + n ways.
Product rule: If task A can be done in m ways and task B in n ways, then A followed by B can be done in m × n ways.
Inclusion-exclusion principle:
|A ∪ B| = |A| + |B| − |A ∩ B|
For three sets:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Permutations and Combinations
Permutations (order matters):
- n objects: n!
- r objects from n: P(n, r) = n!/(n−r)!
- With repetition: nʳ
Combinations (order doesn’t matter):
- r objects from n: C(n, r) = n!/(r!(n−r)!)
- With repetition: C(n+r−1, r)
Binomial Theorem
The expansion of (a + b)ⁿ:
Pascal’s triangle displays binomial coefficients, where each entry is the sum of the two entries above it.
Properties of binomial coefficients:
- C(n, 0) = C(n, n) = 1
- C(n, k) = C(n, n−k) (symmetry)
- C(n, k) = C(n−1, k−1) + C(n−1, k) (Pascal’s identity)
Pigeonhole Principle
Basic form: If n + 1 objects are placed into n boxes, at least one box contains more than one object.
Generalised form: If n objects are placed into k boxes, at least one box contains ⌈n/k⌉ objects.
Applications:
- In any group of 13 people, at least 2 share a birth month
- In a sequence of n² + 1 distinct numbers, there exists an increasing or decreasing subsequence of length n + 1
Graph Theory
Basic Definitions
A graph G = (V, E) consists of vertices V and edges E connecting pairs of vertices.
- Undirected graph: edges have no direction
- Directed graph (digraph): edges have direction
- Weighted graph: edges have associated values
The degree of a vertex is the number of edges incident to it. In directed graphs, we distinguish in-degree and out-degree.
Handshaking lemma: The sum of all vertex degrees equals twice the number of edges.
Special Graphs
- Complete graph Kₙ: every pair of vertices is connected
- Bipartite graph: vertices can be partitioned into two sets with edges only between sets
- Tree: connected graph with no cycles (n vertices, n−1 edges)
- Planar graph: can be drawn without edge crossings
Euler’s formula for connected planar graphs: V − E + F = 2 (where F = number of faces)
Graph Properties
A path is a sequence of vertices connected by edges. A cycle is a path that starts and ends at the same vertex.
A graph is connected if there is a path between every pair of vertices.
Eulerian path: visits every edge exactly once (exists iff exactly 0 or 2 vertices have odd degree)
Hamiltonian path: visits every vertex exactly once (NP-complete to determine)
Graph colouring: assigning colours to vertices such that no adjacent vertices share a colour. The chromatic number χ(G) is the minimum colours needed.
Algorithms
Breadth-first search (BFS): explores all neighbours before moving deeper. Uses a queue.
Depth-first search (DFS): explores as far as possible before backtracking. Uses a stack.
Dijkstra’s algorithm: finds shortest paths from a source vertex in weighted graphs with non-negative weights.
Minimum spanning tree:
- Prim’s algorithm: grows tree by adding cheapest edge from tree to non-tree vertex
- Kruskal’s algorithm: adds cheapest edge that doesn’t create a cycle
Recurrence Relations
Definitions
A recurrence relation defines a sequence in terms of previous terms.
Examples:
- Fibonacci: F(n) = F(n−1) + F(n−2), with F(0) = 0, F(1) = 1
- Factorial: n! = n × (n−1)!, with 0! = 1
Solving Recurrences
Iteration method: repeatedly substitute until a pattern emerges.
Characteristic equation method for linear recurrences:
For T(n) = aT(n−1) + bT(n−2), solve r² = ar + b to find the characteristic roots.
Master theorem for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n):
- If f(n) = O(n^(log_b(a)−ε)), then T(n) = Θ(n^(log_b(a)))
- If f(n) = Θ(n^(log_b(a))), then T(n) = Θ(n^(log_b(a)) log n)
- If f(n) = Ω(n^(log_b(a)+ε)), then T(n) = Θ(f(n))
Applications in Computer Science
- Algorithm analysis: Big-O notation, complexity classes
- Data structures: trees, graphs, hash tables
- Cryptography: modular arithmetic, prime numbers
- Database theory: relational algebra uses set theory
- Formal languages and automata: finite state machines, regular expressions
Learning Resources
Books
- Discrete Mathematics with Applications by Susanna Epp
- Discrete Mathematics and Its Applications by Kenneth Rosen
- Concrete Mathematics by Graham, Knuth, Patashnik