離散數學第四章代數系統

離散數學第四章代數系統1第1頁，共73頁，2023年，2月20日，星期一離散數學

§4.群

群的基本概念

群的性質

群中元素的階

循環(huán)群

置換群

子群

陪集與拉格郎日(Lagrange)定理2第2頁，共73頁，2023年，2月20日，星期一離散數學§4.群定義1.群(group)

設(G,*)是含幺半群。若G中每個元素都有逆元，即g(gGg-1G)，則稱(G,*)為群。注：群就是每個元素都有逆元的含幺半群；

驗證一個代數系統是群，必須驗證以下四點：

(1)封閉性

(2)結合律

(3)有幺元

(4)有逆元例1.(I,),(Mnn,),(Nm,m),(2X,),(P[x],)都不是群上一節(jié)中的五個例子(I,),(Mnn,),(Nm,m),(2X,),3第3頁，共73頁，2023年，2月20日，星期一離散數學(P[x],)已經驗證都是含幺半群；但它們都不是群，原因就在于不能保證每個元素都有逆元。例2.(I,+)是一個群這里：I是整數集合，+是整數加法，由算術知識知：

(1)封閉性：兩個整數之和仍為整數，且結果唯一。即

a,b,aIbIa+bI

；

(2)結合律：整數加法滿足結合律。即

a,b,cI,(a+b)+c=a+(b+c)

；

(3)有幺元：取0I,aI,有a+0＝0+a＝a。由幺元的定義知，0是關于+的幺元；

(4)有逆元：aI，取-aI，有a+(-a)＝(-a)+a＝0。由逆元的定義知I中每個元素都有逆元；4第4頁，共73頁，2023年，2月20日，星期一離散數學

由群的定義知(I,+)是群。例3.

(Mnn,+)是一個群這里：Mnn是nn實矩陣的全體，+是矩陣加法。由線性代數知：

(1)封閉性：兩個nn實矩陣相加仍為nn實矩陣，且結果唯一。即

A,B,AMnnBMnnA+BMnn；

(2)結合律：實矩陣加法滿足結合律。即

A,B,CI,(A+B)+C=A+(B+C)

；

(3)有幺元：取零矩陣0Mnn,AMnn,有

A+0=0+A=A。由幺元的定義知0是關于+的幺元；

(4)有逆元：AMnn,取-AMnn,有5第5頁，共73頁，2023年，2月20日，星期一離散數學

A+(-A)=(-A)+A＝0.

由逆元的定義知Mnn中每個元素都有逆元；由群的定義知(Mnn,+)是群。例4.(Nm,+m)是一個群這里：Nm

＝{[0]m,[1]m,…,[m-1]m},+m定義如下

[i]m,[j]mNm,[i]m+m[j]m

＝[(i+j)modm]m(1)封閉性：由于0(i+j)modm<m,且結果唯一。即

[i]m,[j]m,[i]mNm[j]mNm[i]m+m[j]mNm

；

(2)結合律：由于[i]m

，[j]m

，[k]mNm,有

([i]m+m[j]m)+m[k]m＝[(i+j)modm]m+m[k]m

＝[((i+j)modm+k)modm]m＝[(i+j+k)modm]m

[i]m+m([j]m+m[k]m)＝[i]m+m[(j+k)modm]m6第6頁，共73頁，2023年，2月20日，星期一離散數學

＝[(I+(j+k)modm)modm]m＝[(i+j+k)modm]m

故有([i]m+m[j]m)+m[k]m

＝[i]m+m([j]m+m[k]m)

即+m滿足結合律；

(3)有幺元：取[0]mNm,[i]mNm,有

[0]m+m[i]m

＝[(0+i)modm]m

＝[i]m[i]m+m[0]m

＝[(i+0)modm]m

＝[i]m

由幺元的定義知[0]m是關于+m的幺元；

(4)有逆元：[i]mNm,取[m-i]mNm,有

[i]m+m[m-i]m

＝[(i+(m-i))modm]m

＝[0]m[m-i]m+m[i]m

＝[((m-i)+i)modm]m

＝[0]m

由逆元的定義知Nm中每個元素都有逆元；由群的定義知(Nm,+m)是群。7第7頁，共73頁，2023年，2月20日，星期一離散數學例5.(2X,)是一個群這里：X是一非空集合，2X是X的冪集，是集合的環(huán)和運算，即AB=(AB)(BA)。由集合一章知：

(1)封閉性：環(huán)和是2X上的二元運算，具有封閉性；

(2)結合律：環(huán)和運算滿足結合律；

(3)有幺元：關于環(huán)和運算的幺元是；

