返回：0100 离散数学课程总目录 · 上一章：0113 图论应用 · 下一章：0115 半群与独异点

1、学习目标

本章进入代数结构。核心目标是把“集合 + 运算 + 公理”作为一个整体来研究：运算是否封闭、满足哪些算律、有没有单位元/零元/逆元，以及不同结构之间能否通过同态、同构、商代数联系起来。

课程主线：

1
2
3
集合 A + 运算 Ω + 常数 K + 公理
=> 代数系统
=> 子代数 / 积代数 / 同态同构 / 同余关系 / 商代数

本章最容易混的是“性质是否保持”：积代数、商代数、满同态像能保持交换、结合、幂等、分配、吸收、单位元、零元、逆元，但消去律一般不保持。

2、代数结构总图

模块 问什么 关键词
二元运算 运算结果还在集合里吗，满足哪些算律 封闭、交换、结合、幂等、消去
特异元素 有没有特殊元素 单位元、零元、幂等元、逆元
代数系统 集合和运算构成什么结构 载体、运算集、常数集、公理
子代数 子集是否继承结构 非空、封闭、含 0 元运算
积代数 两个同类型系统如何组合 笛卡儿积、按分量运算
同态同构 结构之间如何映射 保持运算、单同态、满同态、同构
同余商代数 怎样按等价类压缩结构 置换性质、同余类、自然映射

3、二元运算与封闭性

设 A 是集合，函数

1
f: A x A -> A

称为 A 上的二元运算。更一般地：

1
2
3
n 元运算：f: A^n -> A
一元运算：f: A -> A
0 元运算：常数，结果是 A 中某个固定元素

判定一个运算是不是 A 上的运算，第一步永远是封闭性：

1
2
任取 a,b in A，若 a*b 仍在 A 中，则 A 对 * 封闭。
若存在一个反例使 a*b 不在 A 中，就不是 A 上的二元运算。

常见例子：

1
2
3
4
5
Z,Q,R,C 上的 + 和 * 是二元运算。
P(B) 上的并、交、相对补、对称差是二元运算。
M_n(R) 上的矩阵加法、矩阵乘法是二元运算。
A 上所有关系 R(A) 对关系合成封闭。
A 到 A 的函数集 A^A 对函数复合封闭。

4、二元运算的算律

设 o,* 是 A 上的二元运算。

算律 判定式 备注
交换律 a o b = b o a 对所有 a,b 成立
结合律 (a o b) o c = a o (b o c) 能省括号的前提
幂等律 a o a = a 每个元素都是幂等元
消去律 a o b = a o c => b=c，右侧同理 常要排除零元
分配律 a o (b*c)=(a o b)*(a o c)，右侧同理 涉及两个运算
吸收律 a o (a*b)=a，a*(a o b)=a 通常以两个运算可交换为前提

证明/反证模板：

1
2
3
4
证明成立：任取元素，按定义展开，化到左右相等。
证明不成立：举一个具体反例即可。
参数题：把恒等式展开，比较各项系数，让恒等式对所有变量成立。
有限集题：列运算表，逐格检查。

5、特异元素

设 o 是 A 上二元运算。

1
2
3
4
5
6
7
8
9
10
11
12
单位元 e：
对任意 a in A，e o a = a o e = a

零元 theta：
对任意 a in A，theta o a = a o theta = theta

幂等元 a：
a o a = a

可逆元 x：
存在 y in A，使 x o y = y o x = e
此时 y 是 x 的逆元。

重要结论：

1
2
3
4
单位元唯一。
零元唯一。
若 |A|>1，则单位元不等于零元。
若运算可结合，则逆元唯一。

单位元、零元、逆元都必须同时验证左右两边。特别是非交换运算里，左单位元不一定自动是右单位元。

常见结构速查

结构 运算 单位元 零元 逆元
<Z,+> 加法 0 无 -x
<Q*,*> 乘法 1 无 1/x
<M_n(R),+> 矩阵加法 零矩阵 无 -X
<M_n(R),*> 矩阵乘法 单位矩阵 零矩阵 可逆矩阵才有逆
<P(B), union> 并 emptyset B 只有 emptyset 可逆
<P(B), intersection> 交 B emptyset 只有 B 可逆
<P(B), symmetric difference> 对称差 emptyset 无 每个集合自己的逆元是自己

6、判定题流程

遇到“判断是否构成代数系统、有哪些性质、求特异元素”的题，可以按这个顺序：

1
2
3
4
5
6
7
8
1. 看封闭性：不封闭，后面全部不用谈。
2. 看交换律：交换变量，比较 a*b 与 b*a。
3. 看结合律：比较 (a*b)*c 与 a*(b*c)。
4. 看幂等律：代入 a*a，看是否恒等于 a。
5. 看单位元：设 e，解 e*a=a 与 a*e=a。
6. 看零元：设 theta，解 theta*a=theta 与 a*theta=theta。
7. 看逆元：先确认单位元，再解 a*x=e 与 x*a=e。
8. 看消去律：用等式推出，或找反例。

