命题逻辑

命题逻辑的基本概念

命题与真值

• 命题：判断结果唯一的陈述句
• 命题的真值：判断的结果
• 真值的取值：真与假
• 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不唯一确定的不是命题

命题分类

简单命题（也称原子命题,不能被分解成更简单的命题） 复合命题（由简单命题通过联结词联结而成的命题）

简单命题符号化

• 用小写英文字母 $p,q,r \cdots$ 或 $p_1,p_2,p_3 \cdots$ 表示
• 用 $1$ 表示真（$T$），用 $0$ 表示假（$F$）

连接词

• 否定：$\neg p$
• 合取：$p \land q$
• 析取：$p \lor q$
• 蕴含：$p \to q$
• 等价：$p \leftrightarrow q$

命题变项

• 命题常项：一个命题标识符表示确定的命题
• 命题变项：一个命题标识符表示不确定的命题

命题常项和变项均由字母表示

合式公式

1. 单个命题变项和命题常项是合式公式, 称作原子命题公式
2. 若A是合式公式，则 ($\neg A$)也是
3. 若A, B是合式公式，则($A \land B$), ($A \lor B$), ($A \to B$), ($A \leftrightarrow B$)也是
4. 只有有限次地应用 1. — 3. 形成的符号串才是合式公式

合式公式的层次

1. 单个命题变项为 $0$ 层
2. 称 A 是 $n+1(n \geq 0)$ 层公式是指下面情况之一： (a) $A=\neg B$, $B$ 是 $n$ 层公式； (b) $A=B \land C$, 其中 $B,C$ 分别为 $i$ 层和 $j$ 层公式， 且 $n=\max(i,j)$； (c) $A=B \lor C$, 其中 $B,C$ 的层次及 $n$ 同 (b)； (d) $A=B \to C$, 其中 $B,C$ 的层次及 $n$ 同 (b)； (e) $A=B \leftrightarrow C$, 其中 $B,C$ 的层次及 $n$ 同 (b).
3. 若公式 $A$ 的层次为 $k$, 则称 $A$ 为 $k$ 层公式.

公式赋值

设 $p_1,p_2,\cdots,p_n$ 是在 $A$ 中出现的所有命题变项，$A$ 是一个合式公式，$a_1,a_2,\cdots,a_n$ 是 $p_1,p_2,\cdots,p_n$ 的真值，则称 $a_1,a_2,\cdots,a_n$ 是 $A$ 的一个赋值。

• 若使 $A$ 的值为真，则称 $a_1,a_2,\cdots,a_n$ 是 $A$ 的一个真值赋值
• 若使 $A$ 的值为假，则称 $a_1,a_2,\cdots,a_n$ 是 $A$ 的一个假值赋值

公式的类型

• 重言式 或 永真式：对任何赋值，公式的值都为真
• 矛盾式 或 永假式：对任何赋值，公式的值都为假

若一个公式不是矛盾式，则称它是可满足式。

真值表

将命题公式 $A$ 在所有赋值下取值的情况列成表, 称作 $A$ 的真值表.

等值式

若 $A \leftrightarrow B$ 是重言式，则称 $A$ 与 $B$ 等值，记作 $A \Leftrightarrow B$，并称 $A$ 与 $B$ 是等值式。

• 真值表法
• 等值演算法

基本等值式

$$\begin{aligned} 双重否定律 & & \neg(\neg A) & \Leftrightarrow A \newline \newline 幂等律 & & A \land A & \Leftrightarrow A \newline & & A \lor A & \Leftrightarrow A \newline \newline 交换律 & & A \land B & \Leftrightarrow B \land A \newline & & A \lor B & \Leftrightarrow B \lor A \newline \newline 结合律 & & A \land (B \land C) & \Leftrightarrow (A \land B) \land C \newline & & A \lor (B \lor C) & \Leftrightarrow (A \lor B) \lor C \newline \newline 分配律 & & A \land (B \lor C) & \Leftrightarrow (A \land B) \lor (A \land C) \newline & & A \lor (B \land C) & \Leftrightarrow (A \lor B) \land (A \lor C) \newline \newline 吸收律 & & A \land (A \lor B) & \Leftrightarrow A \newline & & A \lor (A \land B) & \Leftrightarrow A \newline \newline 零律 & & A \land 0 & \Leftrightarrow 0 \newline & & A \lor 1 & \Leftrightarrow 1 \newline \newline 同一律 & & A \land 1 & \Leftrightarrow A \newline & & A \lor 0 & \Leftrightarrow A \newline \newline 排中律 & & A \lor \neg A & \Leftrightarrow 1 \newline & & A \land \neg A & \Leftrightarrow 0 \newline \newline 矛盾律 & & A \land \neg A & \Leftrightarrow 0 \newline & & A \lor \neg A & \Leftrightarrow 1 \newline \newline 蕴含等值式 & & A \to B & \Leftrightarrow \neg A \lor B \newline & & \neg(A \to B) & \Leftrightarrow A \land \neg B \newline \newline 德摩根律 & & \neg(A \land B) & \Leftrightarrow \neg A \lor \neg B \newline & & \neg(A \lor B) & \Leftrightarrow \neg A \land \neg B \newline \newline 等价等值式 & & A \leftrightarrow B & \Leftrightarrow (A \to B) \land (B \to A) \newline 假言易位 & & A \to B & \Leftrightarrow \neg B \to \neg A \newline & & \neg(A \to B) & \Leftrightarrow A \land \neg B \newline \newline 等价否定 & & A \leftrightarrow B & \Leftrightarrow \neg A \leftrightarrow \neg B \newline 归谬论 & & A \to B & \Leftrightarrow \neg B \to \neg A \newline \end{aligned}$$

析取范式与合取范式

简单析取式与简单合取式

• 文字：命题变项或其否定
• 简单析取式：有限个文字的析取 $$p, \neg q, p \lor q, \neg p \lor q, \neg p \lor \neg q$$
• 简单合取式：有限个文字的合取 $$p, \neg q, p \land q, \neg p \land q, \neg p \land \neg q$$

单个文字既是析取式又是合取式

一个简单析取式是重言式当且仅当它包含一个命题变项和它的否定 一个简单合取式是矛盾式当且仅当它包含一个命题变项和它的否定

析取范式与合取范式

析取范式：$$A_1 \lor A_2 \lor \cdots \lor A_n$$ 其中 $A_i$ 是简单合取式

合取范式：$$A_1 \land A_2 \land \cdots \land A_m$$ 其中 $A_i$ 是简单析取式

一个析取范式是矛盾式当且仅当它的每一个合取式都是矛盾式 一个合取范式是重言式当且仅当它的每一个析取式都是重言式

任意一个命题公式都可以化为析取范式和合取范式

主析取范式与主合取范式

主析取范式与极小项

主析取范式：$$m_0 \lor m_1 \lor \cdots \lor m_{2^n-1}$$ 其中 $m_i$ 被称作极小项，是 $n$ 个文字的析取 $m_i$ 的第 $j$ 个文字是 $p_j$ 或 $\neg p_j$ 若 $i$ 的二进制表示为 $b_1b_2\cdots b_n$，则 $m_i$ 为 $$p_1^{b_1} \land p_2^{b_2} \land \cdots \land p_n^{b_n}$$ $p_j^{b_j}$ 表示 $p_j$ 若 $b_j=1$ 则取 $p_j$，否则取 $\neg p_j$

主合取范式与极大项

主合取范式：$$M_0 \land M_1 \land \cdots \land M_{2^n-1}$$ 其中 $M_i$ 被称作极大项，是 $n$ 个文字的合取 $M_i$ 的第 $j$ 个文字是 $p_j$ 或 $\neg p_j$ 若 $i$ 的二进制表示为 $b_1b_2\cdots b_n$，则 $M_i$ 为 $$p_1^{b_1} \lor p_2^{b_2} \lor \cdots \lor p_n^{b_n}$$ $p_j^{b_j}$ 表示 $p_j$ 若 $b_j=1$ 则取 $p_j$，否则取 $\neg p_j$

任意一个命题公式都可以化为唯一的主析取范式和主合取范式

连接词完备集

• 不可兼析取：$\overline{\lor}$ 即异或
  • $A \overline{\lor} B \Leftrightarrow (A \lor B) \land \neg (A \land B) \Leftrightarrow (A \land \neg B) \lor (\neg A \land B)$
• 或非：$\downarrow$
  • $A \downarrow B \Leftrightarrow \neg (A \lor B) \Leftrightarrow \neg A \land \neg B$
• 与非：$\uparrow$
  • $A \uparrow B \Leftrightarrow \neg (A \land B) \Leftrightarrow \neg A \lor \neg B$

若任意 $n$ 元真值函数都可以由仅含 $S$ 中的连接词构成的公式表示，则称 $S$ 为连接词完备集

部分完备集举例

$$S = \lbrace \neg, \land, \lor \rbrace$$ 证明：任意一个 $n$ 元函数都可与唯一的一个主析取范式和主合取范式对应

$$S = \lbrace \neg, \land \rbrace$$ 证明：$A \lor B \Leftrightarrow \neg (\neg A \land \neg B)$

$$S = \lbrace \neg, \lor \rbrace$$ 证明：$A \land B \Leftrightarrow \neg (\neg A \lor \neg B)$

$$S = \lbrace \neg, \to \rbrace$$ 证明：$A \land B \Leftrightarrow \neg A \to B$

$$S = \lbrace \lor, \land, \to, \leftrightarrow \rbrace$$ 不是完备集，恒取 $0$ 的函数无法表示

$$S = \lbrace \uparrow \rbrace$$ 证明：$$\begin{aligned} \neg A &\Leftrightarrow A \uparrow A \newline A \land B &\Leftrightarrow \neg (A \uparrow B) \newline A \lor B &\Leftrightarrow \neg (\neg A \uparrow \neg B) \newline \end{aligned}$$

最小连接词完备集

若 $S$ 是连接词完备集，从 $S$ 中去掉任意一个连接词后 $S$ 不再是完备集，则称 $S$ 为最小连接词完备集

消解算法与可满足性问题

$$C_1 \land C_2 \approx Res(C_1, C_2) = C_1’ \lor C_2’$$

1. 若 $C_1 \land C_2 \leftrightarrow (l \lor C_1’) \land (\neg l \lor C_2’)$ 是可满足的，则称 $C_1’ \lor C_2’$ 也是可满足的
2. 若 $C_1’ \lor C_2’$ 是可满足的，则称 $C_1 \land C_2$ 也是可满足的 故可将 $C_1 \land C_2$ 化为 $C_1’ \lor C_2’$，称作消解

推理

当 $A_1 \land A_2 \land \cdots \land A_n \to B$ 是重言式时，称 $B$ 由 $A_1, A_2, \cdots, A_n$ 推出，记作 $\lbrace A_1, A_2, \cdots, A_n \rbrace \vdash B$ $A_1, A_2, \cdots, A_n$ 称作前提，$B$ 称作结论 称前提推出结论是有效的或正确的，并称 $B$ 是有效结论。

推理的形式结构

1. $\lbrace A_1, A_2, \cdots, A_n \rbrace \vdash B$
   • 若推理正确，记为 $\lbrace A_1, A_2, \cdots, A_n \rbrace \vDash B$
   • 若推理不正确，记为 $\lbrace A_1, A_2, \cdots, A_n \rbrace \nvDash B$
2. $A_1 \land A_2 \land \cdots \land A_n \to B$
   • 若推理正确，记为 $A_1 \land A_2 \land \cdots \Rightarrow B$
3. 前提：$A_1, A_2, \cdots, A_n$，结论：$B$

推理定律

$$\begin{aligned} 附加律 & & A &\Rightarrow A \land B \newline 化简律 & & A \land B &\Rightarrow A \newline 假言推理 & & A \land (A \to B) &\Rightarrow B \newline 拒取式 & & \neg A \land \neg B &\Rightarrow \neg (A \land B) \newline 析取三段论 & & A \lor B, \neg A &\Rightarrow B \newline 假言三段论 & & A \to B, B \to C &\Rightarrow A \to C \newline 等价三段论 & & A \leftrightarrow B, B \leftrightarrow C &\Rightarrow A \leftrightarrow C \newline 构造性二难 & & A \to B, C \to D, A \lor C &\Rightarrow B \lor D \newline & & A \to B, \neg A \to B &\Rightarrow B \newline 破坏性二难 & & A \to B, C \to D, \neg B \lor \neg D &\Rightarrow \neg A \lor \neg C \newline & & A \to B, \neg B \to A &\Rightarrow A \leftrightarrow B \newline \end{aligned}$$

形式系统

自然推理系统

定义3.3 自然推理系统 $P$ 定义如下:

1. 字母表
   1. 命题变项符号：$p, q, r, \ldots, p_i, q_i, r_i, \ldots$
   2. 联结词符号：$\neg, \land, \lor, \to, \leftrightarrow$
   3. 括号与逗号：$(, ), ,$
2. 合式公式（同定义1.6）
3. 推理规则
   1. 前提引入规则
   2. 结论引入规则
   3. 置换规则

构造证明

设前提 $A_1, A_2, \ldots, A_k$，结论 $B$ 及公式序列 $C_1, C_2, \ldots, C_l$， 如果每一个 $C_i \ (1 \leq i \leq l)$ 是某个 $A_j \ (1 \leq j \leq k)$， 或者可由序列中前面的公式应用推理规则得到， 并且 $C_l = B$， 则称这个公式序列是由 $A_1, A_2, \ldots, A_k$ 推出 $B$ 的证明。

附加前提证明法

附加前提证明法适用于结论为蕴涵式

• 欲证
  • 前提：$A_1, A_2, \ldots, A_k$
  • 结论：$C \to B$
• 等价地证明
  • 前提：$A_1, A_2, \ldots, A_k, C$
  • 结论：$B$

归谬法

• 欲证
  • 前提：$A_1, A_2, \ldots, A_k$
  • 结论：$B$
• 等价地证明
  • 前提：$A_1, A_2, \ldots, A_k, \neg B$
  • 结论：$0$

一阶谓词逻辑

一阶逻辑命题符号化

客体

• 客体：客观存在的实体，如人、物、事物等。
• 个体词：所研究对象中独立存在的客体。
  • 个体常项：具体的事物，用 $a$ 、 $b$ 、 $c$ 等表示 。
  • 个体变项：抽象的事物，用 $x$ 、 $y$ 、 $z$ 等表示。
