半群和群课件.ppt

《半群和群课件.ppt》由会员分享，可在线阅读，更多相关《半群和群课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于半群和群关于半群和群现在学习的是第1页，共55页第一节第一节 半群和独异点半群和独异点半群与群是具有一个二元运算的抽象代数半群与群是具有一个二元运算的抽象代数半群与群在形式语言、快速加法器、纠错码制定等理论中半群与群在形式语言、快速加法器、纠错码制定等理论中有着广泛而有成效的应用有着广泛而有成效的应用现在学习的是第2页，共55页半群和独异点半群和独异点一、半群与独异点的定义一、半群与独异点的定义定义：定义：给定代数给定代数，若若 满足满足，即对任意，即对任意a,b,c S，都有都有a (b c)=(a b)c，则称则称为为半群半群(semigroups)若若为半群，为半群，T S且关于运算

2、且关于运算 封闭，则封闭，则是是的子代数，称为的子代数，称为子半群子半群现在学习的是第3页，共55页半群和独异点半群和独异点定义：定义：给定代数给定代数，若若是半群，且是半群，且，则称则称为为独异点独异点(monoid)，（或含么半群），（或含么半群），通常记作通常记作若若为独异点，为独异点，T S且关于运算且关于运算 封闭，并且封闭，并且e T，则称则称是是的子代数，的子代数，称为称为子独异点子独异点现在学习的是第4页，共55页半群和独异点半群和独异点例例7.1.1 代数代数和和（N是自然数集合，是自然数集合，+和是普通加法和乘和是普通加法和乘法）都是半群法）都是半群并且并且和和都是独异点都

3、是独异点代数代数和和（Z是整数集合，是整数集合，R是实数集合，是实数集合，-是整数减法，是整数减法，/是实数除法）都不是半群是实数除法）都不是半群因为：因为：-和和/都不满足结合律都不满足结合律现在学习的是第5页，共55页半群和独异点半群和独异点代数代数、和和（N是自然数集合，是自然数集合，是普通乘法）都是半群是普通乘法）都是半群并且都是并且都是（R是实数集合）的子半群是实数集合）的子半群和和都是独异点都是独异点并且都是并且都是的子独异点的子独异点 不是独异点，因为它不含关于的么元不是独异点，因为它不含关于的么元现在学习的是第6页，共55页半群和独异点半群和独异点代数代数（*是有限字母集是有限

4、字母集 中字母组成的字母串的集中字母组成的字母串的集合，合，&是连接运算）是半群是连接运算）是半群 是独异点是独异点若若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页半群和独异点半群和独异点定理：若定理：若为独异点，对于任意为独异点，对于任意a,b S，且且a,

6、b均有关均有关于于 的逆元的逆元a-1和和b-1，则则(a-1)-1=aa b有逆元，且有逆元，且(a b)-1=b-1 a-1证明：证明：1)因为因为a-1是是a的逆元，即的逆元，即 a a-1=a-1 a=e，所以所以 a-1 的逆元是的逆元是a，即即(a-1)-1=a2)因为因为 满足结合律，所以满足结合律，所以 (a b)(b-1 a-1)=a (b b-1)a-1=a e a-1=e同理：同理：(b-1 a-1)(a b)=e因此：因此：a b有逆元，且有逆元，且(a b)-1=b-1 a-1现在学习的是第10页，共55页有限半群有限半群二、有限半群二、有限半群定义：定义：是半群，若

7、是半群，若S是有限的，是有限的，称称为为有限半群有限半群定理：若定理：若是有限半群，则是有限半群，则(x)(x S x x=x)即，即，有限半群存在等幂元有限半群存在等幂元（证明见教材（证明见教材P119）现在学习的是第11页，共55页可交换半群可交换半群三、可交换半群三、可交换半群定义：定义：是半群，若是半群，若 是可交换的，是可交换的，称称为为可交换半群可交换半群(commutative semigroups)是独异点，若是独异点，若 是可交换的，是可交换的，称称为为可交换独异点可交换独异点(commutative monoid)现在学习的是第12页，共55页可交换半群可交换半群例例7.1

8、.2 代数代数和和（P(S)是集合是集合S的幂集，的幂集，和和 是是集合上的并运算和交运算）都是可交换半群集合上的并运算和交运算）都是可交换半群并且并且和和都是可交换独异点都是可交换独异点现在学习的是第13页，共55页可交换半群可交换半群定理：定理：是可交换独异点，若是可交换独异点，若P为其等幂元集合，为其等幂元集合，则则为为的子独异点的子独异点证明：对于任意的证明：对于任意的 a,b P，有有a a=a，b b=b，又因为又因为 是可结合和可交换的，所以有是可结合和可交换的，所以有(a b)(a b)=(a a)(b b)=a b P所以所以P对于对于 是是封闭封闭的。的。又因为又因为e P