参数题的经典模式：

1
2
3
4
5
6
7
a o b = pa + qb + r

交换律：比较 a o b 与 b o a
结合律：展开 (a o b) o c 与 a o (b o c)
幂等律：令 a o a = a
单位元：设 e，要求 a o e = a 且 e o a = a
零元：设 theta，要求 a o theta = theta 且 theta o a = theta

7、代数系统、子代数和积代数

代数系统可记为：

1
V = <A, Ω, K>

其中：

1
2
3
A：非空载体集合
Ω：A 上的运算集
K：代数常数集，可以为空，也可以是 A 的子集

也常写成：

1
V = <A, o1, o2, ..., or>

同类型与同种

1
2
同类型：运算个数相同，且对应运算的元数相同。
同种：同类型，并且满足同一组公理。

例子：

1
2
<Z,+,*>, <Q,+,*>, <R,+,*> 同类型，也通常同种。
<P(B), intersection, union> 与 <{0,1}, and, or> 同种。

子代数

设 V=<A,o1,...,or>，B 是 A 的非空子集。若 B 对 V 中所有运算都封闭，则

1
V'=<B,o1,...,or>

是 V 的子代数。

注意：

1
2
3
4
1. B 必须非空。
2. 对所有运算都要封闭。
3. 若系统里有 0 元运算/常数，也必须包含这些常数。
4. 子代数至少有平凡子代数：原系统自身，以及可能由常数集生成的平凡子代数。

例子：

1
2
<Z,+,0> 的子代数是 nZ，n in N。
<Z,+> 的子代数除了 nZ，也可能有 N、Z+ 等，因为没有常数 0 的限制。

积代数

两个同类型代数系统

1
2
V1=<A,o11,...,o1r>
V2=<B,o21,...,o2r>

的积代数是：

1
V1 x V2 = <A x B, o1,...,or>

按分量运算：

1
<a,b> oi <c,d> = <a o1i c, b o2i d>

积代数保持的性质：

1
2
交换律、结合律、幂等律、分配律、吸收律
单位元、零元、幂等元、逆元

但：

1
消去律不一定保持。

8、同态与同构

设

1
2
V1=<A,o1,...,or>
V2=<B,o1',...,or'>

是同类型代数系统。映射 f:A -> B 若对每个对应运算都满足：

1
f(oi(a1,...,ak)) = oi'(f(a1),...,f(ak))

则 f 是从 V1 到 V2 的同态。

对二元运算可简写为：

1
f(a o b) = f(a) o' f(b)

分类：

1
2
3
4
5
单同态：f 是单射。
满同态：f 是满射。
同构：f 是双射同态。
自同态：定义域和值域是同一个代数系统。
自同构：同构且定义域和值域相同。

重要性质：

1
2
3
4
5
1. 同态的合成仍是同态。
2. 同构关系具有自反、对称、传递性。
3. 同态像是目标代数系统的子代数。
4. 满同态像保持交换、结合、幂等、分配、吸收、单位元、零元、逆元。
5. 消去律不一定被满同态保持。

同态必须保持所有运算，包括 0 元运算。只保持二元运算但不保持常数，不算这个代数系统的同态。

典型例子：

1
2
3
4
5
6
7
<Z,+> 中 fc(x)=cx 是自同态。
c=0：零同态
c=1 或 -1：自同构
其他 c：单自同态

<Z6,⊕> 中 fp(x)=px mod 6 是自同态。
p=1,5 时是自同构。

9、同余关系与商代数

同余关系先是等价关系，再要求和运算相容。

设 ~ 是 A 上等价关系。若对每个 ki 元运算 oi 都有：

1
2
a1~b1, ..., aki~bki
=> oi(a1,...,aki) ~ oi(b1,...,bki)

则称 ~ 对运算有置换性质；若对所有运算都有置换性质，则 ~ 是 V 上的同余关系。

商代数

设 R 是 V=<A,o1,...,or> 上的同余关系，则商代数：

1
V/R = <A/R, o1,...,or>

其中 A/R 的元素是等价类，运算定义为：

1
[a] o [b] = [a o b]

良定义依赖于同余关系的置换性质。

商代数保持：

1
2
交换、结合、幂等、分配、吸收
单位元、零元、逆元

但：

1
消去律不一定保持。

例子：

1
2
3
4
<Z,+> 中按 mod 3 同余：
Z/~ = {[0],[1],[2]}
[x] ⊕ [y] = [x+y]
得到的商代数就是模 3 加法结构。

同态基本定理

同态、同余、商代数之间的关系：

