---

---

# 集合论

# 集合的基本概念

# 集合的定义

• 具有某种特定性质事物的全体，通常，用大写的英文字母$A, B, C,……$ 表示集合

# 集合的元素

• 组成一个集合的那些对象或单元称为这个集合的元素，通常，用小写的英文字母$a$,$b$,$c$,…，或者$a_1$,$a_2$,$b_1$,$b_2$… 表示集合中的元素

# 属于

• 设 A 是一个集合，a 是集合 A 中的元素，记以$a \in A$，读作$a$ 属于$A$；若$a$ 不是集合$A$ 中的元素，则记以$a \notin A$，读作$a$ 不属于$A$

# 有限集

• 包含有限个元素的集合，称为有限集或有穷集 (finite set)

# 无限集

• 包含无限个元素的集合，称为无限集或无穷集 (infinite set)

# 空集

• 约定，存在一个没有任何元素的集合，称为空集 (empty set) ，记为$\varnothing$，有时也用$\{\}$ 来表示

# 全集

• 约定，所讨论的对象的全体称为全集 (universal set)，记作$E$ 或$U$，我们所讨论的集合都是全集的子集

• 全集是相对的

# 集合的元素数

• 设$A$ 是有穷集合，$A$ 中元素的个数称为集合$A$ 的元素数，记为$|A|$，特别，$|\varnothing|=0$

# 集合的表示法

# 列举法

• 将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征

# 描述法

• 通过描述集合中元素的共同特征来表示集合

# 文氏图

• 用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素

# 集合的特征

# 确定性

• 任何一个对象，或者是这个集合的元素，或者不是，二者必居其一

# 互异性

• 集合中任何两个元素都是不同的，即集合中不允许出现重复的元素

# 无序性

• 集合与其中的元素的顺序无关

# 多样性

• 集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征

# 集合间的关系

# 集合相等

• 当两个集合$A$ 和$B$ 的元素完全一样，即$A$，$B$ 实际上是同一个集合时，则称集合$A$，$B$ 相等，记以$A=B$

# 集合包含

# 子集

• 设$A$，$B$ 是两个集合，若$A$ 的元素都是$B$ 的元素，则称$A$ 是$B$ 的子集 (subset) ，也称$B$ 包含$A$，或$A$ 包含于$B$，记以$A \subseteq B$，或$B \supseteq A$

# 真子集

• 若$A \subseteq B$，且$A \neq B$，则称$A$ 是$B$ 的真子集 (proper subset)，也称$B$ 真包含$A$，或$A$ 真包含于$B$，记以$A \subset B$，或$B \supset A$

# 重要结论

• 对任意集合$A$, 有$A ⊆ A$
• $\varnothing$ 是任意集合的子集，且空集是唯一的
• 对于任意两个集合$A$、$B$，$A=B$ 当且仅当$A⊆B$ 且$B⊆ A$。

# 幂集

# 定义

• 设$A$ 是集合，$A$ 的所有子集为元素组成的集合称为$A$ 的幂集，记以$ρ(A)$ 或$2^A$，$ρ(A)=\{S|S ⊆ A\}$

# 性质

• 若 A 为有穷集，$|A|=n$，则$|2^A | = |ρ(A)|= C_n^0 + C_n^1 + … + C_n^n =2^n$
• $x∈ρ(A)$ 当且仅当$x⊆A$
• 设$A$、$B$ 是两个集合，$A⊆B$ 当且仅当$ρ(A)⊆ρ(B)$

# 集合运算

# 集合的并集

• 设$A$，$B$ 是两个集合。所有属于$A$ 或者属于$B$ 的元素组成的集合，称为$A$ 和$B$ 的并集，记以$A∪B$。即$A∪B=\{x|x∈A或x∈B\}$

# 集合的交集

• 设$A$，$B$ 是两个集合。由属于$A$ 又属于$B$ 的元素组成的集合，称为$A$ 和$B$ 的交集，记以$A∩B$。即$A∩B=\{x|x∈A且x∈B\}$

# 并集和交集的推广

• 设$A_1$，$A_2$，…，$A_n$ 是$n$ 个集合，则：$A_1∪A_2∪…∪A_n$，简记为$\bigcup\limits_{i=1}^nA_i$

• $A_1∩A_2∩…∩A_n$，简记为$\bigcap\limits_{i=1}^n A_i$

# 集合的补集

• 设$A$ 是一个集合，全集$E$ 与$A$ 的差集称为$A$ 的补集，记以$\sim A$，即$\sim A=E-A$

• 特别， $\sim \varnothing=E$，$\sim E= \varnothing$

# 集合的差集

• 设$A$，$B$ 是两个集合。由属于集合$A$ 而不属于集合$B$ 的所有元素组成的集合，称为$A$ 与$B$ 的差集，记以$A-B$。即$A-B=\{x|x∈A且x ∉B\}$

# 集合的对称差

• 设$A$，$B$ 是两个集合。则$A$ 与$B$ 的和 (对称差), 记以$A⊕B$, 定义为$A⊕B=(A-B)∪(B-A)$，即$A \oplus B=\{x|(x \in A)且(x \notin B)或(x \in B)且(x \notin A)\}$
• $A$ 与$B$ 的对称差还有一个等价的定义，即$A⊕B=(A∪B)-(A∩B)$

# 集合的运算律

# 等幂律

• $A∩A=A$
• $A∪A=A$

# 交换律

• $A∩B=B∩A$
• $A∪B=B∪A$

# 结合律

• $(A∩B)∩C=A∩(B∩C)$
• $(A∪B)∪C=A∪(B∪C)$

# 分配律

• $A∩(B∪C)=(A∩B)∪(A∩C)$
• $A∪(B∩C)=(A∪B)∩(A∪C)$

# 吸收律

• $A∩(A∪B)=A$
• $A∪(A∩B)=A$

# 互补律

• $\sim A∩A= \varnothing$
• $\sim A∪A=E$

# 德摩根律

• $\sim (A∩B)=\sim A ∪ \sim B$
• $\sim(A∪B)=\sim A ∩ \sim B$

# 同一律

• $E∩A=A$
• $\varnothing ∪A=A$

# 零一律

• $\varnothing∩A=\varnothing$

• $E∪A=E$

# 双重否定律

• $\sim (\sim A)=A$

# 其他算律

• $A-B=A∩ \sim B$
• $A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)$
• $A⊕A=\varnothing$
• $\sim\varnothing=E$
• $\sim E=\varnothing$

# 有限集合的计数

# 容斥原理

• $|A∪B|=|A|+|B|-|A∩B|$
• $|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|$
• 设$A_1，A_2，…，A_n$ 是$n$ 个集合，则：$|\bigcup\limits_{i=1}^n A_i|=\sum\limits_{i=1}^n|A_i|-\sum\limits_{i<j}^n|A_i\cap A_j|+\sum\limits_{i<j<k}^n|A_i\cap A_j \cap A_k|+...+(-1)^{n-1}|A_1 \cap A_2 \cap A_3 \cap ...\cap A_n|$ 称为包含排斥原理，简称容斥原理

# 集合恒等式的证明

# 基本定义法

# 公式等价法

# 基本原则

• 将集合运算表达式中其他运算符号转换为∩和∪；
• 将补运算作用到单一集合上；
• 左$\implies$ 右，右$\implies$ 左，左$\implies$ 中间式，右$\implies$ 中间式；
• 根据基本运算符号的定义和运算定律转换。

# 集合成员表法

# 关系

# 序偶和笛卡尔积

# 序偶

# 定义

• 对于有序$n$ 元组，当$n=2$ 时，我们将其称作有序二元组，也称作有序对，或序偶。

# 特点

• 若$a≠b$, 则$(a,b)≠(b,a)$
• 两个有序对$(a,b)$ 和$(c,d)$ 相等当且仅当$a=c$，$b=d$

# 特征

• 成对出现、具有一定的顺序

# 笛卡尔积

# 定义

• 设$A$，$B$ 是两个集合，所有有序对$(x, y)$ 做成的集合$(其中x∈A，y∈B)$，称为$A$，$B$ 的笛卡儿积，记为$A×B$，$A×B=\{(x，y)|x∈A且y∈B\}$
• 设$A_1,A_2 , ...,A_n$ 是$n$ 个集合，由所有有序$n$ 元组 ($a_1,a_2,…,a_n$) 组成的集合$(其中ai∈A_i，i=1,2, … ,n)$，称为$A_1,A_2,...,A_n$ 的笛卡儿积，记以$A_1×A_2 ×...×A_n$，$A_1×A_2 ×...×A_n=\{(a_1,a_2 ,… ,a_n) | a_i∈A_i，i=1,2, … ,n \}$

# 性质

• $|A×B|=|A|× |B|$

• 对任意集合$A$，有$A×\varnothing=\varnothing$，$\varnothing \times A=\varnothing$

• 笛卡儿积运算不满足交换律，即$A×B≠B×A$

• 笛卡儿积运算不满足结合律，即$(A×B)×C≠A×(B×C)$

• 笛卡儿积运算对并和交运算满足分配律， 即

  • $A×(B∪C)=(A×B)∪(A×C)$
  • $(B∪C)×A=(B×A)∪(C×A)$
  • $A×(B∩C)=(A×B)∩(A×C)$
  • $(B∩C)×A=(B×A)∩(C×A)$

• 设$A$，$B$，$C$，$D$ 是集合，若$A⊆C$ 且$B⊆D$，则$A×B ⊆ C×D$

# 二元关系

# 定义

• 给定任意集合$A$ 和$B$，若$R⊆A×B$，则称$R$ 为从$A$ 到$B$ 的二元关系，特别在$A=B$ 时，称$R$ 为$A$ 上的二元关系

# 补充

• 关系是一个集合，是序偶的集合
• $R$ 是有序对的集合。若$(x,y)∈R$，则也表示为$x R y$，即$(x,y)∈ R \iff x R y$
  • 若$R =\varnothing$，则称$R$ 为$A$ 到$B$ 上空关系
  • 若$R =A×B$，称$R$ 为$A$ 到$B$ 上全域关系
  • 称$R=\{(x,x)|x∈A\}$ 为$A$ 上的恒等关系，记为$I_A$
