1. 集合论基础

1.1 集合的基本概念

整数集： $\mathbb{Z}$
基数：集合 $A$ 中元素的个数称为 $A$ 的基数，记作 $|A|$
集合的表示方法：
- 枚举法
- 描述法
- 递归定义法
空集：

\emptyset=\{x\mid x\ne x\}

空集是唯一的，并且：

|\emptyset|=0,\qquad |\{\emptyset\}|=1

全集：通常记作 $U$ ，相对于所讨论的问题而定
集合元素的特性：
- 无序性
- 互异性

例如：

\{a\}=\{a,a\}

外延公理（外延性原理）：若两个集合包含完全相同的元素，则这两个集合相等

1.2 包含与幂集

子集：

A\subseteq B

真子集：

A\subset B

幂集：

P(A)=\{X\mid X\subseteq A\}

满足：

X\in P(A)\iff X\subseteq A

若 $|A|=n$ ，则：

|P(A)|=2^n

1.3 集合的基本运算

（1）差集

A-B=A\setminus B=\{x\mid x\in A\land x\notin B\}

（2）对称差

A\oplus B=(A-B)\cup(B-A)=A\Delta B

性质：

A\oplus A=\emptyset

A\oplus \emptyset=A

（3）补集

相对于全集 $U$ ，集合 $A$ 的补集记为：

A^c,\quad A',\quad C_UA

（4）分配律

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

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

（5）吸收律

A\cup(A\cap B)=A

A\cap(A\cup B)=A

2. 可数集合与计数问题

2.1 可数集合

一个集合若能与自然数集 $\mathbb{N}$ 建立一一对应，则称为可数集。

有限集是可数的
$\mathbb{N}$ 、 $\mathbb{Z}$ 、 $\mathbb{Q}$ 都是可数集
实数区间 $(0,1)$ 是不可数集

2.2 $\mathbb{Z}$ 是可数集

可构造 $\mathbb{N}$ 与 $\mathbb{Z}$ 的一一对应，例如：

$\mathbb{N}$ 中元素	0	1	2	3	4	5	6	…
对应的整数	0	1	-1	2	-2	3	-3	…

因此 $\mathbb{Z}$ 可数。

2.3 不可数集合

区间 $(0,1)$ 的基数通常记为连续统基数 $c$ 。凡与 $(0,1)$ 等势的集合都是不可数集。

原稿中把 $c$ 说成“阿列夫”不准确。 $\aleph_0$ 通常表示可数无限集的基数； $(0,1)$ 的基数通常记为 $c$ 。

2.4 计数问题

（1）排列与组合

排列数：

P(n,r)=\frac{n!}{(n-r)!}

组合数：

C(n,r)=\frac{n!}{r!(n-r)!}

可重复组合数：

C(n+r-1,r)

（2）容斥原理

对于三个集合：

|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|

（3）鸽笼原理

若把 $m$ 只鸽子放入 $n$ 个笼子，则至少有一个笼子中鸽子数不少于

\left\lceil \frac{m}{n}\right\rceil

也可写为：

\left\lfloor \frac{m-1}{n}\right\rfloor+1

3. 命题逻辑

3.1 命题与联结词

1. 命题

命题是具有确定真值的陈述句。

例如：

“ $2+3=5$ ”是命题
“ $x+y>0$ ”若未说明 $x,y$ 的取值范围，则不是命题

2. 逻辑联结词

否定： $\neg P$
合取： $P\land Q$
析取： $P\lor Q$
蕴含： $P\to Q$
等价： $P\leftrightarrow Q$

其中：

$P\to Q$ 只有在 $P$ 真而 $Q$ 假时为假
$P\leftrightarrow Q$ 当且仅当 $P,Q$ 同真同假时为真

3.2 常见语言到逻辑公式的转换

“只有 $A$ 才 $B$ ”：

B\to A

“只要 $A$ 就 $B$ ”：

A\to B

“如果 $A$ ，那么 $B$ ”：

A\to B

“除非 $A$ ，否则不 $B$ ”：

B\to A

3.3 逻辑等价

两个命题公式 $G,H$ 若在所有赋值下真值都相同，则称它们逻辑等价，记为：

G\equiv H

等价地，

G\leftrightarrow H

是永真式。

常见等价式

A\to B \equiv \neg A\lor B

