代數(shù)系統(tǒng)基礎

1、第三篇 代數(shù)系統(tǒng)1近世代數(shù)這部分內容屬于近世代數(shù)的范疇，近世代數(shù)是研究具有運算的集合，它第一次揭示了數(shù)學系統(tǒng)的多變性與豐富性。代數(shù)結構理論可用于計算機算法的復雜性分析，研究抽象數(shù)據(jù)結構的性質及操作，同時也是程序設計語言的理論基礎。2本篇內容我們將介紹代數(shù)系統(tǒng)的最基本概念和最基本理論，以及幾類常用的代數(shù)系統(tǒng)，它們是：半群，群，環(huán)，域，格和布爾代數(shù)。本課程在第五、六、七章中介紹代數(shù)系統(tǒng)的內容。3第五章 代數(shù)系統(tǒng)基礎代數(shù)系統(tǒng)是用代數(shù)運算構造數(shù)學模型的方法。這是一種抽象的方法，故又稱抽象代數(shù)，又由于此種方法是在集合上通過構造手段生成，也可稱為代數(shù)系統(tǒng)。45.1代數(shù)系統(tǒng)的一般概念一個代數(shù)系統(tǒng)需要滿足三個

2、條件： （1）一個非空集合S； （2）一些建立在集合S上的運算； （3）這些運算在S上是封閉的； 5封閉的含義其運算的結果都是在原來的集合中，我們稱具有這種特征的運算是封閉的。如：數(shù)集上加法、絕對值、相反數(shù)運算；冪集上交、并運算等。不封閉運算的例子也有很多，如設N是自然數(shù)集，Z是整數(shù)集，普通的減法定義為NN到Z的運算，是不封閉的。6運算符通常用等，等表示二元運算，稱為運算符。若f：sss是集合S上的二元運算，對任意x,y,如果x與y運算的結果是z, 即f (x，y) = z ,可利用運算簡記為xy=z。類似于二元運算，也可以使用運算符來表示n元運算。如 f（a1，a2，an）= b 可簡記為

3、（a1，a2，an）= b 7 n=1時 （a1）=b是一元運算； n=2時 （a1，a2）=b是二元運算； n=3時 （a1，a2，a3）=b是三元運算； 這些相當于前綴表示法，但對于二元運算用得較多的還是a1 a2 = b，以下所涉及的n元運算主要是一元運算和二元運算。8代數(shù)系統(tǒng)的例子（1）求一個數(shù)的倒數(shù)是非零實數(shù)集R*上的一元運算。（2）非零實數(shù)集R*上的乘法和除法都是R*上的二元運算，而加法和減法不是。（3）S是一非空集合，SS是S到S上的所有函數(shù)的集合，則復合運算是SS上的二元運算。（4）空間直角坐標系中求點（x，y，z）的坐標在 x 軸上的投影，可以看作實數(shù)集R上的三元運算：f (

4、x，y，z) = x，因為參加運算的是有序的3個實數(shù)，而結果也是實數(shù)。9運算規(guī)律考察代數(shù)系統(tǒng)Z，+。很明顯，在這個代數(shù)系統(tǒng)中，關于加法運算，具有以下二個運算規(guī)律，即對于任意的x，有 (1) x+y=y+x (交換律) (2) (x+y)+z=x+(y+z) （結合律）又如，設S是集合，P（S）是S的冪集，則代數(shù)系統(tǒng)P（S），U和P（S），中的、都適合交換律，結合律，即他們與Z，+有類似的運算性質。這些就是代數(shù)系統(tǒng)研究的一部分內容。10同類型的代數(shù)系統(tǒng)定義：如果兩個代數(shù)系統(tǒng)有相同個數(shù)的運算符，每個對應的運算符有相同的元數(shù)，則稱這兩個代數(shù)系統(tǒng)有相同的類型。例：整數(shù)集上加法與實數(shù)集上乘法； N階矩陣

5、集上加法、乘法運算。11子代數(shù)定義：兩個代數(shù)系統(tǒng)（S，），（S，+），若滿足下列條件： （1）S是S的子集 （2） 則稱（S，+） 是（S，）的子代數(shù)或子系統(tǒng)。例：偶數(shù)集上加法是整數(shù)集上加法的子代數(shù)。125.2代數(shù)系統(tǒng)常見的性質對給定的集合，我們可以任意地在這個集合上規(guī)定運算使它成為代數(shù)系統(tǒng)。但我們所研究的是其運算有某些性質的代數(shù)系統(tǒng)。在前面考察幾個具體的代數(shù)系統(tǒng)時，已經涉及到我們所熟悉的運算的某些性質。這一節(jié)，主要討論一般二元運算的一些性質。13代數(shù)系統(tǒng)（S，*）上性質1.結合律2.交換律例：常用的代數(shù)系統(tǒng)：數(shù)集上加法、乘法，冪集上交、并運算。143.分配律以上是第一分配律、第二分配律。例：

6、數(shù)集上乘法對加法滿足分配律，但加法對乘法不滿足。冪集上交對并、并對交滿足分配律。15單位元定義：若存在一個元素eS,對任一x S，均有x*e=x，則稱e為右單位元，記1r；若e*x=x，則稱e為左單位元,記1l。常用1來表示單位元。注：1只是一個符號，用來表示S中單位元素。16單位元定理定理1：若左單位元、右單位元都存在，則兩者相等。定理2：若單位元存在，則必唯一。17證明定理1：若1r、1l存在， 1l*1r=1r=1l。定理2：設有兩個單位元e1、e2，任一xS，e1*x=x，取x=e2，有e1*e2=e2，又e2也是單位元， e1*e2=e1。因此e1=e2，單位元是唯一的。18零元素定

