1、離散數(shù)學(xué) 第六章 代數(shù)第1頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/25第六章 代 數(shù) 6.1 代數(shù)結(jié)構(gòu)6.2 子代數(shù)6.3 同態(tài)6.4 同余關(guān)系6.5 商代數(shù)6.6 半群和獨異點6.7 群6.8 環(huán)和域第2頁，共175頁，2022年，5月20日，1點51分，星期六 32022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)系統(tǒng)一個非空集合A，連同若干個定義在該集合上的運算f1,f2,fn，所組成的系統(tǒng)稱為一個代數(shù)系統(tǒng)，簡稱代數(shù)，記為。第3頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu) 代數(shù)系統(tǒng)的組成 載體（一個非空集合A） 定義在載體上的

2、運算 (f1,f2,fn) 代數(shù)常元第4頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)【例題1】(a)正整數(shù)集合I+，以及定義在該集合上的普通加法運算“+”組成一個代數(shù)系統(tǒng)。(b)一個有限集合S，由S的冪集(S)，及定義在(S)上的交、并、補運算組成一個代數(shù)系統(tǒng) 。第5頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算 設(shè)A1,A2,An,A是非空集合，f是從A1A2An 到A的一個映射，則稱f為從集合A1A2An到A的一個n元代數(shù)運算，簡稱運算，n稱為代數(shù)運算的階。xnx3fx2x1y第6頁，共175

3、頁，2022年，5月20日，1點51分，星期六 72022/9/256.1代數(shù)結(jié)構(gòu)運算的封閉性 設(shè)f是從A1A2An到A的一個n元運算，若A=A1=A2=An，則稱該n元運算在集合A上是封閉的，亦稱f是A上的n元運算。 特別地，設(shè)f是從A到A的映射，則稱f是一個在A上封閉的一元運算。設(shè)f是從A2到A的映射，則稱f是一個在A上的封閉的二元運算。第7頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)【例題2】 一臺自動售貨機能接受五角和一元的硬幣。當(dāng)人們投入任意兩枚上述硬幣時，自動售貨機將供應(yīng)出相應(yīng)的飲料，如下表5角1元5角雪碧可樂1元可樂酷兒第8頁，共17

4、5頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu) 設(shè)集合A5角，1元，集合B雪碧，可樂，酷兒，則上表其實是一個從AA到B的一個映射，也即一個從A2到B的一個二元運算。問運算在A上是否封閉？第9頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)【例題3】 設(shè)有正整數(shù)集I+，“+”是I+上的普通加法運算。在I+上定義二元運算*為：任取x, yI+, x*y=x+y。令 S=2k | kI+=2,4,6,8, T=n | n I+, n能整除30=1,2,3,5,6,10,15,30問運算*在S和T上是否封閉? 第10頁，共17

5、5頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)運算表 當(dāng)集合A是有限集時，例如A=a1,a2,an，則A上一元代數(shù)運算和二元代數(shù)運算分別用如表(a)和(b)所示的運算表來表示。 a1 a2 ana1a2an a1 a1 a1 a2 a1 an a2 a1 a2 a2 a2 an an a1 an a2 an an(ai)a1a2an(a1)(a2)(an)(a)(b)運算符集合A運算結(jié)果第11頁，共175頁，2022年，5月20日，1點51分，星期六 122022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)一交換律 設(shè)*是定義在集合A上的一個二元運算，如果任取x,y

6、A，都有x*y=y*x，則稱該二元運算是可交換的?！纠}4】設(shè)Q是有理數(shù)集合，是Q上的二元運算，對任意a,bQ, ab=a+b-ab,其中+和是普通的加法、乘法運算，問是否是可交換的？第12頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)二結(jié)合律 設(shè)*是定義在集合A上的一個二元運算，如果對于任意x,y,zA ，都有x*(y*z)=(x*y)*z,則稱該二元運算是可結(jié)合的?！纠}5】設(shè)A是一個非空集合，*是A上的一個二元運算，對于任意a,b A ,有a*b=b,證明運算*是可結(jié)合的。第13頁，共175頁，2022年，5月20日，1點51分，

7、星期六 142022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)三分配律 設(shè)*和 是定義在集合A上的二元運算，如果對任意的a,b,cA，都有 *對 左可分配 *對 右可分配則稱*對 是可分配的。 第14頁，共175頁，2022年，5月20日，1點51分，星期六 152022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)三【例題6】設(shè)集合A=,在A上定義兩個二元運算*和，如下表(a)和(b)所示。運算對運算*可分配嗎？運算*對運算呢？* (a)(b)第15頁，共175頁，2022年，5月20日，1點51分，星期六 162022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)四吸收律 設(shè)*和 是定義在集合A上的兩個可交換

8、的二元運算，如果對于任意的x,yA ,都有 則稱運算*和 滿足吸收律。第16頁，共175頁，2022年，5月20日，1點51分，星期六 172022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)五等冪律 設(shè)*是定義在集合A上的一個二元運算，如果對于任意xA,都有x*x=x,則稱運算*滿足等冪律。第17頁，共175頁，2022年，5月20日，1點51分，星期六 182022/9/256.1代數(shù)結(jié)構(gòu)【例題7】設(shè)(S)是集合S上的冪集，在(S)上定義兩個二元運算：集合的并運算和集合的交運算，驗證和滿足吸收律和等冪律。解答：和運算是可交換的。 A,B(S),有 A(AB)=A A(AB)=A所以和滿足吸收律。

9、又有 A A=A A A=A所以和滿足等冪律。第18頁，共175頁，2022年，5月20日，1點51分，星期六2022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)運算的性質(zhì)六消去律 設(shè)*是定義在集合上的一個二元運算，元素aA,如果對于任意x,y A,都有 a*x=a*y x=y a是左可消去的 x*a=y*a x=y a是右可消去的 則稱a關(guān)于運算*是可消去的。若A中的所有元素都是可消去的，則稱運算*滿足消去律。第19頁，共175頁，2022年，5月20日，1點51分，星期六 202022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)常元代數(shù)系統(tǒng)中，針對某一代數(shù)運算表現(xiàn)出具有某些特殊性質(zhì)的元素稱為代數(shù)常元，常見的有：幺元、零元