• 当集合$A,B$ 都是有限集时，$A×B$ 共有$2^{|A|\cdot|B|}$ 个不同的子集，
  即从$A$ 到$B$ 的不同关系共有$2^{|A|\cdot|B|}$ 个

# 定义域、值域和域

# 定义

• 令$R \subseteq A \times B$，且
  $\begin{cases} D (R) = \{ x | (∃y) (x R y ) \}\\R (R) = \{ y | (∃x) (x R y ) \}\\F(R) = D(R)∪R(R)\end{cases}$ 则称$D(R)$、$R(R)$ 和$F(R)$ 分别是二元关系$R$ 的定义域、值域和域，显然$D(R) ⊆ A$，$R(R) ⊆ B$

# 关系矩阵与关系图

# 关系矩阵

• 给定集合$A=\{a_1,a_2,···,a_m \}$ 和$B=\{b_1,b_2,···,b_n \}$，且$R⊆A×B$，若$r_{ij}=\begin{cases} 1 ,& {a_i R b_j}\\0 ,& 否则 \end{cases}$
  则称矩阵$M_R=(r _{i j})$ 为$R$ 的关系矩阵

# 关系图

• 给定集合$A=\{a_1,a_2,···,a_m \}$ 和$A$ 上的关系$R$，且$R⊆A×A$，若：以$A$ 中的元素为结点；对$R$ 中的元素$(a_i ,a_j )$, 以$a_i$ 为起点，以$a_j$ 为终点，作有向边所构成的图，则称该图为$R$ 的关系图

# 关系运算

# 关系的并、交、补、差

• 关系是序偶 (有序对) 的集合，因此可以对关系进行运算。
  若$R, S⊆A×B$，则$R∪S$，$R ∩S$，$\sim R$，$R-S⊆A×B$

# 关系的复合

# 定义

• 设$R$ 是从集合$X$ 到$Y$ 的关系，$S$ 是从$Y$ 到$Z$ 的关系，把$X$ 到$Z$ 的关系定义为$R\circ S$。称$R\circ S$ 是关系$R$ 和$S$ 的合成关系或复合关系，$R\circ S=\{(x,z)|∃x∈X, ∃z∈Z, 至少存在一个y∈Y有(x , y)∈R且(y , z)∈S\}$

# 定理

• 已知集合$X,Y,Z,W$，关系$R_1,R_2,R_3,R_4$ 如下$X\stackrel {R_1}\longrightarrow Y \stackrel {R_2R_3}\longrightarrow Z \stackrel {R_4}\longrightarrow W$，则有：

  • $𝑅_1∘(𝑅_2∪𝑅_3)=(𝑅_1∘𝑅_2)∪(𝑅_ 1∘𝑅_3)$
  • $R_1∘(R_2∩R_3)⊆(R_1∘R_2)∩(R_1∘R_3)$
  • $(𝑅_2∪𝑅_3)∘𝑅_4=(𝑅_2∘𝑅_4)∪(𝑅_3∘𝑅_4)$
  • $(𝑅_2∩𝑅_3)∘𝑅_4⊆(𝑅_2∘𝑅_4)∩(𝑅_3∘𝑅_4)$

• 已知集合$X, Y, Z, W$，关系$R_1, R_2, R_3$ 如下$X\stackrel {R_1}\longrightarrow Y \stackrel {R_2}\longrightarrow Z \stackrel {R_3}\longrightarrow W$，则有：$(R_1 \circ R_2)\circ R_3=R_1\circ (R_2 \circ R_3)$ 结合律

• $R\circ R\circ R \circ\dots\circ R=R^{(n)}$

• $R^{(0)}=I_X=\{(x,x)|x\in X\}$

# 逆关系

# 定义

• 若$R⊆A×B$，则关系$\overline R =\{(y,x)|(x,y)∈ R\}$
  是集合$B$ 到$A$ 的关系，$\overline R$ 称为关系$R$ 的逆关系

# 定理

• $R_1, R_2, R$ 为$X$ 到$Y$ 的二元关系，则

  • $\overline{R_1∪ R_2} =\overline{R_1} ∪\overline{R_2}$

  • $\overline{R_1 \cap R_2}=\overline {R_1} \cap \overline {R_2}$

  • $\overline{X \times Y} = Y \times X$

  • $\overline{\sim R}=\sim \overline{R}$

  • $\overline{R_1-R_2}=\overline{R_1}-\overline{R_2}$

  • $S \subseteq R \iff \overline{S}\subseteq\overline{R}$

• 已知集合$X, Y, Z$，关系$R, S$ 如下，$X \stackrel {R}\longrightarrow Y \stackrel {S}\longrightarrow Z$，则有：$\overline{R\circ S}=\overline{S}\circ\overline{R}$

# 注意

• 将$R$ 的关系矩阵转置即得$\overline R$ 的关系矩阵，即$R$ 和$\overline R$ 的关系矩阵互为转置矩阵
• $\overline R$ 的前域与后域正好是$R$ 的后域和前域，即$domR=ran\overline R$，$dom\overline R=ranR$
• $|R|=|\overline R|$

# 关系性质

# 自反性

• 令$R⊆A×A$，若对$A$ 中每个$x$，都有$xRx$，则称$R$ 是自反的，即$A上关系R是自反的\iff∀x(x∈A→xRx)$
• 该定义表明了，在自反的关系$R$ 中，除其他有序对外，必须包括由每个$x∈A$ 所组成的元素相同的有序对

# 反自反性

• 令$R⊆A×A$，若对于$A$ 中每个$x$，有$(x,x) ∉R$，则称$R$ 是反自反的，即$A上关系R是反自反的\iff∀x (x∈A→(x,x) ∉R)$
• 该定义表明了，一个反自反的关系$R$ 中，不应包括有任何相同元素的有序对
• 应该指出，任何一个不是自反的关系，未必是反自反的；反之，任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系

# 对称性

• 令$R⊆A×A$，对于$A$ 中每个$x$ 和$y$，若$xRy$，则$yRx$，称$R$ 是对称的，即$在A上关系R是对称的\iff(∀x)(∀y)(x,y∈A且xRy→yRx)$
• 该定义表明了，在表示对称的关系$R$ 的有序对集合中，若有有序对$(x, y)$，则必定还会有有序对$(y, x)$

# 反对称性

• 令$R⊆A×A$，对于$A$ 中每个$x$ 和$y$，若$xRy$ 且$yRx$，则$x=y$，称$R$ 是反对称的，即$A上关系R是反对称的 \iff (∀x)(∀y)(x,y∈A且xRy且yRx→x=y)$
• 该定义表明了，在表示反对称关系$R$ 的有序对集合中，若存在有序对$(x, y)$ 和$(y, x)$，则必定是$x=y$。或者说，在$R$ 中若有有序对$(x, y)$，则除非$x=y$，否则必定不会出现$(y, x)$

# 传递性

• 令$R⊆A×A$，对于$A$ 中每个$x, y, z$，若$xRy且yRz$，则$xRz$，称$R$ 是传递的，即$A上关系R是传递的 \iff (∀x)(∀y)(∀z)(x,y,z∈A且xRy且yRz→xRz)$
• 该定义表明了，在表示可传递关系$R$ 的有序对集合中，若有有序对$(x, y)$ 和$(y, z)$，则必有有序对$(x, z)$

# 结论

• 关系$R$ 是自反的$\implies$ $R$ 不是反自反的
• 关系$R$ 是自反的$\iff$ 关系图中每个结点都有环
• 关系$R$ 是反自反的$\iff$ 关系图中每个结点都无环
• 关系$R$ 是自反的$\iff$ 关系矩阵的主对角线上全为 1
• 关系$R$ 是反自反的$\iff$ 关系矩阵的主对角线上全为 0
• 关系$R$ 是对称的$\iff$ 关系图中任何一对结点之间，要么有方向相反的两条边，要么无任何边
• 关系$R$ 是反对称的$\iff$ 关系图中任何一对结点之间，至多有一条边
• 关系$R$ 是对称的$\iff$ $R$ 的关系矩阵为对称矩阵
• 关系$R$ 是反对称的$\iff$ $R$ 的关系系矩阵满足$r_{ij}\cdot r_{ji}＝0，i,j=1,2,…,n，i≠j$
• 非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的
• 非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的
• 设$R⊆A×A$，若$R$ 是反自反的和传递的，则$R$ 是反对称的

# 闭包运算

# 自反闭包

• 设$R$ 是$A$ 上的二元关系，若$R'$ 是$R$ 的自反闭包，记作$r(R)$，则：
  • $R'$ 是自反的
  • $R⊆R'$
  • 对任意的自反关系$R''$，$R⊆R''$，则必有$R'⊆R''$

# 对称闭包

• 设$R$ 是$A$ 上的二元关系，若$R'$ 是$R$ 的对称闭包，记作$s(R)$，则：
  • $R'$ 是对称的
  • $R⊆R'$
  • 对任意的对称关系$R''$，$R⊆R''$，则必有$R'⊆R''$

# 传递闭包

• 设$R$ 是$A$ 上的二元关系，若$R'$ 是$R$ 的传递闭包，记作$t(R)$，则：

  • $R'$ 是传递的
  • $R⊆R'$
  • 对任意的传递关系$R''$，$R⊆R''$，则必有$R'⊆R''$

# 定理

• R 是 X 上的二元关系，则：
  • $r(R)=R∪\{(x,x)|x∈X\}=R∪I_x$
  • $s(R) = R∪ \overline{R}$
  • $t(R)=R∪ R^{(2)}∪ R^{(3)}...∪ R^{(n)}$，$n$ 为集合$X$ 的元素的个数
  • $R$ 是自反的$\iff$ $r(R)$
  • $R$ 是对称的$\iff$ $s(R)=R$
  • $R$ 是传递的$\iff$ $t(R)$

# 等价关系

# 定义

