离散数学(第15章)陈瑜.ppt

《离散数学(第15章)陈瑜.ppt》由会员分享，可在线阅读，更多相关《离散数学(第15章)陈瑜.ppt（224页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、陈瑜陈瑜Email：2023/5/211计算机科学与工程学院第第15章：章：半群与群半群与群15.1 半群半群2023/5/212023/5/212 2计算机科学与工程学院计算机科学与工程学院n群群是是一一种种特特殊殊的的代代数数系系统统，是是最最重重要要的的代代数数系系统统之之一一。群群的的理理论论广广泛泛应应用用于于数数学学、物物理理、化化学学以以及及很很多多人人们们不不太太熟熟悉悉的的领领域域如如社社会会学学等等。对对计计算算机机科科学学而而言言，群群在在自自动动化化理理论论、形形式式语语言言、语语法法分分析析、编编码码理理论论等等方方面都有直接应用，并显示出其强大功能。面都有直接应用，

2、并显示出其强大功能。n上上一一章章中中已已经经给给出出了了半半群群的的定定义义，它它要要求求运运算算是是可可结结合合的的。许许多多常常见见的的代代数数系系统统都都是是半半群群，甚甚至至是是含含幺幺半半群。下面是一些典型的半群例子。群。下面是一些典型的半群例子。2023/5/212023/5/213 3计算机科学与工程学院计算机科学与工程学院n群群是是一一种种特特殊殊的的代代数数系系统统，是是最最重重要要的的代代数数系系统统之之一一。群群的的理理论论广广泛泛应应用用于于数数学学、物物理理、化化学学以以及及很很多多人人们们不不太太熟熟悉悉的的领领域域如如社社会会学学等等。对对计计算算机机科科学学而

3、而言言，群群在在自自动动化化理理论论、形形式式语语言言、语语法法分分析析、编编码码理理论论等等方方面都有直接应用，并显示出其强大功能。面都有直接应用，并显示出其强大功能。n上上一一章章中中已已经经给给出出了了半半群群的的定定义义，它它要要求求运运算算是是可可结结合合的的。许许多多常常见见的的代代数数系系统统都都是是半半群群，甚甚至至是是含含幺幺半半群。下面是一些典型的半群例子。群。下面是一些典型的半群例子。2023/5/212023/5/214 4计算机科学与工程学院计算机科学与工程学院n例：例：满满足足封封闭闭、可可结结合合、有有幺幺元元0 0的的条条件件，因因而而是是含含幺幺半半群群。另另

4、外外，它它还还满满足足可可换换性性，每每个个元元x xR R都都有加法逆元有加法逆元-x-x，因此，因此，也是一个可换群。也是一个可换群。R,满满足足封封闭闭、可可结结合合、有有幺幺元元1 1，因因此此是是含含幺幺半半群群。注注意意，因因为为0 0无无乘乘法法逆逆元元，所所以以R,只只能能是含幺半群。是含幺半群。2023/5/212023/5/215 5计算机科学与工程学院计算机科学与工程学院n例例 设设M Mm,nm,n表表示示全全休休m m行行n n列列矩矩阵阵构构成成的的集集合合，+是是矩矩阵阵加加法法，那那么么+满满足足封封闭闭、可可结结合合的的条条件件，元元素素全全为为0 0的的m

5、m行行n n列列矩矩阵阵是是幺幺元元，因因此此+是是含含幺幺半群。半群。此此外外，M Mm,nm,n中中每每个个矩矩阵阵A Am,nm,n都都有有加加法法逆逆矩矩阵阵-A-Am,nm,n ，因而，因而 M+还满足逆元条件。还满足逆元条件。2023/5/212023/5/216 6计算机科学与工程学院计算机科学与工程学院n例例 设设F F是是由由定定义义在在非非空空集集合合S S上上的的全全体体函函数数构构成成的的集集合合，即即F=F=f:f:S SSS。对对于于函函数数的的复复合合运运算算“”，F 满足封闭性和可结合性，所以是半群。满足封闭性和可结合性，所以是半群。此此外外，定定义义在在S S

6、上上的的恒恒等等函函数数I Is s是是F 的的幺幺元元，所以所以F 又是含幺半群。又是含幺半群。2023/5/212023/5/217 7计算机科学与工程学院计算机科学与工程学院n例例 设设是是非非空空有有限限字字母母表表，*是是由由定定义义在在上上的的全全体体有有限限长长字字母母串串构构成成的的集集合合，或或叫叫做做上上全全体体字字的的集集合合。在在*上上定定义义运运算算为为字字的的连连接接“”，则则 满满足足封封闭闭和和可可结结合合的的条条件件，并并且且空空字字 是是系系统统的的幺幺元元，所以所以 是一个含幺半群。是一个含幺半群。n半半群群或或含含幺幺半半群群在在计计算算机机科科学学中中

