离散数学
计算机专业 · 本科阶段集合论、数理逻辑、图论与组合数学，计算机科学理论（编译原理、数据结构、算法）的基础。
离散数学是计算机科学理论的数学心脏：集合论与数理逻辑服务形式化与程序正确性，图论与组合数学服务算法与数据结构，代数结构服务密码学与编译原理。它是「从连续世界走向离散世界」的关键课程。
§ 01
数理逻辑
命题逻辑（联结词、真值表、等值演算）与一阶谓词逻辑（量词、辖域）：逻辑是程序正确性证明（霍尔逻辑）、数据库查询语言（SQL 基于关系代数）与知识表示（描述逻辑）的基础。范式（合取/析取范式）通向布尔函数化简与电路设计。
§ 02
集合论与关系
集合运算、笛卡尔积、幂集；二元关系的性质（自反、对称、传递）与闭包，等价关系与偏序关系。关系代数是关系数据库的理论模型：选择、投影、连接对应集合运算；哈斯图可视化偏序结构（如程序模块依赖）。
§ 03
图论
图的概念与表示（邻接矩阵、邻接表）、欧拉路与哈密顿路、树与生成树（Kruskal/Prim 最小生成树算法）、最短路径（Dijkstra）、图的着色与平面图（四色定理）。图论是网络路由、社交网络分析、编译优化（寄存器分配=着色问题）的共同语言。
§ 04
组合数学与代数结构
计数原理（加法/乘法原理）、排列组合、鸽巢原理、容斥原理、递推关系（斐波那契、主定理）与生成函数。代数结构：群（对称性与密码）、环、域（有限域 GF(2^n) 是编码与 AES 的基础）、格与布尔代数（电路化简）。
核心公式速查
鸽巢原理
容斥原理
主定理递推
学习建议与易错点
- 证明技巧三件套：数学归纳法、反证法、构造法——离散数学的证明题九成靠它们。
- 等价关系三性质（自反、对称、传递）要逐条验证，漏掉传递性是常见失分点。
- 递推关系求解先写特征方程 ，再代入初值定系数，套路固定。
- 图论算法（Dijkstra、Prim、Kruskal）建议手推小例子，理解贪心策略为什么成立比背步骤重要。