• 个体域：个体变项的取值范围。
  • 有限个体域：如 $\lbrace a,b,c \rbrace$，$\lbrace 1, 2 \rbrace$ 等。
  • 无限个体域：如全体自然数 $\mathbb{N}$，全体实数 $\mathbb{R}$ 等。
  • 全总个体域：由宇宙间一切事物组成的个体域。

谓词

• 谓词：对客体的性质、特征、关系等进行描述的符号。常用大写字母表示，如 $P$ 、 $Q$ 、 $R$ 等。 例如 $A(x)$ 表示 $x$ 满足性质 $A$。
  • 谓词常项：如，$F(a):a$ 是男性。
  • 谓词变项：如，$F(x):x$ 是男性。
  • $n$ 元谓词：含有 $n$ 个变项的谓词。
    • 一元谓词：表示一个客体的性质。
    • 多元谓词：表示多个客体之间的关系。
    • 零元谓词：不含个体变项的谓词，即命题常项或命题变项。

量词

$\forall$ 和 $\exists$ 称为量词。

• 全称量词：$\forall$，表示“对任意”、“对一切”。
• 存在量词：$\exists$，表示“存在”、“至少有一个”。 如 $\forall x P(x)$ 表示“对任意 $x$，$x$ 满足性质 $P$”。

对于 $\forall$ 用 $\to$ 而不是 $\land$ 对于 $\exists$ 用 $\land$ 而不是 $\to$

变元的约束

在公式 $\forall x A$ 和 $\exists x A$ 中，$x$ 称为指导变元，$A$ 为对应量词的 辖域。 在辖域内，$x$ 称为约束出现，$A$ 中不是约束出现的其他变项称为自由出现。 若 $A$ 中没有自由出现的变项，则称 $A$ 为闭式。

公式的解释

若公式在任何解释和该解释下的任何赋值下都为真，则称该公式为永真式。 若公式在任何解释和该解释下的任何赋值下都为假，则称该公式为永假式。 若公式在某个解释和该解释下的某个赋值下为真，则称该公式为可满足式。

一阶逻辑公式是不可判定的，即无法判断一个公式是否永真、永假或可满足。

代换实例

设 $A_0$ 是含命题变项 $p_1, p_2, \ldots, p_n$ 的命题公式，$A_1, A_2, \ldots, A_n$ 是 $n$ 个谓词公式，用 $A_i$ ($1 \leq i \leq n$) 处处代替 $A_0$ 中的 $p_i$，所得公式 $A$ 称为 $A_0$ 的代换实例。

例如，$F(x) \to G(x)$，$\forall x F(x) \to \exists y G(y)$ 等都是 $p \to q$ 的代换实例。

重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。

一阶逻辑的等值演算与推理

基本等值式

命题逻辑的基本等值式

基本等值式 在一阶逻辑中仍然成立，如双重否定律、德摩根律等。需要代换实例。

量词的等值式

消去量词等值式

设 $D = \lbrace a_1, a_2, \ldots, a_n \rbrace$

1. $\forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n)$
2. $\exists x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)$

量词否定等值式

1. $\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$
2. $\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)$

量词辖域收缩与扩张等值式

$A(x)$ 是含 $x$ 的自由出现的公式，$B$ 中不含 $x$ 的自由出现的公式。

• 关于全称量词的：

  • $\forall x (A(x) \land B) \Leftrightarrow \forall x A(x) \land B$
  • $\forall x (A(x) \lor B) \Leftrightarrow \forall x A(x) \lor B$
  • $\textcolor{orange}{\forall x} (A(x) \to B) \Leftrightarrow \textcolor{orange}{\exists x} A(x) \to B$
  • $\forall x (B \to A(x)) \Leftrightarrow B \to \forall x A(x)$

• 关于存在量词的：

  • $\exists x (A(x) \land B) \Leftrightarrow \exists x A(x) \land B$
  • $\exists x (A(x) \lor B) \Leftrightarrow \exists x A(x) \lor B$
  • $\textcolor{orange}{\exists x} (A(x) \to B) \Leftrightarrow \textcolor{orange}{\forall x} A(x) \to B$
  • $\exists x (B \to A(x)) \Leftrightarrow B \to \exists x A(x)$

量词分配等值式

• $\forall x (A(x) \land B(x)) \Leftrightarrow \forall x A(x) \land \forall x B(x)$
• $\exists x (A(x) \lor B(x)) \Leftrightarrow \exists x A(x) \lor \exists x B(x)$
• $\exists x (A(x) \to B(x)) \Leftrightarrow \forall x A(x) \to \exists x B(x)$

形式类似的重演蕴含式

• $\forall x (A(x) \lor B(x)) \Leftarrow \forall x A(x) \lor \forall x B(x)$
• $\exists x (A(x) \land B(x)) \Rightarrow \exists x A(x) \land \exists x B(x)$
• $$\begin{aligned}\exists x A(x) \to \forall x B(x) &\Rightarrow \forall x (A(x) \to B(x)) \newline \Rightarrow \forall x A(x) \to \forall x B(x) &\Rightarrow \exists x A(x) \to \exists x B(x)\end{aligned}$$

置换规则、换名规则、代替规则

置换规则

若 $A \Leftrightarrow B$ 则 $F(A) \Leftrightarrow F(B)$

换名规则

将公式 $A$ 中某量词辖域内的所有约束变元替换为该辖域中未出现的个体变项符号，得到的公式 $A’$ 与 $A$ 等值。

代替规则

设 $A$ 为一公式，将 $A$ 中的某个自由出现的变项用未曾出现在 $A$ 中的个体常项符号代替，得到的公式 $A’$ 与 $A$ 等值。

一阶逻辑前束范式

设 $A$ 为一阶逻辑公式，若 $A$ 的量词部分出现在公式的最前面，则称 $A$ 为前束范式。即 $A$ 可以表示为： $$Q_1 x_1 Q_2 x_2 \cdots Q_n x_n B$$ 其中 $Q_i$ 为量词，$x_i$ 为变项，$B$ 为不含量词的公式。

一阶逻辑中的任何公式都存在与之等值的前束范式

一阶逻辑的推理理论

量词规则

1. US：全称引入规则（Universal Specification） $$\forall x A(x) \Rightarrow A(c)$$
2. UG：全称推广规则（Universal Generalization） $$A(c) \Rightarrow \forall x A(x)$$
3. ES：存在引入规则（Existential Specification） $$A(c) \Rightarrow \exists x A(x)$$
4. EG：存在推广规则（Existential Generalization） $$\exists x A(x) \Rightarrow A(c)$$

自然推理系统

定义5.3 自然推理系统 $N_\mathcal{L}$ 定义如下：

1. 字母表：同一阶语言 $\mathcal{L}$ 的字母表。
2. 合式公式：同 $\mathcal{L}$ 的合式公式。
3. 推理规则： 基本等值式 、 量词规则 。

集合代数

集合的基本概念

集合的定义

由一些个体构成的整体称为集合。称为集合的个体为元素。

集合的表示

• 枚举法：列举出集合中的所有元素。

• 谓词表示法：通过谓词概括集合中的元素。 例如：

• 枚举法：自然数集合：$\mathbb{N} = \lbrace 1, 2, 3, \cdots \rbrace$

• 谓词表示法：偶数集合：$A = \lbrace x | x = 2k, k \in \mathbb{N} \rbrace$

• 集合的树形结构表示：

          A
             /|\
            / | \
           /  |  \
          /   |   \
         /    |    \
      {a, b}{{b}}   d
       /  \   |
      a    b {b}
              |
              b
    

集合的元素具有的性质

• 无序性：集合中的元素之间没有先后次序之分。
• 相异性：集合中的元素各不相同。
• 确定性：一个元素要么属于一个集合，要么不属于一个集合。
• 任意性：集合中的元素可以是任意的，也可以是集合。

元素和集合的关系

$\in$：元素属于集合。 $\notin$：元素不属于集合。

集合与集合的关系

$$A \subseteq B \Leftrightarrow \forall x(x \in A \Rightarrow x \in B)$$ $$A = B \Leftrightarrow A \subseteq B \land B \subseteq A$$ $$A \varsubsetneqq B \Leftrightarrow A \subseteq B \land A \neq B$$ $$A \nsubseteq B \Leftrightarrow \exists x(x\in A \land x \notin B)$$

空集

不包含任何元素的集合称为空集，记作 $\varnothing$ 空集是任何集合的子集，即 $\varnothing \subseteq A$ 空集是唯一的。

全集

包含一切可能元素的集合称为全集，记作 $E$。

全集具有相对性，与讨论的问题有关，不存在绝对的全集。

幂集

$$P(A) = \lbrace x \ | \ x \subseteq A \rbrace$$ 例如：$A = \lbrace a, b \rbrace$，则 $P(A) = \lbrace \varnothing, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace a, b \rbrace \rbrace$

集合的运算

$$\begin{aligned} 并 & & A \cup B &= \lbrace x \ | \ x \in A \lor x \in B \rbrace \newline 交 & & A \cap B &= \lbrace x \ | \ x \in A \land x \in B \rbrace \newline 相对补\ /\ 差 & & A - B &= \lbrace x \ | \ x \in A \land x \notin B \rbrace \newline 绝对补 & & \overline{A} &= ~A = E - A \newline 对称差 & & A \oplus B &= (A - B) \cup (B - A) \newline \newline 广义并 & & \bigcup_{i=1}^n A_i &= \lbrace x \ | \ \exists z(z \in A \land x \in z) \rbrace \newline 广义交 & & \bigcap_{i=1}^n A_i &= \lbrace x \ | \ \forall z(z \in A \to x \in z) \rbrace \newline \end{aligned}$$

1. $\displaystyle \bigcup \varnothing = \varnothing$，$\displaystyle \bigcap \varnothing$ 无意义
2. 广义运算减少集合的层次（括弧减少一层）
3. 广义运算的计算：一般情况下可以转变成初级运算

运算顺序

一类运算：广义并，广义交，幂集，绝对补，运算由右向左进行 二类运算：初级运算 $\cup$，$\cap$，$-$，$\oplus$，运算由左向右进行 混合运算：一类运算优先于二类运算

有穷集合的计数

1. 文氏图法
2. 包含排斥原理（容斥原理） $$\begin{aligned} \left| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n} \right| =& \left| E \right| \newline &- \sum_{i=1}^n \left| A_i \right| \newline &+ \sum_{1 \leq i < j \leq n} \left| A_i \cap A_j \right| \newline &- \cdots \newline &+ (-1)^n \left| A_1 \cap A_2 \cap \cdots \cap A_n \right| \end{aligned}$$ 推论：$n$ 个集合的并的元素个数 $$\begin{aligned} \left| A_1 \cup A_2 \cup \cdots \cup A_n \right| =& \sum_{i=1}^n \left| A_i \right| \newline &- \sum_{1 \leq i < j \leq n} \left| A_i \cap A_j \right| \newline &+ \cdots \newline &+ (-1)^{n-1} \left| A_1 \cap A_2 \cap \cdots \cap A_n \right| \end{aligned}$$

$$\left| A_1 \cup A_2 \cup \cdots \cup A_n \right| = \left|E\right| - \left| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n} \right|$$

集合恒等式

只涉及一个运算符的恒等式

涉及两个不同运算符的恒等式

涉及补运算的恒等式

涉及空集和全集的恒等式

集合等式的证明

命题演算法

例3 证明 $A \cup (A \cap B) = A$ （吸收律）

$$\begin{aligned} \text{证：任取 } x \newline x \in A \cup (A \cap B) \Leftrightarrow &x \in A \lor x \in A \cap B \newline \Leftrightarrow &x \in A \lor (x \in A \land x \in B) \newline \Leftrightarrow &(x \in A \land x \in E) \lor (x \in A \land x \in B) \newline \Leftrightarrow &x \in A \land (x \in E \lor x \in B) \newline \Leftrightarrow &x \in A \newline \text{因此得 } A \cup (A \cap B) = A. \end{aligned}$$

等式置换法

直接运用集合恒等式演算。

二元关系

二元关系的性质

有序对与笛卡尔积

有序对

由两个元素 $x$ 和 $y$，按照一定的顺序组成的二元组称为有序对，记作 $\langle x,y \rangle$.

有序对性质：

• 有序性：$<x,y> \neq \langle y,x \rangle$
• 相等性：$<x,y> = <u,v> \Leftrightarrow x = u \land y = v$

笛卡尔积

$$A \times B = \lbrace <x,y> \ | \ x \in A \land y \in B \rbrace$$

笛卡尔积的性质：

• 不适合交换律：
• 不适合结合律：
• 对于并和交运算满足分配律： $$A \times (B \cup C) = (A \times B) \cup (A \times C)$$ $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$
• $A \times \varnothing = \varnothing \times B = \varnothing$
• $\left|A \times B\right| = \left|A\right| \times \left|B\right|$

二元关系

二元关系的定义

集合 $R$ 称为一个二元关系，当：

• $R$ 是空集
• $R$ 中的所有元素都是有序对 若 $<x,y> \in R$，则称 $x$ 与 $y$ 有关系 $R$，记作 $xRy$. 若 $<x,y> \notin R$，则称 $x$ 与 $y$ 无关系 $R$，记作 $x \cancel{R} y$.

设 $A$ 和 $B$ 是两个集合，$A \times B$ 的任意子集所定义的二元关系称为从 $A$ 到 $B$ 的二元关系. 当 $A = B$ 时，称为 $A$ 上的二元关系.

重要关系的实例

设 $A$ 为集合

• 空关系：$\varnothing$ 是 $A$ 上的关系，称为空关系
• 全域关系：$E_A = \lbrace <x, y> \ | \ x in A \land y \in A \rbrace = A \times A$ 是 $A$ 上的关系，称为全域关系
• 相等关系：$I_A = \lbrace <x, x> \ | \ x \in A \rbrace$ 是 $A$ 上的关系，称为相等关系
• 小于等于关系：$L_A = \lbrace <x, y> \ | \ x, y \in A \land x \leq y \rbrace$ 是 $A$ 上的关系，称为小于等于关系
• 整除关系：$D_A = \lbrace <x, y> \ | \ x, y \in A \land x | y \rbrace$ 是 $A$ 上的关系，称为整除关系
• 包含关系：$R_\subseteq = \lbrace <x, y> \ | \ x, y \in A \land x \subseteq y \rbrace$ 是 $A$ 上的关系，称为包含关系

关系的表示

关系矩阵

