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

離散數(shù)學(xué)教學(xué)群論第1頁，課件共34頁，創(chuàng)作于2023年2月近世代數(shù)—第八章群論§8.1半群和獨(dú)異點(diǎn)§8.2群、阿貝爾群及性質(zhì)結(jié)束§8.3循環(huán)群和置換群

§8.4群的同態(tài)和同構(gòu)第2頁，課件共34頁，創(chuàng)作于2023年2月例1．a(chǎn))〈N，x〉〈{0，1}，x〉是半群，是獨(dú)異點(diǎn),且是〈R，x〉的子半群,子獨(dú)異點(diǎn),〈R，-〉不是半群

*abaabbab§8.1半群和獨(dú)異點(diǎn)b)設(shè)s={a，b}，*定義如右表：即a，b都是右零元∵x,y,zs①x*ys∴運(yùn)算封閉②x*（y*z）=x*z=z

（x*y）*z=z∴結(jié)合律成立

∴〈s，*〉是一半群，該半群稱為二元素右零半群

第3頁，課件共34頁，創(chuàng)作于2023年2月1、有限半群必有等冪元

證明：設(shè)〈s，*〉是半群有限集，需證as，有a*a=abs，因?yàn)檫\(yùn)算封閉，b2=b*bsb3，b4…ss有限ｉ，j，j>ｉ有bi=bjbi=bj=bj-i*bi令p=j－i當(dāng)q≥i,bq=bp·bq（１）又∵p≥1∴k有kp≥i

由（１）bkp=bp*bkp=bP*(bP*bkp)=…=bkp＊bkp∴令a=bkps則a*a=a

∴bkp是等冪元二、半群的性質(zhì)

二、半群的性質(zhì)第4頁，課件共34頁，創(chuàng)作于2023年2月2、獨(dú)異點(diǎn)運(yùn)算表中任何兩行兩列均不相同證明：設(shè)獨(dú)異點(diǎn)的么元為e，a，bs，ab∵a*eb*e＜ｓ，＊＞運(yùn)算表中ａ，ｂ兩行不同，由ａ，ｂ任意性，運(yùn)算表中任兩行不同∵e*ae*b＜ｓ，＊＞運(yùn)算表中ａ，ｂ二列不同由ａ，ｂ任意性，運(yùn)算表中任兩列不同．二、半群的性質(zhì)第5頁，課件共34頁，創(chuàng)作于2023年2月二、半群的性質(zhì)3、若〈s，*〉的么元為e,a，bs，若a，b均有逆元，則a)（a-1）-1=a;b)（a*b）-1=b-1*a-1

證明：a)∵a*a-1=e∴a是a-1的左逆元

a-1*a=e∴a是a-1的右逆元∴(a-1)-1=ab)∵(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=e∴b-1*a-1是a*b的右逆元又∵（b-1*a-1）*（a*b）=b-1*（a-1*a）*b＝e∴b-1*a-1是a*b的左逆元∴（a*b）-1=b-1*a-1返回目錄第6頁，課件共34頁，創(chuàng)作于2023年2月

群論是抽象代數(shù)發(fā)展充分的一個分支，廣泛應(yīng)用于計算，通訊，計算機(jī)科學(xué)，是我們這一章的重點(diǎn)?！?.2群、阿貝爾群及性質(zhì)一、群的定義

1、定義：對二元運(yùn)算*滿足下列四條性質(zhì)的代數(shù)系統(tǒng)A=〈G，*〉，稱為群

1)運(yùn)算封閉，即a,b,G，a*bG2)結(jié)合律，即a,b,cG，a*（b*c）=（a*b）*c3)存在么元e，即aG，e*a=a*e=a4)G中每個元素存在逆元即aG，a-1G,使a*a-1=a-1*a=e第7頁，課件共34頁，創(chuàng)作于2023年2月若G是有限集，稱〈G，*〉為有限群，｜G｜稱為群的階數(shù)，若G是無限集，稱〈G，*〉為無限群

一、群的定義2、有限群3、阿貝爾群

若*滿足交換律，稱〈G，*〉為阿貝爾群，或可交換群或加法群，（此時，‘*’符號可用‘+’代替，a-1可寫為-a，么元e可寫為0）第8頁，課件共34頁，創(chuàng)作于2023年2月例1．〈I，+〉是一個群。考慮是否為阿貝爾群？證明：①〈I，+〉運(yùn)算封閉②∵普通加法+滿足結(jié)合律③其中0為么元④

