02324 离散数学 ✒️

命题公式

等价演算

• 双重否定 $p = \neg(\neg p)$
• 交换 $p \lor q = q \lor p$
• 结合 $(p \land q) \land r = p \land (q \land r)$
• 德摩根 $\neg(p \land q) = \neg p \lor \neg q$ 或 $\neg(p \lor q) = \neg p \land \neg q$
• 分配 $p \lor (q \land r) = (p \lor q) \land (p \lor r)$ 或 $p \land (q \lor r) = (p \land q) \lor (p \land r)$
• 吸收 $p \lor (p \land q) = p$ 或 $p \land (p \lor q) = p$
• 条件等价 $p \rightarrow q = \neg p \lor q$
• 双条件等价 $p \leftrightarrow q = (p \rightarrow q) \land (q \rightarrow p)$
• 假言 $p \rightarrow q = \neg q \rightarrow ¬p$

例：证$\neg q \land (p \lor q) \rightarrow q$

• 用真值表证明

假言推理

$$(A \rightarrow B) \land A \Rightarrow B$$

• 拒取式：$(A \rightarrow B) \land \neg B \Rightarrow \neg A$
• 假言三段论：$(A \rightarrow B) \land (B \rightarrow C) \Rightarrow (A \rightarrow C)$
• 析取三段论：$(A \lor B) \land \neg B \Rightarrow A$

补充：

• $A \iff B$的充要条件：$A \rightarrow B$且$B \rightarrow A$
• $A \Rightarrow B$且A是重言式，则B一定是重言式
• $A \Rightarrow B$且$B \Rightarrow C$，则$A \Rightarrow C$（传递性）、并且$A \Rightarrow B \land C$
• $A \Rightarrow B$且$C \Rightarrow B$，则$A \land C \Rightarrow B$
• $A \Rightarrow B$，C为任意公式，则$A \land C \Rightarrow B \land C$

范式

例：求$(P \lor Q) \leftrightarrow P$的合取范式

• 双条件等价：$(P \lor Q) \leftrightarrow P \equiv [(P \lor Q) \rightarrow P] \land [P \rightarrow (P \lor Q)]$
• 条件等价：$(P \lor Q) \rightarrow P \equiv \neg(P \lor Q) \lor P \equiv (\neg P \land \neg Q) \lor P$
• 分配律：$(\neg P \land \neg Q) \lor P \equiv (P \lor \neg P) \land (P \lor \neg Q) \equiv \boxed{\neg Q \lor P}$
• $P \rightarrow (P \lor Q)$，由真指假为假，其中P为真，$P \lor Q$必为真，这个是永真式
• 所以：$(P \lor Q) \leftrightarrow P$的合取范式为：$\boxed{\neg Q \lor P}$

主析取范式

即：$P \land Q \land R$，那么小项可以表示为（一共有$2^n$个小项、只有都为T时为真）

• $m_{000} = \neg P \land \neg Q \land \neg R$
• $m_{001} = \neg P \land \neg Q \land R$
• $m_{010} = \neg P \land Q \land \neg R$
• $m_{011} = \neg P \land Q \land R$
• $m_{100} = P \land \neg Q \land \neg R$
• $m_{101} = P \land \neg Q \land R$
• $m_{110} = P \land Q \land \neg R$
• $m_{111} = P \land Q \land R$

主合取范式

即：$P \lor Q \lor R$，那么大项可以表示为（一共有$2^n$个大项、只有都为F时为假）

• $M_{000} = \neg P \lor \neg Q \lor \neg R$
• $M_{001} = \neg P \lor \neg Q \lor R$
• xxx 省略....

推理

部分规则

规则名称	形式	中文说明
P规则	直接引用前提	表示该公式是题设中的前提
T规则	利用等价或定理推导	表示由前面步骤推出的中间结论
假言三段论	$A \rightarrow B$，$B \rightarrow C \Rightarrow A \rightarrow C$	多步蕴含推理
肯定前件（MP）	$A \rightarrow B$，$A \Rightarrow B$	如果有蕴含和前提成立，则结论成立
否定后件（MT）	$A \rightarrow B$，$\neg B \Rightarrow \neg A$	如果结论不成立，则前提也不成立
析取三段论	$A \lor B$，$\neg A \Rightarrow B$	两种可能中排除一个，则另一个为真
合取消除	$A \land B \Rightarrow A$ 或 $B$	合取式中每一部分都为真
合取引入	$A$，$\ B \Rightarrow A \land B$	两个命题同时为真时可合并
析取引入	$A \Rightarrow A \lor B$	某个命题为真，则析取也为真

直接推理

例：$(P \lor Q) \land (P \rightarrow R) \land (Q \rightarrow S) \Rightarrow S \lor R$

