返回：0100 离散数学课程总目录 · 上一章：0114 代数结构基础 · 下一章：0116 群论基础

1、学习目标

本章是代数结构的第一层：从“一种封闭二元运算”出发，加入结合律得到半群，再加入单位元得到独异点。后续的群就是“每个元素都有逆元的独异点”。

主线：

1
2
3
4
广群：封闭二元运算
半群：封闭 + 结合律
独异点：半群 + 单位元
群：独异点 + 每个元素可逆

半群和独异点看似简单，但证明题高度依赖结合律。看到 abc、a^n、左零元、生成子半群、商半群时，第一反应都应该是：先用结合律合法改括号。

2、半群与独异点定义

半群

代数系统

1
V=<S,*>

若满足：

1
2
1. * 在 S 上封闭；
2. * 满足结合律：(a*b)*c = a*(b*c)；

则称 V 为半群。

半群判定模板：

1
2
第一步：任取 a,b in S，验证 a*b in S。
第二步：任取 a,b,c in S，验证 (a*b)*c = a*(b*c)。

独异点

若半群 <S,*> 中存在单位元 e：

1
e*a = a*e = a,  对任意 a in S

则称

1
<S,*,e>

为独异点，也叫含幺半群。

独异点判定模板：

1
2
3
1. 先证明 <S,*> 是半群。
2. 再找 e，并验证左右单位元条件。
3. 单位元唯一；若有左单位元和右单位元，它们必相等。

3、典型例子

结构 类型 单位元 说明
<N,+> 独异点 0 加法封闭且结合
<N,*> 独异点 1 乘法封闭且结合
<Z,+> 独异点 0 进一步还是群
<Σ+, 连接> 半群 无 非空串连接
<Σ*, 连接> 独异点 空串 自由独异点
<A^A, 复合> 独异点 I_A 函数复合
<R(A), 关系合成> 独异点 I_A 关系合成

任何半群都可以通过“添加一个新单位元”扩张成独异点。若原来没有单位元，就加入新元素 e；若原来已有单位元，就不需要添加。

4、幂运算

半群中因为有结合律，可以定义元素的幂：

1
2
a^1 = a
a^(n+1) = a^n a,  n in Z+

独异点中还能定义：

1
2
a^0 = e
a^(n+1) = a^n a,  n in N

幂运算规则：

1
2
a^n a^m = a^(n+m)
(a^n)^m = a^(nm)

范围要注意：

1
2
半群中 n,m 通常取正整数。
独异点中 n,m 可以取自然数，因为有 a^0=e。

5、子半群、子独异点与生成子半群

子半群

设 <S,*> 是半群，B 是 S 的非空子集。若：

1
对任意 x,y in B，有 x*y in B

则 <B,*> 是 <S,*> 的子半群。

子独异点

设 <S,*,e> 是独异点。B 是子独异点时，要满足：

1
2
3
1. B 非空；
2. B 对 * 封闭；
3. e in B，且 e 作为单位元被继承。

子半群不一定是子独异点。即使一个子半群有自己的单位元，也不一定是原独异点的单位元；作为“子独异点”时必须包含并继承原来的 e。

交与生成

定理：

1
2
若干子半群的非空交集仍为子半群。
若干子独异点的交集仍为子独异点。

由子集 B 生成的子半群：

1
2
3
4
<B> = 所有包含 B 的子半群的交集
     = union_{n>=1} B^n

B^n = {b1 b2 ... bn | bi in B}

例子：

1
2
3
<Z,+> 中 B={4,6}
<B> = {4i + 6j | i,j in N, i+j>0}
    = {4,6,8,10,12,14,16,...}

6、直积、商代数与同态

直积

半群的直积仍是半群：

1
<S1,*1> x <S2,*2>

在 S1 x S2 上按分量运算：

1
<a,b>*<c,d> = <a*1 c, b*2 d>

独异点的直积仍是独异点，单位元为：

1
<e1,e2>

商半群与商独异点

若 R 是半群 <A,o> 上的同余关系，则：

1
<A/R, ō>

是商半群，运算定义：

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

若原来是独异点 <A,o,e>，则商独异点为：

1
<A/R, ō, [e]>

同态

半群同态：

1
f(xy)=f(x)f(y)

独异点同态还要求：

1
f(e)=e'

同构就是双射同态，表示两个结构本质相同。

7、表示定理

