1、第六章 代數(shù)系統(tǒng) 李豪杰 副教授 大連理工大學軟件學院 數(shù)字媒體技術系 Email: ,1/15,同余關系 定義： 給定，且E為S中的等價關系。 若 E關于有代換性質(zhì)：(x1)(x2)(y1)(y2)(x1，x2，y1，y2Sx1Ex2y1Ey2) (x1y1)E(x2y2)。 則 E為中的同余關系 商代數(shù) 及其上的同余關系E，且由E對S所產(chǎn)生同余類構成一個商集S/E，定義運算*， xE *yE = xyE，則稱為代數(shù)結構的商代數(shù)。 積代數(shù) 與是同類型的，可構造 = ,2/15,半群和獨異點的定義 定義：運算滿足結合律 性質(zhì)： 半群、獨異點的同態(tài)與同構 積半群 定義 性質(zhì) 群 定義 性質(zhì),3/

2、39,6.9 積半群 把積代數(shù)方法應用于特殊一類代數(shù)結構半群，便產(chǎn)生積半群。 定義6.9.1 給定兩個半群和。稱為和的積半群，其中ST為集合S與T的笛卡兒積，運算定義如下： = ，其中s1，s2S，t1，t2T 由于運算是經(jīng)和*定義的，易知，積半群是個半群。,4/39,積半群的性質(zhì),結合律 可交換性 幺元 零元 逆元,5/39,不難證明下列定理： 定理6.9.1 若半群和是可交換的，則也是可交換的。 定理6.9.2 給定半群和，且e1和e2分別是它們的幺元，則積半群含有幺元。 換言之，若和是獨異點，則是獨異點。,6/39,定理6.9.3 給定半群和，且1和2分別為它們的零元， 則積半群含有零元

3、。 定理6.9.4 給定半群和，且s的逆元s-1，tT的逆元t-1，則積半群中的逆元是。,7/39,6.10 群的基本定義與性質(zhì) 定義6.10.1 給定代數(shù)系統(tǒng)，若是獨異點且每個元素存在逆元， （或者 是可結合的， 關于存在幺元， G中每個元素關于是可逆的，） 則稱是群。 可見，群是獨異點的特例，或者說，群比獨異點有更強的條件。,8/39,例6.10.1 給定和，其中Z和Q分別是整數(shù)集合和有理數(shù)集合，+和是一般加法和乘法。 可知是群，0是幺元，每個元素iZ的逆元是-i；不是群，1是幺元，0無逆元。但便成為群。 定義6.10.2 給定群，若G是有限集，則稱是有限群。并且把G的基數(shù)稱為該有限群的階

4、數(shù)，若集合G是無窮的，則稱為無窮群。特別，若| G | =1，則稱為平凡群。,9/39,例6.10.2 例6.10.1中的是無限群， ，其中S = a，b，c，運算表如表6.8.1。 可以驗證是群，a為幺元，b和c互為逆元；又因| G | = 3，故是3階群。 由群的定義可知，群具有半群和獨異點的性質(zhì)，這里不再重復羅列了，而且群還有自己獨特的性質(zhì)，僅此討論如下:,10/39,、定理6.10.1 是群|G|1無零元。 證明：若0是的零元，因|G|1，則有eG和e 0并且對任意xG均有0 x=0e 即0無逆元，這與群的定義矛盾故群無零元 非平凡群不含零元 、定理6.10.2 是群中的惟一等冪元是幺

5、元。 證明：若不然，設還有aG,a e并且有 aa=a， 于是e= a-1 a= a-1 (a a) =(a-1 a) a= e a=a矛盾,11/39,、定理6.10.3 給定群，則有 (a)(b)(c)(a，b，cG(ab = acba = ca)b = c) 即群滿足可約律。 證明：因為是群，所以是可結合的，并且每個元素均有逆元，存在幺元e,對任何aG,其逆a-1 G,于是有 a b= a c a-1 (a b)= a-1 (a c) =(a-1 a) b= (a-1 a) c eb= e c b=c 同理可證b a=c a b=c 即群滿足可約律,12/39,、定理6.10.4 給定群

