離散數(shù)學第五章第二節(jié)

1、1,第5-2講 半群與群,1. 半群2. 獨異點3. 群的定義4. 群的性質(zhì)5. 子群6. 子群判定定理7. 第5-2講 作業(yè),,,,,2,1、半群（1）,半群是一種代數(shù)系統(tǒng)。在形式語言、自動機中有應(yīng)用。,定義2 如果代數(shù)系統(tǒng)為廣群，二元運算*可結(jié)合，則稱代數(shù)系統(tǒng)為半群。,定義1 一個代數(shù)系統(tǒng)，S是非空集合，*是S上的二元運算,如果運算*是封閉的,則稱代數(shù)系統(tǒng)為廣群。,例1 設(shè)S={a,b,c},定義S上的運算*如右表

2、：驗證是否為半群。,代數(shù)系統(tǒng)和是半群嗎？這里I+為正整數(shù)集，R為實數(shù)集，-和/是通常數(shù)的減法和除法。,解：從運算可看出運算*是封閉的。 另外a、b、c皆為左幺元，所以，對任意x,y,z?S，均有x*(y*z)=y*z=(x*y)*z所以*運算是可結(jié)合的。從而是半群。,,,,,3,1、半群（2）,定理2 設(shè)是半群，如果S為有限集，則存在a?S，使得a*a=a。,定理1 設(shè)是半群，集合B?S，且*在B是封閉的，則也是半群，稱之為的子

3、半群。,證：因是半群，運算封閉且可結(jié)合，所以可定義半群中任意元素b的冪： b2=b*b, b3=b2*b=b*b*b, ...。 因S為有限集，在冪的序列中，必存在j>i,使 bi=bj。 令p=j-i?1,則bi=bp*bi，此式兩邊不斷右*b,可使 bkp =bp*bkp（k?1為正整數(shù)） 這樣bkp=bp*bkp =bp*(bp*bkp)=b2p*bkp

4、 =b2p*(bp*bkp)=…=bkp*bkp這說明S中存在等冪元素a=bkp，a*a=a。,,,,,4,1、半群（3）,可取定理2證明中的b=2,i=5,j=9。p=j-i=9-5=4。那么2i=2p*2i,即25=24*25,三次右*2得：28=24*28(p=4,k=2)即22p=2p*22p=2p*(2p*22p)=22p*22p,令a=22p=28=1,a*a=a。,例如：設(shè)N5={0,1,2,3

5、,4}，運算*定義如下表，則是半群。,從運算表可以看出：0*0=0，0是等冪元；1*1=1，1是等冪元；21=2 26=2*2=422=2*2=4 27=4*2=3 23=4*2=3 28=3*2=124=3*2=1 29=1*2=225=1*2=2 210=2*2=4,,,,,5,2、獨異點(1),例如，，，都是半群，其中+是普通加法。 Z+、N、Q分別是正整數(shù)集、自然數(shù)集和有理數(shù)集。這些半群中

6、除外都是獨異點,定義3 含有幺元的半群叫獨異點。也稱為含幺半群。,定理3 設(shè)是獨異點，則運算*的運算表中任何兩行或兩列都不相同。,證明：設(shè)S中的幺元為e。那么對任意a,b?S且a?b時,有 e*a=a?b=e*b; a*e=a?b=b*e。前式說明e所在行的任意兩個元素都是不同的，從而任意兩列至少有一個元素是不同的，從而任意兩行不同(參考右圖)。 后式說明e所在列的任意兩個元素都不相同，從而任意兩行是不同的。,

