离散数学复习

离散数学期末复习大纲

发表于 2026/01/10 更新于 2026/01/10

作者 Metahumanz

96 分钟阅读

离散数学复习

详细

好的，没问题！我们就把你当作一张白纸，从零开始，用最通俗的语言配合生动的例子，把第一章的内容彻底拆解清楚。

这一章是离散数学的基石，分为集合论（基础概念）和证明方法（逻辑思维工具）两大部分。

第一部分：集合及其运算

1. 基本概念：什么是集合？

想象一个“大袋子”，里面装了一些互不相同的东西，这个袋子就是一个集合（Set）。袋子里的每一个东西，叫做元素（Element）。

1. 元素与集合的关系

属于 ($\in$)：如果数字 $1$ 在集合 $A$ 里，我们写 $1 \in A$（读作：1 属于 A）。
不属于 ($\notin$)：如果数字 $5$ 不在集合 $A$ 里，我们写 $5 \notin A$（读作：5 不属于 A）。
- 例子：设集合 $A = {1, 2, 3}$，那么 $2 \in A$，但 $4 \notin A$。

2. 子集与真子集

子集 ($\subseteq$)：如果集合 $B$ 里的每一个元素都在集合 $A$ 里，那 $B$ 就是 $A$ 的子集。
- 注意：你自己也是你自己的子集（$A \subseteq A$ 是成立的）。
真子集 ($\subset$)：如果 $B$ 是 $A$ 的子集，而且 $A$ 里还有 $B$ 没有的东西（即 $B$ 比 $A$ 小），那 $B$ 就是真子集。
- 例子：$A={1, 2, 3}$。
- ${1, 2} \subset A$ （是真子集，也是子集）。
- ${1, 2, 3} \subseteq A$ （是子集，但不是真子集）。

3. 空集 ($\emptyset$)

就是一个空袋子，里面什么都没有。
重要性质：空集是任何集合的子集。（$\emptyset \subseteq \text{任何集合}$）。

4. 幂集 ($P(A)$) —— 这是一个难点！

定义：把集合 $A$ 的所有子集（包括空集和它自己）拿出来，作为一个新集合的元素，这个新集合就是幂集。
口诀：子集的大集合。
计算公式：如果 $A$ 有 $n$ 个元素，那么 $P(A)$ 就有 $2^n$ 个元素。
- 详细例子：设 $A = {a, b}$ （这里 $n=2$）。 $A$ 的子集有：
  1. $\emptyset$ (空集)
  2. ${a}$
  3. ${b}$
  4. ${a, b}$ (它自己) 所以，幂集 $P(A) = { \emptyset, {a}, {b}, {a, b} }$。元素个数是 $2^2 = 4$ 个。

2. 集合的运算：怎么玩转这些袋子？

假设全集 $U = {1, 2, 3, 4, 5}$， $A = {1, 2, 3}$， $B = {3, 4, 5}$。

1. 并集 ($\cup$) —— “或者” (OR)

定义：把两个袋子里的东西倒在一起（重复的只算一个）。
例子：$A \cup B = {1, 2, 3, 4, 5}$。

2. 交集 ($\cap$) —— “并且” (AND)

定义：找出两个袋子里都有的东西。
例子：$A \cap B = {3}$ （只有3是公共的）。

3. 相对补集 ($-$) —— “差集”

定义：$A - B$ 意思是，在 $A$ 里面，把属于 $B$ 的东西踢出去（只属于A，不属于B）。
例子：$A - B = {1, 2}$ （把3踢掉了）。注意 $B - A = {4, 5}$。

4. 绝对补集 ($\sim$ 或 $A^c$) —— “非” (NOT)

定义：全集 $U$ 里面，除了 $A$ 以外的所有东西。
例子：$\sim A = {4, 5}$。

5. 对称差 ($\oplus$) —— “异或” (XOR)

定义：属于 $A$ 或属于 $B$，但不是两者的公共部分。也就是“非公共部分”。
公式：$A \oplus B = (A - B) \cup (B - A)$。
例子： $A - B = {1, 2}$ $B - A = {4, 5}$ $A \oplus B = {1, 2, 4, 5}$ （把公共的3去掉了）。

3. 重要的集合恒等式 (用于化简)

这部分就像代数里的 $a(b+c) = ab + ac$，是集合运算的规则。

1. 德摩根律 (De Morgan’s Laws) —— ⭐️ 必考

直观理解：“既不A也不B” 等于 “非(A或B)”。
公式：
- $\sim (A \cup B) = \sim A \cap \sim B$ （并集的补 = 补集的交）
- $\sim (A \cap B) = \sim A \cup \sim B$ （交集的补 = 补集的并）
- 记忆技巧：把括号拆开，$\cup$ 变 $\cap$，$\cap$ 变 $\cup$。

2. 吸收律

公式：$A \cup (A \cap B) = A$
直观理解：$A \cap B$ 本来就是 $A$ 的一部分（在A里面），你把它和 $A$ 取并集，结果当然还是 $A$。小的被大的“吸收”了。

第二部分：证明方法 (⭐️ 老师划重点)

这部分是考试的大题重灾区，一定要理解逻辑思路。

1. 直接证明法

逻辑：也就是“顺藤摸瓜”。已知条件 $P$ 成立，通过定义、公理，一步步推导出结论 $Q$。
例子：证明“若 $n$ 是奇数，则 $n^2$ 也是奇数”。
- 设 $n = 2k+1$ (奇数定义)。
- $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$。
- 结果符合 $2m+1$ 的形式，所以 $n^2$ 是奇数。证毕。

2. 反证法 (归谬法)

逻辑：也就是“抬杠”。
1. 先假设结论是错的。
2. 以此为基础进行推导，结果发现推出了一个荒谬的结论（比如 $1=0$，或者与已知条件矛盾）。
3. 既然假设结论错误会导致矛盾，说明结论必须是对的。
典型场景：证明某物“不存在”、证明 $\sqrt{2}$ 是无理数。

3. 数学归纳法 (重点中的重点)

这就像推倒多米诺骨牌。

第一数学归纳法

适用：证明一个与自然数 $n$ 有关的命题 $P(n)$ 对所有 $n$ 都成立。
步骤：
1. 归纳基础：证明第一块骨牌会倒（例如证明 $n=1$ 时命题成立）。
2. 归纳假设与步骤：假设第 $k$ 块骨牌倒了（$P(k)$ 为真），证明第 $k+1$ 块也会倒（推导出 $P(k+1)$ 为真）。
3. 结论：所有骨牌都会倒。

第二数学归纳法 (强归纳)

区别：推倒第 $k+1$ 块骨牌时，不仅需要第 $k$ 块的力量，需要前面所有 ($1$ 到 $k$) 骨牌倒下的力量。
步骤：
1. 基础：证明 $P(n_0)$ 成立。
2. 步骤：假设对于所有 $n \le k$， $P(n)$ 都成立（假设前面的一堆都倒了），以此推导出 $P(k+1)$ 成立。
应用场景：当推导 $k+1$ 时，不仅依赖 $k$，可能依赖 $k/2$ 或 $k-1$ 等更前面的项（如素数分解定理）。

4. 构造性证明

逻辑：也就是“眼见为实”。
适用：证明存在性命题（证明存在某个 $x$ 满足条件）。
方法：我不跟你讲空话，我直接找出来或者造出来一个满足条件的例子给你看。
例子：证明“存在两个无理数 $x, y$，使得 $x^y$ 是有理数”。我直接构造 $\sqrt{2}^{\sqrt{2}}$ 这种例子来讨论。

复习小结（考试必看）

幂集元素的个数是 $2^n$，别忘了空集 $\emptyset$ 是幂集的元素。
对称差 $\oplus$ 就是“两个集合不重叠的部分”。
反证法起手式：“假设结论不成立…”。
数学归纳法写题时，一定要把“归纳基础”和“归纳假设”这两步写清楚，格式分不能丢。

现在是不是清晰多了？可以尝试对着这个思路去看一遍PPT上的例题！

好的！第二章 命题逻辑 是整个离散数学的“语法基础”，这一章学不好，后面看公式就像看天书。

我们将这一章拆解为三个部分：词汇（基本概念）、语法变形（等值演算与范式）、写作文（推理）。

第一部分：2.1 基本概念（词汇篇）

1. 什么是命题？

简单说，命题就是一句能判断对错的话（陈述句）。