• 设$R$ 是集合$X$ 上的二元关系，如果$R$ 是自反的、对称的、传递的，那么称$R$ 是等价关系

# 划分

• 设集合$A=\{S_1, S_2 , …, S_m\}$,$S_i$ 是$S$ 的非空子集，如果称$A$ 是$S$ 的一个划分，称$S_i$ 为划分的块，则：
  • $S_i$ 之间是不相交的
  • $S_1∪S_2∪…∪S_m = S$

# 等价类

# 定义

• $R$ 是集合$S$ 上的等价关系，对任一$x\in S$，均可构造一个$S$ 的非空子集$[x]_R= \{ y | y\in S 且 xRy \}$，也可记为$[x]$，叫做$x$ 关于$R$ 的等价类:

# 性质

• $x\in[x]$
• 若$y\in[x]$, 则$[y]=[x]$
• 若$y\in[x]$, 则$[y]∩[x]=\varnothing$

# 定理

• 集合$S$ 上的一个等价关系$R$ 生成的等价类集合对应$S$ 的一个划分
• 集合$S$ 上的一个等价关系$R$ 生成的等价类集合对应$S$ 的一个划分。此划分称为集合$S$ 关于$R$ 的商集，记为$S/R$
• 集合$S$ 上的一个划分可产生$S$ 上的一个等价关系

# 偏序关系

# 定义

• 设$R$ 是集合$A$ 中的二元关系，如果$R$ 是自反的、反对称的和可传递的，则称$R$ 是$A$ 中的偏序关系。
• 通常用符号 “$≼$” 来标记偏序关系$R$

# 偏序集

• 在偏序集合$(A ,≼ )$ 中，如果有元素$x,y∈A$, 且$x≼ y$ (或者写为$(x,y)∈≼$) 和$x≠y$, 同时不存在其它任何元素$z∈A$，能使$x≼ z$ 和$z≼ y$, 则称元素$y$ 盖住$x$，若元素$y$ 盖住$x$，则可以将$x,y$ 间的关系用图形表示，即：哈斯图

# 哈斯图

• 用小圆圈表示$A$ 中的元素
• 若$x≼y$ 且$x≠y$, 则$x$ 在$y$ 的下方
• 若$x≼y$ 且$x≠y$, 并且$A$ 中不存在另外的元素$z$, 满足$x≼z$,$z≼y$, 则在$x$ 与$y$ 之间画一直线

# 拟序关系

• 设$R$ 是集合$A$ 中的反自反和传递的二元关系，则称$R$ 是$A$ 中的拟序关系 (“$≺$”)

# 全序和全序集

• 设$≼$是$A$ 中的偏序关系，若对任意的$x,y∈A$，必有$x ≼ y$ 或$y ≼ x$，即$x$ 和$y$ 可比较，则称$≼$是$A$ 中的线性次序关系或全序关系，又称全序或线性序。相应的偏序集$(A,≼)$ 称为线性序集或全序集
• 显然，任一全序集也是偏序集，其哈斯图为一条链，
  但是任一偏序集不一定是全序集合

# 最大（小）元素

• 设$( X, ≼ )$ 是偏序集，$Y$ 是$X$ 的子集。若存在元素$y∈ Y$, 对于每一个$y' ∈ Y$，
  • 若有$y' ≼ y$，则称$y$ 是集合$Y$ 的最大元素
  • 若有$y ≼y'$，则称$y$ 是集合$Y$ 的最小元素

# 性质

• 设$( X, ≼ )$ 是偏序集，$Y$ 是$X$ 的子集，如果$Y$ 有最大（最小）元素，则必定是唯一的

# 极大（小）元素

• 设$( X, ≼)$ 是偏序集，$Y$ 是$X$ 的子集，若$y ∈ Y$，且不存在$y' ∈ Y$，$y≠ y'$，
  • 若有$y ≼ y'$，则称$y$ 是$Y$ 的极大元素
  • 若有$y' ≼ y$，则称$y$ 是$Y$ 的极小元素

# 上（下）界

• 设$( X, ≼ )$ 是偏序集，$Y\subseteq X$，若$x ∈ X$，使得对任意$y' ∈ Y$,
  • 若有$y'≼x$，则称$x$ 是$Y$ 的上界
  • 若有$x ≼ y'$，则称$x$ 是$Y$ 的下界

# 上（下）确界

• 设$( X, ≼ )$ 是偏序集，$Y$ 是$X$ 的子集。
  • $x$ 是$Y$ 的上界，若对$Y$ 的任一上界$x'$，都有$x ≼x'$，则称$x$ 是$Y$ 的上确界，记作$LUB$ $Y$
  • $x$ 是$Y$ 的下界，若对于$Y$ 的任一下界$x'$，均有$x' ≼x$，则称$x$ 是$Y$ 的下确界，记作$GLB$ $Y$

# 函数

# 函数及其分类

# 函数的定义

• 设$f$ 是集合$A$ 到$B$ 的关系
  若称$f$ 是集合$A$ 到$B$ 的函数或映射，记作$f: A→B$ 或 $A → B$。
  当$(a,b)∈f$ 时，通常记为$b=f(a)$，$b$ 称为$a$ 在$f$ 下的像，称$a$ 为$b$ 的原像。则$f$ 满足下列两个条件：
  • 对每个$a∈A$，必存在$b∈B$，使得$(a,b)∈f$—— 存在性条件
  • 对每个$a∈A$，只存在一个$b∈B$，使得$(a,b)∈f$—— 唯一性条件
• 即：值域为函数的像集合

# 函数相等

• 设$f:X→Y$，$g:Z→W$，如果$f$ 和$g$ 具有相同的定义域和值域，即$X=Z$ 和$Y=W$，并且对于所有的$x∈X$ 和$x∈Z$，都有$f(x)=g(x)$，则称函数$f$ 和$g$ 相等，并记作$f=g$

# 函数个数

• 设$A$，$B$ 是非空有限集合，则从$A$ 到$B$ 共有$|B|^{|A|}$ 个不同的函数
• 因为函数是一种特殊的关系，所以一个函数确定一个关系；但一个关系不一定确定一个函数

# 函数的分类

• 设$f: A→B$ 是一个函数：
  • 对任意的$a_1$ 和$a_2∈A$，若$a_1≠a_2$，均有$f(a_1)≠f(a_2)$，则称$f$ 为$A$ 到$B$ 的单射函数或一对一函数；否则，称$f$ 为$A$ 到$B$ 的多对一函数。
  • 如果对任意的$b∈B$，均有$a∈A$，使$b=f(a)$，即$C_f=B$，则$f$ 为$A$ 到$B$ 的满射函数；否则，称$f$ 为$A$ 到$B$ 的内射函数。
  • 如果$f$ 既是$A$ 到$B$ 的单射，又是$A$ 到$B$ 的满射，则称$f$ 为$A$ 到$B$ 的双射函数或一一对应函数。特殊地，在一一对应函数$f: A→B$ 中，若$A=B$，则此函数叫做$A$ 的变换。

# 函数分类结论

• 设 A，B 为有限集合，f 是从 A 到 B 的函数，则：
  • $f$ 是单射的必要条件为$|A|≤|B|$
  • $f$ 是满射的必要条件为$|B|≤|A|$
  • $f$ 是双射的必要条件为$|A|＝|B|$

# 特殊函数

• 设$f$ 是一个函数，若对任意的$a∈A$，均有$f(a)=b$，$b∈B$，则称$f$ 是从$A$ 到$B$ 的常值函数或常函数
• 设$f$ 是一个函数，若对任意的$a∈A$，均有$f(a)=a$，则称$f$ 是$A$ 上的恒等函数
• 设$f:R→R$ 是一个函数，其中$R$ 为实数集，
  • 对任意$a,b∈R$，若$a<b$，必有$f(a)≤f(b)$，则称$f$ 为单调递增函数
  • 对任意$a,b∈R$，若$a<b$，必有$f(a)<f(b)$，则称$f$ 为严格单调递增函数
• 设$U$ 是全集，且$A⊆U$，函数$\Psi _A:U\to \{0,1\}$ 定义为: $\Psi_A=\begin{cases} 1,& a \in A\\ 0,& a \notin A \end{cases}$ 则称$\Psi_A$ 是集合$A$ 的特征函数

# 复合函数与逆函数

# 复合函数

# 复合函数定义

• 函数的合成运算可定义如下：设$f : X→Y$, $g : Y→Z$ 是两个函数，于是合成函数记为$g\circ f : X→Z$
  $\\g\circ f=\{(x,z)|x∈X且z∈Z且存在y∈Y且y=f(x)且z=g(y)\}$ 通常称为函数$f$ 和$g$ 的合成，确切的说，$g\circ f$ 称为$f$ 和$g$ 左合成，从$f$ 和$g$ 求得$g\circ f$ 的运算 “$\circ$” 称为左合成运算
  关系的合成运算为$f\circ g$，函数的合成运算为$g\circ f$

# 复合函数定理

• 函数的合成运算是可结合的
• 设$f$ 和$g$ 是函数，并且有合成函数$g\circ f$, 则
  • 如果$f$ 和$g$ 都是满射函数，则$g \circ f$ 也是满射函数
  • 如果$f$ 和$g$ 都是单射函数，则$g\circ f$ 也是单射函数
  • 如果$f$ 和$g$ 都是双射函数，则$g\circ f$ 也是双射函数

# 逆函数

# 逆函数定义

• 设$f : A→B$ 是一个双射函数，称$f^{-1} : B→A$ 是$f$ 的逆函数
• 在关系部分，曾定义了从集合$X$ 到$Y$ 的关系$R$ 的逆关系，但是对于函数来说，交换序偶中的成员次序并不一定能保证得到的仍然是个函数
• 设$f:A→B$ 是一一对应的函数，则$f$ 的逆关系 称为它的逆函数，记成$f^{-1}: B→A$。这时称函数$f$ 是可逆的

# 逆函数的定理

• 函数$f : A→B$，若存在逆函数$f^{-1} : B→A$，则必须满足：
  • 对任意的$a∈A$，必有唯一的$b∈B$ 与之对应；
  • 对任意的$b∈B$，必有唯一的$a∈A$ 与之对应；