9、，所以所以为为的子独异点的子独异点现在学习的是第14页，共55页循环半群循环半群四、循环半群四、循环半群定义：定义：是半群，若存在是半群，若存在g S，对于每个对于每个x S，都有相都有相应的自然数应的自然数n，将将x表示成表示成gn，即即x=gn，则则称称g为为的的生成元生成元可以说，元素可以说，元素g生成半群生成半群称称为为循环半群循环半群现在学习的是第15页，共55页循环半群循环半群定义：定义：是独异点，若存在是独异点，若存在g S，对于每个对于每个x S，都有相应都有相应的自然数的自然数n，将将x表示成表示成gn，即即x=gn，且且g0=e称称g为为的的生成元生成元可以说，元素可以说，

10、元素g生成独异点生成独异点称称为为循环独异点循环独异点现在学习的是第16页，共55页循环半群循环半群定理：定理：每个循环独异点都是可交换独异点每个循环独异点都是可交换独异点。证明：证明：设设是循环独异点，是循环独异点，g为其生成元为其生成元对于任意对于任意 a,b S，存在自然数存在自然数m,n，使得使得a=gm，b=gn于是，于是，a b=gm gn=gm+n=gn+m=gn gm=b a所以所以 是可交换的，故是可交换的，故是可交换独异点。是可交换独异点。现在学习的是第17页，共55页循环半群循环半群例例7.1.3 下表给出的代数是个循环独异点，生成元是下表给出的代数是个循环独异点，生成元

11、是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页循环半群循环半群例例7.1.4 （Z+是正整数，是正整数，+是普通加法）是半群是普通加法）是半群取元素取元素6为生成元，可生成循环子半群为生成元，

12、可生成循环子半群如果如果n是自然数呢？是自然数呢？取元素取元素3和和5组成的集合组成的集合3,5，可生成什么样的子半群？可生成什么样的子半群？而这个子半群的生成集是？而这个子半群的生成集是？3,5？1？3,5,6？现在学习的是第20页，共55页循环半群循环半群例例7.1.5 是半群，其中是半群，其中S=a,b,c,d，定义如下表所示，试定义如下表所示，试证明证明:a,b 是是的生成集的生成集abcdadcbabbbbbcccccdabcd解：由表中所示，可知a=ab=bc=a bd=a a并且不可能由比a,b更小的集合来生成半群了所以a,b 是的生成集思考：是否还有其他的生成集？a,c现在学习

13、的是第21页，共55页循环半群循环半群定理：给定半群定理：给定半群，以及任意以及任意 a S则则是是的循环子半群的循环子半群证明：因为证明：因为是半群，因此对于任意是半群，因此对于任意 a S，都有都有 ai S（i 是正整数），则是正整数），则a,a2,a3,S又因为又因为a,a2,a3,对对 是是封闭的封闭的，且，且 满足结合律满足结合律所以所以是是的子半群的子半群可知，可知，a是是的生成元的生成元所以所以是是的循环子半群的循环子半群现在学习的是第22页，共55页第二节第二节 半群和独异点的同态与同构半群和独异点的同态与同构一、半群的同态与同构一、半群的同态与同构定义：定义：给定两个半群给

14、定两个半群和和，若存在函数，若存在函数f:S T，且对于任意且对于任意 x,y S，都有都有f(x y)=f(x)f(y)则称则称f为为到到的的半群同态映射半群同态映射称称同态于同态于，记做记做 现在学习的是第23页，共55页半群的同态与同构半群的同态与同构设设f为为到到的半群同态映射的半群同态映射若若f为单射，称为单射，称f为从为从到到的的半群单一同态映射半群单一同态映射若若f为满射，称为满射，称f为从为从到到的的半群满同态映射半群满同态映射若若f为双射，称为双射，称f为从为从到到的的半群同构映射半群同构映射若若f为为到到的半群同态映射的半群同态映射,称称f为为半群自同态映射半群自同态映射；

15、若若f为为到到的半群同构映射的半群同构映射,称称f为为半群自同构映射半群自同构映射代数结构之间满同态映射保持运算的各种性质代数结构之间满同态映射保持运算的各种性质对于半群满同态也完全适用对于半群满同态也完全适用现在学习的是第24页，共55页半群的同态与同构半群的同态与同构定理：定理：若若f是从是从到到的半群同态映射，对于任意的半群同态映射，对于任意a 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)这个定理能否说明：半群同态保