步骤	公式	依据
1	$P \lor Q$	P规则
2	$\neg Q \rightarrow P$	T(1)逻辑等价
3	$P \rightarrow R$	P规则
4	$\neg Q \rightarrow R$	T(2)(3)假言三段论
5	$Q \rightarrow S$	P规则
6	$\neg Q \rightarrow \neg S$	T(5)逆否命题
7	$\neg S \rightarrow R$	T(4)(6)假言三段论
8	$S \lor R$	T(7)逻辑等价

归谬推理（反证）

例：$P \rightarrow (Q \rightarrow R)$、$\neg T \lor P$、$Q \Rightarrow (T \rightarrow R)$

• 设T为真，推出R为真

步骤	公式	依据
1	$T$	P规则
2	$\neg T \lor P$	P规则
3	$P$	T(1)(2)析取三段论
4	$P \rightarrow (Q \rightarrow R)$	P规则
5	$Q \rightarrow R$	T(3)(4)假言推理
6	$Q$	P规则
7	$R$	T(5)(6)假言推理

谓词逻辑

谓词命题符号化

• 全称量词（$\forall$）
• 存在量词（$\exists$）

命题	谓词关系	谓词命题符号化
所有大学生都热爱祖国	令P(x)：x是大学生、 令Q(x)：x热爱祖国	$\forall x P(x) \rightarrow Q(x)$
一些大学生有远大理想	令P(x)：x是大学生、 令Q(x)：x有远大理想	$\exists x P(x) \land Q(x)$
对任意整数x， $x^2 -1 = (x+1)(x-1)$恒成立	令I(x)：x是正数， 令$f(x)=x^2 -1$、 令$g(x)=(x+1)(x-1)$	$\forall x I(x) \rightarrow G(f(x),g(x))$

谓词公式赋值

• $\forall x A(x) \iff A(x_0) \land A(x_1) \land ... \land A(x_n)$
• $\exists x A(x) \iff A(x_0) \lor A(x_1) \lor ... \lor A(x_n)$

等价式

1. $\neg (\forall x) A \iff (\exists x) \neg A$
2. $\neg (\exists x) A \iff (\forall x) \neg A$
3. $\forall x(A(x) \rightarrow B) \iff (\exists x) A(x) \rightarrow B$
4. $(\forall x)(A(x) \land B(x)) \iff (\forall x) A(x) \land (\forall x)B(x)$
5. $(\forall x)(A(x) \land B(x)) \iff [(\forall x)(A(x))] \land B$
6. 4、5中$\land \lor$互换、全称换存在是一致的

前束范式

所有的量词 都出现在公式的最前面 ，且后面跟着一个无量词的公式 （即：不含任何量词的部分）

公式	是否为前束范式	说明
$\forall x\ \exists y\ (P(x) \rightarrow Q(y))$	✅ 是	所有量词在前，后接无量词部分
$\exists z\ \forall x\ (R(x,z) \land S(z))$	✅ 是	同上
$P(x) \land \forall y\ Q(y)$	❌ 否	量词不是全部在最前
$\forall x\ (P(x) \lor \exists y\ Q(x,y))$	❌ 否	存在量词嵌套在公式中间

谓词演算的推理理论

规则名	含义
全称消去 UI	从 $\forall x P(x)$ 推出 $P(a)$
全称引入 UG	从 $P(a)$ 推出 $\forall x P(x)$
条件消去 EI	$\exists x A(x) \Rightarrow A(a)$
条件引入 EG	$A(a) \Rightarrow \exists x A(x)$
条件证明 CP	若从A可推出B，则$A \rightarrow B$成立

例：1.所有人都会死，2.苏格拉底是人，3.苏格拉底会死

定义谓词：

• $H(x)$：$x$ 是人
• $D(x)$：$x$ 会死
• $s$：苏格拉底

转换为逻辑公式：

1. $\forall x (H(x) \rightarrow D(x))$ （所有人都会死）
2. $H(s)$ （苏格拉底是人）
3. $D(s)$ （苏格拉底会死）

步骤	公式	依据	说明
1	$\forall x (H(x) \rightarrow D(x))$	P规则	前提
2	$H(s) \rightarrow D(s)$	T(1)，全称消去	使用全称消去，代入 $x = s$
3	$H(s)$	P规则	前提
4	$D(s)$	T(2)(3)，肯定前件	假言推理：由 $H(s) \rightarrow D(s)$ 和 $H(s)$ 得出

例：$(\forall x)(P(x) \lor Q(x)) \Rightarrow (\forall x)P(x) \lor \exists Q(x)$