aI，-a是a的逆元一、群的定義第9頁，課件共34頁，創(chuàng)作于2023年2月b)〈Q+，x〉是阿貝爾群,

〈Nk，+k〉是阿貝爾群,〈Nk，xk〉不是群（∵0沒有逆元）一、群的定義

c)設(shè)P是集合A的雙射函數(shù)集合，則〈P，復(fù)合運(yùn)算〉是一個群，但不是阿貝爾群d）運(yùn)算max，min一般不能用作群的二元運(yùn)算因?yàn)閷?yīng)運(yùn)算max，min，逆元不存在第10頁，課件共34頁，創(chuàng)作于2023年2月二、群的性質(zhì)二、群的性質(zhì)1、有關(guān)半群和獨(dú)異點(diǎn)的性質(zhì)在群中全部成立,（a*b）-1=b-1*a-1

阿貝爾群半群獨(dú)異點(diǎn)群第11頁，課件共34頁，創(chuàng)作于2023年2月若〈G，*〉是一個群，則a，bGa）存在唯一的x，使得a*x=bb）存在唯一的y，使得y*a=b證：a）存在性:令x=a-1*b，則a*(a-1*b)=a*a-1*b=e*b=b

唯一性:若a*x=b，則a-1*a*x=a-1*b∴x=a-1*bb）略二、群的性質(zhì)2、Th2:第12頁，課件共34頁，創(chuàng)作于2023年2月3、

可逆必可約，反之不成立

Th3:（a）a*b=a*c=>b=c

（b）b*a=c*a=>b=c證：∵a*b=a*c=>a-1*（a*b）=a-1*（a*c）

=>b=c二、群的性質(zhì)第13頁，課件共34頁，創(chuàng)作于2023年2月4、Th5:么元是群中唯一的等冪元

證：若x是等冪元素，則：x=e*x=（x-1*x）*x=x-1*（x*x）＝x-1*x=e

二、群的性質(zhì)5、Th4:群〈G，*〉的運(yùn)算表中的每一行或每一列是G中元素的置換

定義：有限集合s到s的一個雙射，稱為s的一個置換

第14頁，課件共34頁，創(chuàng)作于2023年2月定理：群〈G，*〉的運(yùn)算表中的每一行或每一列是G中元素的置換證：①先證運(yùn)算表中每一行（列）中的元素不能出現(xiàn)二次（單射）

二、群的性質(zhì)∵若a*b1=a*b2=k，且b1b2，與可約性矛盾②再證G中任一元素在任一行（列）中均出現(xiàn)（滿射）∵考察對應(yīng)于a的那一行，bG，則b=a*（a-1*b）∴b出現(xiàn)在a那一行，由ａ，ｂ任意性得證．③因〈G，*〉中有么元，∴任二行（列）均不相同（即各個置換均不相同）證畢第15頁，課件共34頁，創(chuàng)作于2023年2月6、有限群舉例①

一階群僅有1個②

二階群僅有1個

③

三階群僅有1個

④四階群僅有2個（證略）*eee*eaeeaaae*eabeeabaabebbea二、群的性質(zhì)第16頁，課件共34頁，創(chuàng)作于2023年2月7、Th1:群中不可能有零元證：當(dāng)│G│=1，它的唯一元素視為么元當(dāng)G>1且〈G，*〉有零元，則xG，都有x*=*x=e

無逆元，這與G是群矛盾二、群的性質(zhì)第17頁，課件共34頁，創(chuàng)作于2023年2月8、設(shè)〈G，x〉是一個群，則〈G，*〉是阿貝爾群的充要條件是證：充分性：若a，bG，因?yàn)闈M足交換律有(a*b)*(a*b)=(a*a)*(b*b)反之，a-1*(a*b)*(a*b)*b-1=a-1*(a*a)*(b*b)*b-1∴b*a=a*b∴〈G，*〉是阿貝爾群二、群的性質(zhì)a，bG，有（a*b）*（a*b）=（a*a）*（b*b）第18頁，課件共34頁，創(chuàng)作于2023年2月必要性：若〈G，*〉是阿貝爾群，則a，bG，ａ*b=b*a∴a*（a*b）*b=a*（b*a）*a∴（a*a）*（b*b）=（a*b）*（a*a）二、群的性質(zhì)第19頁，課件共34頁，創(chuàng)作于2023年2月