7、,,,,6,2、獨異點(2),例2 設(shè)I為整數(shù)集合，Z6是同余模6的等價類構(gòu)成的集合(參看P132)，即Z6={[0],[1],[2],[3],[4],[5]}。在Z6上定義運算?6如下表： 對任意[i],[j]?Z6，[i]?6[j]=[(i?j)(mod6)]。驗證是獨異點。,解:(1)由定義運算?6顯然是封閉的。(2)可驗證運算?6是可結(jié)合的：([i]?6[j])?6[k]=[i]?6([j]?6[k])=[(i?j

8、?k)(mod6)]。例如:([4]?6[5])?6[3]=[2]?6[3]=[0] [4]?6([5]?6[3])=[4]?6[3]=[0] [(4?5?3)(mod6)]=[60(mod6)]=[0](3)[1]是幺元。因為[1]?6[i]=[i]?6[1]= [(1?i)(mod6)]= [i(mod6)]=[i]。,,,,,7,2、獨異點(3),定理4 設(shè)是獨異點，且對任意a,b?S均有逆元。則(1) (

9、a-1)-1=a; (2)(a*b)-1=b-1*a-1。,證明： (1) 可按定義驗證a-1的逆元是a。因為 a-1*a=e=a*a-1。從而(1)式成立。 (2)此式表達的意思是“a*b的逆元是b-1*a-1”，與(1)類似，可按逆元定義直接驗證： (a*b)*(b-1*a-1)= a*(b*b-1)*a-1= a*e*a-1= a*a-1=e同理可證 (b-1*a-1)*(a*b)=e 所以原式成立。,,

10、,,,8,3、群的定義（1）,定義4 設(shè)是代數(shù)系統(tǒng),G非空,*是G上的二元運算，如果(1)運算*在G上封閉;(2)運算*可結(jié)合;(3)存在幺元e;(4)對每個x?G,存在逆元x-1。則稱為群。,例如,、、都是群,這里,+和*表示數(shù)的加法和乘法,I表示整數(shù)集, Q+表示正有理數(shù)集、R表示實數(shù)集。 的幺元為1,x-1=-x。的幺元為1,x-1=1/x。的幺元為1,x-1=1/x。 、不是群,N中除幺元0外,其余元素無逆元。R中0無

11、逆元。,半群、獨異點、群的關(guān)系示意圖,,,,,9,3、群的定義（2）,例3 設(shè)G={a,b,c,d}, G上的二元運算*由下表給出，證明是群。,另外， 群的運算*是可交換的；并且在a，b，c三者中，任何兩個元素運算的結(jié)果都等于另一個元素。該群特稱為Klein四元群，簡稱四元群。,由運算表可以看出： 運算*是封閉的； 容易驗證運算*可結(jié)合； e為幺元； G中任何元素的逆元就是它自己。所以是群。,,,,,10,3、群的定義（3）,

12、定義5 設(shè)是群,如果（1）若G是有限集，則稱是有限群， G中元素的個數(shù)|G|稱為群G的階。若G是無限集，則稱為無限群。（2）只含幺元的群稱為平凡群。（3）若二元運算*是可交換的，則稱群為交換群或阿貝爾(Abel)群。（4）設(shè)a?G，使得等式ak=e成立的最小正整數(shù)k稱為群中元素a的階，記作|a|=k，這時也稱a為k階元。若不存在這樣的正整數(shù)k，則稱a為無限階元。,例如四階群中:a1=a , a2=a*a=b，a3=a2*a=

13、b*a=c， a4=a3*a=c*a=e，a5=a4*a=e*a=a,...所以，a是4階元。顯然,b是2階元，c也是4階元。,下面引人群論中常用的概念或術(shù)語：,,,,,11,3、群的定義（4）,定義6 設(shè)是群，a?G，n?I(整數(shù)集)，則a的n次冪：,與半群和獨異點不同的是：群中元素可以定義負整數(shù)次冪。,,,,,12,4、群的性質(zhì)（1）,定理5 設(shè)為群,則(1) 群無零元。(2) 對任意a,b?G,存在唯一的x?G,使得a*x

14、=b。(3) 對任意a,b,c?G,如果a*b=a*c或b*a=c*a,則b=c。(4) 群中幺元外，無等冪元。,證：(1) 若G中只有唯一的元素，則該元素可視為幺元。若G中的元素多于一個，假設(shè)群G有零元?，可以證明零元無逆元。事實上，對任意x?G，x*?=?*x=??e(幺元)，這說明G中任何x都不是?的逆元，即?無逆元。與是群相悖。所以群無零元。(2) 記a的逆元為a-1，如果a*x=b，則a-1*(a*x)=a-1*b，由結(jié)

15、合律得：(a-1*a)*x=a-1*b，即e*x=a-1*b,亦即x=a-1*b?G?？沈炞C該x滿足方程a*x=b。 下面證唯一性：設(shè)x’?G,且a*x’=b。則a-1*(a*x’)=a-1*b,進而可得(a-1*a)*x’=a-1*b，即e*x’=a-1*b,亦即x’=a-1*b=x。,,,,,13,4、群的性質(zhì)（2）,（接證定理5） 設(shè)為群,則(3) 對任意a,b,c?G,如果a*b=a*c或b*a=c*a,則b=c。(4)

