离散数学知识点汇总

文章摘要

LCY AI Pro

这篇文章系统整理了离散数学中的命题逻辑、集合论、二元关系、代数结构与图论基础内容，按定义、性质、定理与常见判定方法展开，重点突出符号记法、等值变换、推理规则和典型结论，适合复习时按章节快速回顾与对照记忆。

第一部分 数理逻辑 (Mathematical Logic)

第15章 命题逻辑基本概念

1. 命题 (Proposition)

• 定义：命题是具有唯一真值的陈述句。其真值（Truth Value）必须是“真”（True，记为 T 或 1）或“假”（False，记为 F 或 0）之一，且二者必居其一。
• 分类：
  • 原子命题（简单命题）：不能再分解为更简单陈述句的命题，通常用小写字母 $p, q, r, \dots$ 表示。
  • 复合命题：由原子命题通过逻辑联结词组合而成的命题。
• 非命题判定：感叹句、疑问句、祈使句、真值不确定的陈述句（如含有变量的开语句）均不属于命题。
• 判定要点：判断一个语句是否为命题时，核心是检查其真值是否在当前语境下被唯一确定。若同一句话因时间、对象或变量取值不同而真值不唯一，则通常不是命题。
• 常见辨析：
  • “$x>3$”不是命题，因为未给出 $x$ 的取值。
  • “今天下雨”在给定日期与地点后可判定真值，可视为命题。
  • “请开门”属于祈使句，不具备真值，因此不是命题。

2. 逻辑联结词 (Logical Connectives)

• 否定 ($\neg$)：$\neg p$ 为真当且仅当 $p$ 为假。
• 合取 ($\wedge$)：$p \wedge q$ 为真当且仅当 $p$ 与 $q$ 同时为真。对应自然语言中的“并且”、“不仅……而且”。
• 析取 ($\vee$)：$p \vee q$ 为假当且仅当 $p$ 与 $q$ 同时为假。对应自然语言中的“或者”（相容或）。
• 蕴涵 ($\rightarrow$)：$p \rightarrow q$ 仅在 $p$ 为真且 $q$ 为假时其真值为假。
  • $p$ 称为前件，$q$ 称为后件。
  • 自然语言表述：若 $p$ 则 $q$；只要 $p$ 就 $q$；因为 $p$ 所以 $q$；$p$ 仅当 $q$；只有 $q$ 才 $p$；除非 $q$ 否则 $\neg p$。
• 等价 ($\leftrightarrow$)：$p \leftrightarrow q$ 为真当且仅当 $p$ 与 $q$ 真值相同。对应自然语言中的“当且仅当”。
• 真值理解：
  • 否定相当于“翻转真值”。
  • 合取对应“同时成立”。
  • 析取对应“至少一个成立”。
  • 蕴涵可理解为“前件真而后件假”这一种情形会导致整体为假。
• 语义提醒：自然语言中的“如果……那么……”有时带因果含义；而命题逻辑中的 $p\rightarrow q$ 只关心真值组合，不涉及因果解释。

3. 命题公式与赋值

• 合式公式 (Well-formed Formula, WFF)：
  1. 单个命题变项是合式公式。
  2. 若 $A$ 是公式，则 $(\neg A)$ 是公式。
  3. 若 $A, B$ 是公式，则 $(A \wedge B), (A \vee B), (A \rightarrow B), (A \leftrightarrow B)$ 均是公式。
  4. 有限次使用上述规则产生的符号串是公式。
• 赋值（解释）：给公式中出现的命题变项指定真值的过程。对于含有 $n$ 个变项的公式，共有 $2^n$ 种不同的赋值。
• 公式分类：
  • 重言式（永真式）：在所有赋值下真值均为 1。
  • 矛盾式（永假式）：在所有赋值下真值均为 0。
  • 可满足式：至少存在一种赋值使公式真值为 1。
• 常见辨别：
  • 含有 $A\vee\neg A$ 的公式常可先化为重言式再继续判断。
  • 含有 $A\wedge\neg A$ 的公式常可直接判为矛盾式。
  • 复杂公式若既不显然永真也不显然永假，通常先借助等值演算化简，再判断其类型。
• 判定流程：
  1. 确认公式中的命题变项个数 $n$。
  2. 列出全部 $2^n$ 种赋值。
  3. 逐行计算公式真值。
  4. 依据结果全真、全假或部分为真判断其类型。
• 复杂度说明：真值表法直观但规模增长快；当 $n$ 较大时，常配合等值演算先化简公式，再进行类型判定。

---

第16章 命题逻辑等值演算

1. 等值式 (Equivalent Formulas)

• 定义：若 $A \leftrightarrow B$ 是重言式，则称 $A$ 与 $B$ 等值，记作 $A \Leftrightarrow B$。
• 使用意义：等值变换保证“真值保持不变”，因此在证明、化简、范式构造中可把复杂公式替换成更便于处理的等值公式。

2. 基本等值律