(4)有逆元：A2X，A的逆元是其本身；由群的定義知(2X,)是群。例6.(P[x],+)是一個群這里：P[x]是實系數多項式的全體，+是多項式的加法。

(1)封閉性：由于兩個多項式之和仍為多項式，且結果唯一。即p(x),q(x),8第8頁，共73頁，2023年，2月20日，星期一離散數學

p(x)P[x]q(x)P[x]p(x)+q(x)P[x]；

(2)結合律：由于實數加法滿足結合律，故多項式的加法滿足結合律。即p(x),q(x),r(x)P[x],

(p(x)+q(x))+r(x)=p(x)+(q(x)+r(x))；

(3)有幺元：取0P[x]，p(x)P[x]，有

0+p(x)=p(x)+0=p(x)

由么元的定義知0是關于+的么元；

(4)有逆元：

p(x)P[x]，取-p(x)P[x]，有

p(x)+(-p(x))=(-p(x))+p(x)=0

由逆元的定義知P[x]中每個元素都有逆元。由群的定義知，(P[x],+)是群。定義2.交換群(Abel群加群)

設(G,*)是群。若*運算滿足交換律，則稱(G,*)是交換9第9頁，共73頁，2023年，2月20日，星期一離散數學群。

例7.前面的例2，例3，例4，例5，例6都是交換群。定義3.群的階(rank)設(G,*)是群。稱G的勢(基數)為群(G,*)的階。注：群的階反映群的大??；

由定義3知有限群的階就是G中元素的個數；無限群的階是G的勢；群的階統一記為|G|

。

定理1.設(G,*)是群，|G|2。則

(1)G中每個元素的逆元是唯一的;(2)G中無零元。10第10頁，共73頁，2023年，2月20日，星期一離散數學[證].(1)由于群有結合律，所以由§1定理2可知，逆元唯一；

(2)采用反證法：若零元0G，則對任何元素gG，都有0*g=g*0=0

(1)

由于G是群，每個元都有逆元。設0的逆元為g0，則有

0*g0=g0

*0=e(2)e為群G的幺元。根據(1)，特別地有

0*g0=g0

*0=0(3)

由(2),(3)有e=0

因而對群G的任何元g，都有

g=g*e=g*0=0

故此|G|=1。因而與定理所給條件|G|2矛盾。11第11頁，共73頁，2023年，2月20日，星期一離散數學定理2.

設(G,*)是群。則a,bG，有

(1)反身律：(a-1)-1

=a；

(2)鞋襪律：(a*b)-1=b-1*a-1。[證].(1)aG，(a-1)-1=(a-1)-1*e

=(a-1)-1*(a-1*a)=((a-1)-1*a-1)

*a(結合律)=e

*a=a；

(2)a,bG，(a*b)-1=

(a*b)-1*e

=(a*b)-1*(a*b*b-1*

a-1)(結合律)=((a*b)-1*(a*b))*(b-1*

a-1)(結合律)=e

*(b-1*

a-1)=b-1*a-1。12第12頁，共73頁，2023年，2月20日，星期一離散數學定理3

設(G,*)是群，則*運算滿足消去律。即x,y,zG,

x

y=x

z

y=z

；

y

x=z

x

y=z。[證].只證第一式。x,y,zG,

y=e*

y=(x-1*x)*

y

=x-1*(x*

y)(結合律)=x-1*(x*

z)(條件：x

y=x

z

)

=(x-1*x)*

z(結合律)

=e*

z=z定理4.在有限群(G,*)(設|G|=n)的*運算的運算表中，每13第13頁，共73頁，2023年，2月20日，星期一離散數學一行(每一列)都與G中元素的自然順序構成一個置換(雙射)。也就是說，每個元素在每行(每列)必出現一次且只出現一次。注：因此n階有限群的運算表是由G中元素的

(n個行或n個列所形成的)n個置換所構成的。這個性質來源于群中每個元素都有逆元。例8.(G,o)是一有限群這里：

G={e,a,b,c},o運算的運算表如右：

(1)封閉性：由表1可得；

(2)結合律：留待后證；

(3)有幺元：e；oeabceeabcaaecbbbceaccbae表114第14頁，共73頁，2023年，2月20日，星期一離散數學

(4)有逆元：e-1=e,a-1=a,b-1=b,c-1=c。例如其第三行就與表頭元素構成一置換P3。此群一般稱為Klein4-群，又稱為幾何群或運動群。注：Klein日耳曼民族，幾何學家，我國著名幾何學家蘇步青是他的晚年弟子；

。[證].只證關于第i(1in)行結論成立。我們設

G={a1(=e),a2,,an}構造自然眏射fi:GG使得對任何的aG，fi(a)=ai*

