离散数学群论

离散教学DiscreteMathematics2011.09主讲：陈哲云青岛理工大学计算机工程学院；XX：：oa群论E餐群的基本概念及性质♦子群♦特殊群（循环群置换群阿贝尔群Klein四元群）ca群的基本概念【定义】群(Group):设＜G，*＞是个代数系统，如果★满足(1)封闭(2)可结合(3)有幺元(4)每个元素可逆且逆元仍在G中则称＜6，女＞是个群，简称G为群。ca群的基本概念典型群举例:<Z，+><zn，<P(S)，㊉〉幺元e000X1-Xx-'=：(Ix=0n—x^x^OXca群的基本概念【例1】设S=R+1｝，S上定义运算*:a*b=a+b+ab，试证明＜S,*＞是群。证明从以下几方面进行证明:1）运算*在8上封闭;3）存在幺元；2）运算*满足结合律;4）每个元素存在逆元。1）运算*在S上封闭：任意a，bes,有a*b=a+b+abeR，且a^-1,1#-1。若a*b=_1即a+b+ab=_1，则a=-1或b=-1，与题设矛盾，故所以a*bes，即运算*在S上封闭。.1CQ群的基本概念2)运算*满足结合律：任意a，b,cFS,有(a:1:b):{:c=(a+b+ab):icc=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac+bc+abc，且a^(b*c)=a^(b+c+bc)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac+bc+abc，所以，(a*b)*c=a*(b*c)，Bp*满足结合律。IL3）存在幺元：若幺元e存在，则对任意aES，满足(ae=aci=ci即fa+a+cze

=aLa+a+()ci=ae=0，即幺元存在且为0。8CQ群的基本概念4)每个元素存在逆元：_____对于任意aeS，设a“存在且a-^GS，则{a*a_

丨—O即了a+a-1

+aa-1

=Oa-^=OV^+a+akO得a-4=(・a)/(l+a)eS。t综上知＜S,*＞是群。ca群的基本概念【练习1】设＜6,◦＞是一个群，ugG，在G中定义新的运算*，使得对于任意的a，beG，a*b=aou%b，试证明＜G,*＞也是一个群。10群的性质包括:Is1）可消去性2）群方程的可解性（重点）3）群中无零元4）有限群运算表的特性5）可定义群中元素的幂运算（重点）16）可定义元素的阶1.可消去性设＜&*＞是群，则对任何a,b,cGG,如果有⑴a*b=a*c则b=c。⑵b*a=c*a则b=c。2.群方程可解性设＜G，*＞是个群，则对任何a，bGG,____方程a*x=b或y*a=b在G中存在唯一解。▲思考：解的形式？ca群的性质【例2】设群G=<P({a，b})，©>，其中㊉是集合的对称差运算，解下列方程：(1){a}㊉x=0(2)y㊉{a，b}={b}ca群的性质【练习2】设群＜Z8，㊉8＞，是模8加法，在群中解下列方程：(1)x6=5;(2)2®8y=3.Ji5

■3.群中无零元。4.有限群的运算表的特征<G,*>是个有限群，则G中每个元素在★运算表中的每一行（列）必出现且仅出现一次。奥用：通过运算表可直接看出代数系统是否是群。16ca群的性质卜5.群中元素的幂运算eG,则设G是群，ae.n=Qa”一1a，n>\\axy\n<-\TA【例3】在群＜Z，+＞与群＜ZV

中，分别计算3_5与2A17m群的性质6.群中元素的阶【定义】元素的阶(Order)：设＜G，*＞是群，aeG,使ak=e的最小正整数k称为a的阶，记作lai。如果这样的k不存在，则称a的阶是无限的。注：(1)lai=la“l(2)lel=118【例3】设有群〈Z6,㊉6〉，其中Z产｛0，1，23,4,5｝，

是模6加法，试求出群〈Z6,©6〉中每一元素的阶。lit19【练习3】求群＜Z，+＞，＜Zn，㊉„＞及＜P(S)，㊉〉中各元素的阶。作业：课件中的【练习1】，【练习3】课本6.4，6.9(1)oa群论♦群的基本概念及性质舞子群E♦特殊群（循环群置换群阿贝尔群Klein四元群）CQ子群【定义】子群（Subgroup）:群G的非空子集H如果对于G的运算也构成一个群，则称H为G的子群，记作把G。即：设＜&，*＞是群，H是G的非空子集，如果＜H，*＞满足：（1）任何a，bgS有a*beH，（封闭｝⑵幺元eeH，

（有幺元）⑶任何aEH有aJFH,（元素可逆）L则H＜GGQl子群思考：若HSG,则群G中的幺元及元素的逆元在子群H中能否继承？GQl子群【定理】1)群G的非空子集H对于G的运算构成一个子群的充要条件是：卜SHQVa,beH,<ab]eH。2)H是群G的非空有限子集，H对于G的运算构成一个子群的充要条件是：Va,beH,<abGHoCfl子群【例】设＜6,*＞是一个群，定义G的子集H为H={ala*x=x*a，对于任意的xgG}试问H对于运算*能否构成＜6,*＞的子群？26oa群论♦群的基本概念及性质♦子群♦特殊群（循环群置换群阿贝尔群Klein四元難m循环群【定义】循环群(Cyclicgroup):如果群G可以由一个元素a生成，即G={aklkeZ}，则称G为由a生成的一个循环群，并称a为G的一个生成元(Generator)，记为G=<a>。/匿|r