# 代数系统

# 代数系统的基本概念

# 二元运算

# 定义

• 设$A, B, C$ 是非空集合，从$A×B$ 到$C$ 的一个函数$f ：A×B→C$ 称为一个$A×B$ 到$C$ 的二元代数运算，简称二元运算
• 一个二元运算就是一个特殊的函数 ，该函数能够对$a\in A$ 和$b\in B$ 进行运算，得到$C$ 中的一个元素$c$ ， 即 $\circ (a, b)＝c$。
  中缀方法表示为：$a \circ b＝c$

# 特点

# 封闭性

• 如果 “ $\ast$” 是$A×A$ 到$A$ 的二元运算，则称运算 “ $\ast$” 对集合$A$ 是封闭的，或者称 “ $\ast$” 是$A$ 上的二元运算
• 设 “ $\ast$” 是一个$A_1×A_2×…×A_n$ 到$A$ 的$n$ 元代数运算，如果$A_1＝A_2＝…＝A_n＝A$，则称代数运算 “ $\ast$” 对集合$A$ 是封闭的，或者称 “ $\ast$” 是$A$ 上的$n$ 元代数运算

# 代数系统的定义

• 设$A$ 是非空集合， $\ast$ 是定义在$A$ 上$k$ 元封闭运算，称集合$A$ 和 $\ast$ 所组成的系统称为代数系统，简称代数，记为$(A, \ast )$
• 当$A$ 是有限集合时，该代数系统称为有限代数系统，否则称为无限代数系统
• 注意：判断集合$A$ 和其上的代数运算是否是代数系统，关键是判断两点：
  • 集合$A$ 非空
  • 这些运算关于$A$ 是否满足封闭性

# 同类型代数系统

• 设$(A, \ast )$ 和$(B, \circ )$ 是两个代数系统，若 “$\circ$” 和 “ $\ast$” 都是$k$ 元运算，$i = 1, 2, …, m$，则称这两个代数同类型

# 运算规律

# 结合律

• 设$(A, \ast )$ 是二元代数系统，若对任意$a, b, c∈A$，都有
  $(a \ast b) \ast c＝a \ast (b \ast c)$
  则称 “ $\ast$” 在$A$ 上是可结合的，或称满足结合律

# 交换律

• 设$(A, \ast )$ 是二元代数系统，若对任意$a, b∈A$，都有
  $a \ast b＝b \ast a$
  则称 “ $\ast$” 在$A$ 上是可交换的，或称 “ $\ast$” 满足交换律

# 消去律

• 设$(A, \ast )$ 是二元代数系统，元素$a∈A$，
  • 对任意$x, y∈A$，都有如果$a \ast x = a \ast y$，那$x = y$，则称$a$ 在$A$ 中关于 “ $\ast$” 是左可消去元
  • 对任意$x, y∈A$，都有如果$x \ast a = y \ast a$，那么$x = y$，则称$a$ 在$A$ 中关于 “ $\ast$” 是右可消去元
  • 如果$a$ 既是$A$ 左可消去元又是右可消去元，则称$a$ 是$A$ 的可消去元
  • 若$A$ 中所有元素都是可消去元，则称 “ $\ast$” 在$A$ 上可消去，或称 “ $\ast$” 满足消去律

# 幂等律

• 设$(A, \ast )$ 是二元代数系统，若元素$a∈A$，满足$a \ast a=a$ 则称$a$ 是$A$ 中关于 “ $\ast$” 的一个幂等元，简称$a$ 为幂等元。若$A$ 中的每一个元素都是幂等元，则称 “ $\ast$” 在$A$ 中是幂等的，或称 “ $\ast$” 满足幂等律

# 幂

• 设 “ $\ast$” 是集合$A$ 上可结合的二元运算，$a∈A$，则$a \ast a∈A，a \ast a \ast a∈A，…，$由此，可以归纳定义$a$ 的正整数幂方：
  $a^1 = a，a^2 = a \ast a，a^3 = a^2 \ast a，… ， a^n = a^{n-1} \ast a，…$
• 对任意正整数$n$，$m$，有以下等式：$a^n \ast a^m = a^{n+m}， (a^n)^m = a^{nm}$

# 分配律

• 设 “ $\ast$”、“$\circ$” 是集合 A 上的二元运算，$(A, \ast , \circ)$ 是一个代数系统， 对任意$a,b,c\in A$，
  • $a\circ (b \ast c)=(a\circ b) \ast (a\circ c)$，
    则称运算 “$\circ$” 对 “ $\ast$” 在$A$ 上满足左分配律 (或第一分配律)
  • $(b \ast c) \circ a=(b\circ a) \ast (c\circ a)$，
    则称运算 “$\circ$” 对 “ $\ast$” 在$A$ 上满足右分配律 (或第二分配律)
  • 如果 “$\circ$” 对 “ $\ast$” 既满足左分配律又满足右分配律，则称 “$\circ$” 对 “ $\ast$” 在$A$ 上满足分配律

# 吸收律

• 设 “ $\ast$”、“$\circ$” 是集合$A$ 上的二元运算，$(A, \ast , \circ )$ 是一个代数系统，如果对任意$x, y∈A$，都有$x \ast (x \circ y) = x，x \circ(x \ast y) = x$
  则称 “ $\ast$” 和 “$\circ$” 满足吸收律

# 特殊元

# 特殊元的定义

• 在代数系统中，有些元素有特殊性质，叫特殊元

# 单位元

• 设$(A, \ast )$ 是二元代数系统，
  • 若存在$e∈A$，对任意$a∈A$，都有 $a \ast e = e \ast a = a$，则称$e$ 是$A$ 中关于运算 “ $\ast$” 的一个单位元
  • 若存在$e_l∈A$，使得对任意$a∈A$，都有 $e_l \ast a = a$，则称$e_l$ 是$A$ 中关于运算 “ $\ast$” 的一个左单位元
  • 若存在$e_r∈A$，使得对任意$a∈A$，都有 $a \ast e_r = a$，则称$e_r$ 是$A$ 中关于运算 “ $\ast$” 的一个右单位元

# 零元

• 设$(A, \ast )$ 是一个二元代数系统，
  • 若存在$θ∈A$，使得对任意$a∈A$，都有$a \ast θ = θ \ast a =θ$，则称$θ$ 是$A$ 中关于运算 “ $\ast$” 的一个零元
  • 若存在$θ_l∈A$，使得对任意$a∈A$，都有$θ_l \ast a = θ_l$，则称$θ_l$ 是$A$ 中关于运算 “ $\ast$” 的一个左零元
  • 若存在$θ_r∈A$，使得对任意$a∈A$，都有$a \ast θ_r = θ_r$，则称$θ_r$ 是$A$ 中关于运算 “ $\ast$” 的一个右零元。

# 逆元

• 设$(A, \ast )$ 是二元代数系统，$e$ 是幺元，$a∈A$，若存在一个元素$b∈A$，
  • 使得：$a \ast b = b \ast a = e$，则称$a$ 可逆，并称$b$ 是$a$ 的一个逆元，记为$a^{-1}$
  • 使得：$b \ast a = e$，则称$a$ 左可逆，并称$b$ 是$a$ 的一个左逆元，记为$a_l^{-1}$
  • 使得：$a \ast b = e$，则称$a$ 右可逆，并称$b$ 是$a$ 的一个右逆元，记为$a_r^{-1}$

# 定理

• 设$(A, \ast )$ 是一个代数系统，“ $\ast$” 满足结合律，$a∈A$，$a$ 可逆，则$a$ 是可消去元
• 设$(A, \ast )$ 是二元代数系统，
  • 如果$(A, \ast )$ 存在单位元，则单位元唯一
  • 如果$(A, \ast )$ 存在单位元，则该单位元一定是左、右单位元
  • 如果$(A, \ast )$ 存在左、右单位元，则该左、右单位元相等，且是单位元。
• 设$(A, \ast )$ 是二元代数系统，
  • 如果$(A, \ast )$ 存在零元，则零元唯一
  • 如果$(A, \ast )$ 存在零元，则该零元一定是左、右零元
  • 如果$(A, \ast )$ 存在左、右零元，则该左、右零元相等，且是零元。
• 设$(A, \ast )$ 是二元代数系统，“ $\ast$” 满足结合律且设$e$ 是单位元，则对任意$a∈A$，
  • 如果$a$ 存在逆元，则逆元唯一
  • 如果$a$ 存在逆元，则该逆元一定是左、右逆元
  • 如果$a$ 存在左、右逆元，则该左、右逆元相等，且是逆元。
• 设$(A, \ast )$ 是二元代数系统，“ $\ast$” 满足结合律，$a, b∈A$，
  • 如果$a, b$ 分别有逆元$a^{-1}, b^{-1}$，则$(a \ast b)^{-1} = b^{-1} \ast a^{-1}$
  • 如果$a$ 是左（或右）可逆的元素，则$a$ 是左（或右）可消去的元素
  • 如果$a$ 是可逆的元素，则$a$ 是可消去的元素

# 同构

# 同构的定义

• 在现实社会中，存在着很多代数系统，但仔细分析这些众多的代数系统发现，有些代数系统，他们之间表面上似乎不相同，但他们本质上是 “相同” 的

# 同构的条件

• 必须是同型代数系统
• 两个集合的元素个数应相等
• 运算定义法则相同，即对应元素运算后的结果也对应

# 同态

# 同态的定义