步骤	公式	依据	说明
1	$\forall x (P(x) \lor Q(x))$	P规则	假设前提
2	$P(a) \lor Q(a)$	T(1)，全称消去	对任意个体a，$P(a) \lor Q(a)$成立
3	假设 $\neg (\exists x) Q(x)$	CP假设	即假设不存在x使得Q(x)成立
4	$\forall x \neg Q(x)$	T(3)，等价转换	$\neg \exists x\, Q(x) \equiv \forall x\, \neg Q(x)$
5	$\neg Q(a)$	T(4)，全称消去	从$\forall x \neg Q(x)$ 得出 $\neg Q(a)$
6	$P(a)$	T(2)(5)，析取三段论	$P(a) \lor Q(a),\ \neg Q(a) \Rightarrow P(a)$
7	$\forall x P(x)$	T(6)，全称引入	因为a是任意的，所以 $\forall x P(x)$
8	$\neg (\exists x) Q(x) \rightarrow \forall x P(x)$	T(3)-(7)，CP规则	由假设推出结论
9	$\forall x P(x) \lor \exists x Q(x)$	T(8)，等价转换	$\neg A \rightarrow B \equiv A \lor B$

集合

集合中的元素不能重复出现

• 包含：$\forall x(x \subseteq A \rightarrow x \subseteq B) \iff A \subseteq B$
• $A=B$：$A \subseteq B$且$B \subseteq A$，互为子集
• 空集$\varnothing$：空集是任何集合的子集，唯一的
• 全集 E
• $A={a,b,c}$，A的子集有$2^n=8$个，即$\varnothing$、a、b、c、ab、ac、bc、abc，所有子集构成的新的集合P就是A的幂集

集合运算

• 并集：$A \cup B$
• 交集：$A \cap B$
• 差集：$A - B = \{x|x \in A \land x \notin B\}$
• 对称差：$A \oplus B = (A-B) \cup (B-A)$
• 绝对补：E~A

算律

• $A \cup (B \cap C) = (A \cup B) \cap (B \cup C)$
• $A \cup (A \cap B) = A$、$A \cap (A \cup B) = A$
• DM律：$A - (B \cup C) = (A-B) \cap (A-C)$
• ~$(B \cup C) =$~$B \cap$~$C$
• 有序对：$<x,y> \neq <y,x>$

笛卡尔积

$A={1,2,3}$、$B={a,b,c}$，笛卡尔积$A \times B$为：(个数为$m*n=9$)

$$\{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>\}$$

例：证明：$A \times (B \cup C) = A \times B \cup A \times C$

• 任取$\forall <x,y> \in A \times (B \cup C)$，则有$x \in A$、$y \in (B \cup C)$
• 可以得到$x \in A , y \in B$或$x \in A , y \in C$
• 即$<x,y> \in A \times B$，或$<x,y> \in A \times C$
• 所以$A \times (B \cup C) = A \times B \cup A \times C$

关系与函数

关系

$A=\{1,3,6,12\}$，整除关系包括$\{<1,1>, <1,3>, <1,6>, <1,12>, <3,3>, <3,6>, <3,12>, <6,6>, <6,12>, <12,12>\}$

• 定义域：$domR = \{x| \exists y(<x,y> \in R)\}$
• 值域：$ranR = \{y| \exists x(<x,y> \in R)\}$
• 域：$f|dR = domR \cup ranR$

关系矩阵&关系图

已知$R=\{<1,1>,<1,2>,<2,3>,<2,4>,<4,2>\}$，

关系矩阵 $M_R = \begin{Bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{Bmatrix}$

关系图：

关系的性质

自反&反自反

性质	含义	数学表达	示例
自反	所有元素都与自身相关	$\forall a \in A,(a,a) \in R$	$R = \{(1,1),(2,2),(3,3)\}$
反自反	所有元素都不与自身相关	$\forall a \in A, (a, a) \notin R$	$R = \{(1,2),(2,3),(3,1)\}$

对称&反对称

性质	含义	数学表达	示例
对称	若aRb则必bRa	$(a,b) \in R \Rightarrow (b,a) \in R$	平等关系、朋友关系
反对称	若aRb且bRa， 则a = b	$(a,b) \in R \land (b,a) \in R \rightarrow a = b$	小于等于、整除关系

例：$A=\{1,2,3\}$，判断下列关系

• 对称关系的判断：把R中每一项都颠倒过来看是否在R中能找到
• $R_1=\{<1,1>,<2,2>\}$：对称关系 ，aRb和bRa都成立，那么判断后者为假，不存在，故是反对称关系
• $R_2=\{<1,1>,<1,2>,<2,1>\}$：对称关系 ，1R2和2R1是成立的，但是不能得到1=2（即由真指假为假），故 不是反对称关系
• $R_2=\{<1,2>,<1,3>\}$：不是对称关系，有1R2没有2R1，前者为假a-> b为真，故是反对称关系
• $R_2=\{<1,2>,<2,1>,<1,3>\}$：不是对称关系，同R2， 不是反对称关系

传递性

$A \in B \ and \ B \in C \Rightarrow A \in C$

关系运算

布尔矩阵运算

布尔矩阵的元素只能是 0 或 1

$$A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix},\quad B = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}$$

布尔加法：对每个位置做逻辑或：有真为真

$$A \vee B = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}$$

布尔乘法：第 i 行与第 j 列对应元素做逻辑与，然后将所有结果做逻辑或

