離散數學第4章

1、1,,第四章 代數系統(tǒng)(algebra system) §1.代數系統(tǒng)的基本概念　　　　 §2.代數系統(tǒng)的同態(tài)和同構　　　　 §3.半群與單子 　　　　 §4.群 §5.環(huán) §6.域　　　　 §7.同余關系,2,§1.代數系統(tǒng)

2、的基本概念 ?代數系統(tǒng) ?代數系統(tǒng)的基本性質 ?子代數系統(tǒng),3,,§1.代數系統(tǒng)的基本概念定義1.代數系統(tǒng)　代數結構(algebra structure) 一個代數系統(tǒng)(代數結構，簡稱代數)A是如下的一個有序元組： A=(X,O1 , O2 ,?, Om , R1 , R2 ,?, Rn , c1 , c2 ,?, cl )其中:

3、 (1)X??是一個任意集合,稱為母集或承載子(carrier)； (2)O1 , O2 ,?, Om是X上的m個運算(m?1) ； (3)R1 , R2 ,?, Rn是X上的n個(序)關系(n?0) ； (4)c1 , c2 ,?, cl ?X是X中的l個特殊元素(l?0),稱為常項(constants)。注：?當X是有限集合時，稱A為有限代數系統(tǒng)； 　 ?當X是無限集合時，稱A為無限代數系統(tǒng)； ?在一個代數

4、系統(tǒng)中運算的集合不能是空的，必須至少有一個X上的運算。代數系統(tǒng)中各個運算的元(階)數可能是不一樣的，即每個運算都有自己的運算元數。,4,,例1. (1)(I,+), (I, ?) ,(I,+,?)， (I,+, ?, ?, 0,1)都是代數系統(tǒng)。 這里：I是整數集合：+和?是整數的加法和乘法。小于等于關系?是I上的二元關系(半序)，0,1?I是I上的兩個特殊元素。例2. (?, o)是代數系統(tǒng)。這里： X={a,b}，設?={f

5、 ? f :X?X }，則 ?={f 1 , f 2 , f 3 , f 4 } 。其中： f 1 (a)=a f 2 (a)=a f 3 (a)=b f 4 (a)=b f 1 (b)=b f 2 (b)=a f 3 (b)=b f 4 (b)=a 　o運

6、算是函數的復合運算 o : ?? ? ? ? 其運算可列表如下：,表 1,5,例3. (X,* )是代數系統(tǒng)。 這里： X = { a,b,c,d }，定義運算 * : X2 ? X 如表2所示。,例5.時鐘代數(X, ?)是代數系統(tǒng)?！∵@里：X={a1 , a2 , a3 ,?, an }，定義運算 ? : X? X

7、 。,例4. (1)(2X , ? , ?)是代數系統(tǒng)。 這里X是任意非空的集合，2X是X的冪集， ?和?是集合的交和并。 (2)集合代數(2X , ? , ? , ?)是代數系統(tǒng)。這里?是集合的余。,,表 2,6,,定義2.結合律　交換律(associative law,commutative law) 設( X, ? )是任一代數系統(tǒng)， ?是X上的二元運算。則 稱 (1)?運算滿足結

8、合律 ?(?x?X)(?y?X)(?z?X)((x ? y) ? z ＝ x ? (y? z)) ； (2)?運算滿足交換律?(?x?X)(?y?X)(x? y＝ y ? x ) 。注：結合律改變的是運算的先后次序；交換律改變的是運算對象的位置順序。前者是對運算符而言；后者是對運算對象而言。例6.代數系統(tǒng)(I,+,?)中，二元運算+和?的性質。例7.代數系統(tǒng) (2X, ? , ?) 中，二元運算?和

9、?的性質。例8.代數系統(tǒng)(I,-)中，減法運算-的性質。,7,,定義3.幺元　零元(identity element,zero element) 設 (X, ? )是代數系統(tǒng)，? 是X上的二元運算， x0 ?X 。則 稱 (1)x0是關于?運算的幺元?(?x?X)(x0?x＝x?x0＝x) ； (2)x0是關于?運算的零元?(?x?X)(x0?x＝x?x0＝x0) 。注：? 通常將幺元記為 e ；含有幺元e的

