離散數(shù)學(xué)群論

離散教學(xué)DiscreteMathematics2011.09主講：陳哲云青島理工大學(xué)計(jì)算機(jī)工程學(xué)院；XX：：oa群論E餐群的基本概念及性質(zhì)?子群?特殊群（循環(huán)群置換群阿貝爾群Klein四元群）ca群的基本概念【定義】群(Group):設(shè)＜G，*＞是個(gè)代數(shù)系統(tǒng)，如果★滿足(1)封閉(2)可結(jié)合(3)有幺元(4)每個(gè)元素可逆且逆元仍在G中則稱＜6，女＞是個(gè)群，簡(jiǎn)稱G為群。ca群的基本概念典型群舉例:<Z，+><zn，<P(S)，十〉幺元e000X1-Xx-'=：(Ix=0n—x^x^OXca群的基本概念【例1】設(shè)S=R+1｝，S上定義運(yùn)算*:a*b=a+b+ab，試證明＜S,*＞是群。證明從以下幾方面進(jìn)行證明:1）運(yùn)算*在8上封閉;3）存在幺元；2）運(yùn)算*滿足結(jié)合律;4）每個(gè)元素存在逆元。1）運(yùn)算*在S上封閉：任意a，bes,有a*b=a+b+abeR，且a^-1,1#-1。若a*b=_1即a+b+ab=_1，則a=-1或b=-1，與題設(shè)矛盾，故所以a*bes，即運(yùn)算*在S上封閉。.1CQ群的基本概念2)運(yùn)算*滿足結(jié)合律：任意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*滿足結(jié)合律。IL3）存在幺元：若幺元e存在，則對(duì)任意aES，滿足(ae=aci=ci即fa+a+cze