$$A \odot B = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$$

逆运算

矩阵转置

$$M_R = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \quad \Rightarrow \quad M_{R^{-1}} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}$$

集合翻转

• $R = \{ \langle 1,1 \rangle, \langle 1,3 \rangle, \langle 2,2 \rangle, \langle 3,1 \rangle \}$
• $R^{-1} = \{ \langle 1,1 \rangle, \langle 3,1 \rangle, \langle 2,2 \rangle, \langle 1,3 \rangle \}$

复合运算

例：$A = \{1,2,3,4\}$，R、S都是A上的二元关系

• $R=\{<1,2>,<2,3>,<1,4>,<2,2>\}$
• $S=\{<1,1>,<1,3>,<2,3>,<3,2>,<3,3>\}$
• 桥接：拿R的第一项和S的第二项，并且集合中不能出现重复的元素（去重）
• $R \circ S = \{<1,3>,<2,2>,<2,3>\}$
• $S \circ R = \{<1,2>,<1,4>,<3,3>,<3,2>\}$

定理：F、G、H是任意关系

• $(F \circ G) \circ H = F \circ (G \circ H)$
• $(F \circ G) ^ {-1} = G ^ {-1} \circ F ^ {-1}$

R的n次幂

• $R^0 = I_A$
• $R^1 = R$
• $R^2 = R \circ R$
• $R^3 = R \circ R \circ R$
• $M_{R^2} = M_{R^4} = M_{R^6}$、$M_{R^3} = M_{R^5} = M_{R^7}$

例：证明：设A是一个n元集，R是A上的二元关系，必然存在自然数s、t，使得$R^s = R^t$

• A为n元集，那么A的子集个数为$2^{n^2}$
• 但其$R^0 R^1 R^2 R^3 ··· R^n$是无限的
• 根据原抽屉（鸽舍）理所以一定存在一个数s，使得$R^s = R^t$

闭包运算

• 自反闭包：$r(R) = R \cup I_A$
• 对称闭包：$s(R) = R \cup R^{-1}$
• 传递闭包：$t(R) = R \cup R^2 \cup R^3 ··· R^n$

例：计算：$X=\{1,2,3,4\}$，R是X上的二元关系

• $R=\{<1,2>,<2,1>,<2,3>,<3,4>\}$
• 自反闭包：$r(R) = R \cup I_A = \{...,<1,1>,<2,2>,<3,3>,<4,4>\}$
• 对称闭包：$s(R) = R \cup R^{-1} = \{...,<3,2>,<4,3>\}$（...表示沿用R中的元素）
• 传递闭包：$t(R) = R \cup R^2 \cup R^3 ··· R^n =$

$${ t(R) = \left\{ \begin{aligned} &\langle 1,1 \rangle,\ \langle 1,2 \rangle,\ \langle 1,3 \rangle,\ \langle 1,4 \rangle,\\ &\langle 2,1 \rangle,\ \langle 2,2 \rangle,\ \langle 2,3 \rangle,\ \langle 2,4 \rangle,\\ & \langle 3,3 \rangle,\ \langle 3,4 \rangle,\ \langle 4,4 \rangle \end{aligned} \right\} }$$

证明自反闭包（定义）📌

令$R' = R \cup I_A$，则必须满足三个条件

• $R \subseteq R'$
• $I_A \subseteq R'$（R‘’是自反）
• R'是最小的，即$\exists R'' = R \cup I_A \ and \ R' \subseteq R''$
  • $I_A \subseteq R''$、$R \subseteq R''$、$R' = R \cup I_A$，即$R' \subseteq R''$

证明对称闭包（定义）📌

令$R' = R \cup R^{-1}$，则必须满足三个条件

• $R \subseteq R'$
• $R'$对称
  • $\forall <x,y> \in R' \Rightarrow <x,y> \in R \cup R^{-1}$ 分情况讨论：
    • $<x,y> \in R$，则$<y,x> \in R^{-1} \in R'$
    • $<x,y> \in R^{-1}$，则$<y,x> \in R \in R'$
• R'是最小的：和自反闭包一样

证明传递闭包（定义）📌

令$R' = R \cup R^2 \cup R^3 ··· R^n$，则必须满足三个条件

• $R \subseteq R'$
• R’传递
  • $\forall <x,y> \in R' \ and \ <y,z> \in R'$，目标是找到$<x,z> \in R'$
  • 即：$<x,y> \in R \cup R^2 \cup R^3 ··· R^n$ 和 $<y,z> \in R \cup R^2 \cup R^3 ··· R^n$
  • $\exists m,n$使得$<x,y> \in R^m$和$<y,z> \in R^n$
  • 根据复合运算可以得到$<x,z> \in R^{m+n}$（得到结论，满足传递性）