16、持等幂律？现在学习的是第25页，共55页半群的同态与同构半群的同态与同构定理：若定理：若f是从是从到到的半群同态映射的半群同态映射 g是从是从到到的半群同态映射的半群同态映射 则则g o o f 是从是从到到的半群同态映射的半群同态映射证明：证明：x,y S，有：有：g o o f(x y)=g(f(x y)=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 是函数复合运算，则是函数复合运算，则

17、是半群是半群证明：证明：1)因为因为f为从为从到到的半群自同态映射，的半群自同态映射，所以所以A在在 o o 的作用下是的作用下是封闭封闭的。的。2)又因为函数复合运算又因为函数复合运算 o o 满足结合律，即满足结合律，即 (h o o g)o o f=h o o(g o o f)所以所以是半群是半群现在学习的是第27页，共55页半群的同态与同构半群的同态与同构定理：给定半群定理：给定半群和和其中：其中：SS=f|f为从为从S到到S的所有函数的所有函数，o o 是函数复合运算是函数复合运算则则 证明：定义函数证明：定义函数，a S，则则fa SS。作映射作映射，且且，h(a b)=fa b，

18、a,b S所以：所以：fa b(x)=(a b)x=a (b x)=fa(fb(x)=(fao ofb)(x)所以：所以：h(a b)=fa b=fa o o fb=h(a)o o h(b)所以所以 现在学习的是第28页，共55页独异点的同态与同构独异点的同态与同构二、独异点的同态与同构二、独异点的同态与同构定义：定义：给定独异点给定独异点和和，若存在函数，若存在函数f:S T，且对于任意且对于任意 x,y S，都有都有f(x y)=f(x)f(y)且且 f(es)=eT 则称则称f为为到到的的独异点同态映射独异点同态映射称称同态于同态于 记做记做 现在学习的是第29页，共55页独异点的同态与

19、同构独异点的同态与同构定理：给定独异点定理：给定独异点，则存在则存在T SS，使得使得 证明：证明：1）定义函数）定义函数fa(x)=a x，a S，fa SS。作映射作映射。已经证明已经证明 ，且，且h 是是满射的满射的2）因为）因为是独异点，所以运算表中任意两行或两列都不相是独异点，所以运算表中任意两行或两列都不相同，因此对于任意同，因此对于任意 a,b S，h(a)=fa fb=h(b)所以，所以，h是是单射的单射的因此因此h是双射的是双射的，所以，所以 现在学习的是第30页，共55页第三节第三节 积半群积半群定义：定义：给定两个半群给定两个半群和和，称，称为为和和的的积半群积半群，其中

20、：，其中：ST为为S和和T的笛卡尔积，的笛卡尔积，定义如下：定义如下：=其中，其中，s1,s2 S，t1,t2 T可以证明，可以证明，是半群是半群现在学习的是第31页，共55页积半群积半群定理：给定两个半群定理：给定两个半群和和若若和和是可交换的是可交换的则则也是也是可交换可交换的的若若e1是是的么元，的么元，e2是是的么元的么元则则含有含有么元么元若若s S的逆元是的逆元是s-1，t T的逆元是的逆元是t-1 则则中，中，的逆元是的逆元是现在学习的是第32页，共55页第四节第四节 群群群在抽象代数中具有基本的重要地位：许多代数结构，包括环、域和群在抽象代数中具有基本的重要地位：许多代数结构，

21、包括环、域和模等可以看作是在群的基础上添加新的运算和公理而形成的。模等可以看作是在群的基础上添加新的运算和公理而形成的。群的概念在数学的许多分支都有出现，而且群论的研究方法也对抽象群的概念在数学的许多分支都有出现，而且群论的研究方法也对抽象代数的其它分支有重要影响。代数的其它分支有重要影响。群论在计算机领域有很深的应用，此外，其重要性还体现在物理学和群论在计算机领域有很深的应用，此外，其重要性还体现在物理学和化学的研究中，因为许多不同的物理结构，如晶体结构和氢原子结构化学的研究中，因为许多不同的物理结构，如晶体结构和氢原子结构可以用群论方法来进行建模。可以用群论方法来进行建模。现在学习的是第3

22、3页，共55页群群一、群的定义及性质一、群的定义及性质定义：定义：给定代数结构给定代数结构，若，若 是可结合的，且关于是可结合的，且关于 存存在么元（即在么元（即 是是独异点独异点），且），且S中每个元素关于中每个元素关于 都是都是可逆可逆的，则称的，则称 是是群群(groups)可见，群是独异点的特例可见，群是独异点的特例现在学习的是第34页，共55页群群例例7.4.1有代数有代数和和（其中，其中，Z是整数集合，是整数集合，Q是有理数集合，是有理数集合，+和是普通加法和乘法）和是普通加法和乘法）可知，可知，是独异点（是独异点（+可结合，含么元可结合，含么元0）且对于每个且对于每个x Z，都有

23、逆元都有逆元 x，所以所以是群是群虽然虽然是独异点（可结合，含么元是独异点（可结合，含么元1），但是），但是0无逆元，所以无逆元，所以不是群不是群。而。而是群是群现在学习的是第35页，共55页群群例例7.4.2代数代数是群，是群，0是么元是么元对于对于x Nk，都有逆元都有逆元 k x运算运算max和和min是否能用为群的二元运算？是否能用为群的二元运算？一般不能。因为如果载体多于一个元素，逆运算不能定义一般不能。因为如果载体多于一个元素，逆运算不能定义例如例如，么元是么元是1，那么，那么3的逆元是？的逆元是？现在学习的是第36页，共55页群群定义：给定群定义：给定群若若S是有限集合，则称是有

24、限集合，则称 是是有限群有限群(finite group)且称且称|S|为为的的阶数阶数(order)若若S是无穷的，称是无穷的，称 是是无穷群无穷群(infinite group)例如：群例如：群（Z是整数集合，是整数集合，+是普通加法）是无穷群是普通加法）是无穷群现在学习的是第37页，共55页群的性质群的性质群是半群和独异点的特例，有关半群和独异点的性质在群中也成立。此群是半群和独异点的特例，有关半群和独异点的性质在群中也成立。此外，群还具有以下性质：外，群还具有以下性质：性质性质1：设：设是群，是群，若若|S|1，则则无零元无零元证明：设证明：设为为的零元，的零元，e为为的么元的么元因为

25、因为|S|1，因此因此 e ，因此对于任意因此对于任意x S，都有都有 x=e，因此因此无逆元，这与无逆元，这与是群矛盾是群矛盾现在学习的是第38页，共55页群的性质群的性质性质性质2：设：设是群，则是群，则中唯一的等幂元是么元中唯一的等幂元是么元证明：设有任意等幂元证明：设有任意等幂元a S，即即 a a=a。于是：于是：a=e a=(a-1 a)a=a-1 (a a)=a-1 a=e现在学习的是第39页，共55页群的性质群的性质性质性质3：设：设是群，则对任意是群，则对任意 a,b,c S，有有可约律可约律a b=a c b=cb a=c a b=c 证明：设证明：设e为为的么元，有：的么

26、元，有：a b=a c a-1 (a b)=a-1 (a c)(a-1 a)b=(a-1 a)c e b=e c b=c同理可证：同理可证：b a=c a b=c现在学习的是第40页，共55页群的性质群的性质性质性质4：设：设是群，则对任意是群，则对任意 a,b S，有有存在唯一的元素存在唯一的元素x S，使得使得 a x=b存在唯一的元素存在唯一的元素y S，使得使得 y a=b 证明：设证明：设e为为的么元，令的么元，令 x=a-1 b，有：有：a x=a (a-1 b)=(a a-1)b=e b=b设还存在设还存在 x=c，使得使得 a x=b，则有则有 a x=a c=b=e b=(a

27、 a-1)b=a (a-1 b)因此因此 x=a-1 b，故故x是唯一是唯一的。同理可证的。同理可证 y a=b的解也唯一的解也唯一考虑：该性质说明了对于群的运算表具有什么特点？考虑：该性质说明了对于群的运算表具有什么特点？现在学习的是第41页，共55页群的性质群的性质性质性质5：设：设是群，则对任意是群，则对任意 a,b S，有有(a b)-1=b-1 a-1（P118：定理定理7.1.6曾证明关于独异点的相关定理）曾证明关于独异点的相关定理）证明：设证明：设e为为的么元，有：的么元，有：(a b)(a b)-1=e=a a-1=a e a-1=a (b b-1)a-1=(a b)(b-1

28、a-1)根据可约律，可知：根据可约律，可知：(a b)-1=b-1 a-1现在学习的是第42页，共55页Abel 群群二、二、Abel群群定义：定义：给定群给定群，若，若 是可交换的，是可交换的，则称则称 是是可交换群可交换群，或，或阿贝尔群阿贝尔群(Abel group)现在学习的是第43页，共55页Abel 群群例例7.4.3：代数代数（Z是整数集合，是整数集合，+是一般加法）是是一般加法）是Abel群群代数代数（Q+是正有理数集合，是一般乘法）是是正有理数集合，是一般乘法）是Abel群群设设A是一个集合，是一个集合，P表示表示A上双射函数集合，代数上双射函数集合，代数（o o 表表示函数

29、的复合运算）是群，但通常不是示函数的复合运算）是群，但通常不是Abel群群现在学习的是第44页，共55页Abel 群群定理：给定群定理：给定群，则则为为Abel群的充要条件是：群的充要条件是：对对于任意于任意a,b S 都有都有(a b)2=a2 b2证明：证明：1)充分性充分性若若a,b S 都有都有(a b)2=a2 b2，则有：，则有：(a b)2=a2 b2 (a b)(a b)=(a a)(b b)a (b a)b=a (a b)b b a=a b 即即为为Abel群群现在学习的是第45页，共55页Abel 群群2)必要性必要性若若为为Abel群，则对任意群，则对任意a,b S 有：