10、代數系統(tǒng)(X, ? ), 通常記作(X, ? , e ) ；即　　(?x?X)(e ? x＝x ? e ＝x ) ； ? 在同時具有幺元和零元的代數系統(tǒng)中，通常將幺元記為1，將零元記為 0 ；即 (?x?X)(1 ? x＝x ? 1 ＝x ) ； (?x?X)(0 ? x＝x ? 0 ＝ 0 ) 。例9. 代數系統(tǒng) (I,+, ?) 中，關于+的幺元、?的幺元？

11、例10. 代數系統(tǒng) ( 2X,?,?) 中，關于?的幺元、?的幺元？例11.代數系統(tǒng)(I,+,?)中，關于+的零元、?的零元？例12.代數系統(tǒng)(2X,?,?,)中，關于?的零元、?的零元？,8,,定理1.幺元、零元的唯一性　 設 (X, ?) 是代數系統(tǒng)，? 是X上的二元運算。則 (1)若關于 ?運算的幺元存在，則必是唯一的； (2)若關于 ?運算的零元存在，則必是唯一的。[證].（采用邏輯法）只證幺

12、元的唯一性 e1是?運算的幺元 ? e2是?運算的幺元 ?(?x?X)(x ? e1=x )?(?x?X)(e2 ? x=x ), ?(e2 ? e1= e2)? ( e2 ? e1=e1 ) (因 e1, e2 ?X都是X的普通一元；根據普遍性 特殊化：?xA(x) ?A(y) 及

13、 合成律： (p ? q )?( r?s )? p ? r ? q ? s ) ?(e1 = e2 ? e1) ? (e2 ? e1= e2) 　　　 (交換律：p ? q ? q ? p，以及=的對稱性) ? e1 = e2 (=

14、的傳遞性) 所以，幺元是唯一的。,9,定義4.逆元　可逆性(inverse element,invertibility) 設(X,*,e)是代數系統(tǒng)，*是X上的二元運算，e是關于*運算有幺元。 (1)對于某一元素x?X, 若存在著某個元素y?X ,使得 x*y =y*x =e則稱y是x關于*運算的逆元，并稱x關于*運算是可逆的(invertible)，同時稱x是關于*運算的可逆元； (2

15、) 稱*運算在X上是可逆的　　 ?(?x?X)(?y?X)(x*y=y*x=e) ?X中的每個元素都是關于*運算的可逆元 。,10,,例13.在代數系統(tǒng)(I,+,?)中 (1)加法+的幺元是0，每個元素關于+的逆元是什么？ (2)乘法?的幺元是1，每個元素關于+的逆元是什么？例14.在代數系統(tǒng)(2X,?,?)中 (1)?的幺元是X，每個X的子集關于?的逆元是什么？ (2)?的幺元是?，每個X的

16、子集關于?的逆元是什么？定理2.逆元的唯一性 設(X，*, e)是代數系統(tǒng)，*是X上的二元運算并且滿足結合律，e是幺元。對任何元素x?X，若x的逆元存在，則必是唯一的。,11,,[證].設y1 , y2?X 都是x的逆元，則 y1=e*y1 =(y2*x)*y1 (y2是x的逆元) =y2*(x*y1) (結合律) =y2*e

17、 (y1是x的逆元) =y2 注：?對任何元素x?X，若x的逆元存在唯一，則將其逆元記 為x -1 。于是，就有 x*x -1 =x -1 *x=e ； ?若*運算不滿足結合律，則逆元未必是唯一的。,12,,例15. 設X={a,b,c,d,e,f,g}，*是X上的二元運算，*運算的運算表如下表3。 注：?因此當代數系統(tǒng)中的二元運算不滿足結合

