大学数学学习总结之离散数学：新人能看懂的核心脉络与避坑指南
- 约 38 分钟读完 - 全文 14826 字大学数学学习总结之离散数学：新人能看懂的核心脉络与避坑指南
目标读者：刚接触离散数学、看到 $\forall \exists$ 和哈斯图就发懵的大一同学；也适合想补计算机理论基础的自学者。不需要任何先修知识，高中数学就够了。
阅读目标：不追求证明的严格性，而是帮你建立整条知识主线——每个概念"是什么、为什么需要它、什么时候用它"。读完你应该能看懂教材目录背后的逻辑，知道每种题型对应哪件"工具"，并且明白这门课为什么被称为"计算机科学的数学"。
0. 先看全局：离散数学到底在研究什么
高等数学（微积分）研究的是连续的世界：光滑的曲线、连续变化的速度与面积。而离散数学研究的是离散的世界：一个个可数的、不连续的对象——真或假的命题、有限集合里的元素、图里的点和边、算法的步数。
为什么计算机专业把它列为核心基础课？因为计算机本身就是一台离散机器：
- 内存里只有 0 和 1，没有"连续"；
- 程序一步一步执行，步数可以数；
- 数据结构是集合、序列、树、图——全是离散对象。
所以这门课的全部内容，可以概括为一句话：学会用数学语言精确地描述和推理离散的、可数的结构。
下面的知识地图展示了本门课的主线结构，也是本文的目录：
flowchart TD
A["离散数学"] --> B["逻辑<br>推理的语言"]
A --> C["集合与关系<br>组织的语言"]
A --> D["函数<br>对应关系"]
A --> E["计数<br>数数的技术"]
A --> F["数论初步<br>整数的性质"]
A --> G["图论<br>结构与连接"]
A --> H["递推关系<br>算法分析入门"]
B --> B1["命题逻辑"]
B --> B2["谓词逻辑"]
C --> C1["集合运算"]
C --> C2["等价关系与划分"]
C --> C3["偏序关系与哈斯图"]
E --> E1["加法与乘法原理"]
E --> E2["排列组合"]
E --> E3["鸽笼原理"]
E --> E4["容斥原理"]
F --> F1["整除与同余"]
F --> F2["欧几里得算法"]
F --> F3["模运算与 RSA"]
G --> G1["基本概念与握手定理"]
G --> G2["欧拉图与哈密顿图"]
G --> G3["树与生成树"]
H --> H1["斐波那契数列"]
H --> H2["汉诺塔"]注意各章之间的依赖关系：逻辑是全书的语言（后面每章的定义和证明都用它写），集合与关系是骨架（函数、图都用它来定义），而计数、数论、图论是三大应用板块，递推关系则是通向《算法分析》的桥梁。建议按本文顺序学习，不要跳章。
1. 命题逻辑与谓词逻辑：推理的语言
1.1 命题与联结词
命题（proposition）是能判断真假的陈述句。“2 是偶数"是命题（真），“π 是无理数"是命题（真），“今天会下雨吗"不是命题（疑问句），“x 大于 3"也不是命题（真假取决于 x）。
用小写字母 $p, q, r$ 表示命题，它们只有两种取值：真（T / 1）或假（F / 0）。把简单命题用联结词粘起来，就得到复合命题。五个基本联结词的真值表是这一章的"乘法口诀表”，必须背熟：
| $p$ | $q$ | $\neg p$（非） | $p \land q$（与） | $p \lor q$（或） | $p \to q$（蕴含） | $p \leftrightarrow q$（等价） |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
这张表的用途：当你想验证一个复合命题"什么时候为真、什么时候为假”，就把所有变量的取值组合列出来逐行算——这叫真值表法，是验证命题公式最笨也最可靠的方法。
其中最容易踩坑的是蕴含 $p \to q$。它读作"如果 p 那么 q”，只有当 $p$ 真而 $q$ 假时才算假，其余三种情况都为真。特别是 $p$ 为假时，无论 $q$ 是真是假，整个蕴含都算真——这叫”虚真"（vacuously true）。比如"如果太阳从西边出来，我就把作业抄十遍"，前提永远为假，所以这句话在逻辑上永远成立（你别想靠它赖账）。
等值演算里第一条要记的公式就是这个：
$$p \to q ;\equiv; \neg p \lor q$$
白话解释：蕴含式可以无条件翻译成"非 p 或 q"。凡是不会处理蕴含的地方，先套这条公式把箭头消掉，再往下算。
1.2 等值演算
两个公式在所有取值下真假完全一致，就叫等值（记作 $\equiv$）。等值演算就是"逻辑版的代数变形"，常用定律如下：
- 德摩根律：
$$\neg (p \land q) ;\equiv; \neg p \lor \neg q, \qquad \neg (p \lor q) ;\equiv; \neg p \land \neg q$$
白话解释：否定穿过括号时，“与"变"或”、“或"变"与”。“并非（既高又帅）“等于"不高或者不帅”，而不是"不高且不帅”。写代码时 !(a && b) 和 !a || !b 等价，用的就是它。
- 分配律：$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$，以及 $\lor$ 对 $\land$ 的分配律。
- 吸收律：$p \lor (p \land q) \equiv p$，$p \land (p \lor q) \equiv p$。
- 双重否定：$\neg \neg p \equiv p$。
什么时候用：化简程序里的复杂 if 条件、证明两个逻辑表达式等价、以及数字电路设计里化简逻辑门——都用这套演算。
1.3 谓词逻辑与量词
命题逻辑的颗粒度太粗：“所有人都会死，苏格拉底是人，所以苏格拉底会死"这种推理，命题逻辑表达不了，因为它拆不开"所有人都会死"这句话。谓词逻辑把命题拆成个体 + 谓词：$P(x)$ 表示"x 具有性质 P”，再用量词限定范围：
- 全称量词 $\forall$：$\forall x \, P(x)$ 表示"对论域中所有 x，P(x) 成立"；
- 存在量词 $\exists$：$\exists x \, P(x)$ 表示"论域中至少存在一个 x 使 P(x) 成立"。
量词最重要的规则是带否定时如何翻转：
$$\neg \forall x \, P(x) ;\equiv; \exists x \, \neg P(x), \qquad \neg \exists x \, P(x) ;\equiv; \forall x \, \neg P(x)$$
白话解释：否定"所有人都及格"，等于说"存在至少一个人不及格"；否定"存在满分的人"，等于说"所有人都没满分"。否定穿过量词时，$\forall$ 变 $\exists$、$\exists$ 变 $\forall$，谓词本身加否定。这是写"反例"和"证否命题"的基本功。
下面这张图总结了本章的概念关系：
flowchart LR
P["命题<br>可真可假的陈述"] --> CL["五个联结词<br>非 与 或 蕴含 等价"]
CL --> TT["真值表<br>枚举所有取值"]
CL --> EQ["等值演算<br>逻辑代数变形"]
P --> PL["谓词逻辑<br>拆开命题内部结构"]
PL --> Q["量词<br>全称 与 存在"]
Q --> NQ["量词否定规则<br>否定穿过量词要翻转"]
TT --> APP["应用<br>电路验证 条件化简"]
EQ --> APP
NQ --> APP应用场景：逻辑电路与程序条件
- 数字电路：一个与门就是 $\land$，或门就是 $\lor$，非门就是 $\neg$。整个 CPU 的运算器，本质上是海量的命题公式在同时求值。用等值演算化简逻辑表达式，就能减少芯片上的门数量，省钱省电。
- 程序设计：复杂的
if条件就是复合命题，德摩根律是重构布尔表达式的日常工具；“循环不变式"的断言和验证，用的是谓词逻辑。 - 数据库：SQL 的
WHERE子句就是谓词，AND/OR/NOT直接对应三个联结词；EXISTS子查询就是存在量词。
2. 集合与关系：组织的语言
2.1 集合运算
集合（set）是若干对象的汇集，无序、不重复。属于记作 $x \in A$，不属于记作 $x \notin A$。集合的四大运算：
$$A \cup B = \{x \mid x \in A \lor x \in B\}, \qquad A \cap B = \{x \mid x \in A \land x \in B\}$$
$$\bar{A} = \{x \in U \mid x \notin A\}, \qquad A - B = \{x \mid x \in A \land x \notin B\}$$
白话解释：并集是"两边只要沾边就进来”，交集是"两边都在才进来"，补集是"全集里不要你的那部分"，差集是"在 A 里但不在 B 里"。画文氏图（Venn 图）是理解这些运算最快的办法。
集合运算也满足德摩根律，和逻辑里的形式完全平行：
$$\overline{A \cup B} = \bar{A} \cap \bar{B}, \qquad \overline{A \cap B} = \bar{A} \cup \bar{B}$$
白话解释：这和 1.2 节的逻辑德摩根律是同一条定律的两种写法——因为集合运算本来就是用 $\lor$、$\land$、$\neg$ 定义的。体会到这一点，你就理解了离散数学"各章相通"的感觉。
幂集（power set）：集合 A 的所有子集构成的集合，记作 $\mathcal{P}(A)$。若 A 有 n 个元素，则
$$|\mathcal{P}(A)| = 2^n$$
白话解释：每个元素都有"选 / 不选"两种自由，n 个元素就是 $2^n$ 种组合。这个公式在"枚举所有子集"的算法题里天天见。
2.2 笛卡尔积与二元关系
有序对 $(a, b)$ 讲究顺序，$(a, b) \neq (b, a)$。笛卡尔积：
$$A \times B = \{(a, b) \mid a \in A, \, b \in B\}$$
白话解释：把 A 的每个元素和 B 的每个元素配对，得到所有"搭配方案"的集合。坐标平面就是 $\mathbb{R} \times \mathbb{R}$；数据库表的多列取值组合也是笛卡尔积。
二元关系 R 就是 $A \times B$ 的一个子集：$(a, b) \in R$ 表示"a 和 b 有关系 R"。比如"小于关系"是 $\mathbb{R} \times \mathbb{R}$ 中满足 $a < b$ 的所有有序对。有限集合上的关系可以用关系矩阵（0-1 矩阵）或关系图（有向图）表示——这是图论登场的伏笔。
2.3 等价关系与划分
定义在集合 A 上的关系 R 若满足三条性质：
- 自反：对任意 $x \in A$，都有 $x R x$；
- 对称：若 $x R y$ 则 $y R x$；
- 传递：若 $x R y$ 且 $y R z$ 则 $x R z$；
就叫等价关系。典型例子：“同余”（mod m 意义下）、“同班”、“图里两点互相可达”。
等价关系把集合切成若干互不相交的等价类，所有等价类合起来叫 A 的一个划分（partition）。核心定理：
$$\text{“等价关系”} ;\longleftrightarrow; \text{“集合的划分”}$$
白话解释：给了一个等价关系，就能按"谁和谁等价"把集合切成一堆小格子；反过来给了一种切法，“同格"就是一个等价关系。两者是一回事的两个视角。
2.4 偏序关系与哈斯图
把上面三性中的"对称"换成”反对称"（若 $x R y$ 且 $y R x$ 则 $x = y$），得到的就是偏序关系（partial order），记作 $\preceq$。典型例子：整除关系、集合包含关系 $\subseteq$、实数的 $\le$。
“偏"的意思是：不要求任意两个元素都能比大小。比如在整除关系下，3 和 5 互不整除，不可比。
哈斯图（Hasse diagram）是偏序关系的简化画法：小的画下面、大的画上面，只画"紧挨着的覆盖关系”，自反环和传递边全省略。比如集合 $\{a, b\}$ 的幂集在包含关系下的哈斯图就是一个菱形。
下面用 mermaid 画这个哈斯图（菱形结构）：
flowchart BT
E["空集"] --> A["单元素集 a"]
E --> B["单元素集 b"]
A --> U["全集 ab"]
B --> U白话解释：从下往上读就是"被包含 → 包含"。空集最小、全集最大，两个单元素集在中间且互相不可比——所以中间一层是"横着排"而不是上下排。
应用场景：数据库与分类系统
- 关系数据库：一张表就是元组的集合，表本身就是"关系"（relation 一词由此而来）；
SELECT ... WHERE是取子集，JOIN基于笛卡尔积再筛选。关系代数的整套理论就是本章内容的直接应用。 - 等价类划分：软件测试里的"等价类划分法"，就是把无穷的输入空间按等价关系切成有限个类，每类挑一个代表测试。
- 偏序与拓扑排序：任务调度（先修课关系、编译依赖、Maven 依赖）都是偏序关系，拓扑排序就是给偏序找一个兼容的全序。
📜 历史故事：罗素悖论与第三次数学危机
19 世纪末，数学家们满怀信心地想用集合论给全部数学打地基。但 1901 年罗素发现了一个致命漏洞：考虑"所有不包含自身的集合所组成的集合"R，问 R 是否包含自身？若 R 包含自身，按定义它不该被收进来；若 R 不包含自身，按定义它又该被收进来——两头都矛盾。1902 年罗素把这个悖论写信告诉弗雷格，后者刚完成的著作地基瞬间崩塌，他只得在书末补记中写道：一位科学家完工之日，恰是地基坍塌之时，没有比这更不幸的了。这场危机史称"第三次数学危机"，后来人们用公理化集合论（ZFC）限制"什么样的总体算集合"，才把地基重新夯实。它提醒我们：“随便把一些东西凑成一个集合"这句话并不是永远合法的，这正是教材上定义集合时小心翼翼的深层原因。
3. 函数：对应关系
3.1 函数的定义
函数 $f: A \to B$ 是一种特殊的二元关系：A 中每个元素都恰好对应 B 中一个元素。两个要点缺一不可：每个输入都要有输出（处处有定义），且一个输入不能有两个输出（单值性）。
A 叫定义域，B 叫陪域，实际取到的值构成值域（image），值域是 B 的子集。
3.2 单射、满射、双射
这一节是考试和面试的高频考点，三种性质用一句话区分：
- 单射（injective，一对一）：不同输入必得不同输出，即 $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$。B 中没有"被抢座"的冲突。
- 满射（surjective，映上）：B 中每个元素都被击中，即 $\forall y \in B, \, \exists x \in A, \, f(x) = y$。值域填满整个陪域。
- 双射（bijective，一一对应）：既是单射又是满射，A 和 B 的元素严丝合缝一一配对。
白话解释：把 A 想成学生、B 想成座位。单射 = 没有两人抢一座；满射 = 没有空座；双射 = 人人有座、座座有人。
有限集合上有个常用推论：若 $f: A \to B$ 是双射，则 $|A| = |B|$。这是计数里”一一对应法“的原理——要数一个难数的集合，就找一个好数的集合和它建立双射。
3.3 复合函数与逆函数
复合：先 f 后 g，记作 $g \circ f$，定义为
$$(g \circ f)(x) = g(f(x))$$
白话解释：注意书写顺序和执行顺序相反，$g \circ f$ 是先做 f 再做 g。函数复合一般不满足交换律——“先穿袜子再穿鞋"和"先穿鞋再穿袜子"显然不是一回事。
逆函数：只有双射才有逆函数 $f^{-1}: B \to A$，满足
$$f^{-1}(f(x)) = x, \qquad f(f^{-1}(y)) = y$$
白话解释：逆函数就是"完美撤销”。只有双射能撤销，因为单射保证撤销时不会"一个输出对应回多个输入”，满射保证每个输出都撤得回去。这就是为什么密码学里加密函数必须设计成双射——否则密文解不回明文。
应用场景：哈希函数与数据结构
- 哈希表：哈希函数把无限的 key 空间映射到有限的桶地址空间，它天然不是单射——不同 key 撞同一桶叫"哈希冲突"，拉链法、开放寻址法都是在给"非单射"擦屁股。
- 加密：对称加密的加密函数必须是双射（否则无法解密）；公钥加密则利用"正向容易、逆向极难"的单向函数。
- 类型系统与序列化：序列化（serialize）和反序列化（deserialize）理想情况下互为逆函数。
4. 计数：数数的技术
计数这一章回答的问题是："满足某条件的方案一共有多少种？"——不枚举，用公式算。
4.1 加法原理与乘法原理
- 加法原理：做一件事有 m 类互斥办法，第 i 类有 $n_i$ 种做法，则总做法数为
$$N = n_1 + n_2 + \cdots + n_m$$
- 乘法原理：做一件事分 m 步，第 i 步有 $n_i$ 种做法，则总做法数为
$$N = n_1 \cdot n_2 \cdot \cdots \cdot n_m$$
白话解释：分类用加法，分步用乘法。“从北京去上海，高铁 3 班或飞机 5 班"是分类（选一类就行），$3 + 5 = 8$ 种；“先选上衣 4 件再选裤子 3 条"是分步（两步都要做），$4 \times 3 = 12$ 种。做题时先问自己：这些方案是"或"的关系还是"先…再…“的关系？
4.2 排列与组合
排列（讲顺序）：从 n 个不同元素取 k 个排成一列，
$$P(n, k) = \frac{n!}{(n-k)!}$$
组合（不讲顺序）：从 n 个不同元素取 k 个成一组，
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
白话解释：两者的唯一区别是"顺序算不算数”。选 3 个人当班长、学委、体委，职位不同所以讲顺序，是排列；选 3 个人去参加同一个会议，不讲顺序，是组合。组合数 $\binom{n}{k}$ 读作"n 选 k”，就是二项式系数。
组合数的常用性质：$\binom{n}{k} = \binom{n}{n-k}$（选 k 个留下，等于选 n-k 个扔掉），以及帕斯卡恒等式 $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$（杨辉三角的递推式）。
下面这张流程图帮你判断一道计数题该用哪个工具：
flowchart TD
Q["要数的问题"] --> S1{"是分类还是分步?"}
S1 -- "分类 互斥" --> ADD["用加法原理"]
S1 -- "分步 连贯" --> MUL["用乘法原理"]
MUL --> S2{"顺序算不算数?"}
S2 -- "算" --> PERM["排列 P n k"]
S2 -- "不算" --> COMB["组合 C n k"]
Q --> S3{"是否出现 至少 至多?"}
S3 -- "是" --> COMP["考虑反面 或 容斥原理"]
Q --> S4{"是否要求 必有...发生?"}
S4 -- "是" --> PIG["想想鸽笼原理"]4.3 鸽笼原理
鸽笼原理（抽屉原理）：把 n 只鸽子放进 k 个鸽笼，若 $n > k$，则至少有一个笼子里有不少于两只鸽子。加强版：
$$\text{至少有一个笼子里有不少于 } \left\lceil \frac{n}{k} \right\rceil \text{ 只鸽子}$$
白话解释：$\lceil x \rceil$ 是向上取整。367 个人里至少有两人同一天生日（n=367，k=366）；13 个人里至少 $\lceil 13/12 \rceil = 2$ 人同月出生。鸽笼原理的用法不是"计算”，而是"证明存在性"——它告诉你某种现象必然发生，虽然指不出具体是谁。
📜 历史故事：狄利克雷与抽屉原理
鸽笼原理由德国数学家狄利克雷（Dirichlet）在 1834 年明确提出，德语叫 Schubfachprinzip（抽屉原理）。他并不是把它当成智力趣题，而是用它严肃地证明了数论中"用有理数逼近无理数"的深刻结果（狄利克雷逼近定理）。一个看起来"显然得不能再显然"的原理能推出不显然的定理，这件事本身就很数学：伟大的工具往往长得朴素。后人为了纪念他，也把这个原理称为狄利克雷原理。
4.4 容斥原理
两个集合的容斥：
$$|A \cup B| = |A| + |B| - |A \cap B|$$
三个集合的容斥：
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
白话解释：直接加会重复计算重叠部分，所以要减掉交集；但三个集合时，减掉两两交集又把三者公共部分减过头了，要再加回来。奇加偶减，交替进行。
什么时候用：凡是"至少满足一个条件"的计数（并集），当交集比并集好算时用容斥；配合"反面计数"（总数减去反面）更是解决"至少/至多"问题的黄金搭档。
例题：1 – 100 中能被 2 或 3 整除的数有多少个？能被 2 整除的有 50 个，被 3 整除的有 33 个，被 6 整除的有 16 个，容斥得 $50 + 33 - 16 = 67$ 个。
应用场景：算法分析与概率
- 算法复杂度：估算循环执行次数、递归调用次数，本质都是计数；乘法原理告诉你两层嵌套循环是 $O(n^2)$。
- 概率论基础：古典概型就是"有利方案数 ÷ 总方案数"，分子分母都是排列组合问题。
- 密码与碰撞：生日悖论（23 人中两人同天生日的概率就超过 50%）是计数 + 鸽笼思想的结果，直接决定了哈希值需要多长才安全。
5. 数论初步：整数的性质
数论研究整数的整除结构，是离散数学里最"古老又最新潮"的一章——两千多年的老学问，如今撑着整个互联网的安全体系。
5.1 整除与最大公约数
若存在整数 k 使 $a = bk$（$b \neq 0$），称 b 整除 a，记作 $b \mid a$。否则记作 $b \nmid a$。
最大公约数 $\gcd(a, b)$：能同时整除 a 和 b 的最大整数。若 $\gcd(a, b) = 1$，称 a 与 b 互质。
求最大公约数用欧几里得算法（辗转相除法），核心递推就一行：
$$\gcd(a, b) = \gcd(b, \, a \bmod b)$$
白话解释：不断用"较小数"和"余数"替换原来的两个数，直到余数为 0，此时另一个数就是最大公约数。比如 $\gcd(48, 18) = \gcd(18, 12) = \gcd(12, 6) = \gcd(6, 0) = 6$。这是人类历史上最早的非平凡算法之一，两千年后仍是标准库里的实现。
扩展欧几里得算法还能顺手求出整数 s, t 使：
$$\gcd(a, b) = s \, a + t \, b$$
这叫裴蜀定理（Bézout’s identity）。干什么用：它是求"模逆元"的工具——而模逆元是 RSA 生成密钥的核心步骤。
5.2 同余与模运算
若 $m \mid (a - b)$，称 a 与 b 模 m 同余，记作
$$a \equiv b \pmod{m}$$
白话解释：a 和 b 除以 m 余数相同，在"模 m 的世界"里它们就是同一个数。时钟就是最直观的模运算：15 点 $\equiv$ 3 点（mod 12）。
同余的妙处在于它对加、减、乘都"兼容"：
$$(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m$$
$$(a \cdot b) \bmod m = \big((a \bmod m) \cdot (b \bmod m)\big) \bmod m$$
白话解释：可以先取余再运算，结果一样。这让你能计算天文数字的个位：$7^{100}$ 的末位，只需看 $7^4 \equiv 1 \pmod{10}$，于是 $7^{100} = (7^4)^{25} \equiv 1 \pmod{10}$，末位是 1。完全不用算出那个 85 位数。
模运算下的快速幂（反复平方法）把 $a^n$ 的计算量从 n 次乘法降到 $O(\log n)$ 次，是密码学能落地的前提。
5.3 素数与 RSA 的思想
素数（质数）是大于 1 且只有 1 和自身两个正因子的整数。算术基本定理：每个大于 1 的整数都能唯一分解为素数的乘积。
RSA 的安全基石是下面的不对称性：
- 正向容易：给你两个大素数 p 和 q，算 $n = p \, q$ 只要一次乘法；
- 逆向极难：只给你 n，分解出 p 和 q 在计算上不可行（大整数分解难题）。
密钥生成用欧拉函数：$\varphi(n) = (p-1)(q-1)$，再选 e 满足 $\gcd(e, \, \varphi(n)) = 1$，用扩展欧几里得算法求 d 使
$$e \, d \equiv 1 \pmod{\varphi(n)}$$
公钥是 $(n, e)$，私钥是 $(n, d)$。加密是 $c \equiv m^e \pmod{n}$，解密是 $m \equiv c^d \pmod{n}$。
📜 历史故事：1977 年，密码学走出保密室
在 1970 年代之前，加密双方必须事先偷偷约好同一把钥匙，密钥分发本身就是死结。1977 年，MIT 的三位年轻研究者 Rivest、Shamir、Adleman 发表了一种全新的方案：加密用公开的钥匙，解密用私有的钥匙，即使敌人知道加密方法也解不开。取三人姓氏首字母，这就是 RSA。同年，科普作家马丁·加德纳在《科学美国人》专栏介绍了这个算法，并悬赏破解一个 129 位的 RSA 密文——该挑战直到 1994 年才被一个分布式计算项目攻破。RSA 让"素数"“同余"这些古老的纯数学概念，一夜之间变成了电子商务的看门人。如今你浏览器地址栏的小锁头背后，跑的就是 5.2 节的同余运算。
应用场景：密码学与校验码
- RSA 与 TLS：上面讲过，不重复。重点是理解为什么离散数学的"数论初步"不是屠龙之技。
- 哈希与校验：身份证最后一位、ISBN 书号、CRC 校验，都是模运算（mod 11、mod 10 等）的应用。
- 负载均衡与分库分表：
hash(key) mod N决定数据落到哪台机器，模运算每天都在分布式系统里被执行亿万次。
6. 图论：结构与连接
6.1 图的基本概念
图（graph）由顶点集 V 和边集 E 组成，记作 $G = (V, E)$。边是顶点的无序对（无向图）或有序对（有向图）。
- 度 $\deg(v)$：顶点 v 关联的边数（有向图分出度、入度）；
- 路径（path）：顶点依次相连、边不重复（严格定义教材略有差异，做题时以课本为准）；
- 连通：任意两点间都有路径可达；
- 完全图 $K_n$：n 个顶点两两之间都有边，共 $\binom{n}{2}$ 条边。
图论第一定理——握手定理：
$$\sum_{v \in V} \deg(v) = 2|E|$$
白话解释：所有顶点的度数之和等于边数的两倍，因为每条边给两端各贡献 1 度。推论：奇数度的顶点必有偶数个（总和是偶数，奇数度顶点若为奇数个，总和就成奇数了）。这个推论常用来秒杀选择题。
6.2 欧拉图与哈密顿图
这是最容易混淆的一对概念，先给判别法再给故事。
- 欧拉回路：经过每条边恰好一次并回到起点的回路。无向连通图存在欧拉回路的充要条件：所有顶点度数为偶数。存在欧拉通路（不回到起点）的条件是恰有两个奇度顶点。
- 哈密顿回路：经过每个顶点恰好一次并回到起点的回路。没有简单的充要条件，判定一般图的哈密顿回路是 NP 完全问题——这正是它难的地方。
flowchart TD
Q["一笔画 / 遍历问题"] --> A{"要求是什么?"}
A -- "每条边恰好一次" --> E["欧拉图问题"]
A -- "每个顶点恰好一次" --> H["哈密顿图问题"]
E --> E1{"所有顶点度数为偶数?"}
E1 -- "是" --> E2["存在欧拉回路 可一笔画回起点"]
E1 -- "恰两个奇度点" --> E3["存在欧拉通路 从奇点起到奇点止"]
E1 -- "奇度点超过两个" --> E4["不存在 无法一笔画"]
H --> H1["无通用判别法<br>靠经验定理或搜索"]📜 历史故事：哥尼斯堡七桥，一门学科的诞生
18 世纪的哥尼斯堡（今俄罗斯加里宁格勒）有条河穿城而过，河中有两座岛，七座桥把岛和两岸连起来。市民们有个消遣：能不能散步时把每座桥恰好走一次，最后回到出发点？1736 年，欧拉解决了这个问题。他的关键一步是抽象：把陆地缩成点、把桥画成线，地理问题瞬间变成"一笔画"问题。然后他注意到一个朴素的事实：除了起点和终点，每进入一个顶点就要离开一次，所以中间顶点的度数必须是偶数。而七桥图中四个顶点全是奇数度——答案是不可能。这篇论文被公认为图论的开端，也是拓扑学思想的萌芽。欧拉示范了数学建模的完整流程：舍弃无关细节（岛的大小、桥的长短），只保留连接关系——这正是今天我们用图建模社交网络、路网的思维方式。
6.3 树与生成树
树（tree）：连通且无回路的图。n 个顶点的树有一堆等价的刻画，最常用的一条：
$$|E| = |V| - 1$$
白话解释：n 个顶点的树恰好有 n-1 条边——多一条必出环，少一条必不连通。“恰好"两个字说明树是最省的连通结构：用最少的边把所有点连起来。
生成树（spanning tree）：包含图 G 所有顶点的、用 G 的边构成的树。带权图中边权和最小的生成树叫最小生成树（MST），用 Kruskal 或 Prim 算法求——这两个算法属于贪心算法的经典教材案例。
树的重要性质（都能用 $|E| = |V| - 1$ 和"无环"推出来）：
- 任意两点间有唯一路径；
- 删去任一条边，树就断开；
- 添上任一条新边，恰好出现一个环。
应用场景：网络路由与编译器
- 网络路由：互联网的骨干网路由要避免环路，生成树协议（STP）就是在交换网络里动态维护一棵生成树；OSPF 的最短路径计算基于 Dijkstra 算法。
- 编译器：源代码被解析成抽象语法树（AST）；表达式求值、作用域管理都在树上进行。
- 社交网络与推荐：好友关系是无向图，“你可能认识的人"是图上的二度邻居查询；社区发现、 PageRank 都是图算法。
- 路径规划：地图 App 的导航就是带权图上的最短路问题；旅行商问题（TSP）是哈密顿回路的加权版，NP 难，催生了整个近似算法领域。
7. 递推关系初步：算法分析入门
递推关系（recurrence）用数列前面的项定义后面的项，配上初始条件就能唯一确定整个数列。它是"用数学语言描述递归"的工具，也是《算法导论》分析递归算法复杂度的起点。
7.1 斐波那契数列
$$F_n = F_{n-1} + F_{n-2}, \qquad F_0 = 0, \; F_1 = 1$$
白话解释：从第三项起，每一项是前两项之和：0, 1, 1, 2, 3, 5, 8, 13, …。它有两个经典用途：一是演示"递归定义”（函数自己调用自己）；二是演示朴素递归的指数级浪费与动态规划的改进——直接递归算 $F_n$ 要重复计算大量子问题，改成自底向上填表后只需 $O(n)$。
斐波那契还有封闭形式的通项公式（比内公式），涉及无理数 $\sqrt{5}$，本科阶段知道它存在即可：递推式理论上可以解出显式公式，但大多数场合用递推式本身更方便。
7.2 汉诺塔
n 个盘子从 A 柱借助 B 柱移到 C 柱，大盘不能压小盘，最少移动次数记为 $H(n)$。把上面的 n-1 个盘子先挪到 B（$H(n-1)$ 步），大盘挪到 C（1 步），再把 n-1 个盘子挪回 C（$H(n-1)$ 步），于是：
$$H(n) = 2 \, H(n-1) + 1, \qquad H(1) = 1$$
展开迭代几轮找规律：
$$H(n) = 2 \, H(n-1) + 1 = 2^2 H(n-2) + 2 + 1 = \cdots = 2^n - 1$$
白话解释：每多一个盘子，步数翻倍还多一。64 个盘子要 $2^{64} - 1$ 步——传说是僧侣搬完世界就毁灭的那个数字，约 5800 多亿年（每秒一步）。这个例子让你直观感受指数增长的恐怖，也是理解"为什么指数复杂度算法不能用"的第一课。
应用场景：递归算法的时间复杂度
- 分治算法：归并排序的复杂度满足 $T(n) = 2T(n/2) + O(n)$，解出来是 $O(n \log n)$——解递推关系就是给算法"算工资”。
- 动态规划：状态转移方程（如背包问题、编辑距离）全是递推关系，写 DP 代码就是把数学递推式翻译成填表循环。
- 数据结构分析：二叉树高度与节点数的关系、哈希表扩容的均摊分析，都用递推刻画。
8. 避坑技巧：新人最容易犯的 10 个错误
下面 10 条几乎每条都有人挂过科。按"错误说法 → 正确理解 → 简短例子"自查。
坑 1：把 $\to$ 当成"因为所以”
- 错误说法：$p \to q$ 表示 p 是 q 的原因。
- 正确理解：蕴含只描述真值关系，不描述因果。只要"前件真且后件假"不出现，蕴含就成立。
- 例子：“如果 2 是偶数，那么雪是白的"是真命题，尽管两者毫无因果。
坑 2：忘记"虚真”，觉得 p 假时 $p \to q$ 无意义
- 错误说法：前提不成立时，蕴含式"不成立"。
- 正确理解：前件为假时蕴含式为真（虚真）。
- 例子：“所有会飞的猪都戴眼镜"是真的——因为不存在会飞的猪，找不到反例。
坑 3：把 $p \to q$ 和它的逆命题 $q \to p$ 混为一谈
- 错误说法：“若 p 则 q"成立，所以"若 q 则 p"也成立。
- 正确理解：与原命题等价的是逆否命题 $\neg q \to \neg p$；逆命题和否命题都不等价。
- 例子：“下雨则地湿"为真，推不出"地湿则下雨”（可能是洒水车），但能推出"地没湿则没下雨”。
坑 4：量词否定只否一半
- 错误说法：$\neg \forall x \, P(x)$ 等于 $\forall x \, \neg P(x)$。
- 正确理解：否定穿过量词必须翻转量词：$\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$。
- 例子：“并非所有人都及格”≠“所有人都不及格”，正确是"存在至少一个人不及格”。
坑 5：把 $\subseteq$ 和 $\in$ 用混
- 错误说法：$\{1\} \in \{1, 2, 3\}$。
- 正确理解：$\in$ 连接"元素和集合"，$\subseteq$ 连接"集合和集合"。
- 例子：$1 \in \{1, 2, 3\}$，$\{1\} \subseteq \{1, 2, 3\}$，两者各安其位。
坑 6：以为任意关系都有"三性"
- 错误说法：自反、对称、传递是绑定的，证明一条就行。
- 正确理解：三条性质互相独立，必须分别验证；而且等价关系要三条全占，偏序要自反 + 反对称 + 传递。
- 例子：“整除"在正整数上自反、传递但不对称，所以它不是等价关系而是偏序关系。
坑 7：把"满射"理解成"每个输入都有输出”
- 错误说法：函数每个 x 都有 f(x)，所以是满射。
- 正确理解：“每个输入有输出"是函数定义的基本要求，跟满射无关；满射要求陪域里每个 y 都被击中。
- 例子：$f: \mathbb{R} \to \mathbb{R}$，$f(x) = x^2$ 不是满射（负数没被击中），但若陪域改成 $[0, +\infty)$ 就是满射——满不满射取决于你声明的陪域。
坑 8：排列组合不分，看到"取 k 个"就套 $P(n, k)$
- 错误说法：从 10 人里选 3 人参赛，有 $P(10, 3) = 720$ 种选法。
- 正确理解：先问"选出来的 3 人内部排不排名次”。不排就是组合 $\binom{10}{3} = 120$。
- 例子：选 3 人当不同职务用排列（职务即顺序），选 3 人做同一件事用组合。
坑 9：容斥原理里忘了"奇加偶减"，减完就停
- 错误说法：$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C|$。
- 正确理解：三集合时还要加回三者交集 $|A \cap B \cap C|$，因为它被减过头了。
- 例子：三班都报兴趣班的 5 人，在单班人数里被算了 3 次、在两两交集里被减了 3 次，净算 0 次，必须加回。
坑 10：握手定理数错边，或者以为奇度点可以是奇数个
- 错误说法：一个图可以有 3 个度数为 3 的顶点，其余顶点度数为偶数。
- 正确理解：度数总和 $= 2|E|$ 必为偶数，所以奇度顶点必有偶数个。
- 例子：想构造"恰有 3 个奇度点"的图是徒劳的，这在动笔前就能排除。
9. 应用全景：离散数学与计算机科学的对应表
最后把整门课映射到计算机科学，方便你日后"按图索骥"：
flowchart LR
subgraph DM["离散数学"]
L["命题与谓词逻辑"]
S["集合与关系"]
F["函数"]
C["计数"]
N["数论"]
G["图论"]
R["递推关系"]
end
subgraph CS["计算机科学"]
HW["数字电路 芯片设计"]
DB["关系数据库 SQL"]
AI["人工智能 知识推理"]
AL["算法复杂度分析"]
CR["密码学 RSA 区块链"]
NET["网络路由 社交网络"]
PL["编译器 程序验证"]
end
L --> HW
L --> AI
L --> PL
S --> DB
S --> PL
F --> DB
F --> CR
C --> AL
C --> CR
N --> CR
G --> NET
G --> AL
R --> AL一句话总结这张全景图：离散数学不是一门课，而是计算机科学的"语法书"——你以后学的每一门专业课，都在用这里的符号说话。
10. 学习建议与资源建议
学习建议：
- 先建立"定义直觉"，再背定理。每个概念先找一个生活例子（等价关系→分班，偏序→先修课，双射→对号入座），例子记住了，定义就忘不掉。
- 真值表和文氏图是底线工具。等值式证明不出来就列真值表，集合等式证不出来就画文氏图——笨办法永远兜底。
- 做题先问"这题考哪个工具"。离散数学的题目套路化程度高：出现"至少/至多"想容斥或反面计数，出现"必然存在"想鸽笼，出现"一笔画"想度数奇偶，出现"递归式"想展开迭代。
- 亲手推一遍经典结论。欧几里得算法、$H(n) = 2^n - 1$ 的展开、握手定理的证明，都不超过五行，亲手推一遍胜过读十遍。
- 用代码验证数学。学排列组合就写个
itertools.permutations数数对不对，学欧几里得算法就自己实现一遍——离散数学是少数能"当场编程验证"的数学课，别浪费这个福利。
资源建议：
- 教材：屈婉玲、耿素云、张立昂《离散数学》（高等教育出版社），国内高校主流教材，习题经典；国外可配 Rosen 的 Discrete Mathematics and Its Applications（《离散数学及其应用》），例子极多、应用导向。
- 课程：MIT 6.042 Mathematics for Computer Science（有公开讲义和公开课），计算机视角讲离散数学，非常对胃口。
- 工具：纸上画哈斯图和文氏图；代码验证用 Python（
itertools、sympy足够）。 - 练习顺序建议：每章先做教材课后基础题，概念题（判断对错、举例）优先于计算题——离散数学挂科往往挂在概念混淆，而不是算错数。
祝学习顺利。这门课一旦"通了"，你再看算法、数据库、密码学的教材，会发现满篇都是老朋友。
18 年后端架构，现在独立做 AI 产品。这里记录 AI 视频、AI Agent 与工程实践。