a為此，只須證明fi是一雙射函數即可。15第15頁，共73頁，2023年，2月20日，星期一離散數學

①后者唯一：

aj,

akG，aj=ak

ai*

aj=ai*

ak

fi(aj)=fi(ak)；

②單射：

aj,

akG，fi(aj)=fi(ak)

ai*

aj=ai*

ak

aj=ak

(消去律)；③滿射：

ajG,根據群有逆元及運算封閉性知,

ak=

ai-1

*

ajG,使得

fi(ak)=

ai*

ak

=

ai*(ai-1

*

aj)16第16頁，共73頁，2023年，2月20日，星期一離散數學

=

(

ai*ai-1

)

*

aj(結合律)

=

e*

aj

=

aj

。定義4.元素的乘冪設(G,*)是群。G中元素乘冪的定義在半群定義的基礎上，增補如下：xG，

x0＝e；x-n＝(x-1)n

(nN)。注：從而，我們就將半群中元素的乘冪是在自然數N范圍內進行擴展到群中元素的乘冪是在整數I范圍內進行。

同樣可以由歸納法證明，當指數為整數時，指數定律在群中成立。即任取

xG，m,nI，有

(1)xm

xn=xm＋n=

xn

xm

；17第17頁，共73頁，2023年，2月20日，星期一離散數學

(2)(xm)n=xmn=

(xn)m；

證明時，固定整數m

，對正整數n使用歸納法，當n是負整數時，就變成x-1的正整數指數運算。例9.在(I,+)群中，取1I，有

10＝0,1n＝n；

1-1＝-1,1-n＝-n；

1n+1-n＝n-n＝0。例10.設X是由方程x4＝1的4個根組成的集合，即

X＝{1,-1,i,-i}其中i＝。設是復數乘法，其運算表如表2。由表2容易驗證(X,*)是群。由表2可知：

11＝1,12＝1,13＝1,14＝1,…；

1-1i-i11-1i-i-1-11-iiii-i-11-i-ii1-1表218第18頁，共73頁，2023年，2月20日，星期一離散數學

(-1)1＝-1,(-1)2＝1,(-1)3＝-1,(-1)4＝1,(-1)5＝-1,…；

(i)1＝i,(i)2＝-1,(i)3＝-i,(i)4＝1,(i)5＝i,…；

(-i)1＝-i,(-i)2＝-1,(-i)3＝i,(-i)4＝1,(-i)5＝-i,…。注：從上例各元素乘冪的結果看，都有一個現象，就是4次乘冪的結果是1，為群的幺元；而這正好說明它們都是四次方程x4＝1的根；

群的元素乘冪回歸幺元是群的元素一個比較普遍的現象；這點被總結成下面的定義。它在尋找群的子群，元素的求逆，元素性質的探討等方面都有著廣泛的作用。定義5.元素的階(rank)設(G,*)是群。gG，我們稱

k=min{m:mN\{0}gm＝e}為元素g的階；若這樣的k不存在，則稱g的階為無窮。19第19頁，共73頁，2023年，2月20日，星期一離散數學注：從定義可知，元素g的階k是使gm＝e成立的最小正整數；

由于元素的自乘冪是一次一次乘的，因此這個無窮只能是可數無窮；

由定義5可知，么元是群中唯一的一個一階元素；

這里要強調的是，我們現在有群的階和群中元素的階這樣兩個階的概念，這是兩個根本不同的概念。群的階是指群中元素的個數，而群中元素的階是指使gm＝e成立的最小正整數k；一個是對整體而言，一個是對整體中的個體而言。例11.在例8的Klein4-群(G,o)中，幺元e的階為1；其它元素a,b,c的階均為2；在例9的群(I,+)中，么元0的階為1；其他元素的階均為無窮；在例10的群(X,*)中，幺元1的階為1；-1的階為2；i和-i的階均為4。20第20頁，共73頁，2023年，2月20日，星期一離散數學定理5.設(G,*)是群。gG，

(1)若g的階為n，則g1,g2,…,gn(=e)

互不相同；

(2)若g的階為無窮，則g0(=e),g1,

g2,…,

gn,…互不相同。[證].采用反證法

(1)否則，設有gi=gj(1ijn)，于是有

gj-i=gj+(-i)=gj*g-i(指數律)=gi*g-i(反證假設：gi=gj)=e

即有1j-in，使gj-i=e。這與g的階為n，具有最小性，矛盾。故有g1,g2,…,gn互不相同。

(2)同理可證。