7、義：若存在一個元素aS,對任一xS，均有x*a=a，則稱a為右零元，記0r；若a*x=a，則稱a為左零元,記0l。常用0來表示零元素。注：0只是一個符號，表示S中零元素。定理：若左零元、右零元都存在，則兩者相等。定理：若零元存在，則必唯一。 19例子數(shù)集上加法，單位元1=0；數(shù)集上乘法，單位元1=1。集合A的冪集上交運算。單位元1是A，零元0是空集；并運算的單位元是空集，零元是A。正整數(shù)集I上的運算min,max。其中min為取最小值運算，max是取最大值運算。(I,min)上零元是1，單位元不存在；(I,max)上零元不存在，單位元是1；20逆元素： 設（S，*）上單位元存在定義：若對S內元

8、素a，存在a-1rS,有 a* a-1r=1，則稱a-1r為a的右逆元素； 若存在a-1lS,有a-1l*a =1，則稱a-1l為a的左逆元素。21定理定理1：一個代數(shù)系統(tǒng)（S，*）,如果其運算滿足結合律，則左、右逆元相等。定理2：一個代數(shù)系統(tǒng)（S，*）,如果運算滿足結合律且逆元存在，則S內每一個元素的逆元是唯一的。22例子整數(shù)集上加法。 單位元是0，a的逆元是-a；整數(shù)集上乘法，單位元是1，只有1、-1有逆元；實數(shù)集上乘法，0沒有逆元。自然數(shù)集上加法。 單位元是0，0的逆元是0，其他元素沒有逆元。在非零的實數(shù)集R*上定義運算，使對于任意的元素a,bR*，有ab=a。那么，R*的任何元素都是運

9、算的左零元，而R*中運算沒有右零元，因此沒有零元。23練習題題1 設Z是整數(shù)集， ，分別是Z上的二元運算，其定義為，對任意的a，aabab，aabab，問上的運算，分別是否可交換？24解 因為ababa= baa a ，對Z中任意元素a，b成立，所以運算是可以交換的。 又因為對Z中的數(shù)0，1，01 = 010+1= 1，10 = 101+0 = 1，所以，0110，從而運算是不可交換的25練習題2設是有理數(shù)集合，分別是上的二元運算，其定義為，對于任意的a，b，aa，a*ba-2b ，證明運算是可結合的，并說明運算不滿足結合律。26證明因為對任意的a，b，cQ， （abc=ac=a;a (bc)

10、=a b=a，所以（ab）c=a(bc)，即得運算是可以結合的。 又因為對Q中的元素0，1 （00）1=01=0-2=2 0（01）=0（-2）=0-2（-2）=4 所以（00）10（01），從而運算不滿足結合律。27練習題3設A=a,b,c,d，運算表如下。問題：是否滿足交換律，是否有單位元，是否有零元，哪些元素有逆元？28運算表解(2)(1)29解（1）運算可交換，沒有零元，a是單位元，a-1=a,c-1=c,b-1=d,d-1=b（2）運算不可交換，a是左零元，b是單位元，b-1=b；由于c*d=b，所以c是d的右逆元，d是c的左逆元。30運算表若S, 是代數(shù)系統(tǒng)，其中是有限非空集合S上

11、的二元運算，那么該運算的部分性質可以從運算表直接看出，例如1.當且僅當運算表中每個元素都屬于S，運算具有封閉性。2.當且僅當運算表關于主對角線對稱時，運算具有可交換性。3.S關于運算有單位元e，當且僅當表頭e所在的列與左邊一列相同且表左一列e所在的行與表頭一行相同。314.S關于運算有零元0，當且僅當表頭0所在的列和表中左邊一列0所在的行都是0。5.設S關于運算有單位元，當且僅當位于a所在的行與b所在的列交叉點上的元素以及b所在的行與a所在的列交叉點上的元素都是單位元時，a與b互為逆元。6.代數(shù)系統(tǒng)S，中一個元素是否有左逆元或右逆元也可從運算表中觀察出來，但運算是否滿足結合律在運算表上一般不易

12、直接觀察出來。325.3同構與同態(tài)代數(shù)系統(tǒng)的同構與同態(tài)就是在兩個代數(shù)系統(tǒng)間存在著一種特殊的映射-保持運算的映射，它是研究兩個代數(shù)系統(tǒng)間強有力的工具。后面會分析，同構不僅使兩個代數(shù)系統(tǒng)具有相同的基數(shù)，而且使運算保持相同的性質。33為什么需要研究代數(shù)系統(tǒng)間的關系？在研究代數(shù)系統(tǒng)的過程中，所關心的常常是代數(shù)系統(tǒng)中運算所滿足的性質，而不關心具體的運算，而對于遵循相同運算規(guī)律的系統(tǒng)，只需研究其中一個就可以了解其他的系統(tǒng)。34同構與同態(tài)定義：設（X，）、（Y，*）是同類型的代數(shù)系統(tǒng)，均是二元運算，若存在一個函數(shù)：g：XY，使得若x1,x2X，則有 g(x1x2)=g(x1)*g(x2)則稱g是從（X，）到

13、（Y，*）的同態(tài)函數(shù)。35特別的若g是一一對應，則稱g是（X，）到（Y，*）的同構函數(shù)，記（X， ）（Y，*）；若g是單射，則稱g是（X，）到（Y，*）的單同態(tài)；若g是滿射，則稱g是（X，）到（Y，*）的滿同態(tài)。一個系統(tǒng)與自身的同態(tài)稱為自同態(tài)；一個系統(tǒng)與自身的同構稱為自同構。36例子例1. 定義g:ZZm,g(k)=k（modm）=k，則V1與V2同態(tài)，易知g是滿同態(tài)。37例子例2.f：QR， 定義f(x)=2x,則f是單同態(tài)。例3.教材65頁例5.15，例5.16，例5.17 構造g(a)=a-3，證明g 是一一對應，且g(ab)=g(a)*g(b)38例子例4.(R,+)與(R+，)是同構

