2009-7-29 离散数学 1
第六章 几个典型的代数系统
§ 6.1 半群与群
§ 6.2 格与布尔代数
2009-7-29 离散数学 2
可交换半群,如果半群 V = < S,? >中的 二元运算?是可交换的，则称 V为可交换半群。
一、半群的概念半群,设 V = < S,? >是代数系统,?是二元运算。
如果?在 S上是可结合的，则称 V为半群。
即对?x,y,z?S，有 (x? y)? z = x? (y? z)。
§ 6.1 半群与群如,<Z+,+>,<N,+>,<Z,+>,<R,?>,<Mn(R),?>,
<P(S),∪ >,<P(S),∩>,<P(S),?>,<Zn,?>都是半群，
但 < Z,– >不是半群。
2009-7-29 离散数学 3
一、半群的概念（续）
含幺半群（独异点）,如果半群 V = < S,? >的二元运算?含有幺元，则称 V为含幺半群 (独异点 )。
即? e?S，使得对?x?S都有 e? x = x? e = x。
独异点亦可记为 < S,?,e>。
如,<N,+,0>,<Z,+,0>,<R,?,1>,<Mn(R),?,E>,
<P(S),∪,?>,<P(S),∩,S>,<P(S),?,?>,<Zn,?,0>
都是独异点，但 <Z+,+>不是独异点。
2009-7-29 离散数学 4
独异点的性质,<A,? >是独异点,则?的运算表中没有任何两行或两列相同,
证明,任取 a,b (a?b)所在行,由于 A中含有幺元 e,
我们比较 a行,b行中 e列的元素
a? e = a
b? e = b
因为,a?b,所以 a?e? b?e,从而 a行与 b行不同,
同理可证任两列不同,
2009-7-29 离散数学 5
一、半群的概念（续）
子半群,半群的子代数。
即设 V = <S,?>是半群,B?S且 B，
若 B对? 运算 封闭,则 <B,?>是 V的子半群。
子独异点,含幺元的 子半群。
即设 V = <S,?,e>是独异点,B?S且 B，
若 B对? 运算 封闭，且 e?B,则 <B,?,e>是 V
的子独异点。
如,<Z+,+>和 <N,+>是 <Z,+>的子半群，且 <N,+>是
<Z,+>的子独异点，但 <Z+,+>却不是。
2009-7-29 离散数学 6
一、半群的概念（续）
半群中的幂,设 半群 V = <S,?>，则 对?x?S，
x1 = x,xn+1 = xn? x,(n为正整数 )
独异点中的幂,设 独异点 V = <S,?,e>，则 对?x?S，
x0 = e,xn+1 = xn? x,(n为自然数 )
幂运算的性质,xm? xn = xm + n,
(xm)n = xmn (m,n为正整数 )
2009-7-29 离散数学 7
一、半群的概念（续）
半群的同态,设 V1 = <S1,? >,V2 = <S2,? >为半群，
,S1? S2,且对? x,y?S1有
(x? y) =? (x) (y)，
则称?是半群 V1到 V2的同态。
独异点的同态,设 V1 = <S1,?,e1>,V2 = <S2,?,e2>
为独异点,?,S1? S2,且对?x,y?S1有
(x? y) =? (x) (y),? (e1) = e2，
则称?是独异点 V1到 V2的同态。
2009-7-29 离散数学 8
一、半群的概念（续）
如：半群 V = <S,?>，其中 S =,
为矩阵乘法。令?,S? S,? ( ) =,
则?是半群 V的自同态，且同态象为 <? (S),?>，
其中? (S) = 。
但是?不是独异点 V = <S,?,>的自同态。
Rda
d
a,
0
0
d
a
0
0
00
0a
Raa
00
0
10
01
2009-7-29 离散数学 9
二、群的概念群,设 V = <G,? >是代数系统,?是二元运算。
如果?在 G上是可结合的，存在幺元 e?G，
并且 G中的任意元素 x 都有 x –1?G,
则称 V = <G,? >为群。
如,<Z,+>,<R–{0},?>,<P(S),?>,<Zn,?>是群，
但 <N,+>,<Mn(R),?>不是。
代数系统 独异点 群(1) (2) (3)半群
2009-7-29 离散数学 10
二、群的概念（续）
有限群,G为有限集的群 <G,? >称为有限群，
否则称为无限群。
|G|为 有限群的阶 。
交换群,若群 <G,? >中的二元运算?是可交换的，
则称群 <G,? >为交换群，也称 阿贝尔群 。
如,<Z,+>,<R–{0},?>为无限群,<Zn,?>为有限群。
如,<Z,+>,<R–{0},?>,<P(S),?>,<Zn,?>都是阿贝尔群。
2009-7-29 离散数学 11
二、群的概念（续）
例：设 G = {e,a,b,c},?为 G上的二元运算，运算表如下：
e a b c
a a e c b
b b c e a
e e a b c
c c b a e
称群 <G,? >为 Klein四元群 。 在含四个元素的群中,
任意元素与自己运算的结果都为幺元；除幺元外，任意两个运算的结果都等于另一个元素。
2009-7-29 离散数学 12
二、群的概念（续）
群中的幂,设 群 <G,? >,则 对?x?G，
x0 = e,xn+1 = xn? x,(n为非负整数 )
x -n= (x -1)n= (xn)-1,(n为正整数 )
(1)? x?G,(x -1)-1 = x，
幂运算的性质：
(2)? x,y?G,(x? y)-1 = y -1? x –1，
(3)? x?G,xm?xn = xm + n,m,n为整数
(4)? x?G,(xm)n = xmn,m,n为整数
2009-7-29 离散数学 13
二、群的概念（续）
设 <G,? >为群,对?a,b?G，方程 a? x = b
和 y? a = b在 G中有解，且解是唯一的。定理 1
显然，两个方程的解分别是 x = a -1? b,y = b? a –1。
例 1,S = {1,2,3}，在群 <P(S),?>中解方程
{1,2}? x = {1,3} 和 y? {1} = {2,3}。
解,∵ 群 <P(S),?>的幺元是?，
∴ {1,2}-1= {1,2},{1}-1= {1}
y = {2,3}? {1}-1 = {2,3}? {1} = {1,2,3}。
∴ x = {1,2}-1? {1,3}= {1,2}? {1,3} = {2,3}
2009-7-29 离散数学 14
二、群的概念（续）
群 <G,?>中不存在零元?。定理 2
证明：若 |G| = 1，则 G的唯一元素必是幺元 e。
若 |G| > 1，假设G，
则对?x?G，有 x = x = e，
即说明 G中任何元素都不是?的逆元，
这与 <G,? >中每个元素都有逆元矛盾。
因此，群 <G,?>中不存在零元?。
2009-7-29 离散数学 15
二、群的概念（续）
设 <G,?>为有限群，则 G的运算表中的每一行 (每一列 )都是 G中元素的一个置换，且不同行 (或列 )的置换都不相同。
定理 4
设 <G,?>为群，则 G 中适合消去律。
即对?a,b,c?G，有
(1) 若 a? b = a? c，则 b = c。
(2) 若 b? a = c? a，则 b = c。
定理 3
利用定理 4可以通过运算表判断某个代数系统不是群，
但是不能判断某个代数系统是群。
2009-7-29 离散数学 16
证明,
(b–1?a–1)?(a?b) = b–1?(a–1?(a?b))
= b–1?((a–1?a)?b)
= b–1?(e?b)
= b–1?b
= e
(a?b)?(b–1?a–1) = a?(b?(b–1?a–1))
=a?((b?b–1)?a–1)=e
所以 (a? b)–1 = b–1? a–1
定理 5 设 <G,?>为群，对任意 a,b?G,
(a?b)–1 = b–1?a–1,(a–1)–1 = a
2009-7-29 离散数学 17
三、子群的概念子群,设 <G,? >为群,H是 G的非空子集，如果 H关于 G中的运算? 构成群，则称 <H,?>为 <G,?>
的子群。记作 H? G
如,<nZ,+>是 <Z,+>的子群，其中 <{0},+>和 <Z,+>
是 <Z,+>的平凡子群；
又如,Klein四元群 <{e,a,b,c},?>，有 5个子群：
<{e},?>,<{e,a},?>,<{e,b},?>,<{e,c},?>和
<{e,a,b,c},?>，其中 <{e},?>和 <{e,a,b,c},?>
是 <{e,a,b,c},?>的平凡子群。
2009-7-29 离散数学 18
三、子群的概念（续）
设 <G,? >为群,H是 G的非空子集，
如果 对?x,y?H,x? y -1?H，则 <H,?>
是 <G,? >的子群。
子群的判定定理例 2,<G,?>为群，对?x?G，令 H = { xk | k?Z }，
则 <H,?>是 <G,? >的子群。
称为由元素 x生成的子群,记作 H = <x>。
因为任意取 H中的元素 xm,xn,有 xm?(xn)-1=xm-n?H
如,群 <Z6,?>,<0> = {0},<1> = {0,1,2,3,4,5} = Z6,
<2> = {0,2,4},<3> = {0,3},<4> = <2>,<5> = <1> 。
2009-7-29 离散数学 19
元素的阶 (周期 )：设 群 <G,? >,a?G，使 ak = e 成立的最小正整数 k 称为 a的阶 (周期 ) 。
四、两种常用的群如：任何群的幺元 e 的阶都为 1,Klein四元群中 a,b,
c的阶都是 2,群 <Z6,?>中 2和 4的阶是 3,3的阶是 2,1和 5的阶是 6。
1、循环群：
2009-7-29 离散数学 20
证明,(充分性 )设 k = nr,则 ak = anr = (ar)n = en = e
(必要性 ) 如果 ak = e,反设 k不是 r的倍数,则
),0( 00 rkknrk
(1) ak = e 当且仅当 k是 r的倍数
，矛盾从而 eaaa kknrk 00
周期的性质,设 < G,* >是群,若 a?G有有限周期 r,则
(1) ak = e 当且仅当 k是 r的倍数
(2) a–1的周期亦为 r
(3) r? |G|
2009-7-29 离散数学 21
= (ar)–1 = e–1 = e
证明,反证,如果 r > |G|,则 a,a2,…,ar均为 G中不同元素，与 |G| < r矛盾,
证明,(a–1)r = a–1?a–1?…?a–1
r个
(2) a–1的周期亦为 r
(3) r? |G|
r个
= (a?a?…?a)–1
2009-7-29 离散数学 22
循环群,设 群 <G,? >，如果?a?G，使得
G = { ak | k?Z }
则称为循环群，记 G = <a>，
称 a为循环群 <G,? >的生成元。
四、两种常用的群（续）
如,群 <Z,+>是循环群，其生成元是 1或 -1，
性质,循环 群一定是阿贝尔群，但阿贝尔群不一定是循环群。
群 <Z6,?>是循环群，其生成元是 1或 5。
2009-7-29 离散数学 23
四、两种常用的群（续）
无限阶循环群 G = <a>的生成元就是 a和 a -1，
n阶循环群 G = <a>的生成元是 at (其中 t 与 n互质 )。
循环群的子群仍是循环群。
如,群 <Z6,?>中,Z6 = <1>,6的正因子是 1,2,3,6，
子群有 <16> = <0> = {0},<13> = <3> = {0,3}，
<12> = <2> = {0,2,4},<11> = <1> = {0,1,2,3,4,5}。
n阶循环群 G = < a >的子群的阶都是 n 的因子。
对于 n的每个正因子 d,an/d是 G的 d 阶子群的生成元。
2009-7-29 离散数学 24
四、两种常用的群（续）
如,12阶群 G={e,a,a2,…,a11},12的正因子是 1,2,3,4,6,12,
则 G的 子群是：
< a12/1 >=< e >={e},1阶子群
< a12/2 >=< a6 >={e,a6},2阶子群
< a12/3 >=< a4>={e,a4,a8} 3阶子群
< a12/4 >=< a3>={e,a3,a6,a9} 4阶子群
< a12/6 >=< a2>={e,a2,a4,a6,a8,a10} 6阶子群
< a12/12 >=< a >=G,12阶子群
2009-7-29 离散数学 25
四、两种常用的群（续）
n元置换,设 S= {1,2,…,n},S上的任何双射函数
,S? S构成了 S上 n个元素的置换，
称为 n元置换。记作：
)(.,,)2()1(
.,,21
n
n
如,S = {1,2,3}，令?,S? S且?(1) = 2,?(2) = 3，
(3) = 1，则有一个置换：
132
321
2、置换群：
2009-7-29 离散数学 26
四、两种常用的群（续）
任何 n元置换都可以用不交的轮换之积来表示。
如：置换?1 =,
146253 654321
又如：置换?2 =,
416253 654321
则可表示为?2 = (1 3 2 5) (4 6)
则可表示为?1 = (1 3 2 5 4 6)
又如：置换?3 =,
564213 654321
则可表示为?3 = (1 3 2) (4) (5 6) = (1 3 2) (5 6)
2009-7-29 离散数学 27
四、两种常用的群（续）
解,?1 = (1 4 5 2 3),
例 3：将置换?1和?2表成不交的轮换之积。
其中?1 =,?2 = 。
25134 54321 45213 54321
2 = (1 3 2)(4 5),
恒等置换,称 为恒等置换。记作,Is
nn...21,..21
当 |S| = n时,S上共有 n!种不同的 n元置换，将这些置换构成的集合记作 Sn。
2009-7-29 离散数学 28
置换的运算
(1) 设 S = {x1,x2,…,xn}上有置换：
P =
则称 为 P的逆置换,记作,P–1.
)()()( 21
21
n
n
xxx
xxx
n
n
xxx
xxx
21
21 )()()(
2009-7-29 离散数学 29
(2) 设 S = {x1,x2,…,xn}上有两个置换：
P1 =
则称 P = 为 P1与 P2的合成,
P2 =
显然, Is = Is =?,这说明,Is是 < Sn,? >中的幺元,
)()()( 21
21
n
n
xfxfxf
xxx
)()()(
)()()(
21
21
n
n
xgxgxg
xfxfxf
)()()( 21
21
n
n
xgxgxg
xxx
记作,P= P2? P1
2009-7-29 离散数学 30
四、两种常用的群（续）
(3) 任何置换? = 的逆置换
-1 = 就是?的逆元。
)(...)2()1(,..21 nn
n n...21 )(...)2()1(
因此,<Sn,?>构成一个群，称为 n元对称群 。
<Sn,?>的任何子群则称为 n元置换群 。
对于代数系统 <Sn,?>,?是函数的合成运算，则：
(1) 集合 Sn对运算?封闭，且? 是可结合的。
(2) Is是集合 Sn关于? 运算的幺元。
2009-7-29 离散数学 31
解,(1) 先写出所有的置换,共 3! = 6个,
例 6.5 设 S = {1,2,3},写出 S上所有的置换群
P4 = 2 1 31 2 3 P5 = 1 3 21 2 3
Pe = 1 2 31 2 3
按 顺序写：
1
2
3
P1 = 2 3 11 2 3 P2 = 3 1 21 2 3
P3 = 3 2 11 2 3
2009-7-29 离散数学 32
(2) 再列出 S3 = {pe,p1,p2,p4,p5}上关于合成运算? 的运算表
pe
p1
p2
p3
p4
p5
pe p1 p2 p3 p4 p5
pe p1 p2 p3 p4 p5
p1 p2 pe p4 p5 p3
p2 pe p1 p3 p4p5
p3 p5 p4 pe p2 p2
1p
4 p3 p5 p1 pe p2
p5 p4 p3 p2 p1 pe
Pe = 1 2 31 2 3
P1 = 2 3 11 2 3
P2 = 3 1 2
1 2 3
P3 = 3 2 11 2 3
P4 = 2 1 3
1 2 3
P5 = 1 3 21 2 3
2009-7-29 离散数学 33
(3) 最后写 S3上的置换群 (子群,检验封闭性 )
< pe,? >
<{pe,p4},? >
<{ pe,p1,p2},? >
都是 S3上的 子群，也是 置换群,
<{ pe,p3},? >
<{ pe,p5},? >
6.2 环与域
p3,p4,p5是 2阶元,p1,p2是 3阶元
< S3,? >
2009-7-29 离散数学 34
通常记,{x,y}的最小上界为,x? y
{x,y}的最大下界为,x? y
一、格的基本概念和性质格,设 < S,≤>是偏序集，如果?x,y?S,{x,y}都有最小上界和最大下界，则称 < S,≤>是一个 格 。
§ 6.3 格与布尔代数
< S6,R >
2
1
6
3
2009-7-29 离散数学 35
一、格的基本概念和性质（续）
解：
例 4,设 n为正整数,Sn是 n的正因子的集合,R为整除关系，验证 <Sn,R>是格，并举例说明。
对于?x,y?Sn,x与 y的最小公倍数 [x,y]属于 Sn，
x与 y的最大公约数 (x,y)属于 Sn，
且 x? y = [x,y],x? y = (x,y)。
因为 <Sn,R>是自反的，反对称的，传递的，
从而是偏序集；
因此,<Sn,R>是一个格。
2009-7-29 离散数学 36
一、格的基本概念和性质（续）
例 4：设 n为正整数,Sn是 n的正因子的集合,R为整除关系，验证 <Sn,R>是格，并举例说明。
如当 n = 6,8,30时，分别有下图：
< S8,R >
8
4
2
1
< S6,R >
2
1
6
3
1
3 52
6 1015
30
< S30,R >
解：
2009-7-29 离散数学 37
一、格的基本概念和性质（续）
例 5：判断下列偏序集是否构成格，说明原因。
d
ba
c
fe
c
b
a
d
e
a
b
e
c
d
f
{e,f}没有上界
{b,d}有上界
c,e，但没有最小上界
{d,e}有下界
a,b,c，但没有最大下界
2009-7-29 离散数学 38
(1) 格的对偶原理,设 f 为含有格中的元素及符号 =,
≤,≥,?,?的关系式。 f *是将 f 中的 ≤改成
≥,≥改成 ≤,?改成?,?改成?后所得的关系式,称之为 f 的对偶命题。
若 f 为 对一切格为 真,则 f *也 对一切格 为真。
一、格的基本概念和性质（续）
如：若格中 (a? b)? c≤c成立，则 (a? b)? c≥c成立。
格的性质：
2009-7-29 离散数学 39
幂等律：
(2) 设 < L,≤>是格,a,b,c是 L中任意元素，则有：
一、格的基本概念和性质（续）
交换律,a? b = b? a,a? b = b? a；
结合律,(a? b)? c = a? (b? c)，
(a? b)? c = a? (b? c)；
幂等律,a? a = a,a? a = a；
吸收律,a? (a? b) = a,a? (a? b) = a；
a? a≥a
a≥a
a = a? a
a≥a? a
2009-7-29 离散数学 40
吸收律：
(2) 设 < L,≤>是格,a,b,c是 L中任意元素，则有：
一、格的基本概念和性质（续）
交换律,a? b = b? a,a? b = b? a；
结合律,(a? b)? c = a? (b? c)，
(a? b)? c = a? (b? c)；
幂等律,a? a = a,a? a = a；
吸收律,a? (a? b) = a,a? (a? b) = a；
a? (a? b)≥a
a? b≤a? a = a? (a? b)? a? (a? b)≤a
a≤a
2009-7-29 离散数学 41
一、格的基本概念和性质（续）
结合律,(a? b)? c = a? (b? c)，
(a? b)? c = a? (b? c)；
∵ (a? b)? c≥c
且 (a? b)? c≥a? b≥b
又 ∵ (a? b)? c≥ a? b≥a
∴ (a? b)? c≥b? c
证明：
∴ (a? b)? c≥ a? (b? c)
同理可证 a? (b? c)≥(a? b)? c
∴ (a? b)? c = a? (b? c)
2009-7-29 离散数学 42
格,设 <L,?,?>是代数系统,?和?是二元运算，
若?和?运算满足交换律，结合律和吸收律，
（ 隐含幂等律 ），则称 <L,?,?>是一个格。
一、格的基本概念和性质（续）
子格,设 <L,?,?>是格,S 是 L 的非空子集，若 S
关于运算?和?是封闭的，则称 <S,?,?>是格 <L,?,?>的子格。
格的另一个等价定义：
2009-7-29 离散数学 43
一、格的基本概念和性质（续）
例 6：格 <L,?,?>如图,<Si,?,?>是否构成其子格。
其中 S1 = { a,e,g,h},S2 = { a,c,e,h}，
S3 = { a,b,d,f,h}
a
b dc
e gf
h <S1,?,?>不是子格，
<S2,?,?>是子格，
<S3,?,?>是子格，
2009-7-29 离散数学 44
格的同态,设 <L1,?,?>,<L2,?,?>是格，
,L1? L2,且对?a,b?L1有
(a? b) =? (a) (b) 和? (a? b) =? (a) (b),
则称?是格 <L1,?,?>到格 <L2,?,?>的同态。
一、格的基本概念和性质（续）
若?是单射，则称?是单同态；
若?是满射，则称?是满同态；
若?是双射，则称?是同构。
2009-7-29 离散数学 45
b
e a
c
d
五角格
1,分配格,设 <L,?,?>是格，若对?a,b,c?L有
a? (b? c) = (a? b)? (a? c)
a? (b? c) = (a? b)? (a? c)
成立，则称 <L,?,?>为分配格。
二、特殊的格
d
c
b
a
b
a
d
c a
d
e
cb
钻石格
2009-7-29 离散数学 46
二、特殊的格（续）
格 <L,?,?>是分配格当且仅当它不含有与五角格或钻石格同构的子格。
分配格的判定定理例 6：判断下列格是否为分配格。
c
a
f
ed
b
c
a
ed
b
f
c
a
e
d
b
g
f
c
a
h
ef
b
g
d
2009-7-29 离散数学 47
二、特殊的格（续）
2、有界格：
全下界 (或全上界 ),设 <L,?,?>为 格，
若 存在 a?L,对?b?L有 a≤b(或 a≥b)，
则称 a为格 <L,?,?>的全下界 (全上界 )。
有界格,具有全上界和全下界的格。
记作 <L,?,?,0,1>。
记全下界为 0，全上界为 1。
所有的有限元的格都是有界格。
2009-7-29 离散数学 48
二、特殊的格（续）
3、有补格：
补元,设 <L,?,?,0,1>是有界 格,a?L,若?b?L，
使得 a? b = 0,a? b = 1,则称 b为 a 的补元。
a
0
1
cb c
0
1 b
aa
0
1
b
1
b
a
0
补元可能存在或不存在，存在亦可能不唯一。
2009-7-29 离散数学 49
又 b = b? (a? c) = (b? a)?(b? c)
=b? c,
于是 b = b? (a? c) = (b? a)?(b? c)
= b? c,
设 a有两个补元 b和 c,即 a?b = 0,a? b = 1,
a? c = 0,a? c = 1,
二、特殊的格（续）
有补格,设 <L,?,?,0,1>是有界 格，
若对? a?L,在 L中都存在 a的补元，
则称 <L,?,?,0,1>是有补格。
设 <L,?,?,0,1>是 分配格，若 a?L存在补元，
则 a的补元是唯一的。记为 a'定理证明：
则 b≤c,
则 b≥c,因此 b = c。
2009-7-29 离散数学 50
二、特殊的格（续）
布尔代数也可记为 <L,?,?,',0,1>,'表示求补运算。
4,布尔格,如果格 <L,?,?,0,1>是有补分配格，
则称 <L,?,?,0,1>为布尔格，
也叫做布尔代数。
集合的幂集格（集合代数）：
<P(S),∩,∪,~,?,S>是 布尔代数，
逻辑（开关）代数：
<{0,1},?,?,?,0,1>是 布尔代数。
2009-7-29 离散数学 51
二、特殊的格（续）
布尔代数的性质：
设 <L,?,?,',0,1>是布尔代数，则有
(1)?a?L,(a')' = a，
(2)?a,b?L,(a? b)' = a'? b',(a? b)' = a'? b'。
设 <L,?,?,',0,1>是 有限布尔代数，
则 L含有 2n个元 (n?N)，且 <L,?,?,',0,1>
与 <P(S),∩,∪,~,?,S>同构，
其中 S是一个 n元集合。
定理
第六章 几个典型的代数系统
§ 6.1 半群与群
§ 6.2 格与布尔代数
2009-7-29 离散数学 2
可交换半群,如果半群 V = < S,? >中的 二元运算?是可交换的，则称 V为可交换半群。
一、半群的概念半群,设 V = < S,? >是代数系统,?是二元运算。
如果?在 S上是可结合的，则称 V为半群。
即对?x,y,z?S，有 (x? y)? z = x? (y? z)。
§ 6.1 半群与群如,<Z+,+>,<N,+>,<Z,+>,<R,?>,<Mn(R),?>,
<P(S),∪ >,<P(S),∩>,<P(S),?>,<Zn,?>都是半群，
但 < Z,– >不是半群。
2009-7-29 离散数学 3
一、半群的概念（续）
含幺半群（独异点）,如果半群 V = < S,? >的二元运算?含有幺元，则称 V为含幺半群 (独异点 )。
即? e?S，使得对?x?S都有 e? x = x? e = x。
独异点亦可记为 < S,?,e>。
如,<N,+,0>,<Z,+,0>,<R,?,1>,<Mn(R),?,E>,
<P(S),∪,?>,<P(S),∩,S>,<P(S),?,?>,<Zn,?,0>
都是独异点，但 <Z+,+>不是独异点。
2009-7-29 离散数学 4
独异点的性质,<A,? >是独异点,则?的运算表中没有任何两行或两列相同,
证明,任取 a,b (a?b)所在行,由于 A中含有幺元 e,
我们比较 a行,b行中 e列的元素
a? e = a
b? e = b
因为,a?b,所以 a?e? b?e,从而 a行与 b行不同,
同理可证任两列不同,
2009-7-29 离散数学 5
一、半群的概念（续）
子半群,半群的子代数。
即设 V = <S,?>是半群,B?S且 B，
若 B对? 运算 封闭,则 <B,?>是 V的子半群。
子独异点,含幺元的 子半群。
即设 V = <S,?,e>是独异点,B?S且 B，
若 B对? 运算 封闭，且 e?B,则 <B,?,e>是 V
的子独异点。
如,<Z+,+>和 <N,+>是 <Z,+>的子半群，且 <N,+>是
<Z,+>的子独异点，但 <Z+,+>却不是。
2009-7-29 离散数学 6
一、半群的概念（续）
半群中的幂,设 半群 V = <S,?>，则 对?x?S，
x1 = x,xn+1 = xn? x,(n为正整数 )
独异点中的幂,设 独异点 V = <S,?,e>，则 对?x?S，
x0 = e,xn+1 = xn? x,(n为自然数 )
幂运算的性质,xm? xn = xm + n,
(xm)n = xmn (m,n为正整数 )
2009-7-29 离散数学 7
一、半群的概念（续）
半群的同态,设 V1 = <S1,? >,V2 = <S2,? >为半群，
,S1? S2,且对? x,y?S1有
(x? y) =? (x) (y)，
则称?是半群 V1到 V2的同态。
独异点的同态,设 V1 = <S1,?,e1>,V2 = <S2,?,e2>
为独异点,?,S1? S2,且对?x,y?S1有
(x? y) =? (x) (y),? (e1) = e2，
则称?是独异点 V1到 V2的同态。
2009-7-29 离散数学 8
一、半群的概念（续）
如：半群 V = <S,?>，其中 S =,
为矩阵乘法。令?,S? S,? ( ) =,
则?是半群 V的自同态，且同态象为 <? (S),?>，
其中? (S) = 。
但是?不是独异点 V = <S,?,>的自同态。
Rda
d
a,
0
0
d
a
0
0
00
0a
Raa
00
0
10
01
2009-7-29 离散数学 9
二、群的概念群,设 V = <G,? >是代数系统,?是二元运算。
如果?在 G上是可结合的，存在幺元 e?G，
并且 G中的任意元素 x 都有 x –1?G,
则称 V = <G,? >为群。
如,<Z,+>,<R–{0},?>,<P(S),?>,<Zn,?>是群，
但 <N,+>,<Mn(R),?>不是。
代数系统 独异点 群(1) (2) (3)半群
2009-7-29 离散数学 10
二、群的概念（续）
有限群,G为有限集的群 <G,? >称为有限群，
否则称为无限群。
|G|为 有限群的阶 。
交换群,若群 <G,? >中的二元运算?是可交换的，
则称群 <G,? >为交换群，也称 阿贝尔群 。
如,<Z,+>,<R–{0},?>为无限群,<Zn,?>为有限群。
如,<Z,+>,<R–{0},?>,<P(S),?>,<Zn,?>都是阿贝尔群。
2009-7-29 离散数学 11
二、群的概念（续）
例：设 G = {e,a,b,c},?为 G上的二元运算，运算表如下：
e a b c
a a e c b
b b c e a
e e a b c
c c b a e
称群 <G,? >为 Klein四元群 。 在含四个元素的群中,
任意元素与自己运算的结果都为幺元；除幺元外，任意两个运算的结果都等于另一个元素。
2009-7-29 离散数学 12
二、群的概念（续）
群中的幂,设 群 <G,? >,则 对?x?G，
x0 = e,xn+1 = xn? x,(n为非负整数 )
x -n= (x -1)n= (xn)-1,(n为正整数 )
(1)? x?G,(x -1)-1 = x，
幂运算的性质：
(2)? x,y?G,(x? y)-1 = y -1? x –1，
(3)? x?G,xm?xn = xm + n,m,n为整数
(4)? x?G,(xm)n = xmn,m,n为整数
2009-7-29 离散数学 13
二、群的概念（续）
设 <G,? >为群,对?a,b?G，方程 a? x = b
和 y? a = b在 G中有解，且解是唯一的。定理 1
显然，两个方程的解分别是 x = a -1? b,y = b? a –1。
例 1,S = {1,2,3}，在群 <P(S),?>中解方程
{1,2}? x = {1,3} 和 y? {1} = {2,3}。
解,∵ 群 <P(S),?>的幺元是?，
∴ {1,2}-1= {1,2},{1}-1= {1}
y = {2,3}? {1}-1 = {2,3}? {1} = {1,2,3}。
∴ x = {1,2}-1? {1,3}= {1,2}? {1,3} = {2,3}
2009-7-29 离散数学 14
二、群的概念（续）
群 <G,?>中不存在零元?。定理 2
证明：若 |G| = 1，则 G的唯一元素必是幺元 e。
若 |G| > 1，假设G，
则对?x?G，有 x = x = e，
即说明 G中任何元素都不是?的逆元，
这与 <G,? >中每个元素都有逆元矛盾。
因此，群 <G,?>中不存在零元?。
2009-7-29 离散数学 15
二、群的概念（续）
设 <G,?>为有限群，则 G的运算表中的每一行 (每一列 )都是 G中元素的一个置换，且不同行 (或列 )的置换都不相同。
定理 4
设 <G,?>为群，则 G 中适合消去律。
即对?a,b,c?G，有
(1) 若 a? b = a? c，则 b = c。
(2) 若 b? a = c? a，则 b = c。
定理 3
利用定理 4可以通过运算表判断某个代数系统不是群，
但是不能判断某个代数系统是群。
2009-7-29 离散数学 16
证明,
(b–1?a–1)?(a?b) = b–1?(a–1?(a?b))
= b–1?((a–1?a)?b)
= b–1?(e?b)
= b–1?b
= e
(a?b)?(b–1?a–1) = a?(b?(b–1?a–1))
=a?((b?b–1)?a–1)=e
所以 (a? b)–1 = b–1? a–1
定理 5 设 <G,?>为群，对任意 a,b?G,
(a?b)–1 = b–1?a–1,(a–1)–1 = a
2009-7-29 离散数学 17
三、子群的概念子群,设 <G,? >为群,H是 G的非空子集，如果 H关于 G中的运算? 构成群，则称 <H,?>为 <G,?>
的子群。记作 H? G
如,<nZ,+>是 <Z,+>的子群，其中 <{0},+>和 <Z,+>
是 <Z,+>的平凡子群；
又如,Klein四元群 <{e,a,b,c},?>，有 5个子群：
<{e},?>,<{e,a},?>,<{e,b},?>,<{e,c},?>和
<{e,a,b,c},?>，其中 <{e},?>和 <{e,a,b,c},?>
是 <{e,a,b,c},?>的平凡子群。
2009-7-29 离散数学 18
三、子群的概念（续）
设 <G,? >为群,H是 G的非空子集，
如果 对?x,y?H,x? y -1?H，则 <H,?>
是 <G,? >的子群。
子群的判定定理例 2,<G,?>为群，对?x?G，令 H = { xk | k?Z }，
则 <H,?>是 <G,? >的子群。
称为由元素 x生成的子群,记作 H = <x>。
因为任意取 H中的元素 xm,xn,有 xm?(xn)-1=xm-n?H
如,群 <Z6,?>,<0> = {0},<1> = {0,1,2,3,4,5} = Z6,
<2> = {0,2,4},<3> = {0,3},<4> = <2>,<5> = <1> 。
2009-7-29 离散数学 19
元素的阶 (周期 )：设 群 <G,? >,a?G，使 ak = e 成立的最小正整数 k 称为 a的阶 (周期 ) 。
四、两种常用的群如：任何群的幺元 e 的阶都为 1,Klein四元群中 a,b,
c的阶都是 2,群 <Z6,?>中 2和 4的阶是 3,3的阶是 2,1和 5的阶是 6。
1、循环群：
2009-7-29 离散数学 20
证明,(充分性 )设 k = nr,则 ak = anr = (ar)n = en = e
(必要性 ) 如果 ak = e,反设 k不是 r的倍数,则
),0( 00 rkknrk
(1) ak = e 当且仅当 k是 r的倍数
，矛盾从而 eaaa kknrk 00
周期的性质,设 < G,* >是群,若 a?G有有限周期 r,则
(1) ak = e 当且仅当 k是 r的倍数
(2) a–1的周期亦为 r
(3) r? |G|
2009-7-29 离散数学 21
= (ar)–1 = e–1 = e
证明,反证,如果 r > |G|,则 a,a2,…,ar均为 G中不同元素，与 |G| < r矛盾,
证明,(a–1)r = a–1?a–1?…?a–1
r个
(2) a–1的周期亦为 r
(3) r? |G|
r个
= (a?a?…?a)–1
2009-7-29 离散数学 22
循环群,设 群 <G,? >，如果?a?G，使得
G = { ak | k?Z }
则称为循环群，记 G = <a>，
称 a为循环群 <G,? >的生成元。
四、两种常用的群（续）
如,群 <Z,+>是循环群，其生成元是 1或 -1，
性质,循环 群一定是阿贝尔群，但阿贝尔群不一定是循环群。
群 <Z6,?>是循环群，其生成元是 1或 5。
2009-7-29 离散数学 23
四、两种常用的群（续）
无限阶循环群 G = <a>的生成元就是 a和 a -1，
n阶循环群 G = <a>的生成元是 at (其中 t 与 n互质 )。
循环群的子群仍是循环群。
如,群 <Z6,?>中,Z6 = <1>,6的正因子是 1,2,3,6，
子群有 <16> = <0> = {0},<13> = <3> = {0,3}，
<12> = <2> = {0,2,4},<11> = <1> = {0,1,2,3,4,5}。
n阶循环群 G = < a >的子群的阶都是 n 的因子。
对于 n的每个正因子 d,an/d是 G的 d 阶子群的生成元。
2009-7-29 离散数学 24
四、两种常用的群（续）
如,12阶群 G={e,a,a2,…,a11},12的正因子是 1,2,3,4,6,12,
则 G的 子群是：
< a12/1 >=< e >={e},1阶子群
< a12/2 >=< a6 >={e,a6},2阶子群
< a12/3 >=< a4>={e,a4,a8} 3阶子群
< a12/4 >=< a3>={e,a3,a6,a9} 4阶子群
< a12/6 >=< a2>={e,a2,a4,a6,a8,a10} 6阶子群
< a12/12 >=< a >=G,12阶子群
2009-7-29 离散数学 25
四、两种常用的群（续）
n元置换,设 S= {1,2,…,n},S上的任何双射函数
,S? S构成了 S上 n个元素的置换，
称为 n元置换。记作：
)(.,,)2()1(
.,,21
n
n
如,S = {1,2,3}，令?,S? S且?(1) = 2,?(2) = 3，
(3) = 1，则有一个置换：
132
321
2、置换群：
2009-7-29 离散数学 26
四、两种常用的群（续）
任何 n元置换都可以用不交的轮换之积来表示。
如：置换?1 =,
146253 654321
又如：置换?2 =,
416253 654321
则可表示为?2 = (1 3 2 5) (4 6)
则可表示为?1 = (1 3 2 5 4 6)
又如：置换?3 =,
564213 654321
则可表示为?3 = (1 3 2) (4) (5 6) = (1 3 2) (5 6)
2009-7-29 离散数学 27
四、两种常用的群（续）
解,?1 = (1 4 5 2 3),
例 3：将置换?1和?2表成不交的轮换之积。
其中?1 =,?2 = 。
25134 54321 45213 54321
2 = (1 3 2)(4 5),
恒等置换,称 为恒等置换。记作,Is
nn...21,..21
当 |S| = n时,S上共有 n!种不同的 n元置换，将这些置换构成的集合记作 Sn。
2009-7-29 离散数学 28
置换的运算
(1) 设 S = {x1,x2,…,xn}上有置换：
P =
则称 为 P的逆置换,记作,P–1.
)()()( 21
21
n
n
xxx
xxx
n
n
xxx
xxx
21
21 )()()(
2009-7-29 离散数学 29
(2) 设 S = {x1,x2,…,xn}上有两个置换：
P1 =
则称 P = 为 P1与 P2的合成,
P2 =
显然, Is = Is =?,这说明,Is是 < Sn,? >中的幺元,
)()()( 21
21
n
n
xfxfxf
xxx
)()()(
)()()(
21
21
n
n
xgxgxg
xfxfxf
)()()( 21
21
n
n
xgxgxg
xxx
记作,P= P2? P1
2009-7-29 离散数学 30
四、两种常用的群（续）
(3) 任何置换? = 的逆置换
-1 = 就是?的逆元。
)(...)2()1(,..21 nn
n n...21 )(...)2()1(
因此,<Sn,?>构成一个群，称为 n元对称群 。
<Sn,?>的任何子群则称为 n元置换群 。
对于代数系统 <Sn,?>,?是函数的合成运算，则：
(1) 集合 Sn对运算?封闭，且? 是可结合的。
(2) Is是集合 Sn关于? 运算的幺元。
2009-7-29 离散数学 31
解,(1) 先写出所有的置换,共 3! = 6个,
例 6.5 设 S = {1,2,3},写出 S上所有的置换群
P4 = 2 1 31 2 3 P5 = 1 3 21 2 3
Pe = 1 2 31 2 3
按 顺序写：
1
2
3
P1 = 2 3 11 2 3 P2 = 3 1 21 2 3
P3 = 3 2 11 2 3
2009-7-29 离散数学 32
(2) 再列出 S3 = {pe,p1,p2,p4,p5}上关于合成运算? 的运算表
pe
p1
p2
p3
p4
p5
pe p1 p2 p3 p4 p5
pe p1 p2 p3 p4 p5
p1 p2 pe p4 p5 p3
p2 pe p1 p3 p4p5
p3 p5 p4 pe p2 p2
1p
4 p3 p5 p1 pe p2
p5 p4 p3 p2 p1 pe
Pe = 1 2 31 2 3
P1 = 2 3 11 2 3
P2 = 3 1 2
1 2 3
P3 = 3 2 11 2 3
P4 = 2 1 3
1 2 3
P5 = 1 3 21 2 3
2009-7-29 离散数学 33
(3) 最后写 S3上的置换群 (子群,检验封闭性 )
< pe,? >
<{pe,p4},? >
<{ pe,p1,p2},? >
都是 S3上的 子群，也是 置换群,
<{ pe,p3},? >
<{ pe,p5},? >
6.2 环与域
p3,p4,p5是 2阶元,p1,p2是 3阶元
< S3,? >
2009-7-29 离散数学 34
通常记,{x,y}的最小上界为,x? y
{x,y}的最大下界为,x? y
一、格的基本概念和性质格,设 < S,≤>是偏序集，如果?x,y?S,{x,y}都有最小上界和最大下界，则称 < S,≤>是一个 格 。
§ 6.3 格与布尔代数
< S6,R >
2
1
6
3
2009-7-29 离散数学 35
一、格的基本概念和性质（续）
解：
例 4,设 n为正整数,Sn是 n的正因子的集合,R为整除关系，验证 <Sn,R>是格，并举例说明。
对于?x,y?Sn,x与 y的最小公倍数 [x,y]属于 Sn，
x与 y的最大公约数 (x,y)属于 Sn，
且 x? y = [x,y],x? y = (x,y)。
因为 <Sn,R>是自反的，反对称的，传递的，
从而是偏序集；
因此,<Sn,R>是一个格。
2009-7-29 离散数学 36
一、格的基本概念和性质（续）
例 4：设 n为正整数,Sn是 n的正因子的集合,R为整除关系，验证 <Sn,R>是格，并举例说明。
如当 n = 6,8,30时，分别有下图：
< S8,R >
8
4
2
1
< S6,R >
2
1
6
3
1
3 52
6 1015
30
< S30,R >
解：
2009-7-29 离散数学 37
一、格的基本概念和性质（续）
例 5：判断下列偏序集是否构成格，说明原因。
d
ba
c
fe
c
b
a
d
e
a
b
e
c
d
f
{e,f}没有上界
{b,d}有上界
c,e，但没有最小上界
{d,e}有下界
a,b,c，但没有最大下界
2009-7-29 离散数学 38
(1) 格的对偶原理,设 f 为含有格中的元素及符号 =,
≤,≥,?,?的关系式。 f *是将 f 中的 ≤改成
≥,≥改成 ≤,?改成?,?改成?后所得的关系式,称之为 f 的对偶命题。
若 f 为 对一切格为 真,则 f *也 对一切格 为真。
一、格的基本概念和性质（续）
如：若格中 (a? b)? c≤c成立，则 (a? b)? c≥c成立。
格的性质：
2009-7-29 离散数学 39
幂等律：
(2) 设 < L,≤>是格,a,b,c是 L中任意元素，则有：
一、格的基本概念和性质（续）
交换律,a? b = b? a,a? b = b? a；
结合律,(a? b)? c = a? (b? c)，
(a? b)? c = a? (b? c)；
幂等律,a? a = a,a? a = a；
吸收律,a? (a? b) = a,a? (a? b) = a；
a? a≥a
a≥a
a = a? a
a≥a? a
2009-7-29 离散数学 40
吸收律：
(2) 设 < L,≤>是格,a,b,c是 L中任意元素，则有：
一、格的基本概念和性质（续）
交换律,a? b = b? a,a? b = b? a；
结合律,(a? b)? c = a? (b? c)，
(a? b)? c = a? (b? c)；
幂等律,a? a = a,a? a = a；
吸收律,a? (a? b) = a,a? (a? b) = a；
a? (a? b)≥a
a? b≤a? a = a? (a? b)? a? (a? b)≤a
a≤a
2009-7-29 离散数学 41
一、格的基本概念和性质（续）
结合律,(a? b)? c = a? (b? c)，
(a? b)? c = a? (b? c)；
∵ (a? b)? c≥c
且 (a? b)? c≥a? b≥b
又 ∵ (a? b)? c≥ a? b≥a
∴ (a? b)? c≥b? c
证明：
∴ (a? b)? c≥ a? (b? c)
同理可证 a? (b? c)≥(a? b)? c
∴ (a? b)? c = a? (b? c)
2009-7-29 离散数学 42
格,设 <L,?,?>是代数系统,?和?是二元运算，
若?和?运算满足交换律，结合律和吸收律，
（ 隐含幂等律 ），则称 <L,?,?>是一个格。
一、格的基本概念和性质（续）
子格,设 <L,?,?>是格,S 是 L 的非空子集，若 S
关于运算?和?是封闭的，则称 <S,?,?>是格 <L,?,?>的子格。
格的另一个等价定义：
2009-7-29 离散数学 43
一、格的基本概念和性质（续）
例 6：格 <L,?,?>如图,<Si,?,?>是否构成其子格。
其中 S1 = { a,e,g,h},S2 = { a,c,e,h}，
S3 = { a,b,d,f,h}
a
b dc
e gf
h <S1,?,?>不是子格，
<S2,?,?>是子格，
<S3,?,?>是子格，
2009-7-29 离散数学 44
格的同态,设 <L1,?,?>,<L2,?,?>是格，
,L1? L2,且对?a,b?L1有
(a? b) =? (a) (b) 和? (a? b) =? (a) (b),
则称?是格 <L1,?,?>到格 <L2,?,?>的同态。
一、格的基本概念和性质（续）
若?是单射，则称?是单同态；
若?是满射，则称?是满同态；
若?是双射，则称?是同构。
2009-7-29 离散数学 45
b
e a
c
d
五角格
1,分配格,设 <L,?,?>是格，若对?a,b,c?L有
a? (b? c) = (a? b)? (a? c)
a? (b? c) = (a? b)? (a? c)
成立，则称 <L,?,?>为分配格。
二、特殊的格
d
c
b
a
b
a
d
c a
d
e
cb
钻石格
2009-7-29 离散数学 46
二、特殊的格（续）
格 <L,?,?>是分配格当且仅当它不含有与五角格或钻石格同构的子格。
分配格的判定定理例 6：判断下列格是否为分配格。
c
a
f
ed
b
c
a
ed
b
f
c
a
e
d
b
g
f
c
a
h
ef
b
g
d
2009-7-29 离散数学 47
二、特殊的格（续）
2、有界格：
全下界 (或全上界 ),设 <L,?,?>为 格，
若 存在 a?L,对?b?L有 a≤b(或 a≥b)，
则称 a为格 <L,?,?>的全下界 (全上界 )。
有界格,具有全上界和全下界的格。
记作 <L,?,?,0,1>。
记全下界为 0，全上界为 1。
所有的有限元的格都是有界格。
2009-7-29 离散数学 48
二、特殊的格（续）
3、有补格：
补元,设 <L,?,?,0,1>是有界 格,a?L,若?b?L，
使得 a? b = 0,a? b = 1,则称 b为 a 的补元。
a
0
1
cb c
0
1 b
aa
0
1
b
1
b
a
0
补元可能存在或不存在，存在亦可能不唯一。
2009-7-29 离散数学 49
又 b = b? (a? c) = (b? a)?(b? c)
=b? c,
于是 b = b? (a? c) = (b? a)?(b? c)
= b? c,
设 a有两个补元 b和 c,即 a?b = 0,a? b = 1,
a? c = 0,a? c = 1,
二、特殊的格（续）
有补格,设 <L,?,?,0,1>是有界 格，
若对? a?L,在 L中都存在 a的补元，
则称 <L,?,?,0,1>是有补格。
设 <L,?,?,0,1>是 分配格，若 a?L存在补元，
则 a的补元是唯一的。记为 a'定理证明：
则 b≤c,
则 b≥c,因此 b = c。
2009-7-29 离散数学 50
二、特殊的格（续）
布尔代数也可记为 <L,?,?,',0,1>,'表示求补运算。
4,布尔格,如果格 <L,?,?,0,1>是有补分配格，
则称 <L,?,?,0,1>为布尔格，
也叫做布尔代数。
集合的幂集格（集合代数）：
<P(S),∩,∪,~,?,S>是 布尔代数，
逻辑（开关）代数：
<{0,1},?,?,?,0,1>是 布尔代数。
2009-7-29 离散数学 51
二、特殊的格（续）
布尔代数的性质：
设 <L,?,?,',0,1>是布尔代数，则有
(1)?a?L,(a')' = a，
(2)?a,b?L,(a? b)' = a'? b',(a? b)' = a'? b'。
设 <L,?,?,',0,1>是 有限布尔代数，
则 L含有 2n个元 (n?N)，且 <L,?,?,',0,1>
与 <P(S),∩,∪,~,?,S>同构，
其中 S是一个 n元集合。
定理
