IB Discrete Mathematics | IB 离散数学

📚 IB Discrete Mathematics | IB 离散数学

Discrete mathematics is a fundamental component of the IB Mathematics curriculum, appearing in both Analysis & Approaches (AA) and Applications & Interpretation (AI). This area covers topics such as logic, sets, combinatorics, graph theory, algorithms, and discrete probability distributions. Mastering these concepts equips you with powerful tools for problem-solving, algorithmic thinking, and understanding the structures that underpin computer science and modern data analysis.

离散数学是IB数学课程的基础组成部分，同时出现在分析与方法(AA)和应用与解释(AI)中。该领域涵盖逻辑、集合、组合数学、图论、算法和离散概率分布等主题。掌握这些概念能为你提供解决问题的有力工具，培养算法思维，并助你理解支撑计算机科学和现代数据分析的结构。

1. Set Theory and Logic | 集合论与逻辑

A set is a well-defined collection of objects. Key operations include union (∪), intersection (∩), complement, and set difference. Venn diagrams are used to visualise these relationships. In logic, we use connectives: conjunction (AND, ∧), disjunction (OR, ∨), negation (NOT, ¬), and implication (→). Truth tables provide a systematic way to determine the truth values of compound statements.

集合是明确界定的一组对象。基本运算包括并集(∪)、交集(∩)、补集和差集。韦恩图用于直观展示这些关系。在逻辑中，我们使用连接词：合取(AND, ∧)、析取(OR, ∨)、否定(NOT, ¬)和蕴含(→)。真值表为确定复合命题的真值提供了一种系统方法。

Understanding how to translate between set notation and logical expressions is essential. For example, an element x belonging to the intersection of sets A and B means x ∈ A ∩ B, which is logically equivalent to x ∈ A ∧ x ∈ B.

理解集合符号与逻辑表达式之间的转换至关重要。例如，元素x属于集合A与B的交集意味着x ∈ A ∩ B，这在逻辑上等价于x ∈ A ∧ x ∈ B。

2. Permutations and Combinations | 排列与组合

Counting principles form the basis of combinatorics. The factorial of a positive integer n is defined as n! = n × (n − 1) × … × 2 × 1, with 0! = 1. A permutation is an arrangement of objects where order matters. The number of permutations of n distinct objects taken r at a time is P(n, r) = n! / (n − r)!.

计数原理是组合数学的基础。正整数n的阶乘定义为n! = n × (n − 1) × … × 2 × 1，且0! = 1。排列是考虑顺序的对象排列方式。从n个不同对象中取出r个的排列数为P(n, r) = n! / (n − r)!。

A combination is a selection of objects where order does not matter. The number of combinations of n distinct objects taken r at a time is C(n, r) = n! / [r! (n − r)!], often written as nCr. The multiplication principle states that if one event can occur in m ways and another in n ways, then both can occur in m × n ways.

组合是不考虑顺序的对象选择方式。从n个不同对象中取出r个的组合数为C(n, r) = n! / [r! (n − r)!]，常写作nCr。乘法原理指出，若一个事件有m种发生方式，另一个事件有n种方式，则两者共同发生的方式为m × n种。

3. The Binomial Theorem | 二项式定理

The binomial theorem gives the expansion of (a + b)ⁿ for a positive integer n. The expansion is given by:
(a + b)ⁿ = Σ C(n, r) aⁿ⁻ʳ bʳ, for r = 0 to n. The coefficients C(n, r) are called binomial coefficients and can be read from Pascal’s triangle, where each entry is the sum of the two above it.

二项式定理给出了正整数n时(a + b)ⁿ的展开式。展开式为：
(a + b)ⁿ = Σ C(n, r) aⁿ⁻ʳ bʳ，求和从r=0到n。系数C(n, r)称为二项式系数，可以从帕斯卡三角形中读取，其中每个数是它上方两数之和。

To find a specific term, say the term containing xᵏ, use the general term T_{r+1} = C(n, r) aⁿ⁻ʳ bʳ. This is particularly useful when solving for unknown exponents or coefficients in IB questions. The sum of all binomial coefficients for a given n equals 2ⁿ.

要找到特定项，比如包含xᵏ的项，可使用通项公式T_{r+1} = C(n, r) aⁿ⁻ʳ bʳ。在解答IB问题中求解未知指数或系数时，这尤为有用。对于给定的n，所有二项式系数之和等于2ⁿ。