14、的； (R+，)與(R,+)是滿同態(tài)的。 （1）設f:RR+,f(x)=ex；驗證f是單射，滿射，滿足同態(tài)方程。 （2）定義f:R+R, f(x)=lnx,同理可以驗證函數(shù)是滿射，滿足同態(tài)方程。39設代數(shù)系統(tǒng)（X，）與（Y,*）同構，g是同構函數(shù)，則兩個同構的代數(shù)系統(tǒng)對運算保持許多相同的性質。 40性質結合律交換律單位元存在性，且g(1x)=1Y零元存在性，且g(0 x)=0Y逆元 若（X，）對每個x均有逆元x-1,則（Y，*）對每個y也有逆元y-1，且g(x-1)=g(y-1)分配律41定理定理：設G是一些只有一個二元運算的代數(shù)系統(tǒng)的非空集合，則G中代數(shù)系統(tǒng)間的同構關系是等價關系。證明：設（

15、X,）（Y,*）（Z,+）,g、f是同構映射。 （1） （X,）（X,）,s(x)=x；自反的 （2） （X,）（Y,* ）；對稱的 (3) （X,）（ Y,*）, （ Y,*）（ Z,+）傳遞的 42有 43同構是代數(shù)系統(tǒng)間的等價關系，所有同構的代數(shù)系統(tǒng)，只需研究一個即可。設代數(shù)系統(tǒng)（X，）與（Y,*）滿同態(tài)，代數(shù)系統(tǒng)的性質是單向保持，即（X， ）的性質（Y,*）具有，反之不一定。44自然同態(tài)同余關系：整數(shù)集上除以m后余數(shù)相同的關系。例R=(x,y)|x-y能被3整除，以3為模的同余關系是等價關系，將Z分為3個劃分塊0、1、2，這是三個等價類： 0=-3,-6,0,3,6,9 1=-5,-2

16、,1,4,7,10 2=-4,-1,2,5,8,1145（Z,+）上討論R的性質任取兩個類中的元素，通過+運算得到的元素均屬同一個等價類。如： -5+（-4） 0，1+11 0, 即 1+2=0, 1+1=2, 2+2=1, 1+0=0這是同余關系特有的性質，一般等價關系沒有。46同余關系推廣上述同余關系。設（X，*）上等價關系E，任意x1、x2、 x1、x2X，若x1Ex1,x2Ex2,則有（x1*x2）E（x1*x2),稱E為同余關系。同余關系不僅要考慮在哪個集合上的關系是等價關系，還用考慮運算后的結果是否保持等價關系。即（X，*）的運算*按等價類保持。47例（Z，）上，R1定義為xy(m

17、odm)； R2定義為R=(x,y)|x/y=2m,mZ. 解：前面已經驗證R1是同余關系； R2首先是等價關系。 其次，x1/x1=2k,x2/x2=2j,則 (x1x2)/(y1y2)=2(k+j), 故R2是同余關系。48練習題設整數(shù)集（A，+）上定義R：(x,y) R等價于|x|=|y|。問R是否是A上等價關系？是否是同余關系？49解 R是A上等價關系。但R不是同余關系。 若(x1,y1)R,(x2,y2)R，但是(x1+x2,y1+y2)R不一定成立。 例(1,1)R, (2,-2)R，但|1+2|1-2|50商代數(shù)定義：設（X，）上同余關系E，因E是等價關系，可按E對X分類，得一個

18、商集X/E，在商集上定義運算*，對任一x1E、x2EX/E,有 x1E*x2E=x1x2E， 這樣（ X/E ，*）構成一個代數(shù)系統(tǒng)，稱為（X，）的商代數(shù)。51定理： （X，）與其上的商代數(shù)（ X/E ，*）同態(tài)。證明：構造函數(shù)g:XX/E，g(x)=xE,， 易證g是滿射。且有 g(x1x2)=x1x2E =x1E*x2E =g(x1)*g(x2)52稱代數(shù)系統(tǒng)與商代數(shù)的同態(tài)是自然同態(tài)。由此任何一個代數(shù)系統(tǒng)總能找到與其同態(tài)的代數(shù)系統(tǒng)，這個同態(tài)的代數(shù)系統(tǒng)就是他的商代數(shù)。下面的工作就是如何得到商代數(shù)，也就是找到代數(shù)系統(tǒng)上的同余關系。53一種同余關系定義：設（X，）與（Y，*）同態(tài)，f：XY是同態(tài)

19、映射。在X上定義一個關系Ef： 即如果X上元素通過映射f，在Y上有相同的像，則由這樣的元素所構成的關系。54定理驗證上面定義的關系Ef是同余關系。證明：首先證明Ef是等價關系。 其次證Ef是同余關系。若x1Efx1,x2Efx2,即 f(x1)=f(x1),f(x2)=f(x2), f(x1x2)=f(x1)*f(x2) =f(x1)*f(x2)=f(x1x2), 因此x1x2Efx1x2，即Ef是同余關系。55定理：設f是（X，）與（Y，*）的滿同態(tài)，必有（ X/Ef，*）與（Y，*）同構。證明:只要證明存在一一對應h： X/EfY,h(x)=f(x),s.t. h(x1*x2)=h(x1)

