离散数学复习 (II)

期中考试时间: 2025.11.20
期末考试时间: 2026.01.07

第三章 集合的基本概念和运算

1. 集合, 元素. 这门课介绍的是朴素集合论, 不试图定义集合. 常见的集合包括 .
2. 属于 , 不属于 .
3. 表示集合的方法: 列元素法 (如 ) 与谓词表示法 (如 ).
4. 集合的元素是彼此不同的. 本书中认为 .
5. 集合的元素是无序的.

6. 子集, 包含 , 不包含 . .
   包含关系有传递性.

7. 相等 . .

8. 真子集 . .
9. 是一切集合的子集.
10. 元集. 集合的大小用 表示.
11. 幂集 . .

12. 并集 , 交集 , 相对补集 , 对称差集 :

    $$A\cup B:=\{x\,\vert\,x\in A\lor x\in B\},\\ A\cap B:=\{x\,\vert\,x\in A\land x\in B\},\\ A-B:=\{x\,\vert\,x\in A\land x\notin B\},\\ A\oplus B:=(A-B)\cap(B-A).$$

    对称差集的另一种定义是
    .
    显然, 集合的并、交、对称差运算满足交换律.

13. 集合的并运算与交运算满足结合律. 事实上,

    $$A_1\cup A_2\cup\cdots\cup A_n=\{x\,\vert\,x\in A_1\lor x\in A_2\lor\cdots\lor x\in A_n\},\\ A_1\cap A_2\cap\cdots\cap A_n=\{x\,\vert\,x\in A_1\land x\in A_2\land\cdots\land x\in A_n\}.$$

    这还可以推广到无穷多个集合的情况.

14. 针对当前的研究对象定义一个全集 , 则可定义绝对补集: 的绝对补集

    $$\text∼A:=E-A.$$

15. 文氏图.

16. 根据 与命题逻辑的等值式, 可以得到大量关于 的运算律.

17. 根据 , 由此可知 $$A\cap B\sube A,\ A\sube A\cup B,\ A-B\sube A.$$
18. 此外, 集合还有一些其他运算性质: $$A\cup B=A\Leftrightarrow B\sube A\Leftrightarrow A\cap B=B\Leftrightarrow B-A=\emptyset,\\ (A\cup B)-C=(A-C)\cup(B-C),\\ (A\oplus B)\oplus C=A\oplus(B\oplus C),\\ A\oplus\emptyset=A,\ A\oplus A=\emptyset,\\ A\oplus B=A\oplus C\Rightarrow B=C,\\ A-B=A\cap\text∼B,\\ A\sube B\Leftrightarrow\text∼B\sube\text∼A,\\ A\sube B\Leftrightarrow P(A)\sube P(B),\\ A\sube C\land B\sube C\Leftrightarrow A\cup B\sube C,\\ C\sube A\land C\sube B\Leftrightarrow C\sube A\cap B,\\ A\sube C\land B\sube D\Rightarrow A\cup B\sube C\cup D,\\ A\sube C\land B\sube D\Rightarrow A\cap B\sube C\cap D.$$
19. 容斥原理.

第四章 二元关系和函数

1. 有序对.

2. 笛卡儿积 . .

3. 笛卡尔积的性质:

   $$A\times\emptyset=\emptyset\times A=\emptyset,\\ A\times B=B\times A\Rightarrow A=\emptyset\lor B=\emptyset\lor A=B,\\ (A\times B)\times C=A\times(B\times C)\Rightarrow A=\emptyset\lor B=\emptyset\lor C=\emptyset,\\ A\times(B\cup C)=(A\times B)\cup(A\times C),\\ (B\cup C)\times A=(B\times A)\cup(C\times A),\\ A\times(B\cap C)=(A\times B)\cap(A\times C),\\ (B\cap C)\times A=(B\times A)\cap(C\times A),\\ A\sube C\land B\sube D\Rightarrow A\times B\sube C\times D.$$
4. (从 到 的) (二元) 关系.
5. 上的二元关系. 上有 个不同的二元关系.
6. 空关系 , 全域关系 , 恒等关系 .
7. 常见的关系: 小于等于关系, 整除关系, 包含关系.

