半群和群精选PPT.ppt
《半群和群精选PPT.ppt》由会员分享,可在线阅读,更多相关《半群和群精选PPT.ppt(55页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、关于半群和群关于半群和群第1页,讲稿共55张,创作于星期日第一节第一节 半群和独异点半群和独异点半群与群是具有一个二元运算的抽象代数半群与群是具有一个二元运算的抽象代数半群与群在形式语言、快速加法器、纠错码制定等理论中半群与群在形式语言、快速加法器、纠错码制定等理论中有着广泛而有成效的应用有着广泛而有成效的应用第2页,讲稿共55张,创作于星期日半群和独异点半群和独异点一、半群与独异点的定义一、半群与独异点的定义定义:定义:给定代数给定代数,若若满足满足结合律结合律结合律结合律,即对任意,即对任意a,b,c S,都有都有a(bc)=(ab)c,则称则称为为半群半群(semigroups)若若为半
2、群,为半群,T S且关于运算且关于运算封闭,则封闭,则是是的子代数,称为的子代数,称为子半群子半群第3页,讲稿共55张,创作于星期日半群和独异点半群和独异点定义:定义:给定代数给定代数,若若是半群,且是半群,且存在么元存在么元存在么元存在么元e e,则称则称为为独异点独异点(monoid),(或含么半群),(或含么半群),通常记作通常记作若若为独异点,为独异点,T S且关于运算且关于运算封闭,并且封闭,并且e T,则称则称是是的子代数,的子代数,称为称为子独异点子独异点第4页,讲稿共55张,创作于星期日半群和独异点半群和独异点例例7.1.1 代数代数和和(N是自然数集合,是自然数集合,+和和是
3、普通加法是普通加法和乘法)都是半群和乘法)都是半群并且并且和和都是独异点都是独异点代数代数和和(Z是整数集合,是整数集合,R是实数集合,是实数集合,-是整数减法,是整数减法,/是实数除法)都不是半群是实数除法)都不是半群因为:因为:-和和/都不满足结合律都不满足结合律第5页,讲稿共55张,创作于星期日半群和独异点半群和独异点代数代数、和和(N是自然数集合,是自然数集合,是普通乘法)都是半群是普通乘法)都是半群并且都是并且都是(R是实数集合)的子半群是实数集合)的子半群和和都是独异点都是独异点并且都是并且都是的子独异点的子独异点 不是独异点,因为它不含关于不是独异点,因为它不含关于的么元的么元第
4、6页,讲稿共55张,创作于星期日半群和独异点半群和独异点代数代数(*是有限字母集是有限字母集 中字母组成的字母串的集中字母组成的字母串的集合,合,&是连接运算)是半群是连接运算)是半群 是独异点是独异点若若A ,A*是是A中字母组成的字母串集合中字母组成的字母串集合则则是是的子半群的子半群且且是是的子独异点的子独异点第7页,讲稿共55张,创作于星期日半群和独异点半群和独异点若若是独异点,那它一定是半群是独异点,那它一定是半群若若是半群,它却不一定是独异点,因为有的半群没有么是半群,它却不一定是独异点,因为有的半群没有么元。元。例如:例如:中没有关于加法的么元,中没有关于加法的么元,因此它只是半
5、群而不是独异点因此它只是半群而不是独异点常用添加元素的办法,把一个没有么元的半群改造成独异点常用添加元素的办法,把一个没有么元的半群改造成独异点例如例如就成了独异点就成了独异点第8页,讲稿共55张,创作于星期日半群和独异点半群和独异点定理:定理:若若为独异点,则关于为独异点,则关于的运算表中的任意两行的运算表中的任意两行或两列均不相同或两列均不相同证明:因为对于任意的证明:因为对于任意的a,b S,且且a b时,总有时,总有a e=a b=b e 因此没有任意两行是相同的因此没有任意两行是相同的e a=a b=e b 因此没有任意两列是相同的因此没有任意两列是相同的第9页,讲稿共55张,创作于
6、星期日半群和独异点半群和独异点定理:若定理:若为独异点,对于任意为独异点,对于任意a,b S,且且a,b均有关于均有关于的逆元的逆元a-1和和b-1,则则(a-1)-1=aab有逆元,且有逆元,且(ab)-1=b-1 a-1证明:证明:1)因为因为a-1是是a的逆元,即的逆元,即 aa-1=a-1 a=e,所以所以 a-1 的逆元是的逆元是a,即即(a-1)-1=a2)因为因为满足结合律,所以满足结合律,所以 (ab)(b-1a-1)=a(bb-1)a-1=aea-1=e同理:同理:(b-1a-1)(ab)=e因此:因此:ab有逆元,且有逆元,且(ab)-1=b-1 a-1第10页,讲稿共55
7、张,创作于星期日有限半群有限半群二、有限半群二、有限半群定义:定义:是半群,若是半群,若S是有限的,是有限的,称称为为有限半群有限半群定理:若定理:若是有限半群,则是有限半群,则(x)(x S xx=x)即,即,有限半群存在等幂元有限半群存在等幂元(证明见教材(证明见教材P119)第11页,讲稿共55张,创作于星期日可交换半群可交换半群三、可交换半群三、可交换半群定义:定义:是半群,若是半群,若是可交换的,是可交换的,称称为为可交换半群可交换半群(commutative semigroups)是独异点,若是独异点,若是可交换的,是可交换的,称称为为可交换独异点可交换独异点(commutativ
8、e monoid)第12页,讲稿共55张,创作于星期日可交换半群可交换半群例例7.1.2 代数代数和和(P(S)是集合是集合S的幂集,的幂集,和和 是集合上的并运算和交运算)都是可交换半群是集合上的并运算和交运算)都是可交换半群并且并且和和都是可交换独异点都是可交换独异点第13页,讲稿共55张,创作于星期日可交换半群可交换半群定理:定理:是可交换独异点,若是可交换独异点,若P为其等幂元集合,为其等幂元集合,则则为为的子独异点的子独异点证明:对于任意的证明:对于任意的 a,b P,有有a a=a,b b=b,又因为又因为是可结合和可交换的,所以有是可结合和可交换的,所以有(ab)(ab)=(aa
9、)(bb)=ab P所以所以P对于对于是是封闭封闭的。的。又因为又因为e P,所以所以为为的子独异点的子独异点第14页,讲稿共55张,创作于星期日循环半群循环半群四、循环半群四、循环半群定义:定义:是半群,若存在是半群,若存在g S,对于每个对于每个x S,都有相都有相应的自然数应的自然数n,将将x表示成表示成gn,即即x=gn,则则称称g为为的的生成元生成元可以说,元素可以说,元素g生成半群生成半群称称为为循环半群循环半群第15页,讲稿共55张,创作于星期日循环半群循环半群定义:定义:是独异点,若存在是独异点,若存在g S,对于每个对于每个x S,都有相都有相应的自然数应的自然数n,将将x表
10、示成表示成gn,即即x=gn,且且g0=e称称g为为的的生成元生成元可以说,元素可以说,元素g生成独异点生成独异点称称为为循环独异点循环独异点第16页,讲稿共55张,创作于星期日循环半群循环半群定理:定理:每个循环独异点都是可交换独异点每个循环独异点都是可交换独异点。证明:证明:设设是循环独异点,是循环独异点,g为其生成元为其生成元对于任意对于任意 a,b S,存在自然数存在自然数m,n,使得使得a=gm,b=gn于是,于是,ab=gmgn=gm+n=gn+m=gngm=ba所以所以是可交换的,故是可交换的,故是可交换独异点。是可交换独异点。第17页,讲稿共55张,创作于星期日循环半群循环半群
11、例例7.1.3 下表给出的代数是个循环独异点,生成元是下表给出的代数是个循环独异点,生成元是dabcdaabcdbbadcccdbaddcab因为因为d=dd2=b d3=c d4=a生成元也可以是生成元也可以是c,但不是但不是a或或b第18页,讲稿共55张,创作于星期日循环半群循环半群定义:给定半群定义:给定半群,以及以及G S,若若S中的所有元素,都可以由中的所有元素,都可以由G中元素经过中元素经过运算而得运算而得并且并且G是最小的这样的集合是最小的这样的集合则称则称G为为的的生成集生成集,即,即(a)(a S a=(G)min|G|第19页,讲稿共55张,创作于星期日循环半群循环半群例例
12、7.1.4 (Z+是正整数,是正整数,+是普通加法)是半群是普通加法)是半群取元素取元素6为生成元,可生成循环子半群为生成元,可生成循环子半群如果如果n是自然数呢?是自然数呢?取元素取元素3和和5组成的集合组成的集合3,5,可生成什么样的子半群?可生成什么样的子半群?而这个子半群的生成集是?而这个子半群的生成集是?3,5?1?3,5,6?第20页,讲稿共55张,创作于星期日循环半群循环半群例例7.1.5 是半群,其中是半群,其中S=a,b,c,d,定义如下表所示,定义如下表所示,试证明试证明:a,b 是是的生成集的生成集abcdadcbabbbbbcccccdabcd解:由表中所示,可知解:由
13、表中所示,可知a=ab=bc=a bd=a a并且不可能由比并且不可能由比a,b更小的集合来生成半群更小的集合来生成半群了了所以所以a,b 是是的生成集的生成集思考:思考:是否还有其他的生成集?是否还有其他的生成集?a,c第21页,讲稿共55张,创作于星期日循环半群循环半群定理:给定半群定理:给定半群,以及任意以及任意 a S则则是是的循环子半群的循环子半群证明:因为证明:因为是半群,因此对于任意是半群,因此对于任意 a S,都有都有 ai S(i 是正整数),则是正整数),则a,a2,a3,S又因为又因为a,a2,a3,对对是是封闭的封闭的,且,且满足结合律满足结合律所以所以是是的子半群的子
14、半群可知,可知,a是是的生成元的生成元所以所以是是的循环子半群的循环子半群第22页,讲稿共55张,创作于星期日第二节第二节 半群和独异点的同态与同构半群和独异点的同态与同构一、半群的同态与同构一、半群的同态与同构定义:定义:给定两个半群给定两个半群和和,若存在函数,若存在函数f:S T,且对于任意且对于任意 x,y S,都有都有f(xy)=f(x)f(y)则称则称f为为到到的的半群同态映射半群同态映射称称同态于同态于,记做记做 第23页,讲稿共55张,创作于星期日半群的同态与同构半群的同态与同构设设f为为到到的半群同态映射的半群同态映射若若f为单射,称为单射,称f为从为从到到的的半群单一同态映
15、射半群单一同态映射若若f为满射,称为满射,称f为从为从到到的的半群满同态映射半群满同态映射若若f为双射,称为双射,称f为从为从到到的的半群同构映射半群同构映射若若f为为到到的半群同态映射的半群同态映射,称称f为为半群自同态映射半群自同态映射;若若f为为到到的半群同构映射的半群同构映射,称称f为为半群自同构映射半群自同构映射代数结构之间满同态映射保持运算的各种性质代数结构之间满同态映射保持运算的各种性质对于半群满同态也完全适用对于半群满同态也完全适用第24页,讲稿共55张,创作于星期日半群的同态与同构半群的同态与同构定理:定理:若若f是从是从到到的半群同态映射,对于任意的半群同态映射,对于任意a
16、 S 有有 a a=a,则有:则有:f(a)f(a)=f(a)证明:因为证明:因为f是从是从到到的半群同态映射,对于任意的半群同态映射,对于任意a S且且 a a=a,都有:都有:f(a)=f(a a)=f(a)f(a)这个定理能否说明:这个定理能否说明:半群同态保持等幂律?半群同态保持等幂律?第25页,讲稿共55张,创作于星期日半群的同态与同构半群的同态与同构定理:若定理:若f是从是从到到的半群同态映射的半群同态映射 g是从是从到到的半群同态映射的半群同态映射 则则g o o f 是从是从到到的半群同态映射的半群同态映射证明:证明:x,y S,有:有:g o o f(x y)=g(f(x y
17、)=g(f(x)f(y)=g(f(x)g(f(y)=g o o f(x)g o o f(y)第26页,讲稿共55张,创作于星期日半群的同态与同构半群的同态与同构定理:给定半群定理:给定半群若若 A=f|f为从为从到到的半群自同态映射的半群自同态映射且且 o o 是函数复合运算,则是函数复合运算,则是半群是半群证明:证明:1)因为因为f为从为从到到的半群自同态映射,的半群自同态映射,所以所以A在在 o o 的作用下是的作用下是封闭封闭的。的。2)又因为函数复合运算又因为函数复合运算 o o 满足结合律,即满足结合律,即 (h o o g)o o f=h o o(g o o f)所以所以是半群是半
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精选 PPT
限制150内