A\leftrightarrow B \equiv (A\to B)\land(B\to A)

吸收律：

G\lor(G\land H)\equiv G

G\land(G\lor H)\equiv G

归谬式：

(G\to H)\land(G\to \neg H)\equiv \neg G

3.4 范式

1. 基本术语

文字：命题变元或其否定
子句：有限个文字的析取
短语（项）：有限个文字的合取

2. 析取范式（DNF）

若公式写成若干合取式的析取，则称为析取范式。

3. 合取范式（CNF）

若公式写成若干析取式的合取，则称为合取范式。

要求否定号只出现在命题变元前面。

3.5 主析取范式与主合取范式

1. 极小项

对 $n$ 个命题变元，每个极小项是每个变元或其否定的合取，并且每个极小项对应唯一一组真值赋值。

2. 极大项

每个极大项是每个变元或其否定的析取，并且每个极大项对应唯一一组使它为假的赋值。

3. 性质

不同极小项不可能同时为真
所有极小项的析取恒为真
所有极大项的合取恒为假

4. 真值表法

主析取范式：把公式值为 1 的各行对应极小项相析取
主合取范式：把公式值为 0 的各行对应极大项相合取

4. 命题逻辑的推理

4.1 基本推理形式

（1）附加规则

P \Rightarrow P\lor Q

Q \Rightarrow P\lor Q

（2）假言推理（Modus Ponens）

P,\ P\to Q \Rightarrow Q

（3）拒取式（Modus Tollens）

\neg Q,\ P\to Q \Rightarrow \neg P

（4）假言三段论

P\to Q,\ Q\to R \Rightarrow P\to R

（5）析取三段论

P\lor Q,\ \neg P \Rightarrow Q

4.2 证明中的常用规则

P：前提引用
T：由逻辑等价或推理规则得到
CP：附加前提规则（条件证明）

5. 谓词逻辑

5.1 基本概念

命题逻辑把原子命题看作不可再分，而谓词逻辑进一步分析命题内部结构。

1. 个体域（论域）

讨论对象的集合称为个体域，记作 $D$ 。

2. 个体词

能独立表示对象的符号，如常量、变量。

3. 谓词

表示对象性质或对象间关系的符号。

一元谓词：刻画性质
二元及以上谓词：刻画关系

4. 量词

全称量词： $\forall x$
存在量词： $\exists x$

例如：

“所有老虎都吃人”可表示为：

(\forall x)(T(x)\to P(x))

“有些人登上过月球”可表示为：

(\exists x)(H(x)\land R(x))

5.2 量词的直观理解

若个体域有限：

(\forall x)G(x)\equiv G(x_1)\land G(x_2)\land \cdots \land G(x_n)

(\exists x)G(x)\equiv G(x_1)\lor G(x_2)\lor \cdots \lor G(x_n)

5.3 谓词符号化常见错误

例如：

(\forall x)(\exists y)(F(x)\land F(y)\to G(x,y))

通常不能正确表达“对每个满足 $F$ 的 $x$ ，存在某个满足 $F$ 的 $y$ 使得 $G(x,y)$ 成立”。

更准确的写法应是：

(\forall x)\bigl(F(x)\to (\exists y)(F(y)\land G(x,y))\bigr)

5.4 谓词公式与自由变元

1. 项

项包括：

常量
变量
函数项

2. 原子公式

若 $P$ 是 $n$ 元谓词， $t_1,\dots,t_n$ 是项，则

P(t_1,\dots,t_n)

是原子公式。

3. 闭式

不含自由出现个体变元的公式称为闭式。

4. 可满足、有效、矛盾

有效公式：永真
矛盾公式：永假
可满足公式：至少在某个解释下为真

5.5 前束范式

前束范式的一般形式为：

(Q_1x_1)(Q_2x_2)\cdots(Q_nx_n)\,M(x_1,x_2,\dots,x_n)

其中：

$Q_i$ 是量词
$M$ 是不含量词的母式

整理前束范式时，应先处理否定、蕴含与等价，再把量词前移，并注意变元改名，防止自由变元被约束。

5.6 量词推理规则

（1）全称特指规则（US）

(\forall x)G(x)\Rightarrow G(c)

其中 $c$ 是任意个体常量。

（2）存在特指规则（ES）