• 设$(A, \ast )$ 和$(B, \circ)$ 为两个二元代数系统，$g$ 是$A$ 到$B$ 的函数。对任意$x, y∈A$，都有$g(x \ast y) = g(x) \circ g(y)$，则称$g$ 是从$(A, \ast )$ 到$(B, \circ)$ 的同态映射，称$g(A)$ 为同态像，其中$g(A) = \{g(x) | x∈A\}$。如果存在一个从$(A, \ast )$ 到$(B, \circ )$ 的同态映射，则称$(A, \ast )$ 与$(B, \circ )$ 同态，记为$(A, \ast )∽(B, \circ )$。当$(A, \ast )= (B, \circ )$ 时，称其同态为自同态
• 当同态映射$g$ 分别是单射、满射、双射时，分别称$g$ 是单一同态映射、满同态映射、同构映射
• 如果存在一个从$(A, \ast )$ 到$(B, \circ )$ 的同构映射（单一同态映射、满同态映射），则称代数系统$(A, \ast )$ 与$(B, \circ )$ 同构（单一同态、满同态）。
  用$(A, \ast )≌(B, \circ )$ 表示$(A, \ast )$ 与$(B, \circ )$ 同构

# 命题逻辑

# 命题与命题联结词

# 命题

• 具有真假意义的陈述句称为命题
• 命题可以取一个 “值”，称为真值
• 真值只有 “真” 和 “假” 两种，分别用 “$Ｔ$”(或 “$１$”) 和 “$Ｆ$”(或 “$０$) 表示

# 命题的分类

• 原子命题 (简单命题)：不能再分解为更为简单命题的命题
• 复合命题：可以分解为原子命题的命题，这些原子命题之间通过如 “或者”、“并且”、“不”、“如果... 则...”、“当且仅当” 等这样的关联词和标点符号复合而构成一个复合命题。（优先级：否定→合取→析取→蕴涵→等价）

# 命题联结词

# 否定$\neg$

• 设$P$ 是任一命题，复合命题 “非$P$”(或 “$P$ 的否定”) 称为$P$ 的否定式 (Negation)，记作$\neg P$，“$\neg$” 为否定联结词

# 合取$\wedge$

• 设$P$、$Q$ 是任两个命题，复合命题 “$P并且Q$”(或 “$P和Q$”) 称为$P$ 与$Q$ 的合取式 (Conjunction)，记作$P∧Q$，“$∧$” 为合取联结词

# 析取$\vee$

• 设$P$、$Q$ 是任两个命题，复合命题 “$P或者Q$” 称为$P$ 与$Q$ 的析取式 (Disjunction)，记作$P∨Q$，“$∨$” 为析取联结词

# 蕴涵$→$

• 设$P$、$Q$ 是任两个命题，复合命题 “$如果P，则Q$” 称为$P$ 与$Q$ 的蕴涵式 (Implication)，记作$P→Q$，“$→$” 称为蕴涵联结词，$P$ 称为蕴涵式的前件，$Q$ 称为后件

# 等价$\leftrightarrow$

• 设$P、Q$ 是任两个命题，复合命题 “$P当且仅当Q$” 称为$P$ 与$Q$ 的等价式 (Equivalence)，记作$P\leftrightarrow Q$，“$\leftrightarrow$” 称为等价联结词

# 说明

• 联结词与自然语言之间的对应并非一一对应：
  • 合取联结词 “$∧$” 对应自然语言的 “既… 又…”、“不仅… 而且…”、“虽然… 但是…”、“并且”、“和”、“与” 等
  • 蕴涵联结词 “$→$”,“$P→Q$” 对应自然语言中的 “如 P 则 Q” , “只要 P 就 Q”,“P 仅当 Q”,“只有 Q 才 P”,“除非 Q 否则$\neg$ P” 等
  • 等价联结词 “$↔$” 对应了自然语言中的 “等价”、“当且仅当”、“充分必要” 等
  • 析取联结词 “$\vee$” 对应的是相容（可兼）的或
  • 否定联结词 “$\neg$” 是自然语言中的 “非”、“不” 和 “没有” 等
• 当前件$P$ 为假时，不管$Q$ 的真假如何，则$P→Q$ 都为真。此时称为 “善意推定”
• 复合命题的真值只取决于构成他们的各原子命题的真值，而与它们的内容、含义无关，与联结次所连接的两原子命题之间是否有关系无关

# 命题公式与符号化

# 命题公式的定义

• 一个特定的命题是一个常值命题，它不是具有值 “T”(“1”)，就是具有值 “F”(“0”)
• 一个任意的没有赋予具体内容的原子命题称为命题变量 (或命题变元)，该命题变量无具体的真值，它的变域是集合$\{T，F\}$(或$\{0，1\}$)
• 当原子命题是命题变元时，此复合命题也即为命题变元的 “函数”，且该 “函数” 的值仍为 “真” 或 “假” 值，这样的函数可形象地称为 “真值函数”, 或称为命题公式，此命题公式没有确切真值

# 公式的解释

# 定义

• 设$P_1、P_2、…、P_n$ 是出现在公式$G$ 中的所有命题变元，指定$P_1、P_2、…、P_n$ 一组真值，则这组真值称为$G$ 的一个解释，常记为$I$

# 性质

• 一般来说，若有$ｎ$个命题变元，则应有$2^n$ 个不同的解释
• 如果公式$G$ 在解释$I$ 下是真的，则称$I$ 满足$G$；如果$G$ 在解释$I$ 下是假的，则称$I$ 弄假$G$

# 真值表

# 定义

• 将公式$G$ 在其所有可能解释下的真值情况列成的表，称为$G$ 的真值表

# 公式的等价性

# 基本等价式

# 交换律

• $P∧Q\iff Q∧P$
• $P∨Q\iff Q∨P$
• $P\leftrightarrow Q\iff Q\leftrightarrow P$

# 结合律

• $(P∧Q)∧R\iff P∧(Q∧R)$
• $(P∨Q)∨R\iff P∨(Q∨R)$
• $(P\leftrightarrow Q)\leftrightarrow R\iff P\leftrightarrow (Q\leftrightarrow R)$

# 分配律

• $P∧(Q∨R)\iff (P∧Q)∨(P∧R)$
• $P∨(Q∧R)\iff(P∨R)∧(P∨R)$

# 否定深入

• $\neg \neg P \iff P$
• $\neg (P∧Q) \iff \neg P∨ \neg Q$
• $\neg (P\vee Q) \iff \neg P\wedge \neg Q$
• $\neg (P → Q)\iff P ∧ \neg Q$
• $\neg(P \leftrightarrow Q) \iff \neg P \leftrightarrow Q \iff P \leftrightarrow \neg Q$

# 联结词化归

• $P∧Q\iff \neg（\neg P∨\neg Q）$
• $P∨Q\iff \neg （\neg P∧\neg Q）$
• $P→Q\iff \neg P∨Q$
• $P \leftrightarrow Q \iff (P→Q)∧(Q→P) \iff (\neg P∨Q) ∧(\neg Q∨P) \iff (P ∧ Q) ∨(\neg P ∧ \neg Q)$

# 命题与集合的关系

• 将$G，H$ 理解为某总体论域上的子集合，而规定$G∧H$ 为两集合的公共部分（交集），$G∨H$ 为两集合的全部（并集），$\neg G$ 为总体论域（如矩形域）中$G$ 的补集，将命题中的真值 “1” 理解为集合中的总体论域（全集），将命题中的真值 “0” 理解为集合中的空集

# 永真式、永假式与蕴含式

# 定义

• 公式 G 称为永真式，如果在它的所有解释之下都为 “真”
• 公式 G 称为永假式，如果在它的所有解释之下都为 “假”
• 公式 G 称为可满足的，如果它不是永假的

# 公式等价

# 定义

• 设 G、H 是公式，如果在任意解释 I 下，G 与 H 的真值相同，则称公式 G、H 是等价的，记作$G\iff H$

# 定理

• $G\iff H$ 等价的充分必要条件为$G\implies H$ 且$H\implies G$
• 公式 G、H 等价的充分必要条件是公式$G\iff H$ 是永真公式

# 性质

• 由于 “$\iff$” 不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：
  • 自反性 G=G
  • 对称性 若 G=H，则 H=G
  • 传递性 若 G=H，H=S，则 G=S

# 命题逻辑推理

# 基本蕴含式

• $(P \to Q) \land (Q \to R) \implies P \to R$ (假言三段论)

# 定理

• 若前提集合为$\{ H_1，H_2，…，H_m \}$, 结论为$P→ Q$ ，则$\{ H_1，H_2，…，H_m \}\implies P\to Q$ 等价于$\{H_1，H_2，…，H_m，P\}\implies Q$ (CP 规则)

# 推理规则

• $P \to Q, Q \to R \vdash P \to R$

# 公式蕴涵的证明方法

• 真值表法
• 证$G \to H$ 是恒真公式
• 利用一些基本等价式及蕴涵式进行推导
• 任取真值 I，若 I 满足 G，往证 I 满足 H
• 反证法，设结论假，往证前提假

# 三个基本推理规则

• P 规则 (前提引入规则)：前提总是可用
• T 规则 (推理引入规则)：推理中允许使用推理规则，所得结果在后面的推理中可用
• CP 规则 (附加前提引入规则) ：证明$P\to Q$ 时可将 P 作为附加前提引入

# 范式

# 定义

# 合取式

• 在一公式中，仅由命题变元及其否定构成的合取，称该公式为合取式
• 其中每个命题变元或其否定，称为合取项

# 析取式

• 在一公式中，仅由命题变元及其否定构成的析取，称该公式为析取式
• 其中每个命题变元或其否定，称为析取项

# 析取范式

• 一个命题公式 A 称为析取范式可表示为：多个合取式的析取

# 合取范式

• 一个命题公式 A 称为合取范式可表示为：多个析取式的合取

# 定理

• 合取式为永假式的充要条件是：它同时含有某个命题变元及其否定
• 析取式为永真式的充要条件是：它同时含有某个命题变元及其否定
• 对于任何一命题公式，都存在与其等价的析取范式和合取范式

# 范式的应用

• 公式 A 为永假式的充要条件是其析取范式中每个简单合取式至少包含一个命题变元及其否定
• 公式 A 为永真式的充要条件是其合取范式中每个简单析取式至少包含一个命题变元及其否定

# 公式的主范式

# 最小项

• 在含有 n 个命题变元的合取式中， 若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该合取式为最小项
• n 个命题变元共形成$2^n$ 个最小项
• 任意两个不同的最小项的合取式是永假的：$m_i∧m_j\iff F,i≠j$
• 所有最小项之析取为永真：$\bigvee\limits_{i=1}^n m_i \iff T$
• 每个最小项只有一个真值组合为真

