Silent-Sure

期末考试时间: 2026.01.07

为了打字方便, 用 代替 .

第六章 (I) 群、环、域

1. 半群, 幺半群.

2. 幺半群的常见例子: .

3. 群.
4. 群的常见例子: .
5. Klein 四元群.
6. 有限群与无限群. 群的阶.
7. 平凡群.
8. 交换群/Abel 群.
9. 群中元素的幂. 幂的性质.
10. 群中元素 的阶 . 若 存在, 则: (i) ; (ii) 当且仅当 .
11. 设 是群 的元素, 则方程 在 中有唯一解 , 方程 在 中有唯一解 .
12. 群的运算满足消去律.
13. 群中的唯一幂等元是 .
14. 设 为群. 若 是 的非空子集, 且 关于 的运算与单位元构成群, 则称 是 的子群, 记作 .
15. 设 为群. 若 为 的非空子集, 且 关于 的运算构成群, 则 .
    证 只需证明 , 也就是证明 . 事实上, 由 知 .
16. 子群判定定理: 设 为群, 为 的非空子集, 则 的充分必要条件是 .
17. 设 为群 的元素, 令 , 则由子群判定定理可知 . 称 为 的由 生成的子群.
18. 设 为群, 令 , 可以通过子群判定定理证明 . 称 为 的中心.
19. 设 为群 的子群, 则: (i) ; (ii) .
20. 循环群与生成元.
21. 循环群的常见例子: .
22. 若 是循环群, 则:
    (a) 若 为无限群, 则对任意两个不同的整数 , 有 .
    (b) 若 为 阶有限群, 则 且 互不相同.
23. 若 是循环群, 则:
    (a) 若 为无限群, 则只有 和 是 的生成元.
    (b) 若 为 阶有限群, 则 有 个生成元. (使用 Bezout 定理证明.)
24. 若 是循环群, 则 的子群都是循环群. ( 是无限群时显然; 否则设子群有两个元素 , 使用 Bezout 定理.)
25. 置换及其符号. 置换的乘法 (积).
26. 轮换及其符号.
27. 任何置换都可分解为若干个不交的轮换的积. (用图论证明.)
28. 全体 元置换关于置换的乘法构成群, 称为 元对称群, 记作 . 的子群称为 元置换群.
29. 陪集.
30. 设 为群 的子群, 则 的所有不同的左陪集形成 的一个划分.
31. Lagrange 定理: 若 阶有限群 是 阶有限群 的子群, 则 且 在 中的不同的左陪集的个数为 .
32. 环. 零元 , 幺元 , 负元 , 逆元 .
33. 环的常见例子: .
34. 交换环, 幺环, 无零因子环, 整环.
35. 幺环的幺元不等于零元, 除非此幺环只有一个元素.
36. 若 为环 的元素, 则 .
37. 若环 的元素个数大于 , 则 不是群.
38. 整环的常见例子: .
39. 域.
40. 若 是域, 则 和 是 Abel 群.
41. 域的常见例子: .
42. 为合数时, 不是整环; 但 为素数时, 不仅是整环, 还是域.

第六章 (II) 格与布尔代数

1. 格. 最小上界 与最大下界 .

2. 格的常见例子:

   • 设 , 是 的正因子的集合, 为整除关系, 则 是格, 其中 , .
   • 设 为一个集合, 则 是格, 其中 .
   • 是格, 其中 .
3. 格的最小上界运算 与最大下界运算 满足交换律、结合律、幂等律、吸收律.
4. 若代数系统 $(S,\,,\,\circ)\circS\preceq(S,\,\preceq)x,\,y\in Sx\land y=x*y,\,x\lor y=x\circ y$.
5. 子格.
6. 格的同构.
7. 分配格.
8. 分配格判定定理:
   (a) 格 是分配格的一个充分必要条件是 不含有与钻石格和五角格同构的子格.
   (b) 格 是分配格的一个充分必要条件是, 对任意 , 若 且 , 则 .
