09 代數(shù)系統(tǒng)2.ppt

1、1,第六章 代數(shù)結(jié)構(gòu),6.2 半群,2,定義6-2.2 一個代數(shù)系統(tǒng)，其中S是非空集合，*是S上的一個二元運(yùn)算，如果 (1) 運(yùn)算*是封閉的。 (2) 運(yùn)算*是可結(jié)合的，即對任意的 x,y,zS，滿足 (x*y)*z=x*(y*z) 則稱代數(shù)系統(tǒng)為半群。,定義6-2.1 一個代數(shù)系統(tǒng)，其中S是非空集合，*是S上的一個二元運(yùn)算，如果運(yùn)算*是封閉的，則稱代數(shù)系統(tǒng)廣群。,3,示 例,例1: 設(shè)集合Sk=x|xI xk, k0, 那么是一個半群，其中+是普通的加法運(yùn)算。 解: 因為運(yùn)算+在Sk上是封閉的，而且普通加法運(yùn)算是可結(jié)合的，所以，是一個半群。,4,例2: 設(shè)S=a,b,c, 在S上的一個二元運(yùn)

2、算定義如下表，驗證是一個半群。,解: 從表中可知運(yùn)算是封閉的，同時a,b,c 都是左幺元。所以，對于任意的a,b,cS, 都有 a(bc)=ac=c (ab)c= bc=c 因此, 是半群。,5,定理6-2.1 設(shè)是一個半群，BS且*在B上是封閉的，那么也是一個半群。通常稱是半群的子半群。 證明: 因為*在S上是可結(jié)合的，而BS且*在B上是封閉的，所以*在B上也是可結(jié)合的，因此，是一個半群。,6,示例,例: 設(shè)表示普通乘法運(yùn)算，那么、和都是的子半群。 解: 首先，運(yùn)算在R上是封閉的，而且是結(jié)合的，所以是一個半群。其次，運(yùn)算在0,1、0,1)和I上都是封閉的,且0,1R,0,1)R, IR。 因

3、此,由定理6-2.1可知、和都是的子半群。,7,證明 因為是半群。對于任意的bS,由*的封 閉性可知 b*bS, 記b2=b*b b2*b=b*b2 S,記b3=b2*b=b*b2 因為S是有限集，所以必定存在ji, 使得 bi=bj 令 p=j-i 便有 bi=bp*bi (P1) (1),定理6-2.2 設(shè)是一個半群，如果S是一個有限集，則必有aS,使得a*a=a。(等冪),8,由(1)式有 bq=bp*bq (qi) (2) 又p1,所以總可以找到k1,使得kpi 對于S中的元素bkp, 由(2)式可得 bkp=bp*bkp =bp*(bp*bkp) =b2p*bkp =b2p*(bp*

4、bkp)= =bkp*bkp 這就證明了在S中存在元素a=bkp,使得 a*a=a,9,定義6-2.3 含有幺元的半群稱為獨異點。 例如，代數(shù)系統(tǒng)是一個獨異點，因為，是一個半群，且0是R中關(guān)于運(yùn)算+的幺元。另外，代數(shù)系統(tǒng)，都是具有幺元1的半群，因此它們都是獨異點。,10,證明 設(shè)S中關(guān)于運(yùn)算*的幺元是e。因為對于任意的a,bS且ab時，總有 e*a=ab=e*b 和 a*e=ab=b*e 所以, 在*的運(yùn)算表中a行與b行不可能相同, a列與b列也不可能是相同的。,定理 6-2.3 設(shè)是一個獨異點，則在關(guān)于運(yùn)算*的運(yùn)算表中任何兩行或兩列都是不相同的。,11,例題 設(shè)I是整數(shù)集合, m是任意正整數(shù)