• 双重否定律：$\neg \neg A \Leftrightarrow A$
• 幂等律：$A \vee A \Leftrightarrow A, A \wedge A \Leftrightarrow A$
• 交换律：$A \vee B \Leftrightarrow B \vee A, A \wedge B \Leftrightarrow B \wedge A$
• 结合律：$(A \vee B) \vee C \Leftrightarrow A \vee (B \vee C), (A \wedge B) \wedge C \Leftrightarrow A \wedge (B \wedge C)$
• 分配律：$A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C), A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C)$
• 德·摩根律 (De Morgan)：$\neg(A \vee B) \Leftrightarrow \neg A \wedge \neg B, \neg(A \wedge B) \Leftrightarrow \neg A \vee \neg B$
• 吸收律：$A \vee (A \wedge B) \Leftrightarrow A, A \wedge (A \vee B) \Leftrightarrow A$
• 同一律：$A \vee 0 \Leftrightarrow A, A \wedge 1 \Leftrightarrow A$
• 零律：$A \vee 1 \Leftrightarrow 1, A \wedge 0 \Leftrightarrow 0$
• 排中律：$A \vee \neg A \Leftrightarrow 1$
• 矛盾律：$A \wedge \neg A \Leftrightarrow 0$
• 蕴涵等值式：$A \rightarrow B \Leftrightarrow \neg A \vee B$
• 等价等值式：$A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \wedge (B \rightarrow A)$
• 假言易位：$A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$

推导与证明要点

下列为常用等值律的简要推导或证明思路（多以真值条件或等值替换为主），以便理解等值律的来源与应用场景：

1. 双重否定律 $\neg\neg A \Leftrightarrow A$：对于 $A$ 的任一真值，先取否定再取否定可恢复原真值；可用真值表直接验证。

2. 幂等律 $A \vee A \Leftrightarrow A$，$A \wedge A \Leftrightarrow A$：若 $A$ 为真，则 $A\vee A$ 与 $A\wedge A$ 均为真；若 $A$ 为假，则两式均为假，故等值成立。

3. 交换律 与 结合律：交换律（$A\vee B \Leftrightarrow B\vee A$）与结合律（$(A\vee B)\vee C \Leftrightarrow A\vee(B\vee C)$ 等）均可由二元运算的对称性或真值表对称性直接验证，常作为运算重排的基础。

4. 分配律 $A\vee(B\wedge C) \Leftrightarrow (A\vee B)\wedge(A\vee C)$：左式当且仅当 $A$ 为真或 $B$ 与 $C$ 同时为真；右式当且仅当 $(A\vee B)$ 与 $(A\vee C)$ 同时为真，即 $A$ 为真或同时 $B,C$ 为真，两者条件等价。

5. 德·摩根律 $\neg(A\vee B) \Leftrightarrow \neg A \wedge \neg B$：$A\vee B$ 为假当且仅当 $A$ 与 $B$ 都为假，故其否定等价于 $\neg A\wedge\neg B$；同理 $\neg(A\wedge B) \Leftrightarrow \neg A\vee\neg B$。

6. 吸收律 $A\vee(A\wedge B) \Leftrightarrow A$：若 $A$ 为真，左式显然为真；若 $A$ 为假，则 $A\wedge B$ 为假，左式为假，故等值成立。对偶 $A\wedge(A\vee B) \Leftrightarrow A$ 类似。

7. 同一律与零律（中性元与支配元）：$A\vee 0\Leftrightarrow A$, $A\wedge 1\Leftrightarrow A$，以及 $A\vee 1\Leftrightarrow 1$, $A\wedge 0\Leftrightarrow 0$ 可由中性元或常真/常假项的定义直接得出。

8. 排中律与矛盾律：$A\vee\neg A \Leftrightarrow 1$ 和 $A\wedge\neg A \Leftrightarrow 0$ 均为恒真/恒假式，可用真值表直接验证，是命题逻辑的基本公理性质之一。

9. 蕴涵等值式 $A\rightarrow B \Leftrightarrow \neg A \vee B$：由蕴涵的真值定义（当 $A$ 真且 $B$ 假时蕴涵为假，其余情况为真）可化为上述析取形式，便于将含蕴涵的公式化为 CNF/ DNF。

10. 等价等值式 与 假言易位：$A\leftrightarrow B \Leftrightarrow (A\rightarrow B)\wedge(B\rightarrow A)$ 是等价的定义展开；$A\rightarrow B \Leftrightarrow \neg B\rightarrow\neg A$ 可由 $A\rightarrow B\equiv\neg A\vee B$ 及交换析取项得出（即 $\neg B\rightarrow\neg A \equiv B\vee\neg A$，同为 $\neg A\vee B$）。

这些推导均可通过真值表逐项验证，或使用已知的等值律逐步替换得到。理解等值律的推导能帮助在化简公式、构造范式或证明推理规则时进行有条理的代换。

进一步说明：在实际化简中，常把“含蕴涵、双条件的公式”先改写为仅含 $\neg,\wedge,\vee$ 的形式，再统一使用分配律和德·摩根律推进化简。例如

$$(A\rightarrow B)\wedge(B\rightarrow C) \Leftrightarrow (\neg A\vee B)\wedge(\neg B\vee C),$$

