离散数学-高等教育出版社配套课件-屈婉玲-耿素云-张立昂ch.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,*,*,第十章 群与环,主要内容,群的定义与性质,子群与群的陪集分解,循环群与置换群,环与域,1,半群、独异点与群的定义,半群、独异点、群的实例,群中的术语,群的基本性质,10.1,群的定义与性质,2,半群、独异点与群的定义,定义,(1)设,V,=是代数系统，为二元运算，如果运算是可,结合的，则称,V,为,半群,.,(2)设,V,=是半群，若,e,S,是关于运算的单位元，则称,V,是,含幺半群,，也叫做,独异点,.有时也将独异点,V,记作,V,=.,(3)设,V,=是独异点，,e,S,关于运算的单位元，若,a,S,，,a,1,S,，则称,V,是,群,.通常将群记作,G,.,3,实例,例1,(1),都是半群，+是普通加,法.这些半群中除外都是独异点,(2)设,n,是大于1的正整数，和都是半,群，也都是独异点，其中+和分别表示矩阵加法和矩阵,乘法,(3)为半群，也是独异点，其中,为集合对称差运算,(4)为半群，也是独异点，其中Z,n,=0,1,n,1，,为模,n,加法,4,例2,设,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,实例,特征：,1.满足交换律,2.每个元素都是自己的逆元,3.,a,b,c,中任何两个元素运算结,果都等于剩下的第三个元素,5,有关群的术语,定义,(1)若群,G,是有穷集，则称,G,是,有限群,，否则称为无,限群.群,G,的基数称为群,G,的,阶,，有限群,G,的阶记作|,G,|.,(2)只含单位元的群称为,平凡群,.,(3)若群,G,中的二元运算是可交换的，则称,G,为,交换群,或,阿贝,尔(Abel)群,.,实例：,和是无限群，是有限群，也是,n,阶群.,Klein四元群是4阶群.是平凡群.,上述群都是交换群，,n,阶(,n,2)实可逆矩阵集合关于矩阵乘法,构成的群是非交换群.,6,任取a,bH，知b1H.,综合上述，可知H是G的子群.,每个元素都是自己的逆元,c=ec=(a1a)c=a1(ac)=a1b,常用的证明手段或工具是,所以a1b 是该方程的解.,c b a e,a,b,c中任何两个元素运算结,(ab1)x=ab1x=ab1(x1)1,做出 H 的全体右陪集如下：,0+=,令 G=f1,f2,f6，则G 关于函数的复合运算构成群.,例7 (1)设G=e,a,b,c是Klein四元群，H=是G的子群.,定义,设,G,是群，,a,G,，,n,Z,，则,a,的,n,次幂.,群中元素的幂,群中元素可以定义负整数次幂.,在,中有 2,3,=(2,1,),3,=1,3,=1,1,1=0,在中有,(,2),3,=2,3,=2+2+2=6,7,元素的阶,定义,设,G,是群，,a,G,，使得等式,a,k,=,e,成立的最小正整数,k,称为,a,的阶，记作|,a,|=,k,，称,a,为,k,阶元,.若不存在这样的正,整数,k,，则称,a,为,无限阶元,.,例如，在中，,2和4是3阶元，,3是2阶元，,1和5是6阶元，,0是1阶元.,在中，0是1阶元，其它整数的阶都不存在.,8,群的性质：幂运算规则,定理,设,G,为群，则,G,中的幂运算满足：,(1),a,G,，(,a,1,),1,=,a,(2),a,b,G,，(,ab,),1,=,b,1,a,1,(3),a,G,，,a,n,a,m,=,a,n,+,m,，,n,m,Z,(4),a,G,，(,a,n,),m,=,a,nm,，,n,m,Z,(5)若,G,为交换群，则(,ab,),n,=,a,n,b,n,.,证 (1)(,a,1,),1,是,a,1,的逆元，,a,也是,a,1,的逆元.根据逆元唯一,性，等式得证.,(2)(,b,1,a,1,)(,ab,)=,b,1,(,a,1,a,),b,=,b,1,b,=,e,同理 (,ab,)(,b,1,a,1,)=,e,，,故,b,1,a,1,是,ab,的逆元.根据逆元的唯一性等式得证.,9,群的性质：方程存在惟一解,定理10.2,G,为群，,a,b,G,，方程,ax,=,b,和,ya,=,b,在,G,中有解且,仅有惟一解.,例3,设群,G,=，其中,为对称差.解下列群方程：,a,X,=,，,Y,a,b,=,b,解,X,=,a,1,=,a,=,a,，,Y,=,b,a,b,1,=,b,a,b,=,a,证,a,1,b,代入方程左边的,x,得,a,(,a,1,b,)=(,aa,1,),b,=,eb,=,b,所以,a,1,b,是该方程的解.下面证明惟一性.,假设,c,是方程,ax,=,b,的解，必有,ac,=,b,，从而有,c,=,ec,=(,a,1,a,),c,=,a,1,(,ac,)=,a,1,b,同理可证,ba,1,是方程,ya,=,b,的惟一解.,10,群的性质：消去律,定理,G,为群，则,G,中适合消去律，即对任意,a,b,c,G,有,(1)若,ab,=,ac,，则,b,=,c,.,(2)若,ba,=,ca,，则,b,=,c,.,证明略,11,群的性质：元素的阶,定理,G,为群，,a,G,且|,a,|=,r,.设,k,是整数，则,(1),a,k,=,e,当且仅当,r,|,k,(2)|,a,1,|=|,a,|,12,实例,例 5,设,G,是群，,a,b,G,是有限阶元.证明,(1)|,b,1,ab,|=|,a,|(2)|,ab,|=|,ba,|,证 (1)设|,a,|=,r,，|,b,1,ab|,=,t,，则有,从而有,t,|,r,.另一方面，由,a,=(,b,1,),1,(,b,1,ab,),b,1,可知,r,|,t,.从而,有|,b,1,ab,|=|,a,|.,13,实例,(2)设|,ab,|=,r,，|,ba,|=,t,，则有,由消去律得(,ab,),t,=,e,，从而可知，,r,|,t,.,同理可证,t,|,r,.因此|,ab,|=|,ba,|.,14,子群与群的陪集分解,定义,设,G,是群，,H,是,G,的非空子集，,(1)如果,H,关于,G,中的运算构成群，则称,H,是,G,的,子群,记作,H,G,.,(2)若,H,是,G,的子群，且,H,G,，则称,H,是,G,的,真子群,，记作,H,G,.,例如,n,Z(,n,是自然数)是整数加群 的子群.当,n,1时,n,Z是Z的真子群.,对任何群,G,都存在子群.,G,和,e,都是,G,的子群，称为,G,的,平凡,子群,.,15,子群判定定理,1,定理,（判定定理一）,设,G,为群，,H,是,G,的非空子集，则,H,是,G,的子群当且仅当,(1),a,b,H,有,ab,H,(2),a,H,有,a,1,H,.,证 必要性是显然的.为证明充分性，只需证明,e,H,.,因为,H,非空，存在,a,H,.由条件(2)知,a,1,H,，根据条件(1),aa,1,H,，即,e,H,.,16,子群判定定理,2,定理,（判定定理二）,设,G,为群，,H,是,G,的非空子集.,H,是,G,的子群当且仅当,a,b,H,有,ab,1,H,.,证 必要性显然.只证充分性.,因为,H,非空，必存在,a,H,.,根据给定条件得,aa,1,H,，即,e,H,.,任取,a,H,由,e,a,H,得,ea,1,H,，即,a,1,H,.,任取,a,b,H,，知,b,1,H,.再利用给定条件得,a,(,b,1,),1,H,，即,ab,H,.,综合上述，可知,H,是,G,的子群.,17,子群判定定理,3,定理,（判定定理三）,设,G,为群，,H,是,G,的非空有穷子集，则,H,是,G,的子群当且仅当,a,b,H,有,ab,H,.,证 必要性显然.为证充分性，只需证明,a,H,有,a,1,H,.,任取,a,H,若,a,=,e,则,a,1,=,e,H,.,若,a,e,，令,S,=,a,a,2,，则,S,H,.,由于,H,是有穷集，必有,a,i,=,a,j,（,i,1，由此得,a,j,i,1,a,=,e,和,a a,j,i,1,=,e,从而证明了,a,1,=,a,j,i,1,H,.,18,典型子群的实例:生成子群,定义,设,G,为群，,a,G,，令,H,=,a,k,|,k,Z，,则,H,是,G,的子群，称为由,a,生成的子群,，记作.,证 首先由,a,知道,.任取,a,m,a,l,，则 ,a,m,(,a,l,),1,=,a,m,a,l,=,a,m,l,根据判定定理二可知,G,.,实例：,例如整数加群，由2生成的子群是=2,k,|,k,Z=2Z,中，由2生成的子群=0,2,4,Klein四元群,G,=,e,a,b,c,的所有生成子群是：,=,e,=,e,a,=,e,b,=,e,c,.,19,典型子群的实例:,中心,C,定义,设,G,为群,令,C,=,a,|,a,G,x,G,(,ax,=,xa,)，,则,C,是,G,的子群，称为,G,的,中心,.,证,e,C,.,C,是,G,的非空子集.任取,a,b,C,，只需证明,ab,1,与,G,中所有的元素都可交换.,x,G,，有,(,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,),由判定定理二可知,C,G,.,对于阿贝尔群,G,，因为,G,中所有的元素互相都可交换，,G,的中,心就等于,G,.但是对某些非交换群,G,，它的中心是,e,.,20,典型子群的实例:子群的交,例6,设,G,是群，,H,K,是,G,的子群.证明,(1),H,K,也是,G,的子群,(2),H,K,是,G,的子群当且仅当,H,K,或,K,H,21,图1,定义,设,G,为群,令,L,(,G,)=,H,|,H,是,G,的子群,则偏序集,称为,G,的,子群格,子群格,实例：,Klein,四元群的子群格如下：,22,陪集定义与实例,定义,设,H,是,G,的子群，,a,G,.令,Ha,=,ha,|,h,H,称,Ha,是子群,H,在,G,中的,右陪集,.称,a,为,Ha,的,代表元素,.,例7,(1)设,G,=,e,a,b,c,是Klein四元群，,H,=是,G,的子群.,H,所有的右陪集是：,He,=,e,a,=,H,Ha,=,a,e,=,H,Hb,=,b,c,Hc,=,c,b,不同的右陪集只有两个，即,H,和,b,c,.,23,实例,(2)设,A,=1,2,3，,f,1,f,2,f,6,是,A,上的双射函数.其中,f,1,=,，,f,2,=,f,3,=,，,f,4,=,f,5,=,，,f,6,=,令,G,=,f,1,f,2,f,6,，则,G,关于函数的复合运算构成群.考虑,G,的子群,H,=,f,1,f,2,.做出,H,的全体右陪集如下：,Hf,1,=,f,1,f,1,f,2,f,1,=,H,Hf,2,=,f,1,f,2,f,2,f,2,=,H,Hf,3,=,f,1,f,3,f,2,f,3,=,f,3,f,5,Hf,5,=,f,1,f,5,f,2,f,5,=,f,5,f,3,Hf,4,=,f,1,f,4,f,2,f,4,=,f,4,f,6,Hf,6,=,f,1,f,6,f,2,f,6,=,f,6,f,4,结论：,Hf,1,=,Hf,2,，,Hf,3,=,Hf,5,，,Hf,4,=,Hf,6,.,24,定理,设,H,是群,G,的子群，则,a,b,G,有 ,a,Hb,ab,1,H,Ha,=,Hb,陪集的基本性质,证 先证,a,Hb,ab,1,H,a,Hb,h,(,h,H,a,=,hb,),h,(,h,H,ab,1,=,h,),ab,1,H,再证,a,Hb,Ha,=,Hb.,充分性.若,Ha,=,Hb,，由,a,Ha,可知必有,a,Hb,.,必要性.由,a,Hb,可知存在,h,H,使得,a,=,hb,，即,b,=,h,1,a,任取,h,1,a,Ha,，（根据陪集的定义,h,1,H,）则有,h,1,a,=,h,1,(,hb,)=(,h,1,h,),b,Hb,从而得到,Ha,Hb,.反之，任取,h,1,b,Hb,，则有,h,1,b,=,h,1,(,h,1,a,)=(,h,1,h,1,),a,Ha,从而得到,Hb,Ha,.综合上述，,Ha,=,Hb,得证.,26,10.4,环与域,定义,设是代数系统，+和是二元运算.如果满足,以下条件:,(1)构成交换群,(2)构成半群,(3)运算关于+运算适合分配律,则称是一个,环,.,通常称+运算为环中的,加法,，运算为环中的,乘法,.,环中加法单位元记作 0，乘法单位元（如果存在）记作1.,对任何元素,x,，称,x,的加法逆元为,负元,，记作,x,.,若,x,存在乘法逆元的话，则称之为,逆元,，记作,x,1,.,29,(2)构成半群,(2)S关于V1不构成子半群也不构成子独异点，S关于V2构,定理 G为群，aG且|a|=r.,有|b1ab|=|a|.,因为H非空，存在aH.,(2)只含单位元的群称为平凡群.,(2)构成半群,0+=,群，也都是独异点，其中+和分别表示矩阵加法和矩阵,由 aHb 可知存在 hH 使得 a=hb，即b=h1a,(5)若G为交换群，则(ab)n=anbn.,由 aHb 可知存在 hH 使得 a=hb，即b=h1a,证明两个元素的阶r 和 s 相等或证明某个元素的阶等于r，基本方法是证明相互整除.,对任何群G都存在子群.,任取aH,由e,aH 得 ea1H，即a1H.,环的实例,例15,(1)整数集、有理数集、实数集和复数集关于普通的加法和,乘法构成环，分别称为,整数环,Z，,有理数环,Q，,实数环,R,和,复数环,C.,(2),n,(,n,2)阶实矩阵的集合,M,n,(R)关于矩阵的加法和乘法构,成环，称为,n,阶实矩阵环,.,(3)集合的幂集,P,(,B,)关于集合的对称差运算和交运算构成环.,30,定理,设是环，则(1),a,R,，,a,0=0,a,=0(2),a,b,R,，(,a,),b,=,a,(,b,)=,ab,(3),a,b,c,R,，,a,(,b,c,)=,ab,ac,，(,b,c,),a,=,ba,ca,(4),a,1,a,2,.,a,n,b,1,b,2,.,b,m,R,(,n,m,2),环的运算性质,证 (1),a,R,有,a,0=,a,(0+0)=,a,0+,a,0由环中加法的消去律得,a,0=0.同理可证0,a,=0.(2),a,b,R,，有 (,a,),b,+,ab,=(,a,+,a,),b,=0,b,=0,ab,+(,a,),b,=(,a,+(,a,),b,=0,b,=0(,a,),b,是,ab,的负元.由负元惟一性(,a,),b,=,ab,，同理,a,(,b,)=,ab,31,同理可证,b,1,b,2,.,b,m,有,(4)证明思路：用归纳法证明,a,1,a,2,.,a,n,有,于是,证明,(4),32,实例,例16,在环中计算(,a,+,b,),3,(,a,b,),2,解,(,a,+,b,),3,=(,a,+,b,)(,a,+,b,)(,a,+,b,)=(,a,2,+,ba,+,ab,+,b,2,)(,a,+,b,)=,a,3,+,ba,2,+,aba,+,b,2,a,+,a,2,b,+,bab,+,ab,2,+,b,3,(,a,b,),2,=(,a,b,)(,a,b,)=,a,2,ba,ab,+,b,2,33,特殊的环,定义,设是环,(1)若环中乘法 适合交换律，则称,R,是,交换环,(2)若环中乘法 存在单位元，则称,R,是,含幺环,(3)若,a,b,R,，,ab,=0,a,=0,b,=0，则称,R,是,无零因子环,(4)若,R,既是交换环、含幺环、无零因子环，则称,R,是,整环,(5)设,R,是整环，且,R,中至少含有两个元素.若,a,R,*，其中,R,*=,R,0，都有,a,1,R,，则称,R,是,域,.,34,例17,(1)整数环Z、有理数环Q、实数环R、复数环C都是交换,环,含幺环,无零因子环和整环.除了整数环以外都是域.,(2)令2Z=2,z,|,z,Z，则构成交换环和无零因子环.,但不是含幺环和整环.,(3)设,n,Z,n,2,则,n,阶实矩阵的集合,M,n,(R)关于矩阵加法和乘,法构成环，它是含幺环，但不是交换环和无零因子环，,也不是整环.,实例,35,第十章 习题课,主要内容,半群、独异点与群的定义,群的基本性质,子群的判别定理,陪集的定义及其性质,循环群的生成元和子群,环的定义与性质,特殊的环,36,基本要求,判断或证明给定集合和运算是否构成半群、独异点和群,熟悉群的基本性质,能够证明,G,的子集构成,G,的子群,熟悉陪集的定义和性质,会求循环群的生成元及其子群,能判断给定代数系统是否为环和域,37,练习,1,1.判断下列集合和运算是否构成半群、独异点和群.,(1),a,是正整数，,G,=,a,n,|,n,Z,运算是普通乘法.,(2)Q,+,是正有理数集，运算为普通加法.,解,(1)是半群、独异点和群,(2)是半群但不是独异点和群,方法：根据定义验证，注意运算的封闭性,38,2.设,V,1,=,V,2,=,其中Z为整数集合,+和,分别代表普通加法和乘法.判断下述集合,S,是否构成,V,1,和,V,2,的子半群和子独异点.,(1),S,=2,k,|,k,Z,(2),S,=2,k,+1|,k,Z,解,(1),S,关于,V,1,构成子半群和子独异点，但是关于,V,2,仅构成子,半群,(2),S,关于,V,1,不构成子半群也不构成子独异点，,S,关于,V,2,构,成子半群和子独异点,练习,2,39,3.设Z,18,为模18整数加群,求所有元素的阶.,解：,|0|=1,|9|=2，|6|=|12|=3,|3|=|15|=6,|2|=|4|=|8|=|10|=|14|=|16|=9,|1|=|5|=|7|=|11|=|13|=|17|=18,练习,3,说明：,群中元素的阶可能存在，也可能不存在.,对于有限群，每个元素的阶都存在，而且是群的阶的因子.,对于无限群，单位元的阶存在，是1；而其它元素的阶可能存在，也可能不存在.（可能所有元素的阶都存在，但是群还是无限群）.,40,有关群性质的证明方法,有关群的简单证明题的主要类型,证明群中的元素某些运算结果相等,证明群中的子集相等,证明与元素的阶相关的命题.,证明群的其它性质，如交换性等.,常用的证明手段或工具是,算律：结合律、消去律,和特殊元素相关的等式，如单位元、逆元等,幂运算规则,和元素的阶相关的性质.特别地，,a,为1阶或2阶元的充分必要条件是,a,1,=,a,.,41,证明方法,证明群中元素相等的基本方法就是用结合律、消去律、单位元及逆元的惟一性、群的幂运算规则等对等式进行变形和化简.,证明子集相等的基本方法就是证明两个子集相互包含,证明与元素的阶相关的命题，如证明阶相等，阶整除等.证明两个元素的阶,r,和,s,相等或证明某个元素的阶等于,r,，基本方法是证明相互整除.在证明中可以使用结合律、消去律、幂运算规则以及关于元素的阶的性质.特别地，可能用到,a,为1阶或2阶元的充分必要条件是,a,1,=,a,.,42,练习,5,5,设,G,为群，,a,是,G,中的2 阶元，证明,G,中与,a,可交换的元素构成,G,的子群.,证 令,H,=,x,|,x,G,xa,=,ax,下面证明,H,是,G,的子群.,首先,e,属于,H,，,H,是,G,的非空子集.,任取,x,y,H,，有,(,xy,1,),a,=,x,(,y,1,a,)=,x,(,a,1,y,),1,=,x,(,ay,),1,=,x,(,ya,),1,=,xa,1,y,1,=,xay,1,=,axy,1,=,a,(,xy,1,),因此,xy,1,属于,H,.由判定定理命题得证.,分析：,证明子群可以用判定定理，特别是判定定理二.,证明的步骤是：,验证,H,非空,任取,x,y,H,，证明,xy,1,H,43,6.(1)设,G,为模12加群,求 在,G,中所有的左陪集,(2)设,X,=,x,|,x,R,x,0,1,在,X,上如下定义6个函数：,f,1,(,x,)=,x,，,f,2,(,x,)=1/,x,f,3,(,x,)=1,x,f,4,(,x,)=1/(1,x,),f,5,(,x,)=(,x,1)/,x,f,6,(,x,)=,x,/(,x,1),则,G,=,f,1,f,2,f,3,f,4,f,5,f,6,关于函数合成运算构成群.求子群,H,=,f,1,f,2,的所有的右陪集.,练习,6,解(1)=0,3,6,9,的不同左陪集有3个，即,0+=,1+=4+=7+=10+=1,4,7,10,2+=5+=8+=11+=2,5,8,11.,(2),f,1,f,2,有3个不同的陪集，它们是：,H,，,Hf,3,=,f,3,f,5,Hf,4,=,f,4,f,6,.,44,证 ,a,b,Z有,a,b,a,b,Z,两个运算封闭.任取,a,b,c,Z,(,a,b,),c,=(,a,+,b,1),c,=(,a,+,b,1)+,c,1=,a,+,b,+,c,2,a,(,b,c,)=,a,(,b,+,c,1)=,a,+(,b,+,c,1),1=,a,+,b,+,c,2,(,a,b,),c,=(,a,+,b,ab,),c,=,a,+,b,+,c,(,ab,+,ac,+,bc,)+,abc,a,(,b,c,)=,a,(,b,+,c,bc,)=,a,+,b,+,c,(,ab,+,ac,+,bc,)+,abc,与,可结合，,1为的单位元.2,a,为,a,关于的逆元.Z关于,构成交换群,关于构成半群.关于 满足分配律.,a,(,b,c,)=,a,(,b,+,c,1)=2,a,+,b,+,c,ab,ac,1,（,a,b,)(,a,c,)=2,a,+,b,+,c,ab,ac,1,构成,环,练习,11,11.在整数环中定义和两个运算,a,b,Z 有,a,b,=,a,+,b,1,a,b,=,a,+,b,ab,.,证明构成环,45,