7、有有广广泛泛的的应应用用，尤尤其其在在从从编编译译技技术术发发展展起起来来的的形形式式语语言言与与自自动动机机理理论论领领域域，含含幺幺半半群群是是很很重重要要的的的的内内容容之之一一。下下面面是是半半群群的的一一个个简单的应用例子。简单的应用例子。2023/5/212023/5/218 8计算机科学与工程学院计算机科学与工程学院n例例 设设一一个个简简单单的的液液晶晶显显示示电电子子表表仅仅有有显显示示时时、分分的的两两个个功功能能，有有0 0、1 1两两个个按按键键。按按1 1键键时时由由正正常常状状态态转转入入调调分分状状态态，此此时时按按0 0键键m m次次可可以以调调增增分分数数m

8、m；再再按按1 1键键则则转转入入调调时时状状态态，此此时时按按0 0键键n n次次，则则时时数数增增加加n n；最最后后再再按按1 1键键回回复复到到正正常常状状态态。这这一一调调节节过过程程如如图图 (b)(b)所示。所示。(a)(b)2023/5/212023/5/219 9计算机科学与工程学院计算机科学与工程学院 上面的调分和调时过程可表示为上面的调分和调时过程可表示为 :或或由由符符号号1 1和和0 0组组成成的的形形如如1010m m1010n n1 1的的字字符符串串集集，即即字母表字母表=0=0，11上的一个语言上的一个语言L=10L=10m m1010n n1|m1|m，n0

9、n0。这这种种字字母母串串可可以以被被电电子子表表中中的的微微处处理理器器(可可以以看看成成是是一一个个小小小小的的计计算算机机)识识别别并并执执行行，其其动动作作原原理理就就是是图图15-1.1(b)15-1.1(b)所所示示的的状状态态图图，称称为为一一个个有有限限自自动动机机，它它反反映映了了电电子子表表依依令令而而行行的的规规则则。语语言言L L被被相相应应地地称称为为这这个个自动机所识别的语言。自动机所识别的语言。2023/5/212023/5/211010计算机科学与工程学院计算机科学与工程学院幂幂 设设S,*是是一一个个半半群群,由由于于*满满足足结结合合律律，可定义幂运算，即对

10、可定义幂运算，即对 x x S S，可定义：，可定义：x x=x=x，x x=x*x=x*x，x x=x*x=x*x=x=x*x=x*x*x*x=x*x*x，x xn n=x=xn-1n-1*x=x*x*x=x*xn-1n-1=x*x*x*x=x*x*x*x。如果如果有单位元有单位元e e，可以定义：，可以定义：x x0 0=e=e幂运算有如下的公式：（见下页）幂运算有如下的公式：（见下页）2023/5/212023/5/211111计算机科学与工程学院计算机科学与工程学院n定定理理1 15.1 5.1 设设S*是是半半群群，a a S S，m m和和n n是是正正整整数数，则则：a am m