5、, Zm是由模m的同余類組成的同余類集, 在Zm上定義兩個二元運(yùn)算+m和m分別如下： 對于任意的i,jZ i+mj = (i+j) (mod m) i mj = (ij) (mod m) 試證明在這兩個二元運(yùn)算的運(yùn)算表中任何兩行或兩列都不相同。,12,證明 考察代數(shù)系統(tǒng)和。 (1)由運(yùn)算+m和m的定義，可知它們在Zm上都是封閉的。 (2)對于任意i,j,kZm (i+mj)+mk=i+m(j+mk) =(i+j+k) (mod m) (i mj) mk=im(jmk) =(i j k) (mod m) 即+m , m都是可結(jié)合的。 (3) 因為 0+mi= i+m0=i,所以, 0是中的幺元。

6、因為1mi=im1=i,所以1是中的幺元。 因此，代數(shù)系統(tǒng), 都是獨異點。由定理6-2.3可知，這兩個運(yùn)算的運(yùn)算表中任何兩行或兩列都不相同。,13,本例中, 如果給定m=5, 那么, +5和5的運(yùn)算表分別如下所示。,14,定理6-2.4 設(shè)是獨異點,對于任意a,bS,且a,b均有逆元, 則 a) (a-1)-1=a b) a*b有逆元, 且(a*b)-1=b-1*a-1,證明 a) 因為a-1是a的逆元，即 a*a-1=a-1*a=e 所以 (a-1)-1=a,b) 因為(a*b)*(b-1*a-1)=a*(b*b-1)*a-1 =a*e*a-1=a*a-1=e 同理可證 (b-1*a-1)*

7、(a*b)=e 所以(a*b)-1=b-1*a-1,15,作業(yè),P190 2，3，5，6,16,6-3 群與子群,定義6-3.1 設(shè)是一個代數(shù)系統(tǒng)，其中G是非空集合，*是G上一個二元運(yùn)算，如果 (1) 運(yùn)算*是封閉的。 (2) 運(yùn)算*是可結(jié)合的。 (3) 存在幺元e. (4) 對于每一個元素xG,存在著它的逆元x-1。 則稱是一個群。,每個元素均有逆元的獨異點就是群。,17,示例,例: 設(shè)R=0, 60,120,180,240,300表示在平面上幾何圖形繞形心順時針旋轉(zhuǎn)角度的六種可能情況。設(shè)是R上的二元運(yùn)算，對于R中任意兩個元素a和b, ab表示平面圖形連續(xù)旋轉(zhuǎn)a和b得到的總旋轉(zhuǎn)角度。并規(guī)定旋

8、轉(zhuǎn)360等于原來的狀態(tài)，就看作沒有經(jīng)過旋轉(zhuǎn)。驗證是一個群。 解: 由題意, R上二元運(yùn)算的運(yùn)算表如下:,18,運(yùn)算在R上是封閉的。 對于任意的a,b,cR, (a b) c表示將圖形依次旋轉(zhuǎn)a, b和c, 而a (b c)表示圖形依次旋轉(zhuǎn)b,c和a, 而總的旋轉(zhuǎn)角度都等于 a+b+c (mod 360), 因此, (a b) c = a (b c) 0是幺元。 60,120,180的逆元分別是300, 240, 180.因此, 是一個群。,19,定義6-3.2 設(shè)是一個群。如果G是有限集，那么稱為有限群，G中元素的個數(shù)通常稱為該有限群的階數(shù)，記為|G|；如果G是無限集，則稱為無限群。 例: 試

9、驗證代數(shù)系統(tǒng)是一個群，其中I是所有整數(shù)的集合, +是普通加法運(yùn)算。 解: 明顯地, 二元運(yùn)算+在I上是封閉的且是可結(jié)合的.幺元是0。對于任一元素aA, 它的逆元是-a。所以是一個群，且是一個無限群。,20,廣群僅僅是一個具有封閉二元運(yùn)算的非空集合； 半群是一個具有結(jié)合運(yùn)算的廣群； 獨異點是具有幺元的半群； 群是每個元素都有逆元的獨異點。,21,定理6-3.1 群中不可能有零元。 證明: 當(dāng)群的階為1時,它的唯一元素視作幺元。 設(shè)|G|1且群有零元。那么群中任何元素xG,都有x*=*x=e，所以，零元不存在逆元，這與是群相矛盾。,22,證明: 由于是一個群,故G中任意元素均有逆元，設(shè)a的逆元是a