是命题的例子：
- “北京是中国的首都。”（真命题，值为 True/1）
- “1 + 1 = 3。”（假命题，值为 False/0）
不是命题的例子：
- “快跑！”（祈使句，没法说对错）
- “你吃饭了吗？”（疑问句）
- “$x + 1 = 2$”（除非你告诉我 $x$ 是几，否则不知道对错）

2. 联结词：把简单命题连成复杂命题的“胶水”

假设 $p$ 代表“今天下雨”，$q$ 代表“我带伞”。

否定 ($\neg$, Not)：唱反调。
- $\neg p$：今天不下雨。
- 规则：真变假，假变真。
合取 ($\wedge$, And)：且，两个都要满足。
- $p \wedge q$：今天下雨且我带伞。
- 规则：只有当 $p, q$ 全为真时，结果才为真（1）。有一假则假。
析取 ($\vee$, Or)：或，至少满足一个。
- $p \vee q$：今天下雨或我带伞。
- 规则：只要有一个为真，结果就是真。只有当 $p, q$ 全为假时，结果才为假。
蕴涵 ($\to$, Implication) —— 🚨 最容易晕的地方！
- $p \to q$：如果今天下雨，那么我就带伞。
- 规则（承诺原则）：
  - 把 $p \to q$ 看作一个承诺。$p$ 是条件，$q$ 是结果。
  - 情况1：下雨了($p$真)，我也带伞了($q$真)。承诺兑现，结果为真。
  - 情况2：下雨了($p$真)，我没带伞($q$假)。我食言了，承诺破裂，结果为假。
  - 情况3（重点）：没下雨($p$假)。不管我带没带伞，我都没有违背“如果下雨就…”的承诺。所以，只要条件 $p$ 为假，整个命题直接为真（善意推断）。
- 口诀：只有“真推假”才是假，其他情况全是真。
等价 ($\leftrightarrow$, Iff)：当且仅当。
- $p \leftrightarrow q$：相当于判断 $p$ 和 $q$ 的真假是否一致。
- 规则：$p, q$ 相同为真，不同为假。

3. 公式分类（⭐ 老师划重点）

这就好比给一个人定性：是好人、坏人，还是普通人。我们通过列真值表（穷举所有可能）来判断。

永真式 (重言式)：无论 $p, q$ 取什么值，结果永远是 1。
- 例子：$p \vee \neg p$ （天要么下雨，要么不下雨，这句废话永远是对的）。
永假式 (矛盾式)：无论 $p, q$ 取什么值，结果永远是 0。
- 例子：$p \wedge \neg p$ （天下雨且天没下雨，这是不可能的）。
可满足式：至少有一种情况结果是 1。
- 注意：永真式也是可满足式的一种（因为它全是1，当然满足“至少有一个1”）。
- 通常我们说的“可满足式”大多指那些“有时候真，有时候假”的公式。

第二部分：2.2 等值演算与范式（语法变形篇）

这一部分要求你像做代数题化简 $(a+b)^2$ 一样，对逻辑公式进行变形。

1. 重要的基本等值式

你需要背下来几个核心的，用于化简：

双重否定：$\neg \neg p \Leftrightarrow p$
德摩根律 (De Morgan)：
- $\neg (A \wedge B) \Leftrightarrow \neg A \vee \neg B$ （非(A且B) = 非A 或非B）
- $\neg (A \vee B) \Leftrightarrow \neg A \wedge \neg B$
- 记忆：负号进括号，符号要变号。
蕴涵等值式 (⭐ 必考)：
- $A \to B \Leftrightarrow \neg A \vee B$
- 解释：要把箭头去掉，变成“或”，前面的要加“非”。这是化简范式的核心工具！

2. 范式 (Normal Forms) —— 也就是“标准格式”

逻辑公式可以写得乱七八糟，为了统一标准，我们规定了两种格式：

析取范式 (DNF)：“积之和”
- 样子：$(A \wedge B) \vee (C \wedge \neg D) \vee \dots$
- 结构：里面是小团伙（合取/且），外面用“或”连起来。
合取范式 (CNF)：“和之积”
- 样子：$(A \vee B) \wedge (C \vee \neg D) \wedge \dots$
- 结构：里面是小团伙（析取/或），外面用“且”连起来。

3. 主析取与主合取范式 (⭐ 老师划重点)

“主”意味着唯一性。任何公式的主范式都是独一无二的，像指纹一样。

关键概念：极小项 ($m$) 与极大项 ($M$) 假设有两个变量 $P, Q$。

极小项 ($m_i$) —— 对应“主析取范式”
- 定义：包含所有变量的合取（$\wedge$）项。
- 编码规则：变量本身对应 1，$\neg$变量对应 0。
- 例子：
  - $P \wedge Q \rightarrow$ 编码 11 $\rightarrow m_3$
  - $P \wedge \neg Q \rightarrow$ 编码 10 $\rightarrow m_2$
  - $\neg P \wedge Q \rightarrow$ 编码 01 $\rightarrow m_1$
  - $\neg P \wedge \neg Q \rightarrow$ 编码 00 $\rightarrow m_0$
- 怎么求主析取范式？
  1. 列真值表。
  2. 找到结果为 1 (真) 的那些行。
  3. 把这些行对应的 极小项 ($m$) 用 $\vee$ 连起来。
极大项 ($M_i$) —— 对应“主合取范式”
- 定义：包含所有变量的析取（$\vee$）项。
- 编码规则 (⚠️反直觉，要死记)：变量本身对应 0，$\neg$变量对应 1。
- 例子：
  - $P \vee Q \rightarrow$ 编码 00 $\rightarrow M_0$
  - $P \vee \neg Q \rightarrow$ 编码 01 $\rightarrow M_1$
  - $\neg P \vee Q \rightarrow$ 编码 10 $\rightarrow M_2$
  - $\neg P \vee \neg Q \rightarrow$ 编码 11 $\rightarrow M_3$
- 怎么求主合取范式？
  1. 列真值表。
  2. 找到结果为 0 (假) 的那些行。
  3. 把这些行对应的 极大项 ($M$) 用 $\wedge$ 连起来。

举个栗子 (考试计算题)：设公式 $G = \neg P \vee Q$。

列真值表： | P | Q | $\neg P$ | $G = \neg P \vee Q$ | |—|—|—|—| | 0 | 0 | 1 | 1 (对应 $m_0$) | | 0 | 1 | 1 | 1 (对应 $m_1$) | | 1 | 0 | 0 | 0 (对应 $M_2$) | | 1 | 1 | 0 | 1 (对应 $m_3$) |
求主析取范式：看结果为 1 的行：00, 01, 11。对应极小项：$m_0, m_1, m_3$。结果：$m_0 \vee m_1 \vee m_3$ (或者写成 $\sum(0, 1, 3)$)。
求主合取范式：看结果为 0 的行：10。对应极大项：$M_2$ （注意：P=1对应$\neg P$, Q=0对应$Q$，所以是 $\neg P \vee Q$）。结果：$M_2$ (或者写成 $\prod(2)$)。

第三部分：2.4 推理（写作文篇）

这里主要考察：给你一堆前提，让你证明结论是对的。

1. 推理的有效性

如果“前提1 $\wedge$ 前提2 $\wedge \dots \to$ 结论”是一个重言式（永远为真），那么推理就是有效的。

2. 核心推理规则（背下来，像公式一样用）

假言推理 (P规则) —— 最常用！
- 公式：$(P \to Q) \wedge P \Rightarrow Q$
- 人话：如果“下雨地湿”成立，且“下雨了”成立，那么“地湿”一定成立。
拒取式 (T规则)
- 公式：$(P \to Q) \wedge \neg Q \Rightarrow \neg P$
- 人话：如果“下雨地湿”成立，且“地没湿”，那么“没下雨”一定成立。
析取三段论
- 公式：$(P \vee Q) \wedge \neg P \Rightarrow Q$
- 人话：要是“我喝茶或喝咖啡”，但我“没喝茶”，那我肯定“喝咖啡”了。

复习总结（考前看这个）

箭头转化：看到 $A \to B$，脑子里立刻浮现 $\neg A \vee B$。
真值表是万能的：如果不会化简，列真值表可以解决判断类型、求范式等大部分问题。
分清大小写：
- 求主析取 ($\vee$) $\rightarrow$ 找真值 1 $\rightarrow$ 用小写 $m$ (极小项)。
- 求主合取 ($\wedge$) $\rightarrow$ 找真值 0 $\rightarrow$ 用大写 $M$ (极大项)。
极大项编码陷阱：极大项中，变量原身代表0，否定代表1。千万别弄反了！

好，我们继续攻克第3章：一阶逻辑（谓词逻辑）。