设 <S,*> 是半群，令 S^S 表示所有从 S 到 S 的函数集合，运算为函数复合。则 <S^S, o> 也是半群，并且存在从 <S,*> 到 <S^S,o> 的同态。

构造：

1
2
3
对每个 a in S，定义 f_a:S -> S
f_a(x)=a*x
phi(a)=f_a

验证：

1
phi(a*b)=f_(a*b)=f_a o f_b=phi(a)o phi(b)

若 <S,*,e> 是独异点，则存在 T subset S^S，使得：

1
<S,*,e> ~= <T,o,I_S>

也就是说，每个独异点都可以表示成某个函数复合独异点的子独异点。

8、常见证明套路

结合律改括号

半群证明里最常用：

1
(ab)c = a(bc)

所以可以把 a*b*c 写成 abc，再按需要重新分组。

用反设制造“不交换”矛盾

若题目条件是：

1
a != b => ab != ba

则常用反证法：

1
2
3
假设某个等式不成立；
由条件推出两个元素相乘顺序不同结果不同；
再用结合律化简成同一个表达式不同于自身，矛盾。

有限半群找幂等元

因为 S 有限，某个元素的幂序列：

1
b, b^2, b^3, ...

必然重复。利用重复的幂可以构造 a 使：

1
a^2=a

这就是“每个有限半群都有幂等元”的证明核心。

理想构造商半群

若 I 是半群 <S,o> 的理想：

1
IS subset I,  SI subset I

定义关系：

1
xRy <=> x=y 或 x,y 都在 I

意思是把理想 I 整体压缩成一个等价类，S-I 中每个元素单独成类。这个关系是同余关系。

9、习题答案速查

习题 16.1：a o b = a+b+ab

在 R 上定义 a o b = a+b+ab。

1
2
3
4
5
6
7
(a o b) o c
= a+b+ab+c+(a+b+ab)c
= a+b+c+ab+ac+bc+abc

a o (b o c)
= a+(b+c+bc)+a(b+c+bc)
= a+b+c+ab+ac+bc+abc

所以结合律成立，<R,o> 是半群。

单位元：

1
2
a o 0 = a
0 o a = a

所以 0 是单位元，<R,o> 是独异点。

习题 16.2：由特殊元素推出独异点

已知存在 a in S，使任意 x in S 都可写为：

1
a*u = v*a = x

并取 u0,v0 使：

1
a*u0 = v0*a = a

证明：

1
2
x*u0 = (v*a)*u0 = v*(a*u0)=v*a=x
v0*x = v0*(a*u) = (v0*a)*u=a*u=x

所以 u0 是右单位元，v0 是左单位元，二者相等，记为 e。因此 V 是独异点。

习题 16.3：左零型运算

S={a,b,c}，定义：

1
x o y = x

则：

1
2
(x o y) o z = x o z = x
x o (y o z) = x o y = x

所以 <S,o> 是半群。

扩充为独异点：取 e notin S，令 S'={a,b,c,e}，定义：

1
2
3
4
x o' y = x,  x,y in S
x o' e = x
e o' x = x
e o' e = e

则 e 是单位元，<S',o',e> 是独异点。

习题 16.4：可交换性传递到乘积

若 a 与 c 可交换，b 与 c 可交换，则：

1
2
3
4
5
6
(a o b) o c
= a o (b o c)
= a o (c o b)
= (a o c) o b
= (c o a) o b
= c o (a o b)

所以 a o b 与 c 可交换。

习题 16.5：二元半群中由 a*a=b 推结论

设 <{a,b},*> 是半群，且 a*a=b。

结论：

1
2
a*b = b*a
b*b = b

证明思路：只可能在 {a,b} 中取值，逐个反设会与结合律矛盾。例如若 a*b=a 且 b*a=b，则：

1
2
(a*b)*a = a*a = b
a*(b*a) = a*b = a

矛盾。

习题 16.6：强非交换条件

已知任取 a,b in S，若 a!=b 则 a o b != b o a。

结论：

1
2
3
(1) 对任意 a，a o a = a。
(2) 对任意 a,b，a o b o a = a。
(3) 对任意 a,b,c，a o b o c = a o c。

证明套路：

1
2
若 a o a != a，则 (a o a)o a != a o(a o a)，但两边由结合律相等，矛盾。
后两问同理：反设两个元素不同，再用强非交换条件推出不同，最后由结合律化成同式矛盾。