§8.3循環(huán)群和置換群一.循環(huán)群定義定義:設(shè)<G,*>是一個群,若存在gG,使得aG,iI（I為整數(shù)集），有a=gi,則稱<G,*>是一個循環(huán)群,g是<G,*>的生成元?？煞Q<G,*>是由g生成的,。二.性質(zhì)1.每個循環(huán)群是阿貝爾群證:設(shè)g是<G,*>的生成元則a,bG,a=gr,b=gsa*b=gr*gs=gr+s=gs*gr=b*a下一頁第20頁，課件共34頁，創(chuàng)作于2023年2月2.<G,*>是由g生成的有限循環(huán)群,若|G|=n,即g的階為n,則G={g1,g2,,gn}

證:a)證g的階為n。先證：若m<n,則gm≠e

（反證法）若m<n,且gm=e,gkG,k=mq+r,0≤r<m∴gk=gmq+r=gmqgr=gr∴G中最多有m個不同元素,這與|G|=n矛盾，所以g的階為nb)證G中的元素全不相同證:若gi=gj,1≤i<j≤ngj-i=e∵0≤j-i<n∴這與a)矛盾

c)∵giG且|G|=n,1≤i≤n∴G={g1,,gn}∵<G,*>是一個群,故必有么元，∴gn=eG={g0,g1,

g2,

,gn-1}下一頁第21頁，課件共34頁，創(chuàng)作于2023年2月例1例1.a)<I,+>是無限循環(huán)群,其中-1,1均是生成元

b)<{5j|jI},+>是無限循環(huán)群,其中-5,5是均生成元

c)Nk={[0],,[k-1]}，<Nk,+k>是有限循環(huán)群,其中[1]是生成元,與k互質(zhì)的任一數(shù)也是生成元，這里Nk={[0],,[k-1]},[x]是I中的模k等價類+k定義為:[x]+k[y]=[x+y]+4[0][1][2][3] [3][0][0][1][2][3] [3]2=[6]=[2] [1][1][2][3][0] [3]3=[5]=[1] [2][2][3][0][1] [3]4=[4]=[0] [3][3][0][1][2]下一頁二.循環(huán)群性質(zhì)第22頁，課件共34頁，創(chuàng)作于2023年2月例2.設(shè)G={α,β,γ,δ}，證<G,*>是循環(huán)群*αβγδααβγδββαδγγγδβαδδγαβ證:∵γ2=β,γ3=δ,γ4=α∴運(yùn)算表可改寫如下:*αγγ2γ3ααγ

γ2γ3γγγ2γ3αγ2γ2γ2αγγ3γ3α

γγ2

由上表看出G={α,β,γ,δ}是一個循環(huán)群下一頁第23頁，課件共34頁，創(chuàng)作于2023年2月置換群三、置換群一.復(fù)合運(yùn)算1.定義:一個具有n個元素的集合S,將S上所有n!個不同的置換所生成的集合記作Sn①例:A={1,2}有二個置換1=122=1212

21

A={1,2,3}有6個置換

P0p1p2p3p4p5123

123123123123123123213321132231312下一頁第24頁，課件共34頁，創(chuàng)作于2023年2月二元運(yùn)算②二元運(yùn)算pipj表示先進(jìn)行置換pj,再進(jìn)行置換pi,稱左復(fù)合pipj表示先進(jìn)行置換pi,再進(jìn)行置換pj,稱右復(fù)合例:左復(fù)合123123123

=321213231右復(fù)合123123123

=321213312下一頁第25頁，課件共34頁，創(chuàng)作于2023年2月<Sn,>是一個群證:(1)封閉性p1,p2Sn，須證p1p2Sn∵若a,bS且ab則當(dāng)a,b被p2置換為c,d時,必有cd

當(dāng)c,d被p1置換為e,f時,必有efp1p2將S中任二個不同元素映射到S中的二個不同元素p1p2Sn(有限集A上的單射必為滿射)(2)運(yùn)算滿足結(jié)合律

p1，p2，p3Sn,xS有p3(x)=y，p2(y)=z,p1(z)=u,