如果说第2章的命题逻辑是把一句话看作一个整体（原子），那么第3章的一阶逻辑就是把这个原子“切开”，研究句子内部的主语、谓语和数量关系。

这一章是离散数学中形式化表达的核心，也是考试中考查“规范化能力”（求前束范式）的重点章节。

第一部分：3.1 基本概念（拆解句子）

在命题逻辑里，“苏格拉底是人”只是一个代号 $p$。在一阶逻辑里，我们要把它拆分成：对象（苏格拉底） + 性质（是人）。

1. 词汇表

个体词（描述对象）
- 个体常项：具体的、确定的对象。通常用小写字母 $a, b, c$ 表示。
  - 例子：$a$ = 苏格拉底，$b$ = 那个苹果。
- 个体变项：泛指的、不确定的对象（占位符）。通常用小写字母 $x, y, z$ 表示。
  - 例子：$x$ = 某个人，$y$ = 某个物体。
谓词（描述性质或关系）
- 用来刻画个体性质的符号，通常用大写字母 $F, G, P$ 表示。
- 一元谓词：描述性质。
  - 例子：设 $F(x)$ 表示 “$x$ 是人”。那么 $F(a)$ 就表示“苏格拉底是人”。
- 多元谓词：描述关系。
  - 例子：设 $L(x, y)$ 表示 “$x$ 喜欢 $y$”。那么 $L(我, 你)$ 表示“我喜欢你”。
量词（描述数量）—— 核心！
- 全称量词 ($\forall$, For All)：表示“所有的”、“任意一个”、“一切”。
  - $\forall x F(x)$：对于所有的 $x$，$x$ 都是人（所有人都是人）。
- 存在量词 ($\exists$, Exists)：表示“存在一个”、“至少有一个”、“有的”。
  - $\exists x F(x)$：存在一个 $x$，$x$ 是人（有人是人）。

2. 语法结构：辖域与变元

这部分像编程里的“变量作用域”。

1. 辖域 (Scope)

定义：量词后面紧跟着的括号部分，就是它能管辖的范围。
例子：在公式 $\forall x (P(x) \to Q(y))$ 中，$\forall x$ 的辖域是 $(P(x) \to Q(y))$。

2. 约束变元 vs 自由变元

约束变元：在量词辖域内，且被量词指名的变量。它被“抓”住了。
自由变元：不在辖域内，或者虽然在辖域内但没被量词指名。它是“野生”的。
举个栗子： $\forall x ( P(x) \to Q(y) )$
- $x$：前面有 $\forall x$ 管着，所以括号里的 $x$ 是约束变元。
- $y$：前面没有 $\forall y$ 或 $\exists y$ 管它，所以 $y$ 是自由变元。

考试注意：如果一个公式里没有自由变元（所有变量都被管住了），它就是一个闭式（命题），可以直接判断真假。

第二部分：3.2 等值演算（变形工具）

我们要学会怎么把量词搬来搬去，同时保持句子意思不变。

1. 量词否定等值式（⭐ 必背）

这是把否定号 $\neg$ 塞进量词里面的规则，类似于德摩根律。

规则：$\neg$ 越过量词，量词要翻转（$\forall$ 变 $\exists$，$\exists$ 变 $\forall$），$\neg$ 贴到后面的谓词上。
- $\neg \forall x P(x) \Leftrightarrow \exists x \neg P(x)$
  - 人话：“并不是所有人都会飞” = “存在一个人不会飞”。
- $\neg \exists x P(x) \Leftrightarrow \forall x \neg P(x)$
  - 人话：“不存在吃不胖的人” = “所有人都吃得胖”。

2. 量词辖域的收缩与扩张

这是为了把量词提出来的准备工作。假设 $Q$ 是一个不包含变量 $x$ 的公式（或者 $x$ 在 $Q$ 里已经是被约束的）。

规则：如果 $Q$ 里没有 $x$ 捣乱，量词可以直接跨过 $Q$ 提出来。
- $(\forall x P(x)) \vee Q \Leftrightarrow \forall x (P(x) \vee Q)$
- $(\exists x P(x)) \wedge Q \Leftrightarrow \exists x (P(x) \wedge Q)$
注意（大坑）：如果 $Q$ 里面也有 $x$，那就不能直接提，必须先改名（下面会讲）。

第三部分：前束范式（⭐ 考试大题核心）

这是本章最可能考大题的地方！

1. 什么是前束范式？

样子：所有的量词（$\forall, \exists$）都排排坐，放在最前面，后面跟着一个不含量词的公式。
结构：$Q_1 x_1 Q_2 x_2 \dots Q_k x_k ( \text{不含量词的复杂式子} )$。

2. 怎么求前束范式？（四步走法）

请务必死记这个流程，考试按步骤给分。

第一步：消去蕴涵词 ($\to$) 和等价词 ($\leftrightarrow$)

利用公式 $A \to B \Leftrightarrow \neg A \vee B$。
先把箭头全部变成 $\neg$ 和 $\vee$。

第二步：否定号 ($\neg$) 内移

利用量词否定等值式和德摩根律，把 $\neg$ 一直往里推，直到它紧贴着谓词（比如 $\neg P(x)$），不能停在量词前面。
- $\neg \forall x P(x) \Rightarrow \exists x \neg P(x)$
- $\neg (A \vee B) \Rightarrow \neg A \wedge \neg B$

第三步：变量换名（⭐ 关键步骤，最容易错！）

原则：如果两个量词用了同一个字母（比如前面是 $\forall x$，后面是 $\exists x$），为了避免打架，必须把其中一个改成别的字母（比如 $y$）。
例子：$\forall x P(x) \vee \exists x Q(x)$
- 这里两个 $x$ 容易混淆。
- 改为：$\forall x P(x) \vee \exists y Q(y)$。

第四步：量词外提

利用辖域扩张规则，把所有量词提到最左边。
注意：通常量词提取的顺序不影响最终真值，但保持原有的相对顺序比较安全。

实战演练：求公式的前束范式

题目：化简 $G = \neg (\exists x P(x) \to \forall y Q(y))$

解题步骤：

第一步：消去 $\to$
- 记得 $A \to B \Leftrightarrow \neg A \vee B$。
- $G \Leftrightarrow \neg (\neg \exists x P(x) \vee \forall y Q(y))$
第二步：否定号内移（德摩根律）
- $\neg (A \vee B) \Leftrightarrow \neg A \wedge \neg B$。
- $G \Leftrightarrow \neg (\neg \exists x P(x)) \wedge \neg (\forall y Q(y))$
- 双重否定抵消：$\neg \neg \exists x P(x) \Leftrightarrow \exists x P(x)$。
- 量词否定：$\neg \forall y Q(y) \Leftrightarrow \exists y \neg Q(y)$。
- 现在式子变成了：$\exists x P(x) \wedge \exists y \neg Q(y)$。
第三步：变量换名
- 前半部分用的是 $x$，后半部分用的是 $y$，没有冲突，不需要换名。
- （如果是 $\exists x P(x) \wedge \exists x \neg Q(x)$，就必须把后面改成 $y$）。
第四步：量词外提
- 把 $\exists x$ 和 $\exists y$ 提到最前面。
- $G \Leftrightarrow \exists x \exists y (P(x) \wedge \neg Q(y))$。

最终答案：$\exists x \exists y (P(x) \wedge \neg Q(y))$。这就是前束范式。

复习小结（考前必看）

全称 $\forall$ 对应“且”，存在 $\exists$ 对应“或”：虽然不是绝对的，但 $\forall x (P(x) \to Q(x))$ 和 $\exists x (P(x) \wedge Q(x))$ 是最常见的搭配。
否定号必须沉底：在前束范式中，否定号 $\neg$ 只能出现在谓词 $P(x), Q(y)$ 的前面，绝对不能出现在量词 $\forall, \exists$ 的前面。
一定要换名：提取量词前，先检查有没有重名的变量。如果有，先把其中一个改成 $z$ 或 $w$，否则后面提取时逻辑会乱。

这就是第三章的核心！只要掌握了前束范式的求法，这一章的一半分数就到手了。

这一章是离散数学最核心、考试分值最高、概念最密集的一章。请务必打起十二分精神！特别是关系的5个性质和2种特殊关系（等价、偏序），大题基本上跑不掉。

我们通过“人际关系”和“地图”的例子来通俗讲解。

4.1 关系的定义与表示（基础词汇）

1. 什么是笛卡尔积（$A \times B$）？