$A = \lbrace x_1, x_2, \cdots, x_m \rbrace$，$B = \lbrace y_1, y_2, \cdots, y_n \rbrace$，$R$ 是 $A$ 到 $B$ 的关系，$R$ 的关系矩阵是一个 $m \times n$ 的布尔矩阵 $M_R = [r_{ij}]_{m \times n}$，其中 $$r_{ij} = 1 \Leftrightarrow x_i R y_j$$

关系图

$G_R = (A, R)$，$A$ 是顶点集，$R$ 是边集，$R$ 是 $A$ 到 $A$ 的关系，$G_R$ 是一个有向图.

关系矩阵适合表示从 $A$ 到 $B$ 的关系或 $A$ 上的关系（ $A$，$B$ 为有穷集） 关系图适合表示有穷集 $A$ 上的关系

关系的运算

• 定义域：$\mathrm{dom}R = \lbrace x \ | \ \exists y(xRy) \rbrace$

• 值域：$\mathrm{ran}R = \lbrace y \ | \ \exists x(xRy) \rbrace$

• 域：$fldR = \mathrm{dom}R \cup \mathrm{ran}R$

• 逆运算：$R^{-1} = \lbrace <y, x> \ | \ <x, y> \in R \rbrace$

• 复合运算：$R \circ S = \lbrace <x, z> \ | \ \exists y(xRy \land ySz) \rbrace$

  • $R \circ S \neq S \circ R$

• 幂运算： $$R^n = \begin{cases} {<x, x> \ | \ x \in A} = I_A & n = 0 \newline R \circ R^{n-1} & n > 0 \end{cases}$$

• 限制：$R \upharpoonright A = R \cap (A \times A) = \lbrace <x, y> \ | \ <x, y> \in R \land x \in A \rbrace$

  • $R$ 在 $A$ 上的限制 $R \upharpoonright A$ 是 $R$ 在 $A$ 上的部分，是 $R$ 的子关系，即 $R \upharpoonright A \subseteq R$

• 像：$R[A] = \lbrace y \ | \ \exists x(x \in A \land xRy) \rbrace = \mathrm{ran}(R \upharpoonright A)$

  • A 在 $R$ 下的像 $R[A]$ 是 $\mathrm{ran}R$ 的子集，即 $R[A] \subseteq \mathrm{ran}R$

关系的运算性质

• 逆运算的逆运算：$(F^{-1})^{-1} = F$

• 逆运算的域：$\mathrm{dom}R^{-1} = \mathrm{ran}R, \quad \mathrm{ran}R^{-1} = \mathrm{dom}R$

• 复合运算的逆运算：$(F \circ G)^{-1} = G^{-1} \circ F^{-1}$

• 复合运算的结合律：$(F \circ G) \circ H = F \circ (G \circ H)$

• 复合运算的分配律： $$\begin{aligned} F \circ (G \cup H) = (F \circ G) \cup (F \circ H) & & (G \cup H) \circ F = (G \circ F) \cup (H \circ F) \newline F \circ (G \cap H) \subseteq (F \circ G) \cap (F \circ H)& & F \circ (G \cap H) \supseteq (F \circ G) \cap (F \circ H) \end{aligned}$$ 可以推广到有限个集合的并和交

• 相等关系上的复合运算：$I_A \circ R = R \circ I_A = R$

• 限制与像运算的分配律： $$\begin{aligned} F \upharpoonright (A \cup B) &= F \upharpoonright A \cup F \upharpoonright B & F \upharpoonright (A \cap B) &= F \upharpoonright A \cap F \upharpoonright B \newline F [A \cup B] &= F[A] \cup F[B] & F [A \cap B] &\subseteq F[A] \cap F[B] \end{aligned}$$

幂运算的性质

不同的幂运算只有有限个

$$R^m \circ R^n = R^{m+n}$$ $$(R^m)^n = R^{mn}$$

关系的性质

• 自反性：$R$ 是自反的，当 $\forall x(x \in A \to xRx)$

• 反自反性：$R$ 是反自反的，当 $\forall x(x \in A \to x \cancel{R} x)$

• 对称性：$R$ 是对称的，当 $\forall x \forall y(xRy \to yRx)$

• 反对称性：$R$ 是反对称的，当 $\forall x \forall y(xRy \land yRx \to x = y)$

• 传递性：$R$ 是传递的，当 $\forall x \forall y \forall z(xRy \land yRz \to xRz)$

关系的闭包

关系的闭包

需要改造 $R$ 为一个具有某种性质的关系，$R$ 的闭包是 $A$ 上具有该性质的关系中最小的一个 $R’$。即：

• $R’$ 具有该性质
• $R \subseteq R'$
• 对 $A$ 上任何具有该性质的关系 $S$，$R’ \subseteq S$

$R$ 的自反闭包记作 $r(R) = R \cup R^{0} = R \cup I_A$
$R$ 的对称闭包记作 $s(R) = R \cup R^{-1}$
$R$ 的传递闭包记作 $t(R) = R \cup R^2 \cup R^3 \cup \cdots$

对有穷集 $A(\left|A\right| = n)$，$R$ 的传递闭包 $t(R) = R \cup R^2 \cup \cdots \cup R^n$

矩阵表示

分别设 $R, r(R), s(R), t(R)$ 的关系矩阵为 $M, M_r, M_s, M_t$，则 $$\begin{aligned} M_r &= M + I M_s &= M + M^T M_t &= M + M^2 + M^3 + \cdots + M^n \end{aligned}$$

图表示

• $r(R)$：在 $G_R$ 中添加自环
• $s(R)$：在 $G_R$ 中添加对称边
• $t(R)$：在 $G_R$ 中添加传递边

闭包的性质

$R$ 是自反的 $\Leftrightarrow$ $r(R) = R$
$R$ 是对称的 $\Leftrightarrow$ $s(R) = R$
$R$ 是传递的 $\Leftrightarrow$ $t(R) = R$

若 $R_1 \subseteq R_2$，则
$r(R_1) \subseteq r(R_2)$
$s(R_1) \subseteq s(R_2)$
$t(R_1) \subseteq t(R_2)$

• $r(s(R)) = s(r(R))$
• $r(t(R)) = t(r(R))$
• $s(t(R)) \subseteq t(s(R))$
• $t(s(r(R))) = r(t(s(R))) = t(r(s(R)))$

偏序关系

偏序关系

若 $R$ 是自反的、反对称的、传递的，则称 $R$ 是偏序关系。记作 $\preccurlyeq$。 设 $\preccurlyeq$ 是一个偏序关系，若 $<x, y> \in \preccurlyeq$，则称 $x$ 小于等于 $y$，记作 $x \preccurlyeq y$。

偏序关系的性质

设 $R$ 是 $A$ 上的偏序关系

1. $\forall x, y \in A, x \prec y \Leftrightarrow x \preccurlyeq y \land x \neq y$
2. $\forall x, y \in A, x 与 y \textcolor{orange}{可比} \Leftrightarrow x \preccurlyeq y \lor y \preccurlyeq x$
   • 若 $\forall x, y \in A, x 与 y \textcolor{orange}{可比}$，则称 $R$ 是全序关系
   • 实例：数集上的小于或等于关系是全序关系，整除关系不是正整数集合上的全序关系
3. 若 $x \prec y \land \neg\exists z(x \prec z \prec y)$，则称 $y$ 覆盖 $x$

偏序集

集合 $A$ 与其上的偏序关系 $\preccurlyeq$ 称为偏序集，记作 $\langle A, \preccurlyeq \rangle$ 如：$\langle \mathbb{Z}, \leq \rangle$，$<P(A), \subseteq>, \langle \mathbb{N}, | \rangle$

哈斯图

在 $\langle A, \preccurlyeq \rangle$ ，若 $y$ 覆盖 $x$，则 $y$ 在哈斯图中位于 $x$ 的上方，且用一条从 $x$ 指向 $y$ 的有向边表示。（绘制时忽略箭头）

哈斯图是简化的关系图，是由偏序关系的性质而省略的：

1. 自反性：每个顶点都有自环，故省略自环。
2. 反对称性：从小到大的有向边只有一条，故省略箭头。
3. 传递性：$<a, b>, <b, c> \in R \Rightarrow <a, c> \in R$，故省略 $\langle a, c \rangle$ 的有向边。

特殊元素

最大元、最小元、极大元、极小元

设 $\langle A, \preccurlyeq \rangle$ 是一个偏序集， $B \subseteq A$，$\color{cyan}y \in B$，则

1. 最大元：若 $\forall x(x \in B \to x \preccurlyeq y)$，则称 $y$ 是 $B$ 的最大元
2. 最小元：若 $\forall x(x \in B \to y \preccurlyeq x)$，则称 $y$ 是 $B$ 的最小元
3. 极大元：若 $\forall x(x \in B \to (y \preccurlyeq x \to x = y))$，则称 $y$ 是 $B$ 的极大元
4. 极小元：若 $\forall x(x \in B \to (x \preccurlyeq y \to x = y))$，则称 $y$ 是 $B$ 的极小元

最大元和极小元要求集合中所有元素与其有偏序关系
极大元和极小元仅要求没有比它更大或更小的元素。

最大元和最小元不一定存在，但若存在则唯一。
极大元和极小元一定存在，但不一定唯一。

最大元一定是极大元，最小元一定是极小元。

上界、下界、上确界、下确界

设 $\langle A, \preccurlyeq \rangle$ 是一个偏序集，$B \subseteq A$，$\color{cyan}y \in A$，则

1. 上界：若 $\forall x(x \in B \to x \preccurlyeq y)$，则称 $y$ 是 $B$ 的上界
2. 下界：若 $\forall x(x \in B \to y \preccurlyeq x)$，则称 $y$ 是 $B$ 的下界
3. 上确界：若 $C = \lbrace y \ | \ y \text{ 是 } B \text{ 的上界} \rbrace$，则 $C$ 的最小元称为 $B$ 的上确界或最小上界，记作 $\text{sup}B$
4. 下确界：若 $C = \lbrace y \ | \ y \text{ 是 } B \text{ 的下界} \rbrace$，则 $C$ 的最大元称为 $B$ 的下确界或最大下界，记作 $\text{inf}B$

上下界与最大最小元的区别在于，上下界是在整个偏序集中寻找，而最大最小元是在指定的子集中寻找。

上界和下界不一定存在，若存在也不一定唯一。 上确界和下确界不一定存在，若存在一定唯一。

一个集合的最小元是它的下确界，最大元是它的上确界。反之不一定成立。

等价关系

等价关系与划分

若 $R$ 是自反的、对称的、传递的，则称 $R$ 是等价关系。 设 $R$ 是一个等价关系，若 $xRy$，则称 $x$ 与 $y$ 是等价的，记作 $x \sim y$.

等价类

设 $R$ 是 $A$ 上的等价关系，$x \in A$，则 $$[x]_R = \lbrace y \ | \ y \in A \land xRy \rbrace$$

$$\forall x \in A, [x]_R \neq \varnothing, [x]_R \subseteq A$$ $$\forall x, y \in A, [x]_R \cap [y]_R = \begin{cases} \varnothing & x \nsim y \newline [x]_R & x \sim y \end{cases}$$ $$\bigcup \lbrace [x]_R | x \in A \rbrace = A$$

商集与划分

$$A/R = \lbrace [x]_R \ | \ x \in A \rbrace$$ 实例：$A = \lbrace 1, 2, \cdots 8 \rbrace$，关于模 $3$ 同余的等价关系 $R$ 的商集 $A/R = \lbrace [1]_R, [2]_R, [3]_R \rbrace = \lbrace \lbrace 1, 4, 7 \rbrace, \lbrace 2, 5, 8 \rbrace, \lbrace 3, 6 \rbrace \rbrace$

若 $A$ 的子集族 $\pi(\pi \subseteq P(A))$ 满足

• $\varnothing \notin \pi$
• $\bigcup \pi = A$ 则称 $\pi$ 是 $A$ 的一个覆盖。

若 $A$ 的子集族 $\pi$ 是一个覆盖，且

• $\forall x \forall y(x, y \in \pi land x \neq y \to x \cap y = \varnothing)$ 则称 $\pi$ 是 $A$ 的一个划分，$\pi$ 的元素称为 $A$ 的划分块。

集合 $A$ 上的一个等价关系 $R$ , 决定了 $A$ 的一个划分，该划分就是商集 $A/R$

集合 $A$ 的一个划分,确定 $A$ 的元素间的一个等价关系

函数

函数的定义

设 $F$ 为 二元关系 ，若 $F$ 满足 $\forall x \in \mathrm{dom}F$ 都存在唯一的 $y \in \mathrm{ran}F$ 使 $xFy$ 成立，则称 $F$ 为函数 。 对于函数 $F$，若有 $xFy$，则记作 $y = F(x)$，并称 $y$ 为 $F$ 在 $x$ 处的值

函数相等

$$F = G \Leftrightarrow F \subseteq G \land G \subseteq F \Leftrightarrow \mathrm{dom}F = \mathrm{dom}G \land \forall x (x \in \mathrm{dom}F \to F(x) = G(x))$$

设 $A$ 和 $B$ 是两个集合，$f$ 为函数， $\mathrm{dom}F = A$，$\mathrm{ran}F \subseteq B$，则称 $f$ 为从 $A$ 到 $B$ 的函数，记作 $f: A \to B$ 。

从 $A$ 到 $B$ 的函数的集合

所有从 $A$ 到 $B$ 的函数的集合记作 $B^A$。 $$B^A = \lbrace f \ | \ f: A \to B \rbrace$$ $$\left|B^A\right| = \left|B\right|^{\left|A\right|}$$

特别地： $A = \varnothing$，则 $B^A = B^\varnothing = \lbrace \varnothing \rbrace$ $A \ne \varnothing$ 且 $B = \varnothing$，则 $B^A = \varnothing^A = \varnothing$

函数的像和完全原像

设 $f: A \to B$，$A_1 \subseteq A$，$B_1 \subseteq B$，则

1. $A_1$ 在 $f$ 下的像为 $f(A_1) = \lbrace f(x) \ | \ x \in A_1 \rbrace$
2. $B_1$ 在 $f$ 下的完全原像为 $f^{-1}(B_1) = \lbrace x \ | \ f(x) \in B_1 \rbrace$

像和函数值的区别： $f(x) \in B$，$f(A_1) \subseteq B$

$$\begin{aligned} f^{-1}(f(A_1)) \neq A_1, \quad A_1 \subseteq f^{-1}(f(A_1)) \newline f(f^{-1}(B_1)) \neq B_1, \quad f(f^{-1}(B_1)) \subseteq B_1 \end{aligned}$$ 前者是因为 $f$ 不一定是单射，后者是因为 $f$ 不一定是满射。