=aLa+a+()ci=ae=0，即幺元存在且為0。8CQ群的基本概念4)每個(gè)元素存在逆元：_____對(duì)于任意aeS，設(shè)a“存在且a-^GS，則{a*a_

丨—O即了a+a-1

+aa-1

=Oa-^=OV^+a+akO得a-4=(?a)/(l+a)eS。t綜上知＜S,*＞是群。ca群的基本概念【練習(xí)1】設(shè)＜6,?＞是一個(gè)群，ugG，在G中定義新的運(yùn)算*，使得對(duì)于任意的a，beG，a*b=aou%b，試證明＜G,*＞也是一個(gè)群。10群的性質(zhì)包括:Is1）可消去性2）群方程的可解性（重點(diǎn)）3）群中無(wú)零元4）有限群運(yùn)算表的特性5）可定義群中元素的冪運(yùn)算（重點(diǎn)）16）可定義元素的階1.可消去性設(shè)＜&*＞是群，則對(duì)任何a,b,cGG,如果有⑴a*b=a*c則b=c。⑵b*a=c*a則b=c。2.群方程可解性設(shè)＜G，*＞是個(gè)群，則對(duì)任何a，bGG,____方程a*x=b或y*a=b在G中存在唯一解?！伎迹航獾男问?？ca群的性質(zhì)【例2】設(shè)群G=<P({a，b})，?>，其中十是集合的對(duì)稱差運(yùn)算，解下列方程：(1){a}十x=0(2)y十{a，b}=ca群的性質(zhì)【練習(xí)2】設(shè)群＜Z8，十8＞，是模8加法，在群中解下列方程：(1)x6=5;(2)2?8y=3.Ji5

■3.群中無(wú)零元。4.有限群的運(yùn)算表的特征<G,*>是個(gè)有限群，則G中每個(gè)元素在★運(yùn)算表中的每一行（列）必出現(xiàn)且僅出現(xiàn)一次。奧用：通過(guò)運(yùn)算表可直接看出代數(shù)系統(tǒng)是否是群。16ca群的性質(zhì)卜5.群中元素的冪運(yùn)算eG,則設(shè)G是群，ae.n=Qa”一1a，n>\\axy\n<-\TA【例3】在群＜Z，+＞與群＜ZV

中，分別計(jì)算3_5與2A17m群的性質(zhì)6.群中元素的階【定義】元素的階(Order)：設(shè)＜G，*＞是群，aeG,使ak=e的最小正整數(shù)k稱為a的階，記作lai。如果這樣的k不存在，則稱a的階是無(wú)限的。注：(1)lai=la“l(fā)(2)lel=118【例3】設(shè)有群〈Z6,十6〉，其中Z產(chǎn)｛0，1，23,4,5｝，

是模6加法，試求出群〈Z6,?6〉中每一元素的階。lit19【練習(xí)3】求群＜Z，+＞，＜Zn，十?＞及＜P(S)，十〉中各元素的階。作業(yè)：課件中的【練習(xí)1】，【練習(xí)3】課本6.4，6.9(1)oa群論?群的基本概念及性質(zhì)舞子群E?特殊群（循環(huán)群置換群阿貝爾群Klein四元群）CQ子群【定義】子群（Subgroup）:群G的非空子集H如果對(duì)于G的運(yùn)算也構(gòu)成一個(gè)群，則稱H為G的子群，記作把G。即：設(shè)＜&，*＞是群，H是G的非空子集，如果＜H，*＞滿足：（1）任何a，bgS有a*beH，（封閉｝⑵幺元eeH，

（有幺元）⑶任何aEH有aJFH,（元素可逆）L則H＜GGQl子群思考：若HSG,則群G中的幺元及元素的逆元在子群H中能否繼承？GQl子群【定理】1)群G的非空子集H對(duì)于G的運(yùn)算構(gòu)成一個(gè)子群的充要條件是：卜SHQVa,beH,<ab]eH。2)H是群G的非空有限子集，H對(duì)于G的運(yùn)算構(gòu)成一個(gè)子群的充要條件是：Va,beH,<abGHoCfl子群【例】設(shè)＜6,*＞是一個(gè)群，定義G的子集H為H={ala*x=x*a，對(duì)于任意的xgG}試問(wèn)H對(duì)于運(yùn)算*能否構(gòu)成＜6,*＞的子群？26oa群論?群的基本概念及性質(zhì)?子群?特殊群（循環(huán)群置換群阿貝爾群Klein四元難m循環(huán)群【定義】循環(huán)群(Cyclicgroup):如果群G可以由一個(gè)元素a生成，即G={aklkeZ}，則稱G為由a生成的一個(gè)循環(huán)群，并稱a為G的一個(gè)生成元(Generator)，記為G=<a>。/匿|r