21第21頁，共73頁，2023年，2月20日，星期一離散數學例12.在例10的群(X,*)中,元素i的階為4,所以有i1,i2,i3,i4互不相同；-i的階也為4，所以(-i)1,(-i)2,(-i)3,(-i)4也互不相同。定理6.設(G,*)是群。gG，g與g-1有相同的階。[證].分兩種情況來證：

(1)設g的階有限，為n。從而gn=e。由于

(g-1)n=(gn)-1(指數律)=e-1(gn=e)=e

這說明g-1的階也是有限的，故可設其階為m，于是有(g-1)m=e。從而由階定義的最小性知mn；其次，又由于

gm=((g-1)m)-1(指數律)=e-1((g-1)m=e)=e22第22頁，共73頁，2023年，2月20日，星期一離散數學

從而由階定義的最小性知nm；

于是(由的反對稱性)有n=m，即g和g-1的階相同。

(2)設g的階無窮，則g-1的階也必是無窮的。否則，設g-1的階是有限的，為m，從而(g-1)m=e。于是gm=((g-1)m)-1(指數律)

=e-1((g-1)m=e)

=e

這說明g的階也是有限的，故與g的階為無窮矛盾。因此當g的階是無窮時，g-1的階也是無窮的。由(1)和(2)知，g和g-1有相同的階。例13.在例10的群(X,*)中,元素i和-i互為逆元，i和-i的階均為4，相同。定理7.設(G,*)是群。gG

23第23頁，共73頁，2023年，2月20日，星期一離散數學

(1)若g的階有限，設其為k，從而gk=e。則

(1.1)mN,

gm＝ek|m；

(1.2)m,nN,

gm＝gn

k|m-n；

(2)若g的階無限，則

m,nN,

gm＝gn

m=n。[證].(1)(1.1)先證)：若gm＝e，則必有k|m。否則km，于是，由帶余除法，可設m=kq+r(0rk)，故可得r=m-kq，從而

gr＝gm-kq

＝gm+(-kq)

＝gm

*(gk)-q(指數律)

＝e*(e)-q(gm＝e,gk=e)

＝e*e

＝e故與g的階為k，具有最小性，矛盾24第24頁，共73頁，2023年，2月20日，星期一離散數學

次證):

若k|m，則m=kq。于是

gm＝gkq

＝(gk)q(指數律)

＝eq(gk=e)=e(1.2)gm＝gn

gm*g-n＝gn*g-n

gm+(-n)＝gn+(-n)(指數律)

gm-n＝e(g0=e)

k|m-n(根據(1.1))(2)若g的階無限，則

gm＝gn25第25頁，共73頁，2023年，2月20日，星期一離散數學

gm*g-n＝gn*g-n

gm+(-n)＝gn+(-n)(指數律)

gm-n＝e(g0=e)

m-n=0(g的階無限，只有g0=e)

m=n例14.在例10的群(X,*)中,

元素-1的階是2,所以

(-1)2＝1,(-1)4＝1,(-1)6＝1,…,(-1)2n＝1,…；元素i的階是4,所以

(i)4＝1,(i)8＝1,(i)12＝1,…,(i)4n＝1,…；元素-i的階是4,所以

(-i)4＝1,(-i)8

＝1,(-i)12＝1,…,(-i)4n＝1,…。26第26頁，共73頁，2023年，2月20日，星期一離散數學定理8.有限群中每個元素的階都是有限的。設(G,*)是有限群，|G|＝n，則G中每個元素的階n。[證].對任一元素gG，設其階為m，構造集合S={e,g

,g2,,gm-1}由定理5知g1,g2,…,gm這m個元素互不相同，因此|S|＝m，并且由群的封閉性知SG

，因此有|S||G|;所以mn。所以群G中每個元素的階

n。例15.在例8的Klein4-群(G,

o)中，么元e的階為1，其他元素a,b,c的階均為2，均小于群的階4；在例10的群(X,*)中,么元1的階為1，-1的階為2，i和-i的階均為4，均小于等于群的階4。定義6.循環(huán)群(cyclicgroup)設(G,*)是群。若存在著元素g0G，使得

(gG)(nI)(g=g0n)

27第27頁，共73頁，2023年，2月20日，星期一離散數學則稱(G,*)為循環(huán)群；同時稱g0是該循環(huán)群的生成元(generatingelement)。并且將(G,*)記作(g0)。例16.群(I,+)是循環(huán)群在群(I,+)中取1I，由于0＝10,n=1n,-n=(-1)n=(1-1)n=1-n，故I中的每個元素都可表示成1的整數次冪。由循環(huán)群的定義知(I,+)是循環(huán)群，1是該循環(huán)群的生成元。例17.群(Nm,+m)是循環(huán)群在群(Nm,+m)中，取[1]mNm，由于[0]m=([1]m)0,[i]m=([1]m)i,故Nm中的每個元素都可表示成[1]m