函数的性质

• 单射：$\forall x_1, x_2 \in \mathrm{dom}F, F(x_1) = F(x_2) \Leftrightarrow x_1 = x_2$
• 满射：$\mathrm{ran}F = B$
• 双射：若 $f$ 既是单射又是满射，则称 $f$ 为双射的。

某些重要函数

1. 常函数：$f: A \to B$，$\forall x \in A, f(x) = b$，称 $f$ 为常函数。
2. 恒等函数：$I_A = \lbrace <x, x> \ | \ x \in A \rbrace$，$I_A$ 是 $A$ 上的函数，称为恒等函数。
3. 单调函数：$\langle A, \preceq \rangle$ 和 $\langle B, \preceq \rangle$ 是两个偏序集，$f: A \to B$。
   • 若 $\forall x_1, x_2 \in A, x_1 \preceq x_2 \Rightarrow f(x_1) \preceq f(x_2)$，则称 $f$ 为单调递增函数。
   • 若 $\forall x_1, x_2 \in A, x_1 \prec x_2 \Rightarrow f(x_1) \prec f(x_2)$，则称 $f$ 为严格单调递增函数。
   • 类似的，可以定义单调递减函数和严格单调递减函数。
4. 特征函数：$A$ 是集合，对任意的 $A’ \subseteq A$，定义 $f: A \to \lbrace 0, 1 \rbrace$，$f(x) = \begin{cases} 1, & x \in A’ \newline 0, & x \notin A’ \end{cases}$，称 $f$ 为 $A’$ 的特征函数，记为 $\chi_{A’}$。不同的子集对应不同的特征函数。
5. 自然映射：设 $R$ 是集合 $A$ 上的等价关系，$g: A \to A/R$，$g(x) = [x]_R$，称 $g$ 为 $A$ 到 $A/R$ 的自然映射。

不同的等价关系确定不同的自然映射
恒等关系确定的自然映射是双射
其他自然映射一般来说只是满射

函数的运算

复合运算

若 $f$ 和 $g$ 是函数，则 $h = f \circ g$ 也是函数，满足：

1. $\mathrm{dom}h = \lbrace x \ | \ x \in \mathrm{dom}f \land f(x) \in \mathrm{dom}g \rbrace$
2. $\forall x \in \mathrm{dom}h, h(x) = g(f(x))$

复合运算的性质

1. 若 $f: A \to B$ 是单射的，$g: B \to C$ 是单射的，则 $g \circ f: A \to C$ 是单射的。
2. 若 $f: A \to B$ 是满射的，$g: B \to C$ 是满射的，则 $g \circ f: A \to C$ 是满射的。
3. 若 $f: A \to B$ 是双射的，$g: B \to C$ 是双射的，则 $g \circ f: A \to C$ 是双射的。

上述的逆命题都不一定成立。

设 $f: A \to B$，则 $f = f \circ I_B = I_A \circ f$。

反函数

1. 函数 $f$ 的逆 $f^{-1}$ 不一定是函数，只是个二元关系
2. 单射函数的逆是函数，且 $f: A \to B$ 的逆函数 $f^{-1}$ 是 $\mathrm{ran}f$ 到 $A$ 的双射函数。
3. 双射函数 $f: A \to B$ 的逆是在 $B$ 到 $A$ 的双射函数。

对双射函数 $f: A \to B$ $$f^{-1} \circ f = I_A, \quad f \circ f^{-1} = I_B$$

集合的等势

设 $A$ 和 $B$ 是两个集合，若存在双射函数 $f: A \to B$，则称 $A$ 和 $B$ 是等势的，记作 $A \approx B$。

1. $A \approx A$
2. 若 $A \approx B$，则 $B \approx A$
3. 若 $A \approx B$ 且 $B \approx C$，则 $A \approx C$

实例：

• $\mathbb{N} \approx \mathbb{Z} \approx \mathbb{Q} \approx \mathbb{N \times N}$
• $a, b \in \mathbb{R}, a < b$，$(a, b) \approx (a, b] \approx [a, b] \approx [a, b) \approx \mathbb{R}$
  • 以 $[0, 1] \approx (0, 1)$ 为例。
  • $A = {0, 1, 1 / 2, 1 / 3, \cdots} \subset [0, 1]$
  • $B = {1 / 2, 1 / 3, 1 / 4, \cdots} \subset (0, 1)$
  • 关键在于构造双射函数 $f: A \to B$，$f(x) = x / (x + 2)$
• $P(A) \approx \lbrace0, 1\rbrace^A$，$P(A)$ 是 $A$ 的幂集，$\lbrace 0, 1 \rbrace^A$ 是 $A$ 到 $\lbrace 0, 1 \rbrace$ 的函数集合。双射函数为 $f: P(A) \to {0, 1}^A$，$f(A’) = \chi_{A’}$

康托定理

1. $\mathbb{N} \not\approx \mathbb{R}$
2. $A \not \approx P(A)$

证明

1. 定义基数：如果两个集合之间存在双射（双向一一对应），则称这两个集合等势，表示为它们的基数相同。我们希望证明 $\mathbb{N}$ 和 $\mathbb{R}$ 不等势，换句话说，$\mathbb{R}$ 的基数大于 $\mathbb{N}$ 的基数。

2. 假设反证法：假设 $\mathbb{R}$ 和 $\mathbb{N}$ 等势，也就是说，假设存在一个从 $\mathbb{N}$ 到 $\mathbb{R}$ 的双射 $f \colon \mathbb{N} \to \mathbb{R}$。这样，所有实数可以被自然数“列举”出来。

3. 使用康托尔对角线法则：我们接下来将通过对角线法则，展示出在 $\mathbb{R}$ 中总有一个实数无法通过 $f$ 来与自然数一一对应，从而得出矛盾。

   • 考虑单位区间 $[0, 1]$ 中的实数，可以表示为无限小数（例如：0.123456…）。
   • 假设我们能够通过 $f$ 列出这些实数：$f(1), f(2), f(3), \dots$，其中每个 $f(n)$ 都表示 $[0,1]$ 中的一个实数，其小数部分为 $f(n) = 0.a_{n1}a_{n2}a_{n3}\dots$，其中 $a_{ni}$ 表示第 $n$ 个数的第 $i$ 位小数。
   • 现在通过对角线法构造一个新的实数 $r$，使得 $r$ 的第 $i$ 位小数 $b_i$ 与 $f(i)$ 的第 $i$ 位小数 $a_{ii}$ 不同。例如：可以令 $b_i$ 取值为 $9$（若 $a_{ii} \neq 9$），或 $8$（若 $a_{ii} = 9$）。
   • 由于 $r$ 的每一位与对应的 $f(i)$ 在第 $i$ 位不同，因此 $r \neq f(i)$ 对所有 $i$ 都成立。

4. 矛盾产生：这个通过对角线法构造出来的 $r$ 在 $[0, 1]$ 中，但根据假设，$f$ 应该是一个双射，也就是说，应该能够“列举”出所有实数。然而，$r$ 不在这列举出来的实数序列中，这与 $f$ 为双射的假设矛盾。

因此，假设 $\mathbb{N}$ 和 $\mathbb{R}$ 等势是错误的，$\mathbb{R}$ 的基数严格大于 $\mathbb{N}$ 的基数。

集合的优势

设 $A$ 和 $B$ 是两个集合，若存在单射函数 $f: A \to B$，则称 $B$ 优势于 $A$，记作 $A \preccurlyeq\cdot B$。如果 $B$ 不优势于 $A$，则记作 $B \not\preccurlyeq\cdot A$。

设 $A$ 和 $B$ 是两个集合，若 $A \preccurlyeq\cdot B$ 且 $A \not\approx B$，则称 $B$ 真优势于 $A$，记作 $A \prec\cdot B$。如果 $B$ 不真优势于 $A$，则记作 $B \not\prec\cdot A$。

实例：

• $\mathbb{N} \preccurlyeq\cdot \mathbb{N}, \mathbb{N} \preccurlyeq\cdot \mathbb{R}, A \preccurlyeq\ P(A)$
• $\mathbb{R} \not\preccurlyeq\cdot \mathbb{N}$
• $\mathbb{N} \prec\cdot \mathbb{R}, \mathbb{N} \not\prec\cdot \mathbb{N}, A \prec\cdot P(A)$

性质

1. $A \preccurlyeq\cdot A$
2. $A \preccurlyeq\cdot B \land B \preccurlyeq\cdot C \Rightarrow A \preccurlyeq\cdot C$
3. $A \preccurlyeq\cdot B \land B \preccurlyeq\cdot A \Rightarrow A \approx B$

式 3. 可以用于构造两个单射函数证明两个集合等势。

自然数的集合定义

$a^+ = a \cup \lbrace a \rbrace$，称 $a^+$ 为 $a$ 的后继。 $$\begin{aligned} 0 &= \varnothing \newline 1 &= 0^+ = \lbrace 0 \rbrace = \lbrace \varnothing \rbrace \newline 2 &= 1^+ = \lbrace 0, 1 \rbrace = \lbrace \varnothing, \lbrace 0 \rbrace \rbrace \newline 3 &= 2^+ = \lbrace 0, 1, 2 \rbrace = \lbrace \varnothing, \lbrace 0 \rbrace, \lbrace 0, 1 \rbrace \rbrace \newline \cdots \end{aligned}$$

有穷集与无穷集

一个集合是 有穷的 当且仅当它与某个自然数等势。否则，它是 无穷的。 实例：

1. $\lbrace a, b, c \rbrace$ 是有穷集，与 $3 = \lbrace 0, 1, 2 \rbrace$ 等势。
2. $\mathbb{N}$ 和 $\mathbb{R}$ 是无穷集。

任何有穷集只与某个自然数等势，而无穷集与任何自然数都不等势。

集合基数

1. 对于有穷集 $A$，$A$ 的基数是 $\mathrm{card}A = n \Leftrightarrow A \approx n$，称 $n$ 为集合 $A$ 的基数。
2. 自然数集合 $\mathbb{N}$ 的基数是 $\aleph_0$
3. 实数集 $\mathbb{R}$ 的基数是 $\aleph$

集合基数的性质

1. $\mathrm{card}A = \mathrm{card}B \Leftrightarrow A \approx B$
2. $\mathrm{card}A \le \mathrm{card}B \Leftrightarrow A \preccurlyeq\cdot B$
3. $\mathrm{card}A < \mathrm{card}B \Leftrightarrow A \prec\cdot B$

$$\begin{aligned} \mathrm{card}\mathbb{Z} = \mathrm{card}\mathbb{N} &= \mathrm{card}\mathbb{Q} = \mathrm{card}\mathbb{N \times N} = \aleph_0 \newline \mathrm{card}\mathbb{R} = \mathrm{card}[a, b] = \mathrm{card}(c, d) &= \mathrm{card} P(N) = \mathrm{card} 2^\mathbb{N} = \aleph \newline \end{aligned}$$ 有 $\aleph_0 < \aleph$

若 $\mathrm{card}A \le aleph_0$，则称 $A$ 是可数的，否则称 $A$ 是不可数的。

代数系统

二元运算及其性质

一元运算的定义

设 $S$ 为集合，函数 $f: S \to S$ 称为 $S$ 上的一元运算，简称为一元运算。

二元运算的定义

设 $S$ 为集合，函数 $f: S \times S \to S$ 称为 $S$ 上的二元运算，简称为二元运算。

• $S$ 中任意两个元素都可以进行运算，且运算结果唯一。
• 二元运算的运算结果仍然属于 $S$，即运算封闭。

一元运算和二元运算的表示方法

1. 算符：$\oplus, \odot, \cdots$，$x \oplus y, \Delta x, \cdots$
2. 解析公式
3. 运算表

二元运算的性质

单个二元运算的性质

• 交换律：若 $\forall x, y \in S, x \circ y = y \circ x$，则称 $\circ$ 满足交换律。
• 结合律：若 $\forall x, y, z \in S, (x \circ y) \circ z = x \circ (y \circ z)$，则称 $\circ$ 满足结合律。
• 幂等律：若 $\forall x \in S, x \circ x = x$，则称 $\circ$ 满足幂等律。

多个二元运算的性质

• 分配律：若 $\forall x, y, z \in S, x \circ (y \bullet z) = (x \circ y) \bullet (x \circ z) 且 (y \bullet z) \circ x = (y \circ x) \bullet (z \circ x)$，则称 $\circ$ 对 $\bullet$ 满足分配律。
• 吸收律：若 $\forall x, y \in S, x \circ (x \bullet y) = x$，则称 $\circ$ 对 $\bullet$ 满足吸收律。

特异元素

单位元

• 左单位元：若 $\forall x \in S, e_l \circ x = x$，则称 $e_l$ 为 $\circ$ 的左单位元。
• 右单位元：若 $\forall x \in S, x \circ e_r = x$，则称 $e_r$ 为 $\circ$ 的右单位元。
• 单位元：若 $e$ 既是左单位元又是右单位元，则称 $e$ 为 $\circ$ 的单位元，也称为幺元。

零元

• 左零元：若 $\forall x \in S, \theta_l \circ x = \theta_l$，则称 $\theta_l$ 为 $\circ$ 的左零元。
• 右零元：若 $\forall x \in S, x \circ \theta_r = \theta_r$，则称 $\theta_r$ 为 $\circ$ 的右零元。
• 零元：若 $\theta$ 既是左零元又是右零元，则称 $\theta$ 为 $\circ$ 的零元。

逆元

若二元运算存在单位元 $e$：

• 左逆元：若 $\forall x \in S, x \circ x^{-1} = e$，则称 $x^{-1}$ 为 $x$ 的左逆元。

• 右逆元：若 $\forall x \in S, x^{-1} \circ x = e$，则称 $x^{-1}$ 为 $x$ 的右逆元。

• 逆元：若 $x$ 既有左逆元又有右逆元，则称 $x^{-1}$ 为 $x$ 的逆元。

• 可逆的：若 $\forall x \in S, \exists x^{-1} \in S, x \circ x^{-1} = x^{-1} \circ x = e$，则称 $x$ 可逆。

唯一性定理：若 $x$ 有左逆元 $y_l$ 和右逆元 $y_r$，则 $y_l = y_r$，且 $y_l$ 为 $x$ 的逆元。

运算表

运算表与运算性质

