离散数学 第2版 教学课件 ppt 作者 尤枫 第07章 半群与群

《离散数学 第2版 教学课件 ppt 作者 尤枫 第07章 半群与群》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 尤枫 第07章 半群与群（111页珍藏版）》请在金锄头文库上搜索。

1、第7章 半群与群,第7章 半群与群,7.1半群与独异点,第7章 半群与群,定义7-1设有非空集合S，*是定义在S上的二元代数 运算，若*运算满足结合律，则称代数系统 U=为半群。 例如，, , , 等 都是半群。其中，N是自然数集合，Ev是偶 数集合，+和*是通常的加法和乘法运算。,7.1半群与独异点,第7章 半群与群,【例7-1】设Od是奇数集合，+是通常的加法运算， 则 U=不是半群。 因为 1,3Od， 但 1+3=4Od， 即 +运算在Od上不封闭， 故 U不是半群。,7.1半群与独异点,第7章 半群与群,【例7-2】在正实数集合R+中定义两个 二元运算和如下: ab=ab, ab=a

2、/b 由此得到两个代数系统U=和V=。 对于2,3,4R+，有 (23)4 = 234 = 212 2(34) = 2(34) = 281 (23)4 =(2/3)4 = 2/12 2(34) = 2(3/4)=8/3 显然，运算和运算都不满足结合律， 故U和V都不是半群。,7.1半群与独异点,第7章 半群与群,定义7-2 设U=是一个半群，R是S的子集， RS，若V=也构成一个半群，则称 V是U的子半群。 例如， 是 的子半群， 是 的子半群。,7.1半群与独异点,第7章 半群与群,定理7-1 设U=是一个半群，R是S的子集， RS，若*运算在R上是封闭的，则 V=也是一个半群。 证明 因*

3、运算在S上是可结合的，在R上是封闭的， 且RS，故*运算在R上也是可结合的，根据 定义，V是一个半群。,7.1半群与独异点,第7章 半群与群,定义7-3 若在半群U=中*运算适合交换律， 则称U为可交换半群。 例如，和都是可交换半群， 因为+运算和*运算都满足交换律。,7.1半群与独异点,第7章 半群与群,定义7-4 含有么元的半群称为含么半群或独异点。 例如，U=和V=都是含么半群， 0和1分别是U和V的么元。 但和都不是独异点， 因为在Ev中，+运算和*运算都不存在单位元。 有时为了强调么元e， 常把含么半群表示成。,7.1半群与独异点,第7章 半群与群,定义7-5 设U=是独异点，R是S

4、的子集， RS，若V=也构成独异点，则称 V是U的子独异点。 这里特别强调的是，V的单位元必须和U的单 位元一样，否则的话，即使V能构成一个独异点， 也不能算是U的子独异点。 例如，对于实数集合R、整数集合I、自然数集 合N和普通的加法运算+来说，是一个独异 点，0是单位元，和都是的子独 异点。,7.1半群与独异点,第7章 半群与群,【例7-3】设集合S=e,0,1，*运算的定义如下：,显然，U=是一个独异点，单位元为e。V=也是一个独异点，单位元为1。但V不是U的子独异点，因为V的单位元1不等于的U单位元e。,【例7-4】设V为独异点，e是么元，则是V的一个子独异点；V本身也是V的一个子独异

5、点。这两个子独异点称为平凡子独异点。,7.1半群与独异点,第7章 半群与群,定义7-6 若独异点U=中*运算适合交换律， 则称U为可交换独异点。 例如，对于任意集合S的幂集(S)以及集合间 的“交”、“并”运算来说，U=和 V=都是可交换的独异点，U的么元是S， V的么元是。,7.1半群与独异点,第7章 半群与群,【例7-5】设RS是集合S上所有二元关系的集 合，表示关系的复合运算，则U= 是一个独异点，恒等关系IS是单位元。但 因关系的复合运算不满足交换律，故U不 是可交换的独异点。,7.1半群与独异点,第7章 半群与群,定义7-7 设U=是一个独异点，若存在一个元 素gS，使得对于任意的a