16、 群中幺元外，無等冪元。,證：(3) 若a*b=a*c，e為幺元，則 a-1*(a*b)=a-1*(a*c) (a-1*a)*b=(a-1*a)*c即 e*b=e*c亦即 b=c同理可證，當b*a=c*a,有b=c。(4) （用反證法）設(shè)G中有等冪元a?e，a*a=a，那么 a=e*a=(a-1*a)*a==a-1*(a*a)=a-1*a=e

17、與假設(shè)a?e矛盾！,,,,,14,4、群的性質(zhì)（3）,定義7 設(shè)集合S非空，雙射P：S?S稱為S的一個置換。 例如，設(shè)S={1,2,3}，令雙射P：S?S，P(1)=2, P(2)=1, P(3)=3。P是S的一個置換，可簡記為：,S的置換共有3！=6個，列如下：,,,,,15,4、群的性質(zhì)（4）,定理6 群的運算表(簡稱群表)中的每行或每列都是G的一個置換。,證：(1) 由于幺元的存在，所以群表中無相同的行和列。 (2) 任一

18、行或任一列中，G的元素不會重復出現(xiàn)。 假設(shè)任意x?G,對應(yīng)于x所在的那一行中有兩個元素為c。則應(yīng)有x*y=c=x*z(如右下圖所示)。按群的消去律(定理5)y=z,但這是不可能的！說明一行中不能有兩個相同的元素。對列也是一樣。,(3) G中每個元素必出現(xiàn)在群表的任一行和任一列。 設(shè)任意x,w?G,那么x-1*w是G中的元素，它應(yīng)出現(xiàn)在群表的頂行；另一方面，x*(x-1*w)=(x*x-1)*w=w，所以w必出現(xiàn)在x所在的行(如

19、右圖所示)。對列也是一樣。 綜上所述，定理6得證,,,,,16,5、子群（1）,定義8 設(shè)是群，S?G，S非空。如果也是群，則稱之為的子群。 和是群的兩個平凡子群。,定理8 設(shè)是群，是的子群，則二者有相同的幺元。,證：設(shè)的幺元為e，的幺元為e1。對任意x?S,必有x?G，那么，e1*x=x=e*x，由消去律，e1=e。,,,,,17,5、子群（2）,例4 是群。令I(lǐng)E={x|x=2n,n?I},證明是群的子群。,證： 本題的實

20、質(zhì)是要證明是群。按群的定義證明如下： (1)證+運算在IE上封閉。任取x,y?IE，可設(shè)x=2n1, y=2n2，其中n1,n2?I。那么x+y=2(n1+n2)?IE,故運算封閉。 (2)因+運算在I上可結(jié)合，而+運算在IE上封閉，所以，+運算在IE上可結(jié)合。 (3)因的幺元0在IE中，所以有幺元0。 (4)對任意2n?IE,有2n+(-2n)=2n+2(-n)=0。這說明IE中的任意元素有逆元。 所以是群，又因I

21、E?I,所以是群的子群。,,,,,18,6、子群判定定理（1）,定理9 設(shè)是群，如果運算*在G的非空有限子集B上封閉，則是的子群。,證：已設(shè)運算*在B上封閉，故結(jié)合性在B中保持下來。 其次證B有幺元。設(shè)任意b?B，由封閉性，b2,b3,…都在B中。因B有限，必存在正整數(shù)i和j,i1,則 e=bj-i=b*bj-i-1=bj-i-1*b,即b的逆元是bj-i-1。如果j-i=1,則j=1+i,于是bi=bj=b1+i=b*bi

22、=bi*b,即b是幺元。這時，b以自身為逆元。 由上述，是的子群。,參閱,,,,,19,6、子群判定定理（2）,定理10 設(shè)是群，S?G且非空，如果對任意a,b?S 有a*b-1?S，則是的子群。,證：(1)設(shè)e是G的幺元。任取a?S,因a*a-1?S,所以e?S。(2)任取a?S，因e?S，那么e*a-1?S,即a-1?S。(3)對任意a,b?S,由(2),b-1?S,所以a*b=a*(b-1)-1?S,故運算*在B上封閉。