的整數次冪。由循環(huán)群的定義知(Nm,+m)是循環(huán)群,[1]m是該循環(huán)群的生成元。定理9.設(G,*)是循環(huán)群，|G|＝n。那么28第28頁，共73頁，2023年，2月20日，星期一離散數學

(1)g0是生成元

g0-1是生成元；

(2)g0是生成元

g0的階是n。[證].(1)g0是生成元

(gG)(kI)(g=g0k)

(gG)(kI)(g=(g0-1)-k)(指數律)

(gG)(mI)(g=(g0-1)m)(這里：m=-k)

g0-1是生成元；

(2)由于|G|＝n，所以(G,*)是有限群，根據定理8可知g0G的階有限，不妨設其為m，并且mn。先證)：構造集合

S={e,g0,g02,,g0m-1}

根據定理5可知|S|＝m，并且由群的封閉性知SG。29第29頁，共73頁，2023年，2月20日，星期一離散數學

又對任何gG，由于g0是生成元，故存在著整數k，使得g=g0k

。而g0的階是m，則有g0m=e；根據帶余除法，有k=qm+r(0rm)

從而g=g0k

=g0qm+r

=(g0m)q*g0r(指數律)=eq*g0r(因：g0m=e)

=e*g0r(因：eq=e)

=g0r

S(因：0rm)

故GS；從而S=G,于是m=|S|＝|G|＝n

即g0的階是n。30第30頁，共73頁，2023年，2月20日，星期一離散數學次證)：若g0的階是n，則構造集合

S={e,g0,g02,,g0n-1}

根據定理5可知|S|＝n，并且由群的封閉性知SG，因此由|G|＝n可知有S=G。從而，顯然，g0是生成元。定理10.設(G,*)是循環(huán)群，g0是生成元。

(1)若g0的階為m，則(G,*)與(Nm,+m)

同構；

(2)若g0的階為無窮，則(G,*)與(I,+)同構。[證].(1)由條件知

G={e,g0,g02,,g0m-1}

Nm={[0]m,[1]m,[2]m,,[m-1]m}

定義自然映射h:GNm，h(g0k)=[k]m

。由雙射31第31頁，共73頁，2023年，2月20日，星期一離散數學函數的定義知h是雙射函數。由于h(g0i*g0j)=h(g0(i+j)modm)=[(i+j)modm]m=[i]m+m[j]m

=h(g0i)+m

h(g0j)故h滿足同態(tài)公式。由同構的定義知h是從(G,*)到(Nm,+m)的同構函數，即(G,*)和(Nm,+m)同構。

(2)由于g0的階為無窮，故根據定理5的(2)有

e(=g00),g0,g02,,g0n,

①互不相同。由于根據定理6，g0和g0-1有相同的階，故與上同理可得32第32頁，共73頁，2023年，2月20日，星期一離散數學

g0-1,g0-2,,g0-n,

②互不相同。另外①與②中任何一對元素g0i和g0-j互不相同。否則有i0,j0(故有i+j0),使得g0i=g0-j

，于是

g0i+j=e這說明g0的階有限，與g0的階為無窮矛盾。于是有

G={,g0-n,,g0-2,g0-1,e,g0,g02,,g0n,

}

定義自然映射h:GI，h(g0k)=k。由于kI有原象g0kG

，使h(g0k)=k。故h是滿射的。由于若h(g0i)=h(g0j),即i=j，則有g0i=g0j

，即h是單射的。于是，由雙射函數的定義可知h是雙射函數。33第33頁，共73頁，2023年，2月20日，星期一離散數學由于有h(g0i*g0j)=h(g0i+j)=i+j

=h(g0i)+

h(g0j)故滿足同態(tài)公式。由同構的定義知h是從(G,*)到(I,+)的同構函數，即(G,*)和(I,+)同構。定理11.循環(huán)群一定是交換群。[證].仿§3定理2可證。34第34頁，共73頁，2023年，2月20日，星期一離散數學定義7.置換群(permutationgroup)設ASn,A,

是置換的合成運算。若(A,

)構成群，則稱(A,

)為一(n次)置換群。例18.設在三維空間有一矩形方框如圖1所示。四個頂點分別標記為1,2,3,4。我們用這些標記來表示矩形方框的運動。令e:不動(在平面內繞原點旋轉360)

a:繞橫軸旋轉180

(上下翻轉)b:繞縱軸旋轉180

(左右翻轉)

4OYX圖112335第35頁，共73頁，2023年，2月20日，星期一離散數學

c:在平面內繞原點旋轉180

