命题逻辑

命题的定义

能判断真假的陈述句叫做命题。

命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题。
这个陈述句对事物的判断是否符合客观事实是可以给出结论的：不是真 (符合客观事实)就是假 (不符合客观事实)不能不真也不假，也不能既真又假，所以又称二值逻辑。
悖论不是命题。

命题的真值

真值只取两个值：真 (判断与事实相符)或假 (判断与事实不符)。通常用 1 (或字母 T)表示真，用 0 (或字母 F)表示假。

命题的分类

简单命题

也称原子命题，指不能再分解为更简单的陈述句的命题。

复杂命题

由若干简单命题用联结词联结成的命题。

联结词

否定联结词 $\neg$。否定联结词是一元联结词。相当于日常用语中的“非”、”不”、“无”、“没有”等。
合取联结词 $\wedge$。合取词是二元联结词。相当于自然语言中的“与”、“并且“、“而且”、“也”等。
析取联结词 $\vee$。析取词是二元联结词。相当于自然语言中的“或”、“要么…要么”等。
蕴含联结词 $\to \gets$。蕴涵词是二元联结词。相当于自然语言中的“若... 则”、“如果... 就”、”只有... 才”。
等价联结词 $\leftrightarrow$。等价联结词是二元联结词。相当于自然语言中的“等价”、“当且仅当”、“充要条件”等。

同时联结词的运算顺序优先级按照上方的由上到下递减。

命题公式

单个命题常项或命题变项 $p, q, r, \ldots, p_{i} q_{p} r_{i}, \ldots$ 是命题公式。
如果 $A$ 是命题公式，则 $\neg A$ 也是命题公式。
如果 $A$ 和 $B$ 是命题公式，则 $A \wedge B$，$A \vee B$，$A \rightarrow B$，$A \leftrightarrow B$ 均是命题公式;
只有有限次地利用 (1)(3)形成的符号串才是命题公式。

公式层数

若 $A$ 是单个命题常项或命题变项, 则称 $A$ 是 $0$ 层公式;
称 $A$ 是 $n+1(n \geq 0)$ 层公式是指 $A$ 符合下列情况之一:
1. $A=\neg B$，$B$ 是 $n$ 层公式。
2. $A=B \wedge C$，其中 $B$、$C$ 分别为 $i$ 层和 $j$ 层公式，且 $n=\max (i, j)$。
3. $A=B \vee C$，其中 $B$、$C$ 分别为 $i$ 层和 $j$ 层公式，且 $n=\max (i, j)$。
4. $A=B \rightarrow C$，其中 $B$、$C$ 分别为 $i$ 层和 $j$ 层公式，且 $n=\max (i, j)$。
5. $A=B \leftrightarrow C$，其中 $B$、$C$ 分别为 $i$ 层和 $j$ 层公式, 且 $n=\max (i, j)$。

赋值

可以使用真值表来计算命题公式的值。

重言式/永真式：若命题公式 $A$ 在所有赋值下都是真的，则称 $A$ 为重言式或永真式。
矛盾式/永假式：$A$ 在所有赋值下都是假的，则称 $A$ 为称为矛盾式或永假式。
可满足式：若 $A$ 至少存在一组成真赋值。

设 $A$ 、 $B$ 是两个命题公式, 若等价式 $A \leftrightarrow B$ 是重言式 , 则称公式 $A$ 与 $B$ 是等价的, 记作 $A \Leftrightarrow B$ 。

公式之间的等价关系的特点：

自反的： $A \Leftrightarrow A$ 。
对称的：若 $A \Leftrightarrow B$ ，则 $B \Leftrightarrow A$ 。
传递的：若 $A \Leftrightarrow B$ ， $B \Leftrightarrow C$ ，则 $A \Leftrightarrow C$ 。

等价公式

常用等价公式：

\[ \begin{array}{ll} \neg(\neg A) \Leftrightarrow A & \text {双重否定律}\\ A \vee A \Leftrightarrow A，A \wedge A \Leftrightarrow A & \text {等幂律}\\ A \vee B \Leftrightarrow B \vee A，A \wedge B \Leftrightarrow B \wedge A & \text {交换律}\\ (A \vee B) \vee C \Leftrightarrow A \vee(B \vee C) & \text {结合律}\\ (A \wedge B) \wedge C \Leftrightarrow A \wedge(B \wedge C)\\ A \vee(B \wedge C) \Leftrightarrow(A \vee B) \wedge(A \vee C) & \text {分配律}\\ A \wedge(B \vee C) \Leftrightarrow(A \wedge B) \vee(A \wedge C)\\ \neg(A \vee B) \Leftrightarrow \neg A \wedge \neg B & \text {德·摩根律}\\ \neg(A \wedge B) \Leftrightarrow \neg A \vee \neg B\\ A \vee(A \wedge B) \Leftrightarrow A & \text {吸收律}\\ A \wedge(A \vee B) \Leftrightarrow A\\ A \vee 1 \Leftrightarrow 1，A \wedge 0 \Leftrightarrow 0 & \text {零律}\\ A \vee 0 \Leftrightarrow A，A \wedge 1 \Leftrightarrow A & \text {同一律}\\ A \vee \neg A \Leftrightarrow 1 & \text {排中律}\\ A \wedge \neg A \Leftrightarrow 0 & \text {矛盾律}\\ A \rightarrow B \Leftrightarrow \neg A \vee B & \text {蕴含等值式}\\ A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \wedge (B \rightarrow A) & \text {等价 (双条件)等值式}\\ A \leftrightarrow B \Leftrightarrow (A \wedge B) \vee (\neg A \wedge \neg B)\\ A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A & \text {假言易位}\\ A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B & \text {等价否定等值式}\\ (A \rightarrow B) \wedge (A \rightarrow \neg B) \Leftrightarrow \neg A & \text {归谬论} \end{array} \]

等价的书写规范？

置换定理

设 $\Phi (A)$ 是含命题公式 $A$ 的命题公式， $\Phi (B)$ 是用命题公式 $B$ 置换了 $\Phi (A)$ 中的 $A$ 之后的得到的命题公式，如果 $A \Leftrightarrow B$ ，则 $\Phi (A) \Leftrightarrow \Phi (B)$ 。

析取范式与合取范式

仅由有限个简单合取式构成的析取式称为析取范式。

仅由有限个简单析取式构成的合取式称为合取范式。

范式存在定理

任一命题公式都存在与之等价的析取范式和合取范式。

主合取范式与主析取范式

极小项与极大项

真值表法

相互转换

真值函数

称定义域为 $\{00 \ldots 0,00 \ldots 1, \ldots, 11 \ldots 1\}$ ，值域为 $\{0,1\}$ 的函数是 $n$ 元真值函数 (其中 $n \geq 1$ )。

常用 $F:\{0,1\}^{n} \rightarrow\{0,1\}$ 表示 $F$ 是 $n$ 元真值函数。

共有 $2^{2^{n}}$ 个 $n$ 元真值函数。

冗余与全功能集

冗余的联结词

在一个联结词的集合中, 如果一个联结词可由集合中的其他联结词定义, 则称此联结词为冗余的联结词, 否则称为独立的联结词。

全功能集

设 $S$ 是一个联结词集合，如果任何真值函数都可以由仅含 S 中的联结词构成的公式表示，则称 $S$ 是联结词全功能集。

若 $S$ 是全功能集，则任何命题公式都可用 $S$ 中的联结词表示。

若 $S_1$ ， $S_2$ 是两个联结词集合，且 $S_1\subseteq S_2$ ，若 $S_1$ 是全功能集，则 $S_2$ 也是全功能集。

若一个联结词的全功能集中不含冗余的联结词，则称它是极小全功能集。

推理

前提：已知的命题公式。

结论：从前提出发应用推理规则推出的命题公式。

推理：从前提推出结论的思维过程。

若 $\left (A_{1} \wedge A_{2} \wedge \ldots \wedge A_{\mathrm{n}}\right) \rightarrow B$ 为重言式, 则称 $A_{1}, A_{2}, \ldots, A_{n}$ 推出结论 $B$ 的推理正确， $B$ 是 $A_{1}, A_{2}, \ldots, A_{n}$ 的逻辑结论或有效结论。称 $\left (A_{1} \wedge A_{2} \wedge \ldots \wedge A_{\mathrm{n}}\right) \rightarrow B$ 为由前提 $A_{1}, A_{2}, \ldots, A_{n}$ 推出结论 $B$ 的推理的形式结构。

用“ $A \Rightarrow B$ ”表示 $A \rightarrow B$ 是重言式，因而若有前提 $A_{1}, A_{2}, \ldots, A_{n}$ 推出结论 $B$ 的推理正确，也记作 $\left (A_{1} \wedge A_{2} \wedge \ldots \wedge A_{\mathrm{n}}\right) \Rightarrow B$ 或：

前提：$A_{1}, A_{2}, \ldots, A_{n}$ 结论：$B$

推理定律

\[ \begin{array}{ll} A \Rightarrow (A \vee B) & \text { 附加律 } \\ (A \wedge B) \Rightarrow A & \text { 化简律 } \\ (A \rightarrow B) \wedge A \Rightarrow B & \text { 假言推理 } \\ (A \rightarrow B) \wedge \neg B \Rightarrow \neg A & \text { 拒取式 } \\ (A \vee B) \wedge \neg B \Rightarrow A & \text { 析取三段论 } \\ (A \rightarrow B) \wedge (B \rightarrow C) \Rightarrow (A \rightarrow C) & \text { 假言三段论 } \\ (A \leftrightarrow B) \wedge (B \leftrightarrow C) \Rightarrow (A \leftrightarrow C) & \text { 等价三段论 } \\ (A \rightarrow B) \wedge (C \rightarrow D) \wedge (A \vee C) \Rightarrow (B \vee D) & \text { 构造性二难 } \\ (A \rightarrow B) \wedge (C \rightarrow D) \wedge (\neg B \vee \neg D) \Rightarrow (\neg A \vee \neg C) & \text { 破坏性二难 } \end{array} \]

推理的书写规范？

推理规则

前提引入规则：在推理过程中，可以随时引入已知的前提。
结论引入规则：在推理过程中，前面已推出的有效结论 (本演绎的中间结论)都可作为后续推理的前提引用。
置换规则：在推理过程中，命题公式中的子公式都可以用与之等价的命题公式置换，得到证明的公式序列的另一公式。

两种特殊证明法

附加前提证明法

欲证明：

前提： $A_{1}, A_{2}, \ldots, A_{k}$ 结论： $C \rightarrow B$

等价地证明：

前提： $A_{1}, A_{2}, \ldots, A_{k}, C$ 结论： $B$

反证法

欲证明：