8. 关系矩阵与关系图.

9. 关系的定义域 , 值域 , 域 :

   $$\operatorname{dom}R:=\{x\,\vert\,\exists y(x\,R\,y)\},\\ \operatorname{ran}R:=\{y\,\vert\,\exists x(x\,R\,y)\},\\ \operatorname{fld}R:=\operatorname{dom}R\cup\operatorname{ran}R.$$

10. 关系 的逆关系 .

11. 关系 对关系 复合 . 注意, 本书采用右复合写法.

12. 关系的一些性质: $$(R^{-1})^{-1}=R,\\ \operatorname{dom}F^{-1}=\operatorname{ran}F,\ \operatorname{ran}F^{-1}=\operatorname{dom}F,\\ (F\circ G)\circ H=F\circ(G\circ H),\\ (F\circ G)^{-1}=G^{-1}\circ F^{-1}.$$

13. 上的关系 满足 .

14. 上的关系 的 次幂 的定义是 .

15. 若 上的关系 的关系矩阵为 , 则 的关系矩阵为 用逻辑加替代普通加法计算的 次幂.
16. 关系的幂满足性质 .
17. 有限集合上的关系的各次幂必有周期.
18. 上的关系可能具有的性质:
    1. 自反性: .
    2. 反自反性: .
    3. 对称性: .
    4. 反对称性: .
    5. 传递性: .

19. 上的关系可能具有的五种性质的集合描述:

    1. 自反性: .
    2. 反自反性: .
    3. 对称性: .
    4. 反对称性: .
    5. 传递性: .

20. 关系的运算是否保持原来关系的性质:

	自反性	反自反性	对称性	反对称性	传递性
	√	√	√	√	√
	√	√	√	√	√
	√	√	√	×	×
	×	√	√	√	×
	√	×	×	×	×

---

1. 自反闭包, 对称闭包, 传递闭包.

2. 闭包存在唯一定理: 设 为 上的关系, 则:

   1. 其自反闭包 .
   2. 其对称闭包 .
   3. 其传递闭包 .
3. 设 为 上的关系, 则 $$r(s(R))=s(r(R)),\ r(t(R))=t(r(R)),\ s(t(R))=t(s(R)).$$
4. 等价关系及其记号 .
5. 为 上的等价关系, 则 关于 的等价类 $$[x]_R=\{y\,\vert\,y\in A\land x\,R\,y\}.$$

6. 关于 的商集 .

7. 划分与划分块. 注意划分块不能为空.

8. 关于 的商集是 的划分. 反过来, 给定 和 的划分 , “处于 同一划分块中” 是 上的等价关系, 且 关于此关系的商集为 . 也就是说, 一个非空集合中, 等价关系与商集一一对应.

9. 一个典型的等价关系是模 等价关系 . 这一等价关系下共有 个等价类, 即

   $$[i]=\{nt+i\,\vert\,t\in \mathbf Z\},\ i=0,\,1,\,\cdots,\,n-1,$$

   它们组成 的一个划分.

10. 偏序关系 (“小于等于”) 及其记号 .

11. 可比.