18、律時，逆元的情況變得極為復雜；　　?結合律的驗證有時是十分困難的。上百個成員的代數，驗證結合律，其工作量即使對于一般計算機也是很困難的，有上億次的計算量。,表3,13,,定義5.消去律(cancellation law) 消去律有三種形式：　(1)設(X, ?)是代數系統(tǒng)，?是X上的二元運算。 稱 ?運算滿足消去律? a) (?x?X)(?y?X)(?z?X)(x ? y = x ? z ?

19、 y = z) b) (?x?X)(?y?X)(?z?X)(y ? x = z ? x ? y = z)； (2)設(X, ?,0)是代數系統(tǒng)，?是X上的二元運算， 0是零元。稱 ?運算滿足消去律? a) (?x?X)(?y?X)(?z?X)(x? 0?x ? y = x ? z? y = z) b) (?x?X)(?y?X)(?z?X)(x? 0?y ? x = z ?

20、x? y = z)； (3)設(X,*,?)是代數系統(tǒng)，?, ?都是X上的二元運算。 稱 ?及?運算滿足消去律? a) (?x?X)(?y?X)(?z?X) (x ? y = x ? z ? x ? y = x ? z ? y = z) b)(?x?X)(?y?X)(?z?X) (y ? x

21、 = z ? x ? y ? x = z ? x ? y = z)。,14,,例16.在代數系統(tǒng)(I,+,?)中，加法+滿足消去律(1)；乘法?不滿足消去律(1)，但滿足消去律(2) ?！±?7.在代數系統(tǒng) (2X,?,?)中， ?和?都不滿足消去律(1) ，但滿足消去律(3) 。,定義6.分配律(distributive law) 設(X,*,?)是代數系統(tǒng)，*和?是X上的兩個二元運算。 (1)稱*運算對?運算滿足分配律

22、? a) (?x?X)(?y?X)(?z?X) (x ? ( y ? z ) = ( x ? y ) ?(x ? z )) b) (?x?X)(?y?X)(?z?X) ( ( y ? z ) ? x = ( y ? x ) ?(z ? x ))； (2)稱運算?對運算*滿足分配律?

23、 a) (?x?X)(?y?X)(?z?X) (x ?( y ?z ) = ( x ? y ) ?(x ? z )) b) (?x?X)(?y?X)(?z?X) ( ( y ? z ) ? x = ( y ? x ) ?(z ? x )) 。,15,,例18.在代數系統(tǒng)

24、(I,+,?)中 (1)乘法對加法滿足分配律嗎？ (2)加法對乘法滿足分配律嗎？例19.在代數系統(tǒng)(2X,?,?)中 (1)?對?滿足分配律嗎？ (2)?對?滿足分配律嗎？定義7.反身律　鞋襪律 設(X,*,?)是代數系統(tǒng)，*是X上的二元運算，?是X上的一元運算。 (1)稱?運算滿足反身律?(?x?X)((x?)? = x) ； (2)稱?運算關于*運算滿足鞋襪律 ?(?x?X

25、)(?y?X)((x * y)? = y?*x?) 。,16,,例20.在代數系統(tǒng)(?*,o,v)中, ?*是?上字的全體集合， o是兩個字的毗連(concatenation)運算， v是一個字的逆置(倒置(inverse))運算。例如，取?={a,b},字 ?=abaaaaabbbbbb，?=abbbbaa,則有 ? o ?=abaaaaabbbbbb o abbbbaa=abaaaaabbbbbbabbbbaa

26、 ?v=bbbbbbaaaaaba 于是v運算滿足反身律： (?v)v =?　v運算關于o運算滿足鞋襪律： (? o ?)v=?v o ?v 　。注：?一個字?? ?*稱為是一個迴文(palindromes)? ?v=?　。定義8.反身律 de Morgan律 設(X,*,?,?)是代數系統(tǒng)，*和?是X上的兩個二元運算，?是X上的一元運算。 (1)稱?運算滿足反身律?(?x?X)((x?)? = x)；,1