通俗理解：就是“配对”。集合 $A$ 是男生，集合 $B$ 是女生。$A \times B$ 就是把所有可能的“一男一女”配对组合列出来。
数学定义：$A \times B = {<x, y> x \in A, y \in B}$。
- 结果是一个集合，里面的元素是有序对 $<x, y>$。

2. 什么是二元关系（$R$）？

通俗理解：在上面的所有配对中，不是每一对都“有关系”（比如谈恋爱）。我们挑出那些“真正谈恋爱”的配对，组成一个新的集合，这就是关系。
定义：$R$ 是 $A \times B$ 的子集。
- 如果 $<x, y> \in R$，记作 $xRy$（$x$ 和 $y$ 有关系）。
- 如果 $<x, y> \notin R$，说明没关系。

3. 怎么表示关系？（三种方式）

假设 $A = {1, 2, 3}$，关系 $R = {<1, 1>, <1, 2>, <2, 3>}$。

集合法：直接列出来，如上所示。
关系矩阵（$M_R$）：用 0 和 1 的表格表示。
- 行代表 $x$，列代表 $y$。
- 有关系填 1，没关系填 0。
- 上面的例子矩阵： $\begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$ (第1行第1列是1，代表 <1,1>；第1行第2列是1，代表 <1,2>)
关系图：画点和箭头。
- 有 $1, 2, 3$ 三个点。
- $<1, 2>$ 就在 1 和 2 之间画个箭头指向 2。
- $<1, 1>$ 就是在 1 上画个圈（自环）。

4.2 关系运算（工具箱）

域：
- 定义域 (dom)：所有出发的点（箭头的尾巴）。
- 值域 (ran)：所有到达的点（箭头的头）。
逆 ($R^{-1}$)：
- 操作：把箭头反过来。$<x, y>$ 变成 $<y, x>$。
- 矩阵：矩阵的转置（行列互换）。
合成 ($R \circ S$) —— 难点！
- 逻辑：搭桥过河。
- 如果 $x$ 能到 $y$（在 $R$ 中），$y$ 能到 $z$（在 $S$ 中），那么 $x$ 就能直接到 $z$。中间的 $y$ 就是桥。
- 注意顺序：通常写作 $R \circ S$（右复合）或 $S \circ R$（左复合），考试时请以教材定义的符号方向为准（通常是从右往左读，类似复合函数 $f(g(x))$）。
幂运算 ($R^n$)：
- $R^2$：走 2步能到达的关系。
- $R^n$：走 n步能到达的关系。
- 应用：用于判断连通性和传递性。

4.3 关系的性质（⭐ 考试必考重灾区）

给你一个关系（通常是矩阵），问你它满足哪些性质？怎么改造成满足性质？

1. 自反性 (Reflexive)

人话：每个人都爱自己。
定义：$\forall x \in A, <x, x> \in R$。
矩阵特征：主对角线全为 1。
图特征：每个点都有自环（自己指自己的圈）。

2. 反自反性 (Irreflexive)

人话：没人爱自己（绝对不自恋）。
定义：$\forall x \in A, <x, x> \notin R$。
矩阵特征：主对角线全为 0。
图特征：每个点都没有自环。
注意：如果对角线有0有1，那既不是自反也不是反自反。

3. 对称性 (Symmetric)

人话：双向奔赴。我爱你，你必须也爱我。
定义：如果 $<x, y> \in R$，那么必须 $<y, x> \in R$。
矩阵特征：对称矩阵（沿对角线折叠重合）。$M_{ij} = M_{ji}$。
图特征：如果有箭头从 A 指向 B，必须也有箭头从 B 指回 A（或者直接画无向边）。

4. 反对称性 (Antisymmetric) —— 最容易错！

人话：单相思或等级制。如果我爱你，你绝对不能爱我（除非咱俩是一个人）。
定义：如果 $<x, y> \in R$ 且 $<y, x> \in R$，那么必须 $x=y$。
矩阵特征：对称位置（$M_{ij}$ 和 $M_{ji}$）不能同时为 1（除非在对角线上）。
- 可以是：一个1一个0，或者两个都是0。
图特征：两个不同点之间，最多只能有一条单向边，不能有双向箭头。

5. 传递性 (Transitive)

人话：爱屋及乌 / 传染病。如果 A 传给 B，B 传给 C，那么 A 必须也能直接传给 C。
定义：$<x, y> \in R \wedge <y, z> \in R \Rightarrow <x, z> \in R$。
判定方法：$R^2 \subseteq R$（走两步能到的地方，一步也能到）。

闭包 (Closure) —— “补全计划”

如果一个关系不满足某个性质，我们加最少的边让它满足。

自反闭包 ($r(R)$)：
- 做法：把主对角线全变成 1。
- 公式：$R \cup I_A$ （$I_A$ 是恒等关系，即所有 $<x,x>$）。
对称闭包 ($s(R)$)：
- 做法：把矩阵沿对角线对称补全（你有单向，我就补回向）。
- 公式：$R \cup R^{-1}$。
传递闭包 ($t(R)$)：
- 做法：如果 A->B->C，就补上 A->C。一直补到不能补为止。
- Warshall 算法（计算题重点）：
  - 通过矩阵运算求传递闭包。
  - 核心思想：遍历中间点 $k$。如果 $i$ 能到 $k$，且 $k$ 能到 $j$，则标记 $i$ 能到 $j$。
  - 公式：$M_k[i, j] = M_{k-1}[i, j] \vee (M_{k-1}[i, k] \wedge M_{k-1}[k, j])$。

4.4 特殊关系（⭐ 大题核心）

1. 等价关系 (Equivalence Relation)

口诀：自反 + 对称 + 传递。
意义：分类。比如“同余”、“同姓”、“同班同学”。
核心概念：
- 等价类 $[x]_R$：和 $x$ 有关系的所有元素组成的小团体。比如“模3同余”，$[1] = {1, 4, 7, \dots}$。
- 商集 $A/R$：所有小团体组成的集合。即把大集合 $A$ 切蛋糕一样切开。
定理：等价关系对应于集合的划分（Partition）。切出来的蛋糕块互不重叠，拼起来是原集合。

2. 偏序关系 (Partial Order)

口诀：自反 + 反对称 + 传递。
意义：排座次、等级、包含关系。比如“小于等于 $\le$”、“整除 $ $”、“包含 $\subseteq$”。
哈斯图 (Hasse Diagram) —— 作图题重点：
- 它是偏序关系的简化图。
- 画法三原则：
  1. 去环（因为自反，默认都有环，不画）。
  2. 去传递边（如果 A->B->C，就把 A->C 那条线删掉）。
  3. 方向向上（把箭头去掉，默认下面的点指向上面的点）。
特殊元素（这是最难区分的，考试必考！）：假设大家在爬山（哈斯图）：
- 极大元 (Maximal)：站在某个山头的人，上面没人了。（可以有好几个山头，好几个人）。
- 最大元 (Maximum)：站在珠穆朗玛峰顶的人，他在所有人上面。（全图如果有一个最高点，它是最大元；如果有两个山头，就没有最大元）。
- 极小元 (Minimal)：站在谷底的人，下面没人了。（可以有多个）。
- 最小元 (Minimum)：站在马里亚纳海沟的人，他在所有人下面。（全图唯一）。
- 上界 (Upper Bound)：对于一个小分队（子集），能同时俯视他们的位置。
- 上确界 (LUB, Least Upper Bound)：所有上界里，位置最低的那个（最紧贴着头顶的）。
- 下界和 下确界 (GLB) 同理。

复习总结（考前必背）

五大性质：自反(对角线1)、反自反(对角线0)、对称(翻折相同)、反对称(翻折不互为1)、传递(A->B->C $\Rightarrow$ A->C)。
等价关系 = 自反 + 对称 + 传递 $\rightarrow$ 用来分类。
偏序关系 = 自反 + 反对称 + 传递 $\rightarrow$ 用来排序。
画哈斯图：去自环、去传递、向上画。
Warshall算法：用来求传递闭包，搞定矩阵运算。

好，我们来攻克第5章：函数。

这一章在离散数学中属于“承上启下”的章节，它既是集合论的应用，又是后续图论和代数系统的基础。

你可以把函数想象成一台“自动贩卖机”或者一场“射箭游戏”。

第一部分：5.1 函数的定义（游戏规则）

1. 什么是函数？

设有两个集合：$A$（定义域/输入） 和 $B$（陪域/可能输出）。函数 $f: A \to B$ 就是从 $A$ 到 $B$ 的一种映射关系。

核心规则（死记硬背）：