12. “小于” .
13. 全序关系.
14. 偏序集 . 常见的偏序集包括 与 $\langle P(A),\,R\sube\rangleR\sube$ 为包含关系).
15. 覆盖. 哈斯图.
16. 最小元 (“大于等于” 任何元素), 最大元 (“小于等于” 任何元素), 极小元 (不存在 “小于” 它的元素), 极大元 (不存在 “大于” 它的元素). 注意它们都是就一个定义了偏序关系的集合的子集而言的, 且都属于这个子集. 显然, 最小元和最大元若存在则唯一.
17. 上界 (“大于等于” 任何元素), 下界 (“小于等于” 任何元素), 最小上界 (上界组成的集合的最小元), 最大下界 (下界组成的集合的最大元). 它们也是就一个定义了偏序关系的集合的子集而言的, 但不一定属于这个子集.
18. 的最小元一定是 的最大下界; 的最大元一定是 的最小上界.
19. (从 到 的) 函数. 注意, 这里的 不一定是函数的值域.
20. 从 到 的函数有 个, 它们组成的集合记作 .
21. 一个集合在函数下的像. 函数的像.
22. 满射, 单射, 双射.
23. 若 为单射, 则函数 为双射.
24. 常函数, 单调递增/减函数, 严格单调递增/减函数.
25. 常见的函数:
    1. 恒等函数 .
    2. 特征函数 . 它的定义是 $$\chi_{A'}(a):=\begin{cases}1, & a\in A',\\0, &a\in A-A'.\end{cases}$$
    3. 自然映射. 设 为 上的等价关系, 函数 称为 到它关于 的商集的自然映射.
26. 函数的复合.
27. 复合运算保持函数满射/单射/双射的性质.
28. 若函数 为双射, 则 是从 到 的函数, 且为双射; 否则 不是从 到 的函数. 是函数时, 称之为 的反函数.
29. 一个双射 与其反函数 满足 $$f^{-1}\circ f=I_A,\ f\circ f^{-1}=I_B.$$

第五章 代数系统的一般概念

1. ( 上的) 二元运算及其符号. ( 上的) 一元运算及其符号. 注意, 运算的定义隐含了封闭性.

2. 运算表.

3. 二元运算可能具有的性质: 交换律, 结合律, 幂等律.
4. 幂等元.
5. 一个二元运算对另一个二元运算可能满足分配律.
6. 两个二元运算可能满足吸收律.
7. 左单位元, 右单位元, 单位元.
8. 单位元若存在则唯一.
9. 若一个运算存在左单位元和右单位元, 则左单位元等于右单位元, 从而该运算存在单位元.
10. 左零元, 右零元, 零元.
11. 零元若存在则唯一.
12. 若一个运算存在左零元和右零元, 则左零元等于右零元, 从而该运算存在零元.
13. 单位元和零元不相同, 除非定义运算的集合只有一个元素.
14. 左逆元, 右逆元, 逆元, 可逆.
15. 若二元运算 满足结合律, 且 存在关于 的逆元, 则 关于 的逆元唯一, 此时通常将逆元记作 .
16. 若二元运算 满足结合律, 若 存在关于 的左逆元和右逆元, 则这个左逆元等于这个右逆元, 从而 存在关于 的逆元.
17. 二元运算可能满足左消去律/右消去律/消去律. 注意, 若该运算存在零元, 则消去律的要求不考虑零元. 事实上, 当定义运算的集合多于一个元素时, 零元不可被消去.
18. 代数 (系统) 及其构成类型. 注意, 代数系统的定义要求集合非空.
19. 子代数.
20. 注意代数系统的表示中代数常数的意义. 两个仅有代数常数不同的代数系统是不同的代数系统. 代数常数还影响到子代数的判断. 不过, 这里有一些边缘地带, 例如, 显然不是 的子代数, 但论及 是否为 的子代数, 则见仁见智.
21. 任何一个代数系统的最大的子代数是它本身, 比它小的子代数称为真子代数.
22. 若一个代数系统的所有代数常数组成的集合对这个代数系统的所有运算封闭, 则该集合构成这个代数系统的最小的子代数. 它和这个代数系统本身都是这个代数系统的平凡子代数.
23. 子代数的一个典型例子是: 构成代数 的子代数.
24. 积代数与因子代数.
25. 积代数保持两个因子代数都具有的交换律、结合律、幂等律、单位元、零元. 然而积代数不一定保持两个因子代数都具有的消去律, 原因是积代数的一些成员不是零元, 但其第一元素或第二元素是因子代数中被豁免消去律要求的零元.
26. (代数 到代数 的) 同态 (映射).
27. 同态的一个典型例子是: 是 到 的同态, 其中 , 为模 加法.
28. 同态像.
29. 代数 在 到 的同态 下的同态像是 的子代数.
30. 设 为 到 的同态. 在 下的同态像拥有与 对应的单位元与零元, 且同态像中的运算具有与 中对应的运算相同的性质 (交换律, 结合律, 幂等律).
31. 满同态 $V1\sim\phi V2$, 单同态, 同构 $V_1\cong\phi V_2$.
32. 自同态, 自同构.
33. 自同态的一个典型例子是: 是 的自同态, 其同态像为 .