9. 全下界 , 全上界 . 有界格.
10. 有限格都是有界格.
11. 设 为一个集合, 则 是有界格.
12. 设 为有界格 的元素, 若 满足 , 则称 为 的补元.
13. 有补格.
14. 在分配格中, 若一个元素存在补元, 则它的补元是唯一的.
15. 布尔代数/布尔格 .
16. 布尔代数的等价定义: 代数系统 $(B,\,,\,\circ)\circ0,\,1\in Ba\in Ba1=a\circ0=aa\in Ba’\in Baa’=0,\,a\circ a’=101$ 的定义见上一项.
17. 若 为布尔代数, 则任意 满足 .

第七章 图的基本概念

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. 可达矩阵.

第八章 树

1. 树, 平凡树, 森林, 树叶, 分支点.

2. 对于 条边的 阶图 , 以下命题等价:
   (a) 为树;
   (b) 的每对顶点之间有唯一的路径;
   (c) 连通, 且 ;
   (d) 无圈, 且 ;
   (f) 连通, 且 的边均为桥;
   (e) 无圈, 且在 中任何两个不相邻的顶点之间增加一条边, 就得到圈.

3. 非平凡树至少有两片树叶.
4. 生成树, 树枝, 弦, 余树. 余树一般不是树.
5. 无向连通图都有生成树.
6. 无向连通图都满足 .
7. 基本回路, 基本回路系统.
8. 基本割集, 基本割集系统.
9. 带权图. 边的权 , 图的权 .
10. 最小生成树.
11. 有向树.
12. 若一棵非平凡的有向树, 除一个顶点入度为 外, 其余顶点入度均为 , 则称之为根树, 称入度为 的点为树根, 称出度为 的点为树叶, 称其余点为内点. 内点和树根统称分支点.
13. 层数 , 树高 .
14. 子点, 父点, 祖先, 后代.
15. 根子树.
16. 元树, 元正则树, 元完全正则树.

第九章 二部图、欧拉图、哈密顿图

1. 二部图, 互补顶点子集.

2. 完全二部图.

3. 二部图判定定理: 一个无向图是二部图的充分必要条件是它没有长度为奇数的圈.
4. 匹配. 极大匹配, 最大匹配.
5. 饱和点与非饱和点. 完美匹配.
6. 完备匹配.
7. Hall 定理: 二部图 有完备匹配的充分必要条件是对于 , 中的任意 个顶点至少与 中的 个顶点相邻.
8. 欧拉通路, 欧拉回路, 欧拉图.
9. 无向图 有欧拉通路的充分必要条件是 连通且度数为奇数的顶点不超过 个.
10. 无向图 有欧拉回路的充分必要条件是 连通且所有顶点度数均为偶数.
11. 有向图 有欧拉回路的充分必要条件是 弱连通且所有顶点都满足入度等于出度.
12. 阶有向图 有欧拉通路但无欧拉回路的充分必要条件是 弱连通且各个顶点的入度与出度之差包括一个 、一个 与 个 .
13. 哈密顿通路, 哈密顿圈, 哈密顿图.
14. 若无向图 为哈密顿图, 为 的非空真子集, 则 .
15. 若无向图 有哈密顿通路, 为 的非空真子集, 则 .
16. 设 为 阶无向简单图. 若对 中每一对不相邻的顶点 , 都有 , 则 有哈密顿通路.
17. 设 为 阶无向简单图. 若对 中每一对不相邻的顶点 , 都有 , 则 是哈密顿图.
18. 设 为 阶无向简单图. 若 , 则 为哈密顿图.

第十章 平面图及其着色

1. 平面图, 非平面图, 平面嵌入/表示.

2. 面, 无限面/外部面, 有限面/内部面. 边界, 次数 .

3. 面的次数之和等于边数的 倍.
4. 欧拉公式: 若连通平面图 有 个顶点, 条边, 个面, 则 .
5. 有 个连通分支的平面图满足 .
6. 若连通平面图 的每个面的次数都不小于 , 则 .
7. 同构, 同胚, 收缩.
8. Kuratowski 定理: 对于图 , 下列命题等价:
   (a) 是平面图;
   (b) 没有与 $K5K{3,3}GK5K{3,3}$ 的子图.