• 封闭性：运算表中的元素都在集合中。
• 交换律：运算表关于主对角线对称。
• 幂等性：运算表主对角线上的元素均与表头元素相同。
• 结合律：判断比较复杂，一般通过运算表无法判断。
  • 需要针对运算元素的每种选择进行验证，若 $|A| = n$，一般需要验证 $n^3$ 个等式.

运算表与特异元素

• 有幺元：该元素所对应的行和列依次与运算表的行和列相一致；
• 有零元：该元素所对应的行和列中的元素都与该元素相同；
• 设 $A$ 中有幺元，$a$ 和 $b$ 互逆，当且仅当位于 $a$ 所在行，$b$ 所在列的元素以及 b 所在行，a 所在列的元素都是幺元。

代数系统

非空集合 $S$ 与 $S$ 上的 $k$ 一元或二元运算构成的系统称为代数系统，简称代数。记作：$\langle S, f_1, f_2, \cdots, f_k \rangle$。

代数系统的成分

• 非空集合：$S$，也叫 载体。
• 运算：$S$ 上的一元或二元运算。
• 代数常数：代数系统中的特异元素。

实例： $V_1 = \langle \mathbb{Z},+,0 \rangle$, $V_2 = P(S), \cup, \cap, \varnothing, S$

同类型的代数系统

若两个代数系统中运算的个数以及对应的元数相同，且代数常数的个数也相同，则称这两个代数系统是同类型的。

如 $V_1 = \langle \mathbb{R}, +, \cdot, 0, 1 \rangle$ 和 $V_2 = \langle P(B), \cup, cap, \varnothing, B \rangle$ 是同类型的代数系统。

同类型的代数系统仅仅是具有相同的成分，不一定具有相同的运算性质！

子代数系统

设 $V = \langle S, f_1, f_2, \cdots, f_k \rangle$ 是一个代数系统，若 $S’ \subseteq S$，且 $S’$ 与 $V$ 中的运算在 $S’$ 上封闭，则称 $V’ = \langle S’, f_1, f_2, \cdots, f_k \rangle$ 是 $V$ 的子代数系统，简称子代数。

有时会将子代数系统简记为 $S’$。

特殊的子代数系统

• 最大的子代数：$V$ 本身。
• 最小的子代数：若 $V$ 中所有的代数常数构成的代数系统对 $V$ 中的运算封闭，则该代数系统是 $V$ 的最小子代数。
• 平凡的子代数：最大的子代数和最小的子代数。
• 真子代数：不是 $V$ 本身的子代数。即 $S’ \varsubsetneqq S$。

积代数

设 $V_1 = \langle A, \circ \rangle$ 和 $V_2 = \langle B, \bullet \rangle$ 是同类型的代数系统，在 $A \times B$ 上定义二元运算 $\odot$： $$\forall <a_1, b_1>, <a_2, b_2> \in A \times B, <a_1, b_1> \odot <a_2, b_2> = \langle a_1 \circ a_2, b_1 \bullet b_2 \rangle$$ 称 $V = \langle A \times B, \odot \rangle$ 为 $V_1$ 和 $V_2$ 的积代数，记作 $V = V_1 \times V_2$，此时也称 $V_1$ 和 $V_2$ 是 $V$ 的因子代数。

代数系统的同态与同构

代数系统的同态

$V_1 = \langle A, \circ \rangle$ 和 $V_2 = \langle B, \bullet \rangle$ 是同类型的代数系统，若存在映射 $f: A \to B$，且满足： $$\forall x, y \in A, f(x \circ y) = f(x) \bullet f(y)$$ 则称 $f$ 是 $V_1$ 到 $V_2$ 的同态映射，简称同态。

同态的分类

• 单同态：若 $f$ 是单射，则称 $f$ 是单同态。
• 满同态：若 $f$ 是满射，则称 $f$ 是满同态，此时称 $V_2$ 是 $V_1$ 的同态像。记作 $V_1 \sim V_2$。
• 同构：若 $f$ 是双射，则称 $f$ 是同构映射，$V_1$ 和 $V_2$ 是同构的，记作 $V_1 \cong V_2$。
• 自同态：若 $V_1 = V_2$，则称 $f$ 是 $V_1$ 的自同态。

群与环

群、子群与陪集

群的定义

• 半群：设 $V = \langle S, \circ \rangle$ 是一个代数系统，若 $\circ$ 是可结合的，则称 $V$ 是一个半群。
• 独异点：设 $V = \langle S, \circ \rangle$ 是一个半群，若 $V$ 中存在单位元 $e$，则称 $V$ 是一个含幺半群，也称为独异点。
• 群：设 $V = \langle S, \circ \rangle$ 独异点，若 $V$ 中任意元素 $a$ 都有逆元，则称 $V$ 是一个群，通常将群记作 $G$。

实例：

• $\langle \mathbb{Z}^+, + \rangle$ 是半群
• $\langle \mathbb{N}, + \rangle$ 是含幺半群
• $\langle \mathbb{Z}, + \rangle$ 是群
• Klein 四元群 $G = \lbrace e, a, b, c \rbrace$，满足交换律，每个元素都是自己的逆元，$a, b, c$ 中任意两个元素的运算结果都是第三个元素。

有关群的术语与性质

• 有限群：群 $G$ 是有限集。

• 群的阶：群 $G$ 的 基数 称为 $G$ 的阶，记作 $|G|$。

• 平凡群：只有一个元素的群。（即只含单位元的群）

• 阿贝尔群：满足交换律的群，也称为交换群。

• 元素的幂：设 $a \in G, n \in \mathbb{Z}$，定义 $a^n$ 为：$a^n = \begin{cases} a^{n -1} a & n > 0 \newline e & n = 0 \newline (a^{-1})^n & n < 0 \end{cases}$

• 元素的阶：设 $a \in G$，若存在最小的正整数 $n$ 使得 $a^n = e$，则称 $n$ 为 $a$ 的阶，称 $a$ 为 $n$ 阶元，若不存在这样的 $n$，称 $a$ 为无限阶元。

  • $e$ 是 $\color{cyan}1$ 阶元

幂运算的性质

1. $\forall a \in G, \left(a^{-1}\right)^{-1} = a$
2. $\forall a, b \in G, (ab)^{-1} = b^{-1} a^{-1}$
3. $\forall a \in G, a^n a^m = a^{n + m}$
4. $\forall a \in G, (a^n)^m = a^{nm}$
5. $G 是交换群 \Rightarrow \forall a, b \in G, (ab)^n = a^n b^n$

阶的性质

1. $\forall a \in G, a^k = e \Rightarrow |a| | k$
2. $\forall a \in G, |a| = |a^{-1}|$

• $a, b \in G 且是有限阶元 \left|b^{-1} a b\right| = |a|$

消去律

$a, b, c \in G$

1. $ab = ac \Rightarrow b = c$
2. $ba = ca \Rightarrow b = c$

$$G = {a_1, a_2, \cdots, a_n}, a_iG = \lbrace a_i a_j \ | \ a_j \in G \rbrace = G$$

设群 $G$ 为有限群，则 $G$ 中阶大于 $2$ 的元素有偶数个。

• 若 $a^2 = e$，则 $a = a^{-1}$
• 故 $G$ 中阶大于 $2$ 的元素要成对出现。

$\forall x, b \in G$, 方程 $ax = b$ 和 $ya = b$ 在 $G$ 中存在唯一解。

无零元

若 $G$ 中存在零元 $\theta$，则有 $\forall x \in G, x \theta = \theta x = \theta \neq x$，故 $G$ 中不存在零元。

子群与群的陪集分解

子群

设 $G$ 是一个群，若 $H$ 是 $G$ 的一个非空子集，且 $H$ 对 $G$ 的运算构成一个群，则称 $H$ 是 $G$ 的一个子群，记作 $H \leq G$。 若 $H$ 是 $G$ 的子群，且 $H \neq G$，则称 $H$ 是 $G$ 的真子群，记作 $H < G$。

对任何群 $G$ 都存在子群。$G$ 和 $\lbrace e \rbrace$ 都是 $G$ 的子群，称为 $G$ 的平凡子群。

子群的判定

1. 使用定义验证：
   • $\forall a, b \in H, ab \in H$
   • $\forall a \in H, a^{-1} \in H$
2. $H \neq \varnothing, \forall a, b \in H, ab^{-1} \in H$
3. $H \neq \varnothing$，且 $H$ 是有穷的，$\forall a, b \in H, ab \in H$

生成子群

设 $G$ 是一个群，$a \in G$，令 $H = \lbrace a^k \ | \ k \in \mathbb{Z} \rbrace$，则 $H$ 是 $G$ 的一个子群，称 $H$ 是由 $a$ 生成的子群，记作 $H = \langle a \rangle$。

由子集生成的子群

$B \subseteq G$ $$\langle B \rangle = \bigcap \lbrace H \ | \ B \subseteq H \land H \leq G \rbrace$$

中心

$$C = \lbrace a \in G \ | \ \forall x \in G, ax = xa \rbrace$$ 称 $C$ 为 $G$ 的中心，$C$ 是 $G$ 的一个子群。

子群的并和交

设 $G$ 是一个群，$H_1, H_2$ 是 $G$ 的两个子群，则

1. $H_1 \cap H_2$ 是 $G$ 的子群
2. $H_1 \cup H_2$ 当且仅当 $H_1 \subseteq H_2$ 或 $H_2 \subseteq H_1$ 时是 $G$ 的子群

子群格

$$L(G) = \lbrace H \ | \ H \leq G \rbrace$$ 则偏序集 $\langle L(G), \subseteq \rangle$ 称为 $G$ 的子群格。

子群格

陪集

有 $a \in G, H \leq G$

• $Ha = \lbrace ha \ | \ h \in H \rbrace$ 称为 $H$ 的右陪集
• $aH = \lbrace ah \ | \ h \in H \rbrace$ 称为 $H$ 的左陪集

下面主要讨论右陪集。

$a$ 为 $Ha$ 或 $aH$ 的代表元素。

陪集的性质

1. $H = H$
2. $\forall a \in G, a \in Ha$
3. $a \in Hb \Leftrightarrow ab^{-1} \in H \Leftrightarrow Ha = Hb$

定义等价关系 $R$： $$aRb \Leftrightarrow a \in Hb \Leftrightarrow ab^{-1} \in H$$ $$[a]_R = Ha$$

1. $\forall a, b \in G, Ha = Hb \overline{\lor} Ha \cap Hb = \varnothing$
2. $\bigcup \lbrace Ha \ | \ a \in G \rbrace = G$
3. $H \approx Ha$，即 $|H| = |Ha|$

• 正规子群：若 $H$ 是 $G$ 的子群，且 $\forall a \in G, Ha = aH$，则称 $H$ 是 $G$ 的正规子群，也称 不变子群。

Lagrange 定理

设 $G$ 是一个有限群，$H$ 是 $G$ 的一个子群，有： $$|G| = |H| \cdot [G : H]$$ 其中 $[G : H]$ 称为 $G$ 对 $H$ 的指数，是 $H$ 在 $G$ 中的不同右陪集的个数。

推论

1. 对有限群 $G$，$\forall a \in G, |a| \ \mathbf{\Big|} \ |G|$
2. 对于阶是素数的群，其子群只有平凡子群和本身，即 $\forall a \in G, \langle a \rangle = G$

循环群与置换群

循环群与置换群

循环群

设 $G$ 是一个群，若存在 $a \in G$，使得 $G = \langle a \rangle$，则称 $G$ 是一个循环群，$a$ 称为 $G$ 的生成元。

循环群的性质

任意循环群 $G$ 都是阿贝尔群。反之不一定成立。

循环群的分类

• $n$ 阶循环群：$G = \langle a \rangle$，$|a| = |G| = n$
• 无限循环群：$G = \langle a \rangle$，$|a| = \infty$
  • 若 $G = \langle a \rangle$ 是无限循环群，则 $G$ 只有两个生成元：$a$ 和 $a^{-1}$

若 $G = \langle a \rangle$ 是 $n$ 阶循环群，则 $G$ 含有且仅含有 $\varphi(n)$ 个 $n$ 阶元即生成元。 且 $a^r$ 是 生成元当且仅当 $r$ 与 $n$ 互素。

循环群的子群

设 $G = \langle a \rangle$ 是循环群

1. $G$ 的子群仍是循环群
2. 若 $G$ 是无限循环群，则 $G$ 的子群除了 $\lbrace e \rbrace$ 之外都是无限循环群
3. 若 $G$ 是 $n$ 阶循环群，对 $n$ 的每个正因子 $d$，$G$ 都有且仅有一个 $d$ 阶子群，且 $G$ 的 $d$ 阶子群是 $\langle a^{\frac{n}{d}} \rangle$

置换群

置换

设 $S = {1, 2, \cdots, n}$，$S$ 上的一个任何双射函数 $\delta$ 称为 $S$ 上的一个n 元置换。 $n$ 元置换共有 $n!$ 个。

一个群 $G$ 中的某一行或某一列一定都是 $G$ 的元素的一个置换。

置换的乘法

与函数的复合规则相同。

轮换与对换

• 轮换：若 $\delta(i_1) = i_2, \delta(i_2) = i_3, \cdots, \delta(i_n) = i_1$，则称 $\delta$ 是一个 $n$ 元轮换。
• 对换：若 $\delta(i_1) = i_2, \delta(i_2) = i_1, \delta(i) = i$，则称 $\delta$ 是一个 $2$ 元轮换，即对换。

任意置换都可以唯一地表示成不相交的轮换乘积。

可将该置换表示进一步分解成对换的乘积，且对换分解式中对换之间可以有交，分解式也不惟一.

• 奇置换：含有奇数个对换的置换
• 偶置换：含有偶数个对换的置换

对称群

所有的 $n$ 元置换构成的集合 $S_n$ 关于置换乘法构成群，称为 $n$ 元对称群。 $n$ 元对称群的子群叫做 $n$ 元置换群。

所有的旋转变换是 $S_3$ 的子群 但是所有的翻转变换不是 $S_3$ 的子群

交错群

$n$ 元交错群 $A_n$ 是 $n$ 元对称群 $S_n$ 的一个子群，是 $S_n$ 中所有偶置换构成的集合。

Polya 定理

$N = {1, 2, \cdots, n}$ 是被着色物体的集合，$G$ 是 $N$ 上的一个置换群，$m$ 是着色数，则在 $G$ 作用下的不同的着色方案数为： $$M = \frac{1}{|G|} \sum_{g \in G} m^{c(g)}$$ 其中 $m$ 是着色数，$c(g)$ 是 $g$ 的轮换表示中的轮换个数。

