离散数学复习笔记索引

课程模块

本课程分为四大模块：数理逻辑、集合论、图论、代数系统。

基于高数叔离散数学速成课和我校教学PPT整理

笔记列表

模块一：数理逻辑

模块二：集合论

模块三：图论

模块四：代数系统

各模块重点内容速查

数理逻辑重点

1. 五大联结词：否定¬、合取∧、析取∨、蕴含→、等价↔
2. 蕴含联结词：前件为假时整个命题为真
3. 等值式：16组基本等值式（德摩根律、蕴含等值式等）
4. 主范式：主析取范式（小项析取）、主合取范式（大项合取）
5. 推理规则：假言推理、拒取式、析取三段论等10条规则
6. 证明方法：直接证明法、归谬法、附加前提证明法
7. 量词符号化：全称用蕴含 $\forall x(F(x) \to G(x))$，存在用合取 $\exists x(F(x) \wedge G(x))$
8. 量词否定转移：$\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$，$\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)$
9. 量词分配律：$\forall$ 对 $\wedge$ 分配，$\exists$ 对 $\vee$ 分配
10. 谓词推理规则：UI（全称消去）、EI（存在消去）、UG（全称引入）、EG（存在引入）

集合论重点

1. 集合运算：并、交、差、补、对称差
2. 幂集：$|P(A)| = 2^n$
3. 包含排斥原理：$|A \cup B| = |A| + |B| - |A \cap B|$
4. 关系的五个性质：自反、反自反、对称、反对称、传递
5. 闭包：自反闭包、对称闭包、传递闭包
6. 等价关系：自反+对称+传递，产生等价类和划分
7. 偏序关系：自反+反对称+传递，哈斯图表示

图论重点

1. 握手定理：$\sum d(v_i) = 2m$，奇数度顶点个数为偶数
2. 连通性：无向图连通；有向图分强连通、单向连通、弱连通
3. 邻接矩阵：$A^n$ 表示长度为n的通路数
4. 欧拉图：所有顶点度数为偶数（无向图）
5. 哈密顿图：通过所有顶点一次且仅一次的回路
6. 最短路：Dijkstra标号算法
7. 树的性质：$n = m + 1$，至少两片树叶
8. 根树：入度为0的根结点，出度为0的叶结点
9. 二叉树遍历：先序（根左右）、中序（左根右）、后序（左右根）；先序+中序或中序+后序可唯一确定二叉树
10. 最小生成树：避圈法（Kruskal）、破圈法
11. 最优二元树：Huffman算法
12. 欧拉公式：$v - e + r = 2$（连通平面图）
13. 平面图判定：$e \leq 3v - 6$；库拉托夫斯基定理（不含 $K_5$ 或 $K_{3,3}$ 同胚子图）
14. 四色定理：任何平面图点色数不超过4

代数系统重点

1. 代数系统定义：非空集合 + 若干封闭运算
2. 二元运算性质：封闭、可交换、可结合、可分配、可吸收、等幂
3. 幺元：$e * x = x * e = x$，若存在必唯一
4. 零元：$\theta * x = x * \theta = \theta$，若存在必唯一，幺元 $\neq$ 零元
5. 逆元：$a * b = b * a = e$，结合律下逆元唯一
6. 运算表：通过运算表判断封闭性、交换性、等幂性、幺元、零元、逆元
7. 代数系统层次：广群 $\subseteq$ 半群 $\subseteq$ 独异点 $\subseteq$ 群
8. 群的性质：无零元、消去律、方程有唯一解、运算表每行每列为置换
9. 子群：群的非空子集对运算封闭且本身构成群
10. 阿贝尔群：可交换的群，阶数1/2/3/4的群都是阿贝尔群
11. 循环群：由生成元生成所有元素的群，循环群 $\subseteq$ 阿贝尔群
12. 同态：$f(a \star b) = f(a) \triangle f(b)$，保持半群/独异点/群结构
13. 同构：双射的同态，同构的代数系统本质相同，同构是等价关系

常考题型

复习建议

1. 数理逻辑：熟记16组等值式和10条推理规则，多做形式证明练习
2. 集合论：掌握关系的五个性质判断，会画哈斯图
3. 图论：理解握手定理，会用Dijkstra算法求最短路，掌握Huffman算法，掌握欧拉公式和平面图判定，会二叉树遍历及由遍历结果重建二叉树
4. 代数系统：掌握幺元、零元、逆元的定义和判断，会通过运算表分析性质

备注

• 所有笔记均基于紫云老师的课程字幕整理
• 数学公式使用LaTeX格式，可正常渲染