前提： $A_{1}, A_{2}, \ldots, A_{k}$ 结论： $B$

将 $\neg B$ 加入前提, 若推出矛盾, 则得证推理正确。

谓词逻辑

个体词与谓词

个体词

个体词指可以独立存在的客体，它可以是一个具体的事物，也可以是一个抽象的概念。

谓词

用来刻画个体词的性质或个体词之间关系的词是谓词。

个体常项与个体变项

表示具体的或特定的个体的词称为个体常项，一般用小写英文字母 abc 来表示，表示抽象的或泛指的个体的词称为个体变项，常用小写的英文字母 xyz 表示。个体变项的取值范围称为个体域 (或论域)。特别是，当无特殊声明时，个体域由宇宙间的一切事物组成，称为全总个体域。

谓词常项与谓词变项

表示具体性质或关系的谓词为谓词常项，用大写的英文字母 FGH 表示。表示抽象的或泛指的谓词称为谓词变项，也用大写的英文字母 FGH 表示。

N 元谓词

谓词中包含的个体词数称为元数，含有 $n (n\ge 1)$ 个个体词的谓词称为 n 元谓词。一元谓词是表示个体词性质的。当 $n\ge 2$ 时，n 元谓词表示个体词之间的关系。

0 元谓词

不带个体变项的谓词称为 0 元谓词。

量词

全称量词

对应日常语言中的“一切”，“所有的”，“任意的”等词，用符号 $\forall$ 表示。 $\forall x$ 表示对个体域里的所有个体。$\forall xF (x)$ 表示个体域里的所有个体都有性质 $F$。

存在量词

对应日常语言中的“存在着”，“有一个”，“至少有一个”等词，用符号 $\exists$ 表示。$\exists x$ 表示对个体域里的个体。$\exists xF (x)$ 表示存在着个体域中的个体具有性质 $F$。

特性谓词

若一个谓词 $P (x)$ 是用来限制个体变元的取值范围，那么称谓词 $P (x)$ 为特性谓词。

对全称量词，特性谓词常作蕴含的前件，如 $\forall x (M (x)\to F (x))$

对存在量词，特性谓词常作合取项，如 $\exists x (M (x)\wedge F (x))$

在不同的个体域中, 命题符号化的形式可能不一样。
如果事先没有给出个体域, 都应以全总体域为个体域。
在引入特性谓词后, 使用全称量词和存在量词符号化的形式是不同的。
当个体域为有限集时, 如 $D=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}$，对于任意的谓词 $A (x)$，都有

\[ \begin{array}{l} \forall x A (x) \Leftrightarrow A\left (a_{1}\right) \wedge A\left (a_{2}\right) \wedge \cdots \wedge A\left (a_{n}\right) \\ \exists x A (x) \Leftrightarrow A\left (a_{1}\right) \vee A\left (a_{2}\right) \vee \cdots \vee A\left (a_{n}\right) \end{array} \]

多个量词同时出现时, 不能随意颠倒它们的顺序。

字母表

字母表如下:

个体常项: $a, b, c, \ldots, a_{i}, b_{i}, c_{i}, \ldots, i \geq 1$
个体变项: $x, y, z, \ldots, x_{i}, y_{i}, z_{i}, \ldots, i \geq 1$
函数符号: $f, g, h, \ldots, f_{i}, g_{i}, h_{i}, \ldots, i \geq 1$
谓词符号: $F, G, H, \ldots, F_{i}, G_{i}, H_{i}, \ldots, i \geq 1$
量词符号: $\forall, \exists$
联结词符号: $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$
括号与逗号 : $(, ), ,$

项

个体常项和个体变项是项
若 $\varphi\left (x_{1}, x_{2}, \ldots, x_{n}\right)$ 是任意的 $n$ 元函数， $t_{1}, t_{2}, \ldots, t_{n}$ 是任意的 $n$ 个项，则 $\varphi\left (t_{1}, t_{2}, \ldots, t_{n}\right)$ 是项
只有有限次的使用 (1)、(2)生产的符号才是项

将自然语言转换成谓词公式的步骤

确定个体域，如无特别说明，一般使用全总个体域；
根据个体域，分析命题中的个体、个体性质以及各个个体间的关系，确定谓词；
根据表示数量的词确定量词；
利用联结词将整个命题符号化

原子公式

设 $R (x_1 , x_2 , \cdots, x_n)$ 是任意的 n 元谓词 $(n\ge 1)$，$t_1 , t_2 , \cdots, t_n$ 是任意的 n 个项，则称 $R (t_1 , t_2 , \cdots, t_n )$ 是原子公式。原子公式是由项组成的 n 元谓词。

合式公式

原子公式是合式公式
若 $A$ 是合式公式，则 ($\neg A$)也是合式公式
若 $A, B$ 是合式公式，则 $(A\wedge B), (A\vee B), (A\to B), (A\leftrightarrow B)$ 也是合式公式
若 $A$ 是合式公式，则 $\exists xA,\forall xA$ 也是合式公式
只有有限次地应用 (1)~(4)构成的符号串才是合式公式。在谓词逻辑中合式公式又称为谓词公式，简称为公式。

在公式 $\forall xA$ 和 $\exists xA$ 中，称 x 为指导变项，A 为相应量词的辖域。在 $\forall x$ 和 $\exists x$ 的辖域中，x 的所有出现都称为约束出现，A 中不是约束出现的其他变项的出现均称为是自由出现。

若公式 A 中无自由出现的个体变项，则称 A 是封闭的合式公式，简称闭式。

换名规则

将一个指导变项及其在辖域中所有约束出现替换成公式中没有出现的个体变项符号。

改名只对约束出现的变元进行，不对自由出现的变元进行。
改名必须处处进行，即对某量词约束的变元改名时，必须对原式中该变元的一切受该量词约束的约束进行改名。
对受某量词约束的变元改名时新名决不能与该量词的辖域中的其它自由变元同名。
改名前与改名后的约束关系保存不变。

解释

一个解释 $I$ 由下面四部分组成： 1. 非空个体域 $D$。 2. 对每一个个体常项符号指定一个 $D$ 中的元素。 3. 对每一个函数变项符号指定一个 $D$ 上的函数。 4. 对每一个谓词变项符号指定一个 $D$ 上的谓词。

值得说明的是：

将公式的个体常项用 $I$ 的特定常项代替，函数和谓词用 $I$ 的特定函数和谓词代替。
被解释的公式不一定全部包含解释中的 4 部分。
闭式在任何解释下都是命题。
不是闭式的公式在某些解释下也可能是命题。

对于谓词公式来说：

永真式 (逻辑有效式)：A 在任何解释和该解释下的任何赋值下都为真
矛盾式 (永假式)：A 在任何解释和该解释下的任何赋值下都为假
可满足式：若至少存在一个解释和该解释下的一个赋值使 A 为真

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

设 $A, B$ 是谓词逻辑中的两公式，若 $A\leftrightarrow B$ 为逻辑有效式，则称 $A$ 与 $B$ 是等值的，记作 $A\Leftrightarrow B$ ，并称 $A\Leftrightarrow B$ 为等值式。

量词否定等值式

设 $A (x)$ 是含 $x$ 自由出现的公式

$\neg \forall x A (x) \Leftrightarrow \exists x \neg A (x)$
$\neg \exists x A (x) \Leftrightarrow \forall x \neg A (x)$

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

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

关于全称量词

$\forall x (A (x) \vee B) \Leftrightarrow \forall x A (x) \vee B$
$\forall x (A (x) \wedge B) \Leftrightarrow \forall x A (x) \wedge B$
$\forall x (A (x) \rightarrow B) \Leftrightarrow \exists x A (x) \rightarrow B$
$\forall x (B \rightarrow A (x)) \Leftrightarrow B \rightarrow \forall x A (x)$

关于存在量词

$\exists x (A (x) \vee B) \Leftrightarrow \exists x A (x) \vee B$
$\exists x (A (x) \wedge B) \Leftrightarrow \exists x A (x) \wedge B$
$\exists x (A (x) \rightarrow B) \Leftrightarrow \forall x A (x) \rightarrow B$
$\exists x (B \rightarrow A (x)) \Leftrightarrow B \rightarrow \exists x A (x)$

量词分配等值式

$\forall x (A (x) \wedge B (x)) \Leftrightarrow \forall x A (x) \wedge \forall x B (x)$
$\exists x (A (x) \vee B (x)) \Leftrightarrow \exists x A (x) \vee \exists x B (x)$

注意：$\forall$ 对 $\vee$ 无分配律，$\exists$ 对 $\wedge$ 无分配律，即：

$\forall x (A (x) \vee B (x)) \nLeftrightarrow \forall x A (x) \vee \forall x B (x)$
$\exists x (A (x) \wedge B (x)) \nLeftrightarrow \exists x A (x) \wedge \exists x B (x)$

下面两等值式成立:

$\forall x \forall y A (x, y) \Leftrightarrow \forall y \forall x A (x, y)$
$\exists x \exists y A (x, y) \Leftrightarrow \exists y \exists x A (x, y)$

其中 $A (x, y)$ 是任意的含 $x, y$ 自由出现的谓词公式。

前束范式

设 $A$ 为一谓词公式，若 $A$ 具有如下形式：

\[ Q_{1} x_{1} Q_{2} x_{2} \ldots Q_{k} x_{k} B \text {, } \]

则称 $A$ 为前束范式，其中每个 $Q_{i}(1 \leq i \leq k)$ 为 $\forall$ 或 $\exists$，$B$ 为不含量词的谓词公式。

谓词公式化为前束范式的步骤

消去联结词 $\rightarrow, \leftrightarrow$ 及多余的量词。
否定深入。
改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。
量词前移。即利用量词辖域的收缩与扩张把量词移到前面，这样便可求出与公式等价的前束范式。

集合

概念

集合就是一些事物构成的整体，且任一事物是否属于一个集合是完全确定的：要么属于，要么不属于，没有模糊空间。

集合的表示

列举法（花名册法 roster）；谓词表示法（集合构造器 set builder）

符号	含义	元素
$\varnothing$	空集	不包含任何元素的集合
$\mathbb{N}$	自然数集	$\{0,1,2,3,\ldots\}$
$\mathbb{Z}$	整数集	$\{\ldots,-3,-2,-1,0,1,2,3, \ldots\}$
$\mathbb{Z}^{+}$	正整数集	$\{1,2,3, \ldots\}$
$\mathbb{Q}$	有理数集	$\{\frac{p}{q}\mid p, q \in \mathbb{Z}, q \neq 0\}$
$\mathbb{R}$	实数集	所有实数构成的集合
$\mathbb{C}$	复数集	所有复数构成的集合

集合中元素的三个特性