Polya 定理中的置换群求解方法

1. 确定对称操作的类型：

   • 分析物体的对称性，确定所有可能的对称操作（例如旋转、反射等）。
   • 对称操作可以分为不同的类型，如绕不同对称轴的旋转。

2. 求出基本置换：

   • 针对每类对称操作以及其对应的对称轴，求出所有可能的基本置换。
   • 例如，立方体的旋转对称包括绕对称轴旋转90°、180°等。

3. 应用 Polya 定理：

   • 将求出的所有置换作为 Polya 定理中的群元素。
   • 根据定理进行等价类的计数，得出问题的解。

环与域

环与域

环

设 $\langle R, +, \cdot \rangle$ 是一个代数系统，如果满足以下条件：

1. $\langle R, + \rangle$ 是一个阿贝尔群
2. $\langle R, \cdot \rangle$ 是一个半群
3. $\cdot$ 对 $+$ 满足分配律。 则称 $\langle R, +, \cdot \rangle$ 是一个环。

通常称 $+$ 为环 $R$ 的加法，$\cdot$ 为环 $R$ 的乘法。 环中加法单位元 记作 $0$，乘法单位元记作 $1$。

对任何元素 $x$，称其加法逆元为负元，记作 $-x$。 若 $x$ 存在乘法逆元，则称之为逆元，记作 $x^{-1}$。

$nx$ 表示 $n$ 个 $x$ 相加，$x^n$ 表示 $n$ 个 $x$ 相乘。

环的实例

1. 关于普通加法和乘法封闭的环
   • 整数环 $\mathbb{Z}$
   • 有理数环 $\mathbb{Q}$
   • 实数环 $\mathbb{R}$
   • 复数环 $\mathbb{C}$
2. $\oplus$ 和 $\otimes$ 分别表示模 $n$ 加法和乘法的环 $\mathbb{Z}_n$
3. $n$ 阶矩阵环 $M_n(\mathbb{R})$
4. $P(B)$ 对称差和交的环

环的性质

设 $\langle R, +, \cdot \rangle$ 是一个环

1. $\forall a \in R, 0 \cdot a = a \cdot 0 = 0$
2. $\forall a, b \in R, (-a)b = a(-b) = -ab$
3. $\forall a, b, c \in R, a(b - c) = ab - ac, (a - b)c = ac - bc$
4. $\displaystyle\forall a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_m \in R, \sum_{i=1}^n a_i \sum_{j=1}^m b_j = \sum_{i=1}^n \sum_{j=1}^m a_i b_j$

特殊的环

• 交换环：满足乘法交换律的环
• 含幺环：存在乘法单位元的环
• 无零因子环：若 $ab = 0 \Rightarrow a = 0 \lor b = 0$ 的环
  • 当且仅当满足乘法消去律时，环是无零因子环
• 整环：以上三个性质同时满足的环
• 域：设 $R$ 是整环，且 $R$ 中至少含有两个元素，每个非零元都有乘法逆元，则称 $R$ 是一个域。

格与布尔代数

格与布尔代数

设 $\langle S, \preccurlyeq \rangle$ 是一个偏序集，若 $\forall a, b \in S$，存在 上确界和下确界 ，则称 $\langle S, \preccurlyeq \rangle$ 是一个格。

保联与保交

把求 $\lbrace x, y \rbrace$ 的上确界和下确界看作 $x$ 和 $y$ 的二元运算 $\vee$ 和 $\wedge$，称为保联和保交。

通常把在偏序关系的基础上定义的格称为偏序格。

实例

正因子格

$n$ 是正整数，$S_n$ 是 $n$ 的所有正因子的集合，$S_n$ 关于整除关系 $D$ 构格，称为正因子格。

• $x \vee y = \mathrm{lcm}(x, y)$
• $x \wedge y = \gcd(x, y)$

幂集格

$\langle P(B), \subseteq \rangle$ 是一个格，称为幂集格。

• $A \vee B = A \cup B$
• $A \wedge B = A \cap B$

整数集

$\langle \mathbb{Z}, \leq \rangle$ 是一个格。

• $a \vee b = \max(a, b)$
• $a \wedge b = \min(a, b)$

子群格

子群格 是一个格。
$$L(G) = \lbrace H \ | \ H \leq G \rbrace$$

对任意的 $H_1, H_2 \in L(G)$，$H_1 \cap H_2$ 是 $G$ 的子群，$\langle H_1 \cup H_2 \rangle$ 是由 $H_1$ 和 $H_2$ 生成的子群 。（即包含 $H_1$ 和 $H_2$ 的最小子群）。

• $H \vee K = \langle H \cup K \rangle$
• $H \wedge K = H \cap K$

格的性质

对偶原理

设 $f$ 是各种元素以及符号 $=, \preccurlyeq, \succcurlyeq, \vee, \wedge$ 的命题，令 $f^*$ 是 $f$ 的对偶命题，即将 $f$ 中的 $=, \preccurlyeq, \succcurlyeq, \vee, \wedge$ 分别替换为 $\neq, \succcurlyeq, \preccurlyeq, \wedge, \vee$。

若 $f$ 是真，则 $f^*$ 也是真。

计算律

• 交换律：
  • $a \vee b = b \vee a$
  • $a \wedge b = b \wedge a$
• 结合律：
  • $(a \vee b) \vee c = a \vee (b \vee c)$
  • $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
• 幂等律：
  • $a \vee a = a$
  • $a \wedge a = a$
• 吸收律：
  • $a \vee (a \wedge b) = a$
  • $a \wedge (a \vee b) = a$

序与运算的关系

若 $L$ 是一个格，$a, b \in L$，则

• $a \preccurlyeq b \Leftrightarrow a \vee b = b \Leftrightarrow a \wedge b = a$
• $a \succcurlyeq b \Leftrightarrow a \vee b = a \Leftrightarrow a \wedge b = b$

保序：即 $$\forall a, b, c, d \in L, a \preccurlyeq b \land c \preccurlyeq d \Rightarrow a \vee c \preccurlyeq b \vee d 且 a \wedge c \preccurlyeq b \wedge d$$

一般不满足分配律。

子格

设 $\langle L, \wedge, \vee \rangle$ 是一个格，$S$ 是 $L$ 的一个非空子集，若 $S$ 关于 $\wedge$ 和 $\vee$ 构成一个格，则称 $\langle S, \wedge, \vee \rangle$ 是 $\langle L, \wedge, \vee \rangle$ 的一个子格。

分配格

设 $\langle L, \wedge, \vee \rangle$ 是一个格，若 $\forall a, b, c \in L$，满足分配律：

$$\begin{aligned} a \wedge (b \vee c) &= (a \wedge b) \vee (a \wedge c) \newline a \vee (b \wedge c) &= (a \vee b) \wedge (a \vee c) \end{aligned}$$

则称 $\langle L, \wedge, \vee \rangle$ 是一个分配格。

分配格的判定

当且仅当不含与钻石格或五边形格同构的子格。

全上界、全下界

• 若存在 $a \in L$，使得 $\forall x \in L, x \preccurlyeq a$，则称 $a$ 是 $L$ 的一个全上界。
• 若存在 $b \in L$，使得 $\forall x \in L, b \preccurlyeq x$，则称 $b$ 是 $L$ 的一个全下界。

$L$ 中的全上界与全下界即为 $L$ 的 最大元和最小元 。

一般将格 $L$ 的全上界记为 $1$，全下界记为 $0$。 若 $L$ 存在全上界或全下界，则一定是唯一的。

有界格

若 $L$ 存在全上界和全下界，则称 $L$ 是一个有界格。 一般将有界格记为 $\langle L, \wedge, \vee, 0, 1 \rangle$。 $\forall a \in L$，有 $$a \vee 0 = 0, a \vee 1 = 1, a \wedge 0 = 0, a \wedge 1 = 1$$

注意， $\vee$ 和 $\wedge$ 是对偶运算。 $0$ 是 $\wedge$ 的零元，是 $\vee$ 的单位元。 $1$ 是 $\vee$ 的零元，是 $\wedge$ 的单位元。

对于涉及到有界格的命题，如果其中含有全下界 $0$ 或全上界 $1$，在求该命题的对偶命题时，必须将 $0$ 替换成 $1$，而将 $1$ 替换成 $0$。

补元

设 $\langle L, \wedge, \vee, 0, 1 \rangle$ 是一个有界格，若 $\forall a \in L$，存在 $a’$，使得 $$a \wedge a’ = 0, a \vee a’ = 1$$ 则称 $a’$ 是 $a$ 的补元。 $a$ 和 $a’$ 互为补元。

补元是唯一的。 称任何元素都有补元的有界格为有补格。

布尔代数

如果一个格是有补分配格，则称其为布尔代数，记为 $\langle B, \wedge, \vee, ‘, 0, 1 \rangle$。

实例： 正因子格（若每个质因数都只出现一次） 、 幂集格 、 命题代数 、 子群格 。

有限布尔代数

论域 $B$ 为有限集合的布尔代数称为有限布尔代数。 设格 $0 \in L$，$L$ 是格， 若 $\exists a \in L, \forall x \in L, 0 \prec x \preccurlyeq a \Leftrightarrow x = a$ 则称 $a$ 是 $L$ 的原子。

设 $A$ 是 有限布尔代数系统 $B$ 的全体原子构成的集合，则 $B$ 同构于 $A$ 的幂集代数 $P(A)$。

推论：

1. 有限布尔代数的 基数 为 $2^n$。
2. 任何等势的有限布尔代数同构。

图的基本概念

图

基本概念

无向图

无向图 $G = \langle V, E \rangle$，其中：

• $V \neq \varnothing$ 是顶点集，元素称为顶点。
• $E$ 为 $V \And V$ 的多重子集，其元素称为无向边，简称边。
  • 其中 $\And$ 表示无序积，即 $A \And B = \lbrace (a, b) \ | \ a \in A \land b \in B \rbrace$ 实例：$V = \lbrace v_1, v_2, v_3, v_4, v_5 \rbrace$，$E = \lbrace (v_1, v_2), (v_1, v_3), (v_2, v_3), (v_3, v_4), (v_4, v_5) \rbrace$

则 $G = \langle V, E \rangle$ 为一无向图。

有向图

有向图 $D = \langle V, E \rangle$，其中：

• $V \neq \varnothing$ 是顶点集，元素称为顶点。
• $E$ 为 $V \times V$ 的多重子集，其元素称为有向边。

实例：$V = \lbrace v_1, v_2, v_3, v_4, v_5 \rbrace$，$E = \lbrace \langle v_1, v_2 \rangle, \langle v_1, v_3 \rangle, \langle v_2, v_3 \rangle, \langle v_3, v_4 \rangle, \langle v_4, v_5 \rangle \rbrace$

相关概念

• 图
  • 可用 $G$ 泛指图（无向图或有向图）
  • $V(G)$，$E(G)$ 分别表示图 $G$ 的顶点集和边集
  • 用 $e_k$ 表示无向边或有向边
  • 用图形表示图时，如果给每一个顶点和每一条边指定一个符号，则称为标定图，否则称为非标定图。
• $n$ 阶图：$|V(G)| = n$
• $n$ 阶零图：$n$ 个顶点，无边
• 平凡图：即 $1$ 阶零图，只有一个顶点且无边
• 空图：$V(G) = \varnothing$

顶点与边的关联关系

• 无向图：

  • 设 $G = \langle V, E \rangle$，$e_k = (v_i, v_j)$，则称 $e_k$ 与 $v_i$ 和 $v_j$ 相关联，$v_i$ 和 $v_j$ 称为 $e_k$ 的端点。

  • 若 $v_i \neq v_j$，则称 $e_k$ 与 $v_i$ 和 $v_j$ 的关联次数为 $1$。

  • 若 $v_i = v_j$，则称 $e_k$ 与 $v_i$ 的关联次数为 $2$。并称 $e_k$ 为环。

  • 若 $e_k$ 不与 $v_i$ 相关联，则称 $e_k$ 与 $v_i$ 的关联次数为 $0$。

  • 若 $v_i$ 与 $v_j$ 由边 $e_k$ 相关联，则称 $v_i$ 与 $v_j$ 相邻。

  • 若 $e_i$ 与 $e_j$ 有至少一个公共顶点，则称 $e_i$ 与 $e_j$ 相邻。

• 有向图：
  • 设 $D = \langle V, E \rangle$，$e_k = \langle v_i, v_j \rangle$，则称 $e_k$ 与 $v_i$ 和 $v_j$ 相关联。$v_i$ 和 $v_j$ 为 $e_k$ 的端点，$v_i$ 为始点，$v_j$ 为终点。
  • 若 $v_i = v_j$，则称 $e_k$ 为 $D$ 中的环。
  • 若 $v_i$ 和 $v_j$ 由边 $e_k$ 相关联，则称 $v_i$ 与 $v_j$ 相邻。
  • 若 $e_i$ 的终点与 $e_j$ 的始点相同，则称 $e_i$ 与 $e_j$ 相邻。
• 图中没有关联的顶点称为孤立点。

顶点的邻域

• 无向图：
  • 邻域：$N_G(v) = \lbrace u \ | \ u \in V(G) \land \exists e_k = (v, u) \in E(G) \land u \neq v \rbrace$
  • 闭邻域：$\overline{N}_G(v) = N_G(v) \cup \lbrace v \rbrace$
  • 关联集：$I_G(v) = \lbrace e_k \ | \ e_k = (v, u) \in E(G) \rbrace$
• 有向图：
  • 后继元集：$\Gamma_D^+(v) = \lbrace u \ | \ u \in V(D) \land \exists e_k = \langle v, u \rangle \in E(D) \land u \neq v \rbrace$
  • 先驱元集：$\Gamma_D^-(v) = \lbrace u \ | \ u \in V(D) \land \exists e_k = \langle u, v \rangle \in E(D) \land u \neq v \rbrace$
  • 邻域：$N_D = \Gamma_D^+(v) \cup \Gamma_D^-(v)$
  • 闭邻域：$\overline{N}_D(v) = N_D(v) \cup \lbrace v \rbrace$

多重图与简单图

• 平行边：若存在 $e_k = e_0$，则称 $e_k$ 是 平行边。平行边的个数称为重数。
• 多重图：存在平行边的图。
• 简单图：无平行边和环的图。

顶点的度