這樣就將方框的運動用置換的方式表示出來了。令A={e,a,b,c}，

為置換的合成運算。下面用置換的合成來定義旋轉的復合運動。

a

b意味著先旋轉a再旋轉b。于是得到A上的置換合成表如下：例如

a

b===c

eabceeabcaaecbbbceaccbae表336第36頁，共73頁，2023年，2月20日，星期一離散數學

由表3知，這正是我們在前面例8所講的Klein4-群。由于置換的合成運算

就是關系的合成運算o，故

運算滿足結合律。這正好回答了前面例8所遺留的問題。由于Klein4-群(A,

)是由幾何形剛體在空間的運動所產生的，這正是我們把它稱為幾何群、運動群的原因。另外由表3明顯得知，這個置換群還是一個交換群。

注：在例18中可以看到剛體在空間的運動可以由4次置換來描述；但并不是任何4次置換都表示剛體在空間中的運動。如在例18中，置換就不代表任何剛體運動。

由于4個元素的置換應有4!=24個，而在例18中只取了其中的4個置換，沒有取完，所以AS4

。37第37頁，共73頁，2023年，2月20日，星期一離散數學定理12.n個元素的非空集合X上的所有n次置換構成的集合Sn，在置換的合成運算

下構成一置換群(Sn,

)。我們稱為n次對稱群(groupofsymmetry),簡記為Sn。[證].(1)封閉性：因為任意兩個n次置換Pi,Pj的合成Pi

Pj仍為一個n次置換，且結果唯一，即

Pi,Pj,

PiSnPjSnPi

PjSn；

(2)結合律：置換的合成運算

滿足結合律；

(3)有幺元；關于

運算的幺元是n次恒等置換I，即

ISn,

PSn,

I

P=P

I

=P(4)有逆元；由于任一n次置換P的逆置換P-1仍是一n次置換，即P-1Sn，故Sn中任一元素P都有逆元P-1，即PSn,

P-1Sn,

P

P-1=P-1

P

=I。38第38頁，共73頁，2023年，2月20日，星期一離散數學例19.

此例討論一個由所有置換構成的群。為了簡單起見，取X={1,2,3}，3個元素的置換有3！=6個。

S3={1,2,3,4,5,6}={e,,2,,,2}用輪換的形式寫出來是

1==(1)=e=3=2

2==(12)=

3==(13)=2

4==(23)=

5==(123)=

39第39頁，共73頁，2023年，2月20日，星期一離散數學

6==(132)=2

其運算表如下：由表4知

(1)

是S3上的二元運算,具有封閉性；

e

2

2e22e22e222e22e222e22e表440第40頁，共73頁，2023年，2月20日，星期一離散數學(2)置換的合成運算

滿足結合律；(3)e是關于

運算的幺元；(4)e,,2,

的逆元是其本身；,2互為逆元。由群的定義可知(S3,

)是群，因而是置換群。我們稱其為三次六階對稱群。由表4易知其不是交換群，因而它是最小的非交換群。(S3,

)實際上可看作是由兩個較小的置換群(H1,

)和(H2,

)的乘積得到的，這里：

H1={e,}，H2={e,,2}。這就引出了子群及Lagrange定理，還有群的構造等問題。

41第41頁，共73頁，2023年，2月20日，星期一離散數學定理13.(Cayley定理)任何n階有限群(G,*)都與一n次置換群同構。[證].設|G|＝n，G={a1(=e),a2,,an}。則令A={P1,P2,,Pn}，其中：

顯然P1,P2,,Pn是*運算的運算表中n個列置換，由本節(jié)定理4知，它們是n個互不相同的n次置換，即|A|＝n。

是置換的合成運算，則：

(一)(A,

)是一n次置換群

(1)封閉性：對任何Pi,PjA，對應著ai,ajG，由群(G,*)的封閉性知，存在著akG，使

ai*aj=ak

。而ak對應著列置換PkA

。于是對任何xG，都有42第42頁，共73頁，2023年，2月20日，星期一離散數學(Pi

Pj)(x)=Pj(Pi(x))=(x*ai)*aj=x*(ai*aj)=x*ak=Pk(x)

所以Pi

Pj=PkA。故合成運算

關于置換集合A封閉；

(2)結合律：置換的合成運算

滿足結合律；

(3)有幺元；P1A是關于

運算的幺元；因為，對任何PiA,都有對任何xG，都有

(P1

Pi)(x)=Pi(P1(x))=(x*a1)*ai=x*(a1*ai)=x*(e*ai)=x*ai=Pi(x)(Pi

P1)(x)=P1(Pi(x))=(x*ai)*a1=x*(ai*a1)=x*(ai*e)=x*ai=Pi(x)所以P1