10、、逆元、等冪元等。幺元 左幺元：設(shè)*是定義在集合A上的一個二元運算，若存在元素el，對于A中的每一個元素x，都有 el * x=x則稱el為A中關(guān)于運算*的左幺元。 第20頁，共175頁，2022年，5月20日，1點51分，星期六 212022/9/256.1代數(shù)結(jié)構(gòu)幺元 右幺元：設(shè)*是定義在集合A上的一個二元運算，若存在元素er，對于A中每一個元素x,都有 x* er=x則稱er為A中關(guān)于運算*的右幺元。第21頁，共175頁，2022年，5月20日，1點51分，星期六 222022/9/256.1代數(shù)結(jié)構(gòu)幺元 幺元：設(shè)*是定義在集合A上一個二元運算，若A中有一個運算e,它既是左幺元，又是右幺

11、元，則稱e為A中關(guān)于運算*的幺元，亦稱作單位元。 e*x=x*e=x第22頁，共175頁，2022年，5月20日，1點51分，星期六 232022/9/256.1代數(shù)結(jié)構(gòu)【例題8】 設(shè)集合S=a,b,c,d, S上定義的兩個二元運算*和的運算表如下表所示，試求出其中的左幺元和右幺元。* a b c dabcdd a b ca b c da b c ca b c da b c d abcda b d cb a c dc d a bd d b c(a)(b)第23頁，共175頁，2022年，5月20日，1點51分，星期六 242022/9/256.1代數(shù)結(jié)構(gòu)定理設(shè)*是定義在集合A上的一個二元運算，

12、且在A中有關(guān)于運算*的左幺元el和右幺元er,則el =er=e,且A中的幺元是唯一的。 證明：設(shè)el 和er分別是A中關(guān)于運算*的左幺元和右幺元，則有 el= el *er= er=e 假設(shè)另有幺元eA, 則有e=e*e=e,結(jié)論得證。第24頁，共175頁，2022年，5月20日，1點51分，星期六 252022/9/256.1代數(shù)結(jié)構(gòu)代數(shù)常元零元 左零元：設(shè)*是定義在集合A上的一個二元運算，如果有一個元素lA,對于任意的元素xA都有l(wèi)*x= l，則稱l為A中關(guān)于運算*的左零元。 右零元：如果有一個元素rA,對于任意的元素xA都有x*r= r，則稱r為A中關(guān)于運算*的右零元。第25頁，共17

13、5頁，2022年，5月20日，1點51分，星期六 262022/9/256.1代數(shù)結(jié)構(gòu)零元 零元：如果A中的一個元素，它既是左零元，又是右零元，則稱為A中關(guān)于運算*的零元。 * x=x*=第26頁，共175頁，2022年，5月20日，1點51分，星期六 272022/9/256.1代數(shù)結(jié)構(gòu)【例題9】 設(shè)“淺”表示不易褪色的淺色衣服，“深”表示易褪色的深色衣服，集合S=淺，深，定義S的一個二元運算“混洗”，記為“ ”，則 的運算表如下表所示。求S中關(guān)于 運算的幺元和零元。 淺 深淺深 淺 深 深 深第27頁，共175頁，2022年，5月20日，1點51分，星期六 282022/9/256.1代數(shù)

14、結(jié)構(gòu)定理設(shè)*是定義在集合A上一個二元運算，且在A中有關(guān)于運算*的左零元l和右零元r,那么l= r= ，且A中的零元是唯一的。第28頁，共175頁，2022年，5月20日，1點51分，星期六 292022/9/256.1代數(shù)結(jié)構(gòu)逆元 逆元：設(shè)是一個代數(shù)系統(tǒng)，*是定義在集合A上的一個二元運算，e是A中關(guān)于運算*的幺元。x,yA,如果x*y=e,那么關(guān)于運算*,x是y的左逆元，y是x的右逆元。如果x*y=y*x=e,那么關(guān)于運算*,x與y互為逆元。運算x的逆元記為x-1。 第29頁，共175頁，2022年，5月20日，1點51分，星期六 302022/9/256.1代數(shù)結(jié)構(gòu)定理設(shè)是一個代數(shù)系統(tǒng)，*是

15、定義在集合A上的一個二元運算，e是A中關(guān)于運算*的幺元。若運算*是可結(jié)合的，且元素x有左逆元l和右逆元r，則l=r。證明：因為e是A中關(guān)于運算*的幺元且x有左逆元l和右逆元r,則有 l*x=x*r=e又運算是可結(jié)合的，所以 l=l*e=l*(x*r)=(l*x)*r=e*r=r第30頁，共175頁，2022年，5月20日，1點51分，星期六 312022/9/256.1本節(jié)小結(jié)代數(shù)系統(tǒng)組成：載體、定義在載體上的運算、代數(shù)常元。設(shè)為代數(shù)系統(tǒng)，*是定義在A上的二元運算，則運算*的某些性質(zhì)以及代數(shù)常元可以直接從運算表中得到：運算*是封閉的，當(dāng)且僅當(dāng)運算表中的每個元素都屬于A；運算*滿足交換律，當(dāng)且僅

16、當(dāng)運算表關(guān)于主對角線對稱；第31頁，共175頁，2022年，5月20日，1點51分，星期六 322022/9/256.1本節(jié)小結(jié)運算滿足等冪律，當(dāng)且僅當(dāng)運算表中主對角線上的每一元素與它所對應(yīng)的行(列)表頭元素相同;運算滿足消去律，當(dāng)且僅當(dāng)運算表中任意行、任意列沒有相同的兩個元素；若A中有關(guān)于運算*的零元，則該元素所在的行和列中的所有元素都等于該元素；若A中有關(guān)于運算*的幺元，則該元素所在的行(列)中的所有元素都依次與列(行)表頭元素相同;第32頁，共175頁，2022年，5月20日，1點51分，星期六 332022/9/256.1本節(jié)小結(jié)設(shè)A 中有關(guān)于運算*的幺元e，元素a與b互逆，當(dāng)且僅當(dāng)運