27、7,,(2)稱?運算關于*運算和?運算滿足de Morgan律? a) (?x?X)(?y?X)((x?y)? = x??y? ) ； b) (?x?X)(?y?X)((x?y)? = x??y? ) 。例21.在代數系統(tǒng)(2X,?,?,?)中 (1)? 滿足反身律，因為 ?A?2X，有(A?)?=A (2)? 關于?和?滿足de Morgan律。定義9.子代數系統(tǒng)(subalge

28、bra system) 設A=(X,O1,O2,…,Om)是代數系統(tǒng)，其中O1,O2,…,Om是X上的m個運算，其元數分別為p1 , p2 , … , pm 。若有子集S?X且S≠?，對A中的每一個運算Oi，有其子關系Osi=Oi∩SPi ，使得Osi也是S上的Pi元運算，從而使得(S, OS1, OS2 , …, OSm )也構成一代數系統(tǒng)，則 稱此代數系統(tǒng)是A的子代數系統(tǒng)，記為　　 As=(S, O1, O2 , … ,O

29、m )　。,18,例22. X={a,b,c,d}，S1={a,b}，S2={c,d}是X的兩個子集， (S1,*1)是(X,*)的子代數系統(tǒng)？ (S2,*2)是(X,*)的子代數系統(tǒng)？,,表4,表5,表6,19,例23. (N,+, ?)、(I, +, ?)、(Q, +, ?)都是(R, +, ?)的子代數系統(tǒng)嗎？例24. 在代數系統(tǒng) (I, +, ?)中，取I的兩個子集如下： E={x:x是偶數}，O={y:

30、y是奇數} (E, +, ?)是(I, +, ?)的子代數系統(tǒng)嗎？　 (O, +, ?)能構成(I, +, ?)的子代數系統(tǒng)嗎？,定理3.遺傳性定理 設(X，*)是代數系統(tǒng)，*是X上的二元運算。(S，*)是(X，*)的子代數系統(tǒng)。則 (1)*運算在X上有結合律? *運算在S上有結合律； (2)*運算在X上有交換律? *運算在S上有交換律。[證].只證(1) 對于任何元素a,b,c?S ，由于S?X ，

31、所以a,b,c?X 。而*運算在X上有結合律，因此有 (a*b)*c=a*(b*c)?！?由于(S，*)是(X，*)的子代數系統(tǒng)，*運算關于S封閉， (a*b)* c, a*(b*c)?S ，因此上述等式在S上也是成立的。這說明*運算在S上也有結合律。,20,,§2.代數系統(tǒng)的同態(tài)和同構 ?代數系統(tǒng)間的同態(tài) ?代數系統(tǒng)間的同構關系,21,,例1. (2A,?)是代數系統(tǒng)。

32、這里A={a}，?是2A上的并運算。例2. ( B,?)是代數系統(tǒng)。這里B={0,1}，?是B上的或運算 。定義1.同類型(same type) 稱兩個代數系統(tǒng) A=(X,O1,O2,···,Om)和B= (Y, , ,···, )是同類型的代數系統(tǒng)? (1) m = n； (2)Oi運算和相對應的

33、 運算的元數相同 ( i= 1, ···,m )。例3. (I, +,?) 和(2X, ?, ?)是兩個同類型的代數系統(tǒng)。例4. (2X, ?, ?,?) 和(B, *,?,-)是兩個同類型的代數系統(tǒng) 。,§2.代數系統(tǒng)的同態(tài)和同構,22,定義2.同態(tài)(homomorphism) 稱兩個同類型的代數系統(tǒng) A=(X,O1,O2,···

34、,Om)和B= (Y, , ,···, )是同態(tài)的?存在著一個函數 h：X→Y 使得： 對任何一對運算Oi和 ( i= 1, ···,m ) (其元數為pi ) ，都滿足如下的同態(tài)公式： ?(x1,x2,…,xpi )?Xpi h (Oi(x1,x2,…,xpi ))= (h(

35、x1),h(x2),…,h(xpi)) ① 注：? 稱函數 h 是保持運算的；并稱函數 h 為從A到B的同態(tài)函數，記為h：A~B ；稱兩代數系統(tǒng)A與B同態(tài)，記為A ~ B ； ? h對Oi和 保持運算的含義是指在 h 的作用下，元素運算結果的象等于元素象