6、S，a都可 表示成g的方幂，即a=gn(n是个非负整 数，当a=e时，n=0)，则称U是一个循环 独异点，并称g是U的一个生成元，这时 的U也可记为U=,*。 例如，对于自然数集合N和通常的加法运算“+” 来说，是一个循环独异点，0是幺元，1是生 成元。,7.1半群与独异点,第7章 半群与群,【例7-6】设U=，S=1,a,b,c,d，*运算的定 义如下：,则从中可以看出，U是一个循环独异点，1是幺元， c是生成元，而且 e = 1 = c0, a = c3, b = c2, c=c1, d = c4。,7.1半群与独异点,第7章 半群与群,定理7-2 每个循环独异点都是可交换的独异点。 证明

7、 设U=是一个循环独异点，且g是它的生 成元，则对于任意的a,bS，由生成 元的定 义有，存在 m,nN，使得： a = gm,b = gn 于是有 a*b = gm*gn = gm+n = gn+m = gn *gm = b*a 所以，U是可交换的独异点，定理得证。,7.1半群与独异点,第7章 半群与群,定理7-3 设U=是一个可交换的独异点，X是S 中全体幂等元的集合，则V=是U的 子独异点。 证明 因为么元e是幂等元，所以，eX。 于是X是S的非空子集且包含U的幺元。 对于任意的a,bX，因为 a*a = a,b*b = b,7.1半群与独异点,第7章 半群与群,且*是可交换的，所以 (

8、a*b)*(a*b) = a*b*b*a = a*b*a = a*a*b = a*b 故a*b也是幂等元，即*运算在X上是封闭的， 所以是U的子独异点。,7.1半群与独异点,第7章 半群与群,定义7-8 设U=和V=都是半群，f:RS 是从R到S的映射，若对于任意的a,bR， 有 f(a*b) = f(a)+f(b) 则称f为从U到V的半群同态，进一步： (1)若f是满射的，则称f为从U到V的半群满同态； (2)若f是单射的，则称f为从U到V的半群单同态； (3)若f是双射的，则称f为从U到V的半群同构。,7.1半群与独异点,第7章 半群与群,定理7-4 设U=和V=都是半群，f是从U 到V的

9、半群同态，对于任意的aR，若a 是U中的幂等元，则f(a)是V中的幂等元。 证明 由于a是U中关于*运算的幂等元， 且f是半群同态，于是有 f(a)=f(a*a)=f(a)+f(a) 这说明f(a)是V中关于+运算的幂等元， 定理得证。,7.1半群与独异点,第7章 半群与群,定义7-9 设U=，V=都是独异点， 又设f:SX是从U到V的映射，若对于任意 的a,bS，有： (1) f(a*b)=f(a)+g(b) (2) f(e*)=e+ 则称f是独异点同态。,7.1半群与独异点,第7章 半群与群,【例7-7】给定两个含么半群U=和 V=，其中，N是自然数集合，+ 是普通加法运算，S=e,0,1

10、，*运算的定 义如下：,7.1半群与独异点,第7章 半群与群,显然，对于任意的a,bN，a0,b0，有： f(a+b)=0 f(a)*f(b)=0*0=0 故 f(a+b)=f(a)*f(b) 因此，f是从U到V的半群同态，但由于 f(0)=1e 所以，f不是独异点同态。,7.1半群与独异点,第7章 半群与群,【例7-8】给定两个独异点U=和 V=，其中，R为实数集合， R+为正实数集合，+,*是普通的 加、乘法运算。定义f:RR+如下： 对于任意的xR， f(x)=2x,7.1半群与独异点,第7章 半群与群,则对于任意的a,bR，有 f(a+b) = 2a+b = 2a*2b = f(a)*