• R'是最小的
  • 令$R'' = R \cup R^2 \cup R^3 ··· R^n$，那么只需证明$\forall i \in N$、$R^i \subseteq R''$
  • 设$<x,y> \in R^i$证明$<x,z> \in R''$
  • $\exists z_1,z_2,z_3,....,z_{i-1} \in A$，并且$<x,z_1> \in R$、$<z_1,z_2> \in R$、...、$<z_{i-1},y> \in R$
  • $R \subseteq R''$，那么放大上一步：$<x,z_1> \in R''$、$<z_1,z_2> \in R''$、...、$<z_{i-1},y> \in R''$
  • 可以得到：$<x,y> \in R''$

关系性质与关系运算

判断关系性质的充要条件：设R是在A上的关系，则：

• R在A上自反当且仅当$I-A \in R$
• R在A上反自反当且仅当$R \cap I_A=0$
• R在A上对称当且仅当$R= R^{-1}$
• R在A上反对称当且仅当$R \cap R^{-1} \subseteq I_A$
• R在A上传递当且仅当$R·R \subseteq R$
• 如果R是自反的，那么s(R)和t(R)也是自反的
• 如果R是对称的，那么r(R)和t(R)也是对称的
• 如果R是传递的，那r(R)也是传递的。用反例证明：如果R是传递的，那么s(R)也是传递为假

运算、性质	自反性	反自反性	对称性	反对称性	传递性
$R^{-1}$	√	√	√	√	√
$R\cap S$	√	√	√	√	√
$R\cup S$	√	√	√	×	×
R-S	√	√	√	√	×
$R \circ S$	√	×	×	×	×

• 设R1、R2是在A上的关系，且$R1 \subseteq R2$
  • $r(R1) \subseteq r(R2)$
  • $s(R1) \subseteq s(R2)$
  • $t(R1) \subseteq t(R2)$
• R、S是A上的关系
  • $r(R \cup S) = r(R) \cup r(S)$
  • $s(R \cup S) = s(R) \cup s(S)$
  • $t(R) \cup t(S) \subseteq t(R \cup S)$
  • $rs(R) = sr(R)$
  • $rt(R) = tr(R)$
  • $ts(R) \supseteq st(R)$

等价关系

【定义】设A是非空集合，$π={S_1,S_2,...,S_m}$，$S \neq \varnothing$，$i=1,...,m$，且满足：

• $\forall S_i \in π, S \subseteq A$
• $S_1 \cup S_2 \cup ... \cup S_m = A$
• $S_i \cap S_j = \varnothing,(i \neq j)$
• 则称π是A的一个划分。称$S_i, i=1,..,m$是A的划分块。定义中的$s_i \cap s_j = \varnothing, i \neq j$是指π中的元素两两互不相交

记作：$a \sim b$

例：设$X=\{1,2,3,4\}$，X的划分$S=\{\{1\},\{2,3\},\{4\}\}$，求S导出的等价关系$R_0$

• 补充自反、对称
• $R_0=\{<1,1>,<2,2>,<2,3>,<3,2>,<3,3>,<4,4>\}$
• 反之$R_1=\{<1,2>,<2,3>,<3,1>,<4,4>,<5,5>\}$
• 求$S=\{\{1,2,3\},\{4\},\{5\}\}$

序关系

【定义】非空集合A上的自反、反对称和传递的关系，称为A上 的偏序关系，记作$\preceq$。设$\preceq$为偏序关系, 如果$<x, y> \in \preceq$， 则记作$x \preceq y$

例：集合 $X = \{1, 2, 3, 4, 5, 6, 12\}$ 在整除关系下的 COVA

• 找到所有满足a<b，并且满足整除关系的有序对：$<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,12>,<2,4>,<2,6>,<2,12>,<3,6>,<3,12>,< 4,12>,<6,12>$
• 排除：$<1,2>$没有中间元素保留，$<1,4>$有$1 \rightarrow 2 \rightarrow 4$所以去掉，其他同理
• $\text{COVA} = \{<1,2>,\ <1,3>,\ <1,5>,\ <2,4>,\ <2,6>,\ <3,6>,\ <4,12>,\ <6,12>\}$

偏序集中的特殊元素：设$<A,\preceq>$为偏序集，$B \subseteq A \, y \in B$。

• 若$\forall x(x \in B \rightarrow y \preceq x)$成立，则称y为B的最小元
• 若$\forall x(x \in B \rightarrow x \preceq y)$成立，则称y为B的最大元
• 若$\neg \exists x (x \in B \land x \preceq y)$成立，则称y为B的极小元
• 若$\neg \exists x (x \in B \land y \preceq x)$成立, 则称y为B的极大元

函数

设F为二元关系，若$\forall x \in domF$都存在唯一的$y \in ranF$使xFy成立，则称F为函数。对于函数F，如果有xFy，则记作y=F(x) ，并称y为F在x的值

【定理】设F,G是函数，则$F \circ G$也是函数，且满足