人人有份：$A$ 中的每一个元素，都必须射出一支箭。不能有元素“闲着”。
专一：$A$ 中的每一个元素，只能射出一支箭，指向 $B$ 中的某一个元素。不能“脚踏两只船”。
- 注意：$B$ 中的元素可以被射中多次，也可以不被射中。

术语翻译：

定义域 (Domain)：集合 $A$（所有的射箭手）。
陪域 (Codomain)：集合 $B$（所有的靶子）。
值域 (Range/Image)：集合 $f(A)$（$B$ 中真正被射中的那些靶子）。

第二部分：函数的性质（⭐ 考试核心）

这是本章最容易考大题的地方，通常题目会给出一个具体的数学函数，让你判断它是哪种类型。

我们继续用“射箭游戏”来比喻（$A$ 是人，$B$ 是靶子）：

1. 单射 (Injective / One-to-One)

人话：不撞靶。每个人射的靶子都不一样。
定义：对于不同的输入 $x_1 \neq x_2$，输出一定不同 $f(x_1) \neq f(x_2)$。
- 或者反过来说：如果射中了同一个靶子 $f(x_1) = f(x_2)$，那一定是同一个人射的 $x_1 = x_2$。
判断技巧：
- 在 $B$ 中，每个元素最多被射中 1 次（也可以是 0 次）。
- 例子：$f(x) = 2x$ （在整数集合上）是单射。
- 反例：$f(x) = x^2$ （在实数集合上）不是单射，因为 $1$ 和 $-1$ 都射中了 $1$。

2. 满射 (Surjective / Onto)

人话：不脱靶。靶场里的每一个靶子都被射中了，没有空靶子。
定义：值域 = 陪域。对于 $B$ 中的任意一个 $y$，在 $A$ 中都能找到一个 $x$ 使得 $f(x)=y$。
判断技巧：
- 在 $B$ 中，每个元素至少被射中 1 次。
- 例子：$f(x) = x + 1$ （在实数集合上）是满射，因为任何实数都能由另一个实数加1得到。
- 反例：$f(x) = x^2$ （从实数到实数）不是满射，因为负数没人射得中。

3. 双射 (Bijective / One-to-One Correspondence)

人话：完美配对。既不撞靶，也不脱靶。一人对一个，刚刚好。
定义：既是单射，又是满射。
重要性：只有双射函数，才能完全倒退回去（存在反函数）。
例子：身份证号和人（理论上）是双射关系。

第三部分：5.2 复合与反函数（进阶操作）

1. 复合函数 ($f \circ g$)

逻辑：流水线作业。
- 先把原料交给 $g$ 加工，得到中间产物。
- 再把中间产物交给 $f$ 加工，得到最终产品。
写法（⚠️ 容易搞反）：
- $f \circ g (x)$ 读作 “$f$ composite $g$”。
- 运算顺序：从右向左！先算 $g(x)$，再算 $f(\dots)$。
- 公式：$(f \circ g)(x) = f( g(x) )$。
条件：$g$ 的输出（值域）必须在 $f$ 的输入范围（定义域）内，否则 $f$ 接不住。

2. 反函数 ($f^{-1}$) – 逆函数

逻辑：撤销操作 (Undo)。
定义：如果 $f$ 把 $x$ 变成了 $y$，那么反函数 $f^{-1}$ 能把 $y$ 变回 $x$。
存在条件（⭐ 考点）：
- 只有双射函数才有反函数。
- 为什么？
  - 如果不满射（有空靶子），空靶子没法往回指。
  - 如果不单射（两人射一靶），靶子往回指的时候不知道该指谁（二义性）。
性质：
- $f^{-1}(f(x)) = x$ （折腾一圈回到原点）。
- $(f \circ g)^{-1} = g^{-1} \circ f^{-1}$ （注意顺序反过来了！就像穿袜子穿鞋，脱的时候要先脱鞋再脱袜子）。

第四部分：复习小结（考试怎么考？）

判断题：给你一个函数映射图或数学公式，问你是不是单射？是不是满射？
- 单射看箭头：没有两个箭头指同一个点。
- 满射看右边：右边没有落单的点。
证明题：证明某个函数是双射。
- 套路：
  1. 先证单射：设 $f(x_1) = f(x_2)$，推导出 $x_1 = x_2$。
  2. 再证满射：任取 $y \in B$，解方程 $y = f(x)$，证明解出的 $x$ 一定在 $A$ 里面。
计算题：求复合函数或反函数。
- 记得复合是从右往左算。
- 求反函数就是把 $y=f(x)$ 中的 $x$ 解出来。

掌握了单射、满射、双射的区别，这一章基本就稳了！

好的，第六章图论 是离散数学中最“直观”但也最容易“掉坑”的章节。因为它画出来都是点和线，看起来很简单，但背后的定理和计算（特别是矩阵部分）非常严谨。

我们把图论想象成“城市与道路”的系统：点是城市，边是道路。

第一部分：6.1 基本概念（看图识字）

1. 度 (Degree) —— $d(v)$

无向图（双向路）：
- 一个顶点连着几条边，它的度就是几。
- 例子：一个十字路口的度是 4，丁字路口的度是 3。
有向图（单行道）：
- 入度 $d^-(v)$：有多少个箭头指进来。
- 出度 $d^+(v)$：有多少个箭头指出去。
- 总度数 = 入度 + 出度。

2. 握手定理（⭐ 必考公式）

这是图论的“能量守恒定律”。

定理内容：所有顶点的度数之和 = 边数的 2 倍。
- $\sum d(v) = 2 \times E $
为什么？ 因为每一条边都有两个端点。你数度数的时候，这条边的左头数了一次，右头又数了一次，所以刚好是边数的2倍。
重要推论：
- 度数为奇数的顶点个数，一定是偶数个。（如果奇度顶点是奇数个，总度数就是奇数了，不可能是边数的2倍，矛盾）。
- 有向图版本：所有入度之和 = 所有出度之和 = 边数。

3. 特殊图（认识脸熟）

完全图 $K_n$：
- 所有人都互相关注。任意两个点之间都有边。
- 边数公式：$n(n-1)/2$。
正则图：
- 众生平等。所有点的度数都一样（比如都是3度，叫3-正则图）。
圈图 $C_n$：围成一个圈，首尾相接。
方体图 $Q_n$：画成立方体那样。

4. 图的同构 (Isomorphism)

意思：两个图看起来形状不一样（一个画得圆，一个画得方），但其实骨架结构是一模一样的。
怎么判断？（考试重点）：
- 先看“身份证”是否一致：顶点数要一样、边数要一样、度数序列（比如都有2个3度点，4个2度点）要一样。
- 如果这些都一样，还不能由肯定同构，但通常考试里如果不一样就可以直接判“不同构”。

5. 子图与补图

子图：从原图里抠出来一部分（点和边都必须是原图里的）。
补图：原图里有的边，补图里没有；原图里没有的边，补图里把它连上。（相当于“取反”）。

第二部分：6.2 图的连通性（修路问题）

1. 通路与回路

通路：从 A 走到 B 的路线。
回路：从 A 走到 A 的路线（转一圈）。
简单 vs 初级（容易混淆）：
- 简单通路：走过的边不重复。
- 初级通路（路径）：走过的点也不重复（更严格）。

2. 有向图的连通性（⭐ 老师划重点）

假设 A 和 B 是两个城市。

强连通 (Strongly Connected)：
- 双向畅通。A 能走到 B，B 也能走到 A（可以经过中转）。
- 判别：图里任意两点都能互相到达。
单向连通 (Unilaterally Connected)：
- 至少通一边。要么 A 能到 B，要么 B 能到 A。
弱连通 (Weakly Connected)：
- 修路修通了，不管方向。如果不看箭头的方向（把有向图变成无向图），整个图是连在一块的。
包含关系：强连通 $\subset$ 单向连通 $\subset$ 弱连通。

3. 割点与割边（桥）

割点：交通枢纽。删掉这个点（和连它的边），图就断开了（连通分量增加）。
割边 (桥)：交通要道。删掉这条边，图就断开了。

第三部分：6.3 矩阵表示（⭐ 计算题核心）

1. 邻接矩阵 $A$

用 0 和 1 表示点之间有没有边。
$A_{ij} = 1$ 表示点 $i$ 到点 $j$ 有边。
无向图的矩阵是对称的，有向图不一定。

2. 矩阵幂的含义（⭐ 必考计算）

题目通常会给你一个图，让你求邻接矩阵 $A$，然后算 $A^2$ 或 $A^3$。