30、有：(a b)2=(a b)(a b)=(a a)(b b)=a2 b2证毕证毕现在学习的是第46页，共55页阶阶三、阶三、阶定义：给定群定义：给定群，且且a S，么元是，么元是e若存在若存在最小的正整数最小的正整数n，使得使得an=e则称则称n为为a的的阶阶(order)或周期或周期否则称元素否则称元素a具有具有无限阶无限阶任何群的么元的阶数都是任何群的么元的阶数都是1现在学习的是第47页，共55页阶阶定理：给定群定理：给定群，且且a S 的阶的阶n是有限的，则是有限的，则存在正整数存在正整数m，k=mn，使得使得 ak=e若有若有 ak=e，则则 k=mn，其中其中m是正整数是正整数证明：

31、证明：1)因为因为k=mn，故故 ak=amn=(an)m=em=e2)因为因为 ak=e，于是对于正整数于是对于正整数tn，有有 k=mn+t，m是正整数是正整数因此因此 at=ak-mn=ak a-mn=e (an)-m=(e)-m=e因此有因此有ak=amn+t=amn at=amn e=amn 现在学习的是第48页，共55页阶阶推论：若推论：若 an=e，且不存在且不存在n的因子的因子d使使ad=e，则则n为为a的阶的阶定理：给定群定理：给定群，且且a S 则则a及其逆元及其逆元a-1具有相同的阶具有相同的阶证明：设证明：设a的阶是的阶是n，则则an=e。设设a-1的阶数是的阶数是m。