(\exists x)G(x)\Rightarrow G(c)

其中 $c$ 是新引入的特指常量。

（3）全称推广（UG）

由 $G(x)$ 推出 $(\forall x)G(x)$ 需满足一定限制条件。

（4）存在推广（EG）

由 $G(c)$ 可推出：

(\exists x)G(x)

6. 二元关系

6.1 关系的定义

若 $A,B$ 是两个集合，则 $A\times B$ 的任意子集称为从 $A$ 到 $B$ 的一个二元关系。

若 $A=B$ ，则称为 $A$ 上的一个二元关系。

6.2 特殊关系

空关系：

R=\emptyset

全关系：

R=A\times B

恒等关系（在 $A$ 上）：

I_A=\{\langle x,x\rangle\mid x\in A\}

若 $|A|=n, |B|=m$ ，则 $A\times B$ 上关系总数为：

2^{nm}

6.3 定义域、值域与域

对关系 $R\subseteq A\times B$ ：

定义域：

\operatorname{dom}(R)=\{a\in A\mid \exists b\in B,\ \langle a,b\rangle\in R\}

值域：

\operatorname{ran}(R)=\{b\in B\mid \exists a\in A,\ \langle a,b\rangle\in R\}

域：

\operatorname{field}(R)=\operatorname{dom}(R)\cup \operatorname{ran}(R)

6.4 关系的表示

枚举法
描述法
关系图
矩阵表示

若 $A=\{a_1,\dots,a_n\}$ ， $B=\{b_1,\dots,b_m\}$ ，关系 $R\subseteq A\times B$ 的布尔矩阵为：

M_R=(m_{ij})_{n\times m}

其中：

m_{ij}= \begin{cases} 1,& \langle a_i,b_j\rangle\in R\\ 0,& \langle a_i,b_j\rangle\notin R \end{cases}

6.5 关系的运算

（1）并、交、差

对应布尔矩阵有：

M_{R\cup S}=M_R\lor M_S

M_{R\cap S}=M_R\land M_S

M_{R-S}=M_R\land \overline{M_S}

（2）逆关系

R^{-1}=\{\langle b,a\rangle\mid \langle a,b\rangle\in R\}

矩阵上对应为转置：

M_{R^{-1}}=(M_R)^T

原稿里写成 $1-M_R$ 是错误的。 $1-M_R$ 对应的是补关系，不是逆关系。

（3）关系复合

若 $R\subseteq A\times B$ ， $S\subseteq B\times C$ ，则

R\circ S=\{\langle x,z\rangle\mid \exists y\in B,\ xRy\land ySz\}

矩阵表示对应布尔乘积。

（4）幂关系

若 $R$ 是集合 $A$ 上的关系，则

R^0=I_A,\qquad R^1=R,\qquad R^{m+n}=R^m\circ R^n

6.6 关系运算的性质

(R\circ S)\circ T = R\circ (S\circ T)

R\circ I_A = R = I_B\circ R

(R\circ S)^{-1}=S^{-1}\circ R^{-1}

并且可证明：

(R\cup S)^{-1}=R^{-1}\cup S^{-1}

7. 关系的性质

7.1 基本性质

设 $R$ 是集合 $A$ 上的关系。

（1）自反

\forall x\in A,\ \langle x,x\rangle\in R

等价于：

I_A\subseteq R

（2）反自反

\forall x\in A,\ \langle x,x\rangle\notin R

等价于：

I_A\cap R=\emptyset

（3）对称

\langle x,y\rangle\in R \Rightarrow \langle y,x\rangle\in R

等价于：

R=R^{-1}

（4）反对称

\langle x,y\rangle\in R \land \langle y,x\rangle\in R \Rightarrow x=y

等价判定是：

R\cap R^{-1}\subseteq I_A

原稿把反对称写成 $R\cap R^{-1}=\emptyset$ ，这是错误的，因为自反关系的对角元本来就在交集中。

（5）传递

\langle x,y\rangle\in R \land \langle y,z\rangle\in R \Rightarrow \langle x,z\rangle\in R

等价于：

R\circ R\subseteq R

8. 等价关系与商集

8.1 等价关系

若关系同时满足：

自反
对称
传递

则称其为等价关系。

例如整数集上的模 $n$ 同余关系：

x\equiv y\pmod n

是等价关系。

