离散数学第10章群与环.ppt

《离散数学第10章群与环.ppt》由会员分享，可在线阅读，更多相关《离散数学第10章群与环.ppt（45页珍藏版）》请在三一办公上搜索。

1、1,第十章 群与环,主要内容群的定义与性质子群与群的陪集分解循环群与置换群环与域,2,半群、独异点与群的定义半群、独异点、群的实例群中的术语群的基本性质,10.1 群的定义与性质,3,半群、独异点与群的定义,定义10.1(1)设V=是代数系统，为二元运算，如果运算是可结合的，则称V为半群.(2)设V=是半群，若eS是关于运算的单位元，则称V是含幺半群，也叫做独异点.有时也将独异点V 记作 V=.(3)设V=是独异点，eS关于运算的单位元，若 aS，a1S，则称V是群.通常将群记作G.,4,实例,例1(1),都是半群，+是普通加 法.这些半群中除外都是独异点(2)设n是大于1的正整数，和都是半

2、群，也都是独异点，其中+和分别表示矩阵加法和矩阵 乘法(3)为半群，也是独异点，其中为集合对称差运算(4)为半群，也是独异点，其中Zn=0,1,n1，为模n加法,5,例2 设G=e,a,b,c，G上的运算由下表给出，称为Klein四元群,实例,特征：1.满足交换律2.每个元素都是自己的逆元3.a,b,c中任何两个元素运算结 果都等于剩下的第三个元素,6,有关群的术语,定义10.2(1)若群G是有穷集，则称G是有限群，否则称为无限群.群G 的基数称为群 G 的阶，有限群G的阶记作|G|.(2)只含单位元的群称为平凡群.(3)若群G中的二元运算是可交换的，则称G为交换群或阿贝尔(Abel)群.,实

3、例：和是无限群，是有限群，也是 n 阶群.Klein四元群是4阶群.是平凡群.上述群都是交换群，n阶(n2)实可逆矩阵集合关于矩阵乘法构成的群是非交换群.,7,定义10.3 设G是群，aG，nZ，则a 的 n次幂.,群中元素的幂,群中元素可以定义负整数次幂.在中有 23=(21)3=13=111=0 在中有(2)3=23=2+2+2=6,8,元素的阶,定义10.4 设G是群，aG，使得等式 ak=e 成立的最小正整数k 称为a 的阶，记作|a|=k，称 a 为 k 阶元.若不存在这样的正整数 k，则称 a 为无限阶元.,例如，在中，2和4是3阶元，3是2阶元，1和5是6阶元，0是1阶元.在中，

4、0是1阶元，其它整数的阶都不存在.,9,群的性质：幂运算规则,定理10.1 设G 为群，则G中的幂运算满足：(1)aG，(a1)1=a(2)a,bG，(ab)1=b1a1(3)aG，anam=an+m，n,mZ(4)aG，(an)m=anm，n,mZ(5)若G为交换群，则(ab)n=anbn.,证(1)(a1)1是a1的逆元，a也是a1的逆元.根据逆元唯一性，等式得证.(2)(b1a1)(ab)=b1(a1a)b=b1b=e,同理(ab)(b1a1)=e，故b1a1是ab的逆元.根据逆元的唯一性等式得证.,10,群的性质：方程存在惟一解,定理10.2G为群，a,bG，方程ax=b和ya=b在G

5、中有解且仅有惟一解.,例3 设群G=，其中为对称差.解下列群方程：aX=，Ya,b=b解 X=a1=a=a，Y=ba,b1=ba,b=a,证 a1b 代入方程左边的x 得 a(a1b)=(aa1)b=eb=b所以a1b 是该方程的解.下面证明惟一性.假设c是方程ax=b的解，必有ac=b，从而有 c=ec=(a1a)c=a1(ac)=a1b 同理可证ba1是方程 ya=b的惟一解.,11,群的性质：消去律,定理10.3 G为群，则G中适合消去律，即对任意a,b,cG 有(1)若 ab=ac，则 b=c.(2)若 ba=ca，则 b=c.证明略,12,群的性质：元素的阶,定理10.4 G为群，a