之后即可按 CNF 的思路继续整理。

等值演算规范：在书写化简过程时，建议每一步都标注所用等值律，并保持括号结构清晰。例如

$$A\rightarrow(B\wedge C) \Leftrightarrow \neg A\vee(B\wedge C) \Leftrightarrow (\neg A\vee B)\wedge(\neg A\vee C),$$

这样可直接得到 CNF 形式，便于后续推理或机器验证。

3. 范式 (Normal Forms)

• 文字：命题变项或其否定。
• 析取范式 (DNF)：有限个简单合取式的析取。
• 合取范式 (CNF)：有限个简单析取式的合取。
• 极小项 (Minterm)：在含有 $n$ 个变项的简单合取式中，若每个变项均以原形或否定形式出现且仅出现一次，称该合取式为极小项（常用 $m_i$ 表示）。
  • 性质：对于 $n$ 个变项，共有 $2^n$ 个极小项。每个极小项恰有一个成真赋值。
• 极大项 (Maxterm)：在含有 $n$ 个变项的简单析取式中，若每个变项均出现且仅出现一次，称该析取式为极大项（常用 $M_i$ 表示）。
  • 性质：每个极大项恰有一个成假赋值。
• 主析取范式 (PDNF)：公式的等值式，仅由若干极小项的析取组成。
• 主合取范式 (PCNF)：公式的等值式，仅由若干极大项的合取组成。
  • 应用：用于判定公式的类型、求公式的等值式、解决逻辑矛盾等。
• 构造步骤（真值表法）：
  • 构造 PDNF：选取真值为 1 的行；每一行写成对应极小项；最后将这些极小项作析取。
  • 构造 PCNF：选取真值为 0 的行；每一行写成对应极大项；最后将这些极大项作合取。
• 对应关系：在含 $n$ 个变项的情形下，PDNF 与 PCNF 都是唯一确定的（按项次序不同可视为同一公式），因此常作为公式的标准表示。
• 示意：若公式在某一行真值为 1，而该行赋值为 $p=1,q=0,r=1$，则对应极小项可写成 $p\wedge\neg q\wedge r$；若某行真值为 0，则写成对应极大项，方法与极小项相反。

---

第17章 命题逻辑推理理论

1. 推理的形式结构

• 前提与结论：设 $A_1, A_2, \dots, A_k$ 和 $B$ 是命题公式。若对于使 $A_1 \wedge A_2 \wedge \dots \wedge A_k$ 为真的赋值，均能使 $B$ 为真，则称由前提 $A_1, A_2, \dots, A_k$ 推出结论 $B$ 的推理是有效的。
• 逻辑蕴涵：推理有效当且仅当 $(A_1 \wedge A_2 \wedge \dots \wedge A_k) \rightarrow B$ 是重言式，记作 $A_1, A_2, \dots, A_k \Rightarrow B$。
• 检验方法：
  • 真值表法：直接验证上述蕴涵式是否恒真。
  • 反证思路：尝试寻找“前提全真且结论假”的赋值；若不存在，则推理有效。

2. 自然推理系统 P

• 推理规则：
  1. 规则 P（前提引入）：在证明的任何步骤都可以引入前提。
  2. 规则 T（逻辑等值引入）：在证明中，任何步骤出的公式都可以由前面的公式通过等值演算得到。
  3. 规则 CP（附加前提证明）：若要证明 $A \rightarrow B$，可将 $A$ 作为附加前提，证明出 $B$。
• 重要隐含式（推理定律）：
  • 附加规则：$A \Rightarrow A \vee B$
  • 化简规则：$A \wedge B \Rightarrow A$
  • 假言推理：$A \rightarrow B, A \Rightarrow B$
  • 拒取式：$A \rightarrow B, \neg B \Rightarrow \neg A$
  • 析取三段论：$A \vee B, \neg A \Rightarrow B$
  • 假言三段论：$A \rightarrow B, B \rightarrow C \Rightarrow A \rightarrow C$
  • 等价三段论：$A \leftrightarrow B, B \leftrightarrow C \Rightarrow A \leftrightarrow C$
  • 构造性二难：$(A \rightarrow B) \wedge (C \rightarrow D), A \vee C \Rightarrow B \vee D$
• 证明书写建议：
  1. 先列前提。
  2. 每一步仅做一次规则应用（P、T 或 CP）。
  3. 对含蕴涵的式子，可先用 $A\rightarrow B\Leftrightarrow\neg A\vee B$ 转为析取形式，再套用等值律化简。
  4. 最后明确写出目标结论，并标注依赖的前提集合。

---

---

第二部分 集合论 (Set Theory)

第1章 集合代数 (Set Algebra)

1. 集合的基本概念与表示

• 集合与元素：集合由确定的、互异的元素组成。常用 $a \in A$ 表示元素属于集合， $a \notin A$ 表示不属于。
• 特殊集合：
  • 空集 ($\emptyset$)：不含任何元素的集合。空集是任何集合的子集，是任何非空集合的真子集。
  • 全集 ($E$)：在给定范围内，所有考虑的元素构成的集合。
  • 幂集 ($P(A)$)：由集合 $A$ 的全体子集构成的集合。若 $|A| = n$，则其幂集的基数 $|P(A)| = 2^n$。