8.2 等价类

在等价关系 $R$ 下，元素 $x$ 的等价类定义为：

[x]_R=\{y\in A\mid xRy\}

性质：

对任意 $x\in A$ ， $[x]_R\ne \emptyset$
任意两个等价类要么相等，要么不相交
所有等价类的并为整个集合 $A$

8.3 商集

由所有等价类组成的集合称为商集：

A/R=\{[x]_R\mid x\in A\}

9. 关系性质的保守性

设 $R,S$ 是集合 $A$ 上的关系。

一些典型结论：

若 $R,S$ 自反，则 $R\cup S$ 、 $R\cap S$ 自反
若 $R,S$ 对称，则 $R\cup S$ 、 $R\cap S$ 、 $R^{-1}$ 对称
若 $R,S$ 传递，则 $R^{-1}$ 传递
但 $R\cup S$ 不一定保持传递性
两个等价关系的交仍是等价关系
两个等价关系的并不一定是等价关系
两个等价关系的复合不一定是等价关系

例如多选题中，若 $\alpha,\beta$ 是等价关系，则下列不一定是等价关系的是：

$\alpha\circ\beta$
$\alpha\cup\beta$

而：

$\alpha\cap\beta$
$\alpha^{-1}$

仍一定是等价关系。

10. 偏序关系

10.1 定义

若关系满足：

自反
反对称
传递

则称为偏序关系。

常记为 $\le$ ，有序对 $\langle A,\le\rangle$ 称为偏序集。

典型例子：

数的 $\le$
集合的 $\subseteq$
整除关系 $\mid$

10.2 可比与覆盖

若 $x\le y$ 或 $y\le x$ ，则称 $x,y$ 可比
若 $x<y$ 且不存在 $z$ 使得 $x<z<y$ ，则称 $y$ 覆盖 $x$

10.3 哈斯图

哈斯图由关系图简化而来：

去掉自环
去掉由传递性可推出的边
去掉箭头，默认下小上大

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

设 $B\subseteq A$ 。

最大元

若 $b\in B$ 且

\forall x\in B,\ x\le b

则 $b$ 为 $B$ 的最大元。

最小元

若 $b\in B$ 且

\forall x\in B,\ b\le x

则 $b$ 为最小元。

极大元

若 $b\in B$ 且不存在 $x\in B$ 满足 $b<x$ ，则 $b$ 为极大元。

等价写法：

\forall x\in B,\ b\le x \Rightarrow x=b

极小元

若 $b\in B$ 且不存在 $x\in B$ 满足 $x<b$ ，则 $b$ 为极小元。

等价写法：

\forall x\in B,\ x\le b \Rightarrow x=b

最大元/最小元若存在则唯一；极大元/极小元可以不唯一。

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

设 $B\subseteq A$ ， $a\in A$ 。

\forall x\in B,\ x\le a

则称 $a$ 为 $B$ 的上界。

最小上界称为上确界（sup）
若

\forall x\in B,\ a\le x

则称 $a$ 为 $B$ 的下界。

最大下界称为下确界（inf）

10.6 链与反链

链：任意两个元素都可比
反链：任意两个不同元素都不可比

11. 拟序、全序、良序与函数

11.1 拟序

若关系满足：

反自反
传递

则称为拟序（严格偏序）。

11.2 全序

若偏序集中的任意两个元素都可比，则称为全序集。

11.3 良序

在全序的基础上，若任一非空子集都有最小元，则称为良序。

11.4 函数

函数是特殊关系。设 $f:A\to B$ ，则：

单射：不同元素像不同
满射：陪域中每个元素都有原像
双射：既单又满

11.5 函数复合

若 $f:A\to B$ ， $g:B\to C$ ，则复合函数定义为：

g\circ f:A\to C,\qquad (g\circ f)(x)=g(f(x))

原稿里“左复合/右复合”写反了。标准定义是 $g\circ f=g(f(x))$ 。

11.6 逆函数

函数 $f:A\to B$ 存在逆函数 $f^{-1}:B\to A$ 的充要条件是 $f$ 为双射。

12. 图论基础

12.1 图的定义

图记作：

G=\langle V,E\rangle

其中：

$V$ ：顶点集
$E$ ：边集

按边的类型可分为：

无向图
有向图
混合图

按边和环的情况可分为：