1
2
3
同态 f:V1 -> V2
=> 可导出同余关系：x~y <=> f(x)=f(y)
=> V1/~ 同构于同态像 f(V1)

证明模板：

1
2
3
4
1. 定义 h:V1/R -> f(A)，h([a])=f(a)。
2. 验证良定义：[a]=[b] => f(a)=f(b)。
3. 验证 h 是双射。
4. 验证 h 保持运算。

10、习题答案速查

习题 15.4：判断运算性质

重点结论：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(1) 封闭，满足消去律，无单位元和零元。
(2) 封闭，只具有交换律、结合律和消去律；单位元是 1，无零元。
(3) 可逆数集合对加法不封闭，对乘法封闭；乘法交换、结合、消去，单位元为 1，无零元。
(4) 矩阵加法和乘法都封闭。加法交换、结合、消去；乘法结合；乘法对加法分配。
    n=1 时矩阵乘法还交换、消去。
    加法单位元为 0 矩阵；乘法单位元为 I，零元为 0 矩阵。
(5) 实可逆矩阵对加法不封闭，对乘法封闭；乘法结合、消去，单位元为 I，无零元。
(6) Zn 上加法和乘法都封闭；都交换、结合、消去；乘法对加法分配。
    加法单位元 0；乘法零元 0；仅 n=1 时乘法单位元是 1。
(7) 不封闭。
(8) 封闭，满足结合律和幂等律；仅 n=1 时交换、消去，单位元和零元都是 a1。
(9) R(A) 对关系合成封闭，合成结合，单位元为 I_A，零元为空关系。
(10) 两个运算都封闭，都交换、结合、幂等，互相分配并满足吸收律。
     1 是 lcm 的单位元，也是 gcd 的零元。

涉及 n 或集合 A 的题要分类讨论：n=1 与 n>1 往往不同；A 为空集、单元集、至少两个元素时，关系合成的性质也可能不同。

习题 15.5

1
2
(1) 不能。
(2) 能，取 {0,1,-1}。

习题 15.6：函数集合上的运算

1
2
3
4
(1) 构成代数系统；交换、结合；单位元是零函数 f0；无零元。
(2) 构成代数系统；不交换、不结合；无单位元、无零元。
(3) 构成代数系统；交换、结合；单位元是常 1 函数 f1；零元是零函数 f0。
(4) 不构成代数系统。

习题 15.7

1
2
3
4
(1) 构成代数系统；交换、结合、幂等；单位元是 1，无零元。
(2) 构成代数系统；交换、结合、幂等；零元是 1，无单位元。
(3) 构成代数系统；不满足指定算律，无单位元、无零元。
(4) 不构成代数系统。

习题 15.8：a o b = pa + qb + r

1
2
3
4
5
6
7
8
9
10
交换律 <=> p=q

结合律 <=>
p in {0,1}, q in {0,1}, 且 (p=q 或 r=0)

幂等律 <=> p+q=1 且 r=0

单位元存在 <=> p=q=1，此时 e=-r

零元存在 <=> p=q=0，此时 theta=r

习题 15.9：x*y=x+y-xy

在 Q 上定义 x*y=x+y-xy：

1
2
3
4
5
6
交换律：有。
结合律：有。
幂等律：无，例如 2*2=0。
单位元：0。
零元：1。
逆元：若 x != 1，则 x 的逆元为 -x/(1-x)。

习题 15.11

1
2
3
4
只适合结合律。
单位元为 <1,0>。
没有零元。
<a,b> 的逆元为 <1/a, -b/a>，其中 a != 0。

习题 15.12

1
2
3
4
(1) 可交换、可结合，单位元 a。
(2) 可结合、幂等。
(3) 可交换、可结合，单位元 a，零元 c。
(4) 可交换、可结合，单位元 a。

习题 15.13：零元唯一性

证明模板：

1
2
3
4
若存在左零元 theta_l 和右零元 theta_r，
则 theta_l = theta_l o theta_r = theta_r。
若 theta' 也是零元，则 theta = theta o theta' = theta'。
所以零元唯一。

习题 15.14：<Z6,⊕> 的子代数

1
2
3
子代数：Z6, {0,2,4}, {0,3}, {0}
平凡子代数：Z6 和 {0}
除 Z6 外，其余都是真子代数。

习题 15.16：积代数逆元

1
2
3
4
5
6
7
8
单位元：<0,0>

<0,0>^-1 = <0,0>
<0,1>^-1 = <0,1>
<1,0>^-1 = <2,0>
<2,0>^-1 = <1,0>
<1,1>^-1 = <2,1>
<2,1>^-1 = <1,1>

习题 15.17：积代数性质证明

证明要点：