32、于是有：于是有：(a-1)n=a 1n=(an)-1=(e)-1=e可知：可知：m n。又又 am=(a-1)m)-1=(e)-1=e因为因为a的阶是的阶是n，因此可知因此可知n m，所以所以m=n现在学习的是第49页，共55页阶阶定理：在有限群定理：在有限群中，中，若若|S|=n，则对于任意，则对于任意a S a具有一个有限阶，且阶数至多具有一个有限阶，且阶数至多n证明：对于任意证明：对于任意a S，构成序列：构成序列：a,a2,a3,an+1中，至少有两个中，至少有两个元素是相等的。不妨设元素是相等的。不妨设 ar=as（1 s r n+1）因为：因为：e=a0=ar-r=ar a-r=a

33、r a-s=ar-s 因此，因此，a的阶至多是的阶至多是 r-s (n+1)1=n现在学习的是第50页，共55页群群从群的性质上可以得到以下结论：从群的性质上可以得到以下结论：(将同构的群视为相同的将同构的群视为相同的)一阶群只有一个，如右表所示一阶群只有一个，如右表所示二阶群也只有一个，如右表所示二阶群也只有一个，如右表所示三阶群也只有一个，如右表所示三阶群也只有一个，如右表所示eeeeaeeaaaeeabeeabaabebbea现在学习的是第51页，共55页群群四阶群只有两个，如下表所示四阶群只有两个，如下表所示eabceeabcaabcebbceacceabeabceeabcaaecbb

34、bceaccbae现在学习的是第52页，共55页群群五阶群只有一个，如下表所示五阶群只有一个，如下表所示eabcdeeabcdaabcdebbcdeaccdeabddeabc现在学习的是第53页，共55页群群六阶群只有两个，如下表所示六阶群只有两个，如下表所示eabcdfeeabcdfaabcdfebbcdfeaccdfeabddfeabcffeabcdeabcdfeeabcdfaaedfbcbbfedcaccdfeabddcabfeffbcaed群的性质4：设是群，则对任意 a,b S，有 存在唯一的元素x S，使得 a x=b 存在唯一的元素y S，使得 y a=b该性质说明了对于群的运算表具有什么特点？现在学习的是第54页，共55页感谢大家观看现在学习的是第55页，共55页