# 最大项

• 在 n 个命题变元的析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该析取式为最大项
• 任何两个不同最大项之析取是永真的，即：$M_i∨M_j\iff T,i≠j$
• 所有最大项之合取为永假，即：$\bigwedge\limits_{i=1}^n M_i \iff F$
• 每个最大项只有一个真值组合为假，且其真值 0 位于主对角线上

# 主析取范式

• 在给定公式的析取范式中，若其合取式都是最小项，则称该范式为主析取范式
• 任意含 n 个命题变元的非永假命题公式 A，都存在与其等价的主析取范式
• 任意含 n 个命题变元的非永假命题公式，其主析取范式是惟一的

# 主合取范式

• 在给定公式的合取范式中，若其所有简单析取式都是最大项，称该范式为主合取范式
• 任意含有 n 个命题变元的非永真命题公式 A，都存在与其等价的主合取范式
• 任意含 n 个命题变元的非永真命题公式 A，其主合取范式是唯一的

# 求法

• 公式化归法
• 真值表法

# 主析取范式与主合取范式之间的关系

• 由于主范式是由最小项或最大项构成，由其定义，可知两者有下列关系：$\neg m_i\iff M_i, \neg M_i\iff m_i$
• 因此，主析取范式和主合取范式有着 “互补” 关系，即由公式的主析取范式可以求出其主合取范式

# 主范式的应用

• 根据主范式的定义和定理，可以判定含 n 个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按下列条件判定之：
  • 若$A\iff Ｔ$，或 A 可化为与其等价的、含$2^n$ 个最小项的主析取范式，则 A 为永真式
  • 若$A\iff Ｆ$，或 A 可化为与其等价的、含$2^n$ 个最大项的主合取范式，则 A 为永假式
  • 若 A 不与Ｔ或者Ｆ等价，且又不含$2^n$ 个最小项或最大项，则 A 为可满足的
• 由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的

# 推理规则

# “$\implies$” 与 “$\to$” 的不同

• “$→$” 仅是一般的蕴涵联结词，$G→H$ 的结果仍是一个公式，而 “$\implies$” 却描述了两个公式 G，H 之间的一种逻辑蕴涵关系，$G\implies H$ 的 “结果”，是非命题公式
• 用计算机来判断$G\implies H$ 是办不到的。然而计算机却可 “计算” 公式$G→H$ 是否为永真公式

# 谓词逻辑

# 谓词逻辑基本概念

# 谓词

# 定义

• 用以刻划客体的性质或客体之间的关系即是谓词

# 简单命题函数

• 由一个谓词和一些客体变元组成的表达式.
  $A(x_1，x_2,…,x_n)$ 称 n 元命题函数或 n 元原子谓词公式，n 元谓词就是有 n 个客体变元的命题函数

# 复合命题函数

• 由一个或 n 个简单命题函数以及联结词组成的表达式

# 结论

• 谓词中个体词的顺序是十分重要的，不能随意变更。如命题$F(b, c)$ 为 “真”，但命题$F(c, b)$ 为 “假”
• 一元谓词用以描述某一个个体的某种特性，而 n 元谓词则用以描述 n 个个体之间的关系
• 0 元谓词 (不含个体词的) 实际上就是一般的命题
• 具体命题的谓词表示形式和 n 元命题函数 (n 元谓词) 是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中 S (a) 是有真值的，但 S (x) 却没有真值
• 一个 n 元谓词不是一个命题，但将 n 元谓词中的个体变元都用个体域中具体的个体取代后，就成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响

# 客体

• 客体变元在哪些范围内取值（称客体），对是否成为命题及命题的真值都有影响
• 在命题函数中，命题变元的论述范围称作个体域，个体域可以是有限的，也可以是无限的，把各种个体域综合在一起作为论述范围的域称为全总客体域

# 量词

# 全称量词$\forall$

• $\forall$ 称为全称量词，“对所有的” ,“每一个”, “对任一个”

# 存在量词$\exists$

• $\exists$ 称为存在量词，“存在一个”，“有一个”，“对于一些”

# 特性谓词

• 限定客体变元变化范围的谓词

# 注意

• 由量词确定的表达式，都与个体域有关
• 用全总个体域，对每个的客体变元变化范围，用特性谓词加以限制，一般地：
  • 对全称量词，特性谓词常作条件的前提条件
  • 对存在量词，特性谓词常作合取项

# 谓词逻辑符号化的两条规则

• 统一个体域为全总个体域，而对每一个句子中个体变量的变化范围用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：
  • 对于全称量词 ($\forall x$)，刻划其对应个体域的特性谓词作为蕴涵式之前件加入
  • 对于存在量词 ($\exists x$)，刻划其对应个体域的特性谓词作为合取式之合取项加入

# 谓词公式翻译

# 谓词演算的逻辑公式

• 原子谓词公式是逻辑公式，如 Q，A (x)，A (x,y)，...
• 若$A$ 是逻辑公式，则$\neg A$ 也是逻辑公式
• 若 A,B 是逻辑公式，则$A∧B$，$A∨B$，$A→B$，$A\leftrightarrow B$ 也是逻辑公式
• 若 A 是逻辑公式，x 是 A 中出现的任何变元，则$\forall xA$ 和$\exists xA$ 也是逻辑公式

# 约束变元与自由变元

# 约束部分

• 在谓词公式中，形如$\forall x P(x)$ ，$\exists x P(x)$ 的部分，称为谓词公式的 x 约束部分
  • $\forall \exists$ 后的 x 叫量词的指导变元或作用变元
  • P (x) 叫做相应量词的作用域或辖域

# 约束出现

• 在作用域中 x 的一切出现，称为 x 在公式中的约束出现
  • 所有约束出现的变元叫做约束变元
  • 不受约束的变元为自由变元

# n-k 元谓词和有关命题

• $P(x_1,x_2,...,x_n)$ 是 n 元谓词，有 n 个独立的自由变元。若对其中 k 个变元进行约束，则称为 n-k 元谓词。若没有自由变量出现，则该式就成为有关命题

# 变元换名规则

• 换名范围：量词中的指导变元和作用域中出现的该变元。公式中其余部分不变
• 要换成作用域中没有出现的变元名称

# 变元代入规则

• 对该自由变元每一处进行代入
• 代入的变元与原公式中所有变元名称不能相同

# 谓词演算的等价式和蕴含式

# 基本概念

# 等价

• 任意给定两个谓词公式 A 和 B , E 为它们共同的个体域，若对 A 和 B 的任一组变元进行赋值，所得命题真值相同，则称 A 和 B 在 E 上是等价的，
  记为$A\iff B$

# 永真的 (有效的)

• 给定任意谓词公式 A，其个体域为 E 对于 A 的所有赋值 A 都真，则称 A 在 E 上是永真的 (有效的)

# 可满足的

• 一谓词公式 A ，若至少在一种赋值下为真，则称 A 在 E 上是可满足的

# 命题公式的推广

• 当用谓词演算中的公式代替命题演算中永真式的变元时，所得公式为有效公式
  • $∀𝑥(𝑃(𝑥)→𝑄(𝑥))\iff ∀𝑥(¬𝑃(𝑥)∨𝑄(𝑥))$
• 量词与否定联结词$\neg$ 间的关系：量词前的否定，是否定被量化了的整个命题
  • $¬∀𝑥𝑃(𝑥)\iff ∃𝑥¬𝑃(𝑥)$
  • $¬∃𝑥𝑃(𝑥)\iff ∀𝑥¬𝑃(𝑥)$
• 量词作用域的扩张与收缩
  • $∀𝑥(𝐴(𝑥)∨𝐵)\iff ∀𝑥𝐴(𝑥)∨𝐵$
  • $∀𝑥(𝐴(𝑥)∧𝐵)\iff ∀𝑥𝐴(𝑥)∧𝐵$
  • $∀𝑥(𝐴(𝑥)→𝐵)\iff ∃𝑥𝐴(𝑥)→𝐵$
  • $∀𝑥(𝐵→𝐴(𝑥))\iff 𝐵→∀𝑥𝐴(𝑥)$
  • $∃𝑥(𝐴(𝑥)∨𝐵)\iff ∃𝑥𝐴(𝑥)∨𝐵$
  • $∃𝑥(𝐴(𝑥)∧𝐵)\iff ∃𝑥𝐴(𝑥)∧𝐵$
  • $∃𝑥𝐴(𝑥)→𝐵\iff ∀𝑥(𝐴(𝑥)→𝐵)$
  • $∃𝑥(𝐵→𝐴(𝑥))\iff 𝐵→∃𝑥𝐴(𝑥)$
• 量词分配律
  • $∀𝑥(𝐴(𝑥)∧𝐵(𝑥))\iff ∀𝑥𝐴(𝑥)∧∀𝑥𝐵(𝑥)$
  • $∃𝑥(𝐴(𝑥)∨𝐵(𝑥))\iff ∃𝑥𝐴(𝑥)∨∃𝑥𝐵(𝑥)$
  • $∀𝑥𝐴(𝑥)∨∀𝑥𝐵(𝑥)\implies ∀𝑥(𝐴(𝑥)∨𝐵(𝑥))$
  • $∃𝑥(𝐴(𝑥)∧𝐵(𝑥))\implies ∃𝑥𝐴(𝑥)∧∃𝑥𝐵(𝑥)$