6、G且|a|=r.设k是整数，则(1)ak=e当且仅当r|k(2)|a1|=|a|,13,实例,例 5 设G是群，a,bG是有限阶元.证明(1)|b1ab|=|a|(2)|ab|=|ba|,证(1)设|a|=r，|b1ab|=t，则有 从而有t|r.另一方面，由 a=(b1)1(b1ab)b1可知 r|t.从而有|b1ab|=|a|.,14,实例,(2)设|ab|=r，|ba|=t，则有 由消去律得(ab)t=e，从而可知，r|t.同理可证 t|r.因此|ab|=|ba|.,15,10.2 子群与群的陪集分解,定义10.5 设G是群，H是G的非空子集，(1)如果H关于G中的运算构成群，则称H是G

7、的子群,记作HG.(2)若H是G的子群，且HG，则称H是G的真子群，记作HG.,例如 nZ(n是自然数)是整数加群 的子群.当n1时,nZ是Z的真子群.对任何群G都存在子群.G和e都是G的子群，称为G的平凡子群.,16,子群判定定理1,定理10.5（判定定理一）设G为群，H是G的非空子集，则H是G的子群当且仅当(1)a,bH有abH(2)aH有a1H.,证 必要性是显然的.为证明充分性，只需证明eH.因为H非空，存在aH.由条件(2)知a1H，根据条件(1)aa1H，即eH.,17,子群判定定理2,定理10.6（判定定理二）设G为群，H是G的非空子集.H是G的子群当且仅当a,bH有ab1H.,

8、证 必要性显然.只证充分性.因为H非空，必存在aH.根据给定条件得aa1H，即eH.任取aH,由e,aH 得 ea1H，即a1H.任取a,bH，知b1H.再利用给定条件得a(b1)1H，即abH.综合上述，可知H是G的子群.,18,子群判定定理3,定理10.7（判定定理三）设G为群，H是G的非空有穷子集，则H是G的子群当且仅当a,bH有abH.,证 必要性显然.为证充分性，只需证明 aH有a1H.任取aH,若a=e,则a1=eH.若ae，令S=a,a2,，则SH.由于H是有穷集，必有ai=aj（i1，由此得 a ji1a=e 和 a a ji1=e 从而证明了a1=a ji1H.,19,典型子

9、群的实例:生成子群,定义10.6 设G为群，aG，令H=ak|kZ，则H是G的子群，称为由 a 生成的子群，记作.,证 首先由a知道.任取am,al，则 am(al)1=amal=aml根据判定定理二可知G.实例：例如整数加群，由2生成的子群是=2k|kZ=2Z中，由2生成的子群=0,2,4Klein四元群 G=e,a,b,c的所有生成子群是：=e,=e,a,=e,b,=e,c.,20,典型子群的实例:中心C,定义10.7 设G为群,令 C=a|aGxG(ax=xa)，则C是G的子群，称为G的中心.,证 eC.C是G的非空子集.任取a,bC，只需证明ab1与G中所有的元素都可交换.xG，有(a

10、b1)x=ab1x=ab1(x1)1=a(x1b)1=a(bx1)1=a(xb1)=(ax)b1=(xa)b1=x(ab1)由判定定理二可知CG.对于阿贝尔群G，因为G中所有的元素互相都可交换，G的中心就等于G.但是对某些非交换群G，它的中心是e.,21,典型子群的实例:子群的交,例6 设G是群，H,K是G的子群.证明(1)HK也是G的子群(2)HK是G的子群当且仅当 HK 或 KH,22,图1,定义10.8 设G为群,令 L(G)=H|H是G的子群则偏序集称为G的子群格,子群格,实例：Klein四元群的子群格如下：,23,陪集定义与实例,定义10.9 设H是G的子群，aG.令Ha=ha|hH

11、称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.,24,实例,(2)设A=1,2,3，f1,f2,f6是A上的双射函数.其中 f1=,，f2=,f3=,，f4=,f5=,，f6=,令 G=f1,f2,f6，则G 关于函数的复合运算构成群.考虑G 的子群H=f1,f2.做出 H 的全体右陪集如下：Hf1=f1f1,f2f1=H,Hf2=f1f2,f2f2=H Hf3=f1f3,f2f3=f3,f5,Hf5=f1

12、f5,f2f5=f5,f3 Hf4=f1f4,f2f4=f4,f6,Hf6=f1f6,f2f6=f6,f4结论：Hf1=Hf2，Hf3=Hf5，Hf4=Hf6.,25,陪集的基本性质,定理10.8 设H是群G的子群，则(1)He=H(2)aG 有aHa证(1)He=he|hH=h|hH=H(2)任取 aG，由a=ea 和 eaHa 得 aHa,26,定理10.9 设H是群G的子群，则a,bG有 aHb ab1H Ha=Hb,陪集的基本性质,证 先证aHb ab1H aHb h(hHa=hb)h(hHab1=h)ab1H 再证 aHb Ha=Hb.充分性.若Ha=Hb，由aHa 可知必有 aHb

