离散数学

Part1 数理逻辑¶

第一章命题逻辑基本概念¶

1.1 命题与联结词¶

1.1.1 命题与真值¶

定义
- 命题：判断结果==惟一== 的陈述句
- 命题的真值：判断的==结果==
- 真值的取值：真、假
- 真命题：真值为真的命题
  
  假命题：真值为假的命题
判断命题
- 感叹句、祈使句、疑问句属于非陈述句，所以都不是命题
  - 这只兔子跑得真快呀！/ 请不要讲话！/你有铅笔吗？均不是命题
- 如果陈述句的判断结果==不惟一确定== ，那么该陈述句也不是命题
  - 明年我将去欧洲 / 任一大于2的偶数都可写成两个质数之和真值一定存在, 只是不知道, 是命题
  - x－y>2真值不确定, 不是命题
- 陈述句中的悖论也不是命题
  - 我正在说假话 / 理发师猜想

1.1.2 命题符号化¶

原子命题(简单命题)：一个不能再分解为更加简单的命题，是命题逻辑中研究的最基本单位
- 用小写英文字母 p, q, r, p_i, q_i等表示简单命题
复杂命题：由简单命题与联结词按照一定规则复合成的命题

1.1.3 复合命题及联结词¶

否定式与否定联结词 "$\neg$" (\neg)
合取式与合区联结词 "$\wedge$"(\wedge) / "$\cdot$"(\cdot) (且, 逻辑乘)
1. 合取相关规则 - p$\wedge$p 等价于 p - p$\wedge$1 等价于 p - p$\wedge$0 等价于 0 - p$\wedge$($\neg$p) 等价于 p - 合取满足==交换律== ： p $\wedge$ q 等价于 q $\wedge$ p - 合取满足==结合律== ： p $\wedge$(q $\wedge$r) 等价于(p$\wedge$q) $\wedge$r
析取式与析取联结词 "$\vee$" (或, 逻辑加)
1. 分类 - 相容或：全为真时，也为真(普通的或) - 排斥或：只有一真一假时，才为真(异或)
2. 例
  - 2 或 4 是素数 相容或 - 小明只能拿一个苹果或一个梨 排斥或 - 小红生于 2000 年或 2001 年 排斥或/相容或 (因为从实际生活来说，生于 2000 年和生于 2001 年必定一真一假)
蕴涵式与蕴涵联结词"$\rightarrow$"
1. a$\rightarrow$b, 则 a 是 b 的充分条件 / a蕴涵b
2. 真值表
3. p$\rightarrow$q 的逻辑关系等价于以下常见表达(中文连接词)
  
  - 充分系 - p 是 q 的充分条件 - 如果 p，则 q - 只要 p，就 q - 因为 p，所以 q - 必要系 - q 为 p 的必要条件 - p 仅当 q - 除非 q，才 p - 只有 q，才 p
等价式与等价联结词"$\leftrightarrow$" (当且仅当)
- 符号化后，只考虑真值，不考虑两个命题之间是否存在逻辑关系
联结词的优先顺序： (), $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$

1.2 命题公式及其赋值¶

命题常项和命题变项
- 命题常项：一个确定的具体的简单命题称为命题常项，也称为命题常元(相当于常数)
- 命题变项：当 p 所代表的只是一个抽象的命题，它可以表示任意的命题，则称 p 为命题变项，也称为命题变元(相当于变量)
  - 今后常用 p, q, r 表示命题变项
  - 注意：命题变项不是命题
- 指派真值：用一个特定的命题取代命题变元时，命题变元才能确定起真值(真 or 假)，这种取代称作对该命题变元指派真值
合式公式
1. 合式公式的一般化定义：将命题变项用联结词和括号按一定逻辑关系联结起来的符号串称作==合式公式== ，也称==命题公式== ，简称==公式==
2. 合式公式的递归定义：
  
  1. 单个命题常项或变项 p,q,r,…是合式公式； 2. 若 A 是合式公式，则$(\lnot A)$也是合式公式； 3. 若 A, B 是合式公式，则$(A\land B)$, $(A\lor B)$, $(A\rightarrow B)$, $(A\leftrightarrow B)$也是合式公式； 4. 只有有限次地应用(1)~(3)形成的包含命题变元、联结词和括号的符号串才是合式公式
  
  - 此处的 A、B 等称为元语言符号，代表抽象的公式
3. 子公式：若 A 为合式公式，B 为 A 的一部分，且 B 也是合式公式，则称 B 为 A 的子公式
公式的赋值
- 定义：给公式 A 中的命题变项 p₁, p₂, ..., p_n给予一定的真值指派，使其获得一组确定的真值，这个过程称为对 A 的一个==赋值== /解释

含有 n 个变项的公示有 2ⁿ个赋值

公式的分类
- 设 A 为一个命题公式
- 若 A 无成假赋值, 则称 A 为重言式(或永真式)
- 若 A 无成真赋值, 则称 A 为矛盾式(或永假式)
- 若 A 不是矛盾式, 则称 A 为可满足式 (即存在成真赋值)
  - 重言式是特殊的可满足式
公式的层次
- 若公式 A 是单个的命题变项, 则称 A 为0 层公式
- 当满足下列情况是, A 为 n+1 层公式
  1. $A=\lnot B$ , B 是 n 层公式
  2. $A=B\land C$, $A=B\lor C$, $A=B\rightarrow C$, $A=B\leftrightarrow C$ - 其中, BC 分别为 i 层和 j 层公式, 且 n>=0, $n=max(i, j)$;

第二章命题逻辑等值演算¶

主要内容
- 等值式
- 范式：合取范式/析取范式
- 联结词的完备集

2.1 等值式¶

2.1.1 等值式概念¶

定义 1：设 A 和 B 是两个命题公式，如果 A、B==在任意指派下== ，其真值都是相同的，则称 A 和 B 是等值的，或逻辑相等，记作$A\Leftrightarrow B$，称$A\Leftrightarrow B$为等值式

注意：应将等值($\Leftrightarrow$)与等价($\leftrightarrow$)相区别

定义 2：若$A\leftrightarrow B$是重言式, 则称 A 与 B 等值, 记作$A\Leftrightarrow B$, 并称$A\Leftrightarrow B$为等值式
等值式的性质：
1. 自反性：对任意公式 A, 有$A\Leftrightarrow B$
2. 对称性：对任意公式 A 和 B, 若$A\Leftrightarrow B$, 则$B\Leftrightarrow A$
3. 传递性：对任意公式 A, B 和 C, 若$A\Leftrightarrow B$, $B\Leftrightarrow C$, 则$A\Leftrightarrow C$
判断两个公式是否为等值式的基本方法是：通过两个公式的==真值表== 进行验证
- 较复杂, 不常用

2.1.2 基本等值式¶

双重否定律： $\lnot\lnot A\Leftrightarrow A$
幂等律： $A\lor A\Leftrightarrow A$， $A\land A\Leftrightarrow A$
交换律：$A\lor B\Leftrightarrow B\lor A$，$A\land B\Leftrightarrow B\land A$
结合律 $(A\lor B)\lor C\Leftrightarrow A\lor (B\lor C)$， $(A\land B)\land C\Leftrightarrow A\land (B\land C)$
分配律
- $A\lor (B\land C)\Leftrightarrow (A\lor B)\land(A\lor C)$
- $A\land (B\lor C)\Leftrightarrow (A\land B)\lor(A\land C)$
- 注意: 合取和析取都有分配律
德·摩根律 ($\lnot$拆括号)
- $\lnot(A\land B)\Leftrightarrow \lnot A\lor \lnot B$
- $\lnot(A\lor B)\Leftrightarrow \lnot A\land \lnot B$
- 补充： $\lnot(p\leftrightarrow q)\Leftrightarrow \lnot p\leftrightarrow q \Leftrightarrow (p\leftrightarrow \lnot q) $
吸收律 (分配律的推导公式)
- $A\lor(A\land B)\Leftrightarrow A$
- $A\land(A\lor B)\Leftrightarrow A$
零律: $A\lor1\Leftrightarrow1$, $A\land0\Leftrightarrow0$

同一律: $A\land1\Leftrightarrow A$, $A\lor0\Leftrightarrow A$
排中律: $A\lor\lnot A\Leftrightarrow1$

矛盾律: $A\land \lnot A\Leftrightarrow 0$
蕴含等值式 : $A\rightarrow B\Leftrightarrow\lnot A\lor B$ (将蕴含拆成非和或)
等价等值式: $A\leftrightarrow B\Leftrightarrow(A\rightarrow B)\land(B\rightarrow A)$ (很容易理解)
等价否定等值式: $A\leftrightarrow B\Leftrightarrow \lnot A\leftrightarrow\lnot B$ (很容易理解)
归谬论 : $(A\rightarrow B)\land(A\rightarrow \lnot B) \Leftrightarrow \lnot A$

2.2 析取范式和合取范式¶

简单合取、简单析取
合取范式、析取范式
极小项、极大项
主合取范式、主析取范式

2.2.1 合取范式&析取范式¶

简单合取
1. 定义: 仅由命题变项及其否定构成的合取式，称为简单合取式，其中每个命题变项或其否定称为合取项(文字)
2. 定理 1: 简单合取式为矛盾式(永假)的充要条件是：它同时含有某个命题变元及其否定 ($p\land \lnot p$)
析取范式
1. 定义: 由有限个简单合取式构成的析取式称作析取范式 (连接词是析取) - $(p\land \lnot q\land \lnot r)\lor(\lnot p\land r)\lor (q\land r)$
简单析取
1. 定义: 仅由命题变项及其否定构成的析取式，称为简单析取式，其中每个命题变项或其否定称为析取项(文字)
2. 定理 2：简单析取式为重言式(永真)的充要条件是：它同时含有某个命题变元及其否定 $(p\lor \lnot p)$
合取范式
1. 定义: 由有限个简单析取式构成的析取式称作合取范式 (连接词是合取)
- $(p\land \lnot q\land \lnot r)\lor(\lnot p\land r)\lor (q\land r)$
定理 3：任何一个合式公式都可以通过等值演算转换成与之等价的析取范式和合取范式
如何求公式的范式
1. 范式中不包括联结词$\rightarrow$和$\leftrightarrow$，因此需要将原来公式中包括的$\rightarrow$和$\leftrightarrow$消去
  
  -
2. 范式中不能出现以下公式

2.2.2 主析取范式¶

极小项: 在含有 n 个命题变元的简单合取式中，若 ① 每个命题变项与其否定式不同时出现，而 ② 二者之一必出现一次且仅出现一次，则称该简单合取式为极小项(每个命题变项都有, 且只有一个)
主析取范式：由 n 个命题变元构成的析取范式中，所有的简单合取式都是极小项，则称该析取范式为主析取范式
极小项特点
1. 每个极小项只有一组成真赋值；
2. 没有两个不同的极小项是等值的；
3. n 个命题变项可以生成 2ⁿ个极小项； - 将成真赋值用二进制编码
4. 任意两个不同极小项的合取必为假，所有极小项的析取必为真
例:
对极小项的取值进行编码
- m₀ (或 m₀₀)称作极小项$\lnot p\land\lnot q$的编码；
- m₁ (或 m₀₁)称作极小项$\lnot p\land q$的编码；
- m₂ (或 m₁₀)称作极小项$p\land\lnot q$的编码；
- m₃(或 m₁₁)称作极小项$p\land q$的编码；

2.2.3 主合取范式¶

极大项: 在含有 n 个命题变元的简单析取式中，若每个命题变项与其否定式不同时出现，而二者之一必出现一次且仅出现一次，则称该简单析取式为极大项
主合取范式: 由 n 个命题变元构成的合取范式中，所有的简单析取式都是极大项，则称该合取范式为主合取范式
极大项特点:
- 每个极大项只有一组成假赋值；
- 没有两个不同的极大项是等值的；
- n 个命题变项可以生成 2ⁿ个极大项；
- 任意两个不同极大项的析取必为真，所有极大项的合取必为假

如果简单合取式 A 不是极小项, 则可以$A\Leftrightarrow A\land 1 \Leftrightarrow A\land (p \lor \lnot p) \Leftrightarrow (A\land p)\lor(A\land \lnot p)$

如果简单析取式 A 不是==极大项== , 也可以$A\Leftrightarrow A\or 0 \Leftrightarrow A\lor (p \land \lnot p) \Leftrightarrow (A\lor p)\land(A\lor \lnot p)$

(因为不太习惯加法对乘法的分配律, 需要多加留意)

定理 : 设 m_i与 M_i是由 n 个命题变项形成的极小项和极大项，

则$①\lnot m_i \Leftrightarrow M_i$, $②\lnot M_i \Leftrightarrow m_i$
- 根据主析取范式(真值表中取 1 的项)可以推出主合取范式(真值表中取 0 的项)
小结: 主析取范式和主合取范式可以用于一下问题的求解
1. 求公式的成真和成假赋值
2. 判断两个公式的等值关系
3. 判断公式类型

2.3 联结词完备集 –¶

定义: 设 S 是一个联结词集合，如果任何命题公式都可以由==仅含 S 中的联结词构成的公式表示== ，则称 S 是联结词全功能集，也称联结词完备集
若 S₁, S₂是两个联结词集合, 且$S_1\subseteq S_2$, 若 S₁是全功能集, 则 S₂也是全功能集
常见的联结词完备集
1. $S_1 = \{\lnot, \land, \lo<span class="md-search-hit md-search-select">r,</span> \rightarrow, \leftrightarrow\}$
2. $S_2 = \{\lnot, \land, \lor, \rightarrow\}$
  
  - $p\leftrightarrow q \Leftrightarrow (p\rightarrow q)\land(q\rightarrow p)$
3. $S_3 = \{\lnot, \land, \lor\}$
  
  - $p\rightarrow q \Leftrightarrow \lnot p \lor q$
4. $S_4 = \{\lnot, \land\}$
  
  - $p\rightarrow q \Leftrightarrow \lnot p \lor q$
5. $S_5 = \{\lnot, \lor\}$
6. $S_6 = \{\lnot, \rightarrow\}$

2.4 可满足性问题与消解法 –¶