11、f(b) 并且有 f(0) = 20 = 1 所以，f是从U到V的独异点同态。,7.1半群与独异点,第7章 半群与群,定理7-5 设f是从代数系统U=到代数系统 V=的满同态映射，其中，*和+都是 二元运算，则 (1)若U是半群，则V也是半群； (2)若U是独异点，则V也是独异点。,证明 (1)由于f是满射的，故对于任意的x1,x2,x3X， 必存在s1,s2,s3S，使得 x1 = f(s1),x2 = f(s2),x3 = f(s3) 注意到U是半群，+运算适合结合律，,7.1半群与独异点,第7章 半群与群,且f是从U到V的同态映射，于是有 x1*(x2*x3) = f(s1)*(f(s2

12、)*f(s3) = f(s1)*f(s2+s3) = f(s1+(s2+s3) = f(s1+s2)+s3) = f(s1+s2)*f(s3) = (f(s1)*f(s2)*f(s3) = (x1*x2)*x3 这说明*运算适合结合律，所以，V也是半群。,7.1半群与独异点,第7章 半群与群,证明(2) 在(1)基础上，只需证明V存在幺元即可。 设e是U的幺元，下面证明f(e)是V的幺元。 因f是满射的，故对于任意的xX， 必存在sS，使得 x=f(s) 注意到e是U的幺元及f是同态映射，有 x*f(e) = f(s)*f(e)= f(s+e)= f(s)= x 同理可得 f(e)*x = x

13、 这说明f(e)是V中关于*运算的幺元。证毕。,7.1半群与独异点,第7章 半群与群,定理7-6 设U=,V=和W=都是半 群，且函数f:RS，g:ST分别是从U到V 和从V到W的半群同态，则gf是一个从U 到W的半群同态。 证明 对于任意的a,bR，有 (gf)(a*b) = g(f(a*b) = g(f(a)f(b) = g(f(a)g(f(b) = (gf)(a)(gf)(b) 所以，gf是从U到W的半群同态。,7.1半群与独异点,第7章 半群与群,定理7-7 设U=和V=都是半群，则U和 V的积代数UV=也是一个半群。 证明 对于任意的,RS， = 因 *运算在R上是封闭的， +运算在

14、S上是封闭的， 故 r1*r2R,s1+s2S,7.1半群与独异点,第7章 半群与群,于是 RS 所以 运算在RS上是封闭的。 因为U和V都是半群，*运算和+运算都是可结 合的，由定理6-10知，运算是可结合的，所以， 也是一个半群。,7.1半群与独异点,第7章 半群与群,定理7-8 设U=和V=都是独异点， 则U和V的积代数UV=是一个拥 有幺元的独异点。 证明 由定理7-7和定理6-10即可得证。,7.1半群与独异点,第7章 半群与群,【例7-9】给定含幺半群U=，N是自然数 集合，+是通常的加法运算，则 UU=也是一个独异 点，其中的运算定义为：对于任意的 ,NN， = ,7.2 群与子

15、群,第7章 半群与群,定义7-10 给定代数系统U=，S是非空集合，* 是定义在S上的二元运算，若： (1) *运算是可结合的； (2) 存在么元e； (3) 每个元素都可逆。 则称U是一个群。 定义7.10 设U=是一个独异点，若S中的每 个元素都可逆，则称U是一个群。,7.2 群与子群,第7章 半群与群,【例7-10】设有代数系统U=，其中， *运算的定义如下：,容易验证*运算满足结合律，e是幺元，每个 元素都有逆元，并且 e-1=e,a-1=a,b-1=b,c-1=c 因此，U是一个群。,7.2 群与子群,第7章 半群与群,定义7-11 设U=是一个群。若 (1) S为有限集合，则称U为

16、有限群， 若|S|=n，则称U为n阶群； (2) S为无限集合，则称U为无限群。,7.2 群与子群,第7章 半群与群,定理7-9 群中不存在零元。 证明 设U=是任意一个群，当群的阶为1时， 集合S中唯一的一个元素看作是群的幺元。 设|S|1，且存在零元。因零元不存在逆元， 而群中每个元素都必须是可逆的，于是产生矛盾， 所以，群中不存在零元。,7.2 群与子群,第7章 半群与群,定理7-10 幺元是群中唯一的一个幂等元。 证明 对于幺元e，因e2=e，故e是幂等元。 若a也是幂等元，即若a*a=a，则 e = a-1*a = a-1*(a*a) = (a-1*a)*a = e*a = a 这说明e是唯一的幂等元，证毕。,7.2 群与子群,第7章 半群与群,定理7-11 设U=是一个群，则对于任意的 a,bS，有 (1)存在唯一的一个元素xS，使得a*x=b； (2)