20、*h(x2) 56(1)定義h：X/EfY,h(x)=f(x),由f是X到Y的滿同態(tài)，任意x1,x2X，有 f(x1x2)=f(x1)*f(x2)有 所以h是同態(tài)函數(shù)。57（2）如果x1 x2，則h(x1)=f(x1) h(x2)=f(x2) ，所以h是單射。 由f是滿射，對Y中任一元素y必有X中元素x，s.t.f(x)=y。由X/Ef定義，xxEf，即任一y，必有xEf與之對應， s.t.h(x)=y，所以h是滿射。58結論這個定理說明對一個代數(shù)系統(tǒng)(X，)而言，任一個與它同態(tài)的代數(shù)系統(tǒng)(Y,*)總可以找到X的商代數(shù)（X/E，*）與它同構。即從抽象觀念看，一個代數(shù)系統(tǒng)僅與其商代數(shù)滿同態(tài)。也說

21、明若( X，)與 (Y,*)滿同態(tài)，必能找到一個代數(shù)系統(tǒng)與Y同構。59第六章 群論 群是代數(shù)系統(tǒng)中最基本最重要的系統(tǒng)。在編碼理論,密碼安全中也有廣泛的應用. 606.1半群與單元半群定義：設是一個二元代數(shù)系統(tǒng)：半群：運算“*”滿足結合律； 可換半群：半群中運算“*”滿足交換律； 單元半群：半群中存在單位元e可換單元半群：半群滿足交換律，e存在有限半群 ：S是有限集； 無限半群 ：S是無限集；61例指出下列代數(shù)系統(tǒng)中那些是半群，那些是可交換半群，那些不是半群： Z,+,N,+,R,+，Z, N, ,R,，R-0,； （P(A), ）, （P(A), ）； （Z,max）,(Z,min),(Mn,

22、)； （Z4，+4）62例1、設n0, 1, , n1定義n上的運算n 如下： x,yn, xnyxy (mod n) ，證明是含么半群2、設有集合Sk=x|xZ且xk, “+”是 一個普通的加法運算, 試判斷是否是一個半群？63定義定義：子半群 一個半群（S,*），如果它有子代數(shù)（M,*），則M也是半群，稱為S的子半群。定義：等冪元 定義 a的冪 a1=a,a2=a*a,an+1=an*a 若a2=a,則稱a為等冪元。64如果有單位元e,可以定義：x0=e。如同一般的冪運算一樣, 由于結合律滿足, 有如下的公式： akaj=ak+j (ak)j=akj65例例1.半群的子代數(shù), ,都是的子半

23、群。例2.設S, *是一個可交換的單元半群, M是它的所有的冪等元構成的集合, 則是S, *的一個子單元半群。 66循環(huán)半群定義：設是一個半群, 若aS,使得對xS，都有 x=an 其中nZ+, 特別地 e=a0. 則稱此半群為由a所生成的循環(huán)半群, 而a稱為該循環(huán)半群的生成元；67若的生成元素是有限個元素，則稱M=a|aS且a是S的生成元為該循環(huán)半群的生成集。 若滿足交換律，則稱S為可換循環(huán)半群。68例可換循環(huán)半群（N，+）。判斷代數(shù)系統(tǒng)是否是循環(huán)含幺半群？若是,請求出其所有的生成元。代數(shù)系統(tǒng)是一個可換循環(huán)單元半群； 對aZn, 若(a,n)=1,則a是的生成元；當n是素數(shù)時, Zn中除單位

24、元“0”以外, 其它一切元素都是生成元。69定理：一個循環(huán)半群一定是一個可換半群。推論：每個循環(huán)單元半群是可換單元半群。定理：一個半群內的任一元素和它所有的冪組成一個由a生成的循環(huán)子半群。 證明：（S，*）是半群，任意aS，構造M=a,a2,a3,M上運算封閉，M是S的子集，故M是S的子代數(shù)；M是子半群，a是生成元，所以(M,*)是循環(huán)子半群。70單元半群單元半群是有單位元的半群。例：教材P77例6.5。整數(shù)集上模m同余關系R所劃分的類Zm=0,1,2,m-1，定義+m,m如下：（Zm,+m)，（Zm,m)是單元半群，單位元分別是0,1,滿足交換律。71單元半群是半群的擴充，比半群具有更多的性

25、質。設半群（S,*），若存在1S，有性質：1*1=1，任意xS，均有1*x=x*1=x，則(S,*)構成單元半群。定理：設S是有可列個元素的集合，（S，*）是單元半群，則在關于*的運算表中任何兩行或兩列均不相同。具體參見教材表6.2。72定理：單元半群（S，），若存在子系統(tǒng)（M,），且單位元在M中，則（M，）也是單元半群，稱為子單元半群。定義：循環(huán)單元半群：有單位元的循環(huán)半群，同時也是可換單元半群。73定理：一個可換單元半群，它的所有等冪元構成一個子單元半群。（67頁例2）證明：設可換單元半群（M，），M=等冪元（1）設a、bM,a2=a,b2=b，有(ab)(ab)= abab=aabb=a

26、b，故(M,)構成代數(shù)系統(tǒng)。（2）單位元是等冪元，故(M,)中有單位元。（3）M是M的子集。故(M,)是子單元半群。746.2群定義：群。一個二元代數(shù)系統(tǒng)若滿足： 1)G中運算“*”滿足結合律； 2)G中存在關于運算“*”的單位元； 3)G中每個元素都有逆元。 則稱該代數(shù)系統(tǒng)為一個群?；蛘叨x：單元半群，每一個元素都有逆元。75群的相關定義定義：如果為一個群，運算“*” 滿足交換律，則稱此群為可換群或Abel群；若|G|是有限的,則稱此群為有限群；若|G|是無限的,則稱此群為無限群；群的階，|G|，G的基數(shù)。若G的子代數(shù)（H，*）也是群，則稱為子群。76例1（Z,+），（Q,+），（R,+）都