• 集合间的关系：
  • 包含 ($\subseteq$)：若 $\forall x(x \in A \rightarrow x \in B)$，则 $A \subseteq B$。
  • 相等 ($=$)：若 $A \subseteq B \wedge B \subseteq A$，则 $A = B$。
  • 真包含 ($\subset$)：若 $A \subseteq B$ 且 $A \neq B$，则 $A \subset B$。
• 证明方法提示：
  • 证 $A=B$ 常分两步：先证 $A\subseteq B$，再证 $B\subseteq A$。
  • 证 $A\subseteq B$ 的典型写法是“任取 $x\in A$，推出 $x\in B$”。
• 常见例子：
  • 证 $A\cap B\subseteq A$ 时，任取 $x\in A\cap B$，由定义知 $x\in A$ 且 $x\in B$，故 $x\in A$。
  • 证 $A\subseteq A\cup B$ 时，任取 $x\in A$，必有 $x\in A\cup B$。

2. 集合运算

• 并集 ($A \cup B$)：$\{x \mid x \in A \vee x \in B\}$。
• 交集 ($A \cap B$)：$\{x \mid x \in A \wedge x \in B\}$。
• 相对补集 ($A - B$)：$\{x \mid x \in A \wedge x \notin B\}$，即属于 $A$ 但不属于 $B$ 的元素。
• 绝对补集 ($\sim A$)：$E - A$。
• 对称差 ($A \oplus B$)：$(A - B) \cup (B - A)$ 或 $(A \cup B) - (A \cap B)$。
• 运算直观：
  • 并集保留“至少属于一个集合”的元素。
  • 交集保留“同时属于两个集合”的元素。
  • 相对补集体现“从 $A$ 中删去 $B$ 的部分”。
  • 对称差体现“仅属于其中一个集合”的元素。
• 常用等式：
  • $A-B=A\cap\sim B$。
  • $A\oplus B=(A\cup B)-(A\cap B)$。
  • $A\oplus A=\emptyset$，$A\oplus\emptyset=A$。
• 验证提示：集合运算恒等式通常可用元素法验证，即分别说明某元素属于左边当且仅当属于右边。

3. 集合恒等式 (Laws of Set Algebra)

集合运算满足以下规律，其形式与命题逻辑的等值律高度对应：

• 分配律：$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$；$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$。
• 德·摩根律：$\sim(A \cup B) = \sim A \cap \sim B$；$\sim(A \cap B) = \sim A \cup \sim B$。
• 吸收律：$A \cup (A \cap B) = A$；$A \cap (A \cup B) = A$。

证明提示：常用的证明方法为元素逐一判断或包含关系证明。例如要证 $A\cup(A\cap B)=A$，先证 $A\cup(A\cap B)\subseteq A$：任意 $x\in A\cup(A\cap B)$，则 $x\in A$ 或 $x\in A\cap B$，均能推出 $x\in A$；再证 $A\subseteq A\cup(A\cap B)$ 明显成立，由此得等号。德·摩根律亦可用元素是否属于集合的逐项判断证明。

4. 包含排斥原理 (Inclusion-Exclusion Principle)

• 用于计算有限集合并集的元素个数。
• 公式：$|A \cup B| = |A| + |B| - |A \cap B|$。对于三个集合：$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$。
• 应用：欧拉函数 ($\phi(n)$)：计算不大于 $n$ 且与 $n$ 互素的正整数个数。
  • 若 $n$ 的素因子分解为 $p_1, p_2, \dots, p_k$，则 $\phi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\dots(1 - \frac{1}{p_k})$。
• 思想解释：先把各集合元素个数相加会造成交集重复统计，因此需减去两两交集；但这一步又会把三重交集多减一次，所以再加回三重交集，依此交替进行。

---

第2章 二元关系 (Binary Relations)

1. 笛卡儿积与关系定义

• 有序对 ($\langle x, y \rangle$)：具有固定顺序的两个元素组成的序列。
• 笛卡儿积 ($A \times B$)：$\{ \langle x, y \rangle \mid x \in A \wedge y \in B \}$。
• 二元关系 ($R$)：笛卡儿积 $A \times B$ 的任意子集称为 $A$ 到 $B$ 的二元关系。若 $A = B$，则称为 $A$ 上的二元关系。
• 特殊关系：
  • 空关系 ($\emptyset$)：不含任何序偶。
  • 全域关系 ($E_A$)：$A \times A$ 本身。
  • 恒等关系 ($I_A$)：$\{ \langle x, x \rangle \mid x \in A \}$。
• 表示方式：关系可通过集合表示法、关系矩阵和关系图表示。三种表示可互相转换，便于在不同题型中进行判定与运算。

2. 关系的性质

设 $R$ 为 $A$ 上的关系：

