离散数学第151156陈瑜

单击此处编辑母版标题样式,*,计算机学院,*,/226,陈瑜,Email,：,yu,chen,11/28/2024,离散数学,计算机学院,第,15,章： 半群与群,15.1,半群,11/28/2024,2,计算机学院,群是一种特殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。,上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。,11/28/2024,3,计算机学院,群是一种特殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。,上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。,11/28/2024,4,计算机学院,例：,满足封闭、可结合、有幺元,0,的条件，因而是含幺半群。另外，它还满足可换性，每个元,x,R,都有加法逆元,-x,，因此，,也是一个可换群。,满足封闭、可结合、有幺元,1,，因此是含幺半群。注意，因为,0,无乘法逆元，所以,只能是含幺半群。,11/28/2024,5,计算机学院,例,设,M,m,n,表示全休,m,行,n,列矩阵构成的,集合,，,+,是矩阵加法，那么,满足封闭、可结合的条件，元素全为,0,的,m,行,n,列矩阵是幺元，因此,是含幺半群。,此外，,M,m,n,中每个矩阵,A,m,n,都有加法逆矩阵,-,A,m,n,，因而,还满足逆元条件。,11/28/2024,6,计算机学院,例,设,F,是由定义在非空集合,S,上的全体函数构成的集合，即,F= f: S,S,。对于函数的复合运算“,”,，,满足封闭性和可结合性，所以是半群。,此外，定义在,S,上的恒等函数,I,s,是,的幺元，所以,又是含幺半群。,11/28/2024,7,计算机学院,例,设是非空有限字母表，,*,是由定义在上的全体有限长字母串构成的集合，或叫做上全体字的集合。在,*,上定义运算为字的连接“,”，则,满足封闭和可结合的条件，并且空字 是系统的幺元，所以,是一个含幺半群。,半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。,11/28/2024,8,计算机学院,例,设是非空有限字母表，,*,是由定义在上的全体有限长字母串构成的集合，或叫做上全体字的集合。在,*,上定义运算为字的连接“,”，则,满足封闭和可结合的条件，并且空字 是系统的幺元，所以,是一个含幺半群。,半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。,11/28/2024,9,计算机学院,例,设一个简单的液晶显示电子表仅有显示时、分的两个功能，有,0,、,1,两个按键。按,1,键时由正常状态转入调分状态，此时按,0,键,m,次可以调增分数,m,；再按,1,键则转入调时状态，此时按,0,键,n,次，则时数增加,n,；最后再按,1,键回复到正常状态。这一调节过程如图,(b),所示。,(a),(b),11/28/2024,10,计算机学院,上面的调分和调时过程可表示为,:,或由符号,1,和,0,组成的形如,1,0,m,1,0,n,1,的字符串集，即字母表,=0,，,1,上的一个语言,L=1,0,m,1,0,n,1 |m,，,n0,。,这种字母串可以被电子表中的微处理器,(,可以看成是一个小小的计算机,),识别并执行，其动作原理就是图,15-1.1(b),所示的状态图，称为一个,有限自动机,，它反映了电子表依令而行的规则。语言,L,被相应地称为这个自动机所识别的语言。,11/28/2024,11,计算机学院,幂,设,是一个半群,由于,*,满足结合律，可定义幂运算，即,对,x,S,，可定义：,x,=x,，,x,=x*x,，,x,=x*,x,=,x,*x=x*x*x,，,x,n,=,x,n-1,*x=x*,x,n-1,=x*x*x*,*x,。,如果,有单位元,e,，,可以定义：,x,0,=e,幂运算有如下的公式：（见下页）,11/28/2024,12,计算机学院,定理,1,5-1.1,设,是半群，,a,S,，,m,和,n,是正整数，则：,a,m,*a,n,=,a,m+n,；,(,a,m,),n,=,a,mn,。当,是含幺半群时，上述结论对任意非负整数,m,和,n,都成立。,证明：设,m,是一个固定的正整数，对,n,进行归纳。,对于,：,当,n=1,时，由幂的定义可知结论成立；,设结论对,n=k,时成立，则,a,m,*a,k+1,= a,m,*(,a,k,*a) (,由幂的定义,),= (a,m,*,a,k,)*a (,可结合性）,= (,a,m+k,)*a,（归纳假设）,= a,m+(k+1),由归纳法可知，结论成立。,11/28/2024,13,计算机学院,定理,1,5-1.1,设,是半群，,a,S,，,m,和,n,是正整数，则：,a,m,*a,n,=,a,m+n,；,(,a,m,),n,=,a,mn,。当,是含幺半群时，上述结论对任意非负整数,m,和,n,都成立。,证明：,设,m,是一个固定的正整数，对,n,进行归纳。,对于,：,当,n=1,时，由幂的定义可知结论成立；,设结论对,n=k,时成立，则,a,m,*a,k+1,= a,m,*(,a,k,*a) (,由幂的定义,),= (a,m,*,a,k,)*a (,可结合性）,= (,a,m+k,)*a,（归纳假设）,= a,m+(k+1),由归纳法可知，结论成立。,11/28/2024,14,计算机学院,定理,1,5-1.1,设,是半群，,a,S,，,m,和,n,是正整数，则：,a,m,*a,n,=,a,m+n,；,(,a,m,),n,=,a,mn,。当,是含幺半群时，上述结论对任意非负整数,m,和,n,都成立。,证明：,设,m,是一个固定的正整数，对,n,进行归纳。,对于,：,当,n=1,时，由幂的定义可知结论成立；,设结论对,n=k,时成立，则,a,m,*a,k+1,= a,m,*(,a,k,*a) (,由幂的定义,),= (a,m,*,a,k,)*a (,可结合性）,= (,a,m+k,)*a,（归纳假设）,= a,m+(k+1),由归纳法可知，结论成立。,对于,可以类似的进行归纳证明。,11/28/2024,15,计算机学院,注意：,当运算为加法,“,+,”,时，上述定理应写成：,ma+na,=(,m+n)a,n(ma,)=(,mn)a,11/28/2024,16,计算机学院,定理,1,5-1.2,设,是半群，如果,S,是,有限集,，则必有,a,S,，使得,a,2,=a,。,(,参见教材,p277,）,证明：,因为,是半群，,S,是有限集，对,bS,，则元素,b,1,，,b,2,，,b,3,，,中必有重复的，设,b,i,=,b,j,，其中,j,i,，由,b,i,=,b,j-i,*b,i,，则对,ti,都得到,b,t,=,b,j-i,*,b,t,。,反复利用上式，则对任何正整数,k,1,，有,b,t,=,b,k,（,j-i,）,*,b,t,，（,ti,）。特别，取,k,使得,k(j-i,),i,，同时令,t=,k(j-i,),，则得到幂等元。,注意此处的,a,2,的正确含义！,a*a=a,2,不是数学中的乘法！,11/28/2024,17,计算机学院,定理,1,5-1.2,设,是半群，如果,S,是有限集，则必有,a,S,，使得,a,2,=a,。,(,参见教材,p277,）,证明：,因为,是半群，,S,是有限集,，对,bS,，则元素,b,1,，,b,2,，,b,3,，,中必有重复的，设,b,i,=,b,j,，其中,j,i,。,由,b,i,=,b,j-i,*b,i,，则对,ti,都得到,b,t,=,b,j-i,*,b,t,。,反复利用上式，则对任何正整数,k,1,，有,b,t,=,b,k,（,j-i,）,*,b,t,，（,ti,）。特别，取,k,使得,k(j-i,),i,，同时令,t=,k(j-i,),，则得到幂等元。,11/28/2024,18,计算机学院,定理,1,5-1.2,设,是半群，如果,S,是有限集，则必有,a,S,，使得,a,2,=a,。,(,参见教材,p277,）,证明：,因为,是半群，,S,是有限集，对,bS,，则元素,b,1,，,b,2,，,b,3,，,中必有重复的，设,b,i,=,b,j,，其中,j,i,。,由,b,i,=,b,j-i,*b,i,，则对,ti,都得到,b,t,=,b,j-i,*,b,t,。,反复利用上式，则对任何正整数,k,1,，有,b,t,=,b,k,（,j-i,）,*,b,t,，（,ti,）。特别，取,k,使得,k(j-i,),i,，同时令,t=,k(j-i,),，则得到幂等元。,11/28/2024,19,计算机学院,定理,1,5-1.2,设,是半群，如果,S,是有限集，则必有,a,S,，使得,a,2,=a,。,(,参见教材,p277,）,证明：,因为,是半群，,S,是有限集，对,bS,，则元素,b,1,，,b,2,，,b,3,，,中必有重复的，设,b,i,=,b,j,，其中,j,i,。由,b,i,=,b,j-i,*b,i,，则对,ti,都得到,b,t,=,b,j-i,*,b,t,。,反复利用上式，则对任何正整数,k,1,，有,b,t,=,b,k,（,j-i,）,*,b,t,，（,ti,）。特别，取,k,使得,k(j-i,),i,，同时令,t=,k(j-i,),，则得到,幂等元,。,11/28/2024,20,计算机学院,定理,1,5-1.2,设,是半群，如果,S,是有限集，则必有,a,S,，使得,a,2,=a,。,(,参见教材,p277,）,证明：,因为,是半群，,S,是有限集，对,bS,，则元素,b,1,，,b,2,，,b,3,，,中必有重复的，设,b,i,=,b,j,，其中,j,i,，由,b,i,=,b,j-i,*b,i,，则对,ti,都得到,b,t,=,b,j-i,*,b,t,。,反复利用上式，则对任何正整数,k,1,，有,b,t,=,b,k,（,j-i,）,*,b,t,，（,ti,）。特别，取,k,使得,k(j-i,),i,，同时令,t=,k(j-i,),，则得到,幂等元,。,注意，,若,S,不是有限集，则不一定有幂等元。例如，正整数集关于加法运算是一个半群，但是不存在幂等元。含幺半群至少含有一个幂等元，那就是幺元。一个半群甚至含幺半群也可以含有多个幂等元。不难验证,是以,S,为幺元的含幺半群。由于集合交运算是幂等的，所以中每个元都是幂等元。,11/28/2024,21,计算机学院,子半群,定义,15-1.1,如果,是半群，,T,是,S,的非空子集，且,T,对运算*是,封闭,的，则称,是半群,的,子半群,；,如果,是含幺半群，,TS,，,eT,，且,T,对运算*是封闭的，则称,是含幺半群,的子含幺半群。,例：半群,的子代数,，,，,都是,的子半群。,11/28/2024,22,计算机学院,子半群,定义,15-1.1,如果,是半群，,T,是,S,的非空子集，且,T,对运算*是封闭的，则称,是半群,的子半群；,如果,是,含幺半群,，,TS,，,eT,，且,T,对运算*是封闭的，则称,是含幺半群,的,子含幺半群,。,例：半群,的子代数,，,，,都是,的子半群。,11/28/2024,23,计算机学院,子半群,定义,15-1.1,如果,是半群，,T,是,S,的非空子集，且,T,对运算*是封闭的，则称,是半群,的子半群；,如果,是含幺半群，,TS,，,eT,，且,T,对运算*是封闭的，则称,是含幺半群,的子含幺半群。,例：,半群,的子代数,，,，,都是,的子半群。,11/28/2024,24,计算机学院,例,设,是一个可换的含幺半群，,M,是它的所有的等幂元构成的集合，则,是,的一个子含幺半群。,证明：,(1),显然，,M,S,；,(2) ,是含幺半群，所以幺元,e,存在，又,e*e,e,，则,e,是一个等幂元，即有,eM,，,所以,M,是非空的；,(3),eM,；,(4),对任意,a,，,bM,，有,(a*b)*(a*b),a*(b*a)*b,a*(a*b)*b,(a*a)*(b*b),a*b,，,即运算“*”关于集合,M,是封闭的运算。,由,(1),、,(2),、,(3),、,(4),知：,是,的一个子含幺半群。,11/28/2024,25,计算机学院,例,设,是一个可换的含幺半群，,M,是它的所有的等幂元构成的集合，则,是,的一个子含幺半群。,证明：,(1),显然，,M,S,；,(2) ,是含幺半群，所以幺元,e,存在，又,e*e,e,，则,e,是一个等幂元，即有,eM,，,所以,M,是非空的；,(3),eM,；,(4),对任意,a,，,bM,，有,(a*b)*(a*b),a*(b*a)*b,a*(a*b)*b,(a*a)*(b*b),a*b,，,即运算“*”关于集合,M,是封闭的运算。,由,(1),、,(2),、,(3),、,(4),知：,是,的一个子含幺半群。,11/28/2024,26,计算机学院,例,设,是一个可换的含幺半群，,M,是它的所有的等幂元构成的集合，则,是,的一个子含幺半群。,证明：,(1),显然，,M,S,；,(2),是含幺半群，所以幺元,e,存在，又,e*e,e,，则,e,是一个等幂元，即有,eM,，,所以,M,是非空的；,(3),eM,；,(4),对任意,a,，,bM,，有,(a*b)*(a*b),a*(b*a)*b,a*(a*b)*b,(a*a)*(b*b),a*b,，,即运算“*”关于集合,M,是封闭的运算。,由,(1),、,(2),、,(3),、,(4),知：,是,的一个子含幺半群。,11/28/2024,27,计算机学院,例,设,是一个可换的含幺半群，,M,是它的所有的等幂元构成的集合，则,是,的一个子含幺半群。,证明：,(1),显然，,M,S,；,(2),是含幺半群，所以幺元,e,存在，又,e*e,e,，则,e,是一个等幂元，即有,eM,，,所以,M,是非空的；,(3),eM,；,(4),对任意,a,，,bM,，有,(a*b)*(a*b),a*(b*a)*b,a*(a*b)*b,(a*a)*(b*b),a*b,，,即运算“*”关于集合,M,是封闭的运算。,由,(1),、,(2),、,(3),、,(4),知：,是,的一个子含幺半群。,11/28/2024,28,计算机学院,例,设,是一个可换的含幺半群，,M,是它的所有的等幂元构成的集合，则,是,的一个子含幺半群。,证明：,(1),显然，,M,S,；,(2),是含幺半群，所以幺元,e,存在，又,e*e,e,，则,e,是一个等幂元，即有,eM,，,所以,M,是非空的；,(3),eM,；,(4),对任意,a,，,bM,，有,(a*b)*(a*b),a*(b*a)*b,a*(a*b)*b,(a*a)*(b*b),a*b,，,即运算“*”关于集合,M,是封闭的运算。,由,(1),、,(2),、,(3),、,(4),知：,是,的一个子含幺半群。,11/28/2024,29,计算机学院,习题,P,278,2,11/28/2024,30,计算机学院,15.2,群和子群,11/28/2024,31,计算机学院,主要内容,一个非常重要的代数系统,群。,主要从以下几个方面来介绍：,群的概念和基本性质。,群的子群和性质。,群中元素的周期和性质。,特殊群及其性质，如,交换群,（,Abel,群）、循环群。,陪集和拉格郎日定理。,11/28/2024,32,计算机学院,在,14.2,中已经为群下了定义，把群看成是在含幺半群的基础上加上每元有逆元的条件，其核心内容可用“闭、结、幺、逆”四个字予以概括。下面是一些典型的群的例子。,11/28/2024,33,计算机学院,例：,我们已经知道,是含幺半群，由于每个整数,a,都有加法逆元,-a,，所以,是群，一般叫做,整数加群,。,同理，是,实数加群,，,是,有理数加群,。,对于数的乘法，,是含幺半群而不是群，因为整数一般无,Z,中的乘法逆元。,是,实数乘群,，它的幺元是,1,，每元的乘法逆元为,1/a,。,11/28/2024,34,计算机学院,例：,设,Z,k,表示整数集,Z,上的模,k,剩余类集合，即,:,Z,k,=0,1,2,k-1,。在,Z,k,上定义运算 和,如下：,那么， 是群。这是因为封闭性和可结合性是明显成立的，,0,是幺元，每元,i,的逆元是,k-i,。,群 习惯上又称为,剩余类加群,。,11/28/2024,35,计算机学院,例,设,n,个元素的集合,A,上的全体置换构成集合,S,n,。由第,6,章中关于置换的讨论，,S,n,中两个置换的复合仍然是,A,上的一个置换，因而运算是封闭的；,其次，由于函数的复合是可结合的，因而置换的复合也是可结合的；在,S,n,中存在幺置换,=(1),，使对任何,S,n,中的置换 均有 ，因而,=(1),是幺元；把每个元素的,x,变成,y,的置换，其逆置换则把元素,y,变成,x,，因而每个置换都有逆。由此可知，,构成群，这个群一般称为,n,次对称群,，是一类重要的群。,群尽管是用“闭、结、幺、逆”四个条件来定义的，但是它还可以用别的形式等价地定义。,11/28/2024,36,计算机学院,例,设,n,个元素的集合,A,上的全体置换构成集合,S,n,。由第,6,章中关于置换的讨论，,S,n,中两个置换的复合仍然是,A,上的一个置换，因而运算是封闭的；,其次，由于函数的复合是可结合的，因而置换的复合也是可结合的；在,S,n,中存在幺置换,=(1),，使对任何,S,n,中的置换 均有 ，因而,=(1),是幺元；把每个元素的,x,变成,y,的置换，其逆置换则把元素,y,变成,x,，因而每个置换都有逆。由此可知，,构成群，这个群一般称为,n,次对称群，是一类重要的群。,群尽管是用“闭、结、幺、逆”四个条件来定义的，但是它还可以用别的形式等价地定义。,11/28/2024,37,计算机学院,群,定理,15-2.1,如果,是半群，并且对,a,，,bG,，都存在,x,，,yG,使,x*a=b,，,a*y=b,，则,是,群,。群中元素的数目称为,群的阶,。,证明：,设,aG,，方程,x*a=a,的解为,e,1,，, 对,t,G,，,方程,a*y=t,有解,y,0,，,e,1,*t= e,1,*,（,a*y,0,）,=,（,e,1,*a,）*,y,0,=a*y,0,=t,即对,t,G,，必有,e,1,*t=t,，,e,1,是,G,中的左幺元。,同样可以证明,G,中有右幺元,e,2,，所以,G,中有幺元,e,。,同理，对,bG,，方程,x*b=e,有解,x,0,，这个,x,0,是,b,的左逆元，方程,b*y=e,的解是,b,的右逆元，从而,b,有逆元。所以，,是群。,11/28/2024,38,计算机学院,群,定理,15-2.1,如果,是半群，并且对,a,，,bG,，都存在,x,，,yG,使,x*a=b,，,a*y=b,，则,是群。群中元素的数目称为群的阶。,证明：,设,aG,，方程,x*a=a,的解为,e,1,，, 对,t,G,，,方程,a*y=t,有解,y,0,，,e,1,*t= e,1,*,（,a*y,0,）,=,（,e,1,*a,）*,y,0,=a*y,0,=t,即对,t,G,，必有,e,1,*t=t,，,e,1,是,G,中的左幺元。,同样可以证明,G,中有右幺元,e,2,，所以,G,中有幺元,e,。,同理，对,bG,，方程,x*b=e,有解,x,0,，这个,x,0,是,b,的左逆元，方程,b*y=e,的解是,b,的右逆元，从而,b,有逆元。所以，,是群。,11/28/2024,39,计算机学院,群,定理,15-2.1,如果,是半群，并且对,a,，,bG,，都存在,x,，,yG,使,x*a=b,，,a*y=b,，则,是群。群中元素的数目称为群的阶。,证明：,设,aG,，方程,x*a=a,的解为,e,1,，, 对,t,G,，,方程,a*y=t,有解,y,0,，,e,1,*t= e,1,*,（,a*y,0,）,=,（,e,1,*a,）*,y,0,=a*y,0,=t,即对,t,G,，必有,e,1,*t=t,，,e,1,是,G,中的左幺元。,同样可以证明,G,中有右幺元,e,2,，所以,G,中有幺元,e,。,同理，对,bG,，方程,x*b=e,有解,x,0,，这个,x,0,是,b,的左逆元，方程,b*y=e,的解是,b,的右逆元，从而,b,有逆元。所以，,是群。,11/28/2024,40,计算机学院,群,定理,15-2.1,如果,是半群，并且对,a,，,bG,，都存在,x,，,yG,使,x*a=b,，,a*y=b,，则,是群。群中元素的数目称为群的阶。,证明：,设,aG,，方程,x*a=a,的解为,e,1,，, 对,t,G,，,方程,a*y=t,有解,y,0,，,e,1,*t= e,1,*,（,a*y,0,）,=,（,e,1,*a,）*,y,0,=a*y,0,=t,即对,t,G,，必有,e,1,*t=t,，,e,1,是,G,中的左幺元。,同样可以证明,G,中有右幺元,e,2,，所以,G,中有幺元,e,。,同理，对,bG,，方程,x*b=e,有解,x,0,，这个,x,0,是,b,的左逆元，方程,b*y=e,的解是,b,的右逆元，从而,b,有逆元,。所以，,是群。,11/28/2024,41,计算机学院,群,定理,15-2.1,如果,是半群，并且对,a,，,bG,，都存在,x,，,yG,使,x*a=b,，,a*y=b,，则,是群。群中元素的数目称为群的阶。,证明：,设,aG,，方程,x*a=a,的解为,e,1,，, 对,t,G,，,方程,a*y=t,有解,y,0,，,e,1,*t= e,1,*,（,a*y,0,）,=,（,e,1,*a,）*,y,0,=a*y,0,=t,即对,t,G,，必有,e,1,*t=t,，,e,1,是,G,中的左幺元。,同样可以证明,G,中有右幺元,e,2,，所以,G,中有幺元,e,。,同理，对,bG,，方程,x*b=e,有解,x,0,，这个,x,0,是,b,的左逆元，方程,b*y=e,的解是,b,的右逆元，从而,b,有逆元,。所以，,是群。,这个定理说明，在群的定义中幺元及逆元的条件可用方程有解来代替。,另外，,群定义中的幺元条件可以用存在左幺元,(,或右幺元,),的条件代替，逆元的条件可以用左逆元,(,或右逆元,),代替。,11/28/2024,42,计算机学院,定理,15-2.2,群,G,中每个元素都是可消去的，即运算满足,消去律,；,（即如果,a*b=a*c,，则必有,b=c,）,群,G,中除幺元,e,外无其它幂等元；,群,G,的运算表中任意一行,(,列,),都没有两个相同的元素（重复元素）；,11/28/2024,43,计算机学院,定理,15-2.2,群,G,中每个元素都是可消去的，即运算满足,消去律,；,（即如果,a*b=a*c,，则必有,b=c,）,群,G,中除幺元,e,外无其它幂等元；,群,G,的运算表中任意一行,(,列,),都没有两个相同的元素（重复元素）；,证明：,由于群,G,中每个元素都有逆元,a,-1,，,由,a,*,b=a,*,c,a,-1,*,a,*,b=,a,-1,*,a,*,c,，即,b=c,11/28/2024,44,计算机学院,定理,15-2.2,群,G,中每个元素都是可消去的，即运算满足消去律；（即如果,a*b=a*c,，则必有,b=c,）,群,G,中除幺元,e,外无其它幂等元；,群,G,的运算表中任意一行,(,列,),都没有两个相同的元素（重复元素）；,11/28/2024,45,计算机学院,定理,15-2.2,群,G,中每个元素都是可消去的，即运算满足消去律；（即如果,a*b=a*c,，则必有,b=c,）,群,G,中除幺元,e,外无其它幂等元；,群,G,的运算表中任意一行,(,列,),都没有两个相同的元素（重复元素）；,证明：（反证法）,假设,a,是群,G,中非幺元的幂等元，即,a*a,a,，且,ae,。因此,a*a,a*e,，,由（,1,）知,a,e,，矛盾。,11/28/2024,46,计算机学院,定理,15-2.2,群,G,中每个元素都是可消去的，即运算满足消去律；（即如果,a*b=a*c,，则必有,b=c,）,群,G,中除幺元,e,外无其它幂等元；,群,G,的运算表中任意一行,(,列,),都没有两个相同的元素（重复元素）；,11/28/2024,47,计算机学院,定理,15-2.2,群,G,中每个元素都是可消去的，即运算满足消去律；（即如果,a*b=a*c,，则必有,b=c,）,群,G,中除幺元,e,外无其它幂等元；,群,G,的运算表中任意一行,(,列,),都没有两个相同的元素（重复元素）；,证明：,（反证法）,假设群,G,的运算表中某一行,(,列,),有两个相同的元素，设为,a,，并设它们所在的行表头元素为,b,，列表头元素分别为,c,1,c,2,，这时显然有,c,1,c,2,。而,a,bc,1,bc,2,，由,(1),得,c,1,c,2,，矛盾。,11/28/2024,48,计算机学院,补充,例：,构造一个,3,阶群。,解：,设,e,是幺元，,G=e, a, b,则可构造的,3,阶群如下：,11/28/2024,49,计算机学院,定理,15-2.3,设,是群，,a,G,。,构造映射 ，使得对任意,x,G,， ，令 ，则对于函数的复合运算“ ”，,是群。,定理的证明留与读者练习,这个定理说明：可以由一个已知的群来构造出一个新的群。,11/28/2024,50,计算机学院,例：,设,X,是任意集合，,S=,f:X,X|f,是双射函数,，即,S,是,X,上的所有双射函数的集合，运算“,。,”是函数的复合运算，证明,是群。,证明：,（,1,）封闭性：,f,gS,，,f,、,g,是双射，则,f,。,g,也是双射，因此,f,。,g S,，故封闭性成立。,（,2,）结合律：由函数的,运算“,。,”满足结合律，因此在,S,中也满足结合律。,11/28/2024,51,计算机学院,例：,设,X,是任意集合，,S=,f:X,X|f,是双射函数,，即,S,是,X,上的所有双射函数的集合，运算“,。,”是函数的复合运算，证明,是群。,证明：,（,1,）封闭性,：,f,gS,，,f,、,g,是双射，则,f,。,g,也是双射，因此,f,。,g S,，故封闭性成立。,（,2,）结合律：由函数的,运算“,。,”满足结合律，因此在,S,中也满足结合律。,11/28/2024,52,计算机学院,例：,设,X,是任意集合，,S=,f:X,X|f,是双射函数,，即,S,是,X,上的所有双射函数的集合，运算“,。,”是函数的复合运算，证明,是群。,证明：,（,1,）封闭性,：,f,gS,，,f,、,g,是双射，则,f,。,g,也是双射，因此,f,。,g S,，故封闭性成立。,（,2,）结合律,：,由函数的,运算“,。,”满足结合律，因此在,S,中也满足结合律。,11/28/2024,53,计算机学院,例：,设,X,是任意集合，,S=,f:X,X|f,是双射函数,，即,S,是,X,上的所有双射函数的集合，运算“,。,”是函数的复合运算，证明,是群。,证明：,（续）,（,3,）幺元,：恒等映射,I,X,S,且,f,S,，有：,I,X,。,f=f,。,I,X,=f,，因此,I,X,是,的幺元。,（,4,）,f,gS,是双射，则,f,的逆函数,f,-1,存在，,f,-1,也 是双射，即,f,-1,S,，且有：,f,-1,。,f=f,。,f,-1,=,I,X,，,因此，,f,的逆函数,f,-1,就是,f,关于“,。,”的逆元，即,S,的任意元素都有逆元。,综合（,1,）（,2,）（,3,）（,4,）知,是群。,11/28/2024,54,计算机学院,例：,设,X,是任意集合，,S=,f:X,X|f,是双射函数,，即,S,是,X,上的所有双射函数的集合，运算“,。,”是函数的复合运算，证明,是群。,证明：,（续）,（,3,）幺元,：,恒等映射,I,X,S,且,f,S,，有：,I,X,。,f=f,。,I,X,=f,，因此,I,X,是,的幺元。,（,4,）,f,gS,是双射，则,f,的逆函数,f,-1,存在，,f,-1,也 是双射，即,f,-1,S,，且有：,f,-1,。,f=f,。,f,-1,=,I,X,，,因此，,f,的逆函数,f,-1,就是,f,关于“,。,”的逆元，即,S,的任意元素,都有逆元,。,综合（,1,）（,2,）（,3,）（,4,）知,是群。,11/28/2024,55,计算机学院,课外练习,：,设,A=R-0,，,1,，在,A,上定义,6,个映射如下：对于任意,x,A,有：,令,G=f,1,f,2,f,3,f,4,f,5,f,6,。试证明,G,关于函数的复合运算“,。,”构成群,。,11/28/2024,56,计算机学院,子群,定义,15-2.1,设,是一个群，,S,是,G,的一个非空子集，若,S,也是群，则称,是,的,一个子群,。,一般来说，对任意的群,，,都有两个子群,，,，,我们称此两个子群为该群的平凡子群,而若有子群,且,S,e,和,S,G,，,则称,为,的真子群。,另外，由群中的一个元素也可生成一个子群。,定义为：,a,-k,=,（,a,k,）,-1,。,11/28/2024,57,计算机学院,子群,定义,15-2.1,设,是一个群，,S,是,G,的一个非空子集，若,S,也是群，则称,是,的一个子群。,一般来说，对任意的群,，,都有两个子群,，,，,我们称此两个子群为该群的,平凡子群,而若有子群,且,S,e,和,S,G,，,则称,为,的,真子群,。,另外，由群中的一个元素也可生成一个子群。为此，需要将群中元素的幂扩充到负指数的形式，即,定义为：,a,-k,=,（,a,k,）,-1,。,11/28/2024,58,计算机学院,子群,定义,15-2.1,设,是一个群，,S,是,G,的一个非空子集，若,S,也是群，则称,是,的一个子群。,一般来说，对任意的群,，,都有两个子群,，,，,我们称此两个子群为该群的平凡子群,而若有子群,且,S,e,和,S,G,，,则称,为,的真子群。,另外，由群中的一个元素也可生成一个子群。为此，需要将群中元素的幂扩充到负指数的形式，即,定义为：,a,-k,=,（,a,k,）,-1,。,11/28/2024,59,计算机学院,定理,15-2.4,设,是一个群，对任意的,aG,，令,S,a,n,|nZ,，,Z,是整数,，则,是,的子群。,证明：,因为,aS,，,所以显然,S,是,G,的非空子集。,对任意的,a,n,，,a,m,S,，,则,a,n,*,a,m,a,n+m,，,由,n,mZ,，,有,n+mZ,，,所以,a,n+m,S,，即运算是封闭的；由,S,是,G,的子集可得结合律也成立；由于,e=a,0,S,，所以,S,中有幺元；,又,a,n,S,有逆元,a,-n,使,a,n,*a,-n,=e,综上所述，,是,的子群。,11/28/2024,60,计算机学院,定理,15-2.4,设,是一个群，对任意的,aG,，令,S,a,n,|nZ,，,Z,是整数,，则,是,的子群。,证明：,因为,aS,，,所以显然,S,是,G,的,非空子集,。,对任意的,a,n,，,a,m,S,，,则,a,n,*,a,m,a,n+m,，,由,n,mZ,，,有,n+mZ,，,所以,a,n+m,S,，即运算是封闭的；由,S,是,G,的子集可得结合律也成立；由于,e=a,0,S,，所以,S,中有幺元；,又,a,n,S,有逆元,a,-n,使,a,n,*a,-n,=e,综上所述，,是,的子群。,11/28/2024,61,计算机学院,定理,15-2.4,设,是一个群，对任意的,aG,，令,S,a,n,|nZ,，,Z,是整数,，则,是,的子群。,证明：,因为,aS,，,所以显然,S,是,G,的非空子集。,对任意的,a,n,，,a,m,S,，,则,a,n,*,a,m,a,n+m,，,由,n,mZ,，,有,n+mZ,，,所以,a,n+m,S,，即运算是,封闭的,；,由,S,是,G,的子集可得结合律也成立；由于,e=a,0,S,，所以,S,中有幺元；,又,a,n,S,有逆元,a,-n,使,a,n,*a,-n,=e,综上所述，,是,的子群。,11/28/2024,62,计算机学院,定理,15-2.4,设,是一个群，对任意的,aG,，令,S,a,n,|nZ,，,Z,是整数,，则,是,的子群。,证明：,因为,aS,，,所以显然,S,是,G,的非空子集。,对任意的,a,n,，,a,m,S,，,则,a,n,*,a,m,a,n+m,，,由,n,mZ,，,有,n+mZ,，,所以,a,n+m,S,，即运算是封闭的；,由,S,是,G,的子集可得结合律也成立；由于,e=a,0,S,，所以,S,中,有幺元,；,又,a,n,S,有逆元,a,-n,使,a,n,*a,-n,=e,综上所述，,是,的子群。,11/28/2024,63,计算机学院,定理,15-2.4,设,是一个群，对任意的,aG,，令,S,a,n,|nZ,，,Z,是整数,，则,是,的子群。,证明：,因为,aS,，,所以显然,S,是,G,的非空子集。,对任意的,a,n,，,a,m,S,，,则,a,n,*,a,m,a,n+m,，,由,n,mZ,，,有,n+mZ,，,所以,a,n+m,S,，即运算是封闭的；由,S,是,G,的子集可得结合律也成立；由于,e=a,0,S,，所以,S,中有幺元；,又,a,n,S,有逆元,a,-n,使,a,n,*a,-n,=e,综上所述，,是,的子群。,11/28/2024,64,计算机学院,特别把由群的一个元素,a,生成的子群记为,(a),。例如在,中，由元素,2,生成的子群,(2),是由全体偶数关于加法构成的群，而由元素,1,生成的子群正好是,Z,本身。,11/28/2024,65,计算机学院,定理1,5,-,2,.5,设,是一个群,是,的子群,则,:,1,）,子群,的幺元,e,S,也是群,的幺元,e,G,；,2,）对,a,S,，,a,在,S,中的逆元,a,S,-1,就是,a,在,G,中的逆元,a,G,-1,。,证明：,1),对,a,S,，由于,e,S,是,S,的幺元，,所以有：,e,S,*a,a*,e,S,a,又,S,G,所以,a,G,由,e,G,是,G,的幺元，所以有：,e,G,*a,a*,e,G,a ,由,、,有：,e,S,*a,a*,e,S,a,e,G,*a,a*,e,G,，,由于,G,满足消去律，所以有：,e,S,e,G,。,2),对,a,S,，由于,S,G,，,所以,a,G,，即,a,在,S,中的逆元就是,a,在,G,中的逆元。,11/28/2024,66,计算机学院,定理1,5,-,2,.5,设,是一个群,是,的子群,则,:,1,）,子群,的幺元,e,S,也是群,的幺元,e,G,；,2,）,对,a,S,，,a,在,S,中的逆元,a,S,-1,就是,a,在,G,中的逆元,a,G,-1,。,证明：,1),对,a,S,，由于,e,S,是,S,的幺元，,所以有：,e,S,*a,a*,e,S,a,又,S,G,所以,a,G,由,e,G,是,G,的幺元，所以有：,e,G,*a,a*,e,G,a ,由,、,有：,e,S,*a,a*,e,S,a,e,G,*a,a*,e,G,，,由于,G,满足消去律，所以有：,e,S,e,G,。,2),对,a,S,，由于,S,G,，,所以,a,G,，即,a,在,S,中的逆元就是,a,在,G,中的逆元。,11/28/2024,67,计算机学院,定理1,5,-,2,.5,设,是一个群,是,的子群,则,:,1,）,子群,的幺元,e,S,也是群,的幺元,e,G,；,2,）,对,a,S,，,a,在,S,中的逆元,a,S,-1,就是,a,在,G,中的逆元,a,G,-1,。,证明：,1),对,a,S,，由于,e,S,是,S,的幺元，,所以有：,e,S,*a,a*,e,S,a,又,S,G,所以,a,G,由,e,G,是,G,的幺元，所以有：,e,G,*a,a*,e,G,a ,由,、,有：,e,S,*a,a*,e,S,a,e,G,*a,a*,e,G,，,由于,G,满足消去律，所以有：,e,S,e,G,。,2),对,a,S,，由于,S,G,，,所以,a,G,，即,a,在,S,中的逆元就是,a,在,G,中的逆元。,11/28/2024,68,计算机学院,定理1,5,-,2,.5,设,是一个群,是,的子群,则,:,1,）,子群,的幺元,e,S,也是群,的幺元,e,G,；,2,）,对,a,S,，,a,在,S,中的逆元,a,S,-1,就是,a,在,G,中的逆元,a,G,-1,。,证明：,1),对,a,S,，由于,e,S,是,S,的幺元，,所以有：,e,S,*a,a*,e,S,a,又,S,G,所以,a,G,由,e,G,是,G,的幺元，所以有：,e,G,*a,a*,e,G,a ,由,、,有：,e,S,*a,a*,e,S,a,e,G,*a,a*,e,G,，,由于,G,满足消去律，所以有：,e,S,e,G,。,2),对,a,S,，由于,S,G,，,所以,a,G,，即,a,在,S,中的逆元就是,a,在,G,中的逆元。,11/28/2024,69,计算机学院,定理1,5,-,2,.5,设,是一个群,是,的子群,则,:,1,）,子群,的幺元,e,S,也是群,的幺元,e,G,；,2,）,对,a,S,，,a,在,S,中的逆元,a,S,-1,就是,a,在,G,中的逆元,a,G,-1,。,证明：,1),对,a,S,，由于,e,S,是,S,的幺元，,所以有：,e,S,*a,a*,e,S,a,又,S,G,所以,a,G,由,e,G,是,G,的幺元，所以有：,e,G,*a,a*,e,G,a ,由,、,有：,e,S,*a,a*,e,S,a,e,G,*a,a*,e,G,，,由于,G,满足消去律，所以有：,e,S,e,G,。,2),对,a,S,，由于,S,G,，,所以,a,G,，即,a,在,S,中的逆元就是,a,在,G,中的逆元。,11/28/2024,70,计算机学院,定理1,5,-,2,.6,设,是一个群，,S,是,G,的一个非空子集，则,是,的子群的充要条件是：对,a,，,b,S,，,有,a*b,-1,S,。,证明：,“,”,设,S,是,G,的子群，,对,a,S,，,由,群的定义知，,b,-1,S,，即有,a*b,-1,S,。,所以必要性成立；,“,”由子群的定义知，需证明如下四点：,1) S,是非空的子集；,11/28/2024,71,计算机学院,定理1,5,-,2,.6,设,是一个群，,S,是,G,的一个非空子集，则,是,的子群的充要条件是：对,a,，,b,S,，,有,a*b,-1,S,。,证明：,“,”,设,S,是,G,的子群，,对,a,S,，,由,群的定义知，,b,-1,S,，即有,a*b,-1,S,。,所以必要性成立；,“,”由子群的定义知，需证明如下四点：,1) S,是非空的子集；,11/28/2024,72,计算机学院,定理1,5,-,2,.6,设,是一个群，,S,是,G,的一个非空子集，则,是,的子群的充要条件是：对,a,，,b,S,，,有,a*b,-1,S,。,证明：,“,”,设,S,是,G,的子群，,对,a,S,，,由,群的定义知，,b,-1,S,，即有,a*b,-1,S,。,所以必要性成立；,“,”,由子群的定义知，需证明如下四点：,1),S,是非空的子集；,11/28/2024,73,计算机学院,2),幺元存在：,由于,S,，,所以有,a,S,，由对,a,b,S,有,a*b,-,S,取,a,b,有,e,G,a*a,-,S;,3),逆元