36、的運算結果。,,23,,定義3.同態(tài)象 單同態(tài) 滿同態(tài) 設代數系統(tǒng)A=(X,O1,O2,···,Om)同態(tài)于代數系統(tǒng)B= (Y, , ,···, )，其同態(tài)函數為 h：X→Y 。 (1)稱X在h下的象集h(X)?Y與B的所有運算一起組成的 C= (h(X), , ,···, )是

37、A的同態(tài)象；　(2)若h是單射函數，則稱h是從A到B的單同態(tài)函數并,24,,稱C為A的單同態(tài)象； 　(3)若h是滿射函數，則稱h是從A到B的滿同態(tài)函數；并稱 B為A的滿同態(tài)象(這時有h(X)=Y ,C=B) 。例5.代數系統(tǒng)(N, +)與代數系統(tǒng)(Nm , +m )是滿同態(tài)的?！m={[0]m , [1]m ,…,[m－1]m}，二元運算+m定義如下： ?[i]m,[j]m ? Nm , [ i ]m+

38、m [ j ]m = [(i+j)mod m]m。例6.代數系統(tǒng)(N,+)與代數系統(tǒng)(X,?)是滿同態(tài)的?！∵@里N是自然數集合,＋是自然數加法。 X={1, -1}，?是整數乘法，其運算表如下：,25,,定理1. 設代數系統(tǒng)A=(X,O1,O2,···,Om)同態(tài)于代數系統(tǒng)B= (Y, , ,···, )，其同態(tài)函數為 h：X→Y 。則A的

39、同態(tài)象C= (h(X), , ,···, )是B的子代數系統(tǒng)。[證].只須證B的每個運算　　　　　　 (設其元數為pi )在h(X)上都是封閉的即可。　對于任何元素y1 , y2 ,? ,ypi ?h(X)，由于h(X)是X的象集，故存在著其原象x1 , x2 ,? ,xpi ?X，使得　 h(x1)= y1 , h(x2)= y2 , ?,h(xpi)= ypi 于是

40、　 　 (y1 , y2 , ?, ypi) = (h(x1) ,h(x2), ?, h(xpi)) =h(Oi(x1,x2, ?, xpi)) 　 (同態(tài)公式) =h(x) (Oi運算在X上是封閉的，故可設 Oi(x1

41、,x2, ?, xpi)=x?X ) ?h(X)　所以該運算是封閉的；于是由子代數系統(tǒng)的定義可知A的同態(tài)象C是B的子代數系統(tǒng)。,26,,定理2.同態(tài)遺傳定理　設(X，?)和(Y，o) 是兩個代數系統(tǒng)，? 和 o 分別是X和Y上的二元運算，h 是從(X，? )到(Y，o )的滿同態(tài)函數，那么： (1)?運算滿足結合律? o運算滿足結合律； (2)?運算滿足交換律? o運算滿足交換律；

42、 (3)e是關于?運算的幺元? h(e) 是關于o運算的幺元； (4)0是關于?運算的零元? h(0) 是關于o運算的零元； (5)x關于 ?運算有逆元x -1 ? h(x) 關于o運算的逆元是 h(x －1), 即 [h(x) ]-1 = h(x -1 ) 。注：(1)定義遺傳：例如， 定義x? y=max(x , y), x? y=min(x , y)則求大，求小的對稱性就轉變?yōu)檫\算?和?的交

43、換律；又例如，當 定義　[ i ]m+m [ j ]m = [(i+j)mod m]m時，自然數加法的結合律、交換律實際上已自動遺傳給運算+m了；　(2)子代數遺傳(參見§1定理3) ；　(3)同態(tài)遺傳(即本定理) ；,27,,[證].只證(1), (3), (5), (1)對于任何元素y1 , y2 ,y3?Y，由于h是滿射，故存在著其原象x1 , x2 ,x3 ?X，使得　　h(x1)= y1 , h(

44、x2)= y2 , h(x3)= y3 ,于是 (y1 o y2 )o y3 =(h(x1)oh(x2))oh(x3) = h(x1 ? x2)oh(x3)　　　 (同態(tài)公式) = h((x1? x2)?x3) 　　　 (同態(tài)公式) = h(x1 ?(x2 ? x3)) (?運算的結合律) = h(x1)o h(x2 ? x3) 　　 (同態(tài)公式) = h(x1)o