• 自反性 (Reflexive)：$\forall x \in A, \langle x, x \rangle \in R$。
• 反自反性 (Irreflexive)：$\forall x \in A, \langle x, x \rangle \notin R$。
• 对称性 (Symmetric)：若 $\langle x, y \rangle \in R$，则 $\langle y, x \rangle \in R$。
• 反对称性 (Antisymmetric)：若 $\langle x, y \rangle \in R$ 且 $\langle y, x \rangle \in R$，则 $x = y$。
• 传递性 (Transitive)：若 $\langle x, y \rangle \in R$ 且 $\langle y, z \rangle \in R$，则 $\langle x, z \rangle \in R$。
• 判定提醒：
  • 自反性与反自反性不可能在非空集合上同时成立。
  • 对称性与反对称性可以在某些关系中同时成立（如恒等关系）。
  • 传递性常通过“找反例”快速否定：若存在 $xRy, yRz$ 但无 $xRz$，则不传递。

3. 关系运算与闭包

• 逆运算 ($R^{-1}$)：$\{ \langle y, x \rangle \mid \langle x, y \rangle \in R \}$。
• 合成运算 ($R \circ S$)：$\{ \langle x, z \rangle \mid \exists y (\langle x, y \rangle \in R \wedge \langle y, z \rangle \in S) \}$。
• 关系的闭包 (Closure)：通过在 $R$ 中添加最少的序偶使其满足某种性质：
  • 自反闭包 ($r(R)$)：$R \cup I_A$。
  • 对称闭包 ($s(R)$)：$R \cup R^{-1}$。
  • 传递闭包 ($t(R)$)：$R \cup R^2 \cup R^3 \cup \dots$。

构造说明：闭包的给出形式同时体现了“最小性”——例如自反闭包在 $R$ 的基础上仅补入所有 $\langle x,x\rangle$，从而既包含 $R$ 又是自反的，且不存在更小的自反超集包含 $R$。传递闭包的表达式表示所有可以通过有限次合成得到的序偶均被包含，计算上可通过矩阵幂或 Warshall 算法获得具体闭包关系。

• 常见操作：
  • 若题目要求补成对称关系，通常直接把每个 $\langle x,y\rangle$ 的逆序偶 $\langle y,x\rangle$ 一并加入。
  • 若题目要求补成传递关系，则需检查“前后可接”的序偶链，逐步补入缺失的连接。

4. 等价关系与划分

• 等价关系：同时满足自反、对称、传递性质的关系。
• 等价类 ($[x]_R$)：$\{ y \in A \mid \langle x, y \rangle \in R \}$，即所有与 $x$ 等价的元素构成的集合。
• 商集 ($A/R$)：所有等价类的集合。
• 划分：等价关系与集合的划分是一一对应的。商集即为集合 $A$ 的一个划分。
• 对应关系说明：
  • 由等价关系得到划分：把每个元素所在等价类作为一个块，得到互不相交且并为全集的块族。
  • 由划分得到等价关系：定义“属于同一块”即等价，可验证其满足自反、对称、传递。
• 典型例子：整数集合上“模 $m$ 同余”就是等价关系；其等价类把整数按余数分成 $m$ 个块。

5. 偏序关系 (Partial Ordering)

• 定义：满足自反、反对称、传递性质的关系，记作 $\preceq$。
• 哈斯图 (Hasse Diagram)：用于简化表示偏序关系的图形。省略自反环、传递线和方向箭头（由下而上表示方向）。
• 特殊元素：
  • 极大元/极小元：在偏序集中没有比它更大/更小的元素。
  • 最大元/最小元：比集合中所有其他元素都大/小（若存在则唯一）。
  • 上界/下界：针对子集而言，比子集中所有元素都大/小的元素。
  • 最小上界 (LUB/Supremum)：上界中最小的一个。
  • 最大下界 (GLB/Infimum)：下界中最大的一个。
• 易混概念区分：
  • “极大元/极小元”强调局部不可再大/小，可能不唯一。
  • “最大元/最小元”强调对全体元素的全局比较，若存在则必唯一。
  • LUB 与 GLB 针对子集定义，不必属于该子集本身，但必须属于所讨论的偏序集。
• 常见例子：
  • 在整除偏序中，若 $a\preceq b$ 表示“$a$ 整除 $b$”，则 $1$ 是最小元，若全集含有所有数的公共倍数则其最小公倍数可作为某些子集的最小上界。
  • 在子集偏序中，集合并与交分别体现为最小上界与最大下界。

---

---

第三部分 代数结构 (Algebraic Structures)

第12章 代数系统 (Algebraic Systems)

1. 二元运算及其性质

• 二元运算定义：设 $S$ 为集合，映射 $f: S \times S \rightarrow S$ 称为 $S$ 上的二元运算。
  • 封闭性：对于 $\forall x, y \in S$，都有 $x * y \in S$。这是代数系统的基本前提。