9. 平面图的对偶图.
10. (点) 着色. - 可着色, 色数 .
11. (a) 为奇数时, ; 为偶数时, .
    (b) 非空图 的色数为 的充分必要条件是 为二部图.

期中考试时间: 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. 自同态的一个典型例子是: 是 的自同态, 其同态像为 .

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

第一章 命题逻辑

1. 命题, 真值, 真命题, 假命题.
2. 将命题描述的事物替换为变量, 用来表示一系列命题, 这叫做命题变项. 命题变项不是命题. 需要凸显与命题变项相对时, 命题也称命题常项.
3. 简单命题, 复合命题, 联结词.
4. 否定 , 合取 , 析取 , 蕴涵 , 等价 . 中 为前件, 为后件.
5. 联结词的优先级: 从高到低为 .
6. 命题的符号化. 这门课里约定 “ 仅当 ” 指的是 而非 .
7. (命题) 公式. 公式的层次 (从 开始计算). 公式的解释与赋值 (成真赋值, 成假赋值).
8. 含 个命题变项的公式有 个赋值, 全部列出可得到真值表. 含 个命题变项的公式, 其真值表有 种可能.
9. 永真式 (重言式), 永假式 (矛盾式), 可满足式.
10. 等值 (). 注意 与 是不同范畴的概念.
11. 置换规则与等值演算.
12. 24 个重要等值式:
    1. 双重否定律.
    2. 等幂律, 交换律, 结合律, 分配律.
    3. 德摩根律, 吸收律.
    4. 零律, 同一律, 排中律, 矛盾律.
    5. 蕴涵等值式, 等价等值式, 假言易位, 等价否定等值式.
    6. 归谬论.
13. 涉及蕴涵的几个等值式:
    1. .
    2. .
    3. .
    4. .
14. 文字, 简单析取式, 简单合取式, 析取范式, 合取范式.
15. 范式存在定理: 任一命题公式都存在与之等值的析取范式和合取范式. 事实上, 只需进行三个步骤:
    1. 消去除 外的联结词.
    2. 利用 , 内移或消去否定联结词.
    3. 利用 对 的分配律求析取范式, 利用 对 的分配律求合取范式.
16. 极小项及其记号. 主析取范式.

17. 主析取范式存在唯一定理. 任何命题公式均存在主析取范式, 且主析取范式唯一.

    唯一性显然. 存在性的证明方式是把简单合取式都扩充成若干极小项 (这就是主析取范式的构造方法).

18. 极大项及其记号, 主合取范式.
19. 主合取范式也满足存在性和唯一性. 事实上, 主合取范式的各个极大项的出现的下标就是主析取范式各个极小项中没有出现的下标.
20. 联结词完备集. 显然 是一个联结词完备集.
21. 都是联结词完备集.
22. 与非 , 或非 .
23. 都是联结词完备集. 事实上, $$p\uparrow p\Leftrightarrow\neg p\Leftrightarrow p\downarrow p,\\(p\uparrow q)\uparrow(p\uparrow q)\Leftrightarrow p\land q\Leftrightarrow (p\downarrow p)\downarrow(q\downarrow q),\\ (p\uparrow p)\uparrow(q\uparrow q)\Leftrightarrow p\lor q\Leftrightarrow(p\downarrow q)\downarrow(p\downarrow q).$$
24. 推理及其形式结构. 前提与结论. 推理的正确性.
25. 推出 (). 注意 与 是不同范畴的概念.
26. 8 条推理定律:
    1. 附加
    2. 化简
    3. 假言推理
    4. 拒取式
    5. 析取三段论
    6. 假言三段论
    7. 等价三段论
    8. 构造性二难
27. 推理规则: 前提引入, 结论引入, 合取引入, 推理定律.
28. 推理的证明.
29. 附加前提证明法与归谬法.