引入: 如何判断公式的可满足性
- ① 真值表, ② 主范式, ③ 消解法
- 文字 $l$ : 一个命题变项 / 一个命题的变项的否定
- 文字的补 $l^C$: $$ l^C= \begin{cases} \lnot p & ,若 l=p \ p & ,若 l=\lnot p \end{cases} $$
定义: 设$C_1 = l\lor C_1'$, $C_2 = l^C\lor C_2'$ , C₁' 和 C₂' 不含 l 和 l^C. 称为$C_1'\lor C_2'$为 C₁和 C₂(以 l 和 l^C为消解文字)的消解式或消解结果, 记作$\textcolor{#66ccff}{Res(C_1, C_2)}$, 由 C₁和 C₂得到的规则称作消解规则 (使用消解规则即为消解法)
- 例: $Res(\lnot p\lor q\lor r, p\lor q\lor \lnot s) = q\lor r\lor \lnot s$
- 消解法使用的前提条件是: 命题公式已经通过等值演算转换成了==合取范式==
- 定义: 空简单析取式 $\lambda$: 不含任何文字的简单析取式
  - 当 C1 和 C2 都是单文字的简单析取式且互补时($p, \lnot p$), C1 和 C2 的消解结果不含任何文字, 这时称此结果为空简单析取式
  - 规定: $\lambda$是不可满足的
- 定义: 用$\textcolor{#66ccff}{S\approx S'}$表示 S 是可满足的当且仅当 S'是可满足的
定理 1: $C_1\land C_2 \approx Res(C_1, C_2)$
- 证明:
定义: 设 S 是一个合取范式, C1,C2,.....,Cn 是一个简单析取式序列. 如果对每一个 i(1<=i<=n), Ci 是 S 的一个简单析取式或者是 Res(C_i,C_k)(1<=j<k<i), 则称此序列是由 S 导出 Cn 的消解序列. 当==Cn=$\lambda$== 时, 称此序列是 S 的一个否证.
- 定理 2: 一个合取范式是不可满足的当且仅当它有==否证==
例题
1. 证明一个公式是矛盾式 -通过构造否证证明
2. 判断是否是可满足的 -循环消解(为了保证一定已经穷举了)
  
  - 输入: 合式公式 A 输出: 当 A 是可满足时, 回答“Yes”; 否则回答“No”
  1. 求 A 的合取范式 S
  2. 令$S_0\leftarrow \emptyset, S_2\leftarrow \emptyset, S_1\leftarrow \{S$的所有简单析取式$\}$ 3.
  3. For $C_1\in S_0$和$C_2\in S_1$
  4. If (C1, C2 可以消解) then
  5. 计算 C¬Res(C1,C2)
  6. If (C=l) then
  7. 输出“No”, 计算结束
  8. If $(C\notin S_0且C\notin S_1)$ then //产生了新的消解结果
  9. 把 C 加入 S2 11.
  10. $For\ C_1\in S_1, C_2\in S_1且C_1\neq C_2$
  11. If C1, C2 可以消解 then
  12. 计算 C¬Res(C1,C2)
  13. $If\ (C=l)\ then$
  14. 输出“No”, 计算结束
  15. $ If (C\notin S_0 且 C\notin S_1) then$ //产生了新的消解结果
  16. 把 C 加入 S2
  17. $If (S2=\emptyset) then $ //没有新的消解结果
  18. 输出“Yes”, 计算结束
  19. $ Else S_0\leftarrow {S_0\cup S1},S1\leftarrow S2, S2\leftarrow\empty, goto line4$
注意点
1. 定理 1 说明$C_1\land C_2 和 Res(C_1,C_2) $具有相同的可满足性，但是两者并==不一定等值==
2. 如果对 C1 和 C2 有多对文字可以消解，那么无论选择哪一对文字作为消解对象，消解结果等值

第三章命题逻辑的推理理论¶

主要内容:

推理的形式结构
自然推理系统 P

3.1 推理的形式结构¶

推理的形式结构
判断推理有效性的方法
重言蕴涵式

3.1.1 推理的形式结构¶

一组前提为命题公式 A₁, A₂, ......, A_n
一个结论为命题公式 B
则推理形式结构为: A₁, A₂, ......, A_n 推出 B, 记为:
- 前提是有限个公式的集合, 而不是序列
- 这种形式的推理表示不常用

3.1.2 推理的有效性¶

定义：若对于每组赋值，当$A_1\land A_2\land...\land A_k $为真时, 保证*B*也为真；或者$A_1\land A_2\land...\land A_k $为假，则称由A1,A2,…, A_k推 B 的推理正确(有效), 否则推理不正确(无效)
- 有效推理的形式结构
  
  无效推理的形式结构
- 推理有效，结论并不一定正确
- 推理的有效性和前提中公式的顺序无关
- 推理有效性与前提、结论之间的关系类似蕴涵联结关系
定理: 定理："$A_1\land A_2\land...\land A_k 推B$"的推理正确当且仅当$A_1\land A_2\land...\land A_k \rightarrow B$为==重言式== (没有成假赋值)
推理的形式结构: $A_1\land A_2\land...\land A_k \rightarrow B$ (常用)

前提: A₁, A₂, ......, A_k 结论: B

若推理正确, 则将这个正确的推理记作 $A_1\land A_2\land...\land A_k \Rightarrow B$
- $\Rightarrow$ 用于表示==蕴含式是重言式== (即重言蕴涵式)

3.1.3 判断推理有效性的方法¶

常用于判断推理有效性的方法
- 真值表法
  - 使用真值表判断蕴含式$A_1\land A_2\land...\land A_k \rightarrow B$的真假
- 等值演算法
  - 化简$A_1\land A_2\land...\land A_k \rightarrow B$
- 主析取范式法
  - 求$A_1\land A_2\land...\land A_k \rightarrow B$ 的主析取范式, 判断有无成假赋值

本质: 证明$A_1\land A_2\land...\land A_k$ =1 时, B!=0

3.1.4 重言蕴涵式 / 推理定律¶

一些重要的重言蕴含式, 被称作推理定律

定律	定律名	理解
$A\Rightarrow (A\lor B), B\Rightarrow (A\lor B)$	附加律	$A=1时,A\lor B=1$
$A\land B\Rightarrow A, A\land B\Rightarrow B$	化简律	$A\land B=1, A=1, B=1$
$(A\rightarrow B)\land A\Rightarrow B$	假言推理
$(A\rightarrow B)\land \lnot B \Rightarrow \lnot A$	拒取式
$(A\lor B)\land \lnot B\Rightarrow A$	析取三段论
$(A\rightarrow B)\land (B\rightarrow C)\Rightarrow (A\rightarrow C)$	假言三段论	蕴涵可以传递
$(A\leftrightarrow B)\land (B\leftrightarrow C)\Rightarrow (A\leftrightarrow C)$	等价三段论	等价可以传递
$(A\rightarrow B)\land(C\rightarrow D)\land(A\lor C)\Rightarrow (B\lor D)$	构造性二难	两个蕴涵 $\land$ 前键的或$\Rightarrow$ 后键的或
$(A\rightarrow B)\land(\lnot A\rightarrow B)\Rightarrow B$	构造性二难(特殊形式)	$C=\lnot A, D=B$ 感觉没什么用
$(A\rightarrow B)\land(C\rightarrow D)\land(\lnot B\lor \lnot D)\Rightarrow (\lnot A\lor \lnot C)$	破坏性二难	二蕴涵 $\land$ 后键的非的或$\Rightarrow$ 前键的非的或

此外, 一个公式也较为常用: $p\rightarrow q\Leftrightarrow \lnot q \rightarrow \lnot p$

说明:
- 同基本等值式一样, 式子中的 ABC 均为元语言符号
- 若某推理符合上述某条重言蕴涵式, 则它们自然是正确的
  - 证明推理正确: 多次运用此规则, 从结果出发, 倒推构造
- $A\Leftrightarrow B 产生两条推理定律: A\Rightarrow B, B\Rightarrow A$

3.2 自然推理系统 P¶

3.2.1 自然推理系统 P¶

引入
- 证明推理的有效性是命题逻辑推理理论的重要组成部分
- 证明过程以一定的形式系统为背景
- 自然推理系统 P是形式系统的一种类型，即从==给定的前提出发== ，根据==推理规则== 进行推理演算，最后得到的命题公式是推理的结论(和正常的思维方式相同)
自然推理系统 P 由三个部分组成：
1. 字母表：命题变项符号；联结词符号；括号和逗号
2. 命题公式
3. 推理规则

3.2.2 推理规则¶

前提引入: 在证明的任意步骤都可以引入前提
结论引入: 在证明的任何阶段得到的中间结论都可以作为前提引入
置换规则: 任何公式的子公式可以使用等值的公式进行替换，得到公式序列中的有一个公式
九条推理定律 + 合取引入:

3.2.3 构造推理证明直接法¶

例：构造下面推理的证明：

“若明天是星期一或星期三，我就有课若有课，今天必备课我今天下午没备课所以，明天不是星期一和星期三”

3.2.4 附加前提证明法¶

欲证明: 前提: A₁, A₂, ......, A_k 结论: $C\rightarrow B$

等价于证明: 前提: A₁, A₂, ......, A_k, C 结论: $B$

善用能够简化证明过程

3.2.5 归谬法¶

归谬法:
- 欲证明$A_1, A_2, ..., A_k$ 结论: B
- 将$\lnot B$加入前提 , 若能够推出矛盾(如$p\land \lnot p$), 则推理正确

归谬论证明:
- $A_1\land A_2 \land ...\land A_k\rightarrow B$
  
  $ \Leftrightarrow \lnot (A_1\land A_2 \land ...\land A_k)\lor B $
  
  $ \Leftrightarrow \lnot (A_1\land A_2 \land ...\land A_k\land \lnot B)$
- 括号内部为矛盾式(永假), 当且仅当$A_1\land A_2 \land ...\land A_k\rightarrow B$为重言式(即 $A_1\land A_2\land...\land A_k \Rightarrow B$ )

例: 构造下面的推理

证明:	公式
① $q$	结论否定引入
② $r \rightarrow s$	前提引入
③ $\lnot s$	前提引入
④ $ \lnot r$	②③ 拒取式
⑤ $\lnot(p\land q)\lor r$	前提引入
⑥ $\lnot(p\land q)$	④⑤ 析取三段论
⑦ $\lnot p \lor \lnot q$	⑥ 置换
⑧ $\lnot p$	①⑦ 析取三段论
⑨ $p$	前提引入
⑩ $\lnot p \land p$	⑧⑨ 合取

$\lnot p\land p \Leftrightarrow 0$ 所以推理正确

第四章一阶逻辑基本概念¶

4.1 一阶逻辑命题符号化¶

4.1.1 个体词, 谓词, 量词的概念¶

个体词的基本概念
1. 个体词(个体): 可以独立存在的具体或抽象的==客体== - 例: 我是老师, 其中"我"就是个体词; 张三比李四高其中“张三”、“李四”都是个体词
2. - 个体常项：具体的客体，用a, b, c表示(类比常数 C) - 个体变项：抽象或泛指的事物，用x, y, z表示
3. 个体域(论域): 个体变项的取值范围 - 有限个体域: 即个体域是有限集合 - 无限个体域: 即个体域是无穷集合 - 全总个体域: 宇宙间一切事物组成
谓词的基本概念
1. 谓词: 表示个体词性质或者相互之间==关系== 的词
  
  - 例: 张华是大学生...是大学生是谓词; 张三比李四高...比...高是谓词
2. - 谓词常项：表示==具体== 性质或关系
    
    - 例：…是大学生，记为 F，F(张华)表示“张华是大学生”
    - 谓词变项：表示==抽象== 及泛指的性质或关系
      
      例：…具有性质F，记为 F， F(张华)：张华具有性质 F
    - 谓词常项和变项都用大写字母(F, G, H...)表示
3. - n 元谓词(n>=2): 含有 n 个个体变项的谓词。如：L(x,y)：x³y，L 是一个二元谓词。
    - 一元谓词: 只含有一个个体变项的谓词。如：F(x)：x 是女孩。
    - 0 元谓词: 不含个体变项的谓词。
4. 谓词逻辑包括命题逻辑, 只要将变项用常项替代
  
  - 例 1: 用 0 元谓词将下述命题符号化 - - -
量词的基本概念
1. 量词: 表示个体变项或变项之间数量关系的词
2. 全称量词$\forall$ (forall) : 表示==任意的== , 所有的, 一切的...
  
  - $\forall x$ 表示对个体域中所有的 x - $\forall xF(x)$ 表示 对个体域中所有的 x 都有性质 F - 例：F(x):x喜欢喝咖啡。当 x 的个体域为人类集合时，“所有的人都喜欢喝咖啡”可以符号化为：$\forall x F(x)$
3. 存在量词$\exist$ (exist) : 表示==存在== , 有的...
  
  - $\exist x F(x)$表示对个体域中至少有一个 x 具有性质 F。
  
  - “有的人喜欢喝咖啡”符号化为： $\exist x F(x)$

4.1.2 一阶逻辑中命题符号化¶

默认情况下题目的个体域指 全总个体域
全总个体域时记得用谓词表示个体域, $\forall$ 一般使用蕴涵连接($\rightarrow$)个体域和其他谓词; $\exist$ 一般使用合取连接($\land$)个体域和其他谓词
例 2：在两种不同的个体域 D1、D2 中，利用一阶逻辑的思想将下面命题符号化: (1) 人都爱美。 (2) 有人用左手写字。

D1：个体域为人类集合； D2：全总个体域。
- 当个体域为 D1 时:
  - (1) 人都爱美 设 G(x): x 爱美; 符号化为$\forall x G(x)$
  - (2) 有人用左手写字 设 G(x): x 用左手写字; 符号化为$\exist x G(x)$
- 当个体域为 D2(全体域)时: 设 F(x): x 为人
  - (1) 人都爱美 设 G(x): x 爱美; 符号化为$\forall x (F(x)\rightarrow G(x))$
  - (2) 有人用左手写字 设 G(x): x 用左手写字; 符号化为$\exist x (F(x)\land G(x))$
例 3：采用谓词逻辑将下列命题符号化
1. (1) 有的偶数大于 10
  
  - 设: P(x): x 是偶数; Q(x): x>10
  
  - $\exist x(P(x)\land(Q(x)))$
2. (2) 有的无理数大于有的有理数
  
  - 令 F(x): x 是无理数, G(y): y 是有理数, L(x,y)：x>y
  
  - $\exist x(F(x)\land \exist y(G(y) \land L(x, y)))$
3. (3) 没有不犯错的人
  
  - 设：P(x)：x 是人； Q(x)：x 犯错误。
  
  - $\forall x(P(x)\rightarrow Q(x))$ 或者 $\lnot \exist x(P(x) \land \lnot Q(x))$
4. (4) 任何金属都可以溶解在某种溶液里
  
  - 令 F(x): x 是金属，G(x): x 是液体，L(x,y): x 溶解在 y 中
  
  - $\forall x (F(x)\rightarrow \exist y(G(y) \land L(x, y)))$
5. (5) 某些人对所有的花粉都过敏
  
  - 令 F(x): x 是人, G(y): y 是花粉, L(x,y)：x 对 y 过敏。
  
  - $\exist x(F(x) \land \forall y(G(y) \rightarrow L(x, y)))$
6. (6) 所有的学生都上课了，这是错的
  
  - 令 F(x): x 是学生, G(x): x 上课了
  
  - $\lnot \forall x(F(x)\rightarrow G(x))$
  
  - 相当于"有些学生没上课" $\exist x(F(x) \land \lnot G(x))$
7. (7) 不存在最大的整数
  
  - 令 F(x): x 是整数, L(x,y)：x 比 y 大
  
  - $\lnot \exist x(F(x) \land \forall y(F(y) \land L(x, y)))$
  
  - 相当于"任意一个整数, 都存在比它大的整数" $\forall x(F(x)\rightarrow \exist y(F(y)\land L(y, x))$

小结¶

在不同的个体域中，同一个命题的符号化有可能不同。

同一个命题，在不同的个体域中的真值也可能不同。

多个量词出现时，顺序不能随意调换

4.2 一阶逻辑公式及解释¶

4.2.1 原子公式和合式公式¶

定义：设$P(x_1, x_2, …, x_n)$是任意的n 元谓词，$t_1,t_2,…,t_n$是任意的n 个项，则称$P(t_1,t_2,…,t_n)$是原子公式
- 项的定义:
  1. 个体常项和个体变项都算是项
  2. 若$\varphi(x_1, x_2, …, x_n)$是任意的 n 元函数，$t_1,t_2,…,t_n$是任意的 n 个项，则$\varphi(t_1,t_2,…,t_n)$是项
  3. 所有的项都是有限次使用 1, 2 得到的
命题逻辑合式公式和谓词逻辑合式公式
- 命题逻辑合式公式的定义：
  1. 单个命题常项或变项(原子命题公式) p,q,r,…是合式公式；
  2. 若 A , B 是合式公式，则 $(\lnot A), (A\land B), (A\lor B), (A\rightarrow B), (A\leftrightarrow B)$也是合式公式；
  3. 只有有限次地应用(1)~(2)形成的包含命题变元、联结词和括号的符号串才是合式公式。
- 谓词逻辑合式公式的定义：
  1. 原子公式(n 元谓词)是合式公式
  2. 若 A、B 是合式公式，则 $(\lnot A), (A\land B), (A\lor B), (A\rightarrow B), (A\leftrightarrow B)$ 也是合式公式;
  3. 若 A 是合式公式，则$\forall xA, \exist xA$是合式公式; (命题逻辑没有存在 $\exist$ 和任意 $\forall$ )
  4. 所有合式公式都是有限次应用(1)~(3)形成的符号串

4.2.2 个体变项的自由出现与约束出现¶

定义：在公式$\forall xA$ 和 $ \exist xA$中，称
1. x 为指导变元；
2. A 为相应量词的辖域；
3. 在$\forall xA$ 和 $ \exist xA$的辖域中，x 的所有出现都称为约束出现；
4. A 中不是约束出现的其他变项均称为自由出现。
例: 说明以下各式量词的辖域与变元的约束情况

(1) $\forall x\forall y(P(x,y)\land Q(x, y)) \land \exist xP(x, y)$

4.2.3 公式的解释¶

由于公式是抽象的符号串，若不对它们给以具体解释，则公式是没有实在意义的。

定义: 解释$I$由下面 4 个部分组成
1. 非空个体域$D_I$
2. $D_I$中一些特定元素的集合$\{\overline{a_1}, ..., \overline{a_i}, ...\}$
3. $D_I$上特定函数集合$\{ \overline{f_i}^n|i, n\geq 1 \}$
4. $D_I$上特定谓词集合$\{\overline{F_i}^n|i, n\geq 1 \}$
例:
例: 给定解释$I$如下
- 个体域$D=N$ (包括 0)
  - $a = 2$
  - $f(x,y)=x+y, g(x,y)=xy$
  - 谓词 $F(x,y):x=y$
说明下列公式在 I 下的涵义,并讨论真值。
I 下的赋值$\textcolor{#66ccff}{\sigma}$：对每一个个体变项符号 x 指定 DI 中的一个值$\sigma(x)$

设公式 A，规定：在解释 I 和赋值$\sigma$下
1. 取个体域$D_I$
2. 若 A 中含个体常项符号 $a$ 就将它替换成 $\overline{a}$
3. 若 A 中含函数符号$f$就将它替换成 $\overline{f}$
4. 若 A 中含谓词符号 F 就将它替换成 $\overline{F}$
5. 若 A 中含自由出现的个体变项符号 x 就将它替换成 $\sigma(x)$

小结
- 给定解释 I 和 I 下的赋值, 任何公式都被解释成命题
- 对于闭式, 由于没有自由出现的个体变项符号, 所以不需要赋值, 只需要解释

4.2.4 公式的类型¶

分类
- 永真式(逻辑有效式)：无成假解释
- 矛盾式(永假式)：无成真解释
- 可满足式：至少有一个成真解释
例一:
例二: 判断公式类型
- 定义：设 A₀是含命题变项$p_1, p_2, …,p_n$的==命题公式== ，$A_1,A_2,…,A_n$是 n 个==谓词公式== ，用$A_i$代替$A_0$中所有的$p_i (1\leq i\leq n) $，得到的公式 A 称为 A₀的代换实例
- 定理: 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式

第五章一阶逻辑等值演算与推理¶

5.1 一阶逻辑等值式与置换规则¶

5.1.1 等值式的概念¶

定义: 若$A\leftrightarrow B$ 为永真式，则称 A 与 B 是等值的，记作 $A\Leftrightarrow B$，并称$\textcolor{#66ccff}{A\Leftrightarrow B}$为等值式。其中 A、B 是一阶逻辑中任意的两个合式公式

5.1.2 基本等值式¶

命题逻辑中 16 组基本等值式的代换实例 2.1.2 基本等值式
- 命题逻辑中的基本等值式在谓词逻辑中均适用。
有限个体域中, 消去量词等值式
- 设个体域为$D = \{a_1, a_2, ..., a_n\}$
  
  $\forall xA(x) \Leftrightarrow A(a_1)\land A(a_2)\land ...\land A(a_n)$
  
  $\exist xA(x) \Leftrightarrow A(a_1)\lor A(a_2)\lor ...\lor A(a_n)$
量词==否定== 等值式
- $\lnot \forall xA(x) \Leftrightarrow \exist x\lnot A(x)$
- $\lnot \exist xA(x) \Leftrightarrow \forall x\lnot A(x)$
量词==辖域== 收缩与扩张等值式
- 设$A(x)$是含 x自由出现的公式, B 中不含 x 的出现
- 全称量词 $\forall$
  - $\forall x(A(x)\lor B) \Leftrightarrow \forall xA(x)\lor B$
  - $\forall x(A(x)\land B) \Leftrightarrow \forall xA(x)\land B$
  - $\forall x(A(x)\rightarrow B) \Leftrightarrow \textcolor{#ee0000}{\exist} xA(x)\rightarrow B$
  - $\forall x(B\rightarrow A(x)) \Leftrightarrow B\rightarrow \forall xA(x)$
- 存在量词$\exists$
  - $\exist x(A(x)\lor B) \Leftrightarrow \exist xA(x)\lor B$
  - $\exist x(A(x)\land B) \Leftrightarrow \exist xA(x)\land B$
  - $\exist x (A(x)\rightarrow B) \Leftrightarrow \textcolor{#ee0000}{\forall} xA(x)\rightarrow B$
  - $\exist x(B\rightarrow A(x)) \Leftrightarrow B\rightarrow \exist xA(x)$
量词分配等值式
- $\forall x(A(x)\land B(x)) \Leftrightarrow \forall xA(x)\land \forall xB(x)$
- $\exist x(A(x)\lor B()x) \Leftrightarrow \exist xA(x)\lor \exist xB(x)$

5.1.3 等值演算与置换规则¶

置换规则：设$\Phi(A)$是含有公式 A 的公式，用公式 B 置换$\Phi(A)中$所有的 A 后得到新的公式$\Phi(B)$, 若$A\Leftrightarrow B, 则\Phi(B)\Leftrightarrow \Phi(A)$
等值演算的基础:
1. 一阶逻辑的基本等值式
2. 置换规则, 换名规则, 代替规则
例一: 下面的命题都有两种不同的符号化形式，写出其中的一种，然后通过等值演算得到另一种。
1. (1) 没有不犯错误的人
  
  -
2. (2) 不是所有的人都爱看电影
  
  -
例二: 设个体域 D={a,b,c}，在 D 中消去下列公式中的量词。
1. (1) $\forall x(F(x) \land \exist yG(y))$
  
  - 法一:
  
  - 法二:
  
  - 小结：采用不同的演算过程同样可以达到消去量词的目的，但是如何演算才更简单呢？结论是==将量词辖域尽可能的缩小，然后再消量词==
2. (2) $\forall x\forall y(F(x)\rightarrow G(y))$
  
  - 法一:
  
  - 法二:
例三: 证明下面的谓词公式是永真式
1. (1) $\forall xF(x) \rightarrow \exist xF(x)$
  
  -
2. (2) $\forall x(A\rightarrow B)\rightarrow(\forall xA \rightarrow \forall xB)$
  
  -

5.2 一阶逻辑前束范式¶

定义：设 A 为一个一阶逻辑公式, 若 A 具有如下形式$Q_1x_1Q_2x_2…Q_kx_k\textcolor{#ee0000}B$, 则称 A 为==前束范式== , 其中$Q_i (1\leq i\leq k)为\forall或\exist$，B 为不含量词的公式。(将量词前束)
例一: 求下列公式的前束范式

(1) $\lnot \exist x(M(x)\land F(x))$

(2) $\forall xF(x)\land \lnot \exist xG(x)$
- 法一:
- 法二: 换名规则
换名规则：将量词辖域中某个约束变项的所有出现及对应的指导变元，改成另一个在辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值。(在辖域扩展时使用)
- $\forall xF(x)\rightarrow \exist y(G(x,y) \land \lnot H(y))$
- $(\forall x_1F(x_1, x_2)\rightarrow \exist x_2G(x_2)) \rightarrow \forall x_1H(x_1, x_2, x_3)$
定理：一阶逻辑中的任何公式==都存在== 与之等值的前束范式
- 公式的前束范式不唯一
- 求公式的前束范式的方法: 利用基本等值式 / 换名规则进行等值演算

5.3 一阶逻辑的推理理论¶

5.3.1 推理的形式结构¶

推理的形式结构有两种:
- 第一种: $A_1\land A_2 \land ... \land A_k \rightarrow B \ \ \ (*)$
- 第二种:
  
  前提：$A_1，A_2，…，A_k$ 结论： B 其中 $A_1，A_2，…，A_k, B$为一阶逻辑公式.
- 若$(*)$为永真式, 则称==推理正确== , 否则称==推理不正确==

判断推理是否正确的方法:
- 等值演算法, 引用这种方法时应该使用第一种形式结构
- 构造证明法, 采用第二种形式结构

5.3.2 重要的推理定律¶

第一组: 命题逻辑推理定律代换实例
- 如: $\forall xF(x)\land \exist yG(y) \Rightarrow \forall xF(x)$ 化简律代换实例 ( A = $\forall xF(x)$ B = $ \exist yG(y)$ )
第二组: 由基本等值式生成的推理定律 ($\Leftrightarrow 得到\Leftarrow 和 \Rightarrow$)
- 如: 由$\lnot \forall xA(x)\Leftrightarrow \exist x\lnot A(x)$ 生成 $\lnot \forall xA(x)\Rightarrow \exist x\lnot A(x)$ 和 $\exist x\lnot A(x) \Rightarrow \lnot \forall xA(x) $
第三组注意与量词分配等值式相区别
- $\forall xA(x)\lor\forall xB(x) \Rightarrow \forall x(A(x)\lor B(x)) $ 全称对析取只有合并
- $\exist x(A(x)\land B(x)) \Rightarrow \exist xA(x)\land \exist xB(x)$ 存在对合取只有分配
- $\forall x(A(x)\rightarrow B(x))\Rightarrow \forall xA(x)\rightarrow \forall xB(x)$ 全称对蕴涵的分配
- $\exist x(A(x)\rightarrow B(x))\Rightarrow \exist xA(x) \rightarrow \exist xB(x)$ 存在对蕴涵的分配

5.2.3 推理规则¶

命题逻辑的推理定律在逻辑中依然适用 (但是要注意量词的辖域, 本质是使用了替换规则)
全称量词消去规则 (记为UI) 全称 → 变项/常项 $\forall -$
- - 消为个体变项y / 个体常项c
- 在(1)式中，y 应为任意的==不在 A(x)中约束出现== 的个体变项。
- 在(2)式中，c 为任意的==未在 A(x)中出现== 过的个体常项。
- 用 y 或 c 去取代 A(x)中的自由出现的 x 时，一定要在 x 自由出现的==一切地方== 进行取代。
全称量词引入规则(记为UG) 变项 → 全称
- 无论 A(y)中自由出现的个体变项 y 取何值，A(y)应该均为真。
- x 约束尽量不出现在 A(y)中。
存在量词消去规则 (记为EI) 存在 → 常项
- c 是个体域中==使 A 为真== 的某个确定的个体，且==c 不在 A(x)中出现== 。
- 若 A(x)中除自由出现的 x 外，还有其他自由出现的个体变项，此规则不能使用。
存在量词引入规则 (记为EG) 常项 → 存在
- 该式成立的条件是：
  - c 是==使 A 为真== 的特定个体常项
  - 取代 c 的 x==不能在 A(c)中出现过==

5.2.4 构造推理证明¶

一阶逻辑自然推理系统F 包含:
1. 字母表，即一阶语言的字母表
2. 合式公式
3. 推理规则
- 构造推理证明的方法: 直接法, 附加前提引入法, 归谬法
- 注意与命题逻辑的推理区别比较
证明思路: $带有量词的公式\stackrel{UI/EI}{\longrightarrow}不带量词的公式\stackrel{使用推理规则}{\longrightarrow}与结论相似的形式\stackrel{UG/EG}{\longrightarrow}添加量词, 完成证明$
例 2：证明苏格拉底三段论: “人都是要死的, 苏格拉底是人，所以苏格拉底是要死的。”
例 3：乌鸦都不是白色的。北京鸭是白色的。因此，北京鸭不是乌鸦。

补充练习¶

有的病人相信医生，病人都不相信骗子，所以医生都不是骗子。
- $F(x):x是病人\quad G(x):x是医生$ $H(x):x是骗子\quad L(x,y):x相信y$
前提: $\forall x(P(x)\lor Q(x))$

结论: $\forall xP(x) \lor \exist xQ(x)$

Part2 集合论¶

常用符号¶

算式	markdown	描述
$\emptyset$ Ø $\varnothing$	`\emptyset` `\empty` 或者复制"Ø" / `\varnothing`	空集
∈	`\in`	属于
$\ni$	`\ni`
$\notin$	`\notin`	不属于
⊂	`\subset`	离散数学中是真子集
⊃	`\supset`
$\not\subset$ ⊈	`\not\subset` 或者复制 "⊈"	非子集
$\subseteq$	`\subseteq`	真子集离散数学中是子集
⊇	`\supseteq`
$\cup$	`\cup` 或 ∪	并集
$\bigcup$	`\bigcup`	并集
$\cap$	`\cap`	交集
$\bigcap$	`\bigcap`	交集
$\uplus$	`\uplus`	多重集
$\biguplus$	`\biguplus`	多重集
⊏	`\sqsubset`
⊐	`\sqsupset`
⊓	`\sqcap`
⊑	`\sqsubseteq`
⊒	`\sqsupseteq`
$\vee$	`\vee`
$\wedge$	`\wedge`
$\setminus$	`\setminus`	集合中的减法
$\circ$	`\circ`	二元关系复合运算
↾		关系的限制
$\preccurlyeq$	`\preccurlyeq` / ≼	偏序关系 prec : precedence curly : 卷曲的
$\prec$	`\prec` / ≺
⊕

第六章集合代数¶

离散数学中的常用数集和运算¶

符号	集合含义
N	自然数(包括 0)
Z	整数
Z⁺	正整数
Z_n	{0, 1, … , n-1}
Q	有理数
R	实数
C	复数

符号	常见含义
$\oplus$	① 集合的对称差 ②$<Z_n, \oplus>$ 模 n 加法 ③ 异或
$x≡y mod k $	x 与 y 模 k 同余

6.1 集合的基本概念¶

6.1.1 集合的定义与表示¶

定义(集合): 集合是具有某种相同特点或性质的对象的聚合
- 注意: 集合的内涵应该是确定的
  
  即, 给定任意一个对象, 都能明确地判断该对象是否属于这个集合
集合的表示方法
1. 列元素法(列举法)：这种表示方法就是将集合的所有元素一一列举出来，元素之间用逗号分开，并用花括号将它们括起来 - $e.g.\quad A=\{2,4,6,8,10\}$ - $A=\{x| x是偶数\land x\leq 10\land x>0\} \quad集合A中的元素是大于0且小于等于10的偶数$
2. 谓词表示法(特征法)：$B=\{ x | P(x) \}\quad B 由使得 P(x) 为真的 x 构成$
定义(集合的元素)：集合中的每一个对象称为这个集合的一个元素。
集合的特点：
1. 互异性：集合的元素彼此不同；
2. 无序性：集合的元素是无序的；
3. 集合的元素都是集合。

6.1.2 集合与元素间的关系¶

$e.g. A=\{ a, \{b,c\}, d, \{\{d\}\} \}$
- $\{b,c\} \in A; b\notin A, c\notin A$
- $\{\{d\}\} \in A; \{d\} \notin A; d\in A$
当一个集合中的元素个数有限时，该集合称为有限集；
有限集 A 中的元素的个数称为集合 A 的基。记作|A|。如 A={a,b,c}，则|A|=3。
集合中的元素的个数无限时，该集合称为无限集

6.1.3 集合之间的关系¶

定义(子集)：如果集合 A 中的每一个元素又都是集合 B 中的元素，则称A 是 B 的子集,记作$A\subseteq B$ - $A\subseteq B \Leftrightarrow \forall x(x\in A \rightarrow x\in B)$
定义(集合相等)：当两个集合 A 和 B 的所有元素都相同时,称两个集合相等,记作 $A=B$ - $A=B\Leftrightarrow A\subseteq B \land B\subseteq A$
定义(真子集)：如果 A 是 B 的子集，但 A 和 B 不相等，也就是说 B 中总有一些元素不属于 A，则称A 是 B 的真子集。记作$A\subset B$ - $A\subset B \Leftrightarrow A\subseteq B\land A\neq B$
定义(不属于): 如果 A 不是 B 的子集，即在 A 中至少有一个元素不属于 B 时，称B 不包含 A，记作 A⊈B。
- $A\not\subset B \Leftrightarrow \exist x(x\in A \lor x\notin B)$

- 注意: $\in 和 \subset是不同层次的问题$

6.1.4 空集¶

定义(空集)：不含任何元素的集合称为空集，记作Ø 或{ }。
$定理: 空集是任何集合的子集 \quad \Rightarrow \quad 推论: 空集是唯一的$

6.1.5 全集¶

引例：要研究北京市的大学生的学习情况时，研究对象可以是清华的学生，也可以是北京师范大学的大学生，但研究的对象总是限制在北京市大学生这个范围内的。在当前情况下，称“北京市大学生的全体”组成的集合为全集。

定义(全集)：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集。
全集的概念具有==相对性== 。
在给定问题中，全集包含任何集合，如果将全集记为E，则$\forall A(A\subseteq E)$。

6.1.6 幂集¶

定义(幂集)：A 是有限集合，由 A 的所有子集作为元素而构成的集合称为 A 的幂集，记作P(A)。
- $P(A) = \{x| x\subseteq A\}$
- $P(\empty) = \{\empty\}$
例: A={a, b, c} 则 A 的$幂集P(A) = {\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}}$

P(A)中元素的个数为 8, 即|P(A)|=8=2³
当 A 是有限集, 若|A|=n, 则|P(A)|=2ⁿ

6.2 集合的运算¶

6.2.1 集合的基本运算¶

定义(并)：由所有属于 A 或者 B 的元素合并在一起而构成的新集合。记作 $A⋃B$ \cup
- $A\cup B = \{x|x\in A\lor x\in B\}$
定义(交)：由属于 A、B 两个集合的所有共同元素构成的新集合。记作$A⋂B$ \cap
- $A\cap B = \{x|x\in A\land x\in B\}$

交&并的运算规律

并($\cup$)运算的性质	交($\cap$)运算的性质
$A\cup A = A$	$A\cap A = A$
$A \cup \emptyset = A$	$A \cap \empty = \empty$
$A\cup E = E$	$A\cap E = A$
$(A\cup B)\cup C = A\cup(B\cup C)$	$(A\cap B)\cap C = A\cap(B\cap C)$
$A\cup B = B\cup A$	$A\cap B = B\cap A$

分配律
- $A\cup (B \cap C) = (A\cup B)\cap(A\cup C)$
- $A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$

定义(相对补 / 减)：由属于集合 A 但不属于集合 B的那些元素构成的集合称为A 减 B 的差，也称作B 关于 A 的相对补，记作A-B。
- 集合的减运算的性质
  1. $A-A=\empty$
  2. $A-\empty = A$
  3. $A - E = \empty$
  4. $A-B = A - (A\cap B) = A\cap \sim B$ 减只能减去交集
- 定义(绝对补集\sim): $\sim A = E - A = \{x|x\in E \land x \not\in A\}$
- 例: 设 A = {a, b}, 求 P(A), P(A) - A, P(A) - {A}, P(A) - Ø, P(A) - Ø
  - P(A) = {Ø, {a}, {b}, {a,b}}
  - $P(A) - A = P(A) - (A\cap P(A))= P(A) - \textcolor{#ee0000}{\empty} = \{Ø, \{a\}, \{b\}, \{a,b\}\}$
  - $P(A) - A =P(A) - \{a, b\}= \{Ø, \{a\}, \{b\}\}$
  - $P(A) - \empty = \{Ø, \{a\}, \{b\}, \{a,b\}\}$
  - $P(A) - \{\empty\} = \{\{a\}, \{b\}, \{a,b\}\}$
- 减是集合之间的相减, 不能错把元素拿去相减
定义(对称差)：任给集合 A 和 B，A 和 B 的对称差记为$A\oplus B$ (异或)
- $A\oplus B = (A-B)\cup(B-A) = (A\cup B)-(A\cap B)$
- 与逻辑中的"异或 "相似
- 对称差的性质
  1. 交换律: $A\oplus B = B\oplus A$
  2. 结合律: $A\oplus (B \oplus C) = (A\oplus B) \oplus C$
  3. $A\oplus \empty = A$ $A\oplus E = A$
  4. $A\oplus A = \empty$

6.2.1 广义并和广义交¶

定义(广义并)：设 A 为集合，A 的元素的元素构成的集合称为 A 的广义并，记作:$\bigcup A$
- 例: A = {{a, b, c}, {a, c, d}}
定义(广义交)：设 A 为非空集合，A 的所有元素的公共元素构成的集合称为 A 的广义交，记作:$\bigcap A$

6.2.3 集合运算的优先级¶

将广义并、广义交、幂集、绝对补称作一类运算；并、交、相对补、对称差称作二类运算
- 一类运算的优先级高于二类运算；
- 一类运算之间由右向左进行；
- 二类运算之间由括号决定先后顺序。
例:

6.2.4 包含排斥原理¶

- |A|: A 的基, 值为集合 A 包含的元素个数
定理: 设 A₁, A₂, ..., A_n 为有限集合, 则有

$|A_1\cup A_2\cup...\cup A_n| = \\\sum_{i=1}^n|A_i| \textcolor{#ee0000}{-} \sum_{i\leq i<j \leq n}|A_i\cap A_j| \textcolor{#ee0000}{+} \sum_{i\leq i<j<k \leq n}|A_i\cap A_j\cap A_k|+... +\textcolor{#ee0000}{(-1)^n}|A_1\cap A_2\cap ...\cap A_n|$
例: 某班有学生 60 人，其中有 38 人学习 PASCAL，有 16 人学习 C，有 21 人学习 JAVA；有 3 人这三种语言都学习，有 2 人这三种语言都不学习，问仅学两门语言的学生数是多少？
- 解: 设 A 为学习 PASCAL 的学生集合；B 为学习 C 的集合；C 为学习 JAVA 的学生集合。
- 由题意得： $|A|=38;\ |B|=16;\ |C|=21;\ |A∩B∩C|=3;\ 60-|A∪B∪C|=2$
- $|A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|- |B∩C|+|A∩B∩C|$
- 所以：$|A∩B|+|A∩C|+|B∩C|=20$
- 仅学习 PASCAL 和 C 的学生数应是：$|A∩B|-|A∩B∩C|=|A∩B|-3$
- 仅学习两门语言的人数是：$|A∩B|+|A∩C|+|B∩C|-3|A∩B∩C|=11$

6.3 集合恒等式 –¶

6.3.1 集合运算的算律¶

	$\cup$	$\cap$	$\oplus$
交换	$A\cup B = B\cup A$	$A\cap B = B\cap A$	$A\oplus B = B\oplus A$
结合	$(A\cup B)\cup C = A\cup(B\cup C)$	$(A\cap B)\cap C = A\cap(B\cap C)$	$A\oplus (B \oplus C) = (A\oplus B) \oplus C$
幂等律	$A\cup A = A$	$A\cap A = A$	$A\oplus A = \empty$

运算律
分配	$A\cup (B \cap C) = (A\cup B)\cap(A\cup C)$ $A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$
吸收	$A\cup(A\cap B)= A\qquad A\cap(A\cup B)=A$
双重否定	$\sim\sim A = A$

符号	-	$\sim$
D.M 律	$A-(B\cup C) = (A-B)\cap(A-C)$ $A-(B\cap C) = (A-B)\cup(A-C)$	$\sim(B\cup C) = \sim B\ \cap\sim C$ $\sim(B\cap B)=\sim B\ \cup\sim C$

运算律符号	$\empty$	E
补元律	$A\cap\sim A = \empty$ (矛盾律)	$A\cup\sim A = E$(排中律)
零律	$A\cap \empty = \empty$	$A\cup E=E$
同一律	$A\cup \empty = A$	$A\cap E=A$
否定	$\sim\empty = E$	$\sim E = \empty$

6.3.2 集合包含的证明$(X\subseteq Y)$¶

命题推理法
- $欲证明 A\subseteq B:\qquad 任取 x, x\in A \Rightarrow ... \Rightarrow x\in B$
- 例: 证明$A\subseteq B \Leftrightarrow P(A)\subseteq P(B)$
  - 分析: 该证明需要分为两步(左和右)
  - 证明: (1) $A\subseteq B \Rightarrow P(A)\subseteq P(B)$
    
    (2) $A\subseteq B \Leftarrow P(A)\subseteq P(B)$
  - (1) $A\subseteq B \Rightarrow P(A)\subseteq P(B)$
    
    任取 x, $x\in P(A) \Rightarrow x\subseteq A\Rightarrow x\subseteq B\Rightarrow x\in P(B)$
  - (2) $A\subseteq B \Leftarrow P(A)\subseteq P(B)$
    
    任取 x, $x\in A \Rightarrow \{x\}\subseteq A\Rightarrow \{x\}\in P(A) \Rightarrow \{x\}\in P(B)\Rightarrow \{x\}\subseteq B \Rightarrow x\in B$
  - 由(1), (2)证明得 ,$A\subseteq B \Leftrightarrow P(A)\subseteq P(B)$
包含传递法
1. $欲证明A\subseteq B:\qquad 找到集合T，使其满足 A\subseteq T 且 T\subseteq B，从而有A\subseteq B。$
2. 例: 证明$A-B \subseteq A\cup B$
  
  - 证明 : $A-B \subseteq A, 且 A\subseteq A\cup B$
```
所以 $A-B\subseteq A\cup B$
```
利用包含的等价条件进行证明
1. $A\subseteq B \Leftrightarrow A\cup B = B \Leftrightarrow A\cap B = A \Leftrightarrow A-B = \empty$
2. 例: 证明$A\subseteq C\land B\subseteq C \Rightarrow A\cup B\subseteq C$
  
  - 证明: $A\subseteq C \Rightarrow A\cup C=C$
```
 $B\subseteq C \Rightarrow B\cup C = C$

 $(A\cup B)\cup C = A\cup(B\cup C) = A\cup C = C$

 $(A\cup B)\cup C = C \Leftrightarrow A\cup B\subseteq C$ 得证
```
反证法
- $欲证明A\subseteq B, 假设命题不成立, 不存在x是的x\in A 且 x\not\in B, 然后退出矛盾$
- 例: 证明 $A\subseteq C\land B\subseteq C \Rightarrow A\cup B\subseteq C$
- 例: 证明 $A\cap B \subseteq B\cap C \land A-C\subseteq B-C \Rightarrow A\subseteq B$

6.3.3 集合相等的证明¶

命题演算法 (常用)
- 证明思路: 对于任意的 x, 有$x\in Y\Rightarrow ... \Rightarrow x\in X$ 且 $x\in Y\Rightarrow ... \Rightarrow x\in X$
  
  或者, 对于任意的 x, $x\in X\Leftrightarrow...\Leftrightarrow x\in Y$
  
  即: $X\subseteq Y$且$Y\subseteq X$, 所以 X=Y
- 证明: $A\cup (A\cap B) = A$
  - 证: 对于任意的 x
  - $x\in A\cup(A\cap B) \Rightarrow x\in A \lor x\in A\cap B$
- 经常使用定义去证明
等式替换
- 设 A、B 是全集 E 的任意两个子集，当且仅当$A\cup B=E且A\cap B= \empty$时，才有 B=~A。

第七章二元关系¶

7.1 笛卡尔积和二元关系¶

7.1.1 有序对¶

定义(有序对) : 由两个客体 x 和 y，按照一定的顺序组成的二元组称为有序对，记作
有序性 : 一般情况下 ≠
与相等的充要条件是：$<x,y>=<u,v> \Leftrightarrow x=u \land y=v$

7.1.2 笛卡尔积¶

定义(笛卡尔积) : 设 A 和 B 是两个集合, A 到 B 的笛卡尔乘积用A×B表示，它是所有形如的==有序对作为元素== 的集合，其中$a\in A, b\in B$
- A 到 B 的笛卡尔乘积: $A\times B = \{<x, y>|x\in A\land x\in B\}$ B 到 A 的笛卡尔乘积: $B\times A = \{<x, y>|x\in B \land y\in A\}$
例 : A={1,2,3}, B={a,b,c}

$A\times B=\{<1,a>,<1,b>,<1,c>\ ,<2,a>,<2,b>,<2,c>\ ,<3,a>,<3,b>,<3,c>\}$
$B\times A=\{<a,1>,<b,1>,<c,1>\ ,<a,2>,<b,2>,<c,2>\ ,<a,3>, <b,3>,<c,3>\}$

当|A| = m, |B| = n 时, |A×B| = m×n
- 特别的, 当 A=B 时, A×A 称为==集合 A 上的笛卡尔乘积== , 也可以简写为A², |A×A| = n²
例 : 设 A={a,b},B={0,1},C={Ø}。试求出 A×A, A×B,B×A, (A×B)×C, A× (B×C)
笛卡尔积的性质
1. $A\times \empty = \empty \times B = \empty$
2. $当A\neq B, A\neq \empty, B\neq \empty时, \textcolor{#ee0000}{A\times B\neq B\times A}$ 笛卡尔积没有交换律
3. $当A\neq \empty, B\neq \empty时, (A\times B)\times C \neq A\times(B\times C)$ 笛卡尔积没有结合律
4. $A\subseteq C\land B\subseteq D \Rightarrow A\times B\subseteq C\times D$
5. 对于交/并有分配律 - $A\times (B\cup C) = (A\times B)\cup(A\cup C)$ - $(B\cup C)\times A = (B\times A)\cup(C\cup A)$ - $A\times (B\cap C) = (A\times B)\cap(A\cap C)$ - $(B\cap C)\times A = (B\times A)\cap(C\cap A)$
- 根据定义证明
例 5：设 A、B 为任意集合，证明：若 A×A=B×B,则 A=B。

7.1.3 二元关系¶

定义(集合之间的二元关系) : A 和 B 是两个集合,R 是笛卡尔乘积 A×B 的子集==$(R\subseteq A×B)$== ，则称 R 为A 到 B 的一个二元关系。
- e.g. A = {a₁,a₂,a₃,a₄,a₅} ,B = {b₁,b₂,b₃}
  
  R = {,,}是 A 到 B 的一个二元关系。
- 可以写作a₁Rb₁, 称 a₁, b₁以 R 相关
- 例: 列出从集合 A={1,2}到 B={1}的所有的二元关系.
  - 解：A×B 的所有子集都是 A 到 B 的二元关系。
    
    R1= Ø, R2={<1,1>}, R3={<2,1>}, R4={<1,1>,<2,1>}
- 二元关系是一个集合, 其元素是有序对
定义(集合上的二元关系): A 是集合,R 是笛卡尔乘积 A×A 的子集==$(R\subseteq A×A)$== ，则称 R 为A 上的二元关系。
- 当|A|=n 时, A 上有$2^{n^2}$个不同的二元关系 (|A×A| = n², A×A 有$2^{n^2}$个子集)
定义(二元关系) : 如果一个集合满足以下条件之一：① 集合非空, 且它的元素都是有序对 ② 集合是空集则称该集合为一个二元关系, 简称为关系，记作R。
特殊的二元关系: 设 A 为任意集合
- Ø 称为 A 上的空关系；
- $E_A=\{<x,y>|x∈A∧y∈A\}=A×A$称为 A 上的全域关系；
- $I_A=\{<x,x>|x∈A\}$称作 A 上的恒等关系。
- $L_A=\{<x,y>| x,y∈A∧x≤y\}$称作 A 上的小于等于关系，其中 $A\subseteq R$，R 为实数集合；
- $D_A=\{<x,y>| x,y∈A∧x整除y\}$, 称作 A 上的整除关系, $A\subseteq Z*$, Z*为非 0 整数集；
- $R_\subseteq=\{<x,y>| x,y∈A∧x\subseteq y\}$称作 A 上的包含关系， A 是集合族。
  - 集合族: 元素是集合的集合
例: 例 7: A={Ø,{1},{2},{1,2}}, 求 A 上的包含关系

7.1.4 关系的表示¶

常用的集合表示法:
- 集合表示法:
- 矩阵表示法
- 关系图表示法
关系矩阵 : 若 A={x₁, x₂, …, x_m}，B={y₁, y₂, …, y_n}，R 是从 A 到 B 的关系，R 的关系矩阵$M_R = [ r_{ij} ]_{m×n}$, 其中$r_{ij} = 1\Leftrightarrow< x_i, y_j> \in R$
例 : A = {1,2,3,4,6} ，R 是 A 上的整除关系，求 R 的矩阵表示。
关系图 : 若 A= {x₁, x₂, …, x_m}，R 是==A 上的关系== ，R 的关系图是 G_R=, 其中 A 为结点集，R 为边集. 如果属于关系 R，在图中就有一条从 x_i 到 x_j 的有向边。
关系矩阵适于表示从 A 到 B 的关系(不是方阵)或者 A 上的关系(方阵)，关系图适合表示 A 上的关系。

7.2 关系的运算¶

7.2.1 关系的定义域, 值域, 域¶

定义(定义域&值域) : 设 R 是二元关系，
- $<x,y> \in R$的所有 x 组成的集合称为 R 的定义域(前域），记作domR；$\textcolor{#66ccff}{domR = \{ x\ |\ \exist y (<x,y>\in R) \}；}$
- $<x,y> \in R$的所有 y 组成的集合称为 R 的值域，记作ranR。 $\textcolor{#66ccff}{ranR = \{ y\ |\ \exist x (<x,y>\in R) \}}$
R 的域 : $\textcolor{#66ccff}{fldR} = domR \cup ranR$

7.2.2 关系的逆运算及其性质¶

定义(逆关系)：二元关系 R 的逆关系记为$R^{-1}$, $R^{-1} = \{<y,x> | <x,y>\in R\}$
逆运算的性质
1. 设 R 是任意的关系, 则 - $(R^{-1})^{-1} = R$ - $dom(R^{-1}) = ranR; ran(R^{-1}) = domR$
2. 关系 R 和 R^-1的关系矩阵互为转置矩阵 ($R:<a_i, b_j>, R^{-1}:<b_j, a_i>;{M_{R}}^T = M_{R^{-1}}$)
3. 设 R, S 为任意的二元关系 (二元关系也是集合) - $(R\cup S)^{-1} = R^{-1}\cup S^{-1}$ - $(R\cap S)^{-1} = R^{-1}\cap S^{-1}$ - $(\sim R)^{-1} = \sim(R^{-1})$ - $(R-S)^{-1} = R^{-1} - S^{-1}$ - $R\subseteq S \Leftrightarrow R^{-1}\subseteq S^{-1}$ - 注意: 逆没有摩根律 -

7.2.3 关系的复合运算及其性质¶

定义(复合运算): 二元关系 R, S 的符合运算记作$R\circ S$
- 定义式 : $\textcolor{#66ccff}{R\circ S} = \{<x, z>|\ \exist y(<x,y>\in R\ \land <y, z>\in S\}$
- 例: R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}
  - R∘S ={<1,3>, <2,2>, <2,3>} S∘R ={<1,2>, <1,4>, <3,2>, <3,3>}
如果将 R∘S 的关系矩阵记为 M_RS，R 的关系矩阵记为 M_R，S 的关系矩阵记为 M_S
- $M_{RS} = M_R\cdot M_S$
定理 2 : 设 F, G, H 是任意的关系, 则
- $(F\circ G)\circ H = F\circ(G\circ H)$ 符合运算具有结合律
- $(F\circ G)^{-1} = G^{-1}\circ F^{-1}$ 顺序需要交换类比转置矩阵$(AB)^T = B^TA^T$
定理 3 : 设$R\subseteq A×A$ (R 是 A 上的关系), 则$R\circ I_A = I_A\circ R = R$ (I_A相当于单位矩阵)
定理 4 : 若 F, G, H 是任意的二元关系, 则
- $F\circ (G\cup H) = F\circ G\cup F\circ H$
- $(G\cup H)\circ F = G\circ F \cup H\circ F$
- $F\circ (G\cap H) \textcolor{#ee0000}{\subseteq} F\circ G \cap F\circ H$
- $(G\cap H)\circ F \textcolor{#ee0000}{\subseteq} F\circ G \cap F\circ H$
- 原因: 存在对析取有分配 ($\exist x(A(x)\lor B(x)) \Leftrightarrow \exist xA(x)\lor \exist xB(x)$) ,
  
  对合取只有在推理的时候有分配 ($\exist x(A(x)\land B(x)) \Rightarrow \exist xA(x)\land \exist xB(x)$)

7.2.4 关系的"限制"运算及其性质¶

定义(限制) : 二元关系 R 在集合 A 上的限制即$\textcolor{#66ccff}{R↾A} = \{<x, y>|<x,y>\in R\land x\in A\}$ (对前键进行限制)
- $R↾A\subseteq R$
定理 5: 设 F 为关系, A, B 为集合, 则:
- $F↾(A\cup B) = F↾A\cup F↾B$
- $F↾(A\cap B) = F↾A\cap F↾B$
- 证明: 同样使用定义
  - $<x,y>\in F↾(A\cup B)\Leftrightarrow <x,y>\in F\land (x\in A\cup B)$ $\Leftrightarrow <x,y>\in F\land(x\in A\lor x\in B)$ $\Leftrightarrow (<x,y>\in F\land x\in A)\lor(<x,y>\in F\land x\in B)$

7.2.5 集合在关系下的"像"及其性质¶

定义(像) : A 在 R 下的像记作$\textcolor{#66ccff}{R[A]}$ , $R[A]=ran(R↾A)$
- $R[A]\subseteq ranR$
例:
定理 6:设 F 为关系, A, B 为集合, 则:
- $F[A\cup B]=F[A]\cup F[B]$
- $F[A\cap B] \subseteq F[A]\cap F[B]$
- 证明: 定义,
- $y\in F[A\cup B] \Leftrightarrow \exist x(<x,y>\in F↾(A\cup B))$
  
  $\Leftrightarrow \exist x((<x, y>\in F↾A)\lor (<x,y>\in F↾ B))$ 小跳几步
  
  $\textcolor{#ee0000}{\Leftrightarrow} \exist x(<x, y>\in F↾A)\lor \exist x(<x,y>\in F↾B)$ 存在的分配
  
  $\Leftrightarrow y\in F[A] \lor y\in F[B]$
  
  $\Leftrightarrow y\in (F[A]\cup F[B])$

7.2.6 关系的幂运算及其性质¶

定义(幂运算)：设 R 为 A 上的关系, n 为自然数, 则 R 的 n 次幂定义为：
- $R^0=\{<x,x> | x∈A \}=\textcolor{#ee0000}{I_A}$
- $R^{n+1} = R^n∘R$
- 对于 A 上的任何关系 R₁和 R₂都有：$R_1^0 = R_2^0 = I_A $
- 对于 A 上的任何关系 R 都有： $R^1 = R $
关系幂运算的求解方法：
- 用集合表示给出 R 时，通过 n-1 次的右复合得到 R_n ；
- 用关系矩阵 M 给出 R 时， Rn 的关系矩阵由 n 个 M 相乘得到；
- 用关系图 G 给出 R 时，具体步骤见例题。
例
定理 6 : 设 R 是 A 上的关系, m, n∈N, 则
- $R^m∘R^n=R^{m+n}$
- $(R^m)n=R^{mn} $
- 类比矩阵乘法
定理 7：设 A 为 n 元集, R 是 A 上的关系, 则==存在== 自然数 s 和 t, 使得 R^s = R^t.
定理 8（周期性）：设 R 为 A 上的关系，若存在自然数 s,t(s<t)使得$R^s=R^t$，则
- 对任意 k∈N, 有$R^{s+k} = R^{t+k}$
- 对任意 k, i∈N, 有$R^{s+kp + i} = R^{s+i}$ , 其中==$p=t-s$==
- 令$S=\{R^0, R^1, ..., R^{t-1}\}$, 则对于任意的 q∈N, 有 R^q∈S

7.3 关系的性质¶

7.3.1 自反性与反自反性¶

- 定义(关系的自反性)：R 是 A 上的二元关系，如果对于 A 中的每一个元素 x，都有$<x,x>\in R$，则称 R 为==自反的二元关系== 。
  - 即:$\forall x(x∈A→<x,x>\in R)$
  - 每个都属于, 不是自反的证明: $\textcolor{#ee0000}{\exist x}(x∈A→<x,x>\not\in R)$
- 定义(关系的反自反性)：R 是 A 上的二元关系，如果对于 A 中的每一个元素 x，都有$<x,x>\not\in R$，则称 R 为==反自反的二元关系== 。
  - 即:$\forall x(x∈A→<x,x>\not\in R)$
  - 每个都不属于, 不是反自反的证明 : $\textcolor{#ee0000}{\exist x}(x∈A→<x,x>\in R)$
  - 自反和反自反是两个极端
证明 R 在 A 上自反/反自反, 证明模式:
- 自反: 反自反:
- 例一 : 例二 :
定理：设 R 为 A 上的关系, 则：
- R 在 A 上==自反== 当且仅当 $I_A\subseteq R$
  - 表达式：$I_A\subseteq R$
  - 关系矩阵：主对角线元素全是 1
  - 关系图：每个顶点都有环
- R 在 A 上==反自反== 当且仅当 $R\cap I_A = \empty$
  - 表达式：$R\cap I_A = \empty$关
  - 关系矩阵：主对角线元素全是 0
  - 关系图：每个顶点都没有环

7.3.2 对称性和反对称性¶

- 定义(关系的对称性):R 是 A 上的二元关系,如果∈R,就一定有∈R,则称 R 为==对称的二元关系== 。
  - 即：$\forall x\forall y(x,y∈A\ ∧<x,y>∈R→<y,x>∈R)$
- 定义(关系的反对称性):R 是 A 上的二元关系,如果∈R,就一定有∈R, 必有==x=y== ,则称 R 为==反对称的二元关系== 。
  - 即：$\forall x\forall y(x,y∈A\ ∧<x,y>∈R\land <y,x>∈R\rightarrow x=y)$ 反对称不是没有对称, 而是对称一定是在主对角线上
  - 原意 :
    
    $\forall x \forall y(x, y\in A \land x\neq y \land <x, y>\in R \rightarrow <y, x>\not\in R)$
    
    $\Leftrightarrow \forall x\forall y(\lnot (x, y\in A \land \lnot(x=y) \land <x,y>\in R)\lor <y,x>\not\in R))$
    
    $\Leftrightarrow \forall x\forall y(\lnot (x, y\in A) \lor (x=y) \lor \lnot(<x,y>\in R)\lor <y,x>\not\in R))$
    
    $\Leftrightarrow \forall x\forall y((\lnot (x, y\in A) \lor \lnot(<x,y>\in R)\lor <y,x>\not\in R))\lor (x=y))$
    
    $\Leftrightarrow \forall x\forall y((x, y\in A) \land (<x,y>\in R)\land <y,x>\in R)\rightarrow (x=y))$
例 3：设 A ＝{1,2,3}, R1, R2, R3 和 R4 都是 A 上的关系, 判断它们的对称性及反对称性。
- R₁＝{<1,1>,<2,2>} ;
  - R₁ 对称, 反对称
  - “对称的”和“反对称的”这两个概念并非相互对立，相互排斥的。存在着既不是对称又不是反对称的二元关系，也存在着既是对称又是反对称的二元关系(元素都在主对角线上)。
- R2 ＝{<1,1>,<1,2>,<2,1>}
  - R₂ 对称. 不是反对称
- R₃＝{<1,2>,<1,3>}
  - R₃ 反对称, 不对称
- R₄＝{<1,2>,<2,1>,<1,3>}
  - R₄ 既不对称, 也不反对称
R 在 A 上对称 / 反对称, 证明模式:
定理 :
- R 在 A 上==对称== 当且仅当 $R=R^{-1}$
  - 表达式：$R=R^{-1}$
  - 关系矩阵：矩阵是对称矩阵
  - 关系图：若两个顶点之间有边, 那么一定是一对方向相反的边(无单边)
- R 在 A 上==反对称== 当且仅当 $R∩R^{-1}\subseteq I_A$
  - 表达式：$R∩R^{-1}\subseteq I_A$
  - 关系矩阵：若 r_ij＝ 1, 且 i≠j(不在主对角线), 则 r_ji＝ 0 (没有对称的点)
  - 关系图：两点之间的边一定是一条单向有向边(无双向边)

7.3.3 传递性¶

定义(关系的传递性)： R 是 A 上的二元关系,每当有∈R 和∈R 时,必有∈R，则称 R 为可传递的二元关系。
- $\forall x\forall y\forall z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)$
例 6：设 A ＝{1,2,3}, R1, R2, R3 是 A 上的关系
- R1 ＝{<1,1>,<2,2>} R₁是 A 上的传递关系
- R2 ＝{<1,2>,<2,3>} R₂不是 A 上的传递关系(缺了<1,3>)
- R3 ＝{<1,3>} R₃ 是 A 上的传递关系(根本没有 z, 前键为假)
R 在 A 上传递, 证明模式:
定理:
- 设 R 为 A 上的关系, 则：R 在 A 上传递当且仅当$\textcolor{#66ccff}{R\circ R\subseteq R}$
  - 表达式: $R\circ R\subseteq R$
  - 关系矩阵：M²中 1 所在位置，M 中也是 1。($R^2\subseteq R$)
  - 关系图：如果顶点 x_i 连通到 x_k , 则从 x_i到 x_k 有直接的边

例 8：给定 A={1,2,3,4},A 上的关系 R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 用 R 的关系矩阵说明其具有哪些性质。

主对角线全是 1/0? ①R 具有反自反性
矩阵是对称矩阵? R 不具有对称性
若 r_ij＝ 1, 且 i≠j, 则 r_ji＝ 0 ②R 具有反对称性
对 M2 中 1 所在位置，M 中相应位置都是 1？③R 具有传递性

例 9：判断下图中关系的性质, 并说明理由

对称性
反自反性, 反对称性, 传递性
自反性, 反对称性
- 没有传递缺 2->3(图上的是 3->2)

7.4 关系的闭包¶

7.4.1 闭包的概念¶

定义(闭包)：设 R 是 A 上的二元关系，R 的自反（对称、传递）闭包是关系 R₁，则 ① R₁是自反的（对称的、传递的） ② $ R\subseteq R_1$ ③ 对A上的任何自反的（对称的、传递的）关系R₂，若$R\subseteq R_2$，则。$R_1\subseteq R_2$
- R 的自反、对称和传递闭包分别记为r(R)、s(R)和t(R)。
例:
- 闭包运算即：添加最少的有序对，使得原关系具有某种性质的运算。

7.4.2 闭包的构造方法¶

例 1：A = {a,b,c,d,e}，R = {,,,,},求 r(R) 和 s(R)。
- r(R) = {,,,,< d,e >,, , ,} s(R ) = {,,,,,,}
定理 : 设 R 为 A 上的关系, 则有
- 自反(reflexive)闭包: $\textcolor{#66ccff}{r(R) = R∪R^0 = R∪I_A}\quad (\Rightarrow 矩阵:M_r = M + E)$
- 对称(symmetry)闭包: $\textcolor{#66ccff}{s(R) = R \cup R^{-1}}\quad (\Rightarrow M_s = M + M^T)$
例 2：设 A={a,b,c,d}, R={,,,,}, 通过 R 的关系图构造 r(R), s(R), t(R)的关系图
例 3: A = {a,b,c},R = {,,} 。求 R 的传递闭包。
- ∈R, ∈R，而 ∉R; ∈R, ∈R，而 ∉R; ∈R, ∈R，而 ∉R。
  
  所以 R₁ ={,,,,,}
  
  ($R\circ R=R_2= \{<a,c>,<b,a>,<c,b>\}$)
  
  $R_1 = \textcolor{#ee0000}{R∪R\circ R = R∪R^2}=\{<a,b>,<b,c>,<c,a>,\textcolor{#ee0000}{<a,c>,<b,a>,<c,b>}\}$ 还不具有传递性
- R₂已经是全域了, 一定具有传递性
定理(传递(transfer)闭包的计算) : 设 R 为 A 上的关系, 则有$\textcolor{#66ccff}{t(R) = R∪R^2∪R^3∪…} (\Rightarrow 矩阵: M_t=M+M^2+M^3+...)$
- 推论 : 若 A 为有限集合，R 为 A 上的关系, 那么存在正整数 t 使得 $\textcolor{#66ccff}{t(R) = R\cup R^2 \cup ... \cup R^t}$
例 4：设 A={1,2,3},R 为 A 上的二元关系 R={<1,2>,<2,3>,<3,1>}，求 t(R)

7.4.3 Warshall 算法¶

求传递闭包的算法

例 5：A = {a1,a2,a3,a4,a5}, R = {,,,,,}，求 R 的传递闭包。
1. 先写出 R 的关系矩阵
2. 考察第 1 列，m₅₁=1，于是应将第 1 行元素==加到== 第 5 行上去。
3. 考察第 2 列元素，现有 m₁₂=1 和 m₅₂=1，于是应将第 2 行元素分别==加到== 第 1 行和第 5 行上去。
4. 考察第 3 列元素，现有 m₁₃=1,m₂₃=1,m₃₃=1,m₅₃=1。于是应将第 3 行元素分别加到第 1,2,3,5 行上去。
5. 考察第 4 列元素，现有 m₁₄ = 1,m₂₄ = 1,m₃₄ = 1,m₅₄ = 1,于是应将第 4 行元素加到 1、2、3、5 行上去

7.5 等价关系¶

7.5.1 等价关系的定义¶

定义(等价关系): 设 R 为非空集合上的关系。如果 R 是自反的、对称的和传递的,则称 R 为 A 上的等价关系。
- e.g. I_A和 E_A都是等价关系。
定义(元素的等价): 设 R 是一个等价关系, 若∈R, 称 x 等价于 y, 记作x~y
- 例 1:设 A={1,2,3,4,5}，R 是 A 上的二元关系，R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>}
  - 1 和 1 等价， 2 和 2 等价， 1 和 2 等价； 3 和 3 等价， 4 和 4 等价， 3 和 4 等价； 5 和 5 等价；
例 2：设 R 是正整数集合 Z⁺上的关系：$R = \{ <x,y> | x,y∈ Z^+ ∧ x≡y\ mod\ k \}$, 验证关系 R 的等价性 (证明等价)
- $x≡y mod k $: 表示 x,y 除以 k 的余数相等, 称为x 和 y 模 k 同余
- $x≡y\ mod\ k\quad\Leftrightarrow\quad (x-y)\%k=0\ ((x-y) = nk)$
1. 证明自反性()
  
  - $\forall x\in Z^+ \because x-x=0\times k\therefore x\equiv x\ mod\ k$ - R 具有自反性
2. 证明对称性(和)
  
  - $设<x,y>\in R, x\equiv y\ mod\ k$ $\Rightarrow\exist t( x-y = k\cdot t\land t\in Z)$ $\Rightarrow \exist t(y-x = k\cdot(-t)\land -t\in Z)$ $\Rightarrow y\equiv x\ mod\ k, <y, x>\in R$ - R 具有对称性
3. 证明传递性(,和)
  
  - $设<x,y>\in R, <y, z>\in R, x\equiv y\ mod\ k, y\equiv z\ mod\ k$
```
$\Rightarrow\exist t_1( x-y = k\cdot t_1\land t_1\in Z),\ \exist t_2( x-y = k\cdot t_2\land t_2\in Z)$
$\Rightarrow x-z=(x-y)+(y-z) = k\cdot(t_1+t_2),\ t_1+t_2\in Z$
$\Rightarrow x\equiv z\ mod\ k, <x,z>\in R$
```
  - R 具有传递性
4. 综上所述, R 具有自反性, 对称性, 传递性, 所以 R 是 Z⁺上的等价关系

7.5.2 等价类¶

定义(等价类) : 设 R 为非空集合 A 上的等价关系, $\forall x∈A，令[x]_R = { y | y∈A∧xRy } $称 [x]_R 为x 关于 R 的等价类, 简称为 x 的等价类, 简记为[x]
- e.g. A={ 1, 2, … , 8 }上模 3 等价关系的等价类
  - $[1]_R = \{1, 4, 7\}; [4]_R = \{1, 4, 7\}; [7]_R = \{1, 4, 7\}$
  - $[2]_R = \{2, 5, 8\}; [5]_R = \{2, 5, 8\}; [8]_R = \{2, 5, 8\}$
  - $[3]_R = \{3, 6\}; [6]_R = \{3, 6\}$
等价的元素, 其等价类是相同的, 所以不同的等价类仅有 3 个( {1,4,7}、 {2,5,8}、 {3,6} )

7.5.3 商集¶

定义(商集) : 设 R 为非空集合 A 上的等价关系, 以 R 的所有==等价类作为元素== 的集合称为 A 关于 R 的商集, 记做A/R, $\textcolor{#66ccff}{A/R}=\{[x]_R\ |\ x∈A\}$。
- A={ 1, 2, … , 8 }上模3等价关系的商集：A/R={{1,4,7},{2,5,8},{3,6}}
例 3：A={0,1,2,3,4,5,6,7,8,9} 求 A 关于恒等关系和全域关系的商集。
- 解：A 关于恒等关系和全域关系的商集为：
  - $A/I_A = \{\{0\},\{1\},\{2\}, … ,\{9\}\}$
  - $A/E_A = \{ \{0,1, 2, … ,8,9\} \}$

7.5.4 等价类及商集的性质¶

定理: 设 R 是非空集合 A 上的等价关系, 则
- $\forall x\in A, [x]是A的非空子集([x]\in A\land [x]\neq \empty)$
- $\forall x,y\in A, 如果x R y(<x,y>\in R), 则[x] = [y]$
- $\forall x,y\in A, 如果x\not R y(<x,y>\not\in R), 则[x][y]不相交, [x]\cap [y]=\empty$
- $\bigcup (A/R)=A(广义并), 即所有等价类的并集就是A$

7.5.5 集合的划分¶

定义 1(划分&块)：设 A₁,A₂, ···,A_n是集合 A 的非空子集,如果$A_1∪ A_2∪···∪A_n = A，且A_i∩A_j=\empty\ (i≠j)$，以 A₁,A₂, ···,A_n作为元素构成的集合 S = {A₁,A₂, ···,A_n}称为 A 的一个划分，每一个子集 A_i称为块
定义 2(划分&块) : 设 A 为非空集合, 若 A 的子集族$π(π\subseteq P(A))$ 满足下面条件

$①\ \forall x\forall y (x,y∈π\ ∧\ x≠y→x∩y=\empty)\\②\ \empty \not\in π \\③\ \bigcupπ=A$

称 π 是 A 的一个划分, 称 π 中的元素为 A 的划分块.
定理：集合 A 的一个划分能确定一个 A 上的等价关系；反之，A 上的一个等价关系确定了 A 上的一个划分。$(\textcolor{orange}{一个等价关系\Leftrightarrow 一个划分})$
例 5:A = {a,b,c,d,e},A 的划分 S = {{a},{b,c,d,e}}，那么它所确定的等价关系 R 是什么？
例 6： A = {a,b,c,d,e}，R 为 A 上的等价关系,其矩阵表示如下,由 R 确定了怎样的划分？
例 7：给出 A ＝{1,2,3}上所有的等价关系
- 先做出 A 的所有划分, 然后根据划分写出对应的等价关系
- π₁,π₂和 π₃分别对应等价关系 R₁, R₂ 和 R₃ $R_1=\{1\}×\{1\}∪\{2,3\}×\{2,3\} =\{<2,3>,<3,2>\}∪I_A=\{<1,1>,<2,2>,<3,3><2,3>,<3,2>\}$ $R_2 =\{2\}×\{2\}∪\{1,3\}×\{1,3\} =\{<1,3>,<3,1>\}∪I_A =\{<1,1>,<2,2>,<3,3><1,3>,<3,1>\}$ $R_3 =\{3\}×\{3\}∪\{1,2\}×\{1,2\} =\{<1,2>,<2,1>\}∪I_A=\{<1,1>,<2,2>,<3,3><1,2>,<2,1>\}$
例 8：设 A={1, 2, 3, 4}，在 A×A(关系)上定义二元关系 R：$<<x,y>,<u,v>>\in R\Leftrightarrow x+y = u+v$，求 R 导出的划分

A×A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>,<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>, <4,4>}

根据 x + y = 2,3,4,5,6,7,8 将 A×A 划分成 7 个等价类：

7.6 偏序关系 ≼¶

7.6.1 偏序关系的定义¶

定义(偏序关系 ) : 非空集合 A 上的自反、反对称且传递的关系，称为 A 上的偏序关系，记作≼。
- 如果∈≼, 则记作 x≼y, 读作 x“小于或等于”y。(x 在偏序关系定义出的比较上小于 y)
例 1: A={1,2,4},R={<1,1>,<1,2>,<1,4>,<2,2>,<2,4>,<4,4>}

从 R 的关系矩阵可以得出 R 具有 ① 自反性,② 反对称性和 ③ 传递性。所以 R 是 A 上的偏序关系.
偏序集：

注意点
- 集合 A 上的整除关系、恒等关系、小于等于关系都是偏序关系;
- 集合 A 上的全域关系不是偏序关系;
  - 注: 特殊的二元关系
- 例 2：设 P(A)是集合 A 上的幂集合。证明：P(A)上的包含关系是 P(A)上偏序关系
  - $R_\subseteq=\{<x,y>| x,y∈A∧x\subseteq y\}$
  - $\forall x\in P(A), x\subseteq x, <x,x> \in R_\subseteq \quad R_\subseteq 具有自反性$
  - $若<x,y>\in R_\subseteq \land <y, x>\in R_\subseteq\quad 则x\subseteq y\land y\subseteq x \Rightarrow x=y\quad R_\subseteq 具有反对称性$
  - $若<x,y>\in R_\subseteq \land<y,z>\in R_\subseteq\quad 则x\subseteq y\land y\subseteq z\Rightarrow x\subseteq z\Rightarrow <x, z> \in R_\subseteq\quad R_\subseteq具有传递性$
  - 所以 P(A)上的包含关系是偏序关系

7.6.2 偏序关系的哈斯图¶

引入: 偏序关系的哈斯图是指：利用偏序关系的自反性、反对称性和传递性将其对应的关系图进行==简化== 得到的图。
简化方法
1. 由于偏序关系是自反的，关系图中每个结点都有环，为了简化图形，省略这些环；
2. 由传递性知，当∈R 和∈R 时，必有∈R，所以 a 到 c 的有向边可以省略。(只留下相邻节点的边)
3. 如果将图中各结点放在适当位置，使图中各有向边的箭头都是朝上的，那么可以将图中各边的箭头也省略。
例 3：A = {2,3,4,6,8,12,24},R 是 A 上的整除关系，画出 R 的哈斯图。
- $\Rightarrow \begin{cases}4盖住2, 6盖住2\\6盖住3, 8盖住4\\12盖住4, 12盖住6\\24盖住8,24盖住12\end{cases}$
定义(元素的盖住)：R 是 A 上的偏序关系,∈R,a≠b；且在 A 中没有其他元素 c，使得∈R,∈R,则称元素 b 盖住元素 a(元素 b 在元素 a 的上一层)
- 当∈R 时，代表 b 的结点应画在代表 a 的结点之上；当 b 盖住 a 时，a 点与 b 点之间用直线连接。
例 4: $<\{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}, R_{整除}> <P(\{a, b, c\}), R_\subseteq>$画出上述两个偏序集对应的哈斯图。
例 5：已知偏序集的哈斯图如右图所示, 请求出集合 A 和关系 R 的表达式。
- A={a, b, c, d, e, f, g, h}
- R={,, ,,, ,,,}∪I_A

7.6.3 偏序的相关概念¶

定义(可比)：设 R 为非空集合 A 上的偏序关系, $\forall x,y\in A, x与y\textcolor{#66ccff}{可比} \Leftrightarrow x≼y 或 y≼x；\\\forall x,y\in A, \textcolor{#66ccff}{x≺y} \Leftrightarrow x≼y 且x≠y$
例 6：设集合为 A={3,9,27,54}，T 是集合 A 上的整除关系，画出 T 的哈斯图，并总结该偏序关系及其哈斯图的特点。
- $\begin{cases}集合A中的任意两个元素均可比。\\整除关系T的哈斯图是一条直线。\end{cases}$
定义(全序关系)：R 为非空集合 A 上的偏序关系, $\forall x,y\in A$, x 与 y 都是可比的，则称 R 为全序关系（或线序关系）
- 全序关系的哈斯图是一条直线。
- 例 7：找出在集合{0,1,2,3}上包含序偶<0,3>和<2,1>的全序关系。
  - (总共$A_4^4$=24 种)

7.6.4 偏序集的特定元素¶

元¶

定义(xx 元)：$设<A,≼>为偏序集, B\subseteq A, y∈B.$
- $若\forall x(x∈B→y≼x) 成立, 则称y为B的\textcolor{#66ccff}{最小元}$
- $若\forall x(x∈B→x≼y) 成立, 则称y为B的\textcolor{#66ccff}{最大元}$
  - 最小元和最大元 : 与任何一个元素都可比
- $若\forall x (x∈B∧x≼y→x=y) 成立, 则称y为B的\textcolor{#66ccff}{极小元}$
- $若\forall x (x∈B∧y≼x→x=y) 成立, 则称 y 为B的\textcolor{#66ccff}{极大元}$
  - 极小元和极大元 : 如果有比它小/大, 一定是它本身(环)
例 8：设偏序集如下图所示，求 A 的极小元、最小元、极大元、最大元。
- 集合 A 的极小元是：a,b,c,g;
- 集合 A 没有最小元；
- 集合 A 的极大元是：a,f,h
- 集合 A 没有最大元。
例 9：集合 A={Ø,{a},{b},{a,b}}, 关系 R 是 A 上的包含关系，求 A 的极小元、最小元、极大元、最大元
- $\begin{cases}集合A的极小元、最小元都是:\empty\\集合A的极大元、最大元都是：\{a,b\}\end{cases}$
- 对于有穷集，极小元和极大元必存在，可能存在多个；最小元和最大元不一定存在,如果存在一定惟一。
- 最小元一定是极小元;最大元一定是极大元.
- 孤立结点既是极小元，也是极大元.
- 在哈斯图中，如果集合 A 的某个元素不存在A 的其他元素从它上（下）方与其相通，则该元素就是 A 的极大元（极小元）；
- 在哈斯图中，如果集合 A 的某个元素向下（上）通向 A 的所有元素，则该元素就是 A 的最大元（最小元）

界¶

定义(xx 界)：$设<A, ≼>为偏序集, B\subseteq A, y\in A$
- $若\forall x(x∈B→x≼y) 成立, 则称 y 为B的\textcolor{#66ccff}{上界}$
- $若\forall x(x∈B→y≼x) 成立, 则称 y 为B的\textcolor{#66ccff}{下界}$
- $令C＝\{y | y为B的上界\}, 则称C的最小元为B的\textcolor{#66ccff}{最小上界或上确界}$
- $令D＝\{y | y为B的下界\}, 则称D的最大元为B的\textcolor{#66ccff}{最大下界或下确界}$
- 和最值不同, 界可能会取到集合 B==之外== 的元素
例 10：设偏序集如右图所示，设 B ＝{b,c,d}, 求 B 的下界、上界、下确界、上确界
- B 的下界和最大下界都不存在；上界有 d 和 f, 最小上界为 d.
例 11：设 A={2,3,6,12,24,36}， R 是 A 上的整除关系，确定下列集合的上界、上确界、下界和下确界。

(1)B₁={2,3,6} (2)B₂={12,24,36}
- $\begin{cases}B_1的上界是6,12,24,36,没有下界；上确界为6；\\B_2的下界是2,3,6,12,没有上界；下确界为12。\end{cases}$
例 12：设集合 P={x₁,x₂,x₃,x₄,x₅}上的偏序关系如图所示，P 的最大元、最小元、极大元、极小元分别是什么？子集{x₂,x₃,x₄}、{x₃,x₄,x₅}、{x₁,x₂,x₃}的上界、下界、上确界、下确界分别是什么？
- $\begin{cases}P的最大元为x_1，无最小元；\\P的极大元为x_1，极小元为x_4,x_5；\end{cases}$
- 上界下界上确界下确界
  
  {x₂,x₃,x₄} x₁ x₄ x₁ x₄
  
  {x₃,x₄,x₅} x₁ ，x₃ 无 x₃ 无
  
  {x₁,x₂,x₃ } x₁ x₄ x₁ x₄
- 下界、上界、下确界、上确界不一定存在
- 下界、上界存在不一定惟一
- 下确界、上确界如果存在，则惟一
- 集合的最小元就是它的下确界，最大元就是它的上确界；反之不对
  - 如{x₂,x₃,x₄} , 有上确界 x₁, 但是集合无最大元
  - 如 {x₁,x₂,x₃ } , 有下确界 x₄, 但是集合无最小元

第八章函数¶

8.1 函数的定义与性质¶

8.1.1 函数的基本概念¶

定义(函数) : 设 F 为二元关系,若$\forall x\in dom F$都存在==唯一== 的$y\in ranF$使$xFy$成立,则称 F 为函数.
- 对于函数 F 如果有$xFy$,则记作y=F(x),并称 $y为在x的值$。
- 复习: 设 R 是二元关系，由$<x,y> \in R$的所有 x 组成的集合称为 R 的定义域(前域），记作domR；使$<x,y> \in R$的所有 y 组成的集合称为 R 的值域，记作ranR。$domR = \{ x\ |\ \exist y (<x,y>\in R) \}；ranR = \{ y\ |\ \exist x (<x,y>\in R) \}$
- 函数的本质就是二元关系
定义(从 A 到 B 的函数) : 设 A, B 为集合, 如果 f 为函数，且 $dom f \textcolor{#66ccff}= A,ran f\textcolor{#66ccff}\subseteq B$, 则称 f 为从 A 到 B 的函数, 记作 $f：A→B$
- 例 2：判别下列二元关系中哪个能构成 A 到 B 的函数
  1. $A=\{1,2,3\},B=\{4,5,6\},当a∊A,b∊B,且a<b时,<a,b>∊f$ - $f不是A到B的函数;$ $如:1∊A,有<1,4>∊f,<1,5>∊f,<1,6>∊f,这表明A中的元素1与B中的3个元素有关系$ - 函数不能一对多
  2. 设 A、B 集合都是自然数集合 N,f 是N 到 N的二元关系,对于 a,b ∊N,当 a+b=10 时, ∊f - $因为a的取值仅有0,1,2…10,所以f不是N到N的函数$ - 集合 A 到 B 的函数定义域等必须于集合 A
  3. A={2,3,5},B={0,1},对于 a∊A,当 a 为素数时∊f - $f是A到B的函数$
- 例 3：设 X = {a,b}, Y = {0, 1,2}, 求$f:X\rightarrow Y$所有可能的函数。
  - $f_0=\{<a,0>,< b,0>\}, f_1 =\{<a,0>,< b,1>\}, f_2 =\{<a,0>,< b,2>\}\\ f_3=\{<a,1>,< b,0>\}, f_4 =\{<a,1>,< b,1>\}, f_5 =\{<a,1>,< b,2>\}\\ f_6=\{<a,2>,< b,0>\}, f_7 =\{<a,2>,< b,1>\}, f_8 =\{<a,2>,< b,2>\}$
定义(B 上 A) : 所有从 A 到 B 的函数的集合记作 $B^A = \{f|f:A\rightarrow B\}$ 读作“B 上 A”
函数-矩阵表示 : 函数是特殊的二元关系，也可以用关系矩阵表示。函数的关系矩阵的每一行上==有且只有== 一个元素是 1。
- 所以可以简化表示为->函数的像
定义(原像 & 像) : $设函数 f：A→B, A_1\subseteq A;\quad$

$ \textcolor{#66ccff}{原像 A_1 在 f 下的像}： \textcolor{#66ccff}{f(A_1)} = { f(x) | x∈A_1 };$

$ 当 A_1=A 时，将\textcolor{#66ccff}{f(A)}称作\textcolor{#66ccff}{函数的像}$
- 注意与函数值相区别, $函数值f(x)\textcolor{#ee0000}{\in} B , A_1在f下的像f(A_1)\textcolor{#ee0000}{\subseteq} B$ 原像是定义域的子集, 像是值域的子集
- - 解： $f(A_1) = f(\{0,1\}) = \{ f(0), f(1) \} = \{0, 2\}$
定义(完全原像) : $设函数f：A→B, B_1\subseteq B,f^{-1}(B_1) = \{ x| x∈A且 f(x) ∈B_1 \} 称f^{-1}(B_1) 为B_1在f下的\textcolor{#66ccff}{完全原像}$。
- 求原像 A₁的像 f(A₁)的逆运算
例 5：已知集合 A={a,b,c},B={0,1}, f 是 A 到 B 的函数，且$f (a)=f (b)=0，f (c)=1，A_1={a}, 求 f(A_1) ， f ^{-1}(f (A_1) ) $
- 解：$f(A_1)= f(\{a\})=\{0\};\qquad f^{-1}(f (A_1) )= f^{-1}(\{0\})=\{a,b\}$
- $f(A_1)\subseteq B;\qquad A_1\subseteq f^{-1}(f(A_1))$ 函数会存在多对一, 求完全原像会得到 A₁之外的元素

8.1.2 函数的性质¶

定义(函数满射) : 设 f：A→B, 若$ranf = B$, 则称 f：A→B 是满射的。
- f 满射意味着：$\forall y\in B, 都存在 x\in A 使得 f(x) = y$. (值域中每一个元素都有与其对应的元素)
定义(函数单射) : 设 f：A→B，若$\forall y∈ranf 都存在唯一的 x∈A使得 f(x)=y$, 则称 f：A→B 是单射的。
- f 单射意味着：$f(x_1) = f(x_2)\Rightarrow x_1= x_2$ (只能一对一, 不能多对一)
定义(双射) : 设 f：A→B,若 f：A→B既是满射又是单射的, 则称 f：A→B 是双射的。
- AB 元素完美一对一
- (6)不满足满射(b₃), 也不满足单射(b₂)

8.1.3 特殊函数¶

定义(常函数) : $设f：A→B, 若存在 c∈B 使得\forall x∈A 都有 f(x)=c, 则称 f：A→B是\textcolor{#66ccff}{常函数}$。
定义(恒等函数) : $称A上的\textcolor{#66ccff}{恒等关系}I_A为 A上的\textcolor{#66ccff}{恒等函数}, 对所有的 x∈A 都有I_A(x)=x$。
定义(单调递增) : 设, 为偏序集， f：A→B
- 如果对任意的 x₁, x₂∈A，x₁≺x₂, 则 f(x₁)≼f(x₂), 称 f 为单调递增；
- 如果对任意的 x₁, x₂∈A, x₁≺x₂, 就有 f(x₁) ≺ f(x₂), 则称 f 为严格单调递增。
定义(特征函数) : 设 A 为集合 ,$\forall A'\subseteq A, A'的\textcolor{#66ccff}{特征函数}\chi_{A'}\rightarrow \{0,1\} 定义为\chi_{A'}(a) = \begin{cases}1,& a\in A'\\0, & a\in A - A'\end{cases}$
- 针对于 A 的子集的特殊函数
- 例 9：集合：X ={ A, B, C, D, E, F, G, H }, 子集：T = { A, C, F, G, H } , 求$\chi_T$
  - $\chi_T ={,,,,,,,} $
- A 的每一个子集 A’都对应于一个特征函数, 不同的子集对应于不同的特征函数。
定义(自然映射) : $设R是A上的等价关系, 令 g：A→A/R, g(a) = [a], \forall a∈A, 称g是从A到商集A/R的\textcolor{#66ccff}{自然映射}$.
- 注 : [A/R] : A 集合根据等价关系 R 划分的商集 ; [a] : a 的等价类
- 给定集合 A， A 上不同的等价关系确定不同的自然映射。
- 恒等关系确定的自然映射是双射
- 其他的自然映射通常是满射不是单射

8.2 函数的复合函数与反函数¶

8.2.1 复合函数¶

函数的复合也就是关系的复合

设 F,G 是函数，则 F。G 也是函数，且满足$①dom(F\circ G)={x| x∈dom F ∧ F(x) ∈dom G}\quad\②\forall x∈dom(F\circ G) 有 F\textcolor{#ee0000}{\circ} G (x)=G( F(x)) $
例 1：$设 f ,g\in R^R,且 f (x)= x+3, g(x) = 2x+1。求 f\circ g , g\circ f $
- $f\circ g=g( f(x) )=2*(x+3)+1= 2x+7$
- $g\circ f =f ( g(x) )=(2x+1)+3= 2x+4$
例 2：$设 f ,g\in R^R,且f (x)= x+3, g(x) = 2x+1，h(x)=x/2; 求f\circ g \circ h , f \circ (g \circ h)$
- $f \circ g=g( \textcolor{#ee0000}{f(x)} )=2*(x+3)+1= 2x+7$
  
  $ f \circ g \circ h =h( 2x+7 )=x+7/2$
- $ g \circ h =h( \textcolor{#ee0000}{g(x)} )=(2x+1)/2=x+1/2$
  
  $ f \circ (g \circ h) =f (\textcolor{#ee0000}{x+1/2} )= x+7/2$
结论 : $设F,G,H为函数，则(F \circ G) \circ H和F \circ (G \circ H)都是函数，且 \textcolor{#66ccff}{(F \circ G) \circ H=F \circ (G \circ H)}$
例：设 A={0,1,2}, B={a,b,c}, f={<0,a>,<1,b>,<2,b>}

显然，关系 f 是 A 到 B 的函数

但 f^-1={,,}, 关系 f 的逆 f^-1不是函数
- 只有 f 既是单射又是满射时，f ^-1才是 B 到 A 的函数。

8.2.2 反函数¶

定理：$设 f :A→B是双射的,则f^{-1} :B→A也是双射的。$
例: $设 f: R→R, g: R→R; g(x) = x+2; f(x) = \begin{cases}x^2,& x\geq3\\-2,&x<3\end{cases}$

求$f\circ g, g \circ f$ , 如果 f 和 g 存在反函数, 求出它们的反函数
- f : R→R 不是双射, 不存在其反函数. g : R→R 是双射, 其反函数 : g ^-1: R→R, g ^-1(x) = x-2

Part3 代数结构¶

第九章代数系统¶

9.1 二元运算及其性质¶

9.1.1 二元运算的定义及其性质¶

定义(二元运算)：设 S 为集合,函数 f：S×S→S 称为S 上的二元运算, 简称为二元运算。也称 S 对 f 封闭

定义(一元运算)：设 S 为集合，函数 f：S→S 称为S 上的一元运算
- 例：
  - Z, Q 和 R 上的一元运算: 求相反数
  - 非零有理数集 Q，非零实数集 R 上的一元运算: 求倒数
  - 幂集 P(S) 上, 全集为 S 的一元运算: 求绝对补运算
  - 在 M_n(R) ( n≥2 )上一元运算: 求转置矩阵

9.1.2 二元与一元运算的表示¶

用算符表示二元或一元运算：如 ∘, ∗, · 等
- 对二元运算 ∘，如果 x 与 y 运算得到 z，记做：$x∘y = z$
- 对一元运算 ∘, x 的运算结果记作 $∘x$
- 注意：在同一问题中不同的运算使用不同的算符
用函数表达式（公式）表示二元或一元运算
- 例 1：设 R 为实数集合，如下定义 R 上的二元运算 ∗：$\forall x, y∈R, x ∗ y = \textcolor{#ee0000}{x}$
  
  则: 3 ∗ 4 = 3 0.5 ∗ (-3) = 0.5
- 不要与平时的运算混淆
运算表（表示有穷集上的一元和二元运算）
- $例2：A = P({a, b}),\oplus,\sim分别为对称差和绝对补运算（{a,b}为全集），给出\oplus, \sim的运算表$
  
  ${5N_${VB$NNQDT.png" alt="img" style="zoom:50%;" />

9.1.3 二元运算的性质¶

定义：设 ∘ 为 S 上的二元运算,

如果对于任意的 x, y ∈S 有：x ∘ y = y ∘ x, 则称运算在 S 上满足交换律。
如果对于任意的 x, y, z ∈S 有：(x ∘ y) ∘ z = x ∘ (y ∘ z) 则称运算在 S 上满足结合律。
如果对于任意的 x ∈ S 有：x ∘ x = x 则称运算在 S 上满足幂等律。

例 3：设是集合 Z 中的==可结合== 的二元运算，并且对于任意的 x,y∈Z，若 x*y=y*x，则 x=y。证明 Z 中的每个元素都是幂等的。
- 证明：对任意的 x ∈ Z，因*满足结合律，所以(x*x)*x=x*(x*x)
  
  由已知条件知 x*x = x，所以满足幂等律。

如果$\forall x, y, z∈S$ 有 ① (x ∗ y) ∘ z = (x ∘ z) ∗ (y ∘ z) 右分配 ② z ∘ (x ∗ y) = (z ∘ x) ∗ (z ∘ y) 左分配则称 ∘ 运算对 ∗ 运算满足分配律
如果 ∘ 和 ∗ 都可交换, 并且$\forall x, y, z∈S$ 有 ①x ∘ (x ∗ y) = x；②x ∗ (x ∘ y) = x 则称 ∘ 和 ∗ 运算满足吸收律
$例5：设*和\otimes是集合A上的两个二元运算，且对任意的a, b∈A，a*b=a，证明\otimes对*是可分配的$
- 左分配 ( $a \otimes(b*c) = (a\otimes b)*(a\otimes c)$ )
  - $a \otimes(b*c) = a\otimes b$
  - $(a\otimes b)*(a\otimes c) = a\otimes b$
- 右分配 ($(b*c)\otimes a = (b\otimes a)* (c\otimes a)$)
  - $(b*c)\otimes a = b\otimes a$
  - $(b\otimes a)* (c\otimes a) = b\otimes a$

9.1.4 二元运算特异元素¶

特异元素和分配律有分左右, 其余运算律并没有

- 定义(左右单位元): 设 ∘ 为 S 上的二元运算,如果存在$e_l(或e_r)\in S$,使得对任意 x∈S 都有$e_l∘x=x(或x ∘ e_r=x)$ 则称$e_l($或$e_r$)是 S 中关于 ∘ 运算的左单位元(或右单位元)
- 定义(单位元) : 若e∈S 关于 ∘ 运算既是左单位元又是右单位元,则称 e 为 S 上关于 ∘ 运算的单位元; 单位元也叫做幺元
- 定义(左右零元)：设 ∘ 为 S 上的二元运算, 如果存在$θ_l(或θ_r)∈S$,使得对任意 x∈S 都有 $θ_l ∘ x =θ_l(或x∘θ_r=θ_r )$ 则称$θ_l ( 或θ_r )$是 S 中关于 ∘ 运算的左零元(或右零元)
- 定义(零元) : 若θ∈S 关于 ∘ 运算既是左零元又是右零元，则称 θ 为 S 上关于运算 ∘ 的零元。
- 定义(左右逆元)：令 e 为中关于运算 ∘ 的单位元，对于 x∈S，如果存在$y_l（或 y_r）∈S$ 使得$y_l ∘ x = e（或 x ∘ y_r = e）$ 则称 $y_l ( 或 y_r )$是 x 的左逆元 ( 或右逆元 ) (有逆元的必要条件是有单位元)
- 定义(逆元) : 关于 ∘ 运算，若 y∈S 既是 x 的左逆元又是 x 的右逆元，则称 y 为 x 的逆元。(逆元针对一个元素)
  - 如果 x 的逆元存在，就称 x 是可逆的。
例 6：设 ∘ 运算为 Q 上的二元运算，$\forall x, y\in Q, x∘y = x+y+2xy $ (1) ∘ 运算是否满足交换和结合律? 说明理由 (2) 求 ∘ 运算的单位元、零元和所有可逆元
1. ① $任取x, y∈Q;\quad x\circ y = x+y+2xy = y\circ x, \circ符合交换律$
  
  ② $任取x, y, z\in Q;$
  
  $(x∘y)∘z= (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz$
  
  $x∘(y∘z) = x + (y+z+2yz) + 2x(y+z+2yz) = x+y+z+2xy+2xz+2yz+4xyz$
  
  $\therefore(x∘y)∘z= x∘(y∘z) $
2. 设 ∘ 运算的单位元和零元分别为 e 和 θ
  
  ① $对于任意 x 有 x∘e_r = x 成立，即 x+e_r+2xe_r = x\stackrel{解得}\Longrightarrow e_r = 0 $ 由于 ∘ 运算可交换, $e_r∘ x = x∘e_r = x$，所以左单位元和右单位元相等。即 0 是 ∘ 运算的单位元
  
  ② 对于任意 x 有 x ∘ θr = θr 成立，
  
  即 $x+ θr +2xθr = θr\Longrightarrow x + 2 x θr = 0 \Longrightarrow θr = -\frac{1}{2}$ 由于 ∘ 运算可交换， θr ∘ x = x∘ θr ，所以左零元和右零元相等。即$-\frac{1}{2}$是 ∘ 运算的零元
  
  ③ 给定 x，设 x 的逆元为 y, 则有 x ∘ y = 0(单位元)成立，即 $x+y+2xy = 0 \Longrightarrow y = -\frac{x}{1+2x}(x\neq -\frac{1}{2}) $ 所以当$x\neq -\frac{1}{2}时, x 的逆元为 -\frac{x}{1+2x}$
通过运算表观察得到二元运算的性质和特异元素
- 交换律：运算表关于主对角线==对称== ； 幂等律：主对角线元素排列与表头顺序一致($a_{ii} = a_i$)； 结合律：除了单位元、零元之外，要对所有 3 个元素的组合验证表示结合律的等式是否成立
  - 图解:
- 单位元: 所在的行与列的元素排列都与表头一致零元：元素的行与列都由该元素自身构成 可逆元：若 a 所在的行(第 i 行)中某列 (比如第 j 列) 元素为单位元 e，且第 j 行 i 列的元素也是 e，那么 a 与第 j 个元素互逆。
例 7: (1) 由下面三个运算表给出了三种不同的运算,说明哪些运算是可交换的、可结合的、幂等的。 (2) 求出各个运算的单位元、零元、所有可逆元素的逆元。
- * 满足交换、结合律； ∘ 满足结合、幂等律； $\bullet$ 满足交换、结合律
- * 的单位元为 b, 无零元， $a^{-1} = c, b^{-1} = b, c^{-1} = a$ ∘ 的单位元和零元都不存在，没有可逆元素。 $\bullet$ 的单位元为 a，零元为 c, $a^{-1}=a$, b, c 不可逆

9.1.5 唯一性定理¶

设 ∘ 为 S 上的二元运算，e_l 和 e_r分别为中关于运算的左、右单位元，则 e_l = e_r = e 为上关于 ∘ 运算的惟一的单位元
设 ∘ 为 S 上的二元运算，θ_l 和 θ_r 分别为中关于运算的左、右单位元，则 θ_l = θ_r = θ 为上关于 ∘ 运算的惟一的零元
设 ∘ 为 S 上的二元运算，当 $|S| \geq 2$，单位元与零元是==不同== 的
设 ∘ 为 S 上可结合的二元运算,e 为该运算的单位元, 对于 x∈S 如果存在左逆元 y_l 和右逆元 y_r , 则有 y_l = y_r = y, 且 y 是 x 的惟一的逆元
设 ∘ 为 V 上二元运算，如果$\forall x, y, z\in V$， ① 若 x ∘ y = x ∘ z，且 x 不是零元，则 y = z, (左消去) ② 若 y ∘ x = z ∘ x, 且 x 不是零元，则 y = z, (右消去) 那么称 ∘ 运算满足消去律
由下面三个运算表给出了三种不同的运算是否满足消去律？
- 解：* 满足消去；∘ 和 $\bullet$ 都不满足消去律
- 总结：每个元素所在的行与列中没有重复元素

9.2 代数系统¶

9.2.1 代数系统¶

定义(代数系统)设 S 是个非空集合且 f_i (i=1,2,…,k) 是S 上的一元或二元运算。由 S 及 f₁, f₂, …, f_k 组成的系统称为代数系统，简称代数
- 记作$\textcolor{#66ccff}{<S，f_1，f_2，…，f_k>}$
- S 称为代数系统的载体， S 和运算叫做代数系统的成分
- 实例：是代数系统,但不是代数系统 (N 为非负整数集)
- 因为 S 对 f₂不封闭，即 f2 不是 S 上的二元运算
$\forall x,y\in S, f(<x,y>) = gcd(x,y) <S, f>$ 为代数系统, f 的零元为 1, 将代数系统写作, 1 称作该系统的代数常数

9.2.2 同类型代数系统¶

定义(同类型)：设两个代数系统 V1=和 V2=，如果 f_i和 g_i(1≤i≤m)具有相同的元数，且 V₁和 V₂具有相同个数的代数常数，则称这两个代数系统是同类型的
如果两个同类型的代数系统规定的运算的性质也相同, 则称为同种的代数系统
V₁ = , V₂ =

V₁ V₂是同类型, 但不同种

9.2.3 子代数系统¶

定义(子代数系统)：设是一个代数系统，非空集合$T\subseteq S$对于运算 f₁, f₂ ,… , f_m是封闭的，且 T 含有与 S 中相同的代数常数，则称为代数系统的子代数系统，简称子代数。
- 区别只有集合中的元素, 并且常数一定在
子代数的性质
- n 子代数和原代数是同种的代数系统
- n 对于任何代数系统 V ，其子代数一定存在
- 最大的子代数就是 V 本身；
- 如果 V 中所有代数常数构成集合 B，且 B 对 V 中所有运算封闭，则 B 就构成了 V 的==最小的子代数== ；
- 最大和最小子代数称为 V 的平凡的子代数；
- 若 B 是 S 的真子集，则 B 构成的子代数称为 V 的真子代数。
例 3：设$V_1 = <\{1, 2,3 \}, \circ, 1>$其中$x\circ y$表示取 x 和 y 之中较大的数。求出 V1 的所有子代数。指出哪些是平凡的子代数，哪些是真子代数。
- {1}, {1,2}, {1,3}, {1,2,3}可以构成 V1 的子代数；
- 其中， {1}, {1,2,3}是平凡子代数； {1,2}, {1,3}是真子代数

9.3 代数系统地同构和同态¶

定义(同态映射)：设$V_1= <A, \circ >，V_2= <B,∗>$是同类型的代数系统， f：A→B. 若对任意的 x, y∈A 有$\textcolor{#66ccff}{f (x\circ y) = f(x) ∗ f(y)}$则称 f 是 V₁ 到 V₂ 的同态映射，简称同态。
- 特别地，当 V₁ = V₂ =V 时，则称 f 是 V 的自同态。($f (x\circ y) = f(x) \circ f(y)$)
例 1: $V_1 = <R, +>, V_2 = <R^*, \times>$, 验证$f: R→R^*, f(x) = e^x$ 是 V₁ 到 V₂的同态 (R*表示非零实数集合)
- $\forall x, y\in R, f(x+y) = e^{x+y} = e^x\cdot e^y = f(x)\times f(y)$
例 2：G1=，G2=< Z_n,$\oplus$ >，$\varphi : Z→Z_n, \varphi(x) = (x)\ mod\ n$验证是 G1 到 G2 的同态
- $\forall x, y\in Z$
  
  $ \varphi(x+y) = (x+y) mod n = ((x) mod n + (y) mod n) mod n = (x) mod n \oplus (y) mod n = \varphi (x)\oplus\varphi(y)$
同态和同构
- 设 f:V₁→V₂是 V₁到 V₂的同态
- 若 f: V₁ → V₂是==满射== ，则称 f 为满同态，称 V₂是 V₁的同态像，记作 V₁ ~ V₂
- 若 f: V₁ → V₂是==单射== ，则称 f 为单同态；
- 若 f: V₁ → V₂是==双射== ，则称 f 为同构,记作$V_1\cong V_2$

第十章群¶

10.1 群的定义和性质¶

10.1.1 半群与独异点¶

定义(半群) : 定义：设$V=<S, o>$是代数系统，o 为二元运算，如果 o 运算是==可结合== 的，则称 V 为半群。
- 具有一个二元运算的代数系统
- 例:$（A，*）$是半群，对于 A 中任意两个不同的元素 x 和 y 都有$x*y≠y*x$。证明 A 中每一个元素都是幂等元
  - 由题意可知，当 x≠y 时，必有$x*y≠y*x$，即$x*y=y*x$时，必有 x=y
  - 对任意 a∈ A ，由于*是可结合运算，所以$(aa)a=a(aa) $由此可得 a*a=a，即 a 为幂等元
定义(幺半群)：设 V = 是半群，若 e∈S 是关于 o 运算的==单位元== ，则称 V 是幺半群，也叫做独异点
- 含有幺元的半群
- 例：（R，＋）是半群且含有幺元 0，所以（R，+）是独异点。
半群与独异点的子代数
- 半群的子代数称为子半群
- 独异点的子代数称为子独异点
- 例：, 是的子半群，是的子独异点，不是的子独异点。

10.1.2 群的定义与性质¶

定义(群) : 设是代数系统，о 为二元运算。如果 о 运算是可结合的，存在单位元 e∈G，并且对 G 中的任何元素 x 都有 x^-1∈G，则称 G 为群
- $\textcolor{orange}{半群\stackrel{有单位元}\Longrightarrow独异点 \stackrel{有x^{-1}}\Longrightarrow 群}$
- 实例：
  - ,,是群；不是群
  - 是群，而不是群
例：某二进制码的==码字== $x=x_1x_2...x_7$，其中$x_1,x_2,x_3,x_4$为数据位，$x_5,x_6,x_7$为校验位，并且满足： $x_5=x_1\oplus x_2 \oplus x_3$, $x_6=x_1 \oplus x_2 \oplus x_4$, $x_7=x1\oplus x_3\oplus x_4$
- 设 G 为所有码字构成的集合，在 G 上定义二元运算 : $\forall x,y\in G, x\circ y=z=z_1z_2...z_7, z_i=x_i\oplus y_i$
- $<G,\circ>$构成什么类型的代数系统?
- 封闭性($z\in G, 即z满足码字的特点$)
  
  $ \forall x,y \in G, x=x_1x_2...x_7，y=y_1y_2...y_7， x\circ y=z =z_1z_2...z_7, $
  - 先验证 $z_5=z_1\oplus z_2\oplus z_3$ $z_1\oplus z_2\oplus z_3 = (x_1\oplus y_1)\oplus (x_2\oplus y_2)\oplus (x_3\oplus y_3) = (x_1\oplus x_2\oplus x_3)\oplus (y_1\oplus y_2\oplus y_3) = x_5\oplus y_5 = z_5$
  - 同理可以验证$z_6=z_1\oplus z_2\oplus z_4$ $z_7=z_1\oplus z_3\oplus z_4$ 所以$z=z_1z_2...z_7\in G$,即 G 对$\circ$运算封闭
- 单位元
  - $\forall x\in G, x_1x_2...x_7\circ 0000000=x_1x_2...x_7\qquad 0000000\circ x_1x_2...x_7=x_1x_2...x_7$
  - $\circ$ 不一定可交换
  - 所以 0000000 是$<G,\circ>$的单位元
- 逆元
  - $\forall x\in G, 因为x_i取值为0或1 ,且0\oplus 0=0, 1\oplus 1=0$
  - 所以 x_i的逆元为 x_i , $(x_1x_2...x_7)^{-1}=x_1x_2...x_7$
- 所以 $<G, \circ>是群$
Klein 四元群
- G={e, a, b, c}, G 上的运算由下表给出
- 运算表特征
  - 对称性---运算可交换
  - 主对角线元素都是幺元 e
  - 每个元素是自己的逆元
  - a, b, c 中任两个不同的元素运算都等于第三个元素 (可推出满足结合性)
- 上面的这个群称作 Klein 四元群

群的相关术语¶

定义(有限 / 无限群) : 若群 G 是有穷集，则称 G 是有限群，否则称为无限群
定义(有限群的阶) : 有限群群 G 的基数(元素的个数)称为群 G 的阶，记作|G|。
定义(交换群 / Abel 群) : 若群 G 中的二元运算是==可交换== 的，则称 G 为交换群或阿贝尔(Abel)群
定义(群的元素的 n 次幂) : 设 G 是群, x∈G, n∈Z，则 x 的 n 次幂 $x^n$ 定义为：$x^n \begin{cases}e &n=0\\ x^{n-1}x&n>0\\ (x^{-1})^m & m=-n, n<0\end{cases} n\in Z$

分别在$<Z_3,\oplus >$中求$2^{-3}$，在中求$(-2)^{-3}$
- $<Z_3,\oplus >$的单位元是 0, 任意的$x\in Z_3$, x 的逆元为(3-x), 2 的逆元为 1
  
  $2^{-3} = (2^{-1})^{3} = 1\oplus 1\oplus 1 = 2\oplus1=0$
- $<Z, +>$的单位元为 0, $(-2)^{-3} = 2^3 = 2+2+2 = 6$

例:在$<Z_6,\oplus>$中,1⁶，2³，3²，4³，5⁶的值分别为多少？
- $1^6 =1\oplus1\oplus1\oplus1\oplus1\oplus1= 0=e$
- $2^3 =2\oplus2\oplus2= 0=e$
- $3^2 =3\oplus3= 0=e$
- $4^3 =4\oplus4\oplus4= 0=e$
- $5^6 =5\oplus5\oplus5\oplus5\oplus5\oplus5= 0=e$
- 结论：0 是 1 阶元；2 和 4 是 3 阶元； 3 是 2 阶元；1 和 5 是 6 阶元。

定义(元素的阶) : 设 G 是群，x∈G，使得等式$x^k=e$成立的最小正整数 k 称为x 的阶（或周期），记作 |x|=k，称 x 为k 阶元。若不存在这样的正整数 k，则称 x 为无限阶元
- e 是 1 阶元
- 例：在中，哪些元素有阶数？
  
  0 是 1 阶元，其它整数的阶都不存在。

群的性质¶

定理 1 群的幂运算的性质 : 设 G 为群, 则 G 中的==幂运算== 满足
1. $\forall x∈G，(x^{-1}) = x $
2. $\forall x, y∈G，(xy)^{-1} = y^{-1}x^{-1}$
3. $\forall x∈G，x^nx^m = x^{n+m}，n, m∈Z$
4. $\forall x∈G，(x^n)^m = x^{nm}，n, m∈Z.$
5. 若 G 为可交换群，则$(xy)^n = x^n y^n$
定理 2 群的运算的消去律 : G 为群，则 G 满足消去律，即$\forall a,b,c∈G$ 有
1. 若 ab = ac，则 b = c (左消去)
2. 若 ba = ca，则 b = c (右消去)
例：设 G 为群， a,b∈G，k∈Z⁺，证明：$(a^{-1}ba)^k = a^{-1}ba \Leftrightarrow b^k = b$
- $(a^{-1}ba)^k = a^{-1}ba \Leftarrow b^k = b$
  
  $(a^{-1}ba)^k = (a^{-1}ba)(a^{-1}ba)...(a^{-1}ba)\\=a^{-1}b(a^{-1}a)b(a^{-1}a)b...(a^{-1}a)b\\=a^{-1}b^ka = a^{-1}ba$
- $(a^{-1}ba)^k = a^{-1}ba \Rightarrow b^k = b$
  
  $(a^{-1}ba)^k = (a^{-1}ba)(a^{-1}ba)...(a^{-1}ba)\\=a^{-1}b(a^{-1}a)b(a^{-1}a)b...(a^{-1}a)b\\=a^{-1}b^ka$
  
  $\therefore a^{-1}b^ka = a^{-1}ba$
  
  $由消去律得 b^k = b$
群的运算表可以看出：每一行或每一列都是群中所有元素的一个排列。
例：设 G = {a1, a2, …, an} 是 n 阶群，令$a_iG = { a_i a_j|j=1,2, … , n} $ 证明：a_iG = G
- 证：因为群对其上运算有封闭性， $a_i a_j ∈G$，所以$a_i G\subseteq G$。假设$a_i G\subset G$，即$|a_i G|<n$ 则必存在$a_j, a_k∈G$使得$a_i a_j = a_i a_k （j≠k） $ 由消去律得 $a_j = a_k$, 与 |G| = n 矛盾。所以，$a_iG = G$
定理 3 群的元素的阶 ：设 G 为群，a∈G，且|a|=r，设 k 是整数，则
1. $a^k=e$ 当且仅当$r|k$ (r 能整除 k)
2. $|a^{-1}| = |a|$
- 例：设 G 为群， a,b∈G 是有限阶元，证明：
  
  ①$|b^{-1}ab| = |a|$
  1. 设|a|=r ; |b^-1ab|=t
    要证|b^-1ab| = |a| 即证 r|t, 且 t|r
    
    - -
例:设 G 为有限群, 证明 G 中阶大于 2 的元素有偶数个
- G 中的 1 阶元==为== G 的单位元 e, e¹=e, e=e^-1 ；
- 设 G 中的 2 阶元为 x，则 x²=e 即：xx=e，又因为 xx^-1=e 所以由消去律得：x = x^-1
  - $①\ x^2 = e\Rightarrow x = x^{-1}$
- 若 $x = x^{-1}$ 则有 $x^2 = xx = xx^{-1}=e $
  - $②\ x = x^{-1} \Rightarrow x^2 = e$
- $\textcolor{#66ccff}{x为G中的1阶或二阶元\Leftrightarrow x^2 = e\Leftrightarrow x = x^{-1}}$
  
  若 x 为 G 中阶数>2 的元素那么$x\neq x^{-1}$
- $|x| = |x^{-1}|$ 所以 G 中阶数大于 2 的元素成对出现，即 G 中阶数大于 2 的元素有偶数个
证明：偶数阶群必含 2 阶元。
- 群一定含有单位元，且单位元是群中唯一的 1 阶元；(一个元)
- 由前面一题的证明可知，群中阶数大于 2 的元素一定有偶数个。(偶数个元素)
- 所以为了使得群中含有偶数个元素，群中至少有一个 2 阶元。

10.2 子群¶

10.2.1 子群的定义¶

定义(子群 & 真子群)：
- 设 G 是群，H 是 G 的非空子集，如果 H 关于 G 中的运算构成群，则称 H 是 G 的子群, 记作 $\textcolor{#66ccff}{H≤G}$;
- 若 H 是 G 的子群，且 $H\subset G$，则称 H 是 G 的真子群，记作$\textcolor{#66ccff}{H<G}$。
定理:
- 对任何群 G 都存在子群。
- G 和{e}都是 G 的子群，称为 G 的平凡子群
例：设为群，定义集合 S 如下：$S = \{a|a\in G 且 \forall x(x\in G\rightarrow a _ x = x \*a)\}$

证明是的子群
- ① 由 S 集合的定义可知, $S \subseteq G$
- ② 证明 S 对运算*封闭 (a*b 运算结果也属于 S)
  
  $a * x = x * a;\ b * x = x * b$
  
  $(a*b)*x = a*(b*x) = a*(x*b) = (a*x)*b = (x*a)*b = x*(a*b)$
  
  $\therefore a*b \in S$
- ③ 证明 S 中含有单位元 e（G 中的单位元）
  
  $\forall x\in G, e*x = x*e \qquad\therefore e\in S$
- ④ 证明 S 中的任意元素都存在逆元
  
  $\forall a\in S ; \forall x\in G$
  
  $x*a^{-1} \ = (a^{-1}*a)*x*a^{-1} = a^{-1}*x*a*a^{-1} = a^{-1}*x$
  
  $\therefore a^{-1}\in S$
- 由 ①~④ 证明了是的子群

10.2.2 子群的判定定理¶

判定定理 1：设 G 为群，H 是 G 的非空子集。H 是 G 的子群当且仅当

①$\forall x, y∈H有 \textcolor{#ee0000}{x y∈H}$；

②$\forall x∈H有 \textcolor{#ee0000}{x^{-1}∈H}$
判定定理 2：设 G 为群，H 是 G 的非空子集。H 是 G 的子群当且仅当$\textcolor{#66ccff}{\forall x, y∈H有 x y^{-1}∈H}$
判定定理 3：设 G 为群，H 是 G 的非空子集，如果 H 是==有穷集== ，则 H 是 G 的子群当且仅当$\textcolor{#66ccff}{\forall x, y∈H有 x y∈H}$

注意：G 为群，H 为 G 的非空子集判定定理 1 和 2 适用于任何的 H 判定定理 3 只适用于 H 为有限集的情况

例：设是群的子群，如果$A=\{x|x\in G, x*H*x^{-1} = H\}$

证明：是的子群。
- 存在$e\in G, e*H*e^{-1} = H, e\in A$ 所以 A 是 G 的非空子集
- 根据判定定理 2 知, 只需要证明$\forall x, y\in A, 有x*y^{-1}\in A$即可
  - $\forall x, y\in A, 有x*H*x^{-1} = H;\ y*H*y^{-1} = H$ $y^{-1}*H*y = y^{-1}*(y*H*y^{-1})*y =( y^{-1}*y)*H*(y^{-1}*y) = H$
  - $\forall x, y\in A, x\in G, y\in G\quad \therefore y^{-1}\in G\quad \therefore x*y^{-1}\in G (代数系统上的二元运算具有封闭性)$ $(x*y^{-1})*H*(x*y^{-1})^{-1} = x*y^{-1}*H*(y^{-1})^{-1}*x^{-1} = x*(y^{-1}*H*y)*x^{-1} = x*H*x^{-1} = H$
  - 综上所述, $x*y^{-1}\in A$, 所以是的子群

10.2.3 生成子群¶

例：设 G 为群，a∈G，令 H = { a^k |k∈Z }，证明：H 是 G 的子群。
- 证：首先由 a∈H 知道 H≠Ø。任取 a^m, a^l ∈H,
  则 a^m (a^l)^-1 = a^m a^-l = a^m-l∈H 根据判定定理 2 可知 H≤G。
- 定义(生成子群): H 是由 a 生成的子群, 记作< a > , $<a> = \{ a^k |k∈Z \}$
- 整数加群，由 2 生成的子群: <2>= {2^k |k∈Z } = 2Z
- 模 6 加群中，由 2 生成的子群 <2>= {0,2,4}
- Klein 四元群 G = {e, a, b, c} 的所有生成子群是：< e > = {e}, < a > = {e, a}, < b > = {e,b}, < c > = {e,c}
例：设 G 为群, 令$C=\{ a|a∈G∧\forall x∈G (a x=x a)\textcolor{orange}{(a可交换)}\}$，证明 C 是 G 的子群。
- 证：e∈C，C 是 G 的非空子集。任取 a, b∈C，证明 $ab^{-1}$与 G 中所有的元素都可交换 $\forall x∈G，有(ab^{-1})x = ab^{-1}x = ab^{-1}(x^{-1})^{-1} = a(x^{-1}b)^{-1} = a(bx^{-1})^{-1} = a(xb^{-1}) = (ax)b^{-1} = (xa)b^{-1} = x(ab^{-1})$ 所以$ab^{-1}∈G$，由判定定理可知 C≤G。
- 定义(群的中心) : 群 G 的中心$C=\{ a|a∈G∧\forall x∈G (a x=x a)\textcolor{orange}{(a可交换)}\}$
例：设 G 为群, H,K 是 G 的子群。证明：（1）H∩K 也是 G 的子群；（2）H∪K 是 G 的子群的充要条件是 H⊆K 或 K⊆H
- e∈H，e∈K,所以 e∈H∩K, H∩K 非空；任取 a, b∈H∩K，a, b∈H 且 a, b∈K， $ab^{-1}∈H 且ab^{-1}∈K ，所以ab^{-1}∈H∩K$ 由判定定理 2 可知 H∩K≤G。
- ①H⊆K 或 K⊆H⟹H∪K 是 G 的子群
  - 显然易得 (H⊆K 时, H∪K = K, 是 G 的子群…)
- ②H∪K 是 G 的子群 ⟹H⊆K 或 K⊆H
  - 反证法 H⊈K，K⊈H 存在 h∈H，h∉K 且存在 k∈K，k∉H, 因此 hk ∉H，hk ∉K 即 hk ∉H∪K ，与 H∪K 是 G 的子群矛盾，所以假设错误。

10.2.4 群的分解¶

不考摸了

Part4 图论¶

第十四章图的基本概念¶

14.1 图的基本概念¶

14.1.1 有向图的相关概念¶

定义(有向图)：有向图 D = , 其中
1. ① V 为顶点集($V\neq \empty$)，元素也称为顶点
2. ② E 为$V\times V$ 的多重子集，其元素称为有向边，简称边
  
  - $V\times V$ : 点集的笛卡尔积, 说明边有方向性
  
  - 多重集合 : 元素可以重复出现的集合 (允许出现两条一样的边, 也就是平行边)
- 用无向边代替有向图 D 中所有有向边所得到的无向图称作 D 的基图
写出有向图的 V 和 E
- V={a, b, c,d}, E={(圈),,< a,b>(平行边), ,< c,b >,,< d,c >}
- 注意：有向图的边集中的元素是有序对，即==序偶== 。

14.1.2 无向图的相关概念¶

定义(有向图)：有向图 D = , 其中
1. ① V 为顶点集($V\neq \empty$)，元素也称为顶点
2. ② E 为$V\& V$ 的多重子集，其元素称为无向边，简称边 - $V\& V$ : 无序积, $A\&B=\{\{x,y\}|x\in A\land y\in B\}$。无序积的元素称作无序对,记为(x,y) ，(x,y) = (y,x)
- e.g. G=如图所示, 其中 V={v1, v2, …,v5}, E={(v1,v1)(环), (v1,v2), (v2,v3)(平行边), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}

14.1.3 无向图与有向图的相关概念¶

含平行边的图称为多重图。

既无平行边也无环的图称为简单图。
G 通常泛指无向图和有向图；D 只表示有向图。

如果图中的顶点和边都用字母进行标定，则称该图为标定图。
空图: V=Ø，记作 Ø。零图: E=Ø。平凡图: 1 阶零图

14.1.4 顶点和边的关系¶

点与边的关联关系（环，孤立点）点与点的相邻关系（邻接到，邻接于）
设无向图 G =, $v\in V$ - $v的\textcolor{#66ccff}{邻域} : N_G(v)=\{u|u\in V \land (u,v)\in E(G) \land u\neq v\}$ - $ v 的\textcolor{#66ccff}{闭邻域} : \overline{N}_G(v)=N_G(v) \cup {v}$ - $v的\textcolor{#66ccff}{关联集} I_G(v) = \{e|e\in R\land e与v关联\}$
设有向图 D =, $v\in V$ - $v的\textcolor{#66ccff}{后继元集} \Gamma^+_D(v)=\{u|u\in V \land <v,u>\in E \land u\neq v\}$ - $v的\textcolor{#66ccff}{先驱元集} \Gamma^-_D(v)=\{u|u\in V \land <u,v> \in E \land u\neq v\}$ - $v的\textcolor{#66ccff}{邻域} N_D(v) = \Gamma^+_D(v)\cup \Gamma^-_D(v)$ - $v的\textcolor{#66ccff}{闭邻域} \overline N_D(v) = N_D(v)\cup \{v\}$

14.1.5 图的度¶

定义:
- 顶点的度 : $d_G(v), 简记为d(v), d(v) = d^-(v) + d^+(v)$ 入度 : $d^-(v)$ 出度 : $d^+(v)$
- 最大度 : $\Delta(G)$ 最小度 : $\delta(G)$
- 悬挂点 : 1 度顶点悬挂边 : 和 1 度顶点相连接的边
图的度数列
- 设无向图 G 的顶点集$V=\{v_1, v_2, …, v_n\}$
- G 的度数列: $d(v_1), d(v_2), …, d(v_n)$；
- 若 G 为有向图
  - D 的度数列: $d(v_1), d(v_2), …, d(v_n)$
  - D 的出度列: $d^+(v_1), d^+(v_2), …, d^+(v_n)$
  - D 的入度列: $d^-(v_1), d^-(v_2), …, d^-(v_n)$
图化问题 : 对于给定的非负整数列 d=(d₁, d₂, …, d_n), 若存在以 V={v₁, v₂, …, v_n}为顶点集的 n 阶无向图 G，使得 d(v_i)= d_i ,则称 d 是可图化的。若所得图是简单图，则称 d 是可简单图化的。

度的相关定理¶

握手定理 : 无向图 G=和有向图 D= ,V={v₁,v₂,…,v_n},其所有顶点度数之和等于==边数的 2 倍== $(\sum ^{i=n}_{i=1}d(v_i) = 2|E|)$ 并且对于有向图而言，其所有顶点入度之和等于出度之和等于边数$(\sum ^{i=n}_{i=1}d^+(v_i) = \sum ^{i=n}_{i=1}d^-(v_i) = |E|)$
- 推论: 在任何无向图和有向图中, 奇度顶点的个数一定为==偶数个== (可以用来判断度数列能不能成图)
定理：设非负整数列 d=(d₁, d₂, …, d_n)，则 d 是可图化的当且仅当$\sum^{n}_{i=1}d_i$为==偶数== 。
定理：设 G 为任意 n 阶无向简单图，则$\Delta (G) \leq n-1$
例：(3,3,3,4), (2,3,4,6,8)能成为图的度数列吗?
- 不能, 它们有奇数个奇度顶点
例：已知图 G 有 10 条边, 4 个 3 度顶点, 其余顶点的度数均小于等于 2, 问 G 至少有多少个顶点?
- 设 G 有 n 个顶点。由握手定理, $4\times 3+2\times(n-4)\geq 2\times10$ 解得$n\geq 8$
例：画出 4 阶 3 条边的所有非同构的无向简单图
- 由握手定理得$\sum^{i=4}_{i=1}d(v_i) = 6$ 因为是无向简单图, 所以$\Delta (G)\leq 3$ 并且奇度顶点的个数一定为偶数
- 可能成为度数列的非负整数列有(3 3 1 1) (2 2 2 0) (2 2 1 1)
例：画出 3 阶 2 条边的所有非同构的有向简单图
- $\sum^{i=3}_{i=1}d(v_i) = 4;\quad \sum^{i=3}_{i=1}d^+(v_i) = \sum^{i=3}_{i=1}d^-(v_i) = 2$
  
  $d(v_i)\leq 2, d^+(v_i)\leq 2, d^-(v_i)\leq 2 (i = 1,2,3)$

14.1.6 图的同构¶

定义(无向图的同构)：设$G_1=<V_1,E_1>, G_2=<V_2,E_2>$为两个无向图, 若存在双射函数 $f: V_1\rightarrow V_2$, 使得对于任意的$v_i,v_j\in V_1, (v_i,v_j)\in E_1$当且仅当 $(f(v_i),f(v_j))\in E_2$，并且, $(v_i,v_j)$与 $(f(v_i),f(v_j))$的==重数相同== ，则称$G_1与G_2$是同构的，记作$\textcolor{#66ccff}{G_1\cong G_2}$
定义(有向图的同构)：设$G_1=<V_1,E_1>, G_2=<V_2,E_2>$为两个有向图, 若存在双射函数 $f: V_1\rightarrow V_2$, 使得对于任意的$v_i,v_j\in V_1, <v_i,v_j>\in E_1$当且仅当 $<f(v_i),f(v_j)>\in E_2$，并且, $<v_i,v_j>$与 $<f(v_i),f(v_j)>$的==重数相同== ，则称$G_1与G_2$是同构的，记作$\textcolor{#66ccff}{G_1\cong G_2}$
- 关于图同构的定义说明：两个图的各顶点之间如果存在一一对应关系，而且这种对应关系保持了顶点间的邻接关系（在有向图中还保持边的方向），则这两个图是同构的。
- 两个同构的图除了顶点和边的名称不同外，实际上代表了同样的组合结构。
两个图为同构的==必要条件== 有： ① 边数相同，顶点数相同 ② 度数列相同(不计度数的顺序) ③ 对应顶点的关联集及邻域的元素个数相同
- 图之间的同构关系是等价关系。
例：判断下述每一对图是否同构。
- 因为度数列不同，所以不同构。
- 因为入(出)度列不同，所以不同构。

14.1.7 特殊图¶

n 阶无向完全图，边数为$\frac {n(n-1)}2, 记作\textcolor{#66ccff}{K_n(n\geq1)}$； n 阶有向完全图，边数为$n(n-1)$
定义(竞赛图)：在 n 阶有向简单图中,如果其==基图== 是 n 阶无向完全图,则称此有向图为n 阶竞赛图。
- 左图所示为 5 阶竞赛图, 有 10 条边。
定义： G 为 n 阶无向简单图，$\forall v\in V(G), d(v) = k$ 则称 G 为k-正则图
- 左图为彼得森图, 它是 3-正则图, 边数为 15
- n 阶无向完全图是(n-1)-正则图
- n 阶无向零图是 0 -正则图

14.1.8 子图¶

定义：设$G=<V,E>, G'=<V',E'>$是两个图 (1) 若$V'\subseteq V且E'\subseteq E$, 则称 G'为 G 的子图, G 为 G'的母图, 记作$\textcolor{#66ccff}{G'\subseteq G}$。 (2)若$V'\subset V或E'\subset E$，称 G'为 G 的真子图 (3)若$V'=V且E'\subseteq E$,则称 G'为 G 的生成子图顶点数相同的子图 (4)设$V'\subset V 且V'\neq \empty$, 以 V'为顶点集, 以 G 中两端点都在 V'中的边组成边集的图称作$V'$的导出子图，记作 $\textcolor{#66ccff}{G[V']}$。 (5)设$E'\subset E且E'\neq \empty$, 以 E'为边集, 以 E'中边关联的所有顶点为顶点集的图称作$E'$的导出子图, 记作 $\textcolor{#66ccff}{G[E']}$。
例：判断下列图(b),(c),(d)与图(a)之间的关系。
- (b)是(a)的生成子图； (c),(d)是(a)的子图；
- (b)是边集{(a,b),(b,c),(a,e),(a,c) ,(e,d)}导出的子图；
- (c)是边集{(a,b),(b,e),(a,e),(a,c)}导出的子图；
- (d)是边集{(a,b),(b,c),(a,e),(b,e)}导出的子图； (d)也是由点{a,b,c,e}导出的子图。
例：画出 K₄的所有非同构的生成子图

14.1.9 补图¶

补图：设 G=为 n 阶无向简单图，在 G 中添加一些边后，可使 G 成为==n 阶完全图== ，由这些添加边和 G 的 n 个顶点构成的图称为 G 的补图，记作$\textcolor{#66ccff}{\overline{G}}$
- 若$G\cong \overline{G}$, 则称 G 是自补图
- 右边的图是左边的图的补图。
图 b 是图 a 的补图，且图 b 与图 a 同构，所以 a 是自补图。
图 d 是图 c 的补图，图 d 与图 e 同构，所以图 e 也是图 c 的补图。

14.1.10 无向图的相关操作¶

设 G=为无向图。
1. 删边：删去图 G 中的某一条边 e，但仍保留边的端点，记为G-e。若$E'\subset E$,则 $\textcolor{#66ccff}{G- E'}$ 表示从 G 中删除$E'$中的所有边
2. 删点：删去图 G 中的某个点 v 及其所关联的一切边, 称为删除顶点 v, 记为G-v。若$V'\subset V$,则$\textcolor{#66ccff}{G-V'}$表示从 G 中删除$V'$中的所有顶点
3. 边 e 的收缩：边$e=(u,v)\in E$,从 G 中删除 e 后，将 e 的两个端点 u,v 用一个顶点 w 代替，使 w 关联除 e 以外 u,v 关联的所有边，记为$G\setminus e$。
4. 添加新边：$u,v\in V$, 在 u,v 之间添加一条边(u,v)，记为$\textcolor{#66ccff}{G∪(u,v)}$。
例:(1)将图中的边 e1 删去； (2)删去右图中的点 v2

14.2 通路与回路¶

定义(通路和回路)：给定图 G=（无向或有向的），G 中顶点与边的交替序列 $\Gamma =v_0e_1v_1e_2…e_lv_l$，若$\forall i(i\leq i\leq l)$, $v_{i-1}$, $v_i$是$e_i$的端点(对于有向图, 要求$v_{i-1}$是始点, $v_i$是终点), 则称$\Gamma$为通路, v₀是通路的起点, v_l是通路的终点；图中边的条数 l 称作通路的长度。若$v_0=v_l$，则称$\Gamma$为回路
通路和回路常用表示方法
1. 用顶点和边的交替序列(定义), 如 $\Gamma =v_0e_1v_1e_2…e_lv_l$
2. 用边的序列, 如$\Gamma =e_1e_2…e_l$
3. 简单图中, 用顶点的序列, 如$\Gamma =v_0v_1…v_l$
初级通路：若通路(回路)中所有顶点(对于回路, 除$v_0=v_l$)各异，所有边也各异，则称为初级通路(初级回路)。
- 初级通路又称作路径, 初级回路又称作圈。
简单通路：若通路(回路)中所有边各异, 则称为简单通路(简单回路)
- $v_1v_2v_6v_5v_2v_3$是一条通路，而且是简单通路；但不是初级通路（路径）( $v_2$重复)；
  
  $v_1v_2v_3$是一条通路，而且是初级通路（路径），也是简单通路。
- 环是长度为 1 的圈；
- 无向图中，两条平行边构成长度为 2 的圈；
- 在无向简单图中, 所有圈的长度$\geq3$;
- 在有向简单图中, 所有圈的长度$\geq 2$。
定理 : 在 n 阶图 G 中，若从顶点$v_i到v_j (v_i\neq v_j)$存在通路，则从$v_i$到$v_j$存在长度小于等于$n-1$的==通路== 。

推论 : 在 n 阶图 G 中，若从顶点$v_i到v_j (v_i\neq v_j)$存在通路，则从$v_i$到$v_j$存在长度小于等于$n-1$的==初级通路== 。

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

推论：在一个 n 阶图 G 中，若存在 vi 到自身的回路，则一定存在 vi 到自身长度小于等于 n 的==初级回路== 。
例：无向完全图 K_n 中有几种非同构的初级回路（圈）？
- 即有多少个长度不同的圈: n-2 种

14.3 图的连通性¶

14.3.1 无向图的连通性¶

一. 无向图的连通性¶

连通：设 G=，若$u,v\in V$，且 u,v 之间存在通路，则称 u,v 连通，记作$u\sim v$。
连通关系：$R=\{<u,v>| u,v \in V且u\sim v\}$。连通关系是 V 上的==等价关系== 。
- 该图中的顶点被分作两组，同一组中的顶点两两连通，即每一组中的顶点构成一个等价类。
- 该图不是连通图，且具有两个连通分支。

二. 无向图的连通分支¶

连通分支: V 关于连通关系 R 的等价类的导出子图。
设$V/R=\{V_1,V_2,…,V_k\}$, $G[V_1], G[V_2], …,G[V_k]$是 G 的连通分支, 其个数(连通分支数)记作p(G)=k
G 是连通图$\Leftrightarrow$ p(G)=1

三. 无向图的短程线与距离¶

设无向图 G=
- u 与 v 之间的短程线：当 u~v 时(联通), u 与 v 之间长度最短的通路；
- u 与 v 之间的距离：u 与 v 之间短程线的长度。记作d(u,v)。
  - 若 u 与 v 不连通, 规定 d(u,v)=∞。
- 图中 v₂~ v₅ ， v₂和 v₅之间通路有：
  
  $\Gamma_1 = v_2v_1v_5;\ \Gamma_2 = v_2v_1v_3v_5;\ \Gamma_3 = v_2v_1v_3v_5;\ \Gamma_2 = v_2v_4v_5;\ \Gamma_4 = v_2v_4v_3v_5;$ $d(v_2, v_5) = 2$
u 与 v 之间的距离满足以下性质：
- $d(u,v)\geq0$, 且$d(u,v)=0 \Leftrightarrow u=v$
- $d(u,v)=d(v,u)$
- $d(u,v)+d(v,w)\geq d(u,w) $ 从 u 借助 v 到 w

四. 无向图的点割集&边割集¶

定义(点割集) : 设无向图 G=, $V'\subset V$，V’ 非空。若$p(G-V') >p(G)$(删去 V’后, 连通分支数变大(出现新的非连通部分))，且$\forall V''\subset V', p(G-V'') = p(G)$ , 则(V’ 不能再拆分)称 V’为 G 的点割集。
- 特别地，当{v}为点割集时, 称 v 为割点。
- {v1,v4}, {v6}是点割集, v6 是割点； {v2,v5}是点割集吗？不是， v5 是割点
定义(边割集) : 设无向图 G=, $E'\subset E$，E’ 非空。若$p(G-E') >p(G)$，且$\forall E''\subset E', p(G-E'') = p(G)$ , 则称 E’ 为 G 的边割集。
- 特别地，当{e}为点割集时, 称 e 为割点边或桥。
关于点割集和边割集的几个结论：
1. K_n无点割集 - 删去一个点不会影响连通性
2. n 阶零图既无点割集，也无边割集
3. 若 G 连通，E’ 为边割集，则$p(G-E' ) \textcolor{#ee0000}{= 2}$
4. 若 G 连通，V’ 为点割集，则$p(G-V')\textcolor{#ee0000}{\geq 2}$

五. 无向图的点连通度&边连通度¶

定义(点连通度)：设 G 为无向连通图且不含完全图作为子图，则称$\kappa(G)=min\{|V'|\ |\ V'为G的点割集\}$为 G 的点连通度，简称连通度
- 规定：完全图 K_n的点连通度为 n-1。非连通图的点连通度为 0。
- 连通度越大, 说明需要删除越多的点才能使图不再联通
若$\kappa (G)\geq k, 则成G是\textcolor{#66ccff}{k-连通图}$
- 若 G 是 k-连通图，则在 G 中删去任意的k-1个顶点，所得图仍然是连通的。
- 点连通度为：1；称此图为 1-连通图。
- 左图为 5 阶完全图 K5，点连通度为 4
- 此图是 1-连通图， 2-连通图，3-连通图，4-连通图。
定义(边连通度)：设 G 为无向连通图，称$\lambda (G)=min\{|E'|\ |\ E'为G的边割集\}$为 G 的边连通度
- 规定 : 非连通图的边连通度为 0
若$\lambda (G)\geq r, 则成G是\textcolor{#66ccff}{r边-连通图}$
- 若 G 是 r 边-连通图，则在 G 中删去任意的r-1条边，所得图仍然是连通的。
- G₁和 G₂都是 5 阶无向简单图,
  
  $\lambda(G_1) = 2; \lambda(G_2) = 4; \lambda(G_2) > \lambda(G_1) $
  
  G₂ 比 G₁边连通度高。
定理:
- 对于无向图 G, 有$\textcolor{#66ccff}{\kappa (G)\leq\lambda(G) \leq \delta(G)}$
- 对于 n 阶无向完全图 G, 有$\kappa (G)=\lambda(G) = \delta(G) = n-1$
- 对于 n 阶零图 G, 有$\kappa (G)=\lambda(G) = \delta(G) = 0$
- $\delta(G) = 3\\\lambda(G) =2\\\kappa(G) = 1$

14.3.2 有向图的连通性¶

一. 有向图的连通性¶

定义(可达)：设有向图 D=，$\forall u,v\in V$

- 如果 u 到 v 有通路，则称u 可达 v，记作$u→v$; 规定 u 到自身总是可达的。 - 若 u→v 且 v→u，则称 u 和 v 是相互可达的，记作$u\leftrightarrow v$
连通图种类

- D 是弱连通图(连通图): D 的基图为无向连通图 - D 是单向连通图: $\forall u,v\in V$，u 可达 v 或 v 可达 u - D 是强连通图: $\forall u,v\in V$，u 与 v 相互可达

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

二. 有向图的短程线与距离¶

定义：设有向图 D=
- u 到 v 的短程线: u 可达 v, u 到 v 长度最短的通路
- u 与 v 之间的距离$d<u,v>$: u 到 v 的短程线的长度
  - 若 u 不可达 v, 规定 d=∞。
性质：
- $d<u,v>\ \geq 0$, 且$d<u,v>=0 \Leftrightarrow u=v$d
- $d<u,v>+\ d<v,w>\ \geq\ d<u,w>$

14.3.3 二部图¶

定义(二部图)：若无向图 G 的顶点集 V 可以划分成两个子集 V1 和 V2 (即 V1∪V2=V，V1∩V2= Ø) 使图中的每一条边的一个端点在 V1 中，另一个端点在 V2 中，则称 G 为二部图或偶图，记作(V1,V2,E)。
- V1 和 V2 称作互补顶点子集。
定义(完全二部图)：若(V1,V2,E)是简单二部图，且 V1 中的每一个顶点都与 V2 中的每一个顶点邻接，则称图(V1,V2,E)为完全二部图，记作$\textcolor{#66ccff}{K_{r,s}}$，其中 r =|V₁|，s =|V₂|。
定理：无向图 G 为二部图的==充要条件== 是图 G 中的每一条回路都由偶数条边组成。

14.4 图的矩阵表示¶

14.4.1 无向图的关联矩阵¶

定义：设无向图 G=, V={v₁, v₂, …, v_n}, E={e₁, e₂, …, e_m}, 令 m_ij为 v_i与 e_j的关联次数 $m_{ij} = \begin{cases}0,&v_i与e_j无关\\ 1, &v_i与e_j关联一次\\ 2, &v_i与e_j关联两次(自连)\end{cases}$

，称$(m_{ij})_{n\times m}$为G 的关联矩阵，记为M(G)
- 矩阵 n 行 m 列, 顶点数 n 行, 边数 m 列
M(G)的性质
1. $\sum^n_{i=1}m_{ij} = 2(j=1,2,...,m)$ : 第 j 条边只会与两个顶点相连
2. $\sum^m_{j=1}m_{ij} = d(v_i)(j=1,2,...,m)$ : 第 i 个顶点与边的关联次数记为 i 的度数
3. $\sum^n_{i=1}d(v_i) = \sum^n_{i=1}\sum^m_{j=1}m_{ij} = \sum^m_{j=1}\sum^n_{i=1}m_{ij} = \sum^m_{j=1}2 = 2m$
4. 平行边在关系矩阵中的列相同

14.4.2 有向图的关联矩阵¶

定义：设无环有向图 D=, V={v₁, v₂, …, v_n}, E={e₁, e₂, …, e_m}, 令 $m_{ij} = \begin{cases}1,&v_i为e_j的始点\\ 0, &v_i为e_j不关联\\ -1, &v_i为e_j的终点\end{cases}$ , 则称$(m_{ij})_{n\times m}$为D 的关联矩阵，记为M(D)
- 矩阵 n 行 m 列, 顶点数 n 行, 边数 m 列
M(D)的性质
1. $\sum^n_{i=1}m_{ij} = (j=1,2,...,m)$ : 第 j 条边只会与两个顶点相连, 一个 1, 一个-1
2. $\sum^m_{j=1}(m_{ij} = 1) = d^+(v_i) \textcolor{orange}{(出度)}$
  
  $\sum^m_{j=1}(m_{ij} = -1) = d^-(v_i) \textcolor{orange}{(入度)}$
3. $\sum^n_{i=1}\sum^m_{j=1}(m_{ij}=1) = \sum^n_{i=1}\sum^m_{j=1}(m_{ij}=-1) = m$
4. 平行边在关系矩阵中的列相同

14.4.3 有向图的邻接矩阵 A¶

定义：设有向图 D=
, V={v₁, v₂, …, v_n}, E={e₁, e₂, …, e_m}, 令$a^{(1)}_{ij}$为顶点 v_i邻接到顶点 v_j边的条数，$(a^{(1)}_{ij})_{n\times n}$称为 D 的邻接矩阵, 记作A(D), 简记为A。
A(D)的性质
1. $\sum^n*{j=1}a = d^+(v_i) $ 第 i 行为 v}*{ij_i出度
2. $\sum^n*{i=1}a = d^-(v_j) $ 第 j 列为 v}*{ij_j入度
3. $\sum^n_{i=1}\sum^{n}_{j=1}a^{(1)}_{ij} = m$ D 中长度为 1 的通路数
4. $\sum^n_{i=1}a^{(1)}_{ii}$ 为 D 中长度为 1 的回路数

14.4.4 D 中长度为 l 的通路与回路数 $A^l$ *¶

$\textcolor{#66ccff}{A^l(D)}$表示$A(D)$的l 次幂，记为$A^l (l ≥2)$, $A^l(D)$的元素为$a^{(l)}_{ij} = \sum^n_{k=1}a^{\textcolor{#ee0000}{l-1}}_{ik} \cdot a^{\textcolor{#ee0000}{1}}_{kj}, A^l = (a^{(l)}_{ij})_{n\times n}$
定理：设 A 为 n 阶有向图 D 的邻接矩阵, 则$A^l(l\geq 1)$中元素 (必考)
- $a^{(1)}_{ij}$为 D 中$v_i$到$v_j$长度为 l 的通路数；
- $a^{(1)}_{ii}$为 vi 到自身长度为 l 的回路数；
- $\sum^n_{i=1}\sum^n_{j=1}a^{(1)}_{ij}$ 为 D 中长度为 l 的通路总数；
- $\sum^n_{i=1}a^{(1)}_{ii}$ 为 D 中长度为 l 的回路总数。
推论：设$B_l=A+A^2+…+A^l(l\geq 1)$, 则$B_l$中元素 $\sum^n_{i=1}\sum^n_{j=1}b^{(1)}_{ij}$为 D 中长度小于或等于 l 的通路数， $\sum^n_{i=1}b^{(1)}_{ii}$为 D 中长度小于或等于 l 的回路数。
例:有向图 D 如图所示, 求 A, A2, A3, A4, 并回答以下问题： (1) D 中长度为 1, 2, 3, 4 的通路各有多少条？其中回路分别为多少条？ (2) D 中长度小于或等于 4 的通路为多少条？其中有多少条回路？

14.4.5 有向图的可达矩阵¶

定义：设 D=为有向图, $V=\{v_1, v_2, …, v_n\}$, 令：$p_{ij}=\begin{cases}1,&v_i可达v_j\\0,&v_i不可达v_j\end{cases}$称$(p_{ij})_{n\times n}$为 D 的可达矩阵, 记作$\textcolor{#66ccff}{P(D)}$, 简记为P。

性质:
- P(D)主对角线上的元素全为 1。
- D 强连通当且仅当 P(D)的元素全为 1。

第十五章欧拉图与哈密顿图¶

15.1 欧拉图¶

15.1.1 欧拉图相关定义¶

定义:
1. 欧拉回路: 经过图中所有顶点, 且行遍每条边有且仅有一次的回路
2. 欧拉图: 具有欧拉回路的图 - 规定: 平凡图是欧拉图
3. 欧拉通路: 经过图中所有顶点, 且行遍所有边有且仅有一次的通路
4. 半欧拉图: 有欧拉通路, 但是没有欧拉回路的图
例：判断下列图中哪些是欧拉图，哪些是半欧拉图。
- (1)欧拉图 (2)半欧拉图

15.1.2 无向欧拉图的判定方法¶

无向图 G 是欧拉图 当且仅当 ①G 联通 ②==无== 奇数度顶点
无向图 G 是半欧拉图 当且仅当 ①G 联通 ②==有两个== 奇数度顶点
无向图 G 是非平凡的欧拉图 当且仅当 ①G 联通 ② 为若干个==边不重合== 的圈的并
- 图(1)可以看作$ (边 e_5 构成的圈)\cup (边 e_1e_2e_3e_4 构成的圈)$
$\stackrel{拆成3个圈}\longrightarrow$

15.1.3 欧拉回路的构造 - Fleury 算法¶

任取$v_0\in V(G)$, 令$P_0 = v_0$
设$P_i= v_0e_1v_1e_2...e_iv_i$已经行遍, 按照下面的操作从$E(G) - \{e_1, e_2,...e,i\}$中选取$e_{i+1}$
1. $e_{i+1}与v_i$相关联
2. 除非无变得边可行, 否则$e_{i+1}$不应该为$G_i = G-\{e_1,e_2,...,e_i\}$ 中的桥避桥不走
当 2 不能继续进行时, 算法停止

15.1.4 有向欧拉图的判别方式¶

定理：有向图 D 是欧拉图 当且仅当 D 是强连通的且每个顶点的==入度都等于出度== 。
定理：有向图 D 是半欧拉图 当且仅当 D 是==单向连通== 的且恰有==两个奇度顶点== , 其中一个入度比出度大 1, 另一个出度比入度大 1, 其余顶点的入度等于出度。

15.2 哈密顿图¶

15.2.1 哈密顿图相关概念¶

定义
- 哈密顿通路: 经过图中所有顶点一次且仅一次的通路
- 哈密顿回路: 经过图中所有顶点一次且仅一次的回路
- 哈密顿图: 具有哈密顿回路的图
- 半哈密顿图: 具有哈密顿通路但不具有哈密顿回路的图
- 与欧拉图相比, 哈密顿对经过边的次数没有要求
几点说明
- 平凡图是哈密顿图
- 哈密顿通路是初级通路, 哈密顿回路是初级回路
- 环与平行边不影响图的哈密顿性

15.2.2 无向哈密顿图的一个必要条件¶

无向哈密顿图的必要条件 (证明不是哈密顿图)
- 定理 : 设无向图 G=是哈密顿图, 则对于任意$V_1\subset V且V_1\neq \empty\ \(均有$p(G-V_1)\leq \textcolor{#ee0000}{|V_1|}\)
- 推论 : 设无向图 G=是半哈密顿图, 则对于任意$V_1\subset V且V_1\neq \empty\ \(均有$p(G-V_1)\leq \textcolor{#ee0000}{|V_1| + 1}\)
- 可利用该定理判断某些图不是哈密顿图；
对于二部图$G = <V_1, V_2, E>, 2\leq|V_1|\leq |V_2|$
- G 是哈密顿图,则$\textcolor{#ee0000}{|V_1|=|V_2|}$ ;
- 若$\textcolor{#ee0000}{|V_2|\geq |V_1| + 2}$，则 G 不是哈密顿图也不是半哈密顿图。
例：证明下面的图(1)和图(2)都不是哈密顿图。
- 令$V_1 = \{v_1, v_4\}, |V_1| = 2, p(G-V_1) = 3;\ p(G-V_1)>|V_1|,不满足 p(G-V_1)\leq |V_1|$ 所以图(1)不是哈密顿图
- 令$V_2 = \{v\} 则p(G-V_2) = 2, |V_2|=1;\ p(G-V_1)>|V_2|,\ 不满足 p(G-V_2)\leq |V_2|$ 所以图(2)不是哈密顿图
例：设 G 为 n 阶无向连通简单图, 若 G 中有割点或桥，则 G 不是哈密顿图。
- 设 v 为 G 的割点, $p(G-v)\geq2\ >\ |\{v\}| = 1$ 根据哈密顿图的必要条件得, G 不是哈密顿图
- 若 G 是 K₂(K₂有桥), 它显然不是哈密顿图. 除 K₂外, 其他的有桥连通图均有割点. 由(1), 得证 G 不是哈密顿图。

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

无向哈密顿图的充分条件 (证明是哈密顿图)
- 定理 : 设 G 是 n 阶无向简单图, 若任意两个不相邻的顶点的度数之和$\textcolor{#ee0000}{\geq n-1}$, 则 G 中存在哈密顿通路。
- 推论 : 若$n (n\geq3)$阶无向简单图 G 中任意两个不相邻的顶点的度数之和$\textcolor{#ee0000}{\geq n}$, 则 G 是哈密顿图。
- 推论 : 设 G 是$n (n\geq3)$阶无向简单图，若 G 的最小度$\textcolor{#ee0000}{\geq\frac n2}$, 则 G 是哈密顿图。
- 由推论可知，当$n\geq 3$时, K_n都是哈密顿图。
- 当$r=s\geq 2$时，完全二部图$K_{r,s}$是哈密顿图。
例:某次国际会议 8 人参加，已知每人至少与其余 7 人中的 4 人有共同语言，

问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？
- 人 → 顶点有共同语言 → 有边圆桌, 两边能交谈 → 哈密顿回路
- 作无向图 G=, $V=\{v|v为与会者\}$，$E=\{(u,v) | u,v\in V, u与v有共同语言, 且u\neq v\}$。G 为简单图。
  
  由已知条件得： $\forall v\in V, d(v)\geq4$，所以，$\forall u,v\in V, 有d(u)+d(v)\geq8$，由定理可知 G 为哈密顿图。
  
  服务员在 G 中找一条哈密顿回路 C，按 C 中相邻关系安排座位即可。

第十六章树¶

注意：本章中所讨论的回路均指简单回路或初级回路。

16.1 无向树及其性质¶

16.1.1 无向树的定义¶

无向树 ( 简称树,T) : 连通无回路的无向图。
树叶: 树中度数为 1 的顶点(悬挂点)。
分支点: 树中度数$\geq 2$的顶点。
森林: 每个连通分支都是树的非连通的无向图。
平凡树: 平凡图。

16.1.2 无向树的性质¶

定理：设 G=是 n 阶 m 条边的无向图，则下面各命题是==等价== 的：
1. G 是树 (连通无回路);
2. G 中任意两个顶点之间存在惟一的路径;
3. G 中无回路且$m=n-1$;
4. G 是连通的且$m=n-1$;
5. G 是连通的且 G 中任何边均为桥;
6. G 中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈。
定理：设 T 是 n 阶非平凡的无向树，则 T 中至少有两片树叶。
例: 无向树 T 有 5 片树叶, 2 度与 3 度顶点各 1 个,其余顶点的度数均为 4。

求 T 的阶数 n，并画出满足要求的所有非同构的无向树。
- 设 T 的阶数为 n, 则边数为 n-1, 4 度顶点的个数为 n-7。
- 由握手定理得：$2m=2(n-1)=5\times 1+2\times 1+3\times 1+4(n-7)$
- 解得：n=8。所以 4 度顶点为 1 个。
- T 的度数列为(1,1,1,1,1,2,3,4)。有 3 棵非同构的无向树。

16.2 生成树¶

16.2.1 生成树的相关概念¶

设 G 为无向连通图
- G 的生成树 $T$ : G 的生成子图并且是树
- 生成树 T 的树枝 : G 在 T 中的边
- 生成树 T 的弦 : G 不在 T 中的边；
- 生成树 T 的余树 : 所有弦构成的集合的导出子图，记作$\overline{T}$ 。
- 黑边构成图 G 的生成树,红边构成余树
- 余树不一定连通，余树中有可能含有回路。

16.2.2 生成树的存在性及其性质¶

定理：无向图 G 有生成树当且仅当 G 连通
推论 1：设 n 阶无向连通图有 m 条边, 则 $m\geq n-1$
推论 2：设 n 阶无向连通图有 m 条边, 则它的生成树的余树有$m-n+1$条边
推论 3：设 $\overline T$ 为 G 的生成树 T 的余树，C 为 G 中任意一个圈，则 C 与 $\overline T$ 一定有公共边

16.2.3 最小生成树¶

定义：设无向连通带权图 G=, T 是 G 的一棵生成树。T 的各边权之和称为 T 的权，记作W(T)。G 的所有生成树中权最小的生成树称作 G 的最小生成树。

16.3 根树及其应用¶

16.3.1 有向树的相关概念¶

有向树: 基图为无向树的有向图。
根树: 有一个顶点入度为 0, 其余的入度均为 1 的非平凡的有向树。
树根: 有向树中入度为 0 的顶点。
树叶: 有向树中入度为 1, 出度为 0 的顶点。
内点: 有向树中入度为 1, 出度大于 0 的顶点。分支点: 树根与内点的总称。
顶点 v 的层数: 从树根到 v 的通路长度。树高: 有向树中顶点的最大层数。

16.3.2 家族树、根子树、有序树¶

定义：把根树看作一棵家族树:
- 若顶点 a 邻接到顶点 b, 称 b 是 a 的儿子, a 是 b 的父亲;
- 若 b 和 c 为同一个顶点的儿子, 称 b 和 c 是兄弟;
- 若 ab 且 a 可达 b,称 a 是 b 的祖先,b 是 a 的后代。
r 叉树 : 根树的每个分支点至多有 r 个儿子 r 叉正则树 : 根树的每个分支点
恰有 r 个儿子 r 叉完全正则树 : 每个树叶的层数都等于树高的 r 叉正则树

16.3.3 最优二叉树¶

定义：设 2 叉树 T 有 t 片树叶$v_1, v_2, …, v_t$, 树叶的权分别为$w_1, w_2, …, w_t$ , 称$W(T) = \sum^t_{i=1}w_i l(v_i)$为树 T 的权, 其中$l(v_i)$是$v_i$的层数
定义：在所有有 t 片树叶, 带权$w_1, w_2, …, w_t$ 的 2 叉树中, 权最小的 2 叉树称为最优 2 叉树(哈夫曼树)
求最优二叉树算法 Huffman 算法
- 给定实数 w1, w2, …, wt , 且 w1≤ w2 ≤…≤ wt
1. 连接权为 w1, w2 的两片树叶，得到一个分支点，其权为 w1+w2;
2. 在中选两个最小的权，连接它们对应的顶点，得到新的分支点及所带的权；
3. 重复 2，直到形成 t 片树叶为止。

第十七章平面图¶

17.1 平面图的基本概念¶

17.1.1 平面图和平面嵌入¶

定义：如果能将图 G 除顶点外，边不相交地画在平面上, 则称 G 是平面图。
- 这个画出的无边相交的图称作 G 的平面嵌入。
- 没有平面嵌入的图称作非平面图。
例：下面 5 幅图哪些是平面图？
- (1)~(4)是平面图
- (2)是(1)的平面嵌入，(4)是(3)的平面嵌入。
- (5)是非平面图。
定理：设$G'\subseteq G$, 若 G 为平面图, 则 G' 也是平面图。
- 由定理可知$K_n(n≤4), K_{2,n}(n\geq1)$都是平面图。
定理：设$G'\subseteq G$,若 G’ 为非平面图, 则 G 也是非平面图。
- $K_5$和$K_{3,3}$都是是非平面图。
  
  所以，由定理可知$K_n(n\geq5), K_{3,n}(n\geq3)$都是非平面图。
定理：平行边与环不影响图的平面性。

17.1.2 平面图的面与次数¶

定义：设 G 是一个平面图(且已经是平面嵌入)
- G 的面：G 的边将平面划分成的每一个区域；
- 无限面(外部面): 面积无限的面, 用$R_0$表示；
- 有限面(内部面): 面积有限的面, 用$\textcolor{#66ccff}{R_1, R_2,…, R_k}$表示；
- 面$R_i$的边界: 包围$R_i$的所有边构成的回路组；面$R_i$的次数: $R_i$边界的长度，用$\textcolor{#66ccff}{deg(R_i)}$表示。
例：下图有几个面？分别写出各面的边界与次数。
- R1 的边界为 a；R2 的边界为 b c e；R3 的边界为 f g；R0 的边界为d e a b c d和 f g 共同构成。
- deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8
- R1 的边界为 a c d b；deg(R1)= 4; R2 的边界为 g e f；deg(R2)=3;
- R3 的边界为 h；deg(R3)=1; R4 的边界为 l j k； deg(R4)=3
- R0 的边界为 a c d g f e b 和 k l i h i j 共同构成。 deg(R0)=13
定理：平面图各面的次数之和等于边数的 2 倍。

17.1.3 极大平面图¶

定义：若 G 是简单平面图, 并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图, 则称 G 为极大平面图。
定理：设 G 是大于等于 3 阶的简单连通平面图，G 为极大平面图的充要条件是 G 的每个面的次数均为 3。
例：证明下面的图是极大平面图
- 由该图的一个平面嵌入可得：每个面的次数均为 3，所以该平面图是极大平面图。

17.1.4 极小非平面图¶

定义：若 G 是非平面图, 并且任意删除一条边所得图都是平面图, 则称 G 为极小非平面图。
- $K_{3,3}$是极小非平面图

17.2 欧拉公式¶

定理 (欧拉公式)：设 G 为 n 阶 m 条边 r 个面的连通平面图，则 $\textcolor{#66ccff}{n-m+r=2}$。
例：证明：具有 6 个顶点、12 条边的连通简单平面图，它的每个面都是由三条边围成的。
- 设该图有 r 个面，由欧拉定理得： r = 2-n+m= 2-6+12 = 8
- 因为是简单图，所以每个面至少由 3 条边围成。又因为平面图各面的次数之和等于边数的 2 倍。即，各面次数之和为 24。
- 所以每个面只能由三条边围成。
欧拉公式的推广：设 G 是有 p ($p\geq2$) 个连通分支的平面图, 则：$\textcolor{#66ccff}{n - m + r = p + 1}$
- n=9, m=9, r =4 连通分支 p=3 $n- m+ r =4= p+1$

并(\(\cup\))运算的性质	交(\(\cap\))运算的性质
\(A\cup A = A\)	\(A\cap A = A\)
\(A \cup \emptyset = A\)	\(A \cap \empty = \empty\)
\(A\cup E = E\)	\(A\cap E = A\)
\((A\cup B)\cup C = A\cup(B\cup C)\)	\((A\cap B)\cap C = A\cap(B\cap C)\)
\(A\cup B = B\cup A\)	\(A\cap B = B\cap A\)

	\(\cup\)	\(\cap\)	\(\oplus\)
交换	\(A\cup B = B\cup A\)	\(A\cap B = B\cap A\)	\(A\oplus B = B\oplus A\)
结合	\((A\cup B)\cup C = A\cup(B\cup C)\)	\((A\cap B)\cap C = A\cap(B\cap C)\)	\(A\oplus (B \oplus C) = (A\oplus B) \oplus C\)
幂等律	\(A\cup A = A\)	\(A\cap A = A\)	\(A\oplus A = \empty\)

运算律符号	\(\empty\)	E
补元律	\(A\cap\sim A = \empty\) (矛盾律)	\(A\cup\sim A = E\)(排中律)
零律	\(A\cap \empty = \empty\)	\(A\cup E=E\)
同一律	\(A\cup \empty = A\)	\(A\cap E=A\)
否定	\(\sim\empty = E\)	\(\sim E = \empty\)

定律	定律名	理解
\(A\Rightarrow (A\lor B), B\Rightarrow (A\lor B)\)	附加律	\(A=1时,A\lor B=1\)
\(A\land B\Rightarrow A, A\land B\Rightarrow B\)	化简律	\(A\land B=1, A=1, B=1\)
\((A\rightarrow B)\land A\Rightarrow B\)	假言推理
\((A\rightarrow B)\land \lnot B \Rightarrow \lnot A\)	拒取式
\((A\lor B)\land \lnot B\Rightarrow A\)	析取三段论
\((A\rightarrow B)\land (B\rightarrow C)\Rightarrow (A\rightarrow C)\)	假言三段论	蕴涵可以传递
\((A\leftrightarrow B)\land (B\leftrightarrow C)\Rightarrow (A\leftrightarrow C)\)	等价三段论	等价可以传递
\((A\rightarrow B)\land(C\rightarrow D)\land(A\lor C)\Rightarrow (B\lor D)\)	构造性二难	两个蕴涵 \(\land\) 前键的或\(\Rightarrow\) 后键的或
\((A\rightarrow B)\land(\lnot A\rightarrow B)\Rightarrow B\)	构造性二难(特殊形式)	\(C=\lnot A, D=B\) 感觉没什么用
\((A\rightarrow B)\land(C\rightarrow D)\land(\lnot B\lor \lnot D)\Rightarrow (\lnot A\lor \lnot C)\)	破坏性二难	二蕴涵 \(\land\) 后键的非的或\(\Rightarrow\) 前键的非的或

证明:	公式
① \(q\)	结论否定引入
② \(r \rightarrow s\)	前提引入
③ \(\lnot s\)	前提引入
④ $ \lnot r$	②③ 拒取式
⑤ \(\lnot(p\land q)\lor r\)	前提引入
⑥ \(\lnot(p\land q)\)	④⑤ 析取三段论
⑦ \(\lnot p \lor \lnot q\)	⑥ 置换
⑧ \(\lnot p\)	①⑦ 析取三段论
⑨ \(p\)	前提引入
⑩ \(\lnot p \land p\)	⑧⑨ 合取

算式	markdown	描述
\(\emptyset\) Ø \(\varnothing\)	`\emptyset` `\empty` 或者复制"Ø" / `\varnothing`	空集
∈	`\in`	属于
\(\ni\)	`\ni`
\(\notin\)	`\notin`	不属于
⊂	`\subset`	离散数学中是真子集
⊃	`\supset`
\(\not\subset\) ⊈	`\not\subset` 或者复制 "⊈"	非子集
\(\subseteq\)	`\subseteq`	真子集离散数学中是子集
⊇	`\supseteq`
\(\cup\)	`\cup` 或 ∪	并集
\(\bigcup\)	`\bigcup`	并集
\(\cap\)	`\cap`	交集
\(\bigcap\)	`\bigcap`	交集
\(\uplus\)	`\uplus`	多重集
\(\biguplus\)	`\biguplus`	多重集
⊏	`\sqsubset`
⊐	`\sqsupset`
⊓	`\sqcap`
⊑	`\sqsubseteq`
⊒	`\sqsupseteq`
\(\vee\)	`\vee`
\(\wedge\)	`\wedge`
\(\setminus\)	`\setminus`	集合中的减法
\(\circ\)	`\circ`	二元关系复合运算
↾		关系的限制
\(\preccurlyeq\)	`\preccurlyeq` / ≼	偏序关系 prec : precedence curly : 卷曲的
\(\prec\)	`\prec` / ≺
⊕

符号	常见含义
\(\oplus\)	① 集合的对称差 ②\(<Z_n, \oplus>\) 模 n 加法 ③ 异或
$x≡y mod k $	x 与 y 模 k 同余

运算律
分配	\(A\cup (B \cap C) = (A\cup B)\cap(A\cup C)\) \(A\cap(B\cup C) = (A\cap B)\cup(A\cap C)\)
吸收	\(A\cup(A\cap B)= A\qquad A\cap(A\cup B)=A\)
双重否定	\(\sim\sim A = A\)

	上界	下界	上确界	下确界
{x₂,x₃,x₄}	x₁	x₄	x₁	x₄
{x₃,x₄,x₅}	x₁ ，x₃	无	x₃	无
{x₁,x₂,x₃ }	x₁	x₄	x₁	x₄

离散数学

Part1 数理逻辑¶

第一章 命题逻辑基本概念¶

1.1 命题与联结词¶

1.1.1 命题与真值¶

1.1.2 命题符号化¶

1.1.3 复合命题及联结词¶

1.2 命题公式及其赋值¶

第二章 命题逻辑等值演算¶

2.1 等值式¶

2.1.1 等值式概念¶

2.1.2 基本等值式¶

2.2 析取范式和合取范式¶

2.2.1 合取范式&析取范式¶

2.2.2 主析取范式¶

2.2.3 主合取范式¶

2.3 联结词完备集 –¶

2.4 可满足性问题与消解法 –¶

第三章 命题逻辑的推理理论¶

3.1 推理的形式结构¶

3.1.1 推理的形式结构¶

3.1.2 推理的有效性¶

3.1.3 判断推理有效性的方法¶

3.1.4 重言蕴涵式 / 推理定律¶

3.2 自然推理系统 P¶

3.2.1 自然推理系统 P¶

3.2.2 推理规则¶

3.2.3 构造推理证明直接法¶

3.2.4 附加前提证明法¶

3.2.5 归谬法¶

第四章 一阶逻辑基本概念¶

4.1 一阶逻辑命题符号化¶

4.1.1 个体词, 谓词, 量词的概念¶

4.1.2 一阶逻辑中命题符号化¶

小结¶

4.2 一阶逻辑公式及解释¶

4.2.1 原子公式和合式公式¶

4.2.2 个体变项的自由出现与约束出现¶

4.2.3 公式的解释¶

4.2.4 公式的类型¶

第五章 一阶逻辑等值演算与推理¶

5.1 一阶逻辑等值式与置换规则¶

5.1.1 等值式的概念¶

5.1.2 基本等值式¶

5.1.3 等值演算与置换规则¶

5.2 一阶逻辑前束范式¶

5.3 一阶逻辑的推理理论¶

5.3.1 推理的形式结构¶

5.3.2 重要的推理定律¶

5.2.3 推理规则¶

5.2.4 构造推理证明¶

补充练习¶

Part2 集合论¶

常用符号¶

第六章 集合代数¶

离散数学中的常用数集和运算¶

6.1 集合的基本概念¶

6.1.1 集合的定义与表示¶

6.1.2 集合与元素间的关系¶

6.1.3 集合之间的关系¶

6.1.4 空集¶

6.1.5 全集¶

6.1.6 幂集¶

6.2 集合的运算¶

6.2.1 集合的基本运算¶

6.2.1 广义并和广义交¶

6.2.3 集合运算的优先级¶

6.2.4 包含排斥原理¶

6.3 集合恒等式 –¶

6.3.1 集合运算的算律¶

6.3.2 集合包含的证明\((X\subseteq Y)\)¶

6.3.3 集合相等的证明¶

第七章 二元关系¶

7.1 笛卡尔积和二元关系¶

7.1.1 有序对¶

7.1.2 笛卡尔积¶

7.1.3 二元关系¶

7.1.4 关系的表示¶

7.2 关系的运算¶

7.2.1 关系的定义域, 值域, 域¶

第一章命题逻辑基本概念¶

第二章命题逻辑等值演算¶

第三章命题逻辑的推理理论¶

第四章一阶逻辑基本概念¶

第五章一阶逻辑等值演算与推理¶

第六章集合代数¶

第七章二元关系¶

第八章函数¶

第九章代数系统¶

第十章群¶

第十四章图的基本概念¶