确定性：某一元素是否属于一个集合是完全确定的互异性：同一集合中的元素是互相不同的无序性：构成集合的各元素地位等同，无先后次序

集合之间的关系

\[ \begin{array}{ll} \text { 包含 (子集) } & A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B) \\ \text { 不包含 } & A \nsubseteq B \Leftrightarrow \exists x (x \in A \wedge x \notin B) \\ \text { 相等 } & A=B \Leftrightarrow A \subseteq B \wedge B \subseteq A \\ \text { 不相等 } & A \neq B \\ \text { 真包含 (真子集) } & A \subset B \Leftrightarrow A \subseteq B \wedge A \neq B \\ \text { 不真包含 } & A ⊄ B \end{array} \]

空集 $\varnothing$：不含任何元素的集合

集合的大小

对于有限集 $S$，如果 $S$ 中恰有 n 个不同的元素，则称 n 是 $S$ 的基数。$S$ 的基数记为 $|S|$。如果 $|S|=n$，则称 $S$ 是 n 元集，它的含有 m 个 $(m\le n)$ 元素的子集称作它的 m 元子集。如果集合不是有限集，则称它是无限的。

幂集（Power Set）

集合 $S$ 的幂集是集合 $S$ 所有子集的集合，记作 $P (S)$。

\[ P (S)=\{x | x \subseteq S\} \]

集合包含关系的性质

对任意集合 $A$，$\varnothing \subseteq A$。
自反性：$A \subseteq A$。
反对称性：若 $A \subseteq B$ 且 $B \subseteq A$, 则 $A=B$。
传递性: 若 $A \subseteq B$ 且 $B \subseteq C$, 则 $A \subseteq C$。
若 $|\boldsymbol{A}|=n$, 则 $\boldsymbol{A}$ 有 $2^{n}$ 个子集。

集合的运算

并集：$A \cup B=\{x / x \in A \vee x \in B\}$ 交集：$A \cap B=\{x / x \in A \wedge x \in B\}$ 相对补集：$A-B=\{x \mid x \in A \wedge x \notin B\}$ 对称差：$A \oplus B=(A-B) \cup (B-A)$

全集

在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作 E（或 U）. 全集具有相对性在给定问题中，全集包含任何集合，即 $\forall A (A\subseteq E)$

集合中的元素不重复出现，当允许元素重复出现时称作多重集。

设 A 与 B 为两集合, 称 $\{\{a, b\} \mid a \in A \wedge b \in B\}$ 为 A 与 B 的无序积。记作 $A \& B$ 。为方便起见, 将无序对 $ {a, b}$ 记为 $(a, b)$ .

集合运算法则

\[ \begin{array}{ll} \text {幂等律} & A \cup A=A \\ \text {交换律} & A \cap A=A \\ & A \cup B=B \cup A \\ & A \cap B=B \cap A \\ \text {结合律} & (A \cup B) \cup C=A \cup (B \cup C) \\ & (A \cap B) \cap C=A \cap (B \cap C) \\ \text {分配律} & A \cup (B \cap C)=(A \cup B) \cap (A \cup C) \\ & A \cap (B \cup C)=(A \cap B) \cup (A \cap C) \\ \text {恒等律} & A \cup \varnothing=A \\ & A \cap E=A \\ \text {支配律} & A \cup E=E \\ \text {互补律} & A \cap \varnothing=\varnothing \\ & A \cup \bar{A}=E \\ & A \cap \bar{A}=\varnothing \\ \text {吸收律} & A \cup (A \cap B)=A \\ & A \cap (A \cup B)=A \\ \text {双重否定律} & \overline{(\bar{A})}=A \\ \end{array} \]

德·摩根 (De Morgen)对偶原理

效果：将关于集合的某种性质转移到它的补集上去。

绝对补集情况：

\[ \begin{array}{l} \overline{\boldsymbol{B} \cup C}=\overline{\boldsymbol{B}} \cap \bar{C} \\ \overline{\boldsymbol{B} \cap C}=\overline{\boldsymbol{B}} \cup \overline{\boldsymbol{C}} \end{array} \]

相对补集情况：

\[ \begin{array}{l} A-(B \cup C)=(A-B) \cap (A-C) \\ A-(B \cap C)=(A-B) \cup (A-C) \end{array} \]

对称差运算法则

\[ \begin{array}{l} A \oplus A=\varnothing \quad A \oplus \varnothing=A \\ A \oplus E=\bar{A} \quad A \oplus B=B \oplus A \\ A \oplus B=(A \cup B) \cap (\bar{A} \cup \bar{B}) \\ A \oplus B=(A \cap \bar{B}) \cup (B \cap \bar{A}) \\ A \cup B=(A \oplus B) \cup (A \cap B) \\ (A \oplus B) \oplus C=A \oplus (B \oplus C) \\ A \cap (B \oplus C)=(A \cap B) \oplus (A \cap C) \\ \text { iff } A \oplus B=A \oplus C \text {, then } B=C\\ A \oplus B=(A-B) \cup (B-A) \\ A \oplus B=(A \cup B)-(A \cap B) \\ A-B=A \cap \bar{B} \end{array} \]

包含排斥原理

设 $S$ 为有限集，$P_{1}, P_{2}, \ldots, P_{m}$ 是 $m$ 种性质，$A_{i}$ 是 $S$ 中具有性质 $P_{i}$ 的元素构成的子集，$i=1,2, \ldots, m$，则 $S$ 中不具有性质 $P_{1}, P_{2}, \ldots, P_{m}$ 的元素数为：

\[ \begin{array}{l} \left|\overline{A_{1}} \cap \overline{A_{2}} \cap \ldots \cap \overline{A_{m}}\right| \\ =|S|-\sum_{i=1}^{m}\left|A_{i}\right|+\sum_{1 \leq i<j \leq m}\left|A_{i} \cap A_{j}\right|-\sum_{1 \leq i<j<k \leq m}\left|A_{i} \cap A_{j} \cap A_{k}\right|+\ldots \\ +(-1)^{m}\left|A_{1} \cap A_{2} \cap \ldots \cap A_{m}\right| \end{array} \]

证明要点：任何元素 $x$，如果不具有任何性质，则对等式右边计数贡献为 1，否则为 0。

推论：$S$ 中至少具有一条性质的元素数为：

\[ \begin{array}{l} \left|A_{1} \cup A_{2} \cup \ldots \cup A_{m}\right| \\ =\sum_{i=1}^{m}\left|A_{i}\right|-\sum_{1 \leq i<j \leq m}\left|A_{i} \cap A_{j}\right|+\sum_{1 \leq i<j<k \leq m}\left|A_{i} \cap A_{j} \cap A_{k}\right|+\ldots \\ +(-1)^{m-1}\left|A_{1} \cap A_{2} \cap \ldots \cap A_{m}\right| \end{array} \]

加法法则

如果事件 $A$ 有 $p$ 种产生的方式，事件 $B$ 有 $q$ 种产生的方式，则事件“A 或 B”有 $p+q$ 种产生的方式。

乘法法则

如果事件 $A$ 有 $p$ 种产生的方式，事件 $B$ 有 $q$ 种产生的方式，则事件“A 与 B”有 $pq$ 种产生的方式。

排列与组合

排列问题：从某个集合中有序地选取若干个元素的问题

组合问题：从某个集合中无序地选取若干个元素的问题

这类问题可以根据是否有序、是否允许重复，而划分成 4 种： 1. 不允许重复的有序选取：集合的排列 2. 允许重复的有序选取：多重集的排列 3. 不允许重复的无序选取：集合的组合 4. 允许重复的无序选取：多重集的组合

排列

从 $n$ 个元素的集合 $S$ 中有序选取的 $r$ 个元素叫做 $S$ 的一个 $r$ 排列，不同的排列总数记作 $P_{n}^{r}$ (或 $P (n, r)$)。如果 $r=n$，则称这个排列为 $S$ 的全排列, 简称 $S$ 的排列。

当 $r>n$ 时，$P_{n}^{r}=0$。

对满足 $r \leq n$ 的正整数 $n$ 和 $r$ 有：

\[ P_{n}^{r}=n (n-1) \cdots (n-r+1) \]

一个 $n$ 元素 $S$ 的环形 $r$ 排列数是：

\[ \frac{P_{n}^{r}}{r}=\frac{n !}{r (n-r) !^{\circ}} \]

如果 $r=n$，则 $S$ 的环排列数是 $(n-1)!$。

从 $n$ 元集 $S$ 中无序选取的 $r$ 个元素叫做 $S$ 的一个 $r$ 组合，不同组合总数记作 $C_{n}^{r}\left (C (n, r)\right.$ 或 $\left.\left (\begin{array}{c}r \\ n\end{array}\right)\right.)$。当 $n \geq 0$ 时，规定 $C_{n}^{0}=1$。当 $r>n$ 时，$C_{n}^{r}=0$。

对一切 $r \leq n$，有 $P_{n}^{r}=r ! C_{n}^{r}$，即 $C_{n}^{r}=\frac{n !}{r !(n-r) !}$。

\[ \forall r \leq n \text {, 有 } C_{n}^{r}=C_{n}^{n-r} \]

设 $S$ 为 $n$ 元集, 则 $S$ 的子集总数是：

\[ 2^{n}=C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n} \]

设多重集 $S=\left\{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \cdots, n_{k} \cdot a_{k}\right\}$，从 $S$ 中有序选取的 $r$ 个元素叫做 $S$ 的一个 $r$ 排列，当 $r=n$ 时，$n=n_{1}+n_{2}+\cdots+n_{k}$，也叫做 $S$ 的一个排列。

设多重集 $S=\left\{\infty \cdot a_{1}, \infty \cdot a_{2}, \cdots, \infty \cdot a_{k}\right\}$，则 $S$ 的 $r$ 排列数是 $k^{r}$。

推论：设多重集 $S=\left\{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \cdots, n_{k} \cdot a_{k}\right\}$，并且对一切 $i=1,2, \cdots, k$ 有 $n_{i} \geq r$，则 $S$ 的 $r$ 排列数是 $k^{r}$。

设多重集 $S=\left\{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \cdots, n_{k} \cdot a_{k}\right\}$，且 $n=n_{1}+ n_{2}+\cdots+n_{k}$，则 $S$ 的排列数等于 $\frac{n !}{n_{1} ! N_{2} ! \cdots n_{k} !}$。简记为 $\left (\begin{array}{c}n \\ n_{1} n_{2} \cdots n_{k}\end{array}\right)$。

设多重集 $S=\left\{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \cdots, n_{k} \cdot a_{k}\right\}$，$S$ 的含有 $r$ 个元素的子多重集叫做 $S$ 的 $r$ 组合。