11、*a*an n=a=am+nm+n；(a(am m)n n=a=amnmn 。当当S*是是含含幺幺半半群时，上述结论对任意非负整数群时，上述结论对任意非负整数m m和和n n都成立。都成立。证明：设证明：设m m是一个固定的正整数，对是一个固定的正整数，对n n进行归纳。进行归纳。对于对于：当当n=1n=1时，由幂的定义可知结论成立；时，由幂的定义可知结论成立；设结论对设结论对n=kn=k时成立，则时成立，则 a am m*a*ak+1 k+1=a=am m*(a*(ak k*a)(*a)(由幂的定义由幂的定义)=(a =(am m*a*ak k)*a ()*a (可结合性）可结合性）=(a

12、=(am+km+k)*a )*a （归纳假设）（归纳假设）=a =am+(k+1)m+(k+1)由归纳法可知，结论成立。由归纳法可知，结论成立。2023/5/212023/5/211212计算机科学与工程学院计算机科学与工程学院n定定理理1 15.1 5.1 设设S*是是半半群群，a a S S，m m和和n n是是正正整整数数，则则：a am m*a*an n=a=am+nm+n；(a(am m)n n=a=amnmn 。当当S*是是含含幺幺半半群时，上述结论对任意非负整数群时，上述结论对任意非负整数m m和和n n都成立。都成立。证明：证明：设设m m是一个固定的正整数，对是一个固定的正整

13、数，对n n进行归纳。进行归纳。对于对于：当当n=1n=1时，由幂的定义可知结论成立；时，由幂的定义可知结论成立；设结论对设结论对n=kn=k时成立，则时成立，则 a am m*a*ak+1 k+1=a=am m*(a*(ak k*a)(*a)(由幂的定义由幂的定义)=(a =(am m*a*ak k)*a ()*a (可结合性）可结合性）=(a =(am+km+k)*a )*a （归纳假设）（归纳假设）=a =am+(k+1)m+(k+1)由归纳法可知，结论成立。由归纳法可知，结论成立。2023/5/212023/5/211313计算机科学与工程学院计算机科学与工程学院n定定理理1 15.1

14、 5.1 设设S*是是半半群群，a a S S，m m和和n n是是正正整整数数，则则：a am m*a*an n=a=am+nm+n；(a(am m)n n=a=amnmn 。当当S*是是含含幺幺半半群时，上述结论对任意非负整数群时，上述结论对任意非负整数m m和和n n都成立。都成立。证明：证明：设设m m是一个固定的正整数，对是一个固定的正整数，对n n进行归纳。进行归纳。对于对于：当当n=1n=1时，由幂的定义可知结论成立；时，由幂的定义可知结论成立；设结论对设结论对n=kn=k时成立，则时成立，则 a am m*a*ak+1 k+1=a=am m*(a*(ak k*a)(*a)(由幂

15、的定义由幂的定义)=(a =(am m*a*ak k)*a ()*a (可结合性）可结合性）=(a =(am+km+k)*a )*a （归纳假设）（归纳假设）=a =am+(k+1)m+(k+1)由归纳法可知，结论成立。由归纳法可知，结论成立。对于对于可以类似的进行归纳证明。可以类似的进行归纳证明。2023/5/212023/5/211414计算机科学与工程学院计算机科学与工程学院n注注意意：当当运运算算为为加加法法“+”+”时时，上上述述定定理理应应写成：写成：ma+na=(m+n)ama+na=(m+n)a n(ma)=(mn)a n(ma)=(mn)a2023/5/212023/5/21

16、1515计算机科学与工程学院计算机科学与工程学院n定理定理1 15.25.2 有限半群有限半群 S S，必有幂等元，即必有幂等元，即 存在存在 a a S S，a a2 2=a=a 。(参见教材参见教材p p183183）注意此处的注意此处的a2的正确含义！的正确含义！a*a=a2,不是数学中的乘法！不是数学中的乘法！2023/5/212023/5/211616计算机科学与工程学院计算机科学与工程学院n定理定理1 15.25.2 有限半群有限半群 S S，必有幂等元，即必有幂等元，即 存在存在 a a S S，a a2 2=a=a 。证明证明：如果：如果S S中有幺元中有幺元 e e，则，则

17、e e 就是幂等元。就是幂等元。如果如果S S中没有幺元，任取中没有幺元，任取 b b S S。由集合。由集合S S的的有限性有限性，必有：，必有：b bi i=b=bj j=b=bj-ij-i b bi i (j i)(j i)所以，对任何所以，对任何t i t i 都有：都有：b bt t=b=bj-ij-i b bt t(注注:t=i+l,b:t=i+l,bt t=b=bi+li+l=b=bi i*b*b1 1)=b =b2(j-i)2(j-i)b bt t =.=.（反复迭代）（反复迭代）=b =bk(j-i)k(j-i)b bt t （此处（此处k(j-i)ik(j-i)i）令令t=

18、k(j-i),t=k(j-i),则得到则得到 b bt t=b=bt t b bt t即即 b bt t是幂等元。是幂等元。2023/5/212023/5/211717计算机科学与工程学院计算机科学与工程学院n定理定理1 15.25.2 有限半群有限半群 S S，必有幂等元，即必有幂等元，即 存在存在 a a S S，a a2 2=a=a 。证明证明：如果如果S S中有幺元中有幺元 e e，则，则 e e 就是幂等元。就是幂等元。如果如果S S中没有幺元，任取中没有幺元，任取 b b S S。由集合。由集合S S的有限性，必有：的有限性，必有：b bi i=b=bj j=b=bj-ij-i b

19、 bi i (j i)(j i)所以，对任何所以，对任何t i t i 都有：都有：b bt t=b=bj-ij-i b bt t(例如例如:t=i+l,b:t=i+l,bt t=b=bi+li+l=b=bi i*b*b1 1)=b=b2(j-i)2(j-i)b bt t =.=.（反复迭代）（反复迭代）=b =bk(j-i)k(j-i)b bt t （此处（此处k(j-i)ik(j-i)i）令令t=k(j-i),t=k(j-i),则得到则得到 b bt t=b=bt t b bt t即即 b bt t是幂等元。是幂等元。2023/5/212023/5/211818计算机科学与工程学院计算机科

20、学与工程学院n定理定理1 15.25.2 有限半群有限半群 S S，必有幂等元，即必有幂等元，即 存在存在 a a S S，a a2 2=a=a 。证明证明：如果如果S S中有幺元中有幺元 e e，则，则 e e 就是幂等元。就是幂等元。如果如果S S中没有幺元，任取中没有幺元，任取 b b S S。由集合。由集合S S的有限性，必有：的有限性，必有：b bi i=b=bj j=b=bj-ij-i b bi i (j i)(j i)所以，对任何所以，对任何t i t i 都有：都有：b bt t=b=bj-ij-i b bt t(例如例如:t=i+l,b:t=i+l,bt t=b=bi+li+

21、l=b=bi i*b*b1 1)=b =b2(j-i)2(j-i)b bt t =.=.（反复迭代）（反复迭代）=b =bk(j-i)k(j-i)b bt t （此处（此处k(j-i)ik(j-i)i）令令t=k(j-i),t=k(j-i),则得到则得到 b bt t=b=bt t b bt t即即 b bt t是幂等元是幂等元。2023/5/212023/5/211919计算机科学与工程学院计算机科学与工程学院n定理定理1 15.25.2 有限半群有限半群 S S，必有幂等元，即必有幂等元，即 存在存在 a a S S，a a2 2=a=a 。证明证明：如果如果S S中有幺元中有幺元 e e

22、，则，则 e e 就是幂等元。就是幂等元。如果如果S S中没有幺元，任取中没有幺元，任取 b b S S。由集合。由集合S S的有限性，必有：的有限性，必有：b bi i=b=bj j=b=bj-ij-i b bi i (j i)(j i)所以，对任何所以，对任何t i t i 都有：都有：b bt t=b=bj-ij-i b bt t(例如例如:t=i+l,b:t=i+l,bt t=b=bi+li+l=b=bi i*b*b1 1)=b =b2(j-i)2(j-i)b bt t =.=.（反复迭代）（反复迭代）=b =bk(j-i)k(j-i)b bt t （此处（此处k(j-i)ik(j-i

23、)i）令令t=k(j-i),t=k(j-i),则得到则得到 b bt t=b=bt t b bt t即即 b bt t是幂等元是幂等元。注注意意，若若S不不是是有有限限集集，则则不不一一定定有有幂幂等等元元。例例如如，正正整整数数集集关关于于加加法法运运算算是是一一个个半半群群，但但是是不不存存在在幂幂等等元元。含含幺幺半半群群至至少少含含有有一一个个幂幂等等元元，那那就就是是幺幺元元。一一个个半半群群甚甚至至含含幺幺半半群群也也可可以以含含有有多多个个幂幂等等元元。不不难难验验证证是是以以S为为幺幺元元的的含含幺幺半半群群。由由于于集集合合交交运运算算是是幂幂等等的的，所所以以中中每每个个元

24、元都都是是幂幂等等元。元。2023/5/212023/5/212020计算机科学与工程学院计算机科学与工程学院子半群子半群n定义定义15.115.1如如果果是是半半群群，T T是是S S的的非非空空子子集集，且且T T对对运运算算*是是封封闭闭的的，则则称称是是半半群群的的子子半半群群；如如果果是是含含幺幺半半群群，TSTS，eTeT，且且T T对对运运算算*是是封封闭闭的的，则则称称是是含含幺幺半半群群的子含幺半群。的子含幺半群。n例例：半半群群R的的子子代代数数0，Z，R都是都是R的子半群。的子半群。2023/5/212023/5/212121计算机科学与工程学院计算机科学与工程学院子半群

25、子半群n定义定义15.115.1如如果果是是半半群群，T T是是S S的的非非空空子子集集，且且T T对对运运算算*是是封封闭闭的的，则则称称是是半半群群的的子子半半群；群；如如果果是是含含幺幺半半群群，TSTS，eTeT，且且T T对对运运算算*是是封封闭闭的的，则则称称是是含含幺幺半半群群的的子含幺半群子含幺半群。n例例：半半群群R的的子子代代数数0，Z，R都是都是R的子半群。的子半群。2023/5/212023/5/212222计算机科学与工程学院计算机科学与工程学院子半群子半群n定义定义15.115.1如如果果是是半半群群，T T是是S S的的非非空空子子集集，且且T T对对运运算算*

26、是是封封闭闭的的，则则称称是是半半群群的的子子半半群；群；如如果果是是含含幺幺半半群群，TSTS，eTeT，且且T T对对运运算算*是是封封闭闭的的，则则称称是是含含幺幺半半群群的子含幺半群。的子含幺半群。n例例：半半群群R的的子子代代数数0，Z，R都是都是R的子半群。的子半群。2023/5/212023/5/212323计算机科学与工程学院计算机科学与工程学院n例例 设设S 是是一一个个可可换换的的含含幺幺半半群群，M M是是它它的的所所有有的的等等幂元构成的集合，则幂元构成的集合，则M 是是S 的一个子含幺半群。的一个子含幺半群。证明：证明：(1)(1)显然，显然，M M S S；(2)(

27、2)S 是是含含幺幺半半群群，所所以以幺幺元元e e存存在在，又又e*ee*ee e，则则e e是一个等幂元，即有是一个等幂元，即有eMeM，所以，所以M M是非空的；是非空的；(3)eM(3)eM；(4)(4)对对 任任 意意 a a，bMbM，有有(a*b)*(a*b)(a*b)*(a*b)a*(b*a)*ba*(b*a)*ba*(a*b)*ba*(a*b)*b(a*a)*(b*b)(a*a)*(b*b)a*ba*b，即运算即运算“*”“*”关于集合关于集合M M是封闭的运算。是封闭的运算。由由(1)(1)、(2)(2)、(3)(3)、(4)(4)知知：M 是是S 的的一一个个子子含含幺半

28、群。幺半群。2023/5/212023/5/212424计算机科学与工程学院计算机科学与工程学院n例例 设设S 是是一一个个可可换换的的含含幺幺半半群群，M M是是它它的的所所有有的的等等幂元构成的集合，则幂元构成的集合，则M 是是S 的一个子含幺半群。的一个子含幺半群。证明：证明：(1)(1)显然，显然，M M S S；(2)(2)S 是是含含幺幺半半群群，所所以以幺幺元元e e存存在在，又又e*ee*ee e，则则e e是一个等幂元，即有是一个等幂元，即有eMeM，所以，所以M M是非空的；是非空的；(3)eM(3)eM；(4)(4)对对 任任 意意 a a，bMbM，有有(a*b)*(a

29、*b)(a*b)*(a*b)a*(b*a)*ba*(b*a)*ba*(a*b)*ba*(a*b)*b(a*a)*(b*b)(a*a)*(b*b)a*ba*b，即运算即运算“*”“*”关于集合关于集合M M是封闭的运算。是封闭的运算。由由(1)(1)、(2)(2)、(3)(3)、(4)(4)知知：M 是是S 的的一一个个子子含含幺半群。幺半群。2023/5/212023/5/212525计算机科学与工程学院计算机科学与工程学院n例例 设设S 是是一一个个可可换换的的含含幺幺半半群群，M M是是它它的的所所有有的的等等幂元构成的集合，则幂元构成的集合，则M 是是S 的一个子含幺半群。的一个子含幺半

30、群。证明：证明：(1)(1)显然，显然，M M S S；(2)(2)S 是是含含幺幺半半群群，所所以以幺幺元元e e存存在在，又又e*ee*ee e，则则e e是一个等幂元，即有是一个等幂元，即有eMeM，所以，所以M M是非空的；是非空的；(3)eM(3)eM；(4)(4)对对 任任 意意 a a，bMbM，有有(a*b)*(a*b)(a*b)*(a*b)a*(b*a)*ba*(b*a)*ba*(a*b)*ba*(a*b)*b(a*a)*(b*b)(a*a)*(b*b)a*ba*b，即运算即运算“*”“*”关于集合关于集合M M是封闭的运算。是封闭的运算。由由(1)(1)、(2)(2)、(3

31、)(3)、(4)(4)知知：M 是是S 的的一一个个子子含含幺半群。幺半群。2023/5/212023/5/212626计算机科学与工程学院计算机科学与工程学院n例例 设设S 是是一一个个可可换换的的含含幺幺半半群群，M M是是它它的的所所有有的的等等幂元构成的集合，则幂元构成的集合，则M 是是S 的一个子含幺半群。的一个子含幺半群。证明：证明：(1)(1)显然，显然，M M S S；(2)(2)S 是是含含幺幺半半群群，所所以以幺幺元元e e存存在在，又又e*ee*ee e，则则e e是一个等幂元，即有是一个等幂元，即有eMeM，所以，所以M M是非空的；是非空的；(3)(3)eM eM；(

32、4)(4)对对 任任 意意 a a，bMbM，有有(a*b)*(a*b)(a*b)*(a*b)a*(b*a)*ba*(b*a)*ba*(a*b)*ba*(a*b)*b(a*a)*(b*b)(a*a)*(b*b)a*ba*b，即运算即运算“*”“*”关于集合关于集合M M是封闭的运算。是封闭的运算。由由(1)(1)、(2)(2)、(3)(3)、(4)(4)知知：M 是是S 的的一一个个子子含含幺半群。幺半群。2023/5/212023/5/212727计算机科学与工程学院计算机科学与工程学院n例例 设设S 是是一一个个可可换换的的含含幺幺半半群群，M M是是它它的的所所有有的的等等幂幂元元构构成

33、成的的集集合合，则则M 是是S 的的一一个个子子含含幺幺半半群。群。证明：证明：(1)(1)显然，显然，M M S S；(2)(2)S 是是含含幺幺半半群群，所所以以幺幺元元e e存存在在，又又e*ee*ee e，则则e e是一个等幂元，即有是一个等幂元，即有eMeM，所以，所以M M是非空的；是非空的；(3)(3)eMeM；(4)(4)对对 任任 意意 a a，bMbM，有有(a*b)*(a*b)(a*b)*(a*b)a*(b*a)*ba*(b*a)*ba*(a*b)*ba*(a*b)*b(a*a)*(b*b)(a*a)*(b*b)a*ba*b，即运算即运算“*”“*”关于集合关于集合M M

34、是封闭的运算。是封闭的运算。由由(1)(1)、(2)(2)、(3)(3)、(4)(4)知知：M 是是S 的的一一个个子子含含幺半群。幺半群。2023/5/212023/5/212828计算机科学与工程学院计算机科学与工程学院习题习题P193 2、4、62023/5/212023/5/212929计算机科学与工程学院计算机科学与工程学院15.2 群和子群群和子群2023/5/212023/5/213030计算机科学与工程学院计算机科学与工程学院主要内容主要内容n一个非常重要的代数系统一个非常重要的代数系统群。群。主要从以下几个方面来介绍：主要从以下几个方面来介绍：1)1)群的概念和基本性质。群的

35、概念和基本性质。2)2)群的子群和性质。群的子群和性质。3)3)群中元素的周期和性质。群中元素的周期和性质。4)4)特特殊殊群群及及其其性性质质，如如交交换换群群（AbelAbel群群）、循循环群。环群。5)5)陪集和拉格郎日定理。陪集和拉格郎日定理。2023/5/212023/5/213131计算机科学与工程学院计算机科学与工程学院 在在14.214.2中中已已经经为为群群下下了了定定义义，把把群群看看成成是是在在含含幺幺半半群群的的基基础础上上加加上上每每元元有有逆逆元元的的条条件件，其其核核心心内内容容可可用用“闭闭、结结、幺幺、逆逆”四四个个字字予予以以概概括括。下下面面是是一一些典型

36、的群的例子。些典型的群的例子。2023/5/212023/5/213232计算机科学与工程学院计算机科学与工程学院n例例：我我们们已已经经知知道道是是含含幺幺半半群群，由由于于每每个个整整数数a a都都有有加加法法逆逆元元-a-a，所所以以是是群群，一般叫做一般叫做整数加群整数加群。同同理理，是是实实数数加加群群，是是有有理理数加群数加群。对对于于数数的的乘乘法法，Z,是是含含幺幺半半群群而而不不是是群群，因因为为整整数数一一般般无无Z Z中中的的乘乘法法逆逆元元。R-是是实实数数乘乘群群，它它的的幺幺元元是是1 1，每每元元的的乘法逆元为乘法逆元为1/a1/a。2023/5/212023/5

37、/213333计算机科学与工程学院计算机科学与工程学院n例例：设设Z Zk k表表示示整整数数集集Z Z上上的的模模k k剩剩余余类类集集合合，即即:Z Zk k=0,1,2,k-1=0,1,2,k-1。在。在Z Zk k上定义运算上定义运算 和和 如下：如下：那那么么，是是群群。这这是是因因为为封封闭闭性性和和可可结结合合性性是是明明显成立的，显成立的，00是幺元，每元是幺元，每元ii的逆元是的逆元是k-ik-i。群群 习惯上又称为习惯上又称为剩余类加群剩余类加群。2023/5/212023/5/213434计算机科学与工程学院计算机科学与工程学院n例例 设设n n个个元元素素的的集集合合A

38、 A上上的的全全体体置置换换构构成成集集合合S Sn n。由由第第6 6章章中中关关于于置置换换的的讨讨论论，S Sn n中中两两个个置置换换的的复复合合仍仍然然是是A A上的一个置换，因而运算是封闭的；上的一个置换，因而运算是封闭的；其其次次，由由于于函函数数的的复复合合是是可可结结合合的的，因因而而置置换换的的复复合合也也是是可可结结合合的的；在在S Sn n中中存存在在幺幺置置换换 =(1)=(1)，使使对对任任何何S Sn n中中的的置置换换 均均有有 ，因因而而 =(1)=(1)是是幺幺元元；把把每每个个元元素素的的x x变变成成y y的的置置换换，其其逆逆置置换换则则把把元元素素y

39、 y变变成成x x，因因而而每每个个置置换换都都有有逆逆。由由此此可可知知，构构成成群群，这这个个群群一一般般称称为为n n次次对对称称群群，是是一一类类重重要的群。要的群。n群群尽尽管管是是用用“闭闭、结结、幺幺、逆逆”四四个个条条件件来来定定义义的的，但是它还可以用别的形式等价地定义。但是它还可以用别的形式等价地定义。2023/5/212023/5/213535计算机科学与工程学院计算机科学与工程学院n例例 设设n n个个元元素素的的集集合合A A上上的的全全体体置置换换构构成成集集合合S Sn n。由由第第6 6章章中中关关于于置置换换的的讨讨论论，S Sn n中中两两个个置置换换的的复

40、复合合仍仍然然是是A A上上的一个置换，因而运算是封闭的；的一个置换，因而运算是封闭的；其其次次，由由于于函函数数的的复复合合是是可可结结合合的的，因因而而置置换换的的复复合合也也是是可可结结合合的的；在在S Sn n中中存存在在幺幺置置换换 =(1)=(1)，使使对对任任何何S Sn n中中的的置置换换 均均有有 ，因因而而 =(1)=(1)是是幺幺元元；把把每每个个元元素素的的x x变变成成y y的的置置换换，其其逆逆置置换换则则把把元元素素y y变变成成x x，因因而而每每个个置置换换都都有有逆逆。由由此此可可知知，构成群，这个群一般称为构成群，这个群一般称为n n次对称群，是一类重要的

41、群。次对称群，是一类重要的群。n群群尽尽管管是是用用“闭闭、结结、幺幺、逆逆”四四个个条条件件来来定定义义的的，但是它还可以用别的形式等价地定义。但是它还可以用别的形式等价地定义。2023/5/212023/5/213636计算机科学与工程学院计算机科学与工程学院群群n定定理理15-2.1 15-2.1 如如果果是是半半群群，并并且且对对 a a，b b G G，都都存存在在x x，y y G G 使使x*a=bx*a=b，a*y=ba*y=b，则则是是群群。群群中中元元素的数目称为素的数目称为群的阶群的阶。证明：证明：设设 a a G G，方程，方程 x*a=a x*a=a 的解为的解为e

42、e1 1，对对 t t G G，方程方程 a*y=t a*y=t 有解有解y y0 0，e e1 1*t=e*t=e1 1*（a*ya*y0 0）=（e e1 1*a*a）*y y0 0=a*y=a*y0 0=t=t 即对即对 t t G G，必有，必有e e1 1*t=t*t=t，e e1 1是是G G中的左幺元。中的左幺元。同样可以证明同样可以证明G G中有右幺元中有右幺元e e2 2，所以，所以G G中有幺元中有幺元e e。同同理理，对对 b b G G，方方程程x*b=ex*b=e有有解解x x0 0，这这个个x x0 0是是b b的的左左逆逆元元，方方程程b*y=eb*y=e的的解解

43、是是b b的的右右逆逆元元，从从而而b b有有逆逆元元。所所以以，是群。是群。2023/5/212023/5/213737计算机科学与工程学院计算机科学与工程学院群群n定定理理15.3 15.3 如如果果是是半半群群，并并且且对对 a a，b b G G，都都存存在在x x，y y G G 使使x*a=bx*a=b，a*y=ba*y=b，则则是是群群。群群中中元元素素的数目称为群的阶。的数目称为群的阶。证明：证明：设设 a a G G，方程，方程 x*a=a x*a=a 的解为的解为e e1 1，对对 t t G G，方程方程 a*y=t a*y=t 有解有解y y0 0，e e1 1*t=e

44、*t=e1 1*（a*ya*y0 0）=（e e1 1*a*a）*y y0 0=a*y=a*y0 0=t=t 即对即对 t t G G，必有，必有e e1 1*t=t*t=t，e e1 1是是G G中的左幺元。中的左幺元。同样可以证明同样可以证明G G中有右幺元中有右幺元e e2 2，所以，所以G G中有幺元中有幺元e e。同同理理，对对 b b G G，方方程程x*b=ex*b=e有有解解x x0 0，这这个个x x0 0是是b b的的左左逆逆元元，方方程程b*y=eb*y=e的的解解是是b b的的右右逆逆元元，从从而而b b有有逆逆元元。所所以以，是群。是群。2023/5/212023/5

45、/213838计算机科学与工程学院计算机科学与工程学院群群n定定理理15.3 15.3 如如果果是是半半群群，并并且且对对 a a，b b G G，都都存存在在x x，y y G G 使使x*a=bx*a=b，a*y=ba*y=b，则则是是群群。群群中中元元素素的数目称为群的阶。的数目称为群的阶。证明：证明：设设 a a G G，方程，方程 x*a=a x*a=a 的解为的解为e e1 1，对对 t t G G，方程方程 a*y=t a*y=t 有解有解y y0 0，e e1 1*t=e*t=e1 1*（a*ya*y0 0）=（e e1 1*a*a）*y y0 0=a*y=a*y0 0=t=t

46、 即对即对 t t G G，必有，必有e e1 1*t=t*t=t，e e1 1是是G G中的左幺元。中的左幺元。同样可以证明同样可以证明G G中有右幺元中有右幺元e e2 2，所以，所以G G中有幺元中有幺元e e。同同理理，对对 b b G G，方方程程x*b=ex*b=e有有解解x x0 0，这这个个x x0 0是是b b的的左左逆逆元元，方方程程b*y=eb*y=e的的解解是是b b的的右右逆逆元元，从从而而b b有有逆逆元元。所所以以，是群。是群。2023/5/212023/5/213939计算机科学与工程学院计算机科学与工程学院群群n定定理理15.3 15.3 如如果果是是半半群群

47、，并并且且对对 a a，b b G G，都都存存在在x x，y y G G 使使x*a=bx*a=b，a*y=ba*y=b，则则是是群群。群群中中元元素素的数目称为群的阶。的数目称为群的阶。证明：证明：设设 a a G G，方程，方程 x*a=a x*a=a 的解为的解为e e1 1，对对 t t G G，方程方程 a*y=t a*y=t 有解有解y y0 0，e e1 1*t=e*t=e1 1*（a*ya*y0 0）=（e e1 1*a*a）*y y0 0=a*y=a*y0 0=t=t 即对即对 t t G G，必有，必有e e1 1*t=t*t=t，e e1 1是是G G中的左幺元。中的左

48、幺元。同样可以证明同样可以证明G G中有右幺元中有右幺元e e2 2，所以，所以G G中有幺元中有幺元e e。同同理理，对对 b b G G，方方程程x*b=ex*b=e有有解解x x0 0，这这个个x x0 0是是b b的的左左逆逆元元，方方程程b*y=eb*y=e的的解解是是b b的的右右逆逆元元，从从而而b b有有逆逆元元。所所以以，是群。是群。2023/5/212023/5/214040计算机科学与工程学院计算机科学与工程学院群群n定定理理15.3 15.3 如如果果是是半半群群，并并且且对对 a a，b b G G，都都存存在在x x，y y G G 使使x*a=bx*a=b，a*y

49、=ba*y=b，则则是是群群。群群中中元元素素的数目称为群的阶。的数目称为群的阶。证明：证明：设设 a a G G，方程，方程 x*a=a x*a=a 的解为的解为e e1 1，对对 t t G G，方程方程 a*y=t a*y=t 有解有解y y0 0，e e1 1*t=e*t=e1 1*（a*ya*y0 0）=（e e1 1*a*a）*y y0 0=a*y=a*y0 0=t=t 即对即对 t t G G，必有，必有e e1 1*t=t*t=t，e e1 1是是G G中的左幺元。中的左幺元。同样可以证明同样可以证明G G中有右幺元中有右幺元e e2 2，所以，所以G G中有幺元中有幺元e e

50、。同同理理，对对 b b G G，方方程程x*b=ex*b=e有有解解x x0 0，这这个个x x0 0是是b b的的左左逆逆元元，方方程程b*y=eb*y=e的的解解是是b b的的右右逆逆元元，从从而而b b有有逆逆元元。所所以以，是群。是群。这个定理说明，在群的定义中幺元及逆元的条件可用这个定理说明，在群的定义中幺元及逆元的条件可用方程有解来代替。方程有解来代替。另外，另外，群定义中的幺元条件可以用存在左幺元群定义中的幺元条件可以用存在左幺元(或右幺元或右幺元)的条的条件代替，逆元的条件可以用左逆元件代替，逆元的条件可以用左逆元(或右逆元或右逆元)代替。代替。2023/5/212023/5