• 含多个变元的等价式和蕴含式
  • $∀𝑥∀𝑦𝑃(𝑥,𝑦)\iff ∀𝑦∀𝑥𝑃(𝑥,𝑦)$
  • $∀𝑥∀𝑦𝑃(𝑥,𝑦)\implies ∃𝑦∀𝑥𝑃(𝑥,𝑦)$
  • $∀𝑦∀𝑥𝑃(𝑥,𝑦)\implies ∃𝑥∀𝑦𝑃(𝑥,𝑦)$
  • $∃𝑦∀𝑥𝑃(𝑥,𝑦)\implies ∀𝑥∃𝑦𝑃(𝑥,𝑦)$
  • $∃𝑥∀𝑦𝑃(𝑥,𝑦)\implies ∀𝑦∃𝑥𝑃(𝑥,𝑦)$
  • $∀𝑥∃𝑦𝑃(𝑥,𝑦)\implies ∃𝑦∃𝑥𝑃(𝑥,𝑦)$
  • $∀𝑦∃𝑥𝑃(𝑥,𝑦)\implies ∃𝑥∃𝑦𝑃(𝑥,𝑦)$
  • $∃𝑥∃𝑦𝑃(𝑥,𝑦)\iff ∃𝑦∃𝑥𝑃(𝑥,𝑦)$

# 谓词逻辑的推理理论

# 规则

• 设 A (x) 是谓词公式
  • 全称移去规则 US (全称指定)：$∀𝑥𝐴(𝑥)⇒𝐴(𝑐)$，c 是论域中某个任意客体
  • 全称附加规则 UG (全称推广)：$𝐴(𝑐)⇒∀𝑥𝐴(𝑥)$，每个 c, $A(c)$ 为真
  • 存在移去规则 ES (存在指定)：$∃𝑥𝐴(𝑥)⇒𝐴(𝑐)$，c 是论域中使$A(c)$ 为真的客体
  • 存在附加规则 EG (存在推广)：$𝐴(𝑐)⇒∃𝑥𝐴(𝑥)$，c 是论域中使$A(c)$ 为真的客体

# 谓词演算的综合推理方法

• 推导过程中可以引用命题演算中的 P 规则 和 T 规则
• 如果结论是以蕴涵形式 (或析取形式) 给出，我们还可以使用 CP 规则
• 若需消去量词，可以引用 US 规则和 ES 规则
• 当所要求的结论可能被定量时，此时可引用 UG 规则和 EG 规则将其量词加入
• 证明时可采用如命题演算中的直接证明方法和间接证明方法
• 在推导过程中，对消去量词的公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式
• 在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式

# 图的基本概念

# 图与子图

# 图的定义

• 图 G 是由非空集合$V=\{v_1,v_2,…,v_n\}$，以及边的集合$E=\{l_1,l_2,…,l_m\}$ 所组合，其中每条边可用一个结点对表示，即：$l_i=(v_{i1},v_{i2}),i=1,2,…,m$，这样的图 G 可用$G=(V，E)$ 表示

# 图的基本概念

# 有向图

• 图中的所有边均为有向边，有向边$l_k=<v_i,v_j>$, $v_i$ 为起点，$v_j$ 为终点，箭头指向终点

# 无向图

• 图中的所有边均为无向边

# 邻接与环

• 多条边关联于同一个结点，则这些边称为邻接的
• 构成边的一对结点之间称为邻接的
• 若一条边由相同的结点构成，则称为环$(v_i,v_i)$

# 零图与平凡图

• 仅含一些孤立点的图称为零图
• 特别，仅含一个孤立点的零图称为平凡图

# 多重图与线图

• 有相同端点（起终点）的两条无（有）向边叫做重边
• 含重边的图称为多重图
• 非多重图称为线图
• 不含自环和重边的图称为简单图（无自环的线图）

# 完全图

• 每对结点间都有一条无向边（一对方向相反的有向边）的简单图，称为无（有）向完全图
• 设 G 是含有 n 个顶点和 m 条边的无（有）向完全图$m=n(n-1)/2,m=n(n-1)$

# 赋权图

• 赋权图 G 是一个三重组$(V, E, g)$，其中 V 是结点集合，E 是边的集合

# 子图与补图

