《离散数学》
参考资料
引入
离散数学（Discrete Mathematics）研究 不连续、可数 的数学对象——逻辑、集合、关系、图、代数结构。与处理「连续变化」的微积分相对，它处理的是一个个分立的、可以逐一枚举的东西，而这恰恰是计算机的世界：内存是一格格的，数据是一条条的，程序是一步步的。
所以离散数学被称为 计算机科学的数学语言，几乎每个分支都能在这里找到根：
- 命题逻辑 → 电路设计 / 程序的形式验证。
- 集合 / 关系 → 数据库理论、类型系统。
- 图论 → 网络、算法、数据结构。
- 代数结构 → 编码理论、密码学、纠错码。
各章之间并不孤立——逻辑、集合、布尔代数其实是同一个结构的不同外衣，这种「殊途同归」正是这门课最值得玩味的地方。
章节大纲
- 数理逻辑：命题与谓词逻辑、联结词、真值表、范式（DNF / CNF / 主范式）、推理与证明方法、量词与前束范式。
- 集合与关系：集合运算与恒等式、幂集、笛卡尔积、关系的性质与表示、闭包、等价关系与划分、偏序与哈斯图、函数、基数与可数性。
- 图论：度与握手定理、连通性、矩阵表示、最短路、树与生成树、欧拉图与哈密顿图、平面图与欧拉公式、图的着色。
- 代数结构：二元运算、半群与独异点、群（子群、循环群、陪集与拉格朗日定理、同态同构）、环与域、格与布尔代数。
学习建议
- 重视定义。 离散数学的「难」不在计算，而在概念之间的细微差别（自反 vs 反自反、对称 vs 反对称、极大元 vs 最大元）。一字之差往往是考点。
- 多画图、多列表。 关系图、哈斯图、真值表、关系矩阵都是把抽象具象化的利器，画出来就清楚了。
- 跟着算例动手。 各章都配了带步骤的算例（求主范式、Warshall、Dijkstra、Kruskal、置换分解、群判定等），照着算一遍比只读结论扎实得多。
- 关注同构。 不同领域的结构（命题逻辑 ↔ 集合代数 ↔ 布尔代数；幂集 ↔ 整除偏序）背后往往是同一种代数模式，看穿这一点能让知识量减半。
- 结合计算机背景。 几乎每个概念都有对应的计算机应用，带着「这东西在程序里是什么」去学，会比纯抽象记忆扎实得多。