1
2
3
4
5
1. 交换、结合、幂等：按分量展开，分别用两个因子代数的对应性质。
2. 分配律：先按积代数运算定义展开，再在两个分量里分别用分配律。
3. 吸收律：同样按分量展开。
4. 单位元/零元：若因子里分别是 e1,e2 或 theta1,theta2，则积代数中是 <e1,e2> 或 <theta1,theta2>。
5. 逆元：若 a^-1,b^-1 分别存在，则 <a,b>^-1=<a^-1,b^-1>。

习题 15.18：复数与矩阵代数同构

映射思路：

1
f(a+bi) = [[a,b],[-b,a]]

验证：

1
2
3
1. f 是双射。
2. f((a+bi)+(c+di)) = f(a+bi)+f(c+di)。
3. f((a+bi)(c+di)) = f(a+bi)f(c+di)。

所以两个代数系统同构。

习题 15.19：积代数交换因子同构

定义：

1
2
f:A x B -> B x A
f(<a,b>)=<b,a>

f 是双射，并且按分量保持对应运算，所以：

1
V1 x V2 ~= V2 x V1

习题 15.20：幂集代数到布尔代数的同态

定义特征映射：

1
2
phi(x)=1，当 a in x
phi(x)=0，当 a notin x

验证：

1
2
3
4
5
phi(x union y)=phi(x)+phi(y)   （按布尔或理解）
phi(x intersection y)=phi(x)phi(y)
phi(~x)=1-phi(x)
phi(emptyset)=0
phi({a,b})=1

习题 15.21-15.23：同态性质

1
2
3
15.21：满同态保持交换、结合、幂等、分配、吸收、单位元、零元、逆元。
15.22：同态复合仍是同态。
15.23：同构具有自反、对称、传递性。

习题 15.24-15.26：同态判断

1
2
3
4
5
6
7
8
9
10
11
15.24：
(1) 不是同态
(2) 是同态，phi(V1)=R+ union {0}
(3) 是同态，phi(V1)={0}
(4) 不是同态

15.25：
给定系统的自同构只有恒等映射。

15.26：
phi:Z+ -> Z2 为满同态，按 x=1 或 x>1 分情况验证乘法保持即可。

习题 15.27：同余关系判断

1
2
3
4
(1) 不是同余关系：不保持加法。
(2) 不是同余关系：不传递，也不保持加法。
(3) 不是同余关系：不保持加法。
(4) 不是同余关系：不对称，不是等价关系。

习题 15.28：商代数性质证明

证明模板：

1
2
3
4
在商代数中，[a] o [b] = [a o b]。
若原代数满足交换、结合、幂等、分配、吸收，
就把等价类运算展开为代表元运算，再套原代数性质。
单位元为 [e]，零元为 [theta]，逆元为 [x^-1]。

习题 15.29：自然映射与模 2 同余

1
2
3
phi(x)=x mod 2。
x~y <=> phi(x)=phi(y) <=> x,y 同奇偶。
划分为 {2Z, 2Z+1}。

习题 15.30

1
2
3
phi(x)=nx 是同态。
若 n=0，则所有元素同余，商代数只有一个等价类。
若 n!=0，则 x~y <=> x=y，商代数是恒等划分。

习题 15.31：四元集合运算的同态与同余

答案要点：

1
2
3
自同态共有 13 个。
由这些同态诱导出 7 个同余关系：
恒等关系、全域关系，以及 R1,R2,R3,R4,R5 五类非平凡同余关系。

方法：

1
2
方法一：先找全部自同态，再按 f(x)=f(y) 导出同余关系。
方法二：枚举 4 元集合的 15 种划分，逐一检查置换性质。

习题 15.32：积代数上的同余与商代数

设关系：

1
<a,b> R <c,d> <=> a=c

证明步骤：

1
2
3
4
5
1. R 是等价关系。
2. 按积代数分量运算定义，验证 R 对二元运算、一元运算和 0 元运算有置换性质。
3. 定义 f:V1 x V2 -> V1，f(<a,b>)=a。
4. f 是满同态，且 R 正是 f 导出的同余关系。
5. 由同态基本定理，(V1 x V2)/R ~= V1。

11、复盘清单

1
2
3
4
5
6
7
8
9
10
1. 判断代数系统先看封闭性，尤其注意参数和集合边界。
2. 单位元、零元、逆元必须左右都成立。
3. 证明算律用定义展开；否定算律用反例。
4. 子代数要对所有运算封闭，若有常数/0 元运算必须包含。
5. 积代数按分量运算，保持大多数性质，但消去律例外。
6. 同态必须保持全部运算，包括 0 元运算。
7. 同构就是双射同态，本质是结构相同、元素名字不同。
8. 同余关系 = 等价关系 + 置换性质。
9. 商代数的运算是 [a] o [b] = [a o b]，良定义靠同余。
10. 同态基本定理：同态像同构于商代数。