定理含义：
- $A$：表示从 $i$ 到 $j$ 走 1步的方案数。
- $A^2$ ($A \times A$)：矩阵第 $i$ 行第 $j$ 列的数字，表示从点 $i$ 到点 $j$ 走 2步（长度为2）的通路有多少条。
- $A^3$：表示从点 $i$ 到点 $j$ 走 3步的通路有多少条。
- 举例：如果 $A^2$ 的第1行第3列是 2，说明从点1走到点3，长度为2的路线有2条。

3. 可达矩阵 $P$

不管走几步，只要能走到，就填 1，否则填 0。
用来判断连通性（特别是强连通性）。

第四部分：6.4 特殊图（⭐ 判定大题）

这三种图是图论里的“明星”，一定要分清它们的定义和判定方法。

1. 二部图 (Bipartite Graph)

定义：把点分成两波（比如左边一排男生，右边一排女生），同一波人之间不连线，线只在两波人之间连。
⭐ 判定定理：一个图是二部图 $\Leftrightarrow$ 图中没有奇数长度的回路。
- 解释：如果你能画一个三角形（长度3）或五边形（长度5），它绝对不是二部图。
匹配：
- 就是找边，使得这些边互不接触（没有公共端点）。
- 完备匹配：左边那波人（或者人少的那波），每个人都找到了对象。
- 完美匹配：所有人（左右两波）都找到了对象。

2. 欧拉图 (Euler Graph) —— 刷街任务

定义：一笔画。走遍所有的边，且每条边只走一次。
- 欧拉回路：走完所有边，最后回到起点。
- 欧拉通路：走完所有边，不回到起点（起点终点不同）。
⭐ 判定条件（死记硬背）：
- 欧拉回路（欧拉图）：图是连通的 + 所有顶点的度数都是偶数。
- 欧拉通路（半欧拉图）：图是连通的 + 只有 0 个或 2 个奇度顶点。
  - 如果有2个奇度点，必须从一个奇度点出发，到另一个奇度点结束。

3. 哈密顿图 (Hamilton Graph) —— 旅游任务

定义：走遍所有的点，且每个点只去一次（除了起点回到终点）。
区别：欧拉图关注边（路），哈密顿图关注点（城市）。
判定：哈密顿图很难判定（没有简单的充要条件），但在考试中通常用必要条件来证明“不是哈密顿图”。
⭐ 删点判定法（必要条件）：
- 如果一个图是哈密顿图，那么：删去 $k$ 个点，剩下的图最多变成 $k$ 块（连通分量 $\le k$）。
- 解题套路：如果题目让你证明某图不是哈密顿图，你就试着删掉几个关键节点（通常是度数高的），看图是不是碎成了好多块。如果碎成的块数比删掉的点数多，那就证明它不是。

复习小结（考前必看）

握手定理算度数和边数。
矩阵乘法算路径条数（$A^2, A^3$）。
欧拉图看度数奇偶（全是偶数->回路；2个奇数->通路）。
哈密顿图用删点法证伪。
二部图看有没有奇圈。

好的，我们进入第7章：树 (Trees)。

这一章非常“清爽”，因为它不像前面的图论那么抽象，很多概念（比如族谱、文件夹目录）我们在生活中天天见。这一章的计算题非常多，而且套路固定，是拿分的好机会。

我们将它分为无向树（基础理论）和根树（应用算法）两部分。

第一部分：7.1 无向树（骨架篇）

1. 什么是树？

直观理解：一个图，如果它连在一起（连通），而且没有闭环（无回路），它就是一棵树。
定义：连通且无回路的无向图。
森林：如果一个图不连通，但每个连通分量都是树，那它就是森林（好几棵树在一起）。

2. 树的性质（⭐ 填空选择题考点）

假设这棵树有 $n$ 个顶点，那么它一定满足：

边数固定：边数 $m = n - 1$。
- 例子：5个点的树，一定只有4条边。多一条这就成环了，少一条就不连通了。
连通性：树是“刚刚好”连通的。
- 删掉任意一条边，图就不连通了（这条边叫割边或桥）。
- 加上任意一条边，图里就会出现唯一的回路（圈）。

3. 生成树 (Spanning Tree)

场景：你要给 $n$ 个城市修路，要求所有城市都能互相到达，但为了省钱，修的路越少越好。
做法：在原有的道路图里，保留所有的点，删掉多余的边（破坏所有的环），最后剩下的这就是生成树。它包含原图所有顶点，边数刚好是 $n-1$。

4. 最小生成树 (Minimum Spanning Tree, MST) —— 【⭐ 必考大题】

场景：每条路都有造价（权值 $w$），怎么修路最省钱？
算法：我们主要掌握 PPT 强调的 Kruskal 算法（避圈法）。

Kruskal 算法步骤（贪心策略）：

排序：把图中所有的边，按权值从小到大排队。
选边：从最小的边开始选。
判断：
- 如果选这条边不会形成回路（圈），就把它加入生成树。
- 如果选这条边会形成回路（两个端点已经连通了），就扔掉这条边，看下一条。
结束：直到选够了 $n-1$ 条边为止。

考试技巧：做题时，把选中的边在图上描粗，并在旁边写出权值之和。

(注：关于 Prim 算法，虽然录音提了，但既然 PPT 明确写了 Kruskal，建议优先熟练 Kruskal。Prim 的逻辑是“从一个点出发，像霉菌一样慢慢向外吞噬最近的点”，主要用于稠密图，若有余力可了解)。

第二部分：7.2 根树及其应用（算法篇）

1. 什么是根树？

把无向树拎起来，指定一个点做“头头”（树根），其他的点一层层往下挂，就成了根树。
术语：
- 父亲/儿子/兄弟：很直观的亲属关系。
- 树叶：最底下的点，没有儿子（度数为1）。
- 分支点：有儿子的点（内点）。
- 层数/高度：树根是第0层（有的教材定为第1层，请以老师PPT为准，通常树根到某点的路径长度即为层数）。

2. 二叉树 (Binary Tree)

定义：一种特殊的有序树。
- 每个节点最多有两个儿子。
- 严格区分左儿子和右儿子（即使只有一个儿子，也要分是左还是右）。

3. 树的遍历 (Traversal) —— 【⭐ 必考操作】

给你一棵二叉树，让你写出遍历序列。记住口诀：根在哪里，就是什么序。

前序遍历 (Pre-order)：根 $\to$ 左 $\to$ 右。
- (先访问根节点，再逛左边，最后逛右边)。
中序遍历 (In-order)：左 $\to$ 根 $\to$ 右。
- (先把左边逛完，再访问根，最后逛右边)。
后序遍历 (Post-order)：左 $\to$ 右 $\to$ 根。
- (左右都逛完了，最后才访问根)。

4. 最优二叉树 (哈夫曼树) —— 【⭐ 计算题重灾区】

这是数据压缩的核心原理。

概念：带权路径长度 (WPL)

路径长度：从树根到该节点的边数（层数）。
带权路径长度 = 该节点的权值 $\times$ 它的路径长度。
树的 WPL = 所有叶子节点的带权路径长度之和。

哈夫曼树构造步骤（拼积木）：

找最小：在所有剩下的权值里，找出最小的两个。
合并：把这两个数作为叶子，造一个父节点，父节点的权值 = 两个子节点权值之和。
替换：把刚才那两个数划掉，把新生成的父节点权值放回去。
重复：重复上述步骤，直到只剩下一个点（树根）。

哈夫曼编码：

在哈夫曼树上，规定左分支为 0，右分支为 1（反之亦可，看题目要求）。
从根走到叶子，路上的 0/1 连起来就是该字符的编码。
特点：权值越大的（出现频率高），编码越短；权值越小的，编码越长。

实战演练：构造哈夫曼树

题目：给定权值 ${2, 3, 5, 7}$，求哈夫曼树及 WPL。

步骤：

池子：${2, 3, 5, 7}$。
第一轮：最小的是 2 和 3。合并得到 $2+3=5$。
- 新池子：${5, 7, \mathbf{5(新)}}$。
第二轮：最小的是 5 和 5(新)。合并得到 $5+5=10$。
- 新池子：${7, \mathbf{10(新)}}$。
第三轮：最小的是 7 和 10。合并得到 $7+10=17$。
- 结束。树根是 17。

计算 WPL：

节点 2 和 3：被合并了 3 次才到根（或者看图，层数为3）。不对，看合并过程：
- 2 和 3 在最底层（离根最远）。
- 5 和 7 离根近。
- 修正：看图最准确。
  - 根(17) -> 左(7), 右(10)
  - 右(10) -> 左(5), 右(5-由2+3生成)
  - 右下的(5) -> 左(2), 右(3)