13、.必要性.由 aHb 可知存在 hH 使得 a=hb，即b=h1a 任取 h1aHa，（根据陪集的定义h1 H）则有h1a=h1(hb)=(h1h)bHb 从而得到 Ha Hb.反之，任取h1bHb，则有h1b=h1(h1a)=(h1h1)aHa 从而得到Hb Ha.综合上述，Ha=Hb得证.,27,定理10.10 设H是群G的子群，在G上定义二元关系R：a,bG,R ab1H则 R是G上的等价关系，且aR=Ha.,陪集的基本性质,证 先证明R为G上的等价关系.自反性.任取aG，aa1=eH R 对称性.任取a,bG，则 Rab1H(ab1)1Hba1HR 传递性.任取a,b,cG，则 RR

14、ab1Hbc1H ac1H R 下面证明：aG，aR=Ha.任取bG，（p123等价类）baR R ab1H Ha=Hb bHa（TH10.9）,28,推论,推论 设H是群G的子群,则(1)a,bG，Ha=Hb 或 HaHb=(2)Ha|aG=G 证明：由等价类性质可得.,定理10.11 设H是群G的子群，则 aG，H Ha 证明 略,29,10.4 环与域,定义10.12 设是代数系统，+和是二元运算.如果满足以下条件:(1)构成交换群(2)构成半群(3)运算关于+运算适合分配律则称是一个环.通常称+运算为环中的加法，运算为环中的乘法.环中加法单位元记作 0，乘法单位元（如果存在）记作1.对