2fl|L可以證明，若G=<a>,則G=<al>>即a與a.1都是G的生成元。m循環(huán)群循環(huán)群舉例：(1)無(wú)限階循環(huán)群：<z,+>，Z=<1>=<-1>(2)n階循環(huán)群：<Zn，十n>，Zn=<l>=<n-1>這是兩個(gè)重要的循環(huán)群，且可以證明，從同構(gòu)的意義來(lái)說(shuō)，循環(huán)群只有兩個(gè)，即無(wú)限群<2，+>與11階有限群<2，。>。鏵m循環(huán)群【定理1】設(shè)循環(huán)群G=<a>，則lal=IGI，即循環(huán)群的階與生成元的階是相同的。當(dāng)IGI=oo時(shí)，G=<a>={…，a_2,al,e,a\a2，..?}當(dāng)IGI=n時(shí)，G=<a>={a°,al，a2”?”anl}m循環(huán)群關(guān)于循環(huán)群的兩個(gè)問(wèn)題：(1)如何求取循環(huán)群的所有生成元？(2)如何求取循環(huán)群的所有(循環(huán))子群?31m循環(huán)群【定理2】設(shè)G=<a>，(1)若IGI=oo,則G的生成元只有a與a-1。(2)若IGI=n,則G的生成元是ak，其中k是與n互素的正【定理3】設(shè)G=＜a＞，(1)若IGI=oo,則G的循環(huán)子群有無(wú)限個(gè)，即為＜a0＞，＜a＞，＜a2＞，＜a3＞,...(2)若IGI=n,貝ijG的循環(huán)子群為＜a^＞，其中d是n的所有正因子，即G的循環(huán)子群的個(gè)數(shù)為n的正因子個(gè)數(shù)。且|<an/d>l=dom循環(huán)群<lk>=<k>=kZ，醒⑴沒(méi)，+>生成元：1與-1.循環(huán)子群：<1(>>=<0>={0}，<P>=<1>=Z，<12>=<2>=2Z,【例1】求＜乂，+＞與＜28，十s＞的生成元與循環(huán)子群。解：31m循環(huán)群(2)<Z8,十生成元：己知ZS=<1>=<7>,且與8互素的正整數(shù)有1,3，5,7,故么的所有生成元有1_=1，13=3,15=5#17=7可以看到，以上生成元的階都相同，都等于8.Zk1循環(huán)子群，8的所有正因子有1，2,4,8,故義8的所有循環(huán)子群為<p/i>=<0>={0}m循環(huán)群gag卜<18/2>=<14>=<4>={0,4}<18/4>=<12>=<2>={0,2,4,6}<18^>=<1>=Z836m循環(huán)群【例2】設(shè)G=<4,*>，A={arb，c}r*的運(yùn)算表為:(1)找出G的單位元；(2)找出G的冪等元；(3)求^的逆元Zr1和c的逆元r1.(4)G是否為阿貝爾群？(5)求G的生成元和所有子群.匾abcaabcbbcaccabm循環(huán)群【練習(xí)】設(shè)G=<a2>為12階群，求G的所有生成元與循環(huán)子群。38總結(jié)：對(duì)于具體給定的循環(huán)群，能夠求出其所有的生成元及循環(huán)子群。m循環(huán)群作業(yè)：6.56.9co置換群在伽羅瓦理論中起關(guān)鍵作用的就是置換群，它是有限群的特例，是群的典型代表。0幾個(gè)概念:co置換群n元對(duì)稱群＜Sn，。＞的子群稱為n元置換群。n元對(duì)稱群：＜Sn，。＞，其中S，n元置換的集合，“。”為n元置換的復(fù)合運(yùn)算。n元置換集合S上的雙射函數(shù)，S={l，2，...，n}。n元置換的復(fù)合運(yùn)算一函數(shù)的復(fù)合運(yùn)算。ca置換群【定義1】n元置換：有限集合S上的雙射函數(shù)q：S^S稱為S上的n元置換，其中S={1，2,3，...，n}o記法:(12...n、a(2)…cr(n、)j記Sn:S上所有n元置換的集合。且在8。上可以定義置換的復(fù)合運(yùn)算“?！?，稱作置換的“乘法”。I芎I13co置換群^1=cr.-tr4

二=21f\<3rl<321222323223'2；【例1】集合S={1,2,3}上共有6個(gè)不同的置換，它們的集合記為S3={GjJ◎2,3、3；3、3J3、I<2rl<1rl<23、I3、2>tlca置換群置換的“乘法”——復(fù)合運(yùn)算:【例2】fl234)設(shè)<T=bl34j0234、411}則d=4234^,TqG=rl234>*not1342lj<4312；45ca置換群置換的乘法有下述一些性質(zhì):(1)滿足結(jié)合律(ffT)p=(T(Tp),Vff,T,pGSno(2)n元恒等置換15是8?中的單位元即：VTGSnO(3)每個(gè)n元置換在8。中都有逆元46ca置換群■■賺111卜奸?！纠?】集合S=｛1,2,3｝上6個(gè)置換構(gòu)成的集合，a3,a6｝，其子集為3元置換群?！径ɡ?】n元置換的全體構(gòu)成的集合8。對(duì)置換的乘法構(gòu)成一個(gè)群，稱為n元對(duì)稱群。【定義2】n元對(duì)稱群的任何子群都稱為S上的n元置換11117置換的輪換表示法【定義3】設(shè)CT是S的置換，若可取到S的元素aP

…，a/?(r(al)=a2，G(a2):a3”.”<T(ar.l)=ar,(r(ar)=a,，而不變S的其余的元素，則<7稱為一個(gè)輪換，記為