设多重集 $S=\left\{\infty \cdot a_{1}, \infty \cdot a_{2}, \cdots, \infty \cdot a_{k}\right\}$，则 $S$ 的 $r$ 组合数是 $C_{k+r-1}^{r}$。

推论 1：设多重集 $S=\left\{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \cdots, n_{k} \cdot a_{k}\right\}$，且对一切 $i=1,2, \cdots, k$ 有 $n_{i} \geq r$，则 $S$ 的 $r$ 组合数是 $C_{k+r-1}^{r}$。

推论 2：设多重集 $S=\left\{\infty \cdot a_{1}, \infty \cdot a_{2}, \cdots, \infty \cdot a_{k}\right\}, r \geq k$，则 $S$ 中每个元素至少取一个的 $r$ 组合数是 $C_{r-1}^{k-1}$。

设 $S=\left\{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \cdots, n_{k} \cdot a_{k}\right\}$，$n=n_{1}+n_{2}+\cdots+n_{k}$，则 $S$ 的 $r$ 组合数 $N$ 满足：

若 $r>n$，则 $N=0$。
若 $r=n$，则 $N=1$。
若 $r<n$，且对一切 $i=1,2, \cdots, k$ 有 $n_{i} \geq r$，则 $N=C_{k+r-1}^{r}$。
若 $r<n$，且存在着某个 $n_{i}<r$，则对 $N$ 没有一般的求解公式，可以用包含排斥原理或其他的组合数学方法求解。

映射

设 $A$ 与 $B$ 是两个非空集合。如果按照一定的法则 $f$，对于 $A$ 中的每个元素 $x$，都存在 $B$ 中的一个确定的元素 $y$ 与 $x$ 相对应，那么称 $f$ 是定义在 $A$ 上取值于 $B$ 中的一个映射，记作 $f: A→B$，$y$ 称为 $x$ 在映射 $f$ 下的象，记作 $y = f (x)$。对于固定的 $y$，$A$ 中适合关系式 $y = f (x)$ 的 $x$ 的全体称为 $y$ 的原象，$A$ 称为映射 $f$ 的定义域，$f (A)=\{f (x) | x\in A\}$ 称为映射 $f$ 的值域。

若 $B$ 是一个数集，此时映射 $f$ 称为泛函，即定义在集 $A$ 上的函数；若 $A$ 与 $B$ 都是数集，$f$ 就是通常的函数。

设 $X$ 为任一集合，$A$ 是 $X$ 的一个子集，定义

