离散数学：从集合到图论的形式化思维全景
离散数学并非一堆孤立概念的堆砌，而是以集合为语言、逻辑为推理、关系与函数为结构、图论为建模的一整套离散世界认知体系。它既是计算机科学的理论地基，也是培养严格抽象思维的训练场。
一、基石：集合论与数学语言
一切从”集合”开始。集合是离散数学里最底层的容器，后续所有结构（关系、函数、图、逻辑域）都建立在它之上。
- 集合的初见：元素确定性、互异性、无序性；特殊集合（空集、全集、幂集）。
- 集合间关系与运算：包含、相等；并、交、差、补、对称差；运算定律（交换律、结合律、分配律、德·摩根律）。
- 无限集合的层次：可数集（如自然数集）与不可数集（如实数集）的基数区分，打开”无穷也有大小”的视野。
集合论的价值不在背定义，而在提供一套统一记号——后面谈”关系”是笛卡尔积的子集，谈”函数”是特殊的关系，谈”图”是点集与边集的组合，全都能回归到集合。
二、推理机器：命题逻辑与谓词逻辑
逻辑部分解决一个问题：怎样把自然语言里的真假判断，变成可计算、可证明的符号系统。
命题逻辑（语法与语义）
- 命题与联结词：非、合取、析取、蕴涵、等价。
- 符号化与真值表：把”如果下雨则地湿”翻译成 p→q，用真值表判定永真/矛盾/可满足。
- 等价演算与范式：基本等价式、合取范式（CNF）、析取范式（DNF）、主范式。
- 推理理论：演绎法、蕴涵式、自然演绎规则——程序正确性证明的雏形。
谓词逻辑（带量词的升级版）
命题逻辑管不了”所有””存在”这类量化陈述，谓词逻辑补上这块：
- 个体、谓词、量词（∀、∃）、自由变元与约束变元。
- 公式解释与等价、前束范式。
- 谓词综合推理：从”每人都有父亲”推”存在某人是所有人的父亲”为何不成立。
三、结构之间：二元关系与函数
关系是”集合元素之间的联线”，函数是”一一对应的特殊关系”。这一层把前面集合与逻辑的能力用起来。
- 序偶与笛卡尔积：关系被定义为 A×B 的子集。
- 关系表示与运算：矩阵、关系图；复合、逆、闭包（自反/对称/传递闭包）。
- 关系的性质：自反、对称、反对称、传递——数据库完整性约束的理论源头。
- 特殊关系：等价关系（划分集合）、偏序关系（哈斯图、极大极小元）。
- 函数：单射、满射、双射，复合与反函数，为后续代数与算法分析铺垫。
四、看得见的结构：图论、树与特殊图
图论是离散数学里最”像工程”的部分，直接对应网络、路径、依赖、调度等问题。
图论基础
- 图的定义：顶点、边、有向/无向、度、握手定理。
- 连通性：通路、回路、连通分量、可达性。
树
- 无向树：无环连通，边数 = 顶点数 − 1。
- 有向树与根树：层次、遍历、最优树（哈夫曼编码基础）。
特殊图与应用判定
- 欧拉图：一笔画问题，边遍历一次。
- 哈密顿图：顶点遍历一次，存在性判定远难于欧拉图。
- 偶图（二分图）：匹配、资源分配建模。
- 平面图：面、欧拉公式、四色问题直觉。
总结：三条主线与一句金句
- 集合是字母，逻辑是语法，关系与函数是词法，图论是篇章——离散数学教的是如何用一套严格语言描述离散世界。
- 从”静态容器”（集合）到”动态推理”（逻辑），再到”结构关联”（关系/函数）与”可视建模”（图），难度递增，但每一层都依赖前一层。
- 它不直接教你写代码，但决定了你能不能写对算法、证对系统、想清依赖。
金句：离散数学的尽头不是公式，而是把模糊的世界拆成”元素—关系—结构”三重清晰的能力。