路径长度：
- 7：走1步。
- 5：走2步。
- 2：走3步。
- 3：走3步。
WPL = $7 \times 1 + 5 \times 2 + 2 \times 3 + 3 \times 3 = 7 + 10 + 6 + 9 = 32$。

复习小结（考前必背）

树的边数：$n$ 个点对应 $n-1$ 条边。
Kruskal算法：选最小边，别构成圈。
遍历口诀：前序（根左右）、中序（左根右）、后序（左右根）。
哈夫曼树：每次挑最小的俩合并，WPL = $\sum$ (叶子权值 $\times$ 层数)。

好，我们终于来到了最后一站：第14章代数系统。

这一章听起来名字很吓人（“代数”总是让人想起复杂的公式），但其实它研究的是“运算的规则”。

你可以把它想象成在研究“游戏规则”。我们不关心你玩的是弹珠还是扑克牌（集合里的元素），我们关心的是怎么玩（运算），以及这个玩法有什么特性（律）。

第一部分：14.1 二元运算及其性质（基础规则）

1. 什么是二元运算？

定义：给两个输入，通过某种规则，吐出一个输出。比如 $1+2=3$，“+”就是二元运算。
表示：通常用 $*$、$\circ$、$\cdot$ 等符号表示。

2. 运算的性质（⭐ 老师划重点，必背）

这是判断一个系统“厉不厉害”的标准。

封闭性 (Closure)
- 人话：肥水不流外人田。
- 定义：集合 $S$ 中的任意两个元素运算后，结果还在 $S$ 里面。
- 例子：自然数做减法不封闭（$1-2=-1$，跑出去了）；但自然数做加法是封闭的。
交换律 (Commutative)
- 人话：顺序无所谓。
- 定义：$a * b = b * a$。
- 例子：加法（$1+2=2+1$）满足；矩阵乘法（$AB \neq BA$）通常不满足。
结合律 (Associative)
- 人话：先算谁都行（只要不改变左右顺序）。
- 定义：$(a * b) * c = a * (b * c)$。
- 例子：加法、乘法都满足；减法不满足（$(5-3)-1 = 1$，但 $5-(3-1)=3$）。
分配律 (Distributive)
- 定义：$a * (b \circ c) = (a * b) \circ (a * c)$。
- 通常涉及两个运算（如乘法对加法的分配律）。

3. 特异元素（⭐ 重点计算项）

在一个社会里，总有几个特殊人物。

单位元 (Identity) —— 记作 $e$
- 人话：透明人。谁跟它运算，结果还是谁自己。
- 定义：$a * e = a$ 且 $e * a = a$。
- 例子：加法的单位元是 0 ($5+0=5$)；乘法的单位元是 1 ($5 \times 1 = 5$)。
- 性质：如果存在，一定是唯一的。
零元 (Zero) —— 记作 $\theta$
- 人话：黑洞。谁跟它运算，结果就被它吞掉，变成它。
- 定义：$a * \theta = \theta$ 且 $\theta * a = \theta$。
- 例子：乘法的零元是 0 ($5 \times 0 = 0$)。
逆元 (Inverse) —— 记作 $a^{-1}$
- 人话：解药/后悔药。你做了什么操作，用逆元就能“抵消”掉，变回单位元 $e$。
- 定义：$a * a^{-1} = e$ 且 $a^{-1} * a = e$。
- 例子：
  - 加法中（$e=0$）：$5$ 的逆元是 $-5$。
  - 乘法中（$e=1$）：$5$ 的逆元是 $1/5$。
- 注意：只有当单位元存在时，谈论逆元才有意义。

第二部分：14.3 典型的代数系统（群论核心）

这是本章的大Boss。代数系统就像是给集合穿装备，装备（性质）越多，等级越高。

1. 升级路线图

半群 (Semigroup)
- 装备：封闭性 + 结合律。
- 例子：正整数的加法 $<Z^+, +>$。
独异点 (Monoid) / 含幺半群
- 装备：半群 + 单位元 $e$。
- 例子：自然数的乘法 $<N, \times>$，单位元是1。
群 (Group) —— 【⭐ 考试核心，必须背诵】
- 装备：独异点 + 逆元。
- 判定群的4个条件（缺一不可）：
  1. 封闭性。
  2. 结合律。
  3. 存在单位元 $e$。
  4. 集合里每个元素都有逆元。
- 例子：整数集合的加法 $<Z, +>$ 是群（有0，有负数）。
- 反例：整数集合的乘法 $<Z, \times>$ 不是群（因为像 $2, 3$ 这样的数没有整数逆元，2的逆元是0.5，不在整数里）。
阿贝尔群 (Abelian Group)
- 装备：群 + 交换律。
- 也叫：交换群。

2. 子群 (Subgroup)

定义：大群里面的一个小团队，自己也能构成一个群。
判定定理（⭐ 怎么证明 $H$ 是 $G$ 的子群？）：
- 只需验证一步：对于 $H$ 中任意两个元素 $a, b$，都有 $a * b^{-1} \in H$。
- (注：如果是加法群，就是验证 $a - b \in H$)。

3. 循环群 (Cyclic Group)

定义：整个群是由一个元素（生成元）通过不断运算“生”出来的。
表示：$G = = {a^1, a^2, a^3, \dots}$。
例子：模4加法 ${0, 1, 2, 3}$。
- 生成元是 $1$：$1, 1+1=2, 1+1+1=3, 1+1+1+1=0$。遍历了所有元素。

第三部分：复习策略总结（如何拿分？）

1. 证明题：XXX是不是群？

这是送分题，但格式要写对。必须按顺序验证四步：

第一步：设 $a, b \in S$，证明 $a * b \in S$ (封闭)。
第二步：说明运算满足结合律（通常题目给的数系运算都默认满足，写一句即可）。
第三步：找出单位元 $e$（解方程 $a*x=a$），并说明 $e \in S$。
第四步：对于任意 $a \in S$，找出逆元 $a^{-1}$（解方程 $a*y=e$），并说明 $a^{-1} \in S$。
结论：所以它是群。

2. 计算题：求幂、求逆元

在模运算（Mod）或者矩阵运算中，逆元不是简单的倒数。
方法：先求单位元 $e$，再解方程 $x * x^{-1} = e$。

3. 概念辨析

半群 vs 独异点 vs 群：看装备多少。
一定要注意集合的范围！
- 实数集上的乘法 $<R, \times>$ 是群吗？不是！因为 0 没有逆元。
- 非零实数集 $<R^*, \times>$ 才是群。

全书备考最后一句话

离散数学的考试，定义就是解题的钥匙。

遇到图论，先画图，数度数。
遇到逻辑，化简范式，看真值表。
遇到代数，套用“群”的四个条件去验证。
遇到关系，画出矩阵，看对角线和对称性。

lastPPT

1.命题的判断、判断命题公式类型、 1.判断命题公式类型(等值演算)、 1.判断命题公式类型（主析取范式）、 1.归谬法（反证法）实例（PPT）、 2.前束范式、 3.集合定义、 3.反证法、 4.性质判断、关系的闭包构造、 4.集合的划分、偏序关系判断、 6.定义：顶点的度数与握手定义，同构图、 6.实例：图的同构实例，生成子图 6.定义：通路、回路、割点 6.计算：利用邻接矩阵计算图中的通路数与回路数 6.二部图（定义、证明、判断），欧拉图，哈密顿图（判断、推论） 7.带权图的最小生成树（kruskal算法） 7.前缀码的生成 14.实例：二元运算的性质，交换律、结合律、幂等律的判断，特异元素的求解 14.群相关的概念和判断 14.子群的定义及判别

这份复习指南是根据你提供的“必考重点”清单整理的。我会把每一个知识点掰开了揉碎了讲，同时告诉你考试的时候大概率会怎么出题，让你心中有数。

第1章：命题逻辑

1. 命题的判断

知识点：
- 定义：命题必须是陈述句，且必须能判断真假（要么真，要么假，不能既真又假）。
- 不是命题的情况：
  - 感叹句（“哇！”）、疑问句（“吃了吗？”）、祈使句（“快跑！”）。
  - 真值不确定的陈述句（“$x + 1 = 2$”，因为不知道 $x$ 是几）。
  - 悖论（“我正在说谎”）。
考试怎么考：
- 选择题/判断题：给出一组句子，问你“下列哪个是命题？”
- 陷阱：“明天会下雨”通常被认为是命题（虽然现在不知道，但明天那一刻是有定论的），但“$x>0$”不是命题（谓词）。