\[ \chi_{A}(x)=\left\{\begin{array}{ll} 0, & x \notin A \\ 1, & x \in A \end{array}\right. \]

则映射 $\chi_{A}: X \rightarrow\{0,1\}$ 是集合 $X$ 上的一个函数，称为 $A$ 的特征函数。

设有映射 $f: A \rightarrow B$。若 $f (A)=B$，即对 $B$ 中的每个元素 $y$ 都有 $A$ 中的元素 $x$，使 $f (x)=y$，则称 $f$ 是一个满射，或 $A$ 到 $B$ 上的映射；若对于 $f (A)$ 中的每个元 $y$，都有 $A$ 中的唯一的元 $x$，使 $f (x)=y$，或者等价地，对于 $A$ 中的任意不同元 $x_{1}$ 与 $x_{2}$，都有 $f\left (x_{1}\right) \neq f\left (x_{2}\right)$，则称 $f$ 是一个单射；若 $f$ 既是满射，又是单射，即对于 $B$ 中的每个元 $y$，都有 $A$ 中的唯一元 $x$，使 $f (x)=y$，则称 $f$ 是一个双射或 $A$ 到 $B$ 上的一一映射。

设 $A$ 与 $B$ 是两个非空集合，若存在一个从 $A$ 到 $B$ 上的一一映射，则称集合 $A$ 与 $B$ 是对等的，或称 $A$ 与 $B$ 是一一对应的，记作 $A\sim B$。

设 $A$ 与 $B$ 是两个集合，如果 $A \sim B$，那么就称 $A$ 与 $B$ 具有相同的势。集合 $A$ 的势记为 $\overset{=}{A}$。

对等关系具有下述基本性质：

自反性：$A \sim A$。
对称性：若 $A \sim B$，则 $B \sim A$。
传递性：若 $A \sim B$，$B \sim C$，则 $A \sim C$。

因此可以将势相同的集合归于同一类。

设 $A$ 与 $B$ 是两个集合, 若 $A$ 对等于 $B$ 的一个子集，则称 $A$ 的势小于或等于 $B$ 的势 (或 $B$ 的势大于或等于 $A$ 的势)，记作 $A \leq \bar{B}$ (或 $B \geq A$)。若 $A \leq B$ 且 ${A}$ 与 ${B}$ 不对等，则称 $A$ 的势小于 $B$ 的势（或 $B$ 的势大于 $A$ 的势），记作 $\overset{=}{A}<\overset{=}{B}$（或 $\overset{=}{B}>\overset{=}{A}$）。

凡与正整数对等的集合称为可数集 (或可列集)。

可数集的势用 $\aleph_0$ 表示，读作“阿列夫零”。

任意的无限集都有一个可数子集

可数集的子集或者是有限集，或者是可数集

推论可数集是无限集中具有最小势的一类集。

可数个可数集的并是可数集

可数集是无限集中最简单的一类集，然而，并非任何无限集都是可数集。

区间 $[0,1]$ 中的点的全体构成一个不可数集。

区间 $[0,1]$ 的点构成的集合的势称为连续统的势，记作 $\aleph$ (读作“阿列夫”)

实数集的势为 $\aleph$

伯恩斯坦（Bernstein）定理：设 A 与 B 是两个非空集。若 $A_{0} \subset A, B_{0} \subset B$，且 $A \sim B_{0}, B \sim A_{0}$，则 $A \sim B$。

无理数集的势为 $\aleph$。

康托猜想或连续统假设：在 $\aleph_0$ 与 $\aleph$ 之间不存在另一种势。

非空集合 $A$ 的幂集的势比 $A$ 本身的势大。

闭区间套定理

设 $\left\{\left[a_{n}, b_{n}\right]\right\}$ 是 $\mathbb{R}$ 中的闭区间列 ($n \geq 1$)，如果满足：

$\left[a_{1}, b_{1}\right] \supset\left[a_{2}, b_{2}\right] \supset \ldots \supset\left[a_{n}, b_{n}\right] \supset \ldots$
$\lim _{n \rightarrow \infty}\left (b_{n}-a_{n}\right)=0$

则存在唯一实数 $\xi$ 属于所有闭区间 $\left[a_{n}, b_{n}\right], n \geq 1$。

Cantor 集

Cantor 集的势为 $\aleph$。

因为 Cantor 集在构造的过程中，去掉中间保留左右两侧，用 L 与 R 表示则对于 Cantor 集中的点，LR 交替出现，若 L 表示为 0，R 表示为 1，同时在前面加上 $0.$，Cantor 集中的点可以表示为二进制小数，也就与 $[0,1]$ 一一对应，所以与 $[0,1]$ 等势，势为 $\aleph$。

图

无向图

无向图 $G$ 是一个二元组，其中：

$G$ 的顶点集 $V$ 是非空有穷集合，其元素称为顶点或节点。
$G$ 的边集 $E$ 为 $V\&V$ 的多重子集，其元素称为无向边，简称边。

有向图

有向图 $D$ 是一个二元组，其中： 1. 顶点集 $V$ 是非空有穷集合，其元素称为顶点或节点。 2. 边集 $E$ 为卡氏积 $V\times V$ 的多重子集，其元素称为有向边，简称边。 3. D 的基图：用无向边代替有向边。

$n$ 阶图：$n$ 个顶点的图。零图：$E=\varnothing$。平凡图：$1$ 阶零图。空图：$V=\varnothing$。

设 $e=(u, v)$ 是无向图 $G=<V,E>$ 的一条边，称 $u, v$ 为 $e$ 的端点，$e$ 与 $u (v)$ 关联。若 $u\neq v$，则称 $e$ 与 $u (v)$ 的关联次数为 $1$；若 $u=v$，则称 $e$ 为环，此时称 $e$ 与 $u$ 的关联次数为 $2$；若 $w$ 不是 $e$ 端点，则称 $e$ 与 $w$ 的关联次数为 $0$。无边关联的顶点称作孤立点。

设 $e=(u, v)$ 是有向图 $D=<V,E>$ 的一条有向边，$u$ 为 $e$ 的始点，$v$ 为 $e$ 的终点，称 $u, v$ 为 $e$ 的端点，$e$ 与 $u (v)$ 关联。无边关联的顶点称作孤立点。若有一条有向边的始点与终点重合，称该边为环。

$G=<V,E>$ 为无向图，$v\in V$：

$v$ 的度数 (度) $d (v)$：$v$ 作为边的端点的次数之和。
悬挂顶点：度数为 $1$ 的顶点。
悬挂边：与悬挂顶点关联的边。
$G$ 的最大度 $\Delta (G)=\max\{d (v)|v\in V\}$。
$G$ 的最小度 $\delta (G)=\min\{d (v)|v\in V\}$。

顶点的度数

$v$ 的出度 $d^{+}(v)$：$v$ 作为边的始点次数之和
$v$ 的入度 $d^{-}(v)$：$v$ 作为边的终点次数之和
$v$ 的度数 (度) $d (v)$：$v$ 作为边的端点次数之和

\[ D (v)=d^{+}(v)+d^{d}(v) \]

$D$ 的最大出度：$\Delta^{+}(D)=\max \left\{d^{+}(v) \mid v \in V\right\}$。 $D$ 的最小出度：$\delta^{+}(D)=\min \left\{d^{+}(v) \mid v \in V\right\}$。 $D$ 的最大入度：$\Delta^{-}(D)=\max \left\{d^{-}(v) \mid v \in V\right\}$。 $D$ 的最小入度：$\delta^{-}(D)=\min \left\{d^{-}(v) \mid v \in V\right\}$。 $D$ 的最大度：$\Delta (D)=\max \{d (v) \mid v \in V\}$。 $D$ 的最小度：$\delta (D)=\min \{d (v) \mid v \in V\}$。

设图 $G=<V, E>$ 为无向图或有向图，$V=\left\{v_{1}, V_{2}, \ldots, V_{n}\right\}$，边数 $|E|=m$，则：

\[ \sum_{i=1}^{n} d\left (v_{i}\right)=2 m . \]

推论：任何图 (无向或有向)，度数为基数的顶点个数是偶数。

设有向图 $D=<V, E>$，$V=\left\{v_{1}, V_{2}, \ldots, V_{n}\right\}$，$|E|=m$，则：

\[ \sum_{i=1}^{n} d^{+}\left (v_{i}\right)=\sum_{i=1}^{n} d^{-}\left (v_{i}\right)=m \]

多重图与简单图

在无向图中，如果有 2 条或 2 条以上的边关联同一对顶点，则称这些边为平行边，平行边的条数称为重数。
在有向图中，如果有 2 条或 2 条以上的边具有相同的始点和终点，则称这些边为有向平行边，简称平行边，平行边的条数称为重数。
含平行边的图称为多重图。
既无平行边也无环的图称为简单图。

完全图

设 $G=<V, E>$ 是 $n$ 阶无向简单图，若 $G$ 中任何顶点都与其余的 $n-1$ 个顶点相邻，则称 $G$ 为 $n$ 阶无向完全图，记作 $K_{n}$。设 $D=<V, E>$ 是 $n$ 阶有向简单图，若对于任意的顶点 $u, v \in V (u \neq v)$，既有有向边 $\langle u, v\rangle$，又有 $\langle v, u\rangle$，则称 $D$ 为 $n$ 阶有向完全图。

子图

设 $G=<V, E>$，$G^{\prime}=< V^{\prime}, E^{\prime}>$ 是两个图：

若 $V^{\prime} \subseteq V$ 且 $E^{\prime} \subseteq E$，则称 $G^{\prime}$ 为 $G$ 的子图，$G$ 为 $G^{\prime}$ 的母图，记作 $G^{\prime} \subseteq G$。
若 $G^{\prime} \subseteq G$ 且 $V^{\prime}=V$，则称 $G^{\prime}$ 为 $G$ 的生成子图。
若 $G^{\prime} \subseteq G$ 且 $G^{\prime} \neq G$，称 $G^{\prime}$ 为 $G$ 的真子图。
设 $V_{1} \subseteq V$ 且 $V_{1} \neq \varnothing$，以 $V_{1}$ 为顶点集，以两端点都在 $V_{1}$ 中的所有边为边集的 $G$ 的子图称作 $V_{1}$ 的导出子图，记作 $G\left[V_{1}\right]$。
设 $E_{1} \subseteq E$ 且 $E_{1} \neq \varnothing$，以 $E_{1}$ 为边集，以 $E_{1}$ 中边关联的所有顶点为顶点集的 $G$ 的子图称作 $E_{1}$ 的导出子图，记作 $G\left[E_{1}\right]$。

补图

设 $G=<V, E>$ 为 $n$ 阶无向简单图，$G$ 的补图 $\bar{G}$ 定义如下：$\bar{G}=\langle V, \bar{E}>$，其中 $\bar{E}=\{(u, v) \mid u, V \in V, (u, v) \notin E\}$。

同构

设两个无向图 $G_{1}=<V_{1}, E_{1}>$，$G_{2}=<V_{2}, E_{2}>$，如果存在双射函数 $f : V_{1} \rightarrow V_{2}$，使得对于任意的 $e=(u, v) \in E_{1}$，当且仅当 $e^{\prime}=(f (u) , f (v)) \in E_{2}$，并且 $e$ 与 $e^{\prime}$ 的重数相同，则称 $G_{1}$ 与 $G_{2}$ 是同构的，记作 $G_{1} \cong G_{2}$。

必要条件：

边数相同，顶点数相同
度数列相同 (不计度数的顺序)
对应顶点的关联集及邻域的元素个数相同

通路与回路

设 $G$ 中顶点与边的交替序列 $\Gamma=V_{0} e_{1} V_{1} e_{2} \cdots e_{l} V_{l}$，若 $1 \leq i \leq 1, v_{i-1}, V_{i}$ 是 $e_{i}$ 的端点 (当 $G$ 是有向图，要求 $v_{i-1}$ 是 $e_i$ 始点，$v_{i}$ 是 $e_{i}$ 终点)，则称 $\Gamma$ 为顶点 $v_{0}$ 到 $v_{l}$ 的通路，$v_{0}$ 和 $v_{l}$ 分别称为此通路的起点和终点，$\Gamma$ 中边的数目 $l$ 为称为 $\Gamma$ 的长度。又若 $v_{0}=v_{1}$，则称 $\Gamma$ 为回路。

$\Gamma$ 中所有边互不相同，则称 $\Gamma$ 为简单通路，当 $v_{0}=v_{l}$ 时，称此简单通路为简单回路。

$\Gamma$ 中除 $v_{0}, v_{l}$ 外所有顶点互不相同，所有的边也互不相同，则称此通路为初级通路或路径，当 $v_{0}=v_{l}$ 时，称此通路为初级回路或圈。

有边重复出现的通路称为复杂通路吗，有边重复出现的回路称为复杂回路。

表示方法：

用顶点和边的交替序列 (定义)，如 $\Gamma=V_{0} e_{1} V_{1} e_{2} \ldots e_{1} V_{l}$。
用边的序列，如 $\Gamma=e_{1} e_{2} \ldots e_{l}$。
简单图中，用顶点的序列，如 $\Gamma=v_{0} v_{1} \ldots V_{l}$。
非简单图中, 可用混合表示法, 如 $\Gamma=v_{0} v_{1} e_{2} v_{2} e_{5} v_{3} v_{4} v_{5}$。

无向图：环是长度为 $1$ 的圈，两条平行边构成长度为 $2$ 的圈。

有向图：环和两条方向相反边构成的回路分别为长度为 $1$ 和 $2$ 的圈。

在无向简单图中，所有圈的长度 $\geq 3$；在有向简单图中，所有圈的长度 $\geq 2$。

圈的个数

定义意义下：

在无向图中，一个长度为 $l$ ($l\ge 3$)的圈看作 $2 l$ 个不同的圈。
在有向图中，一个长度为 $l$ ($l\ge 3$)的圈看作 $l$ 个不同的圈。

同构意义下：

所有长度相同的圈都是同构的，因而是 1 个圈。

在一个 $n$ 阶图 $G$ 中，若从顶点 $u$ 到 $V (u \neq V)$ 存在通路，则从 $u$ 到 $v$ 存在长度小于等于 $n-1$ 的通路。

推论：在一个 $n$ 阶图 $G$ 中，若从顶点 $u$ 到 $v (u \neq v)$ 存在通路，则从 $u$ 到 $v$ 存在长度小于等于 $n-1$ 的初级通路。

在一个 $n$ 阶图 $G$ 中，若存在 $v$ 到自身的回路，则一定存在 $v$ 到自身长度小于等于 $n$ 的回路。

在一个 $n$ 阶图 $G$ 中，若存在 $v$ 到自身的简单回路，则存在 $v$ 到自身长度小于等于 $n$ 的初级回路。

在一个无向图 $G$ 中，若从顶点 $u$ 到 $v$ 存在通路（当然从 $v$ 到 $u$ 也存在通路），则称 $u$ 与 $v$ 是连通的。规定任何顶点与自身总是连通的。

在一个有向图 $D$ 中，若从顶点 $u$ 到 $v$ 存在通路，则称 $u$ 可达 $v$ 。规定任何顶点到自身总是可达的。

若无向图 $G$ 是平凡图或 $G$ 中任意两顶点都是连通的，则称 $G$ 是连通图；否则，称 $G$ 是非连通图。

连通分支

在无向图中，顶点之间的连通关系是等价关系。设 $G$ 为一个无向图，$R$ 是 $G$ 中顶点之间的连通关系。按照 $\mathrm{R}$ 可将 $\mathrm{V}(G)$ 划分成若干个等价类，设为 $V_{1}, V_{2}, \ldots, V_{k}$ 由它们导出的导出子图 $G\left[V_{1}\right]，G\left[V_{2}\right], \ldots, G\left[V_{k}\right]$ 称为 $G$ 的连通分支，$G$ 的连通分支的个数记为 $p (G)$。

设 $D$ 是一个有向图，如果略去 $D$ 中各有向边的方向后所得无向图是连通图，则称 $D$ 是弱连通图，简称连通图。若 $D$ 中任意两顶点至少一个可达另一个，则称 $D$ 是单向连通图。若 $D$ 中任何一对顶点都是相互可达的，则称 $D$ 是强连通图。

关联矩阵

无向图

设无向图 $G=<V, E>$，$V=\left\{v_{1}, V_{2}, \ldots, V_{n}\right\}$，$E=\left\{e_{1}, e_{2}, \ldots, e_{m}\right\}$，令 $m_{i j}$ 为 $v_{i}$ 与 $e_{j}$ 的关联次数，称 $\left (m_{i j}\right)_{n \times m}$ 为 $G$ 的关联矩阵，记为 $M (G)$。

每一列恰好有两个 $1$ 或一个 $2$，这是因为每条边关联两个顶点 (环关联的两个顶点重合)。
第 $i$ 行元素之和为 $v_{i}$ 的度数，$\sum_{j=1}^{m} m_{j j}=d\left (V_{i}\right)$。
所有元素之和等于 $2 m$，$\sum_{f=1}^{m} \sum_{k=1}^{n} m_{j}=\sum_{k=1}^{n} \sum_{j=1}^{m} m_{y}=\sum_{i=1}^{n} d\left (v_{l}\right)=2 m$。
$v_{i}$ 为孤立点当且仅当第 $1$ 行全为 $0$。
$e_{j}$ 与 $e_{k}$ 平行边当且仅当第 $j$ 列与第 $k$ 列相同。

设无环有向图 $D=<V, E>$，$V=\left\{v_{1}, v_{2}, \ldots, v_{n}\right\}$，$E=\left\{e_{1}, e_{2}, \ldots\right. \left. E_{m}\right\}$，令：

\[ M_{i j}=\left\{\begin{array}{ll} 1, & v_{i} \text { 为 } e_{j} \text { 的始点 } \\ 0, & v_{i} \text { 与 } e_{j} \text { 不关联 } \\ -1, & v_{i} \text { 为 } e_{j} \text { 的终点 } \end{array}\right. \]

则称 $\left (m_{i j}\right)_{n \times m}$ 为 $D$ 的关联矩阵，记为 $M (D)$。

每一列恰好有一个 $1$ 和一个 $- 1$。
第 $1$ 行 $1$ 的个数等于 $d^{+}\left (v_{i}\right),-1$ 的个数等于 $d\left (v_{i}\right)$。$M (D)$ 中所有 $1$ 的个数等于所有 $-1$ 的个数，且都等于 $m$。

在有向图中，若存在一条边 $e$ 以顶点 $u$ 为始点、以 $v$ 为终点，则称 $u$ 邻接到 $v_{0}$。

设有向图 $D=<V, E>$，$V=\left\{V_{1}, V_{2}, \ldots, V_{n}\right\}$，$|E|=m$，令 $a_{i j}^{(1)}$ 为 $V_{i}$ 邻接到 $V_{j}$ 的边的条数，称 $\left (a_{i j}^{(i)}\right)_{n \times n}$ 为 $D$ 的邻接矩阵，记作 $A (D)$。

有向图的邻接矩阵有下述性质：

第 $i$ 行元素之和等于 $d^{+}\left (V_{j}\right), \sum_{j=1}^{n} a_{j j}^{(i)}=d^{+}\left (v_{i}\right)$。
第 $j$ 列元素之和等于 $d\left (v_{j}\right), \sum_{i=1}^{n} a_{i j}^{(i)}=d^{-}\left (v_{j}\right)$。
所有元素之和等于边数 (长度为 $1$ 的通路数)，$\sum_{i=1}^{n} \sum_{j=1}^{n} a_{i j}^{(i)}=m$。
长度为 $1$ 的回路数为 $\sum_{i=1}^{n} a_{i i}^{(i)}$。

有向图的通路数与回路数：

设 $A$ 为 $n$ 阶有向图 $D$ 的邻接矩阵，则 $A^{l}(\geq 1)$ 中： $a_{i j}^{(l)}$ 为 $D$ 中 $V_{i}$ 到 $V_{j}$ 长度为 $l$ 的通路数， $a_{i i}^{(l)}$ 为 $D$ 中 $V_{i}$ 到自身长度为 $l$ 的回路数， $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} a_{i j}^{(l)}$ 为 $D$ 中长度为 $l$ 的通路（含回路）总数， $\sum\limits_{l=1}^{n} a_{ii}^{(l)}$ 为 $D$ 中长度为 $1$ 的回路总数。

推论：设 $B_{r}=A+A^{2}+\ldots+A^{r}(r \geq 1)$，则 $B_{r}$ 中元素 $b_{i j}^{(r)}$ 为 $D$ 中 $v_{i}$ 到 $v_{j}$ 长度小于等于 $r$ 的通路数，$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} b_{i j}^{(r)}$ 为 $D$ 中长度小于等于 $r$ 的通路（含回路）总数，其中 $\sum\limits_{i=1}^{n} b_{i}^{(r)}$ 为 $D$ 中长度小于或等于 $r$ 的回路总数。