4. Proof by Mathematical Induction | 数学归纳法证明

Mathematical induction is a method used to prove statements for all natural numbers n. It consists of three main steps: prove the base case (usually n=1) is true; assume the inductive hypothesis that the statement holds for n = k; then prove that the statement is true for n = k + 1 using the hypothesis. If successful, the statement holds for all n ≥ 1 by induction.

数学归纳法用于证明对所有自然数n成立的命题。它包含三个主要步骤：证明基础情形（通常n=1）为真；假设归纳假设，即命题对n = k成立；然后利用该假设证明命题对n = k + 1成立。若成功，则由归纳法可得命题对所有n ≥ 1成立。

Example: Prove that 1 + 2 + 3 + … + n = ½ n(n + 1). Base case n=1: LHS=1, RHS=½ × 1 × 2 = 1, true. Inductive hypothesis: assume sum to k is ½ k(k+1). Then for n=k+1: LHS = ½ k(k+1) + (k+1) = (k+1)(k/2 + 1) = ½ (k+1)(k+2) = RHS. The proof is complete.

例如：证明1 + 2 + 3 + … + n = ½ n(n + 1)。基础情形n=1：左边=1，右边=½ × 1 × 2 = 1，成立。归纳假设：设前k项之和为½ k(k+1)。则对n=k+1：左边 = ½ k(k+1) + (k+1) = (k+1)(k/2 + 1) = ½ (k+1)(k+2) = 右边。证明完成。

5. Introduction to Graph Theory | 图论导论

A graph consists of vertices (nodes) and edges connecting them. The degree of a vertex is the number of edges incident to it. A simple graph has no loops or multiple edges. A graph is connected if there is a path between every pair of vertices. A complete graph Kₙ has n vertices and every pair is connected by an edge. A bipartite graph has its vertex set divided into two disjoint sets where edges only go between the sets.

图由顶点（节点）和连接它们的边构成。顶点的度是指与该顶点相连的边的数目。简单图无自环或多重边。若图中任意两顶点间都存在一条路径，则称该图是连通的。完全图Kₙ有n个顶点且每对顶点间均有边相连。二分图将顶点集划分为两个不相交的集合，边仅存在于不同集合之间。

Graphs can be represented by an adjacency matrix A, where A[i][j] = 1 if there is an edge between vertex i and vertex j, and 0 otherwise. For an undirected graph, the adjacency matrix is symmetric. This representation is useful for algorithmic processing in IB AI.

图可以用邻接矩阵A表示，若顶点i与顶点j间有边，则A[i][j] = 1，否则为0。对于无向图，邻接矩阵是对称的。这种表示在IB AI中的算法处理中十分有用。

6. Eulerian and Hamiltonian Paths | 欧拉路径与哈密顿路径

An Eulerian trail visits every edge of a graph exactly once; an Eulerian circuit is an Eulerian trail that starts and ends at the same vertex. A connected graph has an Eulerian circuit if and only if every vertex has an even degree. It has an Eulerian trail but not a circuit if it has exactly two vertices of odd degree. These conditions are easy to check.

欧拉路径恰好经过图中每条边一次；欧拉回路是起点和终点相同的欧拉路径。一个连通图含有欧拉回路当且仅当所有顶点的度均为偶数。若连通图恰好有两个奇度顶点，则它含有欧拉路径但不含回路。这些条件很容易验证。

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does so and returns to the start. Unlike Eulerian paths, there is no simple necessary and sufficient condition for the existence of Hamiltonian paths. This problem is NP-complete, but for small graphs it can be tested by inspection or systematic search.

哈密顿路径恰好经过每个顶点一次；哈密顿循环则在此基础上回到起点。与欧拉路径不同，哈密顿路径的存在性没有简单的充要条件。这是一个NP完全问题，但对于小规模图可通过观察或系统搜索进行验证。

7. Trees and Minimum Spanning Trees | 树与最小生成树

A tree is a connected graph with no cycles. Properties: a tree with n vertices has exactly n − 1 edges, and any two vertices are connected by a unique simple path. A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree. A weighted graph has a number (weight) associated with each edge.