Pi=Pi=Pi

P1

故P1A是關于

運算的幺元；

(4)有逆元；對任何PiA，對應著aiG，由群(G,*)有逆元知，存在著ajG，使

ai-1

=aj

。而aj對應著列置換43第43頁，共73頁，2023年，2月20日，星期一離散數學PjA

。于是對任何xG，都有

(Pi

Pj)(x)=Pj(Pi(x))=(x*ai)*aj=x*(ai*aj)=x*e=x*a1=P1(x)(Pj

Pi)(x)=Pi(Pj(x))=(x*aj)*ai=x*(aj*ai)=x*e=x*a1=P1(x)所以Pi

Pj=P1=Pj

Pi

故Pi-1=Pj

A是Pi關于

運算的逆元；由群的定義知(A,

)是群。因此(A,

)是n次置換群。

(二)群(G,*)與n次置換群(A,

)同構定義自然映射h:GA

對任何aiG，h(ai)=Pi(1)h是雙射函數：由定義顯然；(也可參見定理4)(2)h滿足同態(tài)公式：對任何ai,ajG，由群(G,*)的封閉性知，存在著akG，44第44頁，共73頁，2023年，2月20日，星期一離散數學使

ai*aj=ak

。于是對任何xG，都有

h(ai*aj)(x)=h(ak)(x)=Pk(x)=x*ak

=x*(ai*aj)=(x*ai)*aj=Pj(Pi(x))=(Pi

Pj)(x)=(h(ai)

h(aj))(x)所以h(ai*aj)=h(ai)

h(aj)；因此(G,*)與(A,

)同構。45第45頁，共73頁，2023年，2月20日，星期一離散數學定義8.子群(subgroup)若群(G,*)的子代數系統(S,*)也是群，則稱(S,*)是(G,*)的子群。注：驗證子群，除了驗證子代數系統的

(1)SG；

(2)S

；

(3)*運算關于S封閉；似乎還應該驗證

(4)有幺元(并與群G中的幺元重合)；

(5)有逆元(并與群G中的同一元的逆元重合)；而結合律則不須驗證，因為根據本章§1定理3可知，遺傳。

群(S,*)是群(G,*)的子群，我們簡記為SG；

由于群是一種代數系統，因此可以討論它的子代數系統。子46第46頁，共73頁，2023年，2月20日，星期一離散數學代數系統在群中的反映就是子群的概念。定理14.設(G,*)是群，SG且S

。那么

(S,*)是(G,*)的子群

(1)封閉性：ab(aSbSa*bS)(2)有逆元：a(aSa-1S)[證].先證)：由于(S,*)是(G,*)的子群，故(S,*)是群。因而

(1)有封閉性：ab(aSbSa*bS)這就證明了條件(*)(1)；

(2)有幺元：暫設其為es

；

(3)有逆元：即對任何aS，都存在著bS，使

b*a＝a*b=es

；

47第47頁，共73頁，2023年，2月20日，星期一離散數學下面我們來證兩點：

(a)es=e，即子群(S,*)的幺元es與大群(G,*)的幺元e重合；從而說明eS。

(b)b=a-1，即任一元素aS在子群(S,*)中的逆元b與其在大群(G,*)中的逆元a-1重合；從而說明a-1S，這就證明了條件(*)

(2)。

首先，由于es,eG，因此有

es*e=es

(因e是群(G,*)的幺元)

es*es=es

(因es是群(S,*)的幺元)故有es*es=es*e于是由群(G,*)的消去律可得

es=e；其次b=b*e

48第48頁，共73頁，2023年，2月20日，星期一離散數學

=b*(a*a-1)

=(b*a)*a-1(結合律)

=e*a-1

(b是a在子群(S,*)中的逆元且es=e)=a-1

次證)：只需驗證(S,*)是群即可

(1)封閉性：條件(*)(1)保證；

(2)結合律：遺傳；

(3)有幺元：由于S，故必至少有某一元素a0S，于是由條件(*)(2)有a0-1S，從而由條件(*)(1)有

e=a0*a0-1S；

(4)有逆元：條件(*)(2)保證；故(S,*)是群；所以(S,*)是(G,*)的子群。

49第49頁，共73頁，2023年，2月20日，星期一離散數學定理15.設(G,*)是群，SG且S

。那么

(S,*)是(G,*)的子群

(混合)封閉性：ab(aSbSa*b-1S)

(**)[證].我們證明：定理15條件(**)定理14條件(*)

先證)：

(1)有逆元：由于S，故必至少有某一元素a0S，于是重復有a0S，從而由條件(**)有