定义 $D=<V, E>$ 为有向图，$V=\left\{V_{1}, V_{2}, \ldots, V_{n}\right\}$，令：

\[ P_{t j}=\left\{\begin{array}{ll} 1, & \text { 若 } v_{t} \text { 可达 } v_{j}, \\ 0, & \text { 否则, } \end{array}\right. \]

称 $\left (p_{i j}\right)_{n \times n}$ 为 $D$ 的可达矩阵，记作 $P (D)$。性质：

$P (D)$ 主对角线上的元素恒为 $1$。
$D$ 强连通当且仅当 $P (D)$ 的元素全为 $1$。

割集

设无向图 $G=<V, E>$，$V \subset V$，若 $p\left (G-V^{\prime}\right)>p (G)$，且对 $V$ 的任何真子集 $V^{\prime}, p\left (G-V^{\prime}\right)=p (G)$，则称 $V$ 为 $G$ 的点割集。若点割集中只有一个顶点 $v$，则称 $r$ 为割点。

又 $E \subseteq E$，若 $p (G-E)>p (G)$ 且对 $E$ 的任何真子集 $E^{\prime}$，$p\left (G-E^{\prime}\right)=p (G)$，则称 $E^{\prime}$ 为 $G$ 的边割集。简称割集。若为边割集中只有一条边 $e$，则称 $e$ 为割边或桥。

二部图

若能将无向图 $G=<V,E>$ 的顶点集 $V$ 划分成两个不相交的非空子集 $V_{1}$ 和 $V_{2}$，使得 $G$ 中的每条边的两个端点一个属于 $V_{1}$，另一个属于 $V_{2}$，则称 $G$ 为二部图 (或偶图)。称 $V_{1}$ 和 $V_{2}$ 为互补顶点子集，此时可将 $G$ 记为 $G=< V_{1}, V_{2}, E>$。

若 $V_{1}$ 中每个顶点都与 $V_{2}$ 中每个顶点均有且仅有一条边相关联，则称二部图 $G$ 为完全二部图 (或完全偶图)。当 $\left|V_{1}\right|=n,\left|V_{2}\right|=m$，完全二部图 $G$ 记为 $K_{n, m}$。

一个无向图 $G=<V, E>$ 是二部图当且仅当 $G$ 中没有长度为奇数的回路。

设无向图 $G=< V, E>$，$M \subseteq E$，若 $M$ 中任意两条边均不相邻，则称 $M$ 为 $G$ 中的匹配。若在 $M$ 中再加入任何 $1$ 条边就都不是匹配了，则称 $M$ 为极大匹配。

边数最多的匹配称为最大匹配，最大匹配中的边的条数称为 $G$ 的匹配数，记为 $\beta_{1}(G)$，简记为 $\beta_{1}$。设 $M$ 为 $G$ 中一个匹配，$v \in V (G)$，若存在 $M$ 中的边与 $v$ 关联，则称 $v$ 为 $M$ 的饱和点，否则称 $v$ 为 $M$ 的非饱和点。若 $G$ 中每个顶点都是 $M$ 饱和点，则称 $M$ 为完美匹配。

设 $G=<V_{1}, V_{2}, E>$ 为二部图，$\left|V_{1}\right| \leq\left|V_{2}\right|$，$M$ 是 $G$ 中一个最大匹配，若 $|M|=\left|V_{1}\right|$，则称 $M$ 为 $G$ 中 $V_{1} 到 $V_{2}$ 的完备匹配。当 $\left|V_{1}\right|=\left|V_{2}\right|$ 时，完备匹配是完美匹配。

Hall 定理：设二部图 $G=<V_{1}, V_{2}, E>$ 中，$\left|V_{1}\right| \leq\left|V_{2}\right|$。$G$ 中存在从 $V_{1}$ 到 $V_{2}$ 的完备匹配当且仅当 $V_{1}$ 中任意 $k$ 个顶点至少邻接 $V_{2}$ 中的 $k$ 个顶点。

相异性条件

二部图 $G=<V_{1}, V_{2}, E>$ 中，如果存在 $t>0$，使得：

$V_{1}$ 中每个顶点至少关联 $t$ 条边。
$V_{2}$ 中每个顶点至多关联条边。

则 $G$ 中存在 $V_{1}$ 到 $V_{2}$ 的完备匹配。

欧拉图

经过图（无向图或有向图）中每条边一次且仅一次并且行遍图中每个顶点的回路（通路），称为欧拉回路（欧拉通路）。存在欧拉回路的图称为欧拉图，存在欧拉通路，但无欧拉回路的图称为半欧拉图。

无向图 $G$ 有欧拉回路，当且仅当 $G$ 是连通图且无奇度顶点。无向图 $G$ 有欧拉通路、但无欧拉回路，当且仅当 $G$ 是连通图且恰有两个奇度顶点。这两个奇度顶点是欧拉通路的端点。

有向图 $D$ 有欧拉回路，当且仅当 $D$ 是连通的且每个顶点的入度都等于出度。有向图 $D$ 有欧拉通路、但无欧拉回路，当且仅当 $D$ 是连通的，且除了两个顶点外，其余顶点的入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度大 $1$，另一个顶点的入度比出度小 $1$。任何欧拉通路以前一个顶点为终点，以后一个顶点为始点。

哈密顿图

经过图中每个顶点一次且仅一次的通路称为哈密顿通路，闭合的哈密顿通路称为哈密顿回路。存在哈密顿回路的图称为哈密顿图，具有哈密顿通路而无哈密顿回路的图称为半哈密顿图。

设无向图 $G=<V, E>$ 是哈密顿图，$V_{1}$ 是 $V$ 的任意非空子集，则：

\[ P\left (G-V_{1}\right) \leq\left|V_{1}\right| \]

推论：设无向图 $G=<V, E>$ 中有哈密顿通路，$V_{1}$ 是 $V$ 的任意非空子集，则 $p\left (G-V_{1}\right) \leq\left|V_{1}\right|+1$。

无向哈密顿图的一个充分条件

设 $G$ 是 $n (n \geq 3)$ 阶无向简单图，如果 $G$ 中任何一对不相邻的顶点的度数之和都大于等于 $n-1$，则 $G$ 中存在哈密顿通路。如果 $G$ 中任何一对不相邻的顶点的度数之和都大于等于 $n$，则 $G$ 中存在哈密顿图。

有向图的哈密通路

在 $n (n \geq 2)$ 阶有向图 $D=<V, E>$ 中，如果所有有向边均用无向边代替，所得无向图含有生成子图 $K_{n}$，则有向图 $D$ 中存在哈密顿通路。

平面图

如果图 $G$ 能画在平面上使得除顶点处外没有边交叉出现，则称 $G$ 是平面图。画出的这种不出现边交叉的图称为 G 的一个平面嵌入。没有平面嵌入的图称作非平面图。

平面图的面与次数

设 $G$ 是一个平面嵌入：

$G$ 的面：由 $G$ 的边将平面划分成的每一个区域。
无限面 (外部面)：面积无限的面，用 $R_{0}$ 表示。
有限面 (内部面)：面积有限的面，用 $R_{1}, R_{2}, \ldots, R_{k}$ 表示。
面 $R_{i}$ 的边界：包围 $R_{i}$ 的所有边构成的回路组。
面 $R_{i}$ 的次数：$R_{i}$ 边界的长度，用 $\operatorname{deg}\left (R_{i}\right)$ 表示。

平面图的所有面的次数之和等于边数的 $2$ 倍。

设 $G$ 为一个简单平面图，如果在 $G$ 中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则称 $G$ 为极大平面图。若在非平面图 $G$ 中任意删除一条边，所得图为平面图，则称 $G$ 为极小非平面图。极大平面图必连通，极小非平面图必为简单图。

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

欧拉公式

设 $G$ 为 $n$ 阶 $m$ 条边 $r$ 个面的连通平面图，则有：

\[ N-m+r=2 \]

设 $G$ 是有 $p (p \geq 2)$ 个连通分支的平面图，则：

\[ N-m+r=p+1 \]

设 $G$ 为 $n$ 阶 $m$ 条边的连通平面图，每个面的次数不小于 $l (l \geq 3)$，则：

\[ M \leq \frac{l}{l-2}(n-2) \]

设 $G$ 为有 $p (p \geq 2)$ 个连通分支的平面图，且每个面的次数不小于 $l (l \geq 3)$，则：

\[ M \leq \frac{l}{l-2}(n-p-1) \]

推论：$K_5$ 和 $K_{3,3}$ 不是平面图。

设平面图 $G$，有 $n$ 个顶点，$m$ 条边和 $r$ 个面，$G$ 的对偶图 $G^{*}=<V^{*}, E^{*}>$ 如下：

在 $G$ 的每一个面 $R_{i}$ 中任取一个点 $v_{i} *$ 作为 $G^{*}$ 的顶点。

\[ V^{*}=\left\{v_{i}^{*} \mid i=1,2, \ldots, r\right\} \]

对 $G$ 的每一条边 $e_{k}$，若 $e_{k}$ 在 $G$ 的面 $R_{i}$ 与 $R_{j}$ 的公共边界上，则作边 $e_{k}^{*}=\left (v_{i}^{*}, v_{j}^{*}\right)$，且与 $e_{k}$ 相交。

若 $e_{k}$ 为 $G$ 中的桥且在面 $R_{i}$ 的边界上，则作环 $e_{k}^{*}=\left (v_{i}^{*}, V_{i}^{*}\right)$。

\[ E^{*}=\left\{e_{k}^{*} \mid k=1,2, \ldots, m\right\} \]

无向树

不含回路的连通无向图称为无向树，简称树。每个连通分支均是树的非连通无向图称为森林。平凡图称为平凡树。树中度数为 $1$ 的顶点称为树叶，度数大于等于 $2$ 的顶点称为分支点。

设 $G=(V, E)$ 是 $n$ 阶 $m$ 条边的无向图，则下面各命题是等价的：

$G$ 连通且不含回路。
$G$ 的每对顶点之间有唯一的一条路径。
$G$ 是连通的且 $m=n-1$。
$G$ 中无回路且 $m=n-1$。
$G$ 中无回路，但在任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路。
$G$ 是连通的且每条边都是桥。

$n$ 阶非平凡的树中至少有 $2$ 片树叶。

设 $G=(V, E)$ 是无向连通图，$T$ 是 $G$ 的生成子图并且是树，则称 $T$ 是 $G$ 的生成树。

生成树 $T$ 的树枝：$G$ 在 $T$ 中的边。生成树 $T$ 的弦：$G$ 不在 $T$ 中的边。生成树 $T$ 的余树：所有弦的集合的导出子图。设 $n$ 阶连通无向图有 $m$ 条边，则它的生成树有 $n-1$ 条边，余树有 $m-n+1$ 条边。

任何无向连通图都有生成树。

主成分分析

内积和范数

对于实向量 $\mathbf{x}$ 和向量 $\mathbf{y}$：

向量 $\mathbf{x}$ 和向量 $\mathbf{y}$ 的内积：

\[ \langle\mathbf{x}, \mathbf{y}\rangle=\mathbf{x}^{T} \mathbf{y}=\sum_{i=1}^{n} x_{i} y_{i} \]

向量 $\mathbf{x}$ 的范数：
1. $L_{0}$ 范数 (也称 $0$ 范数)：$\|\mathbf{x}\|_{0}$ 定义为 $\mathbf{x}$ 中非零元的个数。
2. $L_{1}$ 范数 (也称和范数或 $1$ 范数)：$\|\mathbf{x}\|_{1}=\sum_{i=1}^{n}\left|x_{i}\right|$。
3. $L_{2}$ 范数 (也称欧氏范数或 $2$ 范数)：$\|\mathbf{x}\|_{2}=\left (\sum_{i=1}^{n}\left|x_{i}\right|^{2}\right)^{1 / 2}$。
4. $L_{\infty}$ 范数 (也称无穷范数)：$\|\mathbf{x}\|_{\infty}=\max \left\{\left|x_{1}\right|,\left|x_{2}\right|, \cdots,\left|x_{n}\right|\right\}$。
5. $L_{p}$ 范数 (也称 Hölder 范数)：$\|\mathbf{x}\|_{p}=\left (\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{1 / p}, p \geq 1$。

求解步骤

主成分求解步骤如下：

求样本均值 $\bar{x}=\left (\overline{x_{1}}, \overline{x_{2}}, \ldots, \overline{x_{p}}\right)$ 和样本的协方差矩阵 $\boldsymbol{S}$。
求解特征方程 $|\boldsymbol{I}-\boldsymbol{S}|=0$，解得 $p$ 个特征根 $\lambda_{1}, \lambda_{2}, \ldots \lambda_{p}$。
求每个特征值对应的单位正交特征向量 $\boldsymbol{\alpha}_{i}(k=1,2, \ldots, k)$，解得 $\boldsymbol{\alpha}_{i}=\left (\alpha_{1 i}, \alpha_{2 i}, \ldots, \alpha_{i}\right)^{T}$ 。
写成主成分的表达式：

\[ \boldsymbol{f}_{i}=\alpha_{1 i}\left (\boldsymbol{x}_{1}-\overline{\boldsymbol{x}_{1}} \mathbf{1}\right)+\alpha_{2 i}\left (\boldsymbol{x}_{2}-\overline{\boldsymbol{x}_{2}} \mathbf{1}\right)+\ldots+\alpha_{p i}\left (\boldsymbol{x}_{p}-\overline{\boldsymbol{x}_{p}} \mathbf{1}\right) \]

SVD 分解与 Moore-Penrose 逆矩阵

假设我们有一个矩阵 $A=\left[\begin{array}{ll}1 & 1 \\ 1 & 1 \\ 0 & 0\end{array}\right]$。

第一步计算 U

计算矩阵 $A A^{T}=\left[\begin{array}{lll}2 & 2 & 0 \\ 2 & 2 & 0 \\ 0 & 0 & 0\end{array}\right]$。

对其进行特征分解，分别得到特征值 $4,0,0$ 和对应的特征向量 $\left[\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0\right]^{T},\left[-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0\right]^{T},[0,0,1]^{T}$，可以得到：

\[ U=\left[\begin{array}{ccc} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \end{array}\right] \]

第二步计算 $\Sigma^{m \times n}$

$\Sigma_{m n}=\left[\begin{array}{cc}\Sigma_{1} & 0 \\ 0 & 0\end{array}\right]$，其中 $\Sigma_{1}=\operatorname{diag}\left (\sigma_{1}, \sigma_{1}, \ldots, \sigma_{r}\right)$ 是将第一步求出的非零特征值从大到小排列后开根号的值，这里：

\[ \Sigma=\left[\begin{array}{ll}2 & 0 \\ 0 & 0 \\ 0 & 0\end{array}\right] \]

第三步计算 V

已知 $rank (A)=1$。

计算 $V_1=A^TU_1\Lambda^{-1}=\left[\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right]^{T}$

将 $V_1$ 拓展为酉矩阵 (也就是正交矩阵，但是支持复数形式)得到：

\[ V=\left[\begin{array}{cc} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right] \]

最终，我们可以得到 $A$ 的奇异值分解：

\[ A=U \Sigma V^{T}=\left[\begin{array}{ccc} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \end{array}\right]\left[\begin{array}{ll} 2 & 0 \\ 0 & 0 \\ 0 & 0 \end{array}\right]\left[\begin{array}{cc} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right]^{T}=\left[\begin{array}{ll} 1 & 1 \\ 1 & 1 \\ 0 & 0 \end{array}\right] \]

计算 Moore-Penrose 逆矩阵

\[ A^+=V\Sigma^+U^T \]

回归

已知：$y=\beta_0+\beta_1 x_i$

简单回归的最小二乘估计

\[ \begin{array}{c} \hat{\beta}_{0}=\bar{y}-\hat{\beta}_{1} \bar{x} \\ \hat{\beta}_{1}=\frac{\sum_{i=1}^{n} x_{i} y_{i}-n \bar{x} \bar{y}}{\sum_{i=1}^{n} x_{i}^{2}-n (\bar{x})^{2}} \end{array} \]

多元回归的帽子矩阵法

\[ \begin{array}{c} \widehat{\boldsymbol{\beta}}=\left (\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} \boldsymbol{y} \\ \widehat{\boldsymbol{y}}=\boldsymbol{X}\left (\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T} \boldsymbol{y} \end{array} \]

其中称 $\boldsymbol{H}=\boldsymbol{X}\left (\boldsymbol{X}^{T} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{T}$ 称为帽子矩阵，它是对称幂等阵，即：

\[ \boldsymbol{H}^{T}=\boldsymbol{H}, \quad \boldsymbol{H}^{n}=\boldsymbol{H}, \quad (\boldsymbol{I}-\boldsymbol{H})^{n}=\boldsymbol{I}-\boldsymbol{H} \]

代数系统

群

若在一个非空集合 $G$ 上定义了一个运算，记为” $\cdot$ “，称为乘法，并满足下列条件：

结合律成立，对任意 $a, b, c \in G$，有 $a \cdot (b \cdot c)=(a \cdot b) \cdot c$。
有单位元素 (幺元) $e \in G$，满足：对任意 $a \in G$，有：$a \cdot e=e \cdot a=a$。
$G$ 中任意元素 $a$ 均有逆元素 $a^{1} \in G$，满足：$a \cdot a^{-1}=a^{-1} \cdot a=e$。

则称 $G$ 对于运算“$\cdot$”构成一个群，或简称 $G$ 为一个群。只满足 1)为半群，只满足 1)和 2)为带幺半群。

