1
第十六章 半群与独异点
16.1 半群与独异点
? 半群、独异点的定义与性质
? 半群与独异点定义
? 半群与独异点性质
? 半群、独异点的子代数、积代数、商代数
? 子半群与子独异点
? 半群与独异点的直积
? 商半群与商独异点
? 半群与独异点的同态
? 独异点的表示定理
2
半群与独异点的定义
广群、半群、独异点（含幺半群）的定义
广群：封闭二元运算
半群：封闭二元运算，结合律
独异点：封闭二元运算，结合律，单位元
说明：任何半群都可以扩张成独异点
表示式中可以省略运算符
3
半群与独异点性质
幂运算的定义
半群 独异点
a
1
= a a
0
= e
a
n+1
= a
n
a
性质：
(1) 定理 1 幂运算的等式
a
n
a
m
= a
n+m
(a
n
)
m
= a
nm
(2) 结合律
4
例 1 V 为半群，任取 a,b∈S, 如果 a≠b, 则有 ab≠ba，
证明
(1) V 中成立幂等律
(2) ?a,b∈V, aba = a
(3) ?a,b,c∈V, abc = ac
证 (1) 假若 aa ≠ a, 则
(aa)a ≠ a(aa) ? aaa ≠ aaa，矛盾
(2) 假若 aba ≠ a, 则
(aba)a ≠ a(aba) ? aba ≠ aba ，矛盾
(3) 假若 abc ≠ ac, 则
(abc)(ac) ≠ (ac)(abc) ? abcac ≠ acabc
? ab(cac) ≠ (aca)bc ? abc ≠ abc ，矛盾
实例
5
子半群、子独异点
子半群、子独异点 B 的判别
非空子集 B，
B 对于 V 中的运算（含 0元运算）封闭 .
定理 2 若干子半群的非空交集仍为子半群；
若干子独异点的交集仍为子独异点 .
重要的子半群 ---子集合 B生成的子半群
V=<S,*>, B?S,包含 B 的最小的半群
<B>=∩{A | A是 S的子半群， B?A}
U
+
∈
>=<
Zn
n
BB
, B
n
={ b
1
b
2
…b
n
| b
i
∈B, i=1,2,…,n }
6
例 2 V=<Z,+>半群， B={4,6},
<B>={ 4i+6j | i,j ∈N, i 和 j 不同时为 0 }
={ 4,6,8,10,12,14,16,…} = 2Z
+
?{2}
例 3 Σ有穷字母表， Σ
+
为非空字的集合 , Σ
*
为字的集合。
a
1
a
2
…a
n
= b
1
b
2
…b
n
? a
1
=b
1,
a
2
=b
2
, …, a
n
=b
n
每个字可以唯一分解为 Σ中的元素之积
Σ
+
上的连接运算满足结合律， V=<Σ
+
,?>构成半群，
称为 Σ上的 自由半群 ， Σ为这个自由半群的生成元集，
即 <Σ>=V.
如果包含空串则 Σ
*
构成 自由独异点 .
实例
7
半群独异点的直积、商代数、同态
? 半群与独异点的直积
半群的直积仍是半群
独异点的直积仍是独异点
? 半群与独异点的商代数
半群 <A,°>, 商半群 <A/R,ō >
独异点 <A,°,e>，商独异点 <A/R,ō ,[e]>
? 半群与独异点的同态和同构
半群 f(xy)=f(x)f(y)
独异点 f(xy)=f(x)f(y), f(e)= e’
8
半群的同态性质
定理 3 设 V=<S,?>为半群， V’=<S
S
,°>， °为合成，则 V’也是
半群，且存在 V 到 V’ 的同态 .
证： f
a
:S→S, f
a
(x)=a ?x,
f
a
∈S
S
, 且 { f
a
| a∈S }? S
S
,
令 ?： S→S
S
, ?(a)=f
a
,
?(a ?b)=f
a?b
, ?(a)°?(b)=f
a
°f
b
为证同态只需证明 f
a ?b
=f
a
°f
b
?x∈S,
xbaxbaxbfxffxff
xbaxbaxf
ababa
ba
??=??=?==
??=??=
)()())(()(
)()(
*
o
9
定理 4 设 V=<S,
*
,e>为独异点，则存在 T?S
S
, 使得
<S,
*
,e>同构于 <T,?,I
S
>
证：令 ?： S→S
S
, ?(a) = f
a
, 则
?(a
*
b) = ?(a)??(b)
?(e) = f
e
= I
S
,
?为独异点 V 到 <S
S
,?,I
S
>的同态
?(a) = ?(b) ? f
a
= f
b
? ?x∈S(a
*
x=b
*
x)
? a
*
e = b
*
e ? a=b , ?为单射
令 T=?(S)，则 T?S
S
, 且 ?:S→T 为双射，
<S,
*
,e>?<T,°,I
S
>
独异点的表示定理
10
实例
例 4 S = Z
3
= { 0, 1, 2 }，独异点 V = <S,⊕,0>,
S
S
={ f
0
, f
1
, f
2
, …, f
26
}，其中
f
0
={<0,0>,<1,1>,<2,2>}
f
1
={<0,1>,<1,2>,<2,0>}
f
2
={<0,2>,<1,0>,<2,1>}
?:S→S
S
, ?(0) = f
0
, ?(1) = f
1
, ?(2) = f
2
?(S) ={ f
0
, f
1
,f
2
}?S
S
f
0
f
1
f
2
f
1
f
2
f
0
f
2
f
0
f
1
f
0
f
1
f
2
0 1 2
1 2 0
2 0 1
0
1
2
f
0
f
1
f
2
°0 1 2 ⊕
11
作业
? 复习要点
自然同态的概念
同态基本定理的应用
如何求同余关系
? 书面作业
习题十六， 2, 5, 6
? 阅读
十六章 16.2节 有穷自动机