17、算表中a行、b列對應(yīng)的元素與a列、b行對應(yīng)的元素都是e。代數(shù)常元：幺元、零元。第33頁，共175頁，2022年，5月20日，1點51分，星期六 342022/9/256.1習(xí)題習(xí)題一 設(shè)為代數(shù)系統(tǒng)，其中A=1,2,3,4,“*”定義如下表所示： (a)運算*是可交換的嗎？為什么？ (b)運算*是可結(jié)合的嗎？為什么？ (c)求A中關(guān)于運算*的幺元， 并給出每個元素的逆元。 (d)A中有關(guān)于運算*的零元嗎？*1 2 3 412341 2 3 42 3 4 13 4 1 24 1 2 3 第34頁，共175頁，2022年，5月20日，1點51分，星期六 352022/9/256.1習(xí)題習(xí)題二設(shè)I是整

18、數(shù)集合，函數(shù)g:III，定義為： g(x,y)=x*y=xyxy，其中+和 是普通的加法和乘法運算。(a)試證明二元運算*是可交換的和可結(jié)合的。(b)求運算*的幺元，并指出每個元素的逆元。第35頁，共175頁，2022年，5月20日，1點51分，星期六 362022/9/256.2子代數(shù)子代數(shù)定義 設(shè)是一個代數(shù)系統(tǒng)，*和分別是載體A上的二元運算和一元運算，k是代數(shù)常元，如果滿足 (1)A A, (2)*和運算在A上封閉， (3)kA, 那么稱是的子代數(shù)。第36頁，共175頁，2022年，5月20日，1點51分，星期六 372022/9/256.2子代數(shù)平凡子代數(shù)定義 設(shè)是一代數(shù)系統(tǒng)，T是由A中

19、的代數(shù)常元構(gòu)成的集合，且運算*和在T上封閉。稱和是的平凡子代數(shù)，非平凡子代數(shù)亦稱為真子代數(shù)。第37頁，共175頁，2022年，5月20日，1點51分，星期六 382022/9/256.2習(xí)題習(xí)題一 I是整數(shù)集合，Ie和Io分別是偶數(shù)集合和奇數(shù)集合，+是I上的普通加法運算，則是一代數(shù)系統(tǒng)。和是的子代數(shù)嗎？ 解答：是的子代數(shù)。而不是的子代數(shù)，因為Io在+上不封閉。第38頁，共175頁，2022年，5月20日，1點51分，星期六 392022/9/256.2習(xí)題習(xí)題二 I是整數(shù)集合，I+是正整數(shù)集合，+是I上的普通加法運算，則是一代數(shù)系統(tǒng)。是的子代數(shù)嗎？ 解答： 不是的子代數(shù)，因為 0 I+。第39

20、頁，共175頁，2022年，5月20日，1點51分，星期六 402022/9/256.3同態(tài)同態(tài)的定義 設(shè)A=和A=是兩個具有相同構(gòu)成的代數(shù)系統(tǒng)，f是從S到S的一個映射，且對任意a,bS滿足： f(a*b) = f(a) * f(b) f(a) = f(a) f(k) = k 則稱f為由A到A的一個同態(tài)映射，簡稱同態(tài)。A同態(tài)于A,記作AA。第40頁，共175頁，2022年，5月20日，1點51分，星期六 412022/9/256.3同態(tài)同態(tài)象 設(shè)f是從A=到A=的一個同態(tài)映射，稱為A在映射f下的同態(tài)象。其中 下圖反映了兩個代數(shù)系統(tǒng)間的同態(tài)關(guān)系。第41頁，共175頁，2022年，5月20日，1點

21、51分，星期六 422022/9/256.3同態(tài)kSSfkaf(a)bf(b)cf(c)a*bf(a)*f(b)(c)f(c)*同態(tài)象第42頁，共175頁，2022年，5月20日，1點51分，星期六 432022/9/256.3同態(tài)【例題1】 設(shè)代數(shù)系統(tǒng), I是整數(shù)集, 是普通乘法運算。如果我們只對運算結(jié)果是正數(shù)、負(fù)數(shù)還是零關(guān)心,那么代數(shù)系統(tǒng)中的運算結(jié)果的特征就可以用另一個代數(shù)系統(tǒng)的運算結(jié)果來表示,其中B+,-,0, 是B上的二元運算，運算表如下所示，構(gòu)造從到的同態(tài)映射。第43頁，共175頁，2022年，5月20日，1點51分，星期六 442022/9/256.3同態(tài)解答：構(gòu)造函數(shù)f:IB,

22、f(x)顯然，任取a,bI, f(ab) = f(a) f(b)。所以，f是由到的一個同態(tài)。 + - 0+-0 + - 0 - + 0 0 0 0+ x0 - x00 x=0第44頁，共175頁，2022年，5月20日，1點51分，星期六 452022/9/256.3同態(tài)同態(tài)的分類 設(shè)f是由A=S,*, ,k到A=S,*, ,k的一個同態(tài)。 滿同態(tài):若f是滿射的，則稱f為由A到A的一個滿同態(tài)。A就是A在滿同態(tài)f下一個同態(tài)象。單一同態(tài)：若f是單射的，則稱f為由A到A的一個單一同態(tài)。顯然，A在單一同態(tài)f下的同態(tài)象與A同構(gòu)。第45頁，共175頁，2022年，5月20日，1點51分，星期六 46202