• 度：$d(v) = |\lbrace e_k \ | \ e_k = (v, u) \in E(G) \lor e_k = \langle v, u \rangle \in E(D) \lor e_k = \langle u, v \rangle \in E(D) \rbrace|$

• 入度：$d^-(v) = |\lbrace e_k \ | \ e_k = \langle u, v \rangle \in E(D) \rbrace|$

• 出度：$d^+(v) = |\lbrace e_k \ | \ e_k = \langle v, u \rangle \in E(D) \rbrace|$

• $d(v) = d^-(v) + d^+(v)$

• $\Delta(G) = max\lbrace d(v) \ | \ v \in V(G) \rbrace$ 称为图 $G$ 的最大度

• $\delta(G) = min\lbrace d(v) \ | \ v \in V(G) \rbrace$ 称为图 $G$ 的最小度

  • 类似的可以定义
  • $\Delta(D)$ 和 $\delta(D)$
  • $\Delta^+(D)$ 和 $\delta^+(D)$
  • $\Delta^-(D)$ 和 $\delta^-(D)$

握手定理

• 无向图 $G = \langle V, E \rangle$，则
  • $\sum_{v \in V} d(v) = 2|E| = 2m$
• 有向图 $D = \langle V, E \rangle$，则
  • $\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = |E| = m$
  • $\sum_{v \in V} d(v) = \sum_{v \in V} (d^+(v) + d^-(v)) = 2m$

推论：奇度顶点的个数为偶数。

度数列

$V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，为无向图 $G$ 的顶点集，称：

• $d(v_1), d(v_2), \cdots, d(v_n)$ 为图 $G$ 的度数列

$V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，为有向图 $D$ 的顶点集，称：

• $d^+(v_1), d^+(v_2), \cdots, d^+(v_n)$ 为图 $D$ 的出度数列
• $d^-(v_1), d^-(v_2), \cdots, d^-(v_n)$ 为图 $D$ 的入度数列
• $d(v_1), d(v_2), \cdots, d(v_n)$ 为图 $D$ 的度数列

对于给定的度数列 $d_1, d_2, \cdots, d_n$，若存在一个 $n$ 阶无向图 $G$，使得 $d(v_1), d(v_2), \cdots, d(v_n)$ 为 $G$ 的度数列，则称 $d$ 是可图化的。

非负整数序列 $d_1, d_2, \cdots, d_n$ 是可图化的当且仅当： $$\sum_{i=1}^{n} d_i = 2 是偶数$$

对任意 $n$ 阶无向简单图 $G$，满足 $\Delta(G) \leq n - 1$ 和 $\delta(G) \geq 0$。

图的同构

若存在双射函数 $f: V_1 \to V_2$，使得对于 $v_i, v_j \in V_1$， $$\begin{aligned} (v_i, v_j) \in E_1 &\Leftrightarrow (f(v_i), f(v_j)) \in E_2 \newline \langle v_i, v_j \rangle \in E_1 &\Leftrightarrow \langle f(v_i), f(v_j) \rangle \in E_2 \end{aligned}$$ 且 $(v_i, v_j)$ 与 $(f(v_i), f(v_j))$ 的重数相同，则称 $G_1$ 与 $G_2$ 同构。 （$\langle v_i, v_j \rangle$ 与 $\langle f(v_i), f(v_j) \rangle$ 的重数相同） 记作 $G_1 \cong G_2$。

图之间的同构关系具有 自反性、对称性和传递性 。 能找到多条同构的必要条件，但它们全不是充分条件；

• 边数相同；
• 顶点数相同；
• 度数列相同；
  判断两个图同构是个难题

图的分类

完全图与竞赛图

• $n$ 阶无向完全图：$K_n = \langle V, E \rangle$，其中 $V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，$E = \lbrace (v_i, v_j) \ | \ 1 \leq i < j \leq n \rbrace$
  • $\displaystyle m = \frac{n(n-1)}{2}$
  • $\Delta = \delta = n - 1$
• $n$ 阶有向完全图：$K_n^d = \langle V, E \rangle$，其中 $V = \lbrace v_1, v_2, \cdots, v_n \rbrace$，$E = \lbrace \langle v_i, v_j \rangle \ | \ 1 \leq i \neq j \leq n \rbrace$
  • $m = n(n-1)$
  • $\Delta = \delta = 2(n-1)$
  • $\Delta^+ = \delta^+ = n - 1$
  • $\Delta^- = \delta^- = n - 1$
• $n$ 阶无向竞赛图：基图为 $K_n$ 的有向简单图。
  • $\displaystyle m = \frac{n(n-1)}{2}$
  • $\Delta = \delta = n - 1$

正则图

设 $G$ 为 $n$ 阶无向简单图，若 $\forall v \in V(G), d(v) = k$，则称 $G$ 为 $k$ - 正则图。 $$m = \frac{kn}{2}$$

子图

$G = \langle V, E \rangle$，$G’ = \langle V’, E’ \rangle$

• 子图：$G’ \subseteq G$，当且仅当 $V’ \subseteq V$ 且 $E’ \subseteq E$，称 $G’$ 为 $G$ 的子图，$G$ 为 $G’$ 的母图。
• 生成子图：$G’ \subseteq G$ 且 $V’ = V$，称 $G’$ 为 $G$ 的生成子图。
• 真子图：$V’ \varsubsetneqq V$ 或 $E’ \varsubsetneqq E$，称 $G’$ 为 $G$ 的真子图。
• 导出子图：
  • $V’ \varsubsetneqq V$ 且 $V’ \neq \varnothing$，以 $G$ 中两个端点都在 $V’$ 中的边组成边集 $E’$，称 $G’ = \langle V’, E’ \rangle$ 为 $G$ 的 $V’$ 导出的子图。记作 $G[V’]$。
  • $E’ \varsubsetneqq E$ 且 $E’ \neq \varnothing$，以 $G$ 中两个端点都在 $E’$ 中的顶点组成顶点集 $V’$，称 $G’ = \langle V’, E’ \rangle$ 为 $G$ 的 $E’$ 导出的子图。记作 $G[E’]$。

补图

$G = \langle V, E \rangle$，$G’ = \langle V, E’ \rangle$，其中 $E’ = \lbrace (v_i, v_j) \ | \ v_i, v_j \in V \land (v_i, v_j) \notin E \land i \neq j \rbrace$，称 $G’$ 为 $G$ 的补图。记作 $\overline{G}$。 即添加上 $G$ 中不在 $K_n$ 中的边。

若 $G \cong \overline{G}$，则称 $G$ 为自补图。

删除与增加边与顶点

• 删除边：$G - e_k = \langle V, E - \lbrace e_k \rbrace \rangle$
• 删除顶点：$G - v_i = \langle V - \lbrace v_i \rbrace, E - \lbrace e_k \ | \ e_k = (v_i, v_j) \in E \lor e_k = \langle v_j, v_i \rangle \in E \rbrace \rangle$
• 边的收缩：从 $G$ 中删除 $e$ 后，将 $e$ 的两个端点合并为一个顶点，得到的图称为 $G$ 的边的收缩。记作 $G \backslash e$。
• 新加边：$G + e_k = \langle V, E \cup \lbrace e_k \rbrace \rangle$

在收缩边和新加边的过程可能会产生平行边和环。

通路与回路

设 $\varGamma$ 为 $G$ 中顶点与边的交替序列，即 $\varGamma = v_0 e_1 v_1 e_2 \cdots e_l v_l$ 称 $\varGamma$ 为 $G$ 中的通路，$v_0, v_l$ 分别称为 $\varGamma$ 的始点和终点，$l$ 称为 $\varGamma$ 的长度。

• 通路与回路：
  • 若 $v_0 = v_l$，则称 $\varGamma$ 为回路。
• 简单通路与简单回路：
  • 所有边互不相同的通路称为简单通路。
  • 所有边互不相同的回路称为简单回路。
• 初级通路（路径）与初级回路（圈）：
  • 顶点互不相同的简单通路称为初级通路。也称为路径。
  • 顶点互不相同的简单回路称为初级回路。也称为圈。
  • 若存在 $v_i$ 到 $v_j$ 的通路，则必定存在长度小于或等于 $n - 1$ 的初级通路。
  • 若存在 $v_i$ 回到自身的回路，则必定存在长度小于或等于 $n$ 的初级回路。
• 复杂通路与复杂回路：
  • 有重复边的通路称为复杂通路。
  • 有重复边的回路称为复杂回路。

环 是长度为 $1$ 的圈。

图的连通性

无向图

• 顶点之间的连通关系：$G = \langle V, E \rangle$ 为无向图
  • 若 $v_i$ 到 $v_j$ 有通路，则 $v_i \sim v_j$
  • $\sim$ 是 $V$ 上的等价关系
  • 定义 $v_i$ 与自身连通
• $G$ 的连通性与连通分支
  • 连通：若 $\forall u, v \in V$，$u \sim v$，则称 $G$ 连通
  • 连通分支：$V/R = {V_1, V_2, \cdots, V_k}$，$V_i$ 为 $G$ 的连通分支，$k = 1$ 时 $G$ 连通。连通分支的个数记为 $p(G)$。

短线程与距离

• 短线程：$v_i$ 到 $v_j$ 的短线程是 $v_i$ 到 $v_j$ 的最短通路
• 距离：$d(u, v)$ 是 $u$ 到 $v$ 的短线程的长度
  • $d(u, v) \ge 0$
  • $u \not\sim v \Rightarrow d(u, v) = \infty$
  • $u = v \Rightarrow d(u, v) = 0$
  • $d(u, v) = d(v, u)$
  • $d(u, v) \le d(u, w) + d(w, v)$

割点与割边

$G = \langle V, E \rangle$ 为无向图，若存在 $V’ \varsubsetneqq V$，使得 $p(G - V’) > p(G)$，且对于任意 $V’’ \varsubsetneqq V$，$p(G - V’’) = p(G)$，则称 $V’$ 为 $G$ 的点割集。 若 $V’ = \lbrace v \rbrace$，则称 $v$ 为 $G$ 的割点。

$G = \langle V, E \rangle$ 为无向图，若存在 $E’ \varsubsetneqq E$，使得 $p(G - E’) > p(G)$，且对于任意 $E’’ \varsubsetneqq E$，$p(G - E’’) = p(G)$，则称 $E’$ 为 $G$ 的边割集。 若 $E’ = \lbrace e \rbrace$，则称 $e$ 为 $G$ 的割边或桥。

连通度

设 $G$ 为无向连通图且不是完全图，则称 $$\kappa(G) = min\lbrace |V’| \ | \ V’ \text{ 是 } G \text{ 的割点集} \rbrace$$ 为 $G$ 的点连通度，简称连通度。简记为 $\kappa$。

• 完全图：$\kappa(K_n) = n - 1$
• 树：$\kappa(T) = 1$
• 非连通图：$\kappa(G) = 0$
• k-连通图：$\kappa(G) \textcolor{cyan}{\ge} k$
  • 删除任意 $k - 1$ 个顶点后，图仍然连通

称 $$\lambda(G) = min\lbrace |E’| \ | \ E’ \text{ 是 } G \text{ 的割边集} \rbrace$$ 为 $G$ 的边连通度。简记为 $\lambda$。

• 完全图：$\lambda(K_n) = n - 1$
• 树：$\lambda(T) = 1$
• 非连通图：$\lambda(G) = 0$
• r-边连通图：$\lambda(G) \textcolor{cyan}{\ge} r$
  • 删除任意 $r - 1$ 条边后，图仍然连通

$$\kappa \le \lambda \le \delta$$

有向图

• 顶点之间的可达关系：$D = \langle V, E \rangle$ 为有向图
  • 若 $v_i$ 到 $v_j$ 有通路，则 $v_i$ 可达 $v_j$，记作 $v_i \to v_j$
  • 若 $v_i \to v_j$ 且 $v_j \to v_i$，则称 $v_i$ 与 $v_j$ 相互可达，记作 $v_i \leftrightarrow v_j$
  • 定义 $v_i$ 可达自身
  • $\leftrightarrow$ 是 $V$ 上的等价关系

短线程与距离

距离记作 $d\langle u, v \rangle$，定义与无向图相同。 类似无向图的定义，只不过无对称性。

连通图

• 弱连通图：$D$ 的基图是连通图，则称 $D$ 为弱连通图，简称连通图。
• 单向连通图：$\forall u, v \in V$，$u \to v$ 或 $v \to u$，则称 $D$ 为单向连通图。
• 强连通图：$\forall u, v \in V$，$u \leftrightarrow v$，则称 $D$ 为强连通图。

强连通 $\Rightarrow$ 单向连通 $\Rightarrow$ 弱连通

• 判定定理：
  • $D$ 单向连通当且仅当 $D$ 中存在经过每个节点至少一次的通路。
  • $D$ 强连通当且仅当 $D$ 中存在经过每个节点至少一次的回路。

图的矩阵表示

关联矩阵

无向图

$(m_{ij})_{n \times m} = v_i \text{ 与 } e_j \text{ 相关联的次数}$ 记作 $M(G) = (m_{ij})_{n \times m}$

有向图

$(m_{ij})_{n \times m} =\begin{cases} 1, & \text{若 } v_i \text{ 为 } e_j \text{ 的始点} \newline -1, & \text{若 } v_i \text{ 为 } e_j \text{ 的终点} \newline 0, & \text{其他} \end{cases}$

邻接矩阵

$(a_{ij})_{n \times n} = v_i \text{ 到 } v_j \text{ 边的条数}$ 记作 $A(D) = (a_{ij})_{n \times n}$

$A^{l}_{ij}$ 表示 $v_i$ 到 $v_j$ 的长度为 $l$ 的通路的条数。

可达矩阵

$(p_{ij})_{n \times n} =\begin{cases} 1, & \text{若 } v_i \text{ 到 } v_j \text{ 可达} \newline 0, & \text{其他} \end{cases}$ 记作 $P(D) = (p_{ij})_{n \times n}$

图的运算

$G_1 = \langle V_1, E_1 \rangle$，$G_2 = \langle V_2, E_2 \rangle$

• 若 $V_1 \cap V_2 = \varnothing$，则称 $G_1$ 和 $G_2$ 是不交的。

• 若 $E_1 \cap E_2 = \varnothing$，则称 $G_1$ 和 $G_2$ 是边不交的或边不重的。

• 并图：

  • 边集：$E_1 \cup E_2$
  • 顶点集：$V_1 \cup V_2$
  • 记作 $G_1 \cup G_2$

