离散数学专题
这一页介绍八章各自涉及的问题、建议的学习顺序和章节间的依赖,帮助读者根据需要选择起点。
离散数学研究集合、逻辑、图和计数等离散结构,提供描述对象、分析关系和证明命题的工具。
学习路径:顺序与依赖
八章按概念之间的依赖关系安排学习顺序。
第 1 章 命题逻辑与证明 必须先读。 后面每一章的定理都要用蕴含、量词和归纳法来表达;在读懂这一章之前,“证明一个命题”这件事本身没有严格含义。逻辑先行不是传统,是依赖关系决定的。
第 2 章 集合、关系与函数 紧随其后。 它是描述一切对象的语法:图是顶点集上的二元关系,等价类是聚类的数学定义,函数概念贯穿组合计数与数论。没有它,后面各章研究的对象都无法精确陈述。
第 3 章 组合计数 排在第 4 章之前,因为图论里”有多少条路径、多少棵生成树”这类问题要直接调用计数的工具箱;反过来,计数几乎不依赖图论,先读它不会卡住。
第 4 章 图论基础 与 GeoAI、图学习联系紧密:它用逻辑证明树的性质,用关系描述图的连接,并涉及路径与树的计数。前四章为学习 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 章:代数结构(进阶)