• 运算律：
  • 交换律：$x * y = y * x$。
  • 结合律：$(x * y) * z = x * (y * z)$。
  • 分配律：$x * (y \circ z) = (x * y) \circ (x * z)$（左分配律）及 $(y \circ z) * x = (y * x) \circ (z * x)$（右分配律）。
  • 吸收律：$x * (x \circ y) = x$ 且 $x \circ (x * y) = x$。
• 说明：不同代数系统满足的运算律不同。判断某结构属于哪一类时，需逐条核对定义要求，不能只凭某一条运算律成立就下结论。
• 例子：
  • 自然数加法满足交换律和结合律，因此具有较好的代数结构特征。
  • 矩阵乘法一般不满足交换律，因此在讨论相关代数系统时不能默认交换。

2. 代数系统中的特异元素

• 单位元 (Identity Element)：存在 $e \in S$，使得 $\forall x \in S, e * x = x * e = x$。
  • 左单位元 $e_L$：$e_L * x = x$。
  • 右单位元 $e_R$：$x * e_R = x$。
  • 若既有左单位元又有右单位元，则二者相等且唯一，称为单位元（或幺元）。
• 逆元 (Inverse Element)：设 $e$ 为 $S$ 中的单位元，对于 $x \in S$，若存在 $y \in S$ 使得 $x * y = y * x = e$，则称 $y$ 是 $x$ 的逆元，记作 $x^{-1}$。
• 零元 (Zero Element)：存在 $\theta \in S$，使得 $\forall x \in S, \theta * x = x * \theta = \theta$。
• 唯一性结论：
  • 若单位元存在，则唯一。
  • 若零元存在，则唯一。
  • 在有单位元的系统中，元素的逆元若存在也唯一。
• 证明提示：例如单位元唯一性可由“设 $e,f$ 都为单位元，则 $e=e*f=f$”直接推出；逆元唯一性可由结合律与单位元性质逐步化简得到。
• 逆元唯一性细化：若 $y$、$z$ 都是 $x$ 的逆元，则

  $$y = y*e = y*(x*z) = (y*x)*z = e*z = z,$$

  因而逆元唯一。

3. 代数系统的分类

• 半群 (Semigroup)：包含一个非空集合及定义在其上满足结合律的二元运算。

• 独异点 (Monoid)：含单位元的半群。

• 群 (Group)：一个非空集合及定义在其上的二元运算 $G = \langle S, * \rangle$，满足：

  1. 封闭性。
  2. 结合律。
  3. 存在单位元。
  4. 集合中每个元素都有逆元。
  • 阿贝尔群 (Abelian Group)：满足交换律的群。

• 层次关系：半群 $\supset$ 独异点 $\supset$ 群，条件逐步增强。做题时常先检查封闭与结合，再检查单位元与逆元，最后判断是否交换。

• 常见示例：

  • $\langle \mathbb{Z}, + \rangle$ 是阿贝尔群。
  • 正整数在乘法下是独异点但不是群（除 1 外元素无逆元）。

---

第14章 格与布尔代数 (Lattices and Boolean Algebra)

1. 格 (Lattice)

• 偏序定义：若偏序集 $\langle S, \preceq \rangle$ 中任意两个元素 $x, y$ 都有唯一个最小上界（LUB，记作 $x \vee y$）和最大下界（GLB，记作 $x \wedge y$），则称该偏序集为格。
• 代数定义：格也可以定义为一个代数系统 $\langle S, \vee, \wedge \rangle$，其中 $\vee$（并）和 $\wedge$（交）运算满足：
  1. 交换律。
  2. 结合律。
  3. 吸收律。
• 子格：若 $B \subseteq S$ 且 $B$ 对原格的运算封闭，则 $B$ 构成 $S$ 的子格。
• 对偶原理：在格的恒等式中，把 $\vee$ 与 $\wedge$、$1$ 与 $0$ 互换后得到的命题仍成立。利用该原理可减少重复证明。

2. 特殊类型的格

• 分配格 (Distributive Lattice)：满足分配律的格。
• 有界格 (Bounded Lattice)：存在全上界（最大元 $1$）和全下界（最小元 $0$）的格。
• 有补格 (Complemented Lattice)：在一个有界格中，若对于任意元素 $x$，都存在元素 $y$（称为 $x$ 的补元）使得 $x \vee y = 1$ 且 $x \wedge y = 0$。
• 关系说明：布尔代数要求“分配 + 有界 + 有补”。仅有补而不分配时，不一定构成布尔代数。

3. 布尔代数 (Boolean Algebra)

• 定义：一个有补的分配格称为布尔代数。
• 性质：
  • 补元唯一性：在布尔代数中，每个元素的补元是唯一的，记作 $x'$ 或 $\bar{x}$。
    补元唯一性证明：设 $y,z$ 都为元素 $x$ 的补元，则

  $$x\vee y=1,\quad x\wedge y=0,\qquad x\vee z=1,\quad x\wedge z=0.$$

  由分配律得

  $$y = y\wedge 1 = y\wedge(x\vee z) = (y\wedge x)\vee(y\wedge z) = 0\vee(y\wedge z) = y\wedge z.$$

  同理 $z = y\wedge z$，故 $y=z$，即补元唯一。
  • 满足德·摩根律：$(x \vee y)' = x' \wedge y'$ 且 $(x \wedge y)' = x' \vee y'$。