2fl|L可以证明，若G=<a>,则G=<al>>即a与a.1都是G的生成元。m循环群循环群举例：(1)无限阶循环群：<z,+>，Z=<1>=<-1>(2)n阶循环群：<Zn，㊉n>，Zn=<l>=<n-1>这是两个重要的循环群，且可以证明，从同构的意义来说，循环群只有两个，即无限群<2，+>与11阶有限群<2，。>。鏵m循环群【定理1】设循环群G=<a>，则lal=IGI，即循环群的阶与生成元的阶是相同的。当IGI=oo时，G=<a>={…，a_2,al,e,a\a2，..・}当IGI=n时，G=<a>={a°,al，a2”•”anl}m循环群关于循环群的两个问题：(1)如何求取循环群的所有生成元？(2)如何求取循环群的所有(循环)子群?31m循环群【定理2】设G=<a>，(1)若IGI=oo,则G的生成元只有a与a-1。(2)若IGI=n,则G的生成元是ak，其中k是与n互素的正【定理3】设G=＜a＞，(1)若IGI=oo,则G的循环子群有无限个，即为＜a0＞，＜a＞，＜a2＞，＜a3＞,...(2)若IGI=n,贝ijG的循环子群为＜a^＞，其中d是n的所有正因子，即G的循环子群的个数为n的正因子个数。且|<an/d>l=dom循环群<lk>=<k>=kZ，醒⑴没，+>生成元：1与-1.循环子群：<1(>>=<0>={0}，<P>=<1>=Z，<12>=<2>=2Z,【例1】求＜乂，+＞与＜28，㊉s＞的生成元与循环子群。解：31m循环群(2)<Z8,㊉生成元：己知ZS=<1>=<7>,且与8互素的正整数有1,3，5,7,故么的所有生成元有1_=1，13=3,15=5#17=7可以看到，以上生成元的阶都相同，都等于8.Zk1循环子群，8的所有正因子有1，2,4,8,故义8的所有循环子群为<p/i>=<0>={0}m循环群gag卜<18/2>=<14>=<4>={0,4}<18/4>=<12>=<2>={0,2,4,6}<18^>=<1>=Z836m循环群【例2】设G=<4,*>，A={arb，c}r*的运算表为:(1)找出G的单位元；(2)找出G的幂等元；(3)求^的逆元Zr1和c的逆元r1.(4)G是否为阿贝尔群？(5)求G的生成元和所有子群.匾abcaabcbbcaccabm循环群【练习】设G=<a2>为12阶群，求G的所有生成元与循环子群。38总结：对于具体给定的循环群，能够求出其所有的生成元及循环子群。m循环群作业：6.56.9co置换群在伽罗瓦理论中起关键作用的就是置换群，它是有限群的特例，是群的典型代表。0几个概念:co置换群n元对称群＜Sn，。＞的子群称为n元置换群。n元对称群：＜Sn，。＞，其中S，n元置换的集合，“。”为n元置换的复合运算。n元置换集合S上的双射函数，S={l，2，...，n}。n元置换的复合运算一函数的复合运算。ca置换群【定义1】n元置换：有限集合S上的双射函数q：S^S称为S上的n元置换，其中S={1，2,3，...，n}o记法:(12...n、a(2)…cr(n、)j记Sn:S上所有n元置换的集合。且在8。上可以定义置换的复合运算“。”，称作置换的“乘法”。I芎I13co置换群^1=cr.-tr4

二=21f\<3rl<321222323223'2；【例1】集合S={1,2,3}上共有6个不同的置换，它们的集合记为S3={GjJ◎2,3、3；3、3J3、I<2rl<1rl<23、I3、2>tlca置换群置换的“乘法”——复合运算:【例2】fl234)设<T=bl34j0234、411}则d=4234^,TqG=rl234>*not1342lj<4312；45ca置换群置换的乘法有下述一些性质:(1)满足结合律(ffT)p=(T(Tp),Vff,T,pGSno(2)n元恒等置换15是8„中的单位元即：VTGSnO(3)每个n元置换在8。中都有逆元46ca置换群■■賺111卜奸。【例3】集合S=｛1,2,3｝上6个置换构成的集合，a3,a6｝，其子集为3元置换群。【定理2】n元置换的全体构成的集合8。对置换的乘法构成一个群，称为n元对称群。【定义2】n元对称群的任何子群都称为S上的n元置换11117置换的轮换表示法【定义3】设CT是S的置换，若可取到S的元素aP

…，a/®(r(al)=a2，G(a2):a3”.”<T(ar.l)=ar,(r(ar)=a,，而不变S的其余的元素，则<7称为一个轮换，记为