27、是群，（Z+,+）,（N,+）不是群。設n是大于1的正整數(shù)，（Mn(R),+）是群,而（Mn(R), ）不是群。（P(B),）是群，其中為集合的對稱差運算。（Zn, ）是群,其中Zn=1,2,n-1,為模n運算。（R*, ）不是群，是半群。其中R*為非零實數(shù)集合， 運算定義為： 任意x,y R*, x y=y。 77例2（Z,+）,（R,+）都是無限群; （Zn, ）是n階有限群； （0,+）是平凡群，只有一個元素，既是單位元又是零元素。它們均為交換群.n(n1)階實可逆矩陣的集合關于矩陣乘法構成的群是非交換群，但對于加法構成交換群。78練習題判斷下列代數(shù)系統(tǒng)是否是群或Abel群：,，,， ,

28、，, 解：Abel群有, ,？79練習題證明是群。 證明：前面已證是單元半群，0為單位元，下面證明每個元素均有逆元。 如果x0，顯然010，如果x0，則有n-xn，顯然xn(n-x)=(n-x)+nx=0 所以x的逆元是n-x，因此xn，x有逆元。即是群。80群的性質群G中每個元素都是可消去的，即運算滿足消去律；群G中除e外無其它冪等元；為什么？階大于1的群G不可能有零元；為什么？群G中的任意兩個元素a, b，都有 (a*b)-1b-1*a-1群G的運算表中任意一行(列)都沒有兩個相同的元素；81群的性質一個群的方程a*x=b和y*a=b中，在群內有唯一解。證明：首先方程a*x=b解是存在的，

29、 x=a-1*b; 其次解是唯一的。 若x1也是方程的解，有a*x=a* x1=b，由群的消去律知x= x1。 82群的第二定義定義：若代數(shù)系統(tǒng)(G,*)滿足下列條件，則稱為群。 （1）結合律。 （2）方程a*x=b和y*a=b在G內有唯一解。83證明：只要推出G有單位元和逆元即可。（1） a*x=a的解為右單位元1r,同理y*a=a的解為左單位元1l，由解的唯一性，1r= 1l（2）由a*x=1和y*a=1分別得a的右、左逆元，又因滿足結合律，左右逆元相等。84群的同態(tài)、同構定義：設群(G，)、(H，*)，若存在函數(shù)g：GH，s.t.對每個a、bG，有g(ab)=g(a)*g(b)，則稱g是

30、從(G，)到(H，*)的群同態(tài)。若g是一一對應，則稱為群同構。定理：設(G，)與(H，*)群同態(tài)，函數(shù)g：GH是同態(tài)函數(shù)，則有g(1G)=1H,g(a-1)=g(a)-1定理：設(G，)是群，若(G，)與(H，*)滿同態(tài)或同構，則(H，*)也構成群。85變換群變換的定義：集合上的變換是從S到S的一個一一對應函數(shù)，記為t：SS。例：S=1,2，則t1(1)=1,t1(2)=2是變換； t2(1)=2,t2(2)=1是變換；但t3(1)=1,t3(2)=1不是變換。S=t1,t2是變換的集合，稱為變換集。86S中元素是變換，是一種函數(shù)，這是一種關系，而關系存在復合運算，故變換也存在復合運算，可稱為

31、復合變換。在變換集上定義一個變換的二元運算，可構成一個代數(shù)系統(tǒng)。這個二元運算可以取變換的復合運算。87驗證變換群 （1）S上的變換是封閉的。 （2）S上有恒等變換，故S中單位元即是恒等變換：t1(x)=x。對任意tS,t1*t=t*t1=t （3）S上任意變換t均為一一對應，故其逆變換t-1也是S上的，t*t-1=t1。 （4）復合變換滿足結合律。 因此（S,*）構成群，稱之為變換群。若S上的一些變換和復合運算構成一個群，也稱為變換群。88定義：集合S上的若干變換與復合運算若構成群，則稱為變換群。定理：任一個群(G,*)均與一個變換群同構。證明：取aG,存在變換ta，對G中每個元素，ta(x)