45、(h(x2)o h(x3)) (同態(tài)公式)　 = y1 o( y2 o y3) 　所以o運算滿足結合律；,28,,(3)令e? =h(e)?Y。對于任何元素y?Y，由于h是滿射，故存在著其原象x?X，使得　　h(x)= y ，于是　　 e? o y = h(e)o h(x) = h(e ? x)　　　 (同態(tài)公式) = h(x) 　　　 (e是關于?運算的幺元) = y = h(x)

46、 = h(x? e ) 　　 (e是關于?運算的幺元) = h(x)oh(e) 　(同態(tài)公式)　 = y o e? 　即 e? o y = y o e? = y ，所以e? =h(e)是關于o運算的幺元；,29,,(5)令e? =h(e)?Y。對于任何元素x?X， 由于存在著其逆元x -1?X，故此 h(x), h(x -1)?Y，于是有 h(x)o h(x -1) = h(x? x

47、-1)　　　 (同態(tài)公式) = h(e) 　　　 　( x -1 是x關于 ? 運算的逆元) =e? = h(e) = h(x -1 ? x ) 　　 (x -1 是x關于 ? 運算的逆元) = h(x -1)oh(x) 　 (同態(tài)公式)　 即 　h(x)o h(x -1)= h(x -1)oh(x)=e? 　所以h(x

48、)關于o運算的逆元是h(x -1) ,即 [h(x) ]-1 = h(x -1 ) 。,30,,定義4.同構(isomorphism) 設代數系統(tǒng)A=(X,O1,O2,···,Om)同態(tài)于代數系統(tǒng)B= (Y, , ,···, )，其同態(tài)函數為 h：X→Y 。若h還是雙射函數，則稱h是從A到B的同構函數,記為h：A

49、 B ；并且這時 稱A和B同構,記為A B 。注：?同態(tài)和同構概念要求兩個代數系統(tǒng)必須是同類型的。　 ?同構概念要求兩個集合必須是等勢的(即 　 　　　　　 )。 ?同構概念是雙向的、相互的、可逆的。 ?同態(tài)概念是單方向的、不可逆的。例7.集合代數(2X,? ,? ,? ,? ,?,X)與布爾代數(B, *,?,- , ,0,1)是同構的 這里：X={a1, a2, ?,an},B=

50、{S:S= ?C?X }。,31,,例8.集合代數(2X, ?, ?,? ,?,X)與布爾代數(B, ?, ?, ?,0,1)是同構的。 這里X={a}, 2X ={?,X},B={0,1}，其運算表如下： 構造自然映射　h：2X →B　使得 h(?)=0, h(X)=1，則容易驗證h是同構函數。,表4,表5,表6,表7,表8,表9,32,,同時 h –1：B → 2

51、X h–1(0)= ? , h–1(1)= X。　 h –1 是從(B, ?, ?, ?,0,1)到(2X, ?, ?,? ,?,X)的同構函數，即(B, ?, ?, ?,0,1)與(2X, ?, ?,? ,?,X)同構。 例9. (N, +)和(E, +)同構。 取函數 h：N →E，h(i)=2i (?i?N ) 。例10.(R, +)和(R+,?)同構。 取函數 h：R → R