2. 判断命题公式类型（三种方法）

公式类型：
- 永真式（重言式）：无论变量取什么值，结果永远为1（真）。
- 永假式（矛盾式）：无论变量取什么值，结果永远为0（假）。
- 可满足式：至少有一种情况结果为1（注意：永真式也是可满足式）。如果结果有0有1，它就是“非永真的可满足式”。

方法一：等值演算（化简法）

知识点：利用公式把长式子化简。
- 关键公式：$P \to Q \Leftrightarrow \neg P \vee Q$（去箭头）。
- 德摩根律：$\neg(A \wedge B) \Leftrightarrow \neg A \vee \neg B$。
考试怎么考：计算题或证明题。题目会要求“用等值演算法判断…”。如果不指定方法，这是化简选择题最快的方式。

方法二：主析取范式（$\sum m$）

知识点：
- 极小项 ($m$)：包含所有变量的合取（且）。例如 $P \wedge Q$ 对应 $m_3$ (11)。
- 判别法：求出主析取范式后，看下标的集合。
  - 若包含所有下标（如2变量有0,1,2,3） $\rightarrow$ 永真式。
  - 若为空（一个极小项都没有） $\rightarrow$ 永假式。
  - 若有部分下标 $\rightarrow$ 可满足式。
考试怎么考：计算题。“求公式的主析取范式，并判断其类型”。必拿分项。

3. 归谬法（反证法）

知识点：
- 逻辑依据：$(A \to B) \Leftrightarrow (A \wedge \neg B \to 0)$。
- 步骤：
  1. 把结论否定（加 $\neg$）。
  2. 把否定后的结论当作一个新的前提，加入到原前提中。
  3. 进行推导，直到推导出矛盾（0或空子句）。
考试怎么考：证明题。题目通常是“用归谬法/反证法证明下列推理有效”。切记第一步先写“假设结论不成立…”。

第2章：谓词逻辑

1. 前束范式

知识点：把所有的量词（$\forall, \exists$）都提取到公式的最左边，剩下的部分不含量词。
- 形式：$Q_1x_1 Q_2x_2 \dots Q_kx_k ( \text{无量词公式} )$。
步骤（死记硬背）：
1. 消箭头：$A \to B \Rightarrow \neg A \vee B$。
2. 内移否定：$\neg \forall x P(x) \Rightarrow \exists x \neg P(x)$。
3. 改名：如果两个量词用了同一个字母（如 $\forall x P(x) \vee \exists x Q(x)$），必须把其中一个改成 $y$。
4. 外提：把量词全部提到最前面。
考试怎么考：计算题。“求下列公式的前束范式”。重点考察改名规则和否定内移。

第3章：集合论

1. 集合定义与反证法

知识点：
- 集合的相等 $A=B$：证明 $A \subseteq B$ 且 $B \subseteq A$。
- 反证法在集合中的应用：假设 $x \in A$ 但 $x \notin B$（针对证明包含关系），最后推出矛盾。
考试怎么考：证明题。例如“证明 $(A-B)-C = A-(B \cup C)$”。如果题目要求用反证法，先假设左边集合有个元素 $x$ 但右边没有，然后推导出矛盾。

第4章：关系

1. 性质判断

知识点：看关系矩阵（0/1矩阵）判断：
- 自反：对角线全1。
- 反自反：对角线全0。
- 对称：沿对角线折叠重合 ($M_{ij} = M_{ji}$)。
- 反对称：对称位置不能同时为1 ($M_{ij}$和$M_{ji}$不同时为1，除非$i=j$)。
- 传递：最难看。若 $M \cdot M \subseteq M$ 则传递。
考试怎么考：选择题/填空题。给一个矩阵或集合，问满足哪些性质。

2. 关系的闭包构造

知识点：
- 自反闭包 $r(R)$：$R \cup I$（对角线补1）。
- 对称闭包 $s(R)$：$R \cup R^{-1}$（对称位置补1）。
- 传递闭包 $t(R)$：用 Warshall算法 或 $R \cup R^2 \cup R^3 \dots$。
考试怎么考：计算题。给一个关系矩阵，求它的自反、对称或传递闭包。Warshall算法求传递闭包是重点。

3. 集合的划分

知识点：由等价关系导出。等价类互不相交，且并集等于全集，这就是划分。
考试怎么考：给出等价关系，求商集 $A/R$（即写出所有的等价类）。

4. 偏序关系判断

知识点：满足 自反 + 反对称 + 传递。
考试怎么考：给一个关系图（哈斯图）或集合，问是不是偏序关系。或者画出偏序关系的哈斯图。

第6章：图论（大题集中地）

1. 顶点的度数与握手定理

知识点：
- 度 $d(v)$：连接顶点的边数。
- 握手定理：所有顶点的度数之和 = $2 \times$ 边数。
考试怎么考：填空题/计算题。已知度数求边数，或者已知边数求度数。例如：“有3个3度点，2个2度点，求边数？” $\to (3\times3 + 2\times2)/2 = 6.5$（错！度数和必须是偶数，这题无解）。

2. 同构图

知识点：两个图“形状不同但骨架一样”。
判定：点数相同、边数相同、度数序列相同。
考试怎么考：解答题。给两个图，问是否同构？如果是，标出顶点的对应关系；如果不是，找出一个不同点（如：左图有三角形，右图没有）。

3. 通路、回路、割点

知识点：
- 回路：起点=终点的通路。
- 割点：删掉它，图就断开了（连通分量增加）。
考试怎么考：看图找割点（选择题）；或者计算通路数（见下条）。

4. 邻接矩阵计算通路数与回路数

知识点（⭐高频计算）：
- 邻接矩阵 $A$。
- $A^n$（矩阵的n次方）：$A^n$ 中第 $i$ 行第 $j$ 列的数字，表示从点 $i$ 到点 $j$ 长度为 $n$ 的通路条数。
- 回路数：看 $A^n$ 的对角线元素之和（长度为 $n$ 的回路）。
考试怎么考：计算题。给图写出 $A$，算出 $A^2$ 或 $A^3$，问长度为2或3的通路有几条。

5. 二部图、欧拉图、哈密顿图

知识点：
- 二部图：没有奇数长度的回路（如三角形）。
- 欧拉图（一笔画回路）：连通 + 所有点度数均为偶数。
- 欧拉通路（一笔画不回起点）：连通 + 只有2个奇度点。
- 哈密顿图（经过所有点一次）：没有简单的充要条件。用推论（删点法）判断：删去 $k$ 个点，连通分量数不能超过 $k$。
考试怎么考：综合大题。给一个图，问：是不是二部图？有没有欧拉回路？是不是哈密顿图？（对于哈密顿图通常考“证明它不是”，用删点法）。

第7章：树

1. 带权图的最小生成树 (Kruskal算法)

知识点：
- Kruskal算法（避圈法）：把所有边按权值从小到大排序，依次选边，只要不构成回路就选，直到选够 $n-1$ 条边。
考试怎么考：作图/计算题。给一个带权图，让你画出最小生成树，并计算总权值。记得把选边的顺序写出来。

2. 前缀码的生成 (哈夫曼树)

知识点：
- 哈夫曼树：每次选两个权值最小的合并。
- 前缀码：向左走标0，向右走标1。
考试怎么考：计算题。给一组频率（权值），让你画出哈夫曼树，并写出每个字符的编码，或者计算带权路径长度 (WPL)。

第14章：代数系统

1. 二元运算的性质与特异元素

知识点：
- 交换律：$ab=ba$。
- 结合律：$(ab)c=a(bc)$。
- 幂等律：$a*a=a$。
- 单位元 $e$：$a*e=a$。
- 零元 $\theta$：$a*\theta=\theta$。
- 逆元：$a*a^{-1}=e$。
考试怎么考：解答题。定义一个新的运算（比如 $a*b = a+b-2$），让你验证它是否满足交换/结合律，并求单位元和逆元。

2. 群与子群的判断

知识点：
- 群：封闭 + 结合律 + 有单位元 + 有逆元。
- 子群：非空子集，且满足 $\forall a,b \in H \Rightarrow a*b^{-1} \in H$ （一步判定法）。
考试怎么考：证明题。
- 证明某个集合关于某运算构成群。
- 证明某个子集是子群（必考）。

总结建议：重点复习 第4章（关系性质）、第6章（图的性质与矩阵运算）、第7章（两个算法）、第14章（群的判定）。这四块内容通常占据卷面70%以上的分数。加油！

学习, 离散数学

离散数学

本文由作者按照 CC BY 4.0 进行授权