若上述定义的运算为加法，则将运算符号” $\cdots$ “改为“$+$”，么元改为零元，逆元改为负元。

若群 $G$ 对于对于上述运算还有交换律成立，即对于任意 $a, b \in G$，有 $a \cdot b=b \cdot a$，则称 $G$ 为交换群（或称 Abel 群）。

群是一种代数系统，它是由一个非空集合与一个运算构成的。若集合不同，构成的群当然不同。对同一个集合，运算不同则构成的群也不同。

按群 $G$ 具有元素的个数 (元数)多少分为无限群与有限群。

有限群实例：含有 $n$ 个元素的有限集上的所有可逆映射（称为 $n$ 元置换），对于映射的乘法构成一个群，称为 $n$ 元置换群，或称为 $n$ 次对称群，记为 $S_{n}$。$S_{n}$ 的每一个元素可以表示成一个 $n$ 元置换：

\[ \sigma=\left[\begin{array}{ccccc} 1 & 2 & 3 & \cdots & n \\ J_{1} & j_{2} & j_{3} & \cdots & j_{n} \end{array}\right] \]

其中，$j_{1}, j_{2}, j_{3}, \ldots, j_{n}$ 为 $1,2,3, \ldots, n$ 的某个排列。

无限群实例：非空集合 $U$ 到其自身的所有可逆映射（或称为变换），对于映射的乘法构成群，称为集合 $U$ 的全变换群，记为 $S_{u}$。当 $U$ 为无限集时，$S_{u}$ 为无限群。$S_{u}$ 的非空子集，若对于映射的乘法也构成群，则称为变换群。

群有以下简单性质:

任意一个群的单位元是唯一的。群的任意元的逆元也是唯一的。
若 $(G, \cdot)$ 是一个群，则对任意 $a, b \in G$，方程 $a \cdot x=b \text { 与 } y \cdot a=b$，均有唯一解。
消去律成立，即：

\[ \begin{array}{l} A \cdot x=a \cdot y \Rightarrow x=y \\ X \cdot a=y \cdot a \Rightarrow x=y \end{array} \]

群中可以定义幂：

\[ \begin{array}{l} A^{1}=a, a^{n+1}=a^{n} \cdot a \\ A^{0}=e, a^{-n}=\left (a^{-1}\right)^{n}, n>0 \end{array} \]

子群

如果群 $G$ 的非空子集 $H$ 对于 $G$ 上定义的运算也构成一个群，则称 $H$ 为 $G$ 的子群。

设 $G$ 是任意一个群，$e$ 是 $G$ 的单位元，则单位元群 $\{e\}$ 是 $G$ 的子群，且 $G$ 本身也构成 $G$ 的子群。这两个特殊的子群，称为 $G$ 的平凡子群。除此之外，$G$ 的其他子群 $H$ 可称为非平凡子群。

群 $G$ 的非空子集 $H$ 是 $G$ 的子群的充要条件是：

对任意 $a, b \in H$，有 $a \cdot b \in H$。
对任意 $a \in H$，有 $a^{-1} \in H$。

群 $G$ 的非空子集 $H$ 是 $G$ 的子群的充要条件是：对任意 $a, b \in H$，有 $a \cdot b^{-1} \in H$。

设 $H$ 是群 $G$ 的子群，对任意给定的 $a \in G$，记：

\[ \begin{aligned} A H & =\{a \cdot h \mid \forall h \in H\} \\ H a & =\{h \cdot a \mid \forall h \in H\} \end{aligned} \]

分别称为 $H$ 的左陪集与右陪集。

若群 $G$ 中子群 $H$ 的任意左陪集同时又是 $H$ 的右陪集，也就是说，$H$ 能够与 $G$ 的任意元素 $a$ 交换，即对任意 $a \in G$ 有：

\[ \mathrm{aH}=\mathrm{Ha} \]

则称 $H$ 为 $G$ 的正规子群。

交换群的任意子群均是正规子群。

正规子群 $H$ 可以定义左陪集的乘法运算：

$a H \cdot b H=a H b \cdot H=a b H \cdot H=a b H$ 对任意 $a, b \in G$，$G$ 中所有 $H$ 的左陪集构成的集合对于上述乘法运算构成群。

设 $G$ 与 $G^{\prime}$ 是两个群，如果有一个 $G$ 到 $G^{\prime}$ 上的一一对应 $\sigma$，对于 $G$ 与 $G^{\prime}$ 的运算，有：

\[ \sigma (x \cdot y)=\sigma (x) \circ \sigma (y) \]

对任意 $x, y \in G$ 均成立。那么，就称 $G$ 同构于 $G^{\prime}$，记为 $G \cong G^{\prime}$，称满足上述条件的映射为同构映射（简称同构）。

同构把 $G$ 的单位元变为 $G$ 的单位元，把 $G$ 的逆元变为 $G$ 的逆元。

三维空间刚体运动

旋转向量

三维空间中的旋转也可以表示为向量绕着某一个单位向量旋转一个具体角度。因此，可以用一个旋转轴和一个旋转角进行刻画，其旋转方向为旋转轴的方向。因此，只使用一个向量即可进行描述，其方向与旋转轴一致，长度等于旋转角，这种向量称为旋转向量 (或轴角 angle-axis)，正好为三维：

\[ \boldsymbol{\phi}=\theta \boldsymbol{n} \]

其中 $\theta$ 表示旋转角度，$\boldsymbol{n}$ 表示单位旋转向量。

罗德里格斯公式：旋转向量到旋转矩阵

\[ \boldsymbol{R}=\cos \theta \boldsymbol{I}+(1-\cos \theta) \boldsymbol{n} \boldsymbol{n}^{T}+\sin \theta \boldsymbol{n}^{\wedge} . \]

同样, 对于变换矩阵, 可用一个旋转向量和一个平移向量进行描述, 正好为六维。

旋转矩阵到旋转向量的转换:

\[ \begin{aligned} \operatorname{tr}(\boldsymbol{R}) & =3 \cos \theta+(1-\cos \theta) \operatorname{tr}\left (\boldsymbol{n n}^{T}\right) \\ & =3 \cos \theta+(1-\cos \theta)\|\boldsymbol{n}\|_{2}^{2} \\ & =3 \cos \theta+(1-\cos \theta) \\ & =1+2 \cos \theta \end{aligned} \]

从而 $\theta=\arccos \frac{\operatorname{tr}(\boldsymbol{R})-1}{2}$，同时，由 $\boldsymbol{R} \boldsymbol{n}=\boldsymbol{n}$ 可得：

\[ (\boldsymbol{R}-\boldsymbol{I}) \boldsymbol{n}=0,\|\boldsymbol{n}\|_{2}=1 \]

即通过旋转矩阵的迹求旋转角度，通过旋转矩阵的特征值求单位旋转向量。轴角的表示也有奇异性，比如转 30 度与转 390 度的轴角表示是一样的。

四元数

\[ \begin{array}{l} \boldsymbol{q}=W+x i+y j+z \boldsymbol{k} \\ S=W \in \mathbb{R}, \boldsymbol{v}=(x, y, z)^{T} \in \mathbb{R}^{3} \\ \boldsymbol{q}=(s, x, y, z)^{T}=\left (\begin{array}{l} S \\ \boldsymbol{v} \end{array}\right) \end{array} \]

对于 ijk 有：

\[ \left\{\begin{array}{l} I j=k, j i=-k \\ J k=i, k j=-i \\ K i=j, i k=-j \\ I^{2}=-1, j^{2}=-1, k^{2}=-1 \end{array}\right. \]

对 $\boldsymbol{q}=\left (s, \boldsymbol{v}^{T}\right)^{T}$，若 $s=0$ 则称 $\boldsymbol{q}$ 为虚四元数，或纯虚四元数；若 $\boldsymbol{V}=\mathbf{0}$，则称 $\boldsymbol{q}$ 为实四元数。令 $\boldsymbol{q}_{a}=\left (s_{a}, \boldsymbol{v}_{a}^{T}\right)^{T}, \boldsymbol{q}_{b}=\left (s_{b}, \boldsymbol{v}_{b}^{T}\right)^{T}$。

四元数的基本运算:

加减法：$\boldsymbol{q}_{a} \pm \boldsymbol{q}_{b}=\left (\begin{array}{l}s_{a} \pm s_{b} \\ \boldsymbol{v}_{a} \pm \boldsymbol{v}_{b}\end{array}\right)$。

乘法：$\boldsymbol{q}_{a} \boldsymbol{q}_{b}=\left (\begin{array}{c}s_{a} s_{b}-\boldsymbol{v}_{a}^{T} \boldsymbol{v}_{b} \\ s_{a} \boldsymbol{V}_{b}+s_{b} \boldsymbol{v}_{a}+\boldsymbol{V}_{a} \times \boldsymbol{V}_{b}\end{array}\right)$。

模长：$\|\boldsymbol{q}\|=\|\dot{s}\|,\left\|\boldsymbol{q}_{2} \boldsymbol{q}_{b}\right\|=\left\|\boldsymbol{q}_{a}\right\|\left\|\boldsymbol{q}_{b}\right\|$。

数乘：$k \boldsymbol{q}=\left (k s, k \boldsymbol{v}^{T}\right)^{T}$。

共轭：$\boldsymbol{q}^{*}=\left (\begin{array}{c}s \\ -\boldsymbol{v}\end{array}\right), \boldsymbol{q} \boldsymbol{q}^{*}=\boldsymbol{q}^{*} \boldsymbol{q}=\left (s^{2}+\boldsymbol{v}^{T} \boldsymbol{v}, \mathbf{0}\right)^{T}=\|\boldsymbol{q}\|^{2}+0 i+0 j+0 k=\|\boldsymbol{q}\|^{2}$。

逆：$\quad \boldsymbol{q}^{-1}=\frac{\boldsymbol{q}^{*}}{\|\boldsymbol{q}\|^{2}}, \boldsymbol{q} \boldsymbol{q}^{-1}=\boldsymbol{q}^{-1} \boldsymbol{q}=1$。

若 $\left\|\boldsymbol{q}_{a}\right\|=\left\|\boldsymbol{q}_{b}\right\|=1$，则 $\left (\boldsymbol{q}_{a} \boldsymbol{q}_{b}\right)^{-1}=\boldsymbol{q}_{b}^{-1} \boldsymbol{q}_{a}^{-1}$。

单位四元数表示旋转: 单位四元数实际上具有三个自由度, 对应于三维空间中的旋转。

将三维空间中的点 $\mathrm{P}(x, y, z)$ 用虚四元数 $\boldsymbol{p}=(0, x, y, z)^{T}$ 表示，以及一个由四元数 $\boldsymbol{q}$ 指定的旋转，则旋转后的点 $p^{\prime}$ 可表示为：

\[ \boldsymbol{p}^{\prime}=\boldsymbol{q} \boldsymbol{p} \boldsymbol{q}^{-1} \]

上述乘法均为四元数乘法，结果 $p^{\prime}$ 也是虚四元数，其虚部就是旋转后点的坐标。

任意单元四元数描述了一个旋转, 该旋转也可用旋转矩阵或旋转向量表示。

三维空间中, 从四元数到旋转矩阵的变换关系为：

\[ \boldsymbol{R}=\boldsymbol{v}^{T}+s^{2} \boldsymbol{I}+2 s \boldsymbol{v}^{\prime}+\left (\boldsymbol{v}^{\wedge}\right)^{2} \]

三维空间中，绕单位向量 $n$ 逆时针旋转 $\theta$，对应于单位四元数 $\boldsymbol{q}=\left (\cos \frac{\theta}{2}, \boldsymbol{n}^{T} \sin \frac{\theta}{2}\right)^{T}$ 。

符号	含义	元素
\(\varnothing\)	空集	不包含任何元素的集合
\(\mathbb{N}\)	自然数集	\(\{0,1,2,3,\ldots\}\)
\(\mathbb{Z}\)	整数集	\(\{\ldots,-3,-2,-1,0,1,2,3, \ldots\}\)
\(\mathbb{Z}^{+}\)	正整数集	\(\{1,2,3, \ldots\}\)
\(\mathbb{Q}\)	有理数集	\(\{\frac{p}{q}\mid p, q \in \mathbb{Z}, q \neq 0\}\)
\(\mathbb{R}\)	实数集	所有实数构成的集合
\(\mathbb{C}\)	复数集	所有复数构成的集合