23、2/9/256.3同態(tài)同態(tài)的分類同構(gòu)：若f是雙射的，則稱f為由A到A的一個同構(gòu)映射，簡稱同構(gòu)。A同構(gòu)于A，記作A A。自同態(tài)：若A=A，則稱f為A上的自同態(tài)。自同構(gòu)：若A=A且f是雙射的，則稱f為A上的自同構(gòu)。第46頁，共175頁，2022年，5月20日，1點51分，星期六 472022/9/256.3同態(tài)【例題2】 N是自然數(shù)集合，+是N上的普通加法運算，設(shè)Nk=0,1,2,k-1,+k是定義在N上的模k加法運算。設(shè)函數(shù)f: NNk定義為 f(x)=x (mod k) 證明：f是從到Nk, +k, 0)的一個滿同態(tài) 映射。第47頁，共175頁，2022年，5月20日，1點51分，星期六 48

24、2022/9/256.3同態(tài)證明：(a)顯然，f是從N到Nk的滿射。 (b)任取x,yN,有 f(x+y)=(x+y)(mod k) = (x(mod k) + y(mod k) (mod k) = (x(mod k) +k (y(mod k)=f(x)+kf(y) (c) f(0)=0。 所以，f是從到的一個滿同態(tài)。第48頁，共175頁，2022年，5月20日，1點51分，星期六 492022/9/256.3同態(tài)【例題3】 設(shè)A=a,b,c,d,在A上定義一個二元運算如表a所示，又設(shè)B=0,1,2,3,在B上定義一個二元運算*如表b所示。構(gòu)造從代數(shù)系統(tǒng)到的一個同構(gòu)映射。a b c dabcd

25、a a a aa b c da c a ca d c b*0 1 2 301232 0 2 00 1 2 32 2 2 20 3 2 1(a)(b)第49頁，共175頁，2022年，5月20日，1點51分，星期六 502022/9/256.3同態(tài)解答： 設(shè)函數(shù)h: AB, h(a)=2,h(b)=1,h(c)=0,h(d)=3。 容易驗證： (a) h是雙射的； (b)任取x,yA, h(xy)=h(x)*h(y); (c)中的幺元b,h(b)=1也是中的幺元；中的零元a,h(a)=2也是的零元。 所以h是從代數(shù)系統(tǒng)到的一個同構(gòu)映射。 第50頁，共175頁，2022年，5月20日，1點51分，

26、星期六 512022/9/256.3同態(tài)的性質(zhì)定理設(shè)f是從A=到A=的一個同態(tài)映射，那么A的同態(tài)象是A的子代數(shù)。證明：(i)因為f是從S到S的一個映射,所以f(S) S。(ii)因為kS, f(k)=k,所以kf(S).(iii)任取a,bf(S)，存在x,yS,使得f(x)=a,f(y)=b。因為x*y=zS,所以 a * b=f(x)*f(y)=f(x*y)=f(z) f(S)故f(S)在運算*下是封閉的。第51頁，共175頁，2022年，5月20日，1點51分，星期六 522022/9/256.3同態(tài)的性質(zhì)(iv)任取af(S),存在xS使得f(x)=a。 因為xS,所以a = f(x)

27、=f(x) f(S),故f(S)在運算下是封閉的。 由(i)(ii)(iii)(iv)可知，是A的子代數(shù)。fA=同態(tài)象A=第52頁，共175頁，2022年，5月20日，1點51分，星期六 532022/9/256.3同態(tài)的性質(zhì)定理設(shè)f是從A=到A=的一個同態(tài)映射，A=是A在同態(tài)映射f下的同態(tài)象，則有(1)若*在A中可交換, 則*在A中也是可交換的;(2)若*在A中可結(jié)合,則*在A中也是可結(jié)合的;(3)若在A中*對可分配,則在A中*對也可分配;第53頁，共175頁，2022年，5月20日，1點51分，星期六 542022/9/256.3同態(tài)的性質(zhì)(4)若e是A中關(guān)于運算*的幺元，則f(e)是A中

28、關(guān)于運算*的幺元；(5)若是A中關(guān)于運算*的零元，則f()是A中關(guān)于運算*的零元；(6)任取xS, x對運算*有逆元x-1,在f(S)中，f(x)也有關(guān)于運算*的逆元f(x-1)。第54頁，共175頁，2022年，5月20日，1點51分，星期六 552022/9/256.3小結(jié)子代數(shù)概念：一個代數(shù)系統(tǒng)載體A的一個子集A，如果在該代數(shù)系統(tǒng)的所有運算下都封閉，則稱以A為載體的代數(shù)系統(tǒng)是原代數(shù)系統(tǒng)的子代數(shù)。同態(tài)概念：同態(tài)映射不僅建立了兩個代數(shù)系統(tǒng)載體間的映射關(guān)系，更重要的是同時還建立了兩個代數(shù)系統(tǒng)對應(yīng)運算間的映射關(guān)系。第55頁，共175頁，2022年，5月20日，1點51分，星期六 562022/9

29、/256.3小結(jié)同態(tài)象概念：一個代數(shù)系統(tǒng)與其同態(tài)象之間有許多相似的地方。同態(tài)的分類：根據(jù)同態(tài)映射的性質(zhì)可以將同態(tài)分為：滿同態(tài)、單一同態(tài)和同構(gòu)。同態(tài)性質(zhì)：在同態(tài)映射下，同態(tài)象的運算能夠保持原代數(shù)系統(tǒng)中對應(yīng)運算的交換性、結(jié)合性和分配性，并且幺元、零元和逆元也滿足映射對應(yīng)關(guān)系。第56頁，共175頁，2022年，5月20日，1點51分，星期六 572022/9/256.3本節(jié)習(xí)題習(xí)題一 設(shè)h是從A=到A=的同態(tài)，證明如果是A的子代數(shù)，那么是A的子代數(shù)。h-1(T)Thh-1hA=A=第57頁，共175頁，2022年，5月20日，1點51分，星期六 582022/9/256.3本節(jié)習(xí)題證明：(i)因為是

30、的子代數(shù)，所以T S。故有h-1(T) h-1(S) S。(ii)任取x,yh-1(T),存在x,yT使得h(x)=x,h(y)=y因為x,yS且h是從A到A的同態(tài)，所以有 h(x*y)=h(x)*h(y)=x * y T 故x*yh-1(T),即h-1(T)對*運算是封閉的。(iii)因為h(k)=k T,所以k h-1(T)。由(i)(ii)(iii)可知，是的子代數(shù)。第58頁，共175頁，2022年，5月20日，1點51分，星期六 592022/9/256.4同余關(guān)系同余的定義運算上的同余關(guān)系：設(shè)A=是一個代數(shù)系統(tǒng)，是載體S上的等價關(guān)系，任取a,b,cS。(1)當(dāng)ab時，若ab,則等價關(guān)

31、系在一元運算下是可保持的，稱是關(guān)于運算同余關(guān)系。(2)當(dāng)ab和cd時，若有a*cb*d，則等價關(guān)系在二元運算*下是可保持的，稱是關(guān)于運算*同余關(guān)系。第59頁，共175頁，2022年，5月20日，1點51分，星期六 602022/9/256.4同余關(guān)系ababcdcda=ac=caba*cb*dcda*c=a*c第60頁，共175頁，2022年，5月20日，1點51分，星期六 612022/9/256.4同余關(guān)系【例題1】 設(shè)+是整數(shù)集合I上的普通加法運算，是I上的模k (kI+)相等關(guān)系，問在運算+上是否是I上的同余關(guān)系？分析：任意a,b和c,d有： ab(mod k) 其實就是a-b=n*k

32、 cd(mod k) 其實就是c-d=m*k那么(a+c)-(b+d)=(m+n)*k，即(a+c) (b+d)(mod k)第61頁，共175頁，2022年，5月20日，1點51分，星期六 622022/9/256.4同余關(guān)系【例題2】 設(shè)是集合I上的一元運算，任取aI, a=a2,是I上的模k (kI)相等關(guān)系，問在運算是否是I上的同余關(guān)系？ 是否是代數(shù)系統(tǒng)A上A的同余關(guān)系？分析：ab(mod k) 就相當(dāng)于(a-b)=n*k a -b=(a+b)(a-b)=(a+b)*n*k，即a b整數(shù)m第62頁，共175頁，2022年，5月20日，1點51分，星期六 632022/9/256.4同余

33、關(guān)系代數(shù)系統(tǒng)上的同余關(guān)系： 設(shè)A=是一個代數(shù)系統(tǒng)，是載體S上的等價關(guān)系，若在A上的所有運算下都是可保持的，則稱為代數(shù)系統(tǒng)A上的同余關(guān)系。第63頁，共175頁，2022年，5月20日，1點51分，星期六 642022/9/256.4同余關(guān)系定理 設(shè)g是從代數(shù)系統(tǒng)A=到A=的一個同態(tài)映射，那么由g誘導(dǎo)的S上的等價關(guān)系是代數(shù)系統(tǒng)A上同余關(guān)系。證明：由函數(shù)g誘導(dǎo)的S上的等價關(guān)系為：任取a,bS,ab當(dāng)且僅當(dāng)g(a)=g(b)。(i)若ab,則g(a)=g(b), g(a) = g(b)。第64頁，共175頁，2022年，5月20日，1點51分，星期六 652022/9/256.4同余關(guān)系又g是從A到A

34、的同態(tài)映射，所以有 g(a)=g(a)= g(b)=g(b)故a b，這說明在運算下是可保持的。(ii)若ab且cd,且有g(shù)(a)=g(b),g(c)=g(d),所以g(a)*g(c)=g(b)*g(d),又因g是從A到A的同態(tài)映射，所以有g(shù)(a)*g(c)=g(a*c)=g(b)*g(d)=g(b*d)故a*cb*d,這說明等價關(guān)系在運算*下是可保持的。由(i)(ii)可得，是代數(shù)系統(tǒng)A上的同余關(guān)系。第65頁，共175頁，2022年，5月20日，1點51分，星期六 662022/9/256.4同余關(guān)系運算上的同余關(guān)系：等價關(guān)系在運算下的可保持性是指參與運算的對應(yīng)元素，如果在同一個等價類中，則

35、運算后所得的結(jié)果也必在同一個等價類中。代數(shù)系統(tǒng)上的同余關(guān)系：等價關(guān)系R如果在一個代數(shù)系統(tǒng)中的所有運算下都是可保持的，則R是A上的同余關(guān)系。同余關(guān)系使得元素所在的等價類在運算上可以作為一個整體來看待。第66頁，共175頁，2022年，5月20日，1點51分，星期六 672022/9/256.5商代數(shù)商代數(shù)定義: 設(shè)A=是一個代數(shù)系統(tǒng)，是A上的同余關(guān)系，A關(guān)于的商代數(shù)A/=。其中 a=a a*b=a*b注意：S/是集合的集合，即等價類的集合， 形如：a, b, *, 是集合之間的運算 k是代數(shù)常元的集合 第67頁，共175頁，2022年，5月20日，1點51分，星期六 682022/9/256.5

36、商代數(shù)【例題】 代數(shù)系統(tǒng)A=，其中S=a1,a2,a3,a4,a5,一元運算和由下表所示的運算表定義。又S上的等價關(guān)系R產(chǎn)生的S上的劃分 = a1,a3,a2,a5,a4 (a)證明：R是A上的同余關(guān)系。 (b)給出A/R。a1 a2 a3 a4 a5 a4 a3 a4 a2 a1a3 a2 a1 a3 a5第68頁，共175頁，2022年，5月20日，1點51分，星期六 692022/9/256.5小結(jié)商代數(shù)：由等價關(guān)系R可以得到代數(shù)系統(tǒng)A的載體的一個劃分，以這個劃分為新的載體，按照原運算的規(guī)則建立等價類之間新的運算，這樣得到的代數(shù)系統(tǒng)是原代數(shù)系統(tǒng)的商代數(shù)。第69頁，共175頁，2022年，

37、5月20日，1點51分，星期六 702022/9/256.6半群和獨異點半群：一個代數(shù)系統(tǒng)，其中S是非空集合，*是S上一個二元運算，如果滿足：運算*是封閉的；運算*是可結(jié)合的，即任取x,y,zS,有 (x*y)*z=x*(y*z)則稱為半群。第70頁，共175頁，2022年，5月20日，1點51分，星期六 712022/9/256.6半群與獨異點【例題1】 設(shè)集合Sk=x| xI, xk,其中I是整數(shù)集合，kI,且k 1,+是普通加法運算。證明是一個半群。 證明：因為+運算在Sk上封閉的和可結(jié)合的，所以是半群。 考慮：如果k 0呢？如果k -1呢？第71頁，共175頁，2022年，5月20日，

38、1點51分，星期六 722022/9/256.6半群與獨異點【例題2】 設(shè)I+是正整數(shù)集合，R是實數(shù)集合，R+和R-分別表示正實數(shù)和負(fù)實數(shù)集合。問、和都是半群嗎？為什么？ 解答： 滿足半群的定義，它是半群。 、 、 的運算不封閉，因此均不是半群。第72頁，共175頁，2022年，5月20日，1點51分，星期六 732022/9/256.6半群與獨異點定理設(shè)是一個半群，T S且*在T上是封閉的，那么是的子代數(shù)，也是一個半群，稱為的子半群。獨異點：含有幺元的半群。 由于結(jié)合律在子代數(shù)上是可繼承的，因此半群的子代數(shù)也是半群。第73頁，共175頁，2022年，5月20日，1點51分，星期六 74202

39、2/9/256.6半群與獨異點【例題3】判斷以下代數(shù)系統(tǒng)是否是獨異點。(a);(b)。解答：(a)是半群，但不是獨異點，因為不含有幺元0。 (b)是半群，因為含有幺元0，所以它也是獨異點。第74頁，共175頁，2022年，5月20日，1點51分，星期六 752022/9/256.6半群與獨異點【例題4】 設(shè)A=0,1,2,3,+4和4分別是模4加法和模4乘法，其運算表分別如下頁(a)、(b)所示，即任意a,bA有 a +4 b=(a + b) (mod 4) a4 b=(ab) (mod 4) (a)和是獨異點嗎?為什么? (b) A中的元素在運算+4 和4上有逆元嗎?第75頁，共175頁，2

40、022年，5月20日，1點51分，星期六 762022/9/256.6半群與獨異點 +40 1 2 3 01230 1 2 31 2 3 02 3 0 13 0 1 240 1 2 3 01230 0 0 00 1 2 30 2 0 20 3 2 1(a)(b)第76頁，共175頁，2022年，5月20日，1點51分，星期六 772022/9/256.6半群與獨異點子獨異點：設(shè)是一個獨異點，T S且*在T上是封閉的，那么是的子代數(shù),也是一個獨異點，稱為的子獨異點。原代數(shù)系統(tǒng)的子代數(shù)本身是獨異點在相同運算下，幺元相同第77頁，共175頁，2022年，5月20日，1點51分，星期六 782022/

41、9/256.6半群與獨異點【例題5】設(shè)N10=0,1,2,3,9,10是模10乘法運算，則是一個獨異點，(a)寫出10的運算表；(b)取N10的一個子集A=0,2,4,6,8,證明是一個獨異點，但不是的子獨異點；(c)構(gòu)造的一個含有5個元素的子獨異點。第78頁，共175頁，2022年，5月20日，1點51分，星期六 792022/9/256.6半群與獨異點交換半群（獨異點）：在半群（獨異點）中，若二元運算是可交換的，則稱該半群（獨異點）為交換半群（獨異點）。 注：概念只作了解。第79頁，共175頁，2022年，5月20日，1點51分，星期六 802022/9/256.6半群和獨異點的性質(zhì)定理設(shè)

42、是一個半群，如果S是一個有限集，則必存在aS,使得a*a=a。證明：設(shè)|S|=n,因為是半群，任取bS,由運算*的封閉性以及S為有限集知 b, b*b=b2, b*b*b=b3,bn,bn+1S根據(jù)抽屜原理，必有兩個元素相等,不妨設(shè)為bi=bj(其中ji)。n+1第80頁，共175頁，2022年，5月20日，1點51分，星期六 812022/9/256.6半群與獨異點的性質(zhì)令p=j-i,顯然有p1。由此可得bi=bj=bp+i=bp*bi。 bi = bp*bi bi+1 = bp*bi+1 bkp = bp*bkp又由bkp = bp * bkp知 bkp=b(k+1)p b(k+1)p=

43、b(k+2)p . b(2k-1)p= b2kp因此有 bkp b2kp bkp * bkp令a= bkp，則有a=a*a，證畢。第81頁，共175頁，2022年，5月20日，1點51分，星期六 822022/9/256.6半群與獨異點【思考題】 設(shè)是一個獨異點，*的運算表中可能出現(xiàn)兩行或兩列完全相同嗎？解答：不可能。設(shè)S中關(guān)于運算*的幺元是e。任取a,bS,若ab,則有 e*a e*b (任何兩列不同) a*e b*e (任何兩行不同)所以運算*的運算表中任何兩行和兩列都是不同的。第82頁，共175頁，2022年，5月20日，1點51分，星期六 832022/9/256.6半群與獨異點循環(huán)獨

44、異點：設(shè)是一個獨異點，若存在一個元素gS,對于S中的每一個元素a,都有一個對應(yīng)的kN使得a=gk，則稱此獨異點為循環(huán)獨異點。g稱為此循環(huán)獨異點的生成元。第83頁，共175頁，2022年，5月20日，1點51分，星期六 842022/9/256.6半群與獨異點【例題6】 判斷以下代數(shù)系統(tǒng)是否是循環(huán)獨異點，若是，指出生成元。(a);(b),*的運算表如下表所示。*a b c dabcda b c db a d cc d b ad c a b第84頁，共175頁，2022年，5月20日，1點51分，星期六 852022/9/256.6本節(jié)小結(jié)半群半群定義：封閉、可結(jié)合子半群：子集、封閉，子代數(shù)，子半

45、群半群性質(zhì)：有限半群中必有等冪元交換半群：可交換第85頁，共175頁，2022年，5月20日，1點51分，星期六 862022/9/256.6本節(jié)小結(jié)獨異點獨異點定義：含幺元半群子獨異點：子集、封閉、含有幺元e，子代數(shù)交換獨異點：可交換循環(huán)獨異點：有一個生成元g,每個元素都可以用gk表示第86頁，共175頁，2022年，5月20日，1點51分，星期六 872022/9/256.7群群：設(shè)是一個代數(shù)系統(tǒng)，其中G是非空集合，*是G上一個二元運算。如果滿足運算*是封閉的，運算*是可結(jié)合的，存在幺元e，對于每一個元素xG,都存在逆元x-1G， 則稱是一個群。半群獨異點群半群獨異點群第87頁，共175頁

46、，2022年，5月20日，1點51分，星期六 882022/9/256.7群【例題1】判斷以下代數(shù)系統(tǒng)是否是群？(a),I是整數(shù)集合，+是普通加法運算。(b),Q是有理數(shù)集合，是普通乘法運算。(c)，I是整數(shù)集合，是普通乘法運算。(d),運算*如下表所示。* a b cabc a b c b c a c a b第88頁，共175頁，2022年，5月20日，1點51分，星期六 892022/9/256.7群【例題2】設(shè)有代數(shù)系統(tǒng)，其中I是整數(shù)集合，運算的定義為，對任意a,bI,有 a b=a+b-2試問是否是群？解答：(i)對任意a,b I, a b I,所以運算在I上是封閉的。第89頁，共17

47、5頁，2022年，5月20日，1點51分，星期六 902022/9/256.7群(ii)對任意的a,b,c I,有 (a b) c=(a+b-2) c=(a+b-2)+c-2=a+b+c-4 a (b c)=a+(b c)-2=a+(b+c-2)-2=a+b+c-4所以運算滿足結(jié)合律。(iii)任取aI, ae=a+e-2=a,得到e=2,所以2是幺元。(iv)任取aI, aa-1=a+a-1-2=2,得到a-1=4-aI,因此I中每個元素都有逆元。由以上可知是一個群。第90頁，共175頁，2022年，5月20日，1點51分，星期六 912022/9/256.7群有限群：設(shè)是一個群，如果G是有

48、限集，則稱為有限群。無限群：設(shè)是一個群，如果G是無限集，則稱為無限群。群的階數(shù)：有限群的載體G的基數(shù)|G|，稱為群的階。第91頁，共175頁，2022年，5月20日，1點51分，星期六 922022/9/256.7群的性質(zhì)性質(zhì)一：群中無零元。 說明：當(dāng)群中只有一個元素的時候，一般的把它看作幺元，如果它是零元的話，它就不符合群的定義了。因為零元沒有逆元，零元與任何元素進行操作結(jié)果都是零元。如果群中有零元，則不符合群的定義了(任何一個元素都有逆元)。第92頁，共175頁，2022年，5月20日，1點51分，星期六 932022/9/256.7群的性質(zhì)性質(zhì)二：群中每個元素的逆元都是唯一的。 說明：前

49、面我們學(xué)過一個定理6.1-3，對于可結(jié)合運算，如果一個元素x有左逆元l和右逆元r,那么l=r（即逆元是唯一的）。假設(shè)群中的元素a有兩個逆元c,d，c=c*e=c*(a*d)=(c*a)*d=e*d=d第93頁，共175頁，2022年，5月20日，1點51分，星期六 942022/9/256.7群的性質(zhì)性質(zhì)三：設(shè)是一個群，對于a,bG,必存在唯一的xG,使得a*x=b。證明：設(shè)a的逆元是a-1,令 x=a-1*b 則 a*x=a*(a-1*b) =(a*a-1)*b =e*b=b 第94頁，共175頁，2022年，5月20日，1點51分，星期六 952022/9/256.7群的性質(zhì)若另一解x1,

50、滿足a*x1=b，則 a-1*(a*x1)=a-1*b x1=a-1*b故結(jié)論得證。第95頁，共175頁，2022年，5月20日，1點51分，星期六 962022/9/256.7群的性質(zhì)性質(zhì)四：設(shè)是一個群，對于任意a,b,cG,若有a*b=a*c或者b*a=c*a,則必有b=c。證明：a*b=a*c且a的逆元是a-1,則有 a-1*(a*b)=a-1*(a*c)即有b=c。同理，當(dāng)b*a=c*a,也有b=c。第96頁，共175頁，2022年，5月20日，1點51分，星期六 972022/9/256.7群的性質(zhì)性質(zhì)五：設(shè)是一個群，除幺元e外，不可能有任何別的等冪元。證明：因為e*e=e,所以e是

51、等冪元。 設(shè)xG,且x*x=x，則有 x=e*x=(x-1*x)*x=x-1*(x*x)=x-1*x=e故可以得到除幺元e外，不可能有任何別的等冪元。第97頁，共175頁，2022年，5月20日，1點51分，星期六 982022/9/256.7群的性質(zhì)性質(zhì)六：群的運算表中的每一行或每一列都是G中元素的一個置換。證明：(i)證明G中的每個元素在運算表的每一行和每一列均出現(xiàn)。任取一個元素aG,考察a對應(yīng)的行，設(shè)b是G中任一元素，b=a*(a-1*b),而a-1*bG,所以b必定出現(xiàn)在a對應(yīng)的那一行中。第98頁，共175頁，2022年，5月20日，1點51分，星期六 992022/9/256.7群的

52、性質(zhì)(ii)證明G中的每個元素在運算表中的每一行和每一列出現(xiàn)的次數(shù)不可能多于一次。（反證法）設(shè)對應(yīng)于aG的那一行有兩個元素b出現(xiàn)，即a*c=a*c=b,且cc。 這與群的運算*是可消去的矛盾。 再者，由運算表中沒有兩行（或兩列）相同的事實，便可得的運算表中每一行都是G的元素的一個置換，且每一行都是不相同的。同樣的結(jié)論對列也是成立的。第99頁，共175頁，2022年，5月20日，1點51分，星期六 1002022/9/256.7群一階群一個(見(a)表)、二階群一個(見(b)表)、三階群一個(見(c)表)*eee* e a ea e a a e* e a beab e a b a b e b e

53、 a(a)(b)(c)第100頁，共175頁，2022年，5月20日，1點51分，星期六 1012022/9/256.7群四階群有兩個(見(d1)(d2)表) 。* e a b ceabc e a b c a b c e b c e a c e a b* e a b ceabc e a b c a e c b b c e a c b a e(d1)(d2)第101頁，共175頁，2022年，5月20日，1點51分，星期六 1022022/9/256.7群五階群僅有一個(見表(e)* e a b c deabcd e a b c d a b c d e b c d e a c d e a b d

54、 e a b c(e)第102頁，共175頁，2022年，5月20日，1點51分，星期六 1032022/9/256.7群群中元素的階：對于群，由于*運算是可結(jié)合的，定義a0=e,當(dāng)n為大于0的正整數(shù)時，有 an = a * a * * a對于任意整數(shù)i , j,有(1)ai * aj = ai+j；(2) (ai)j=aijn個第103頁，共175頁，2022年，5月20日，1點51分，星期六 1042022/9/256.7群群中元素的階： 設(shè)是一個群，e是幺元，aG。若存在一個使an=e成立的最小正整數(shù)n,則稱n為元素a的階(或周期)；否則，稱元素a的階是無限的。群中元素的階是使該元素的冪

55、為幺元的最小正整數(shù)第104頁，共175頁，2022年，5月20日，1點51分，星期六 1052022/9/256.7群定理有限群中任何一個元素的階至多是|G|。證明：設(shè)aG,設(shè)a的階為k, k|G|, a, a*a, a*a*a, , a*a*a*aG 因為G中元素的個數(shù)為|G|k, 因此在a1,a2,a3,ak中必有兩個元素ai=aj，那么aj-i = e, 而j-ik,與假設(shè)k是a的階相矛盾，因此假設(shè)錯誤，原結(jié)論正確。k個有限群中元素的階一定小于等于群的階。第105頁，共175頁，2022年，5月20日，1點51分，星期六 1062022/9/256.7群定理群中任何一個元素與它的逆元具有

56、相同的階。證明：設(shè)是群，任取aG。(i)設(shè)a的階為k,即ak=e,則(a-1)k = (ak)-1= e-1 =e。(ii)由(i),不妨設(shè)jk,使(a-1)j=e,則(aj)-1=e,兩邊同時取逆，可得aj=e-1=e,這與a的階是k相矛盾。故由(i)、(ii)可得，a與a-1的階相同。第106頁，共175頁，2022年，5月20日，1點51分，星期六 1072022/9/256.7群的基本概念和性質(zhì)小結(jié)群的定義：封閉、可結(jié)合、含幺元、每一個元素有逆元。群的六個性質(zhì)：群中無零元逆元唯一a*x=b消去律幺元是唯一的等冪元每一行每一列都是群中元素的一個置換第107頁，共175頁，2022年，5月

57、20日，1點51分，星期六 1082022/9/256.7群的基本概念和性質(zhì)小結(jié)群的階群中元素的階有限群中元素的階一定小于等于群的階群中每個元素與其逆元具有相同的階第108頁，共175頁，2022年，5月20日，1點51分，星期六 1092022/9/256.7子群和群同態(tài)子群：設(shè)是一個群，S是G的非空子集，若也構(gòu)成群，則稱是的子群。平凡子群：和是的平凡子群。【思考】中的幺元，一定是它的子群中的幺元嗎？第109頁，共175頁，2022年，5月20日，1點51分，星期六 1102022/9/256.7子群和群同態(tài)定理設(shè)是一個群，是的一個子群，那么中的幺元e必是中的幺元。證明：是群，設(shè)其幺元為e,

58、任取xS,則有xG, e * x = x = e * x根據(jù)群滿足消去律可得e = e。第110頁，共175頁，2022年，5月20日，1點51分，星期六 1112022/9/256.7子群與群同態(tài)【例題1】設(shè)I是整數(shù)集合，是一個群，IE=x | x=2n,nI，問是的子群嗎？解答：(i)IE I;(ii)運算+在IE是封閉的；(iii)運算+在IE上是可結(jié)合的；(iv)中的幺元0也是中的幺元；(v)任取xIE, x-1 = -x, -xIE。所以是的子群。第111頁，共175頁，2022年，5月20日，1點51分，星期六 1122022/9/256.7子群的判定定理設(shè)是一個群，S是G的非空子

59、集，若運算*在S上封閉，并且S中的每個元素都有逆元，則是的子群。證明: (i)運算*的可結(jié)合性在S上是可保持的。(ii)任取aS，因為a-1 S,而且*在S上是封閉的，故e = a * a-1 S。所以是的子群。第112頁，共175頁，2022年，5月20日，1點51分，星期六 1132022/9/256.7子群的判定定理設(shè)是一個群，S是G的非空子集，如果S是有限集，那么只要運算*在S上封閉，是的子群。證明：設(shè)e是的幺元，令|S|=n, aS,因為運算*在S上封閉，則有 a, a*a=a2, a*a*a=a3,an,an+1 S根據(jù)抽屜原理，必存在ai=aj 其中1i,j n+1,不妨設(shè)ji。n+1第113頁，共175頁，2022年，5月20日，1點51分，星期六 1142022/9/256.7子群的判定(i) 因為ai, ajG, 則(ai)-1=a-iG, 因此aj-i=a0=eS(ii) 因為j - i 1, a-1=aj-i-1,而nj-i-10 ,因此a-1S。因此S中的每個元素都有逆元。(iii)結(jié)合律是可繼承的。綜上所述，是的子群。第114頁，共175頁，2022年