树是无回路的连通图。其性质为：有n个顶点的树恰好有n − 1条边，且任意两顶点间由唯一的一条简单路径相连。连通图的生成树是包含所有顶点且构成树的子图。带权图的每条边都关联一个数值（权重）。

A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight. Two classic algorithms to find an MST are Kruskal’s algorithm and Prim’s algorithm. Both are greedy algorithms often examined in IB Applications & Interpretation.

最小生成树(MST)是总边权重最小的生成树。寻找MST的两种经典算法是Kruskal算法和Prim算法。两者都是贪心算法，常在IB应用与解释课程中考查。

8. Algorithms on Graphs (Kruskal, Prim, Dijkstra) | 图的算法（Kruskal, Prim, Dijkstra）

Kruskal’s algorithm works by sorting all edges by weight and adding them one by one, as long as they don’t form a cycle. Use a disjoint-set to track connectivity. Prim’s algorithm starts from an arbitrary vertex and repeatedly adds the cheapest edge that connects a vertex in the tree to a vertex outside, growing the tree until all vertices are included.

Kruskal算法通过按权重排序所有边，并逐一添加不会形成回路的边来实现。可使用并查集跟踪连通性。Prim算法从任一顶点开始，反复添加连接树内与树外顶点的最便宜边，逐步扩展树直至包含所有顶点。

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. It maintains a set of visited vertices and iteratively selects the unvisited vertex with the smallest tentative distance, updating distances for its neighbors. This is fundamental for network routing and logistics problems.

Dijkstra算法可在具有非负权重的带权图中找出从源顶点到所有其他顶点的最短路径。它维护一个已访问顶点集合并迭代选择未访问顶点中暂定距离最小的顶点，并更新其邻居的距离。这是网络路由和物流问题的基础。

9. Travelling Salesman Problem (TSP) | 旅行商问题

The Travelling Salesman Problem seeks the shortest possible route that visits each vertex exactly once and returns to the start. For a small number of vertices, the exact solution can be found by brute force checking all possible Hamiltonian cycles. However, as the number of cities grows, the factorial increase makes exact methods impractical, so heuristic algorithms are used.

旅行商问题寻找一条恰好访问每个顶点一次并返回起点的最短可能路线。对于少量顶点，可通过穷举所有可能的哈密顿循环来找到精确解。然而随着城市数量增长，阶乘暴涨使得精确方法不切实际，因此需使用启发式算法。

To find an upper bound, use the nearest neighbour algorithm: start at a vertex, repeatedly go to the nearest unvisited vertex, then return to the start. A lower bound can be found by deleting a vertex, finding an MST of the remaining graph, and adding the two smallest edges from the deleted vertex to the MST weight. This gives an interval containing the optimal tour length.

要找到上界，可使用最近邻算法：从某顶点出发，反复前往最近的未访问顶点，最后返回起点。下界可通过删除一个顶点，找出剩余图的MST，并将所删顶点的两条最小边权重加至MST权重而得到。这给出了包含最优路线长度的区间。

10. Discrete Probability Distributions | 离散概率分布

The binomial distribution models the number of successes in a fixed number of independent trials, each with the same probability of success p. If X ~ B(n, p), then P(X = k) = C(n, k) pᵏ (1 − p)ⁿ⁻ᵏ, with mean E(X) = np and variance Var(X) = np(1 − p). This distribution is widely used in quality control and survey analysis.

二项分布对固定次数的独立试验中成功的次数建模，每次成功概率为p。若X ~ B(n, p)，则P(X = k) = C(n, k) pᵏ (1 − p)ⁿ⁻ᵏ，均值E(X) = np，方差Var(X) = np(1 − p)。该分布广泛用于质量控制和调查分析。

The Poisson distribution models the number of events occurring in a fixed interval of time or space, assuming these events happen with a constant mean rate λ and independently. If Y ~ Po(λ), then P(Y = k) = (λᵏ e⁻λ) / k!, with mean and variance both equal λ. It approximates the binomial when n is large and p is small with λ = np.

泊松分布对固定时间或空间间隔内发生的事件次数建模，假设事件以恒定平均速率λ独立发生。若Y ~ Po(λ)，则P(Y = k) = (λᵏ e⁻λ) / k!，均值与方差均为λ。当n很大且p很小且λ = np时，该分布可近似二项分布。

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

IB Discrete Mathematics | IB 离散数学