• 若$V'\subseteq V, E'\subseteq E$, 则称$G'=(V',E')$ 是$G=(V,E)$ 的子图
• $E'\subseteq E$ 之子图叫做真子图
• $V'=V$ 之子图叫做生成子图
• 设$V'\subseteq V$ 且$V'≠\varnothing$，以$V'$ 为结点集，以两个端点均在$V$' 中的边的全体为边集的 G 的子图，称为$V'$ 导出的 G 的子图，简称$V'$ 的导出子图
• 图$G'=(V', E')$ 是图$G=(V, E)$ 的子图。若 G 有子图$G''=(V'', E'')$, 其中$E''=E-E'$，$V''$ 是仅含$E''$ 中的边关联的结点和不在$G'$ 中的$G$ 的孤立点的集合，则称$G''$ 是$G'$ 关于$G$ 的补图
• 若称图$G$ 和$G'$ 互为补图，则两图$G=(V, E)、G'=(V, E')$ 满足：
  • $E∩E'=\varnothing$
  • $(V, E∪E')$ 是完全图

# 节点的次数

• 结点的 (全) 度数 d (v)：与结点 v 相关联的边数
• 在有向图中，度数又分为：
  • 引入度数$d^-(v)$：以 v 为终点的边数
  • 引出度数$d^+(v)$：以 v 为起点的边数
• $d(v) = d^-(v)+ d^+(v)$
• 次数为奇（偶）数的结点称为奇（偶）结点
• 图中若有奇结点，则必有偶数个奇结点
• 图中所有结点次数之和必为偶数，为图中边数的两倍

# 握手定理

• (n, m) 图中，结点的总次数为：$\sum\limits_{i=1}^nd(v_i)=2m$

# 图的同构

# 定义

• 图$G=(V, E)$ 与$G'=(V', E')$，如果存在双射函数$ƒ:V→V'$, 使得边也一一对应，则称$G$ 与$G'$ 同构

# 同构的必要条件

• 结点数目相同
• 边数相同
• 度数相同的结点数相同

# 通路、回路与连通性

# 通路

# 定义

• (有向) 图中 k 条 (首尾) 相连的边$(v_{i0},v_{i1}),(v_{i1},v_{i2}),…,(v_{ik-1},v_{ik})$, 记成$(v_{i0},v_{i1},v_{i2}, …, v_{ik})$，其中：$v_{i0}$：起点，$v_{ik}$：终点，$k$：通路长度

# 简单通路

• 边不同之通路

# 基本通路

• 结点不同之通路

# 可达

• 从结点 u 到结点 v 有通路，称 u 到 v 可达

# 短程线

• 两点间最短的通路

# 距离 d (u,v)

• 从 u 到 v 的短程线的长度 (不可达则为无限)

# 回路

# 定义

• $v_{i0}=v_{ik}$ 之通路，即 “起点 = 终点” 之通路

# 简单回路

• 边不同之回路

# 基本回路

• 结点不同之回路

# 结论

• 任一通路删去所有回路必得基本通路
• 任一回路删去其中间回路必得基本回路

# 定理

• 一个 (n,m) 有向图中任何基本通路长度都小于 n，而任何基本回路长度都不大于 n

# 连通性

# 无向连通图

• 任两点间均是可达的无向图

# 有向连通图

• 去掉边的方向后是无向连通图之有向图

# 强连通图

• 任两点间均互相可达之有向图

# 单向连通图

• 任两点间至少有一向可达之有向图

# 弱连通图

• 有向连通图

# 图的矩阵表示法

# 有向图的邻接矩阵

# 定义

• 对图 $G=(\{v_1,v_2, …, v_n\},E)$, 其邻接矩阵$A$ 如下构成： $A=(a_{ij})_{n\times n},a_{ij}=\begin{cases}1 & v_i与v_j邻接\\0 & v_i不与v_j邻接\end{cases}$

# 矩阵中的信息

• 结点$v_i$ 的次数
  • 引出次数：$d^+(v_i)=\sum\limits_{k=1}^n a_{ik}$
  • 引出次数：$d^-(v_i)=\sum\limits_{k=1}^n a_{ki}$
• $A^l$
  • 令 $C=A^l, c_{ij}$ 是$v_i$ 到$v_j$ 的长度为$l$ 的通路数目

# 可达性矩阵

• $R_n=A+A^2+…+A^n$ —— 反映任两点间的通路数目
• 可达性矩阵 P —— 将$R_n$ 中的非零值改为 1—— 反映任两点间是否可达
• P 也可如下计算：$P=A (+) A^(2)} (+) … (+) A({(n)) $

# 无向图的矩阵表示

# 无向图的邻接矩阵

• 无向图的邻接矩阵与有向图的类似，并且是对称的
• 结点的次数只要计算行 (或列) 之和即可，但对角线上的 1 要计算 2 次
• 矩阵$R_n$ 及 P 的计算方法也相同

# 多重图的邻接矩阵

• 1 改为重边的数目

# 有权图的邻接矩阵

• 1 改为权值

# 矩阵与图的连通性

• 无向图 G 是连通的$\iff$G 的可达性矩阵 P 除对角元外均为 1
• 有向图 G 是强连通的$\iff$G 的可达性矩阵 P 除对角元外均为 1
• 有向图 G 是单向连通的$\iff P(+)P^T$ (P 的转置) 除对角元外均为 1
• 有向图 G 是弱连通的$\iff A(+)A^T$ 图的可达性矩阵 P 除对角元外均为 1 （A 是 G 的邻接矩阵）

# 特殊图

# 欧拉图及其应用

# 欧拉回路

• 通过图中每条边一次之回路
• 欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路

# 欧拉图

• 有欧拉回路之图

# 欧拉通路

• 通过图中每条边一次之通路 (非回路)
• 欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路

# 定理

• 无向连通图 G 是欧拉图$\iff$G 的所有结点的次数都是偶数
• 无向连通图中结点 u、v 之间有欧拉通路$\iff$ 图中 u、v 的次数是奇数，其余结点的次数均为偶数
• 无向连通图 G 是欧拉图的充分必要条件是 G 的每个结点均具有偶次数

# 应用

• 一笔画问题
• 蚂蚁比赛问题
• 邮递员问题
• 洒水车

# 哈密顿图及其应用

# 哈密顿回路

• 通过图中每个结点一次之回路
• 是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路

# 哈密顿图

• 有哈密顿回路之图

# 哈密顿通路

• 通过图中每个结点一次之通路 (非回路)
• 是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结点的基本通路

# 定理

• 设无向图$G=(V,E)$ 是哈密顿图，$\varnothing \subseteq V_1 \subseteq V$ ，则$\omega(G-V_1)\leq|V_1|$ （必要）
• 设无向图$G = (V, E)$ 中存在哈密顿通路，则对$V$ 的任意非空子集$V_1$，都有$ω(G-V_1) ≤ |V_1| + 1$
• 设$G = (V, E)$ 是具有 n 个结点的简单无向图。如果对任意两个不相邻的结点$u, v∈V$，均有$d(u)+d(v)≥n-1$ 则 G 中存在哈密顿通路
• 设$G = (V, E)$ 是具有 n 个结点的简单无向图：
  • 如果对任意两个不相邻的结点$u, v∈V$，均有$d(u)+d(v)≥n$ 则 G 中存在哈密顿回路
  • $n≥3$，如果对任意$v∈V$，均有$d(v)≥ n/2$，则 G 是哈密顿图
• 设$G=(V, E)$ 是有$n(n≥2)$ 个结点的一些简单有向图。如果忽略 G 中边的方向所得的无向图中含生成子图$K_n$，则有向图 G 中存在哈密顿通路
• 设$G=(V,E)$ 是有向图，$|V|\geq 2$，如果任意两个不同结点次数之和$\geq |V|-1$，则 G 存在哈密顿通路 (判断有向图是否是哈密顿图不要求)

# 哈密顿图的应用

• 考试安排问题
• 推销员问题

# 树

# 树

• 不含回路的简单连通无向图

# 叶

• 树中次数为 1 的结点

# 森林

• 每个连通分支是树的无向图

# 树枝

• 无向树（林）中的边

# 树的性质

• 设无向图$G = (V,E)，|V| = n，|E| = m$，下列各命题是等价的
  • G 连通而不含回路 (即 G 是树)
  • G 中无回路，且$m = n-1$
  • G 是连通的，且$m = n-1$
  • G 中无回路，但在 G 中任二结点之间增加一条新边，就得到惟一的一条基本回路
  • G 是连通的，但删除 G 中任一条边后，便不连通 ($n≥2$)
  • G 中每一对结点之间有惟一一条基本通路 ($n≥2$)

# 定理

• 任意非平凡树$T = (n, m)$ 都至少有两片叶

# 生成树

# 定义

• 给定图$G = (V, E)$，若 G 的某个生成子图是树，则称之为 G 的生成树 (Spanning Tree)，记为 TG。生成树 TG 中的边称为树枝 (Branch)

# 定理

• 一个图$G = (V, E)$ 存在生成树$T _G = (V, E_T)$ 的充分必要条件是 G 是连通的

# 破圈法与避圈法

• 破圈法算法 求连通图$G = (V, E)$ 的生成树的破圈法：每次删除回路中的一条边，其删除的边的总数为$m-n+1$
• 避圈法算法 求连通图$G = (V, E)$ 的生成树的避圈法：每次选取 G 中一条与已选取的边不构成回路的边，选取的边的总数为$n-1$

# 最小生成树

• 设$G = (V, E)$ 是连通的赋权图，T 是 G 的一棵生成树，T 的每个树枝所赋权值之和称为 T 的权 (Weight)，记为$W(T)$。G 中具有最小权的生成树称为 G 的最小生成树 (Minimal Spanning Tree)

# Kruskal 算法

• (1) 在 G 中选取最小权边$e_1$，置$i = 1$
• (2) 当$i = n-1$ 时，结束，否则转 (3)
• (3) 设已选取的边为$e_1, e_2, …, e_i$，在 G 中选取不同于$e_1, e_2, …, e_i$ 的边$e_{i+1}$，使$\{e_1, e_2, …, e_i, e_{i+1}\}$ 中无回路且$e_{i+1}$ 是满足此条件的最小权边
• (4) 置$i = i+1$，转 (2)

# Prim 算法

• (1) 在 G 中任选取一个结点$v_1$，置$V_T = {v_1}, E_T = \varnothing，k = 1$
• (2) 在$V-V_T$ 中选取与某个$v_i∈V_T$ 邻接的结点$v_j$，使得边$(v_i, v_j)$ 的权最小，置$V_T = V_T∪{v_j}, E_T = E_T∪{(v_i, v_j)}，k = k+1$
• (3) 重复 (2)，直到$k = |V|$

# 有向树

# 定义

• 一个有向图，若略去所有有向边的方向所得到的无向图是一棵树，则这个有向图称为有向树 (Directed Tree)

# 外向树

• T 仅有一个结点的引入次数为 0，该结点为 T 的根
• T 的其他结点的入度均为 1
• T 有一些结点的出度为 0，该结点为 T 的叶
• 由外向树的根到结点$v_i$ 的通路长度称为结点$v_i$ 的级
• 若从结点$v_i$ 到$v_j$ 可达，则称$v_i$ 是$v_j$ 的祖先 (Ancestor)，$v_j$ 是$v_i$ 的后代 (Descendant)
• 若$<v_i, v_j>$ 是根树中的有向边，则称$v_i$ 是$v_j$ 的父亲 (Father)，$v_j$ 是$v_i$ 的儿子 (Son)
• 如果两个结点是同一个结点的儿子，则称这两个结点是兄弟 (Brother)
• 若每个分支点至多有 k 个儿子，则称 T 为 k 元树 (k-ary Tree)
• 若每个分支点都恰有 k 个儿子，则称 T 为 k 元完全树 (k-ary Complete Tree)
• 若 k 元树 T 是有序的，则称 T 为 k 元有序树 (k-ary Ordered Tree)
• 若 k 元完全树 T 是有序的，则称 T 为 k 元有序完全树 (k-ary Ordered Complete Tree)

# 内向树

• T 仅有一个结点的引出次数为 0，该结点为 T 的根
• T 的其他结点的引出次数均为 1
• T 有一些结点的引入次数为 0，该结点为 T 的叶

# 有序树

• 如果在外向树中规定了每一层上结点的次序，这样的根树称为有序树
• 一般地，在有序树中同一层中结点的次序为从左至右。有时也可以用边的次序来代替结点的次序

# 二元树的遍历

• 二元树的先根次序遍历算法：
  • 访问根
  • 按先根次序遍历根的左子树
  • 按先根次序遍历根的右子树
• 二元树的中根次序遍历算法:
  • 按中根次序遍历根的左子树
  • 访问根
  • 按中根次序遍历根的右子树
• 二元树的后根次序遍历算法：
  • 按后根次序遍历根的左子树
  • 按后根次序遍历根的右子树
  • 访问根

# 根树转化为二元树算法

• 从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线
• 兄弟间用从左向右的有向边连接
• 按如下方法确定二元树中结点的左儿子和右儿子：直接位于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依此类推
• 转化的要点：弟弟结点变右儿子结点

# 二分图

# 定义

• 若无向图$G = (V, E)$ 的结点集 V 能够划分为两个子集$V_1, V_2$，满足$V_1∩V_2 = \varnothing$，且$V_1∪V_2 = V$，使得 G 中任意一条边的两个结点，一个属于$V_1$，另一个属于$V_2$，则称 G 为二分图 (Bigraph)。$V_1$ 和$V_2$ 称为互补结点子集，二分图可记为$G = (V_1, V_2)$
• 二分图没有自回路
• 平凡图和零图可看成特殊的二分图

# 完全二分图

• 在二分图$G = (V_1, V_2)$ 中，若$V_1$ 中的每个结点与$V_2$ 中的每个结点都有且仅有一条边相关联，则称二分图 G 为完全二分图 (Complete Bigraph)，记为$K_{m,n}$，其中，$m = |V_1|，n = |V_2|$

# 二分图的判定

• 无向图$G = (V, E)$ 为二分图的充分必要条件是 G 的所有回路的长度均为偶数
• 无向图 G 不是二分图的充分必要条件是 G 中存在长度为奇数的回路

# 匹配

• 在二分图$G = (V_1, V_2)$ 中，$V_1 = \{v_1, v_2, …, v_q\}$，若存在 E 的子集$E'= \{(v_1, v_1')，(v_2, v_2')，…，(v_q, v_q')，其中v_1', v_2', …, v_q' 是V_2中的q个不同的结点\}$，则称 G 的子图$G' = (V_1, E', V_2)$ 为从$V_1$ 到$V_2$ 的一个完全匹配 (Complete Matching)，简称匹配

# 平面图

# 定义

• 如果能把一个无向图 G 的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点，则称 G 为平面图 (Plane Graph)，否则称 G 为非平面图 (Nonplanar Graph)。当且仅当一个图的每个连通分支都是平面图时，这个图是平面图

# 判断图是否是可平面图的方法

# 观察法

# 欧拉公式

• 在平面图 G 的一个平面表示中，

  • 由边所包围的其内部不包含图的结点和边的区域，称为 G 的一个面 (Surface)
  • 包围该面的诸边所构成的回路称为这个面的边界 (Bound)
  • 面 r 的边界的长度称为该面的次数 (Degree)，记为$D(r)$
  • 区域面积有限的面称为有限面 (Finite Surface)，区域面积无限的面称为无限面 (Infinite Surface)
  • 平面图有且仅有一个无限面

• 平面图中所有面的次数之和等于边数的二倍

• 设$G = (V, E)$ 是连通平面图，若它有$n$ 个结点、$m$ 条边和$r$ 个面，则有$n-m+r = 2$

• 设设 G 是一个$(n,m)$ 简单连通平面图，若$m＞1$，则有$m≤3n-6$

• 一个简单连通图，若不满足$m≤3n-6$，则一定是非平面图

# 库拉托夫斯基定理

• 一个图是平面图的充分必要条件是它的任何子图都不可能收缩为$K_5$ 或$K_{3,3}$
• 一个图是非平面图的充分必要条件是它存在一个能收缩为$K_5$ 或$K_{3,3}$ 的子图
• 我们将$K_5$ 和$K_{3,3}$ 称为库拉托夫斯基图 (Kuratowski Graph)

# 平面图的应用

• 公共事业问题