52、+ ，h(?)= e?。,33,定理3.代數系統(tǒng)間的同構關系 是X上的等價關系。其中：X={A:A是代數系統(tǒng)}。[證].(以下都以僅含一個二元運算的代數系統(tǒng)為例)　由等價關系的定義知要證 是 (1)自反的：這點可由幺函數來保證； 對于任何代數系統(tǒng)A=(X,*),有幺函數　　　 I:X →X 使得 ?a?X , I(a)=a 。 幺函數是雙射函數； ?a,b?X ,I(a *

53、b)=a*b=I(a)*I(b),滿足同態(tài)公式； 故I：A A ；故A A 。,,34,,(2)對稱的：這點可由逆函數來保證； 對于任何兩個代數系統(tǒng)A=(X,*), B=(Y, ?), 若有A B，則有同構函數h：A B ?！　亩鴋：X→Y ； h是雙射函數； h滿足同態(tài)公式：?a,b?X ,h(a * b)=h(a)?h(b) ；　 于是有逆函數h

54、 -1存在 h -1 ：Y→X ； h -1是雙射函數(參見第三章§1定理1)； 并且對任何元素c,d?Y,都存在著a,b?X ,使得h(a)=c， h(b)=d ，從而h -1(c)=a， h -1(d)=b ，于是有 h -1(c?d) = h -1(h(a)?h(b)),35,,= h -1(h (a * b)) (h滿足

55、同態(tài)公式) =( h -1oh )(a * b) =I(a * b) (h -1是h的逆函數) =a * b = h -1(c)*h -1(d)　 所以h -1滿足同態(tài)公式；　 所以h -1 ：B A ；所以 B A ； (3)傳遞的：這點可由復合函數來保證。 對于任何三個代數系統(tǒng)A=(X,*), B=

56、(Y, ?),以及C=(Z,?),若有A B，且 B C，則有同構函數： h：A B ， g：B C 。 　　從而有函數h：X→Y ， g：Y→Z ， 　　h,g都是雙射函數；,36,,h ,g都滿足同態(tài)公式： ?a,b?X ,h(a * b)=h(a)?h(b) 　 ?c,d?Y ,g(c?d)=g(c)?g(d) ； 于是有復合函數

57、goh ：X→Z， goh是雙射函數(參見第三章§2定理1)； 并且對任何元素a,b?X , 有　　 (goh )(a * b) = g(h(a * b)) = g(h(a)?h(b)) (h滿足同態(tài)公式) = g(h(a))?g(h(b)) (g滿足同態(tài)公式) =(goh )(a

58、)?(goh )(b) 所以goh滿足同態(tài)公式；　 所以goh ：A C ；所以 A C 　。,37,,§3.半群與單子 ?半群的基本概念　 ?交換半群與含幺半群(單子) ?循環(huán)半群 ?子半群,38,,§3.半群與單子定義1.半群(semigrop)

59、 設(X, ?)是代數系統(tǒng)，? 是X上的二元運算。若 ?運算滿足結合律，則稱(X, ? )為半群。注：?半群就是具有結合律的代數系統(tǒng)；　　?驗證半群的要點是驗證運算的(1)封閉性；(2)結合律。例1. (I,?)是半群?！∵@里：I 是整數集合， ?是整數乘法。由§1的例1. (1) 已知(I,?)是代數系統(tǒng)； 由算術知識知整數乘法?滿足結合律，即?a,b,c?I ， (a?b)?c= a?(b

60、?c) ； 由半群的定義知(I,?)是半群。,39,,例2. (Mn ? n , ?)是半群。 這里： Mn ? n是n 階實(方)矩陣的全體， ?是矩陣乘法。 例3. (2X, ?)是半群。 這里： X 為非空集合，2X是 X 的冪集， ?是2X上的集合交運算。例4.(Nm , ?m)是半群。 這里： Nm={[0]m，[1]m，…，[m－1]m}， ?m定義如下 ? [ i ]m，[ j

61、]m ?Nm ， [ i ]m ?m [ j ]m = [( i ? j ) mod m]m。例5. (P[x], ?)是半群。這里： P[x] 是實系數多項式的全體， ?是多項式的乘法。,40,,例6. (XX, o)是半群(參見§1例2) 這里：X={a,b}，XX={f ? f :X? X }= ? ，則　由§1例2 已知(XX, o)是代數系統(tǒng)；