e=a0*a0-1S因此，對任何aS，由于eS已證，故由條件(**)有a-1=e*a-1S這樣，定理14條件(*)(2)得證；

(2)封閉性：對任何a,bS，由已證(1)有逆元有b-1S,50第50頁，共73頁，2023年，2月20日，星期一離散數學

從而由條件(**)有

a*b=a*(b-1)-1S

故定理14條件(*)(1)得證。次證)：對任何a,bS，根據定理14條件(*)(2)有逆元有b-1S,在根據定理14條件(*)(1)封閉性有

a*b-1S

故條件(**)(混合)封閉性得證。定理16.設(G,*)是有限群，|G|＝n，SG且S

。那么

(S,*)是(G,*)的子群封閉性：ab(aSbSa*bS)

(***)[證].先證)：由于(S,*)是(G,*)的子群，故(S,*)是群。因而具有封閉性：ab(aSbSa*bS)

這就證明了條件(***)。51第51頁，共73頁，2023年，2月20日，星期一離散數學

次證)：只需驗證(S,*)是群即可

(1)封閉性：條件(***)保證；

(2)結合律：遺傳；

(3)有幺元：由于S，故必至少有某一元素a0S，由SG知a0G；由|G|＝n，根據定理8知a0的階有限，設其為k，kn，則有a0k=e，于是由已證之封閉性有

e=a0kS；

(4)有逆元：對任何aS，由SG知aG；由|G|＝n，根據定理8知a的階有限，設其為m，mn，則有am=e；于是由已證之封閉性有am-1S，從而有

a*am-1＝am=e

am-1*a＝am=e；所以a-1=am-1S；

52第52頁，共73頁，2023年，2月20日，星期一離散數學

故(S,*)是群；所以(S,*)是(G,*)的子群。例20.平凡子群設(G,*)是群，則({e},*)和(G,*)是(G,*)的兩個子群。由于每個群都有這樣的子群，且這兩個子群對問題的研究價值不大。故稱這兩個子群是(G,*)的平凡子群。例21.循環(huán)群的子群是循環(huán)群。即若(G,*)是循環(huán)群且(S,*)是(G,*)的子群，則(S,*)是循環(huán)群。[證].由子群的定義知(S,*)是群。下證(S,*)是循環(huán)群。設g0是(G,*)的生成元，于是由SG知S中的每個元素都可表示成g0n，nI。設m是S諸元素中方次最小的正方冪。下證g0m是S的生成元。53第53頁，共73頁，2023年，2月20日，星期一離散數學

任取xS，則有kI使x=g0k

。根據帶余除法，有

k=qm+r(0rm)于是有g0r=g0k-qm=g0k*(g0m)-q(指數律)由于g0k=xS，并且由g0mS可知，(g0m)-qS，故由群(S,*)的封閉性可得g0rS

。而m是S中諸元素的最小正方冪，故有r=0。即有

x=g0k=g0qm=(g0m)q即g0m是(S,*)的生成元。于是由循環(huán)群的定義知(S,*)是循環(huán)群。例22.設(G,*)是群。令

S={c:cG(gG)(c*g=g*c)}則(S,*)是(G,*)的子群。我們稱此子群(S,*)是群(G,*)的中心。54第54頁，共73頁，2023年，2月20日，星期一離散數學[證].(1)SG：由S的定義顯然；

(2)S：有幺元eG，使得(gG)(e*g=g*e)，故有

eS；

(3)(混合)封閉性：ab(aSbSa*b-1S)

對于任何的a,bS，則有a,bG，且對任何gG，

a*g=g*a，b*g=g*b

對后一等式左右兩邊，前后同乘b-1G，我們得到

g*b-1=b-1*g即b-1*g=g*b-1

因此有a*b-1G，使得對任何gG

(a*b-1)*g=a*(b-1*g)

(結合律)

=a*(g*b-1)

(b-1*g=g*b-1)=(a*g)*b-1(結合律)=(g*a)*b-1(a*g=g*a)=g*(a*b-1)(結合律)55第55頁，共73頁，2023年，2月20日，星期一離散數學

因此a*b-1S；所以，根據定理15可知，(S,*)是(G,*)的子群。

56第56頁，共73頁，2023年，2月20日，星期一離散數學陪集和Lagrange定理陪集和Lagrange定理反映了群與子群之間的關系。從這種關系出發(fā)，可以比較容易地求得一些群的子群。目前在信息傳輸中使用的群碼就是由這些概念和定理所產生的。定義9.陪集(coset)

設(G,*)是群，(H,*)是(G,*)的子群。對于任何元素aG，

(1)由a所確定的H在G中的左陪集(leftcoset)定義為