简单图
多重图
赋权图 / 无权图

12.2 子图

子图
真子图
生成子图
导出子图

12.3 完全图与补图

完全图：任意两个不同顶点之间都有边的简单图
图 $G$ 的补图记作 $\overline G$

12.4 顶点的度

无向图

顶点 $v$ 的度记作：

\deg(v)

图的最大度、最小度分别记作：

\Delta(G),\qquad \delta(G)

有向图

入度： $\deg^-(v)$
出度： $\deg^+(v)$

12.5 握手定理

无向图中：

\sum_{v\in V}\deg(v)=2|E|

因此奇度顶点个数必为偶数。

有向图中：

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

12.6 图的同构

两个图 $G,G'$ 同构，记作：

G\cong G'

若存在顶点之间的双射，使得邻接关系保持不变。

判断图同构时，可比较：

顶点数
边数
度数序列
连通性
回路结构等

13. 图的矩阵与通路

13.1 邻接矩阵

设图的邻接矩阵为：

A=(a_{ij})_{n\times n}

则：

$a_{ij}$ 表示 $v_i$ 与 $v_j$ 是否邻接
对有向图，表示从 $v_i$ 到 $v_j$ 是否有弧

13.2 通路数

矩阵幂：

A^m=(a_{ij}^{(m)})

则 $a_{ij}^{(m)}$ 表示从 $v_i$ 到 $v_j$ 长度为 $m$ 的通路条数。

特别地：

$a_{ii}^{(m)}$ 表示长度为 $m$ 的回路数
$\sum_i a_{ii}^{(m)}$ 表示长度为 $m$ 的回路总数

13.3 可达性矩阵

若从 $v_i$ 到 $v_j$ 可达，则称 $v_i$ 可达 $v_j$ 。

布尔意义下，可达矩阵可写为：

P=I+A+A^{(2)}+\cdots +A^{(n-1)}

这里运算采用布尔加法和布尔乘法。

14. 图的连通性

14.1 无向图的连通性

连通图
连通分支

点割集与边割集

点割集：删去后使连通分支数增加的顶点集
边割集：删去后使连通分支数增加的边集

点连通度与边连通度

点连通度： $K(G)$
边连通度： $\lambda(G)$

若 $K(G)\ge k$ ，则称为 $k$ -连通图。
若 $\lambda(G)\ge k$ ，则称为 $k$ -边连通图。

14.2 有向图的连通性

弱连通
单向连通
强连通

强连通分支是极大的强连通子图。

15. 树

15.1 基本定义

树：连通且无回路的无向图
森林：每个连通分支都是树

15.2 树的等价特征

树有多个常见等价定义，例如：

连通且无回路
无回路且有 $n-1$ 条边
连通且有 $n-1$ 条边
任意两点之间有且仅有一条简单通路

15.3 根树与 $k$ 元树

根树中有根、父子、祖先后代、兄弟、叶结点等概念
每个结点儿子数至多为 $k$ 的根树称为 $k$ 元树
每个分支点恰有 $k$ 个儿子的称为满 $k$ 元树

对满 $k$ 元树有公式：

(k-1)\times \text{分支点数} = \text{叶子数} - 1

16. 欧拉图与哈密顿图

16.1 欧拉图

欧拉通路：经过每条边恰好一次的通路
欧拉回路：经过每条边恰好一次的回路

无向图中：

有欧拉回路 $\iff$ 所有顶点度数均为偶数
有欧拉通路 $\iff$ 奇度顶点数为 0 或 2

16.2 哈密顿图

哈密顿通路：经过每个顶点恰好一次的通路
哈密顿回路：经过每个顶点恰好一次的回路

常见判定条件：

必要条件之一：对任意顶点子集 $V_1$ ，若图有哈密顿回路，则
$p(G-V_1)\le |V_1|$
充分条件（Ore 条件）：对任意不相邻顶点 $u,v$ ，若
$\deg(u)+\deg(v)\ge n$
则图有哈密顿回路。

若

\deg(u)+\deg(v)\ge n-1

则常可推出存在哈密顿通路。

17. 二分图与匹配

17.1 二分图

若顶点集可划分为两个不交子集 $V_1,V_2$ ，满足每条边的两个端点分别属于 $V_1,V_2$ ，则称该图为二分图。

记作：