• 交图：

  • 边集：$E_1 \cap E_2$
  • 顶点集：$V’ = \lbrace v \ | \ \exists u, (v, u) \in E_1 \cap E_2 \lor \exists u, (u, v) \in E_1 \cap E_2 \rbrace$
  • 记作 $G_1 \cap G_2$

• 差图：

  • 边集：$E_1 - E_2$
  • 顶点集：$V’ = \lbrace v \ | \ \exists u, (v, u) \in E_1 - E_2 \lor \exists u, (u, v) \in E_1 - E_2 \rbrace$
  • 记作 $G_1 - G_2$

• 环和图：

  • 边集：$E_1 \oplus E_2 = (E_1 - E_2) \cup (E_2 - E_1)$
  • 顶点集：$V’ = \lbrace v \ | \ \exists u, (v, u) \in E_1 \oplus E_2 \lor \exists u, (u, v) \in E_1 \oplus E_2 \rbrace$
  • 记作 $G_1 \oplus G_2$

扩大路径法

扩大路径法

$G = \langle V, E \rangle$ 为无向图，且 $E \neq \varnothing$，取一条初始路径 $\varGamma_l$，将该路径外与该路径的始点和终点相邻的顶点加入路径，得到新路径 $\varGamma_{l+1}$，重复该过程，直到无法再加入新的顶点为止。
最后得到的路径为 $\varGamma_{l + k}$，称为极大路径。
使用该方法证明问题的方法称为扩大路径法。

二部图

二部图

$G = \langle V, E \rangle$ 为无向图，若 $V$ 可分为两个互不相交的子集 $V_1$ 和 $V_2$，使得 $E$ 中的每条边的两个端点分别属于 $V_1$ 和 $V_2$，则称 $G$ 为二部图（也称二分图 或 偶图）。
称 $V_1$ 和 $V_2$ 为 $G$ 的互补顶点子集。
常将二部图记作 $G = \langle V_1, V_2, E \rangle$。

完全二部图

$\forall v_1 \in V_1, v_2 \in V_2$，$(v_1, v_2) \in E$，则称 $G$ 为完全二部图。 记为 $K_{r, s}$，其中 $r = |V_1|$，$s = |V_2|$。

二部图的判定

$G$ 为二部图当且仅当 $G$ 中不含奇圈。

欧拉图与哈密顿图

欧拉图

• 欧拉通路：经过图中每条边一次且仅一次的通路称为欧拉通路。
• 欧拉回路：经过图中每条边一次且仅一次的回路称为欧拉回路。
• 欧拉图：包含欧拉回路的图称为欧拉图。
• 半欧拉图：包含欧拉通路但不包含欧拉回路的图称为半欧拉图。

规定 平凡图 是欧拉图。 欧拉通路与欧拉回路是 简单通路与简单回路

判定定理

无向图

无向图 $G$ 是欧拉图的充要条件是 $G$ 是连通的且每个顶点的度数都是偶数。
无向图 $G$ 是半欧拉图的充要条件是 $G$ 是连通的且恰有两个顶点的度数是奇数。

有向图

有向图 $D$ 是欧拉图的充要条件是 $D$ 是强连通的且每个顶点的入度等于出度。
有向图 $D$ 是半欧拉图的充要条件是 $D$ 是强连通的且恰有两个顶点的度数是奇数。

欧拉图的性质

$G$ 是非平凡欧拉图当且仅当 $G$ 是连通的且为若干个边不重的圈的并。

非环非平凡欧拉图 $G$ 满足： $$\lambda(G) \geq 2$$ 即 $G$ 中没有桥。

哈密顿图

• 哈密顿通路：经过图中每个顶点一次且仅一次的通路称为哈密顿通路。
• 哈密顿回路：经过图中每个顶点一次且仅一次的回路称为哈密顿回路。
• 哈密顿图：包含哈密顿回路的图称为哈密顿图。
• 半哈密顿图：包含哈密顿通路但不包含哈密顿回路的图称为半哈密顿图。

规定 平凡图 是哈密顿图。 哈密顿通路与哈密顿回路是 初级通路与初级回路 。

必要条件

设 $G = \langle V, E \rangle$ 是一个哈密顿图，则对于任意 $V_1 \varsubsetneq V$，且 $V_1 \neq \varnothing$，有： $$p(G - V_1) \leq \left|V_1\right|$$ 其中 $p(G)$ 表示 $G$ 的 连通分支数 。

设 $G = \langle V, E \rangle$ 是一个半哈密顿图，则对于任意 $V_1 \varsubsetneq V$，且 $V_1 \neq \varnothing$，有： $$p(G - V_1) \leq \left|V_1\right| + 1$$

充分条件

设 $G$ 是 $n$ 阶无向简单图，若对于任意不相邻的顶点 $v_i, v_j$，有： $$d(v_i) + d(v_j) \geq n - 1$$ 则 $G$ 中存在哈密顿通路。

若： $$d(v_i) + d(v_j) \geq n$$ 则 $G$ 中存在哈密顿回路。

树

树

• 无向树：连通无回路的无向图，简称树。
• 平凡树：平凡图。
• 森林：有若干个不相交的树组成的图。
• 树叶：度为1的节点。
• 分支点：度大于1的节点。

无向树的等价定义

• $G$ 是树（连通无回路）。
• $G$ 中任意两个顶点之间存在惟一的路径。
• $G$ 中无回路且 $m=n-1$.。
• $G$ 是连通的且 $m=n-1$。
• $G$ 是连通的且 $G$ 中任何边均为桥。
• $G$ 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.。

无向树的性质

设 $T$ 是 $n$ 阶非平凡的无向树，则 $T$ 中至少有两片树叶。

平面图

平面图的基本概念

• 平面图：若能将无向图 $G$ 无边相交地画在平面上，称 $G$ 为平面图或可平面图。
• 平面嵌入：画出的无边相交的平面图称为平面嵌入。
• 非平面图：不能画出无边相交的平面图的图称为非平面图。

面与次数

• 面：由 $G$ 的平面嵌入所分割出的区域称为面。
  • 无限面或外部面：无穷大的面。用 $R_0$ 表示。
  • 有限面或内部面：有限大的面。用 $R_1, R_2, \cdots$ 表示。
• 边界：面 $R_i$ 是包围它的边的组成的回路组。
• 次数：面 $R_i$ 的次数是与边界的长度，即边数，记作 $deg(R_i)$。

握手定理

在平面图中，各面的次数之和等于边数的两倍。 $$\sum_{i=1}^{n} deg(R_i) = 2m$$

极大平面图

极大平面图：在平面图 $G$ 中再加一条边，就会使 $G$ 变成非平面图的图称为极大平面图。

极大平面图的性质

极大平面图是连通的，且 $n(n \geq 3)$ 阶极大平面图中不可能有割点和桥。

$G$ 为 $n(n \geq 3)$ 阶极大平面图当且仅当 $G$ 是简单平面图，且 $G$ 的每个面的次数都为 $3$。

极小非平面图

极小非平面图：在非平面图 $G$ 中去掉一条边，就会使 $G$ 变成平面图的图称为极小非平面图。

极小非平面图必为 简单图 。

欧拉公式

设 $G$ 是一个 $n$ 阶 $m$ 条边 $r$ 个面的连通平面图，则 $$n - m + r = 2$$

欧拉公式的推论

若 $G$ 为 $k$ 个连通分支的平面图，则 $$n - m + r = k + 1$$

由 握手定理 可得，对于联通的平面图，有 $$m \leq \frac{l}{l-2}(n-2)$$ $$m \leq \frac{l}{l-2}(n-k-1)$$ 其中 $l = min\lbrace deg(R_i) \rbrace$。

证明： $$2m = \sum_{i=1}^{r} deg(R_i) \geq r \cdot l \geq (n - k - 1) \cdot l$$

根据 握手定理 和 极大平面图的性质 ，可得 设 $G$ 为 $n$ 阶 $m$ 条边的极大平面图，则 $$m = 3n - 6$$

若 $G$ 为 $n(n \geq 3)$ 阶 $m$ 条边的简单平面图，则 $$m \leq 3n - 6$$ 注意，此推论为简单平面图的必要条件，不是充分条件。

设 $G$ 为简单平面图，则 $$\delta(G) \leq 5$$ 用反证法证明。

平面图的判断

插入 $2$ 度顶点与消去 $2$ 度顶点

• 插入 $2$ 度顶点：设 $e = (u, v)$ 为 $G$ 的一条边，$u$ 与 $v$ 之间插入一个顶点 $w$，并将 $e$ 替换为 $(u, w)$ 和 $(w, v)$ 两条边，称作在 $G$ 中插入 $2$ 度顶点 $w$。
• 消去 $2$ 度顶点：设 $w$ 为 $G$ 的一个 $2$ 度顶点，$w$ 与 $u$ 和 $v$ 相连，将 $w$ 与 $u$ 和 $v$ 相连的两条边替换为一条边 $e = (u, v)$，并删除 $w$，称作在 $G$ 中消去 $2$ 度顶点 $w$。

同胚

若 $G_1$ 与 $G_2$ 在反复进行插入 $2$ 度顶点和消去 $2$ 度顶点的操作后 同构 ，则称 $G_1$ 与 $G_2$ 同胚。

平面图判定定理

1. $G$ 是平面图 $\Leftrightarrow$ $G$ 不含同胚于 $K_5$ 或 $K_{3,3}$ 的子图。
2. $G$ 是平面图 $\Leftrightarrow$ $G$ 中无 可 收缩 的 $K_5$ 或 $K_{3,3}$ 子图。

平面图的对偶图

设 $G$ 是某平面图的某个平面嵌入，构造 $G$ 的对偶图如下：

1. $G$ 的每个面 $R_i$ 对应 $G^*$ 的一个顶点 $v_i$。
2. $G$ 的每条边对应 $G^*$ 的一条边。即若 $e$ 是 $R_i$ 和 $R_j$ 的边界，则 $v_i$ 和 $v_j$ 之间有一条边。
   • 若 $e$ 是 $R_i$ 的边界且是桥，即 $e$ 只属于 $R_i$，则 $v_i$ 与自身有一条边。

对偶图的性质

$G^*$ 是 $G$ 的对偶图，则

1. $G^*$ 也是平面图，且是平面嵌入。
2. $G^{*}$ 是连通图。
3. 若 $G$ 是连通图，则 $\left(G^{*}\right)^* \cong G$。
4. $G$ 中的环对应 $G^*$ 中的桥，$G$ 中的桥对应 $G^*$ 中的环。
5. $n^* = r, m^* = m, r^* = n - k + 1$。
6. 设 $G^*$ 中的顶点 $v_i^*$ 位于 $G$ 的面 $R_i$ 的内部，则 $d(v_i^*) = deg(R_i)$。

若 $G^* \cong G$，则称 $G$ 是自对偶图。

轮图

轮图定义如下： 在 $C_{n-1}$（$n \geq 4$）边形内放置一个顶点，使得这个顶点与 $C_{n-1}$ 上的所有顶点均相邻。所得的 $n$ 阶简单图称为 n阶轮图，常记为 $W_n$。

• 当 $n$ 为奇数时，称为 奇阶轮图。
• 当 $n$ 为偶数时，称为 偶阶轮图。

轮图是自对偶图

着色

点着色

• 图的点着色
  图 $G$ 的一种点着色是指：给图 $G$ 的每个顶点涂上一种颜色，使得相邻的顶点具有不同的颜色。

• k着色
  对图 $G$ 进行 $k$ 着色（称 $G$ 是 $k$-可着色的），即能够用 $k$ 种颜色给 $G$ 的顶点着色。

• 图的色数
  图 $G$ 的色数 $\chi(G) = k$，意味着图 $G$ 是 $k$-可着色的，但不是 $(k-1)$-可着色的。即能给图着色的最少颜色数。

色数的上下界

$$\chi(G) \leq \Delta(G) + 1$$
$\chi(K_n) = n$，$\chi(K_{m,n}) = 2$。
$\chi(G) \leq \Delta(G)$，当且仅当 $G$ 不是完全图。（Brooks 定理）
偶圈的色数为 $2$，奇圈的色数为 $3$。
$\chi(W_n) = \begin{cases} 3 & n \text{ 为奇数} \newline 4 & n \text{ 为偶数} \end{cases}$

Welch-Powell 算法

1. 对图的顶点按度数从大到小排序。
2. 从度数最大的顶点开始，给每个顶点涂色，在序列中找到最近且不相邻的顶点的颜色，涂上该颜色。
3. 重复步骤 2，直到所有顶点都被涂色。

在许多实际情况下，Welch-Powell算法的表现非常好，但它不一定会得到图的最小着色数。

地图着色与平面图的点着色

• 地图：联通无桥平面图的平面嵌入与所有的面。
• 国家：地图的面。
• 相邻：两个国家至少有一条公共边。

地图的面着色

• 地图的面着色
  给地图的每个国家涂上一种颜色，使得相邻的国家具有不同的颜色。
• k-面可着色
  能够用 $k$ 种颜色给地图的国家着色。
• 地图的面着色数
  地图的面着色的最少颜色数。记作 $\chi^*(G)$。

地图的面着色转化为对偶图的点着色问题。
地图 $G$ 是 $k$-面可着色的当且仅当对偶图 $G^*$ 是 $k$-可着色的。

四色定理

地图的面着色数 $\chi^*(G) \leq 4$。

边着色

• 图的边着色
  图 $G$ 的一种边着色是指：给图 $G$ 的每条边涂上一种颜色，使得相邻的边具有不同的颜色。
• k-边可着色
  对图 $G$ 进行 $k$ 边着色（称 $G$ 是 $k$-边可着色的），即能够用 $k$ 种颜色给 $G$ 的边着色。
• 图的边着色数
  图 $G$ 的边着色数 $\chi’(G) = k$，意味着图 $G$ 是 $k$-边可着色的，但不是 $(k-1)$-边可着色的。即能给图边着色的最少颜色数。

边着色的上下界

Vizing 定理：对于任意无向简单图 $G$，有 $$\Delta(G) \leq \chi’(G) \leq \Delta(G) + 1$$
$\displaystyle \chi’(K_n) = \begin{cases} n & n \text{ 为奇数} \newline n - 1 & n \text{ 为偶数} \end{cases}$，$\chi’(K_{m,n}) = \Delta$。
$n \ge 4$ 时，$\chi’(W_n) = n - 1$。
偶圈的边着色数为 $2$，奇圈的边着色数为 $3$。