• 布尔表达式：由布尔变量通过 $\wedge, \vee, '$ 等运算构成的表达式，常用于逻辑电路的简化。
• 化简原则：可优先应用吸收律、德·摩根律和分配律，把表达式化为便于实现的与或非结构；在电路语境中，这对应门电路数量与层数的优化。
• 补元运算的意义：补元相当于把“真”与“假”互换，因此在布尔代数中常用于表达否定与条件排除。

---

---

第四部分 图论 (Graph Theory)

第5章 图的基本概念

1. 图的定义与表示

• 无向图：由顶点集 $V$ 和边集 $E$ 构成的代数系统，记为 $G = \langle V, E \rangle$。边是无序对，表示为 $(u, v)$。
• 有向图：边是有序对（称为弧），表示为 $\langle u, v \rangle$，其中 $u$ 是起点，$v$ 是终点。
• 基本术语：
  • 邻接与关联：边 $(u, v)$ 关联顶点 $u$ 和 $v$，此时 $u$ 和 $v$ 互为邻接点。
  • 孤立点：不与任何边关联的顶点。
  • 简单图：不含平行边（两点间多条边）且不含环（起点终点相同的边）的图。
  • 邻接点的含义：两个顶点之间存在边，就说明它们可以直接相连；在图的描述中，是否相邻通常是判断结构关系的最基本依据。
• 表示补充：同一图可用边集表示、邻接矩阵或邻接表表示。理论分析中常用边集与定义，算法处理时常用矩阵或邻接表。
• 常见例子：若顶点 $v$ 仅与两条边相连，则 $d(v)=2$；若有一条自环，则该环对度数贡献 2。

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

• 度数 ($d(v)$)：与顶点 $v$ 关联的边数（环计 2 度）。度数反映了顶点与其他顶点的连接紧密程度，是判断图结构的重要量。
  • 在有向图中区分入度 ($d^-(v)$) 和出度 ($d^+(v)$)。其中入度表示指向 $v$ 的弧数，出度表示从 $v$ 发出的弧数。
  • 若一个顶点既有入弧又有出弧，则其总度数满足 $d(v)=d^-(v)+d^+(v)$。
• 握手定理 (Handshaking Lemma)：图中所有顶点的度数之和等于边数 $m$ 的 2 倍。

  $$\sum_{v \in V} d(v) = 2m$$

• 推论：
  1. 任何图中，奇度顶点的个数必为偶数。
  2. 有向图中，所有顶点的入度之和等于出度之和，且都等于边数 $m$。
• 证明思路：无向图中每条边都会给两个端点各贡献 1 次计数（环贡献 2 次），因此总和为 $2m$。奇度顶点个数为偶数可由“总和为偶数”直接推出。
• 直观理解：把每条边想象成“拉起两个端点的一次连接”，每次连接都给度数总和贡献 2，因此总和必为偶数。

3. 通路、回路与连通性

• 通路 (Path)：顶点与边的交替序列，记作 $v_0 e_1 v_1 e_2 \cdots e_k v_k$。若从 $v_0$ 到 $v_k$ 的相邻关系都由图中的边依次连接，则该序列就是一条通路。
  • 长度：通路中边的条数称为通路长度。长度越大，说明沿图中边逐步移动的次数越多。
  • 简单通路：所有边各异的通路。它强调边不重复，便于分析经过路径时是否发生折返。
  • 初级通路：所有顶点各异的通路。它比简单通路更严格，要求除终点外不经过重复顶点。
• 回路 (Circuit)：起点和终点重合的通路。若回路中除起点与终点外其余顶点都不重复，则称为圈。回路体现了从某点出发又回到原点的闭合行走方式。
• 连通图：
  • 无向图：任意两点间都存在通路的图。连通性说明图整体上“没有断开”，也就是说任意两个顶点都可以通过若干条边联系起来。
  • 有向图连通性：
    • 强连通：任意两点间互相可达。也就是说，从任意一个顶点出发，沿有向边总能到达另一个顶点，并且还能返回。
    • 单向连通：任意两点间至少单向可达。
    • 弱连通：忽略方向后所得无向图是连通的。
  • 连通分支：图中的极大连通子图。若图不连通，则可分解为若干连通分支，每个连通分支内部彼此连通，而不同分支之间没有通路。
• 分析要点：判断连通性时，常先从任一顶点出发做可达性搜索；若能覆盖全部顶点则连通，否则按覆盖结果划分连通分支。
• 路径与通路区别：通路强调边或顶点的重复限制，而连通性只关心“是否能到达”，不要求路径最短或唯一。

---

第6章 欧拉图与哈密尔顿图

1. 欧拉图 (Eulerian Graphs)

• 欧拉回路：经过图中每条边恰好一次的闭回路。
• 欧拉图定义：具有欧拉回路的图。
• 判定定理：
  • 无向图：$G$ 是欧拉图当且仅当 $G$ 连通且所有顶点的度数均为偶数。
  • 有向图：$G$ 是欧拉图当且仅当 $G$ 强连通且每个顶点的入度等于出度。
