离散数学专题
这一页是全专题的总览与学习地图：它不代替任何一章的正文，而是告诉你八章各自教你什么能力、为什么按这个顺序排列、每天应该用什么方式读。读完这一页，你应该能对着自己手头的真实问题判断：先点开哪一章，哪些章可以暂时跳过。
先保留一个最短的核心答案：离散数学不是一门单一学科，而是一组共享可枚举结构——取值可数、可列的对象——的工具。它的价值不在公式，而在提供一套把”直觉”翻译成”可以证明的命题”的语言。
学习路径：顺序与依赖
八章不是按知识门类排的，而是按依赖关系排的。
第 1 章 命题逻辑与证明 必须先读。 后面每一章的定理都要用蕴含、量词和归纳法来表达；在读懂这一章之前，“证明一个命题”这件事本身没有严格含义。逻辑先行不是传统，是依赖关系决定的。
第 2 章 集合、关系与函数 紧随其后。 它是描述一切对象的语法：图是顶点集上的二元关系，等价类是聚类的数学定义，函数概念贯穿组合计数与数论。没有它，后面各章研究的对象都无法精确陈述。
第 3 章 组合计数 排在第 4 章之前，因为图论里”有多少条路径、多少棵生成树”这类问题要直接调用计数的工具箱；反过来，计数几乎不依赖图论，先读它不会卡住。
第 4 章 图论基础 是前四章的应用高峰，也是与 GeoAI、图学习关系最直接的一章：它同时调用逻辑（用归纳法证明树的性质）、关系（图本身就是一种二元关系）和计数（路径计数、树的计数）。前四章连起来构成一个完整闭环，读完第 4 章，你就能读懂 GNN 消息传递的数学描述。
第 5、6 章相对独立，可按兴趣插入。 数论初步 只需要第 1 章的证明语言；递归与递推 需要第 1 章的归纳法，最好再有一点第 2 章的函数概念。
第 7、8 章标为进阶。 生成函数 建立在第 3 章组合计数之上；代数结构 需要第 2 章的关系概念，并最好已经见过第 4 章的图作为具体例子。第一轮学习可以整体跳过，二轮再回来。
各章一览
每章一段：它教你什么能力，一个你会因此看懂的具体场景，以及点开它之前你该有的问题感。
第 1 章：命题逻辑与证明。 教你把”这个算法对所有输入正确”变成一段可逐步检查的论证，而不是一段有说服力的散文。学完之后，你能读懂循环不变量、递归终止性这类真实代码里的证明。问题感：怎样的论证才算数？
第 2 章：集合、关系与函数。 给你精确描述对象的语法，重点是等价关系与偏序。场景：你会明白为什么”相似”不满足传递性时聚类结果必然重叠，为什么规则网格划分空间等价于按坐标取整定义等价类。问题感：对象之间的结构到底是什么？
第 3 章：组合计数。 回答”有多少种可能”，而且不逐一列举。场景：用乘法原理估算超参配置空间的量级，用鸽巢原理理解哈希表装载因子超过 1 后为什么必有冲突。问题感：不数出来，怎么知道有多少？
第 4 章：图论基础。 当研究对象本身就是关系——道路、网络、社交链接——时的统一语言。场景：读懂邻接矩阵的幂与路径计数的对应、谱分解与图嵌入的关系，以及 GNN 第 层的信息半径。问题感：这些关系型数据如何共用一套数学对象？
第 5 章：数论初步。 整除结构如何决定取模运算的行为。场景：理解一致性哈希和伪随机生成器的周期，以及 RSA 为什么”模幂算得快、分解大数难”。问题感：取模凭什么够用，密码学凭什么成立？
第 6 章：递归与递推。 定义和处理”用自己定义自己”的对象，并估算其代价。场景：分析四叉树、R 树这类空间划分结构的复杂度，写出树上的动态规划递推式并用主定理判定分治算法的规模。问题感：自我引用的结构，怎么算出它的代价？
第 7 章：生成函数（进阶）。 把一串计数结果编码进一个幂级数，用代数运算代替组合推理。场景：估算带约束的数据增强策略的组合规模，解析地计算随机抽样的覆盖程度。问题感：计数一旦带上约束，组合推理变得太绕，怎么办？
第 8 章：代数结构（进阶）。 解释为什么逻辑、集合、数系与对称性共享同一套运算律。场景：用群作用精确定义数据增强的旋转、平移、置换不变性——等变网络的设计语言就建立在这上面。问题感：这些看似无关的结构，共同本质是什么？
怎么用这个教程
- 按顺序读主干。 第 1 到第 4 章有严格的先后依赖，不建议跳；第 5、6 章可在读完第 2 章后按需插入；第 7、8 章属于二轮内容。
- 例题先自己做，再看解答。 直接看解答的收益大约只有先做一遍的三分之一：卡住的地方才是你需要重读定义的地方。
- 练习必做。 每章末尾的练习都给出答案或提示；不做练习，“看懂”和”会用”之间的鸿沟不会被填上。
- 跳读建议。 时间紧时读第 1、2、4 章主干，加上各章讨论与 GeoAI、空间分析联系的段落；数论和递归用到时再回头补。
进一步阅读
想把这些板块按软件工程视角串成一本可读的入门书，可以看 O’Regan 的 Mathematical Foundations of Software Engineering: A Practical Guide to Essentials（2023），它覆盖逻辑、集合、图论与数论，始终面向工程应用 (O’Regan, 2023)。
公认教材中，Kenneth Rosen 的 Discrete Mathematics and Its Applications 例题密集、覆盖面广，适合当工具书；Graham、Knuth 与 Patashnik 的 Concrete Mathematics 直奔计算相关的组合与递推技术。建议带着工作中的真实问题选章跳读，而不是按目录通读。
学习路径
- 返回 数学基础专题首页
- 第 1 章：命题逻辑与证明
- 第 2 章：集合、关系与函数
- 第 3 章：组合计数
- 第 4 章：图论基础
- 第 5 章：数论初步
- 第 6 章：递归与递推
- 第 7 章：生成函数（进阶）
- 第 8 章：代数结构（进阶）