\langle V_1,E,V_2\rangle

17.2 完全二分图

若 $V_1$ 中每个顶点都与 $V_2$ 中每个顶点相邻，则称为完全二分图，记作：

K_{m,n}

17.3 匹配

匹配：任意两条边不共享端点
完全匹配：覆盖一侧或全部顶点的匹配
最大匹配：边数最多的匹配

判定完全匹配的重要工具是 Hall 定理。

18. 平面图

18.1 平面图定义

若无向图可画在平面上，使边除了在公共端点外不相交，则称为平面图。

18.2 欧拉公式

对连通平面图：

n-m+r=2

其中：

$n$ ：顶点数
$m$ ：边数
$r$ ：面数

18.3 推论

对于 $n\ge 3$ 的简单连通平面图：

m\le 3n-6

若图中不含长度为 3 的回路，则：

m\le 2n-4

18.4 同胚与收缩

同胚：通过反复插入或消去 2 度顶点得到
边收缩：删去边并合并其两个端点

18.5 Kuratowski 定理

图是平面图，当且仅当它不包含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。

19. 易错点整理

19.1 集合与基数

$\emptyset$ 和 $\{\emptyset\}$ 不同
$|P(A)|=2^{|A|}$

19.2 命题逻辑

$P\to Q$ 只有在 $P$ 真、 $Q$ 假时为假
$P\leftrightarrow Q$ 表示充要条件

19.3 谓词逻辑

注意自由变元与约束变元
量词移位时要防止变元冲突
“对所有存在”与“存在对所有”不可随意交换

19.4 关系

$R^{-1}$ 是逆关系，不是补关系
反对称不是 $R\cap R^{-1}=\emptyset$
传递性的矩阵判定是 $R\circ R\subseteq R$

19.5 函数

复合函数标准写法：

(g\circ f)(x)=g(f(x))

有逆函数当且仅当函数是双射

19.6 图论

握手定理：无向图总度数等于边数的 2 倍
欧拉图看“边”
哈密顿图看“点”
平面图判定重点：欧拉公式、 $K_5$ 、 $K_{3,3}$

Linked Notes

No outgoing note links.

Referenced By

No backlinks yet.

1. 集合论基础

1.1 集合的基本概念

1.2 包含与幂集

1.3 集合的基本运算

（1）差集

（2）对称差

（3）补集

（4）分配律

（5）吸收律

2. 可数集合与计数问题

2.1 可数集合

2.2 Z\mathbb{Z}Z 是可数集

2.3 不可数集合

2.4 计数问题

（1）排列与组合

（2）容斥原理

（3）鸽笼原理

3. 命题逻辑

3.1 命题与联结词

1. 命题

2. 逻辑联结词

3.2 常见语言到逻辑公式的转换

3.3 逻辑等价

常见等价式

3.4 范式

1. 基本术语

2. 析取范式（DNF）

3. 合取范式（CNF）

3.5 主析取范式与主合取范式

1. 极小项

2. 极大项

3. 性质

4. 真值表法

4. 命题逻辑的推理

4.1 基本推理形式

（1）附加规则

（2）假言推理（Modus Ponens）

（3）拒取式（Modus Tollens）

（4）假言三段论

（5）析取三段论

4.2 证明中的常用规则

5. 谓词逻辑

5.1 基本概念

1. 个体域（论域）

2. 个体词

3. 谓词

4. 量词

5.2 量词的直观理解

5.3 谓词符号化常见错误

5.4 谓词公式与自由变元

1. 项

2. 原子公式

3. 闭式

4. 可满足、有效、矛盾

5.5 前束范式

5.6 量词推理规则

（1）全称特指规则（US）

（2）存在特指规则（ES）

（3）全称推广（UG）

（4）存在推广（EG）

6. 二元关系

6.1 关系的定义

6.2 特殊关系

6.3 定义域、值域与域

6.4 关系的表示

6.5 关系的运算

（1）并、交、差

（2）逆关系

（3）关系复合

（4）幂关系

6.6 关系运算的性质

7. 关系的性质

7.1 基本性质

（1）自反

（2）反自反

（3）对称

（4）反对称

（5）传递

8. 等价关系与商集

8.1 等价关系

2.2 $\mathbb{Z}$ 是可数集

15.3 根树与 $k$ 元树