Discrete Mathematics
Discrete mathematics studies discrete (as opposed to continuous) mathematical structures and forms the mathematical foundation of computer science. Unlike calculus and linear algebra, which focus on continuous objects, discrete mathematics deals with finite or countable objects: sets, graphs, combinatorial structures, logical propositions, and more.
Discrete mathematics has broad applications in AI: graph theory provides the theoretical basis for Graph Neural Networks (GNNs), combinatorics underpins search and optimization algorithms, and Boolean algebra is the core tool for SAT solving and logical reasoning. These notes cover set theory, relations and functions, graph theory, combinatorics, Boolean algebra, and recurrence relations.
1. Set Theory Fundamentals
1.1 Set Operations
Let \(A, B\) be subsets of a universal set \(U\):
| Operation | Notation | Definition |
|---|---|---|
| Union | \(A \cup B\) | \(\{x \mid x \in A \text{ or } x \in B\}\) |
| Intersection | \(A \cap B\) | \(\{x \mid x \in A \text{ and } x \in B\}\) |
| Difference | \(A - B\) | \(\{x \mid x \in A \text{ and } x \notin B\}\) |
| Complement | \(\overline{A}\) | \(\{x \mid x \in U \text{ and } x \notin A\}\) |
| Symmetric Difference | \(A \oplus B\) | \((A - B) \cup (B - A)\) |
De Morgan's Laws:
1.2 Power Set and Cartesian Product
- Power set: \(\mathcal{P}(A) = \{S \mid S \subseteq A\}\). If \(|A| = n\), then \(|\mathcal{P}(A)| = 2^n\).
- Cartesian product: \(A \times B = \{(a, b) \mid a \in A, b \in B\}\), \(|A \times B| = |A| \cdot |B|\).
Cardinality of Sets
- The cardinality of a finite set is simply its number of elements.
- \(\mathbb{N}\) (natural numbers) is countably infinite, while \(\mathbb{R}\) (real numbers) is uncountably infinite.
- Cantor's diagonal argument proves that \(|\mathbb{R}| > |\mathbb{N}|\).
2. Relations and Functions
2.1 Properties of Relations
Let \(R\) be a binary relation on a set \(A\):
| Property | Definition | Example |
|---|---|---|
| Reflexive | \(\forall a \in A,\; (a, a) \in R\) | \(\leq\) is reflexive |
| Symmetric | \((a, b) \in R \Rightarrow (b, a) \in R\) | "is a friend of" is symmetric |
| Antisymmetric | \((a, b) \in R \land (b, a) \in R \Rightarrow a = b\) | \(\leq\) is antisymmetric |
| Transitive | \((a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R\) | \(<\) is transitive |
2.2 Equivalence Relations and Partial Orders
- Equivalence relation: A relation that is reflexive, symmetric, and transitive. An equivalence relation partitions a set into equivalence classes. - Example: Congruence modulo \(n\), i.e., \(a \equiv b \pmod{n}\), is an equivalence relation on \(\mathbb{Z}\).
- Partial order: A relation that is reflexive, antisymmetric, and transitive, denoted \((A, \preceq)\). - Example: \((\mathcal{P}(S), \subseteq)\) is a partially ordered set (poset).
- Total order: A partial order in which every pair of elements is comparable. - Example: \((\mathbb{R}, \leq)\) is a totally ordered set.
2.3 Functions
A function \(f: A \to B\) is a special relation where for every \(a \in A\), there exists a unique \(b \in B\) such that \((a, b) \in f\).
| Type | Definition |
|---|---|
| Injection (one-to-one) | \(f(a_1) = f(a_2) \Rightarrow a_1 = a_2\) |
| Surjection (onto) | \(\forall b \in B,\; \exists a \in A,\; f(a) = b\) |
| Bijection | Both injective and surjective |
3. Graph Theory Fundamentals
3.1 Basic Concepts
A graph \(G = (V, E)\) consists of a vertex set \(V\) and an edge set \(E\).
| Concept | Definition |
|---|---|
| Undirected graph | An edge \(\{u, v\}\) has no direction |
| Directed graph | An edge \((u, v)\) has a direction |
| Degree | Number of edges incident to a vertex; $\sum_{v \in V} \deg(v) = 2 |
| Adjacency matrix | \(A_{ij} = 1\) if and only if \((i, j) \in E\) |
| Adjacency list | Each vertex stores a list of its neighbors |
3.2 Connectivity
- Connected graph: There exists a path between every pair of vertices.
- Strongly connected (directed graphs): There exists a directed path in both directions between every pair of vertices.
- Connected components: Maximal connected subgraphs. Computable via BFS/DFS in \(O(V + E)\) time.
3.3 Special Paths and Cycles
| Type | Condition | Decision |
|---|---|---|
| Eulerian path | Visits every edge exactly once | Exactly 0 or 2 vertices of odd degree |
| Eulerian circuit | Eulerian path that starts and ends at the same vertex | All vertices have even degree |
| Hamiltonian path | Visits every vertex exactly once | NP-complete; no polynomial-time decision algorithm known |
| Hamiltonian cycle | Hamiltonian path that starts and ends at the same vertex | NP-complete |
3.4 Graph Coloring and Planar Graphs
- Graph coloring: Assign the fewest colors to vertices such that no two adjacent vertices share a color. The minimum number of colors needed is the chromatic number \(\chi(G)\).
- Four Color Theorem: The chromatic number of any planar graph is at most 4.
- Planar graph: A graph that can be drawn in the plane without edge crossings. Euler's formula: \(V - E + F = 2\) (where \(F\) is the number of faces).
4. Combinatorics
4.1 Permutations and Combinations
- Permutation: Selecting \(r\) elements from \(n\) with order: \(P(n, r) = \frac{n!}{(n-r)!}\)
- Combination: Selecting \(r\) elements from \(n\) without order: \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)
4.2 The Binomial Theorem
Pascal's identity: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)
4.3 The Inclusion-Exclusion Principle
Application example: Count the integers in \([1, 1000]\) not divisible by 2, 3, or 5.
4.4 The Pigeonhole Principle
If \(n+1\) objects are placed into \(n\) boxes, then at least one box contains two or more objects.
Generalized form: If \(n\) objects are placed into \(k\) boxes, then at least one box contains \(\lceil n/k \rceil\) objects.
4.5 Introduction to Generating Functions
The ordinary generating function (OGF) of a sequence \(\{a_n\}\) is \(G(x) = \sum_{n=0}^{\infty} a_n x^n\).
| Sequence | Generating Function |
|---|---|
| \(1, 1, 1, \dots\) | \(\frac{1}{1-x}\) |
| \(1, 2, 3, \dots\) | \(\frac{1}{(1-x)^2}\) |
| Row of \(\binom{n}{k}\) | \((1+x)^n\) |
| Fibonacci sequence | \(\frac{x}{1-x-x^2}\) |
5. Boolean Algebra
5.1 Boolean Operations
Boolean algebra is defined over the set \(\{0, 1\}\) with the following fundamental operations:
| Operation | Symbol | Truth Table (partial) |
|---|---|---|
| AND | \(a \land b\) | \(1 \land 1 = 1\); all others yield \(0\) |
| OR | \(a \lor b\) | \(0 \lor 0 = 0\); all others yield \(1\) |
| NOT | \(\neg a\) | \(\neg 0 = 1\), \(\neg 1 = 0\) |
| XOR | \(a \oplus b\) | Same inputs yield \(0\); different inputs yield \(1\) |
5.2 Normal Forms
- Disjunctive Normal Form (DNF): A disjunction of conjunctive clauses, e.g., \((A \land B) \lor (\neg A \land C)\)
- Conjunctive Normal Form (CNF): A conjunction of disjunctive clauses, e.g., \((A \lor B) \land (\neg A \lor C)\)
Every Boolean function can be converted into DNF or CNF. CNF is the standard input format for SAT solvers.
5.3 Logic Circuits
Boolean algebra maps directly to digital logic circuits:
- AND gate, OR gate, NOT gate: Fundamental logic gates
- NAND gate: Functionally complete; any Boolean function can be implemented using only NAND gates
- Half adder: \(S = A \oplus B\), \(C = A \land B\)
- Full adder: \(S = A \oplus B \oplus C_{in}\), \(C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B))\)
6. Recurrence Relations
6.1 Linear Recurrences
The general form of a linear homogeneous recurrence is:
Solution method: Solve the characteristic equation \(x^k - c_1 x^{k-1} - \cdots - c_k = 0\) and construct the general solution from its roots.
Example: The Fibonacci sequence \(F_n = F_{n-1} + F_{n-2}\)
Characteristic equation: \(x^2 - x - 1 = 0\), with roots \(\phi = \frac{1+\sqrt{5}}{2}\) and \(\hat{\phi} = \frac{1-\sqrt{5}}{2}\)
6.2 The Master Theorem
For the recurrence \(T(n) = aT(n/b) + f(n)\), where \(a \geq 1\) and \(b > 1\):
| Case | Condition | Result |
|---|---|---|
| Case 1 | \(f(n) = O(n^{\log_b a - \epsilon})\) | \(T(n) = \Theta(n^{\log_b a})\) |
| Case 2 | \(f(n) = \Theta(n^{\log_b a} \log^k n)\) | \(T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\) |
| Case 3 | \(f(n) = \Omega(n^{\log_b a + \epsilon})\) | \(T(n) = \Theta(f(n))\) |
Example: Merge sort \(T(n) = 2T(n/2) + \Theta(n)\), with \(a=2, b=2, \log_b a = 1\). This falls under Case 2 (\(k=0\)), giving \(T(n) = \Theta(n \log n)\).
7. Connections Between Discrete Mathematics and AI
| Area of Discrete Mathematics | AI Application |
|---|---|
| Graph theory | Graph Neural Networks (GCN, GAT, GraphSAGE), knowledge graphs, social network analysis |
| Combinatorial optimization | Search algorithms (A*, Monte Carlo Tree Search), scheduling, NP-hard approximation |
| Boolean algebra | SAT solvers, Constraint Satisfaction Problems (CSP), formal verification |
| Set theory / Relations | Relational database model, type systems |
| Recurrences / Generating functions | Algorithm complexity analysis, dynamic programming state transitions |
| Probabilistic combinatorics | Randomized algorithms, hash function analysis, Bloom filters |
Graph Theory and GNNs
The message-passing mechanism in Graph Neural Networks can be described in graph-theoretic terms: each node aggregates its neighbors' features (adjacency relationships) and updates its own representation. The expressive power of GNNs is closely related to the Weisfeiler-Leman graph isomorphism test.
References
- Rosen, Discrete Mathematics and Its Applications
- Diestel, Graph Theory
- Graham, Knuth & Patashnik, Concrete Mathematics
- MIT 6.042J: Mathematics for Computer Science