10、-1, a*x=b a-1*(a*x)=a-1*b x=a-1*b,定理6-3.2 設(shè)是一個群,對于a,bG,必存在唯一的xG, 使得a*x=b.,23,證明: 設(shè)a*b=a*c, 且a的逆元是a-1, 則有 a-1*(a*b)=a-1*(a*c) (a-1*a)*b=(a-1*a)*c e*b=e*c b=c 當(dāng)b*a=c*a時, 可同樣證得b=c.,定理6-3.3 設(shè)是一個群，對于任意的a,b,cG,如果有a*b=a*c或者b*a=c*a,則必有b=c(消去律)。,24,例: 對于集合Sa,b,c,d，將a映射到b，b映射到d，c映射到a，d映射到c，是從S到S上的一一映射, 這個置換可以

11、表示為,定義6-3.3 設(shè)S是一個非空集合, 從集合S到S的一個雙射稱為S的一個置換。,25,定理6-3.4 群的運(yùn)算表中的每一行或每一列都是G的元素的一個置換。,26,定義6-3.4 代數(shù)系統(tǒng)中，如果存在aG,有a*a=a,則稱a為等冪元。 定理6-3.5 代數(shù)系統(tǒng)中，除幺元e外，不可能有任何別的等冪元。,證明: 因為e*e=e, 所以e是等冪元。 現(xiàn)設(shè) aA，ae且a*a=a 則有 a=e*a=(a-1*a)*a=a-1*(a*a) =a-1*a=e 與假設(shè)ae相矛盾。,27,定義6-3.5 設(shè)是一個群, S是G的非空子集,如果也構(gòu)成群, 則稱是的一個子群。 定理6-3.6 設(shè)是一個群,是

12、的一個子群, 那么, 中的幺元e必定也是中的幺元。 證明: 設(shè)中的幺元為e1,對于任一xSG，必有e1*x=x=e*x，根據(jù)消去律，有e1=e. 定義6-3.6 設(shè)是一個群，是的子群，如果 S=e,，或者S=G，則稱為的平凡子群。,28,證明: (1) 對于任意的x,yIE,不妨設(shè)x=2n1, y=2n2, 其中n1,n2I, 則x+y=2n1+2n2=2(n1+n2), 而n1+n2I, 所以x+yIE, 即+在IE 上是封閉。 (2) 運(yùn)算+在IE上保持可結(jié)合性。 (3) 中的幺元0也在IE中。 (4) 對于任意的xIE, 必有n使得x=2n, 而-x=-2n=2(-n), -nI, 所以

13、-xIE, 而x+(-x)=0, 所以對于任意的xIE其逆元為-x，因此是 的一個子群。,例: 是一個群, 設(shè)IE=x|x=2n,nI, 證明是的一個子群。,29,證明 設(shè)b是B的任一個元素。若*在B上封閉，則元素b2=b*b,b3=b2*b,都在B中。由于B是有限集，所以必存在正整數(shù)i和j, 不妨假設(shè)ji, 使得 bi=bj 即 bi=bi*bj-i. 這就說明bj-i是中的幺元，該幺元也在子集B中。 如果j-i1,那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，且bj-i-1B;如果j-i=1,那么由bi=bi*b可知b就是幺元，而幺元是以自身為逆元的。 因此，是的一個子群。,定理6-3.7 設(shè)是一個群，B是G的非空子集，如果B是一個有限集，那么，只要運(yùn)算*在B上封閉，必定是的子群。,30,證明 (1) G中的幺元e也是S中的幺元。 對任意aSG，由已知條件可得e=aa-1S且 ae=ea=a，即e也是S中的幺元。 (2) S中的每一元素都有逆元。 對任一aS，因為eS，所以ea-1S即a-1S。 (3) 在S上是封閉的。 對任意的a,bS，由上可知b-1S 而 b=