6、，則 (a)(b)(a，bG(!x)(xGax = b)(!y)(yGya = b) 或(a)(b)(a，bG(!x)(!y)(x，yG(ax = bya = b) 即群中方程解是惟一的。 證明：因為a (a-1 b) =( aa-1) b=eb=b 即有 x= a-1 b使得a x=b 下面來證x是唯一的， 令ax=b還有一解c,則 ac=b=eb=(aa-1) b =a(a-1b) 即c= (a-1b). 同理可證ya=b的解是唯一的 即y= b a-1.,13/39,定義6.10.3 設為群，aG，nZ，則a的n次冪為： e n=0 an= an-1 a n0 (a-1)m n0 這里應

7、該注意的是：群中元素定義了負整數(shù)次冪，這與半群和獨異點不同例如， 在中有 (2-1)3 e=0 =13 =1+3 1 +3 1=0 而在中，2-3= e=0 (2-1)3 =(-2)3 =(-2)+(-2)+(-2) =-6,14/39,定義6.10.4 給定群，若是可交換的，則稱是可交換群或是Abel群。 是Abel群。,15/39,、定理6.10.6 給定，則 為Abel群(a)(b)(a，bG (ab)2 = a2b2 證明：充分性，設(ab)2 = a2b2來證 是Abel群，即證可交換： (ab)2 = a2b2 (ab)(ab)=(aa)(bb) a(ba)b=a(ab)b ba=

8、 ab 即是可交換的,16/39,再證必要性：即若是Abel群，來證 (ab)2 = a2b2 (ab)2= (ab) (ab) = a(b a)b =a(a b)b =(aa) (bb) =a2 b2. 得證,17/39,定義6.10.5 給定群，且a，幺元eG，則a的階或周期為 使an=e的最小正整數(shù)， 并稱n為a的階記作| a | = n。 任何群幺元e的階都是1。,18/39,、定理6.10.7 給定群， aG，且| a | = k，p為整數(shù)，則ap=e iff p|k。 證明：必要性：若a的階為k，p為整數(shù)且ap=e, 來證p/k. 對p=qk+r, (0r k),于是 e=ap=a

9、qk+r=aqk ar=(ak)q ar =ear= ar，而k是a的階，即使ak=e的最小正整數(shù)，而0r k,所以r=0. 即p=qk，k能整除p. 再證充分性：因為p|k,必存在qZ使得 p=kq,于是ap=akq=(ak)q=eq=e. 問題得證 推論：若an = e且沒有n的因子d (1dn)使ad = e，則n為a的階。,19/39,例6.10.5 如果a6 = e且a e ,a2 e和a3 e，則6是a的階。,20/39,、定理6.10.8 給定群及aG，則a與a-1具有相同的階。 證明：設a的階是n，則an=e 于是(a-1)n= (an)-1=e-1=e, 若n是a-1的階，則

10、nn. 另一方面， an=(a-1)-1)n)=(a-1)n)-1 =e-1=e 故n n，于是有nn。,21/39,6.11 置換群和對稱群 定義6.11.1 令X是非空有限集合，從X到X的雙射函數(shù)，稱為集合X中的置換，并稱|X|為置換的階。 若X = x1，x2，xn，則n階置換表為 x1， x2， ， xn P = p(x1) p(x2) ， p(xn),22/39,并稱 p(x1) p(x2) ， ， p(xn) P-1= x1， x2， ， xn 為P的反置換 特別把置換 x1， x2， ， xn x1， x2， ， xn 為中的恒等置換或幺置換,23/39,此外，用PX表示集合X中

11、的所有置換的集合。 為了說明n個元素的集合可以有多少不同的置換，特給出如下定理： 定理6.11.1 若X=x1，x2，xn，則|PX| = n! 證明：每一種n階置換都是n個元素的一種全排列，所以n個元素的集合中不同的n階置換的總數(shù)等于n個元素的全排列的種類數(shù)目n!.故 |PX| = n!,24/39,定義6.11.2 給定集合X且pi，psPX，由X的元素先進行置換pi后繼之作置換ps所得到的置換，表為pips，稱pips是置換pi和ps的復合，是復合置換運算。 可以看出，若把置換看成一種特殊關系時，復合置換pips就是復合關系pi ps，常稱之右復合；又若把置換看成函數(shù)時，那么復合置換又可

12、表成如下的復合函數(shù)即所謂左復合： pips= ps pi， 其中表示函數(shù)的復合 于是，對于xX有： (pips)(x)=(ps pi)(x)= ps(pi(x),25/39,例6.11.1 令X=a，b，c， 則PX = p1，p2，p3，p4，p5，p6且 a b c a b c p1 = a b c p4 = a c b a b c a b c p2 = b a c p5 = b c a a b c a b c p3 = c b a p6 = c a b 可見p1是恒等置換(p2p5)(a)=? =(p5 p2)(a)= p5(p2(a)=c 對于各置換的反置換也不難看出，如p2的反置換p

13、2-1是： p2 p2-1 =p2-1 p2 = pe = p1,26/39,由定義6.11.1可知，置換即是雙射，亦即1-1函數(shù)，故PX中的元素, 即置換滿足下列四個性質(zhì): (1) (p1)(p2)(p1，p2PXp1p2PXp2p1PX) (2) (p1)(p2)( p3)(p1，p2，p3PX (p1p2)p3 = p1(p2p3) (3) (pe)(pePX(p)(pPXpep = ppe = p) (4) (p)(pPX (p-1)(p-1PXpp-1 = p-1p = pe) (1)表明PX對于是封閉的； (2)表明PX對于是可結合的； (3)表明PX 中有幺置換； (4)表明PX

14、中每個置換都有反置換。 因此，可知是一個群，并稱它為對稱群，習慣上記為。 若Q PX = S|X|，則稱由Q和構成的群為置換群。 對稱群：集合到自身的所有置換（雙射）構成的群。,27/39, 例6.11.2 例6.11.1中PX (現(xiàn)已寫S|X|即S3)與構成對稱群，其運算表如表6.11.1 表6.11.1 p1 p2 p3 p4 p5 p6 p1 p1 p2 p3 p4 p5 p6 p2 p2 p1 p5 p6 p3 p4 p3 p3 p6 p1 p5 p4 p2 p4 p4 p5 p6 p1 p2 p3 p5 p5 p4 p6 p3 p2 p1 p6 p6 p3 p4 p2 p1 p5,2

15、8/39,對稱群是獨立于集合X中各個元素，但卻依賴于集合X中的元素個數(shù)。這就是說，任何三個其它元素的集合都會生成“同樣”的置換，這就是為什么將對稱群寫成，即的理由。 此外，把集合X的基數(shù)稱為對稱群的次數(shù)。因此，是三次六階群，因為|S3|=3!=6。 一般地說來，由n個元素的集合而構成的所有n!個n階置換的集合Sn與復合置換運算構成群，它便是n次n!階對稱群。,29/39,應該注意，是對稱群一定是置換群，但反之不一定成立，即是置換群不一定是對稱群因為它并不要求一定要包括全部給定階的置換。例如，三次置換群和都不是對稱群， 其中p1，p2，p5，p6S3。 若說置換是個關系即有序?qū)希敲从芍脫Q和

16、構成置換群，它會確立怎樣的二元關系呢？下面就來回答這個問題。,30/39,定義6.11.3 令是一置換群 且Q S |X|。 稱R = 所誘導的X上的二元關系。 例6.11.3 設X = a，b，c，d， Q = pe，p1，p2，p3，其中 a b c d pe= a b c d 可證是X上的一個置換群，而由誘導的X上的二元關系可由圖6.11.1給出。,31/39,定理6.11.2 由置換群誘導的X上的二元關系是一等價關系。 R是等價關系，它必將X劃分成等價類。關于等價類數(shù)目的計算Burnside給出著名定理，這可參見組合學計數(shù)部分，這里就不講了。,32/39,現(xiàn)在，討論一下置換與群的運算表

17、的聯(lián)系。 眾所周知，群保持獨異點的性質(zhì)， 故在群的運算表中，任兩行或任兩列均不相同。不僅如此，可以證明每行或每列都是G中元素的置換。 定理6.11.3 在有限群中，每行或每列都是G中元素的置換。,33/39,現(xiàn)在，應用該定理來考察一、二、三和四階的群。 一階群僅有幺元，即。 二階群除幺元e外，還有一個元素，比如a，則有，其運算表如表6.11.2。由定理6.11.3可知，不可能再有其他運算表。在此預先指出，所有的二階群都與該群同構。 三階群，可令，其運算表如表6.11.3。由定理6.11.3知，不可能再有別的運算表。同樣，任何三階群都與它同構。,34/39,從運算表可以看出，所有二階群和三階群都是Abel群。事實上，四、五階群也是Abel群，但六階群未必都是Abel群。 表6.11. 2 表6.11. 3 e a e a b e e a e e a b a a e a a b e b b e a,35/39,上面講了由有限集合X到X的雙射即置換，以及置換群；下面不再限于X是有限集，換言之，它可以是個無限集。這時從集合X到X的雙射，稱之為一一變換或變換。如果令TX表示所有從集合X到X的變換的集合，則顯然有TX XX，并且TX類似PX所具有的四條性質(zhì)，具體如