15、任何元素 x，称 x 的加法逆元为负元，记作x.若 x 存在乘法逆元的话，则称之为逆元，记作x1.,30,环的实例,例15(1)整数集、有理数集、实数集和复数集关于普通的加法和 乘法构成环，分别称为整数环Z，有理数环Q，实数环R 和复数环C.(2)n(n2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构 成环，称为 n 阶实矩阵环.(3)集合的幂集P(B)关于集合的对称差运算和交运算构成环.,31,定理10.16 设是环，则(1)aR，a0=0a=0(2)a,bR，(a)b=a(b)=ab(3)a,b,cR，a(bc)=abac，(bc)a=baca(4)a1,a2,.,an,b1,b2,.,

16、bmR(n,m2),环的运算性质,证(1)aR有 a0=a(0+0)=a0+a0由环中加法的消去律得a0=0.同理可证0a=0.(2)a,bR，有(a)b+ab=(a+a)b=0b=0ab+(a)b=(a+(a)b=0b=0(a)b是ab的负元.由负元惟一性(a)b=ab，同理a(b)=ab,32,同理可证,b1,b2,.,bm有,(4)证明思路：用归纳法证明 a1,a2,.,an 有,于是,证明(4),33,实例,例16 在环中计算(a+b)3,(ab)2,解(a+b)3=(a+b)(a+b)(a+b)=(a2+ba+ab+b2)(a+b)=a3+ba2+aba+b2a+a2b+bab+ab

17、2+b3(ab)2=(ab)(ab)=a2baab+b2,34,特殊的环,定义10.13 设是环(1)若环中乘法 适合交换律，则称R是交换环(2)若环中乘法 存在单位元，则称R是含幺环(3)若a,bR，ab=0 a=0b=0，则称R是无零因子环(4)若R既是交换环、含幺环、无零因子环，则称R是整环(5)设R是整环，且R中至少含有两个元素.若aR*，其中 R*=R0，都有a1R，则称R是域.,35,例17(1)整数环Z、有理数环Q、实数环R、复数环C都是交换 环,含幺环,无零因子环和整环.除了整数环以外都是域.(2)令2Z=2z|zZ，则构成交换环和无零因子环.但不是含幺环和整环.(3)设nZ,

18、n2,则n阶实矩阵的集合Mn(R)关于矩阵加法和乘 法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环.,实例,36,第十章 习题课,主要内容半群、独异点与群的定义群的基本性质子群的判别定理陪集的定义及其性质循环群的生成元和子群环的定义与性质特殊的环,37,基本要求,判断或证明给定集合和运算是否构成半群、独异点和群熟悉群的基本性质能够证明G的子集构成G的子群熟悉陪集的定义和性质会求循环群的生成元及其子群能判断给定代数系统是否为环和域,38,练习1,1.判断下列集合和运算是否构成半群、独异点和群.(1)a 是正整数，G=an|nZ,运算是普通乘法.(2)Q+是正有理数集，运算为普通加法.

19、,解(1)是半群、独异点和群(2)是半群但不是独异点和群方法：根据定义验证，注意运算的封闭性,39,2.设V1=,V2=,其中Z为整数集合,+和 分别代表普通加法和乘法.判断下述集合S是否构成V1和V2的子半群和子独异点.(1)S=2k|kZ(2)S=2k+1|kZ,解(1)S关于V1构成子半群和子独异点，但是关于V2仅构成子 半群(2)S关于V1不构成子半群也不构成子独异点，S关于V2构 成子半群和子独异点,练习2,40,3.设Z18 为模18整数加群,求所有元素的阶.,解：|0|=1,|9|=2，|6|=|12|=3,|3|=|15|=6,|2|=|4|=|8|=|10|=|14|=|16

20、|=9,|1|=|5|=|7|=|11|=|13|=|17|=18,练习3,说明：群中元素的阶可能存在，也可能不存在.对于有限群，每个元素的阶都存在，而且是群的阶的因子.对于无限群，单位元的阶存在，是1；而其它元素的阶可能存在，也可能不存在.（可能所有元素的阶都存在，但是群还是无限群）.,41,有关群性质的证明方法,有关群的简单证明题的主要类型证明群中的元素某些运算结果相等证明群中的子集相等证明与元素的阶相关的命题.证明群的其它性质，如交换性等.常用的证明手段或工具是算律：结合律、消去律和特殊元素相关的等式，如单位元、逆元等幂运算规则 和元素的阶相关的性质.特别地，a为1阶或2阶元的充分必要条

21、件是a1=a.,42,证明方法,证明群中元素相等的基本方法就是用结合律、消去律、单位元及逆元的惟一性、群的幂运算规则等对等式进行变形和化简.证明子集相等的基本方法就是证明两个子集相互包含证明与元素的阶相关的命题，如证明阶相等，阶整除等.证明两个元素的阶r 和 s 相等或证明某个元素的阶等于r，基本方法是证明相互整除.在证明中可以使用结合律、消去律、幂运算规则以及关于元素的阶的性质.特别地，可能用到a为1阶或2阶元的充分必要条件是a1=a.,43,练习5,5设G为群，a是G中的2 阶元，证明G中与a可交换的元素构成G的子群.,证 令H=x|xG xa=ax,下面证明H是G的子群.首先e属于H，H

22、是G的非空子集.任取x,y H，有(xy1)a=x(y1a)=x(a1y)1=x(ay)1=x(ya)1=xa1y1=xay1=axy1=a(xy1)因此 xy1属于H.由判定定理命题得证.,分析：证明子群可以用判定定理，特别是判定定理二.证明的步骤是：验证 H 非空任取 x,yH，证明xy1H,44,6.(1)设G为模12加群,求 在G中所有的左陪集(2)设 X=x|xR,x 0,1,在X上如下定义6个函数：f1(x)=x，f2(x)=1/x,f3(x)=1x,f4(x)=1/(1x),f5(x)=(x1)/x,f6(x)=x/(x1),则G=f1,f2,f3,f4,f5,f6关于函数合成运

23、算构成群.求子群 H=f1,f2 的所有的右陪集.,练习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)f1,f2有3个不同的陪集，它们是：H，Hf3=f3,f5,Hf4=f4,f6.,45,证 a,bZ有ab,abZ,两个运算封闭.任取a,b,cZ(ab)c=(a+b1)c=(a+b1)+c1=a+b+c2 a(bc)=a(b+c1)=a+(b+c1)1=a+b+c2(ab)c=(a+bab)c=a+b+c(ab+ac+bc)+abc a(bc)=a(b+cbc)=a+b+c(ab+ac+bc)+abc 与可结合，1为的单位元.2a为a关于的逆元.Z关于构成交换群,关于构成半群.关于 满足分配律.a(bc)=a(b+c1)=2a+b+cabac1（ab)(ac)=2a+b+cabac1构成环,练习11,11.在整数环中定义和两个运算,a,bZ 有 ab=a+b1,ab=a+bab.证明构成环,