习题 16.7：幂等元乘积仍幂等

若 <S,*> 是可交换半群，a,b 是幂等元，则：

1
2
3
4
(a*b)*(a*b)
= a*b*a*b
= a*a*b*b
= a*b

所以 a*b 也是幂等元。

习题 16.8：左零元生成左零元

若 theta_l 是左零元，则对任意 x,y in S：

1
2
3
(x o theta_l) o y
= x o (theta_l o y)
= x o theta_l

所以 x o theta_l 也是左零元。

习题 16.9：有限半群存在幂等元

证明要点：

1
2
3
4
5
6
任取 b in S。
由于 S 有限，存在 i>j，使 b^i=b^j。
令 p=i-j>=1。
由重复幂推出当 t>=i 时，b^t=b^(t+p)。
取 k 使 kp>=i，令 a=b^(kp)。
则 a^2=b^(2kp)=b^(kp)=a。

所以 a 是幂等元。

习题 16.10：<Z4, 模 4 乘法> 的子半群

所有子半群：

1
2
3
4
5
6
7
8
{0}
{1}
{0,1}
{0,2}
{1,3}
{0,1,2}
{0,1,3}
{0,1,2,3}

其中 V=<Z4,⊗,1> 的子独异点需要包含原单位元 1：

1
2
3
4
5
6
{1}
{0,1}
{1,3}
{0,1,2}
{0,1,3}
{0,1,2,3}

习题 16.11：商半群运算表

同余类：

1
[a]=[c], [b]=[d]

商代数 V/~=<A/~,*'> 的运算表：

*' [a] [b]
[a] [a] [b]
[b] [b] [a]

习题 16.12：理想诱导同余关系

设 I 是半群 <S,o> 的理想，定义：

1
xRy <=> x=y 或 (x in I 且 y in I)

证明步骤：

1
2
3
4
1. R 自反：x=x。
2. R 对称：x=y 或同在 I 都可对称。
3. R 传递：若 xRy 且 yRz，则 x=z 或 x,z 同在 I。
4. 置换性质：若 xRy 且 uRv，则 xou 与 yov 要么相等，要么都落在 I。

商代数：

1
2
3
4
5
S/R = {{x} | x in S-I} union {I}

{x} ō {y} = [x o y]
{x} ō I = I ō {x} = I
I ō I = I

习题 16.13：IR 触发器自动机

状态、输入、输出：

1
2
3
Q={0,1}
Σ={0,1,e}
Γ={0,1}

转移函数 δ：

δ 0 1 e
0 0 1 0
1 0 1 1

输出函数 λ 输出触发器原状态：

λ 0 1 e
0 0 0 0
1 1 1 1

习题 16.14：有穷自动机读图

答案：

1
2
3
Q={1,2,3}
Σ={a,b}
Γ={x,y}

转移函数 δ：

δ a b
1 1 3
2 1 2
3 1 2

输出函数 λ：

λ a b
1 y x
2 x x
3 x y

习题 16.15：模 5 加法半自动机

Q={0,1,2,3,4}，Σ=Q，转移函数：

1
δ(q,a)=q+a mod 5

表：

δ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3

习题 16.16：商自动机

等价类：

1
2
3
[q0]=[q1]=[q2]=[q3]={q0,q1,q2,q3}
[q4]=[q5]={q4,q5}
[q6]={q6}

所以：

1
2
3
Q/~ = {[q0],[q4],[q6]}
Σ={0,1}
Γ={0,1}

商自动机转移函数：

δ 0 1
[q0] [q0] [q6]
[q4] [q4] [q0]
[q6] [q0] [q4]

输出函数：

λ 0 1
[q0] 0 0
[q4] 1 0
[q6] 0 1

10、复盘清单

1
2
3
4
5
6
7
8
9
10
1. 半群 = 封闭 + 结合律。
2. 独异点 = 半群 + 单位元。
3. 半群的幂只从正整数开始；独异点可定义 a^0=e。
4. 子半群只要非空封闭；子独异点必须包含原单位元。
5. 若干子半群的非空交仍是子半群。
6. <B> 是由 B 中元素有限乘积组成的最小子半群。
7. 半群直积仍是半群，独异点直积仍是独异点。
8. 商半群运算是 [a]ō[b]=[ab]。
9. 半群同态保持乘法；独异点同态还要保持单位元。
10. 有限半群一定存在幂等元。