則(p1p2)p3(x)=u,p1(p2p3)(x)=p1(z)=up1(p2p3)=(p1p2)p3(3)恒等置換為么元

(4)pSn,xS,存在逆元p-1,其中若p(x)=y則p-1(y)=x.所以，<Sn,>是一個群下一頁第26頁，課件共34頁，創(chuàng)作于2023年2月例:p1=123p1-1=123p1p1-1=123312231123四、置換群與對稱群定義:<Sn,>的任何子群稱為集合S上的一個置換群<Sn,>稱為S上的對稱群。例:設(shè)S={1,2,3}，試寫出S的所有的置換群及對稱群解:S上對稱群Sn={p0,p1,p2,p3,p4,p5}置換群以p1為生成元<{p1,p0},>的對稱群,以p2為生成元<{p2,p0},>對稱群以p3為生成元<{p3,p0},>對稱群,以p4為生成元<{p4,p5,p0},>對稱群。下一頁第27頁，課件共34頁，創(chuàng)作于2023年2月同態(tài)與同構(gòu)

§8.4群的同態(tài)與同構(gòu)一.同構(gòu)與同態(tài)1.同構(gòu)定義代數(shù)A=<S,*>和A’=<S’,*’>若1)存在從S到S’的雙射函數(shù)h2)a,bS有h(a*b)=h(a)*’h(b)則稱代數(shù)A與代數(shù)A’是同構(gòu)的,記為<A,*>≌<A’,*’>注:1)A與A’同構(gòu),則調(diào)換符號能從A得到A’,可以認(rèn)為它們是相同的代數(shù);2)若e是A的么元,則h(e)是A’的么元

∵yS’,xS,y=h(x)y*’h(

e)=h(x)

*’h(e)=h(x*e)=y

若o是A的零元,則h(o)是A’的零元下一頁第28頁，課件共34頁，創(chuàng)作于2023年2月一.同構(gòu)與同態(tài)例1.證<R+,>同構(gòu)于<R,+>證:i)令h:R+R,h(x)=㏒x

則因?qū)?shù)函數(shù)單調(diào)增h是單射yR,x=2y使y=㏒2y=h(x)h是滿射h是從R+到R的雙射

ii)h(ab)=㏒（ab）=㏒a+㏒b=h(a)+h(b)<R+,,1>同構(gòu)于<R,+,0>下一頁第29頁，課件共34頁，創(chuàng)作于2023年2月一.同構(gòu)與同態(tài)例2.證明<N,+>和<I+,x>不同構(gòu)證:反證法設(shè)h是<N,+>到<I+,x>的一個同構(gòu)映射,x>2

則:p=h(x)=h(x+0)=h(x)h(0)1)7=h(7)=h(7+0)=h(7)h(0)h(7)=1或h(0)=12)7=h(7)=h(6+1)=h(6)h(1)h(6)=1或h(1)=1

1至少是兩個元素的象,這與h是雙射矛盾

<N,+>和<I+,x>不同構(gòu)下一頁第30頁，課件共34頁，創(chuàng)作于2023年2月證:G={g0,g1,g2,g3,}f:NG,f(n)=gnf(n1+n2)=gn1+n2=gn1*gn2=f(n1)*f(n2)一、同構(gòu)與同態(tài)

例3.證明<N,+>同構(gòu)于無限階循環(huán)群<G,*>

2.同構(gòu)關(guān)系是一個等價關(guān)系3.同態(tài)定義設(shè)A=<S,*>和A’=<S’,*’>若(1)h:SS’是一函數(shù)(2)a,bS，有h(a*b)=h(a)*’h(b)則稱h是從A到A’的一個同態(tài)函數(shù),若h是單射,滿射,雙射,則分別稱h是單一同態(tài),滿同態(tài),同構(gòu)。特別地，若A=A’,且h是同構(gòu),稱h是自同構(gòu)下一頁第31頁，課件共34頁，創(chuàng)作于2023年2月例1例1.a)fk:II,fk(x)=kx，其中I為整數(shù)集合∵fk(x1+x2)=k(x1+x2)=kx1+kx2=fk(x1)+fk(x2)fk是從<I,+>到<I,+>的自同態(tài),若k0,則fk是單一同態(tài),若k=1,則fk是<I,+>到<I,