62、 由第三章函數§2.函數的復合知函數的復合運算o滿足結合律； 由半群的定義知(XX, o)是半群，這里 ?x?X，(fi o fj) ( x )= fi ( fj ( x ) ) 。,41,,定義2.單子(monoid)。 設(X ，?)是半群。 (1)若?運算滿足交換律，則稱(X ，?)是交換半群。 (2)若X關于?運算有幺元，則稱(X ，?)是含幺半群或者單子?！?3)若?運算滿

63、足交換律同時X關于?運算又有幺元，則稱(X ，?)是交換含幺半群或交換單子。,例7. (I，?)是交換含幺半群嗎？幺元是什么？ (Mn?n，?)是交換半群嗎？是含幺半群嗎？幺元是什么？ (Nm，?m)是交換含幺半群，幺元是什么？ (2X，?)是交換含幺半群嗎？幺元是什么？ (P[x]，?)是交換含幺半群嗎？幺元是什么？ (XX，o)是交換半群嗎？是含幺半群嗎？幺元是什么？,42,,例8. 自由單子

64、(free monoid)(?* , o)。設?是一有限集，稱為字母表(alphabet)，任一元素a??稱為字母(alpha)。則?*是?上字的全體集合， 　 ?* ={?}?? ??2 ??3 ????n ? ? (?稱為空字)　其任何元素 w??*稱為一個字(word)；必有 k?N ,使得w? ?k ，從而w =(ai1, ai2, ai3, ? , aik)= ai1 ai2 ai3 ? aik這里aij?

65、? (1 ? j ? k) 。 o是?上字的毗連或并置(concatenation)運算，1）對任何兩個字w1 , w2 ??* ， 　　w1 o w2 = w1 w2??*仍是?上的一個字，且結果唯一，滿足封閉性，故o是?*上的二元運算； 2） 對任何三個字w1 , w2 , w3??* ， (w1 o w2 ) o w3= w1 w2 o w3 = w1 w2 w3 w1 o(w2

66、 o w3 )= w1 o w2 w3 = w1 w2 w3,43,,(w1 o w2 )ow3= w1 o(w2 o w3 )所以， o運算具有結合律；3）　對任何字w??* ， ?ow = wo?= w 所以?*關于o運算具有幺元，是空字?；4）對任何兩個字w1 , w2 ??* ，一般地 　　　　w1 o w2 ?w2 o w1 所以o運算不具有交換律；　因此，(?* , o)是一個含幺半群， 稱為自由單子

67、。它將在計算機編譯系統(tǒng)中應用到?！〉??* , o)不是一個交換半群。　自由單子的一個例子如下，若取?={a,b},則　　?*={?,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa, bab,bba,bbb,aaaa,aaab,aaba,aabb, ? ?}。,44,定義3.元素的乘冪 設(X，?)是代數系統(tǒng)， ? 是 X 上的二元運算。X 中元素的乘冪定義如下： ?

68、x? X， x 1 = x ； x m＋1= x m ? x ( m ? N )。例9. 在代數系統(tǒng)(N，+)中，1?N， 于是有： 11 = 1, 12 = 2, 13 = 12＋1 = 2＋1 = 3, …, 1n = n, …例10. 在代數系統(tǒng)(2X，?)中，A?2X，于是有： A1=A, A2=A?A=A, A3=A2?A=A?A=A,…, An=An-1?

69、A =A?A=A,…定理1. 指數律,45,,設(X，?)是半群。任取 x?X ， ?m、n?N，有 (1)xm ?xn = xm＋n = xn ?xm ； 　(2)(xm)n = xm n = (xn)m 。[證].采用歸納法　(1)固定m,選取n為歸納變元?！　‘攏=1時，由定義3知有xm ?x1 = xm＋1 ；　　當n=k時，設有xm ?xk = xm＋k ；　　當n=k+1時，有xm ?xk+1 =

70、xm ?(xk?x) 　 (定義3) 　　= (xm ?xk ) ?x (結合律) 　　 = xm＋k ?x 　 (歸納假設) 　　= xm＋(k+1) 　　 (定義3