32、=x*a，這樣G中每個元素都有一個變換與之對應，設G=a,b,c,d,，有ta,tb,tc,td,記為集合G=ta,tb,tc,td,。 89 定義為變換的復合運算。下面證明存在一一對應函數(shù)g:GG，滿足同構方程。 令g(a)=ta,可證g是函數(shù)，是單射，是滿射，且有 g(a*b)=ta*b=x*a*b=tb(x*a)=tb(ta(x) =tatb=g(a)g(b)90任意一個群均可在變換群中找到一個同構群，故對群的研究可歸結為對變換群的研究。91有限群 設S為有限集，以|S|=3為例，有6個不同的變換，設S=1,2,3，有 可證這些變換對運算*構成一個群，稱為對稱群。記為S3=p1,p2,p

33、3,p4,p5,p6,其中p1是單位元。p2、p3、p6的逆元還是她們自身。p5、p4互為逆元。92定理：一個有限集上所有變換及復合運算構成一個群。例：S=p1,p4,p5構成一個群，也稱變換群。定義：對稱群、置換群 |S|=n,S上所有變換構成一個集合Sn,Sn及復合運算構成的群稱為S的對稱群。 若S上有若干變換，所組成的集合P及*構成的群（P，*）稱為S的置換群。93定理：S的對稱群（Sn,*）的階為n!。證明：由排列組合的理論知識很容易可知。94有限群的另一個定義定理：一個代數(shù)系統(tǒng)（G，*），若G為有限且滿足結合律及消去律，則構成一個群。證明：用群的第二定義：結合律以及 a*x=b,y*

34、a=b方程存在唯一解。 設G=a1,a2,an，取aG，作 G=a*a1,a*a2,a*an。95 由G代數(shù)系統(tǒng)的封閉性，G是G的子集，且由消去律，若ij，a*aia*aj。故|G|=n,因此G=G。 所以對bG或G，必有 akG,s.t. b=a*ak，且ak唯一。 同理y*a=b也存在唯一解。96群表對有限群，可用一組合表將運算表示出來，稱為群表。設|G|=1，群表是唯一的。設|G|=2，群表是唯一的。設|G|=3，群表是唯一的，且是對稱的，因此3階群是可換群。設|G|=4，群表不是唯一的，且均是對稱的。97群表|G|4|G|=1|G|=2|G|=3|G|=4這幾個群表參見教材87頁。98

35、從以上群表可看出一些特性：由于單位元1存在，群表中總有一行（一列）與表頭元素一樣。由于消去律，群表中每行（每列）各不相同，且任兩行（兩列）對應元也不同。因此，群表每一行（列）是群中元素的一個排列，是G中元素的一個置換。若G是可換群，其可換性與群表的對稱性是一致的。99定理：每個有限群均與一個置換群同構。證明：由教材83頁定理6.11，置換群中的每個置換是變換的特例，與復合運算構成一個群，且與對應的有限群同構。100循環(huán)群定義：方冪 設G是群，令a0=1, aj+1=aj*a , a-j=(a-1)j, 有性質akaj=ak+j，(ak)j=akj 定義：循環(huán)群 若群G的每個元素均是它的某一個固

36、定元素a的某次方冪，則稱G是由a生成的循環(huán)群，a稱為G的生成元素。101定義：周期 一個由a生成的循環(huán)群（G，*），若存在m，使得am=1的最小正整數(shù)m稱為a的周期；若不存在這樣的m，則稱a的周期無限。102循環(huán)群的構造對于任何群G，由G中元素a生成的子群是循環(huán)群。 任何素數(shù)階的群都是循環(huán)群。設G是循環(huán)群，若a是n階元，則 G=a0,a1,a2,an-1， 那么|G|=n 稱G為n階循環(huán)群; 若a是無限階元，則 G=a0,a1,a2,a3 稱G為無限階循環(huán)群。103例：（Z，+） 無限循環(huán)群，生成元：1，-1例：（4，+4） 周期為4的循環(huán)群，生成元：1、3例：模為m 的剩余類加群（Zm,+m

37、） 周期為m的循環(huán)群，生成元：1、k，其中k是與m互質的數(shù)。104循環(huán)群定理定理：設由a生成的循環(huán)群G，則有（1）若a的周期無限，則G與整數(shù)加群（I，+）同構。（2）若a的周期有限，則G與剩余類加群（Zm，+m）同構。證明: (1)定義f:GI，f(ak)=k (2)定義g:GZm，g(ak)=k 驗證f、g函數(shù)均是一一對應，且滿足同態(tài)方程。105由上面定理說明，任何循環(huán)群都可以找到與之同構的群。無論是整數(shù)加群還是剩余類加群的性質特性都有深刻的研究。故循環(huán)群的問題已基本解決。106G=循環(huán)群的生成元定理： (1)若G是無限循環(huán)群，則G的生成元是a和a1 。(2)若G是n階循環(huán)群，則 G有(n)

38、個生成元， 當n=1時G=的生成元為e； 當 n1時,對于任何小于等于n且與n互質的正整數(shù)r，ar是G的生成元。 即G的生成元ar (n,r)=1. 107證明思路： (1)證明 a1是生成元。證明若存在生成元b，則b=a或a1。 (2)只需證明(r,n)=1, 則ar是生成元 反之，若ar是生成元，則(r,n)=1. 108證明（1） (1) a是生成元，G, 任取 aiG, ai=(a1) i G。 假設 b 為生成元，b=aj, a=bt, a=bt=(aj)t=ajt ajt1=e 若 jt10與 a為無限階元矛盾, 因此 j = t = 1 或 j = t = 1。109證明（2）詳

39、細的證明可以參加其它資料。如果同學有興趣，查閱北京大學離散數(shù)學精品課程。110例題例1.設G是12階循環(huán)群，則小于或等于12且與12互質的數(shù)是1，5，7，11。設G=,則a1,a5,a7,a11是生成元。例2.設Z9是模9的整數(shù)加法群，則G的生成元是1，2，4，5，7，8。例3.設G=3Z=3k|kZ,G上的運算是普通加法，那么G只有兩個生成元：3和-3。111子群定義：一個群G如果它的子代數(shù)（H，*）也是一個群，則稱H是G的一個子群。H是群則必須滿足一些條件，下面給出充要條件。定理：一個群G，由它的一個子集H組成一個系統(tǒng)，該系統(tǒng)構成G的子群的充要條件是 a,bH,則a*bH ； aH,則a-

40、1H 證明：略112有關子群的定理定理：設H是G的一個子群，則 1H=1G，aH-1=aG-1定理：設G是群，G的子集H所構成的子代數(shù)（H，*）是子群的充要條件是： 若a,bH，則a*b-1 H。113有限子群的定理定理：設G是群，G的一個有限子集H所構成的（H，*）是一個群的充要條件是： 若a,bH，則a*bH。證明：結合律滿足說明構成代數(shù)系統(tǒng)；114平凡子群及例子例1：任一個群（G，*）都有兩個子群， 群（G，*）和（1 ，*），這兩個是任意群都有的子群，稱之為平凡子群。例2：群（Z4，+4）中， (2,+4)不是子群；(1,3,+4)不是子群；(0,2,+4)是子群。115子群的例子例3

41、：設群（G，*），任意aG,定義H=an,則H是G的子群。例4：定義Z2=2n|n是整數(shù)，（Z2，+）是（Z，+）的子群。116子群的陪集及Lagrange定理 群的子群反映了群的結構和性質；陪集和拉格朗日定理反映了群與子群之間的關系。例：整數(shù)加群利用模3同余關系，將I劃分成3個剩余類，分別是0,1,2。 對于以上的同余關系R，也可表示成另一種方式。記H=3*i|iI，由定理知，H是整數(shù)加群的子群。117模3同余關系G上的模3同余關系，a,bG,a=b(mod3)等價于（a-b）/3余數(shù)為0。即故可由a-bH或a+b-1H來確定等價關系，進而對G進行分類。也就是說，G的剩余類是利用H來分類的。

42、118把上例推廣至一般情況設H是G 的一個子群，確定G上的一個關系R，（a,b）R當且僅當a*b-1 H，這個關系稱為G上的右陪集關系，可寫為 ab(modH)定理：設G有一個子群H，則在G上的一個右陪集關系R，ab(modH)是等價關系。 證明：略119例：H=3i,驗證I上m=3同余關系是右陪集關系。120右陪集定義：右陪集 a.群G的子集H所確定的右陪集關系對G所劃分的類稱為子群H的右陪集，包含a的右陪集記以Ha。 b.H是群G的子群，稱Ha=h*a|hH為由aG確定的子群H的右集，a稱為Ha的代表元素。121分析右陪集的定義由定義知，右陪集是由一個等價關系（右陪集關系）所劃分成的等價類

43、。右陪集的元素構成。Ha=x|xG,xa(modH)，(x,a) R,x與a有右陪集關系：x*a-1H，記h= x*a-1，得x=h*a，故Ha=h*a|hH。因此包含a的右陪集是H內所有元素與a運算后所得結果組成的集合。122左陪集定義：左陪集 由G的一個子群可確定群G上的左陪集關系R，（a,b）R當且僅當b-1*a H，這個R是等價關系,稱為左陪集關系。 由R所劃分的等價類稱為左陪集。包含a的左陪集記以aH=ah|hH。左陪集與右陪集是類似的，都是由陪集關系確定的等價類。123等勢定理：群G的一個子群H與其每個右陪集Ha等勢。證明：定義f：HHa，f(h)=h*a。 可以證明f是一一對應。

44、因此H與Ha等勢。124相同的基數(shù)定理1：設H是群G的一個子群，Ha、Hb是任意兩個右陪集（或左陪集），則或者Ha=Hb，或者Ha與Hb是分離的。證明：略。因為右陪集是等價類，那么按照等價關系的理論，由等價關系劃分的等價類要么相等要么相互分離。125分析 設Ha與Hb相互分離，即是不同的等價類，那么它們均與H是等勢的，因此Ha與Hb這兩個不同的右陪集具有相同的基數(shù)。 得出結論:(H,*)的所有右陪集具有相同的基數(shù)。126拉格朗日定理定理：一個有限群G的階一定被它的子群的階所等分。分析：階為n有限群的子群H階為m,也是有限群，H的所有右陪集構成了G上的所有等價類，也就是構成了G上的一個劃分。每個

45、劃分塊即每個右陪集的基數(shù)是相同的，并且必為整數(shù)，與H的基數(shù)相同。即|aH|=|H|=m，這樣由H確定的等價關系產生的劃分塊個數(shù)為n/m。127拉格朗日定理推論設G的子群H的右陪集個數(shù)為k(稱之為G內H的指數(shù))，則有k=|G|/|H|推論1：任一個階為素數(shù)的有限群沒有真子群。推論2：任一個階為n的有限群的循環(huán)子群，它的周期均能除盡n。推論3：任一個階為n的有限群，可得到 an=1128證明1：若有真子群H階為q，設G的階為p,則p/q為整數(shù)，即q是p的真因子，與p為素數(shù)矛盾。證明2：設H為G的循環(huán)子群，|G|=n，設H=a0,a1,am-1，|H|=m，則mk=n，即H的周期均能除盡n。證明3：

46、任意G中元素a,有a0,a1,am,G，由于G為有限群，故上述元素中必有相同元，設ai=aj(ij),有ai-j=1,記k=i-j，則ak=1,記S=a0,a1,ak-1，則S為G的循環(huán)子群，由推論2，k能被n整除。n=mk，故an=1。129循環(huán)子群定理 2 G=是循環(huán)群，那么 (1) G 的子群也是循環(huán)群。 (2) 若 G是無限階，則 G的子群除e外也是無限階。 (3) 若 G是 n階的，則 G的子群的階是 n的因子， 對于 n的每個正因子 d, 在 G中有且僅有一個 d 階子群130證明思路：(1) 子群 H中最小正方冪元 am 為 H的生成元 。(2) 若子群 H=有限，ae, 則推出

47、 |a| 有限。 (3) H=, |H|=|am|, (am)n=e. 從而 |am| 是 n的因子. (4) 是 d階子群，然后證明唯一性. 131證明 (1) 設 H是 G=的子群，不妨設 He. 取 H中最小正方冪元am ,H. 對于任意整數(shù) i, i = jm+r, r0,1,m1 aiH ar=ai(am)jH r=0 ai H 132(2) 設 H為 G的子群，若 He, H=, m為 H 中最小正方冪元. 假設 |H| =t, 則 (am)t = e amt = e，與 a為無限階元矛盾。(3) 設 G = e ,a, , an1 ，H=e命題顯然成立. 若 He, 必有 H=,

48、 am 為 H中最小正方冪元. 設 |H| =|am|=d, (am)n=(an)m=e |am| | n d | n 。133(4) 設 d | n，則 ,H 是 G的 d階子群. 若H=也是G的d階子群， 其中am為最小正方冪元.則 134求下例的生成元和子群. 例1。 , 生成元為與12 互質的數(shù)：1, 5, 7, 11。 12 的正因子為 1, 2, 3, 4, 6, 12， 子群：, , , 如=0，2，4，6，8，10，子群的階為6.例2 G=為12階群， 生成元為a2, a10, a14, a22 （對應1, 5, 7, 11 ） G的子群：, , , , 135例3 為無限循環(huán)

49、群， 生成元為a, a1； 子群為，i = 0,1,2,；例4 G=， 生成元：1, 1; 子群 nZ, n = 0,1,136群、商群、同態(tài)群如同第五章的代數(shù)系統(tǒng)、商代數(shù)一樣，我們將研究群與商群。要得到一個商群，必須構造一個同余關系，然后據(jù)這種同余關系建立群與商群，以及與它的一個同態(tài)群間的關系。（N，*）是（G，*）的正規(guī)子群，首先證明陪集關系是同余關系，其次定義商群（G/N，）。最后構造一個正規(guī)子群群的同態(tài)核。137正規(guī)子群與同態(tài)定義：群G的一個子群N，若對任意aG，均有aN=Na，則稱N是G的正規(guī)子群。 此時N的左（右）陪集稱為N的陪集。例1：可換群的任意子群都是正規(guī)子群。例2：對稱群的

50、子群。教材94頁。只有當左右陪集相等時，才是正規(guī)子群。138定理定理：群（G，）的子群（N，）是正規(guī)子群的充分必要條件是 ana-1N， a、a-1G， nN 定理：群G的一個正規(guī)子群N所確定的左（右）陪集關系是一個同余關系。分析：右（左）陪集關系指的是群中兩個元素滿足ab-1N（ b-1aN）,則a、b有關系，顯然這是由群的子群來確定的。可驗證這是同余關系。139群與商群的關系由定理知群（G,）的正規(guī)子群（N，）所確定的陪集關系是同余關系；又由第五章自然同態(tài)理論，G/N是由同余關系定義的商集，定義運算* 如下： 任一aN、bNG/N, aN*bN=(ab)N 稱（G/N，*）為G關于正規(guī)子群

51、N的商群。 140分析上面定義出現(xiàn)的幾個因素：（1）等價關系。G上有一個正規(guī)子群，由正規(guī)子群的陪集關系不僅是等價關系，還是同余關系。（2）根據(jù)同余關系，可以定義G的商集，因為同余關系與N有關，故記為G/N。（3）在商集上定義等價類（陪集）的運算，就得到了商代數(shù)，即商群。（4）由第五章最后一節(jié)內容知，群G與商群是滿同態(tài)的。故存在g：G G/N，g是滿同態(tài)映射。141討論一個特殊的正規(guī)子群上面已經定義了群的商群，但是等價關系（同余關系）如何定義？或者確定陪集關系的正規(guī)子群如何得到？這是目前需要考慮的問題。定義：設f是（G，）到（G，）的群同態(tài)，則G的子集K=k|kG，f(k)=1G 叫同態(tài)f的核。

52、142驗證K為正規(guī)子群定理：設K是從群（G，）到（G，）的同態(tài)f的核，則（K，）是（G，）的正規(guī)子群。證明思路： （1）K是G的子群。若k1、k2 K ，有k1k2 -1K即可。 （2）由定理6.24驗證K是正規(guī)子群。 若n K,a G，有ana-1K即可。143定理：設f是群（G，）到（G，）的滿同態(tài)，K是f的核，則（G/K，*）與（G，）同構。證明思路: （1）因為K是正規(guī)子群，由K所確定的陪集關系與第五章所確定的同余關系Ef一致?；仡橢f的定義。 （2）根據(jù)第五章教材72頁定理5.14，可以得到此定理。144練習題1已知（G，*）是群，G=1，2，3，4，5，6，* 是對模7的乘法。（1

53、）構造此群的運算表；（2）找出元素2的生成子群，并指出階是多少。145練習題2設G是群，非空集合H是G的子集，H中的元素都是有限階的，運算在H中封閉，證明 （H，*）是（G，*）的子群。146第七章其他代數(shù)系統(tǒng)本章研究一些較復雜的代數(shù)系統(tǒng)：環(huán)，域，格，布爾代數(shù)等。我們關心的是代數(shù)系統(tǒng)中兩個不同運算間的聯(lián)系。這些代數(shù)系統(tǒng)在計算機科學的復雜領域中有重要應用。1477.1環(huán)、理想、整環(huán)和域定義： 環(huán) 設有代數(shù)系統(tǒng)（R，+，），如滿足下列條件： （1）（R，+）是可換群 （2）（R，）是半群 （3）運算對+滿足分配律 a（b+c)=ab+ac （b+c)a =ba+ca 則稱（R，+，）是環(huán)。148定義：可換環(huán)；定義：含單位元的環(huán)；例：（Z，+，）構成環(huán)； （Z4，+4，4）構成環(huán)；149有關環(huán)的說明在環(huán)中，（R，+）是群，有單位元，有逆元，有交換律，結合律，消去律；（R，）只是半群，不一定有單位元。在環(huán)中，對+滿足分配律，反之不一定。環(huán)中有兩種運算，一般稱之為加、乘，+的單位元用0表示，的單位元若存在，就用1表示。由環(huán)的定義條件3知，+的單位元必是對的零元素，故（R，）有零元素，若階大于1，則不可