离散数学几个典型的代数系统群.pptx

Level 1,Level 2,Level 3,Click to edit Master title style,*,第六章 几个经典代数系统,第1页,半群与独异点,半群定义与性质,交换半群与独异点,半群与独异点子代数和积代数,半群与独异点同态,群,群定义与性质,子群与群直积,循环群,置换群,6.1 半群与群,6.1,半群与群,2,第2页,半群定义与实例,定义,设,V,=是代数系统，,o,为二元运算，假如,运算是可结合，则称,V,为,半群,.,实例（1）,都是半群，+是普通加法.,（2）设,n,是大于1正整数，和都是半群，其中+和 分别表示矩阵加法和矩阵乘法.,（3）为半群，其中,为集合对称差运算.,（4）为半群，其中,Z,n,=0,1,n,1，,为模,n,加法.,（5）为半群，其中,为函数复合运算.,（6）为半群，其中,R,*为非零实数集合，,运算定义,以下：,x,y,R,*,x,y,=,y,6.1,半群与群,3,第3页,元素幂运算性质,因为半群中运算,是结合，能够定义,运算幂。,设V=为半群，对任意 xS，要求：x,1,=x x,n+1,=x,n,x,nZ,+,幂运算规则：x,n,x,m,=x,n+m,(x,n,),m,=x,nm,m,nZ,+,证实方法：数学归纳法,6.1,半群与群,4,第4页,特殊半群,定义,设,V,=是半群,(1)若,运算是可交换，则称,V,为,交换半群,2)若,e,S,是关于,运算幺元，则称,V,是,含幺半群,，也叫做,独异点,.,独异点,V,记作,V,=,6.1,半群与群,5,第5页,独异点幂,独异点幂运算定义 ,x,0,=,e,x,n,+1,=,x,n,x,n,N,幂运算规则,x,n,x,m,=,x,n,+,m,(,x,n,),m,=,x,nm,m,n,N,6.1,半群与群,6,第6页,交换半群和独异点实例,例1（1）,都是交,换半群，也是独异点，+是普通加法.,（2）设,n,是大于 1 正整数，和都是,独异点，其中+和 分别表示矩阵加法和矩阵乘法.加,法组成交换半群，乘法不是交换半群.,（3）为交换半群和独异点，其中,为集合对,称差运算.,（4）为交换半群与独异点，其中,Z,n,=0,1,n,1，,为模,n,加法.,（5）为独异点，不是交换半群，其中,为函数复合运算.,6.1,半群与群,7,第7页,半群与独异点子代数,定义,半群子代数称为,子半群,，独异点子代数称,为,子独异点。,判断方法：,设 V=为半群，T 是 S 非空子集，,T是V子半群当且仅当T对,o,运算封闭.,设V=为独异点，T是V子独异点当且仅当T 对,o,运算封闭，且e,T,实例：,是子半群，是,子独异点，不是子独异点.,6.1,半群与群,8,第8页,半群与独异点积代数,定义,设,V,1,=，,V,2,=是半群(或独异,点)，令,S,=,S,1,S,2定义,S,上 运算以下：,S,，,=,称 为,V,1,和,V,2,积半群,（,直积,），记作,V,1,V,2,.,若,V,1,=和,V,2,=是独,异点，则,V,1,V,2,=,S,1,S,2,也是独异,点,称为独异点,积独异点,(,直积,).,6.1,半群与群,9,第9页,半群和独异点同态,定义,(1)设,V,1,=，,V,2,=是半群，,：,S,1,S,2,.若对任意,x,y,S,1,有,(,x,y,)=,(,x,),(,y,),则称,为半群,V,1,到,V,2,同态映射,，简称,同态,.,(2)设,V,1,=，,V,2,=是独异点，,:,S,1,S,2,.若对任意,x,y,S,1,有x,y,)=,(,x,),(,y,)且,(,e,1,)=,e,2,则称,为独异点,V,1,到,V,2,同态映射,，简称,同态,.,6.1,半群与群,10,第10页,同态实例,例2 设半群,V,1,=，独异点,V,2,=.其中 为矩阵乘法，,e,为 2 阶单位矩阵,令,：SS,是半群,V,1,自同态,不是独异点,V,2,自同态，因为它没有将,V,2,单位元映到,V,2,单位元.,6.1,半群与群,11,第11页,群定义与实例,定义,设是代数系统，,为二元运算.假如,运算是可结合，存在幺元,e,G,，而且对,G,中,任何元素,x,都有,x,1,G,，则称,G,为,群,.,群实例,(1),是群不是群.,(2)是群，而不是群.,(3)是群，,为对称差运算.,(4)是群.,Z,n,=0,1,n,1，,为模,n,加.,6.1,半群与群,12,第12页,Klein,四元群,设,G,=,e,a,b,c,，,G,上运算由下表给出，,称为,Klein四元群,e a b c,e,a,b,c,e a b c,a e c b,b c e a,c b a e,运算表特征：,e为G中幺元,对称性-运算可交换,主对角线元素都是幺元,-每个元素是自己逆元,a,b,c,中任两个元素运算,都等于第三个元素.,6.1,半群与群,13,第13页,群中术语,若群,G,是有穷集，则称,G,是,有限群,，不然称为,无限群,.,群,G,基数（元素个数）称为群,G,阶,有限群,G,阶记作|,G,|.,若群,G,中二元运算是可交换，则称,G,为,交换群,或,阿贝尔(Abel)群,.,6.1,半群与群,14,第14页,实例,和 是无限群,是有限群，也是,n,阶群,Klein四元群,G,=,e,a,b,c,是 4 阶群,上述群都是交换群,n,阶(,n,2)实可逆矩阵集合关于矩阵乘法组成群是非交换群.,6.1,半群与群,15,第15页,群中术语（续）,实例,在,中有,2,3,=(2,1,),3,=1,3,=1,1,1=0,在 中有,(,2),3,=2,3,=2+2+2=6,定义,设,G,是群，,x,G,，,n,Z,，则x,n,次幂,x,n,定义为,6.1,半群与群,16,第16页,设,G,是群，,x,G,，使得等式,x,k,=,e,成立最小正,整数,k,称为,x,阶（或周期）,，记作|,x,|=,k,，称,x,为,k,阶元,.若不存在这么正整数,k,，则称,x,为,无限阶元,.,群中术语（续）,在中，2 和 4 是 3 阶元，3 是 2 阶元，1 和,5 是 6 阶元，0 是 1 阶元,在中，0 是 1 阶元，其它整数阶都不存在.,注：在任何群中，幺元阶都是1,6.1,半群与群,17,第17页,群性质-幂运算规则,定理1,设,G,为群,则,G,中幂运算满足：(1),x,G,，(,x,1,),1,=,x,.2),x,y,G,，(,xy,),1,=,y,1,x,1,.(3),x,G,，,x,n,x,m,=,x,n,+,m,，,n,m,Z,.(4),x,G,，(,x,n,),m,=,x,nm,，,n,m,Z,.,注意,(,xy,),n,=(,xy,)(,xy,),(,xy,),是,n,个,xy,运算，,G,为,交换群，才有(,xy,),n,=,x,n,y,n,.,6.1,半群与群,18,第18页,群性质-群方程存在唯一解,定理2,G,为群，,a,b,G,，方程,ax,=,b,和,ya,=,b,在,G,中有解且仅有惟一解.,a,1,b,是,ax,=,b,解.,ba,1,是,ya,=,b,唯一解.,例 设,G,=,，其中,为对称差,.群方程,a,X,=,，,Y,a,b,=,b,解,X,=,a,1,=,a,=,a,，,Y,=,b,a,b,1,=,b,a,b,=,a,6.1,半群与群,19,第19页,群性质-消去律,定理6.3,G为群，则G适合消去律，即,a,b,cG 有(1)若ab=ac，则 b=c.(2)若ba=ca，则 b=c.例、设G=a,1,a,2,a,n,是 n 阶群，令,a,i,G=a,i,a,j,|j=1,2,n,证实：a,i,G=G.证：由群中运算封闭性有 a,i,G,G,.假设a,i,G,G,，即|a,i,G|n.必有a,j,a,k,G使得 a,i,a,j,=a,i,a,kjk）由消去律得 a,j,=a,k,与|G|=n 矛盾.,6.1,半群与群,20,第20页,群性质-运算表排列规则,定理4,设,G,为有限群，则,G,运算表中每行每列,都是,G,中元素一个置换，且不一样行（或列）,置换都不相同.,了解：G运算表每一行里，G每个元素都出现一次，且只出现一次；不一样行元素排列次序不一样。,注意：必要条件，用于判断一个运算表不是群.,a b c d,a,b,c,d,b,c d a,b,a c d,c d b a,d b a c,a b c d,a,b,c,d,a b c d,c d a b,b c d a,d a b c,6.1,半群与群,21,第21页,子群定义,定义,设 G 是群，H 是 G 非空子集，假如 H 关于 G 中运算组成群，则称 H 是 G,子群,记作 HG.若 H 是 G 子群，且 H,G,，则称 H 是 G,真子群,，记作 HG.,实例 nZ（n是自然数）是整数加群 子群.当 n1 时,nZ 是 Z 真子群.,对任何群 G 都存在子群.G 和 e 都是 G 子群，称为 G 平凡子群.,22,第22页,子群判定定理,判定定理,设,G,为群，,H,是,G,非空子集.,H,是,G,子群当且仅当,x,y,H,有,xy,1,H,.,证实,H,为,G,子群步骤：,经过给出,H,中元素说明,H,是,G,非空子集,任取,x,y,属于,H,，证实,xy,-1,属于,H,6.1,半群与群,23,第23页,主要子群,生成子群：,设G为群，aG，令H=a,k,|kZ，则H是G子群，称为,由a 生成子群，记作.,证：首先由a 知道,.任取 a,m,a,l,，则a,m,(a,l,),1,=a,m,a,l,=a,m,l,依据判定定理可知G.,6.1,半群与群,24,第24页,实例,整数加群，,由 2 生成子群是 =2,k,|,k,Z,=2,Z,模 6 加群 中,由 2 生成子群 =0,2,4,Klein四元群,G,=,e,a,b,c,全部生成子群是：,=,e,=,e,a,=,e,b,=,e,c,.,25,第25页,群G中心C,设 G 为群,令 C=a|aG,xG(ax=xa)，则 C是 G 子群，称为 G,中心,.,证：eC.C是 G 非空子集.任取 a,bC，证实 ab,1,与 G 中全部元素都可交换.,xG，有,(ab,1,)x=ab,1,x=ab,1,(x,1,),1,=a(x,1,b),1,=a(bx,1,),1,=a(xb,1,)=(ax)b,1,=(xa)b,1,=x(ab,1,),由判定定理可知 CG.,主要子群（续）,6.1,半群与群,26,第26页,循环群定义,定义,设G是群，若存在 aG 使得 G=a,k,|kZ,则称G是,循环群,，记作 G=，称 a 为 G,生成元,.,实例,整数加群 G=,模 6 加群 G=,61,半群与群,27,第27页,循环群分类,设 循环群,G,=，依据生成元,a,阶能够分,成两类：,n,阶循环群和无限循环群.,设,G,=是循环群，若,a,是,n,阶元，则 ,G,=,a,0,=,e,a,1,a,2,a,n,1,那么|,G,|=,n,，称,G,为,n,阶循环群,.,若,a,是无限阶元，则 ,G,=,a,0,=,e,a,1,a,2,这时称,G,为,无限循环群,.,28,第28页,循环群生成元,定理,设,G,=是循环群.,(1)若,G,是无限循环群，则,G,只有,a,和,a,1,两个生成元.,(2)若,G,是,n,阶循环群，则,a,r,是,G,生成元当且仅当,r,是小于等于,n,且与,n,互质正整数.,29,第29页,(1)设,G,=,e,a,a,11,是12阶循环群，则小于或等于12且与12互素数是 1,5,7,11,由定理可知,a,，,a,5,，,a,7,和,a,11,是,G,生成元.,(2)设,G,=是模9整数加群，则小于或等于 9且与 9 互素数是 1,2,4,5,7,8.依据定理，,G,生成元是 1,2,4,5,7 和 8.,(3)设,G,=3,Z,=3,z,|,z,Z,G,上运算是普通加法.那么,G,只有两个生成元：3 和,3.,生成元实例,30,第30页,循环群子群,定理：,设,G,=是循环群.(1)设,G,=是循环群，则,G,子群仍是循环群.(2)若,G是无限循环群，则,G,子群除,e,以外都是无限循环群.(3)若,G,=是,n,阶循环群，则对,n,每个正因子,d,，,G,恰好含有一个,d,阶子群.,31,第31页,(1),G,=是1无限循环群，对于自然数,m,N,，1,m,次幂是,m,，,m,生成子群是,mZ,，,m,N,.即 =0 =0,Z,=,mz,|,z,Z,=,mZ,，,m,0,(2),G,=是12阶循环群.12正因子是1,2,3,4,6 和12，所以,G,子群是（a,n/d,）：,1 阶子群=0，2 阶子群 =0,6,3 阶子群=0,4,8，4 阶子群 =0,3,6,9,6 阶子群=0,2,4,6,8,10，12 阶子群=,Z12,子群实例,32,第32页,n,元置换定义,定义,设,S,=1,2,n,S,上双射函数,:,S,S,称为,S,上,n,元置换,.,普通将,n,元置换记为,比如,S,=1,2,3,4,5,则,都是 5元置换,.,33,第33页,k,阶轮换与对换,定义,设,是,S,=1,2,n,上,n,元置换.若,(,i,1,)=,i,2,(,i,2,)=,i,3,(,i,k,1,)=,i,k,(,i,k,)=,i,1,且保持,S,中其它元素不变，则称,为,S,上,k,次轮换,，记作(,i,1,i,2,i,k,).若,k,=2，称,为,S,上,对换,.,比如 5元置换,分别是 5阶和 2 阶轮换,=(1 2 3 4 5),=(1 3),其中,也叫做对换,34,第34页,n,元置换分解为轮换,设,S,=1,2,n,，对于任何,S,上,n,元置换,，,一定存在着一个有限序列,i,1,i,2,i,k,k,1,（能够取,i,1,=1）使得,(,i,1,)=,i,2,(,i,2,)=,i,3,(,i,k,1,)=,i,k,(,i,k,)=,i,1,，令,1,=(,i,1,i,2,i,k,)，它是从,中分解出来第一个轮换.依据函数复合定义可将,写作,1,，其中,作用于,S,i,1,i,2,i,k,上元素.继续对,进行类,似分解.因为,S,中只有,n,个元素,经过有限步以,后，必得到,轮换分解式,=,1,2,t,35,第35页,分解实例,例 设,S,=1,2,8,从,中分解出来第一个轮换式(1 5 2 3 6)；第二个轮换为(4)；第三个轮换为(7 8).,轮换表示式,=(1 5 2 3 6)(4)(7 8)=(1 5 2 3 6)(7 8),用一样方法能够得到,分解式,=(1 8 3 4 2)(5 6 7),注意：在轮换分解式中，1 阶轮换能够省略,.,36,第36页,n,元置换乘法与求逆,37,第37页,n,元置换群及其实例,考虑全部,n,元置换组成集合,S,n,S,n,关于置换乘法是封闭.置换乘法满足结合,律.恒等置换(1)是,S,n,中单位元.对于任何,n,元置换,S,n,，逆置换,1,是逆元.这就证实了,S,n,关,于置换乘法组成一个群，称为,n,元对称群,.,n,元对,称群子群称为,n,元置换群,.,例 设,S,=1,2,3，3元对称群,S,3,=(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2),38,第38页,S,3,运算表,(1)(1 2)(1 3)(2 3)(1 2 3)(1 3 2),(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2),(1)(1 2)(1 3)(2 3)(1 2 3)(1 3 2),(1 2)(1)(1 2 3)(1 3 2)(1 3)(2 3),(1 3)(1 3 2)(1)(1 2 3)(2 3)(1 2),(2 3)(1 2 3)(1 3 2)(1)(1 2)(1 3),(1 2 3)(2 3)(1 2)(1 3)(1 3 2)(1),(1 3 2)(1 3)(2 3)(1 2)(1)(1 2 3),39,第39页,S,3,子群,S,3,=(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2)，,A,3,=(1),(1 2 3),(1 3 2)，,=(1),=(1),(1 2),=(1),(1 3),=(1),(2 3),40,第40页,