• 欧拉通路：经过每条边恰好一次但不是回路。判定条件：连通且恰有两个奇度顶点（作为起点和终点）。
• 常见结论：欧拉通路存在时，两个奇度顶点必然分别对应通路的起点和终点；若不存在奇度顶点，则欧拉通路实际上就是欧拉回路。这说明欧拉图的关键不在于顶点是否全部出现，而在于每条边能否恰好被经过一次。
• 应用提醒：欧拉问题本质是“边覆盖一次”，因此在建模时应优先把任务对象映射为边而非顶点。
• 常见例子：如果一个无向图有 0 个或 2 个奇度顶点并且连通，则可以分别理解为欧拉回路或欧拉通路的典型情形。

2. 哈密尔顿图 (Hamiltonian Graphs)

• 哈密尔顿圈：经过图中每个顶点恰好一次的圈。
• 哈密尔顿图定义：具有哈密尔顿圈的图。
• 判定条件 (必要条件)：若 $G$ 是哈密尔顿图，则对于 $V$ 的任意非空真子集 $S$，有 $p(G-S) \le |S|$，其中 $p(G-S)$ 是删除 $S$ 后所得图的连通分支数。
• 判定条件 (充分条件 - Ore定理)：对于 $n \ge 3$ 的简单图，若任意一对不相邻顶点 $u, v$ 均满足 $d(u) + d(v) \ge n$，则 $G$ 是哈密尔顿图。这个条件说明，当图中任意一对互不相邻的顶点在连接“密度”上足够高时，就更容易形成经过全部顶点的闭回路。
• 比较说明：与欧拉图相比，哈密尔顿图缺少同样简洁的充要判定条件，常依赖必要条件与若干充分条件综合判断。
• 直观区别：欧拉图关心“边是否都走过一次”，哈密尔顿图关心“每个顶点是否恰好访问一次”。

---

第7章 树 (Trees)

1. 无向树及其性质

• 定义：连通且无回路的无向图。
• 等价定义：
  1. $G$ 是连通的且边数 $m = n - 1$。
  2. $G$ 中任意两点间有且仅有一条初级通路。
  3. $G$ 无回路，但在任意两个不相邻顶点间添加一条边后形成唯一的圈。
• 森林：每个连通分支都是树的图。
• 基本性质：树是最简单的连通图之一，任意去掉一条边都会破坏连通性；反过来，若向树中加入一条边，就会唯一地生成一个回路。这一性质表明树在“连通”与“无回路”之间处于临界状态。
• 证明联系：三条等价定义可以两两推出，常见证明路径是“连通无回路 $\Rightarrow m=n-1$”与“$m=n-1$ 且连通 $\Rightarrow$ 任意两点唯一通路”。
• 常见推法：树中的任意两点之间不能有两条不同初级通路，否则会形成回路，因此“唯一通路”与“无回路”紧密对应。

2. 根树 (Rooted Trees)

• 基本概念：有一个特定顶点称为根，边都指向离开根的方向。
  • 叶子：入度为 1、出度为 0 的顶点。
  • 分支点：出度不为 0 的顶点。
  • 层数：从根到该顶点的路径长度。
• m 叉树：每个分支点最多有 $m$ 个儿子的根树。
• 完全 m 叉树：每个分支点恰好有 $m$ 个儿子，且所有叶子在同一层。
• 层次意义：根树常用于表示层级结构，顶点按层次逐级展开，便于描述从根到各顶点的远近关系，也便于理解树的递推性质。
• 遍历视角：根树上的先序、中序、后序和层序遍历对应不同的信息访问顺序，是树结构算法与表达式处理的重要基础。
• 层次结构例子：根的子结点处于第 1 层，孙结点处于第 2 层，依此类推，层数越大表示离根越远。

3. 最优二叉树与 Huffman 算法

• 带权路径长度 (WPL)：设 $t$ 片树叶的权分别为 $w_1, w_2, \dots, w_t$，其层数（路径长度）分别为 $l_1, l_2, \dots, l_t$，则

  $$WPL = \sum_{i=1}^{t} w_i l_i$$

• 最优二叉树：在所有具有给定权值的叶子的二叉树中，$WPL$ 最小的树。
• Huffman 算法步骤：
  1. 从给定的权值集合中选取两个最小的权值 $w_1, w_2$。
  2. 以这两个权值为子节点构造一个分支点，其权值为 $w_1 + w_2$。
  3. 从原集合中删除 $w_1, w_2$，并将新权值 $w_1 + w_2$ 加入集合。
  4. 重复步骤 1-3，直到集合中只剩下一个权值（即根节点）。
• 正确性直观：将最小的两个权值优先放到更深层可使高权值尽量靠近根，从而降低总体 $WPL$；该贪心策略可证明得到全局最优结果。
• 计算提示：实际求解时可把每一次合并记录为一棵新树的权值，最后从根向下还原编码结构或树形结构。