• $dom(F \circ G)=\{ x | x \in domF \land Fx) \in domG\}$
• $\forall x \in dom(F \circ G$ 有$F \circ G(x) = G(F(x)$

例：$f(x) = \begin{cases} x^2, & x \geq 3 \\ -2 , & x < 3\end{cases}$、$g(x)=x+2$，求$f \circ g \ and \ g \circ f$

• $f \circ g = g(f(x)) = f(x) + 2 = \begin{cases} x^2 + 2, & x \geq 3 \\ 0 , & x < 3\end{cases}$
• $g \circ f = f(g(x)) = f(x+2) = \begin{cases} (x+2)^2, & x \geq 1 \\ -2 , & x < 1\end{cases}$

代数系统

幺元

• 【定义】设$\circ$为S上的二元运算，如果存在$e_l (e_r) \in S$，使得对任意$X \in S$都有$e_l \circ x = x (x \circ e_r = x)$，则称$e_l$或$e_r$是S中关于$\circ$运算的左（或右）单位元
• 若$e \in S$关于$\circ$运算既是左单位元又是右单位元，则称e为S上关于$\circ$运算的单位元（幺元）

零元

• 【定义】设$\circ$为S上的二元运算，如果存在$\theta_l (\theta_r) \in S$，使得对任意$X \in S$都有$\theta_l \circ x = \theta_l (x \circ \theta_r = \theta_r)$，则称$\theta_l$或$\theta_r$是S中关于$\circ$运算的左（或右）零元
• 若$\theta \in S$关于$\circ$运算既是左零元又是右零元，则称$\theta$为S上关于$\circ$运算的零元

逆元

• 【定义】令e为S重关于运算$\circ$为S的幺元，对于$x \in S$，如果存在$y \in S$，使得$y_l \circ x = e \ (x \circ y_r = e)$，则称$y_l(t_r)$为x的左（右）逆元
• 关于$\circ$运算，若$y \in S$即是x的左逆元、也是x的右逆元，则称y为x的逆元
• 如果x的逆元存在，则称x是可逆的

例：设$\circ$运算为Q上的二元运算，$\forall x, y \in Q , x \circ y = x+ y+ 2xy$

• 运算是否满足交换和结合律？说明理由
• 把xy互换，其加法、乘法满足对应值相等，故满足交换律
• 结合律指对所有$x,y,z \in Q$，都有 $(x \circ y) \circ z=x \circ (y \circ z)$
• $x \circ y = A$、$A \circ z=A+z+2Az$，同理先计算$y \circ z = B$再计算$B \circ x$，两者是一样的满足结合律
• 求$\circ$运算的单位元、零元和所有可逆元
• 单位元： $x \circ e=x \Rightarrow x+e+2xe=x \Rightarrow e+2xe=0 \Rightarrow e( 1+2x) = 0$
• 零元：$x \circ z = z \Rightarrow x+z+2xz = z \Rightarrow x+2xz=0 \Rightarrow z = -\frac{1}{2}$
• 逆元：$x+y+2xy=0 \Rightarrow y(1+2x)= -x \Rightarrow y= -\frac{x}{1+2x} \Rightarrow x \neq -\frac{1}{2}$

半群

【定义】设$V=<S,\circ>$是代数系统，$\circ$是二元运算，如果$\circ$是封闭的、可结合的，则称V为半群

• 对任意x，（$x \in S$）
• $x^1=x$
• $x^{n+1} = x^n \circ x (n \in Z^{+})$

如果$\circ$是可交换的，那么称V为交换半群。若$e \in S$是关于$\circ$运算的单位元，则称V是含幺半群，也叫做独异点，记作$V = <S, \circ, e>$

$<Z_n, \oplus, e>$为交换半群和独异点，其中$Z_n=\{1,2,3,..., n-1\}$，$\oplus$为模n加法

群

【定义】设$<G, \circ>$是代数系统，$\circ$为二元运算。如果$\circ$运算 是可结合的，存在单位元$e \in G$，并且对G中的任何元素x都有$x^{-1} \in G$，则称G为群

证代数系统是否为群，只需要逐一验证以下四个条件

• 封闭性 $\forall x,y \in G \ ,x \circ y \in G$
• 结合律 $x \circ (y \circ z) = (x \circ y) \circ z$
• 单位元存在性 $e \circ x = x \circ e = x$
• 每个元素都有逆元

是否是群

• $<M_n(R),+> ,<M_n(B), \oplus>, <Z_n, \oplus>$是群（对称差、模n加）
• $<M_n(R),\circ>$不是群

性质：

• G为群，$\forall a,b \in G$，方程 ax=b 和 ya= b 在G中有解且仅有唯一解。$a^1 b$是ax=b的解。$ba^1$是ya=b的唯一解
• $\forall a,b,c \in G$，若ab=ac，则b=c，若ba=ca，则b=c

子群

【定义】设G是群，H是G的非空子集，如果H关于G中的运算构成群，则H是G的子群

• H是G的子群，当且仅当$\forall x,y \in H \rightarrow xy^{-1} \in H$（充要条件）
• $\forall a,b \in H , a * b \in H$和$\forall a \in H, a^{-1} \in H$
• H是G的有穷非空子集，当且仅当$\forall a,b \in H , a * b \in H$

生成子群

G为群，$a \in H$，令$H = \{a^k | k \in Z\}$，则H为G的生成子群

循环群

设G是群，若存在$a \in G$使得$G={a^k | k \in Z}$，则称G是循环群，记作 $G=<a>$，称a为G的生成元。

环

设$<R,+,\circ>$是代数系统，+和$\circ$是二元运算，如果满足以下条件：则称其是一个环

1. $<R,+>$构成交换群
2. $<R,\circ>$构成半群
3. $\circ$运算关于+运算适合分配律

格&布尔代数

格

设$< S, \le >$是偏序集, 如果$\forall x,y \in S$, {x,y都有最小上界（上确界）和是大下界（下确界），则称S关于偏序$\le$作成一个格

设$<S,*,o>$是具有两个二元运算的代数系统，若对于*和o运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得$<S,\le>$构成格，且$\forall a,b \in S$有 $a \land b=a*b$, $a \lor b = aob$

分配格、有界格、有补格

布尔代数

如果一个格是有补分配格，则称这个格为布尔代数（布尔格）

• 设$<B,*,\circ>$是代数系统，* 和 $\circ$是二元运算，若 * 和 $\circ$ 运算满足交换律、结合律、幂等律、吸收律，即其是一个布尔代数

设$<B,\land,\lor,',0,1>$是布尔代数，则

• $\forall a \in B, (a')' = a$
• $\forall a,b \in B$
• $(a \land b)' = a' \lor b'$、$(a \lor b)' = a' \land b'$（德摩根律）

有限布尔代数

设L是有限布尔代数，则L含有$2^n$个元素（$n \in N$ 且 L与$<P(S,\cap,\cup,~,\varnothing,S>$同构，其中S是一个n元集合。

图

基本概念

【定义】一个图G定义为一个三元组<V，E，φ>，其中V、 E是非空有限集合，V的元素称为结点，E的元素称为边， 而φ是从E到V中的序对或无序对的映射

例：G=<V,E, φ>，其中φ={(v1,v2),(v2,v3),(v3,v1),(v3,v5),(v5,v6),<v6,v4>}，绘制图

• n阶图：n个顶点的图
• 有限图：V、E都是有穷集合的图
• 零图：E=∅
• 平凡图：1阶零图
• 空图：V=∅
• n阶（无向）完全图Kn：每个顶点都与其余顶点相邻的n阶无向简单图，其边数为$\frac{n(n-1)}{2}$
• k正则图：无向图中，每个顶点的度数都是k，边数$m=\frac{k(k-1)}{2}$
• 子图：$G=(V',E')$，且$V'\subseteq V$，$E'\subseteq E$
• 生成子图：$G=(V',E')$，且$V'= V$，$E'\subseteq E$

顶点的度数：

G为无向图，$\forall v \in V$

• v的度数：v作为边的端点的边数
• 悬挂顶点：度数为1的顶点
• 悬挂边：与悬挂顶点相关联的边

D为有向图，$\forall v \in V$

• v的入度：v作为边的终点的边数
• v的出度：v作为边的起点的边数

握手定理

任意无向图和有向图的所有顶点度数之和都等于边数的2倍，并且有向图的所有顶点入度之和等于出度之和等于边数

• $\sum_{v \in V}deg(v) = 2|E|$
• $\sum_{v \in V}deg^{+}(v) = \sum_{v \in V}deg^{-}(v) = |E|$

连通性

在n阶图G中，若从顶点$V_i \rightarrow V_j(V_i \neq V_j)$ 存在通路，则从$V_i \rightarrow V_j$存在长度$\le (n-1)$的（初级）通路

无向图	有向图
图中任意两个顶点之间都存在路径	图中任意两个顶点u和v，都存在从u到v的有向路径 且存在从v到u的有向路径

无向图

• 点割集：在连通图G中，使得删除该顶点集合后，图G变得不连通的极小顶点集合
• 边割集：在连通图G中，使得删除该边集合后，图G变得不连通的极小边集合

• 点割集：$\{2,5\}$。删除顶点2和5后，图变得不连通
• 边割集：$\{(1,2), (1,4)\}$。最小的边割集大小为2，所以这个图的边连通度λ(G) = 2

图的表示

邻接矩阵

对于一个包含 n 个顶点的图 G=(V,E) ，其邻接矩阵是一个 n×n 的方阵 A ，其中：

• 元素$A_{i,j}$：若顶点 i 与顶点 j 之间存在边（或有向边），则 $A_{i,j} = 1$，否则$A_{i,j} = 0$
• 对角线元素（$A_{i,i}$）：通常为 0，除非图中存在自环（允许顶点与自身相连）

以有向图为例：

• 邻接矩阵：$A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$
• 出入度：$d^+(2)=2 , d^-(2)=1 , d(2)=3$，看对应横（纵）向上有多少个1

例：邻接矩阵：$A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{bmatrix}$，那么$A^2 = A \times A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 \\ 2 & 0 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ \end{bmatrix}$，

$A^3 = A^2 \times A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 4 & 0 & 1 & 0 \\ 3 & 0 & 0 & 1 \\ 3 & 0 & 1 & 0 \\ \end{bmatrix}$，$A^4 = A^3 \times A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 5 & 0 & 0 & 1 \\ 4 & 0 & 1 & 0 \\ 4 & 0 & 0 & 1 \\ \end{bmatrix}$

通路与回路统计：

• 长度为n的通路数量和：矩阵$A^n$所有元素之和
• 长度为n的回路数量和：矩阵$A^n$对角线上元素之和
• 同时D中长度为1,2,3,4的通路、回路各有多少条

长度	通路数量和	回路数量和
1	1+2+1+1+1+1+1=8	1
2	1+3+1+2+1+2+1=11	1+1+1=3
3	1+4+1+3+1+3+1=14	1
4	1+5+1+4+1+4+1=17	1+1+1=3
总数（长度小于或等于4）	50	8

可达矩阵

• R[i,j] = 1：存在从vi到vj的路径（包括i=j的情况，即顶点到自身的路径）
• R[i,j] = 0：不存在
• 计算规则为：已知矩阵B，计算$B+B^2+...+B^n$，得到结果后，把非零元素改为1

图的应用

欧拉图

• 无向图：连通的，且G中所有顶点的度数都是偶数
• 有向图：连通的，且G中每个顶点的入度等于出度

哈密顿图

• 哈密顿通路：经过图中每一个顶点一次且仅一次的通路
• 哈密顿回路：经过图中每一个顶点一次且仅一次并且回到起点的回路
• 哈密顿图：存在哈密顿回路的图

必要条件（用于排除非哈密顿图）

• 若图G是哈密顿图，则对任意非空顶点子集 $(S \subset V)$，有$\omega(G - S) \leq |S|$ 其中：
  • $G - S$：从图中删除集合S中的顶点及其关联边
  • $\omega(G - S)$：删除后图的连通分支数

充分条件

• 若图G有$n \geq 3$个顶点，
  • 且每个顶点的度数满足：$deg(v) \geq \frac{n}{2}, \quad \forall v \in V$
  • 且对任意两个不相邻的顶点u和v，有$deg(u) + \deg(v) \geq n$
• 则G是哈密顿图

判定流程

例：某会议8人参加，每人至少与其余7人中的4人有共同语言，问能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈

• 构造图 G ，其中 8 个顶点代表 8 个人，若两人有共同语言，则在对应顶点间连边
• 由题意，每人至少与 4 人有共同语言，故每个顶点的度数 ≥4
• $deg(v) \geq \frac{n}{2}, \quad \forall v \in V$即满足充分条件$deg(v) \geq \frac{8}{2} = 4$故可以安排

平面图

一个图G是平面图，如果它可以画在平面上，使得任意两条边除了端点外不相交（即无交叉）

欧拉公式：$\boxed{v - e + f = 2}$

• v ：顶点数$∣V|$
• e ：边数$∣E∣$
• f ：面数（包括外部面）

树

无向树

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

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

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

• 证明：设T有x片树叶，由握手定理及前一个定理可知
• $2(n-1)$即两倍边数，并且设有x片树叶，则有n-x结点
• 有$2(n-1) \geq x + 2(n-x)$即：$x \geq 2$

例：已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶。试求树叶数，并画出满足要求的非同构的无向树

• 设树叶数为x，总顶点数$n=1+2+x=x+3$，边数为$e=n-1=x+2$
• 所有顶点的度数和：$1*3+2*2+1*x=x+7$
• 根据握手定理：$x+7=2e=2(x+2)$解得x=3

D — C — B — A — E
        |
        F

最小生成树

定理：任何无向连通图都有生成树

加边法：按权重从小到大依次添加边，使得每次加边后不会形成回路，只需要加n-1次边

例：已知无向赋权矩阵，求最小生成树

0 3 0 0 9 1
3 0 4 10 0 6
0 4 0 5 7 2
0 10 5 0 8 0
9 0 7 8 0 11
1 6 2 0 11 0

把这个矩阵转成成无向图：就用A、B、C、D、E、F来表示顶点

生成最小树：先按权重从小到大排序，同时6个顶点那么只需要添加5条边

• AF(1)
• AF(1)、CF(2)
• AF(1)、CF(2)、AB(3)
• AF(1)、CF(2)、AB(3)、CD(5)
• AF(1)、CF(2)、AB(3)、CD(5)、CE(7)