第9章代數(shù)系統(tǒng)定理和例題講解離散數(shù)學(xué)

1、第9章 代數(shù)系統(tǒng)定理和例題講解離 散 數(shù) 學(xué)本章說明本章的主要內(nèi)容一元和二元運算定義及其實例二元運算的性質(zhì)代數(shù)系統(tǒng)定義及其實例子代數(shù) 與后面各章的關(guān)系是后面典型代數(shù)系統(tǒng)的基礎(chǔ)9.1 二元運算及其性質(zhì)9.2 代數(shù)系統(tǒng)9.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) 本章小結(jié) 作 業(yè)本章內(nèi)容9.1 二元運算及其性質(zhì)定義9.1 設(shè)S為集合，函數(shù) f：SSS 稱為S上的二元運算，簡稱為二元運算。舉例 f:NNN，f()x +y是自然數(shù)集合N上的二元運算f:NNN，f()x - y不是自然數(shù)集合N上的二元運算稱N對減法不封閉。說明驗證一個運算是否為集合S上的二元運算主要考慮兩點：S中任何兩個元素都可以進(jìn)行這種運算，且運算的

2、結(jié)果是唯一的。S中任何兩個元素的運算結(jié)果都屬于S，即S對該運算是封閉的。（1）自然數(shù)集合N上的加法和乘法是N上的二元運算，但減 法和除法不是。（2）整數(shù)集合Z上的加法、減法和乘法都是Z上的二元運算 ，而除法不是。（3）非零實數(shù)集R*上的乘法和除法都是R*上的二元運算，加 法、減法不是。 （4）設(shè)Sa1,a2,an，aiaj =ai為S上二元運算。例例（5）設(shè)Mn(R)表示所有n階(n2)實矩陣的集合，即 則矩陣加法和乘法都是Mn(R)上的二元運算。（6）S為任意集合，則、 為P(S)上的二元運算。（7）SS為S上的所有函數(shù)的集合，則合成運算為SS上的二元運 算。一元運算定義 設(shè)S為集合，函數(shù)f

3、：SS稱為S上的一元運算，簡稱為一元運算。 （1）求一個數(shù)的相反數(shù)是整數(shù)集合Z、有理數(shù)集合Q和實數(shù)集 合R上的一元運算。（2）求一個數(shù)的倒數(shù)是非零有理數(shù)集合Q*、非零實數(shù)集合R* 上的一元運算。（3）求一個復(fù)數(shù)的共軛復(fù)數(shù)是復(fù)數(shù)集合C上的一元運算。 （4）在冪集P(S)上，如果規(guī)定全集為S，則求集合的絕對補 運算是P(S)上的一元運算。 （5）設(shè)S為集合，令A(yù)為S上所有雙射函數(shù)的集合，ASS， 求一個雙射函數(shù)的反函數(shù)為A上的一元運算。（6）在n(n2)階實矩陣的集合Mn(R)上，求一個矩陣的轉(zhuǎn)置 矩陣是Mn(R)上的一元運算。一元運算舉例可以用、等符號表示二元或一元運算，稱為算符。設(shè)f : SS

4、S是S上的二元運算，對任意的x, yS，如果x與y的運算結(jié)果為z，即f()z，可以利用算符簡記為xy = z。對一元運算，x的運算結(jié)果記作x。例題 設(shè)R為實數(shù)集合，如下定義R上的二元運算 ：x,yR，x y = x。那么 3 4 = 3，0.5 (3) = 0.5。二元與一元運算的算符函數(shù)的解析公式運算表（表示有窮集上的一元和二元運算）二元與一元運算的表示 二元運算的運算表anan ana2 ana1 ana2an a2a2 a2a1 a2a1an a1a2 a1a1 a1an a2a1 一元運算的運算表an ana2 a2a1 a1ai ai例 設(shè)S=1,2，給出P(S)上的運算和的運算表

5、，其中全集為S。例 的運算表121,21,211,22221,2111,221 1,221的運算表1,212211,2 ai ai解答例 設(shè)S=1,2,3,4，定義S上的二元運算如下：x y(xy) mod 5， x,yS 求運算的運算表。例解答123411234224133314244321定義 設(shè)為S上的二元運算，如果對于任意的x,yS都有xy=yx，則稱運算在S上滿足交換律。定義 設(shè)為S上的二元運算，如果對于任意的x,y,zS都有 (xy)z=x(yz)，則稱運算在S上滿足結(jié)合律。說明：若+適合結(jié)合律，則有 (x+y)+(u+v) x+y+u+v。定義 設(shè)為S上的二元運算，如果對于任意的

6、xS有xx=x，則稱運算在S上滿足冪等律。如果S中的某些x滿足xx=x，則稱x為運算的冪等元。舉例：普通的加法和乘法不適合冪等律。但0是加法的冪等元，0和1是乘法的冪等元。二元運算的性質(zhì)例題Z, Q, R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為n階實矩陣集合, n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2 。集合運算交換律結(jié)合律冪等律Z,Q,R普通加法+普通乘法有有有有無無Mn(R)矩陣加法+矩陣乘法有無有有無無P(B)并交相對補對稱差有有無有有有無有有有無無AA函數(shù)復(fù)合無有無定義 設(shè)和為S上兩個二元運算，如果對于任意的x,y,zS，有 x(yz) (xy) (xz)（左分配律）(y

7、z)x (yx) (zx)（右分配律） 則稱運算對運算滿足分配律。 說明：若*對運算分配律成立，則*對運算廣義分配律也成立。 x(y1 y2 yn ) (xy1)(x y2) (x yn) (y1 y2 yn )x (y1x) (y2x) (ynx) 定義 設(shè)和為S上兩個可交換的二元運算，如果對于任意的x,yS，都有x(xy)x x(xy)x 則稱運算和滿足吸收律。二元運算的性質(zhì)Z, Q, R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為n階實矩陣集合，n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2 。 集合運算分配律吸收律Z,Q,R普通加法+與乘法對+可分配+對不分配無Mn(R)矩陣加法+

8、與乘法對+可分配+對不分配無P(B)并與交對可分配對可分配有交與對稱差 對可分配無例題定義 設(shè)為S上的二元運算，如果存在元素el（或er）S，使得對任意xS都有elx = x (或xer = x)則稱el (或er)是S中關(guān)于運算的一個左單位元(或右單位元)。若eS關(guān)于運算既是左單位元又是右單位元，則稱e為S上關(guān)于運算的單位元。單位元也叫做幺元。 運算可以沒有左單位元和右單位元。運算可以只有左單位元。運算可以只有右單位元。運算可以既有左單位元，又有右單位元。 說明二元運算中的特異元素單位元二元運算中的特異元素零元定義 設(shè)為S上的二元運算，如果存在元素l（或r）S，使得對任意xS都有 lx =

9、l (或xr = r)， 則稱l (或r)是S上關(guān)于運算的左零元(或右零元)。若S關(guān)于運算既是左零元又是右零元，則稱為S上關(guān)于運算的零元。 運算可以沒有左零元和右零元。運算可以只有左零元。運算可以只有右零元。運算可以既有左零元，又有右零元。 說明二元運算中的特異元素逆元定義 設(shè)為S上的二元運算，eS為運算的單位元，對于xS，如果存在yl（或yr）S使得ylxe（或xyre） 則稱yl（或yr）是x的左逆元（或右逆元）。若yS既是x的左逆元又是x的右逆元，則稱y為x的逆元。如果x的逆元存在，則稱x是可逆的。運算可以沒有左逆元和右逆元。運算可以只有左逆元。運算可以只有右逆元。運算可以既有左逆元，又

10、有右逆元。 說明特異元素的實例集合運算單位元零元逆元Z,Q,R普通加法普通乘法01無0 x的逆元xx的逆元x1Mn(R)矩陣加法矩陣乘法n階全0矩陣n階單位矩陣無n階全0矩陣x逆元xx的逆元x1（x可逆）P(B)并交BB的逆元為B的逆元為B定理定理 設(shè)為S上的二元運算，el、er分別為運算的左單位元和右單位元，則有 el = er = e 且e 為S上關(guān)于運算的唯一的單位元。 el eler (er為右單位元) eler er (el為左單位元)所以el = er，將這個單位元記作e。假設(shè)e也是S中的單位元，則有 e = ee = e所以，e 是S中關(guān)于運算的唯一的單位元。證明定理定理 設(shè)為S

11、上的二元運算，l和r分別為運算的左零元和右零元，則有 l = r = 且為S上關(guān)于運算的唯一的零元。 l lr (r為左零元) lr r (l為右零元)所以l = r，將這個零元記作 。假設(shè) 也是S中的零元，則有 = = 所以， 是S中關(guān)于運算的唯一的零元。證明定理定理 設(shè)為S上的二元運算，e 和分別為運算的單位元和零元，如果S至少有兩個元素，則e。用反證法。假設(shè) e = ，則xS有x x e x 這與S中至少含有兩個元素矛盾。所以，假設(shè)不 成立，即e。證明定理定理 設(shè)為S上可結(jié)合的二元運算，e為該運算的單位元，對于xS，如果存在左逆元yl和右逆元yr，則有yl = yr= y 且y是x的唯一

12、的逆元。由 ylx = e 和 xyr = e ，得證明yl = yle令yl = yr = y，則y是x的逆元。= yl (xyr)= (ylx) yr= eyr= yr假若yS也是x的逆元，則y= ye= y (xy)= (yx) y= ey= y所以y是x唯一的逆元，記作x1。消去律定義 設(shè)為S上的二元運算，如果對于任意的x,y,zS，滿足以下條件：（1）若xy xz且x ，則y z （左消去律）（2）若yx zx且x ，則yz （右消去律）則稱運算滿足消去律。例如：整數(shù)集合上的加法和乘法都滿足消去律。冪集P(S)上的并和交運算一般不滿足消去律。 例例 對于下面給定的集合和該集合上的二元

13、運算，指出該運算的性質(zhì)，并求出它的單位元、零元和所有可逆元素的逆元。（1）Z+，x,yZ+，xylcm(x,y)，即求x和y的最小公倍數(shù)。（2）Q，x,yQ，xy=x+y-xy解答（1）運算可交換、可結(jié)合、是冪等的。 xZ+，x1=x ， 1x=x ，1為單位元。 不存在零元。 只有1有逆元，是它自己，其他正整數(shù)無逆元。例（2） Q，x,yQ，xy=x+y-xy運算滿足交換律，因為x,yQ，有 xy =x+y-xy = y+x-yx = yx運算滿足結(jié)合律，因為x,y,zQ，有 (xy)z=(x+y-xy)z=x+y-xy+z-(x+y-xy)z= x+y+z-xy-xz-yz+xyz x(y

14、z)=x(y+z-yz)=x+(y+z-yz)-x(y+z-yz)=x+y+z-xy-xz-yz+xyz運算不滿足冪等律，因為2Q，但 22 =2+2-2202 運算滿足消去律，因為x,y,zQ，x1(1為零元)，有 xy = xz x+y-xy=x+z-xz y-z = x(y-z) y=z 由于是可交換的，所以右消去律成立。同理可證明左消去律成立，所以消去律成立。例0是運算的單位元，因為 xQ，有 x0=x+0-x0=x=0 x1是運算的零元，因為 xQ，有 x1=x+1-x1=1=1xxQ，欲使 xy=0和 yx=0成立，即 x+y-xy = 0 得所以，例例 設(shè)A=a,b,c，A上的二

15、元運算、如表所示。(1)說明、運算是否滿足交換律、結(jié)合律、消去律和冪等律。(2)求出關(guān)于、運算的單位元、零元和所有可逆元素的逆元。abcaabcbbcaccab運算滿足交換律、結(jié)合律和消去律，不滿足冪等律。單位元是a，沒有零元，且a-1=a，b-1=c，c-1=b。運算滿足交換律、結(jié)合律和冪等律，不滿足消去律。單位元是a，零元是b，只有a有逆元，a-1=a。運算滿足結(jié)合律和冪等律，不滿足交換律和消去律。沒有單位元，沒有零元，沒有可逆元。解答abcaabcbbbbccbcabcaabcbabccabc復(fù)習(xí)分析9.2 代數(shù)系統(tǒng) 定義9.12 非空集合S和S上k個一元或二元運算f1,f2, fk組成

16、的系統(tǒng)稱為一個代數(shù)系統(tǒng)，簡稱代數(shù)，記做。實例：、都是代數(shù)系統(tǒng)，其中+和分別表示普通加法和乘法。是代數(shù)系統(tǒng)，其中和分別表示n階(n2)實矩陣的加法和乘法。 是代數(shù)系統(tǒng)，其中和為并和交，為絕對補。是代數(shù)系統(tǒng)，其中Zn0,1,2, ,n-1 和分別表示模n的加法和乘法。 集合（規(guī)定了參與運算的元素）運算（只討論有限個二元和一元運算）代數(shù)常數(shù)在定義代數(shù)系統(tǒng)的時候，如果把零元和單位元也作為系統(tǒng)的性質(zhì)，稱這些元素為該代數(shù)系統(tǒng)的特異元素或代數(shù)常數(shù)。有時為了強調(diào)某個代數(shù)系統(tǒng)是含有代數(shù)常數(shù)的系統(tǒng)，也可以把這些代數(shù)常數(shù)列到系統(tǒng)的表達(dá)式中。 例如：代數(shù)系統(tǒng)。代數(shù)系統(tǒng)的成分 列出所有的成分：集合、運算、代數(shù)常數(shù)（如果

17、存在） 例如 ，列出集合和運算，在規(guī)定系統(tǒng)性質(zhì)時不涉及具有單位元的性質(zhì)（無代數(shù)常數(shù)） 例如 ，用集合名稱簡單標(biāo)記代數(shù)系統(tǒng)例如 在前面已經(jīng)對代數(shù)系統(tǒng)作了說明的前提下，上述兩個代數(shù)系統(tǒng)可以簡記為Z, P(S) 代數(shù)系統(tǒng)的表示 定義9.13 如果兩個代數(shù)系統(tǒng)中運算的個數(shù)相同，對應(yīng)運算的元數(shù)相同，且代數(shù)常數(shù)的個數(shù)也相同，則稱這兩個代數(shù)系統(tǒng)具有相同的構(gòu)成成分，也稱它們是同類型的代數(shù)系統(tǒng)。例如 V1= V2=V1、V2是同類型的代數(shù)系統(tǒng)，因為它們都含有2個二元運算， 1個一元運算， 2個代數(shù)常數(shù)。但是它們的運算性質(zhì)不一樣。同類型的代數(shù)系統(tǒng)V1=V2=+ 和可交換、可結(jié)合 對 + 可分配+ 和不滿足冪等律+

18、 與 沒有吸收律+ 和滿足消去律和可交換、可結(jié)合和互相可分配和都有冪等律和滿足吸收律和一般不滿足消去律 在規(guī)定了一個代數(shù)系統(tǒng)的構(gòu)成成分，即集合、運算以及代數(shù)常數(shù)以后，如果在對這些性質(zhì)所遵從的算律加以限制，那么滿足這些條件的代數(shù)系統(tǒng)就具有完全相同的性質(zhì)，從而構(gòu)成了一類特殊的代數(shù)系統(tǒng)。例如：代數(shù)系統(tǒng)V，如果*是可結(jié)合的，則稱V為半群。如、等都是半群。從代數(shù)系統(tǒng)的構(gòu)成成分和遵從的算律出發(fā)，將代數(shù)系統(tǒng)分類，然后研究每一類代數(shù)系統(tǒng)的共同性質(zhì)，并將研究的結(jié)果運用到具體的代數(shù)系統(tǒng)中去。(抽象代數(shù)的基本方法)以后各章分別就幾類重要的代數(shù)系統(tǒng)進(jìn)行分析。代數(shù)系統(tǒng)地說明定義設(shè)V是代數(shù)系統(tǒng)，BS，如果B對f1, f2

19、, , fk 都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱是V的子代數(shù)系統(tǒng)，簡稱子代數(shù)。簡記為B。例如：N是的子代數(shù)，N也是的子代數(shù)。N0是的子代數(shù)，但不是的子代數(shù)。子代數(shù) 子代數(shù)和原代數(shù)具有相同的成分，運算性質(zhì)也相同，是同類型的代數(shù)系統(tǒng)，在許多方面與原代數(shù)非常相似，不過可能小一些。 對于任何代數(shù)系統(tǒng)，其子代數(shù)一定存在。說明最大的子代數(shù)：就是V本身。最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構(gòu)成的集合是B，且B對V中所有的運算都是封閉的，則B就構(gòu)成了V的最小的子代數(shù)。平凡的子代數(shù)：最大和最小的子代數(shù)稱為V的平凡的子代數(shù)。真子代數(shù)：若B是S的真子集，則B構(gòu)成的子代數(shù)稱為V的真子代數(shù)。子代數(shù)的相關(guān)概念

20、例 設(shè)V=，令 nZ=nz | zZ，n為自然數(shù)， 則nZ是V的子代數(shù)。 任取nZ中的兩個元素nz1和nz2(z1,z2Z )，則有nz1+nz2 n(z1+z2 )nZ即nZ對+運算是封閉的。又0=n0 nZ所以，nZ是V的子代數(shù)。 證明當(dāng)n=1和0時，nZ是V的平凡子代數(shù)，其他的都是V的非平 凡的真子代數(shù)。說明例9.8 積代數(shù)定義 設(shè) V1=和 V2=是代數(shù)系統(tǒng)，其中和 是二元運算. V1與V2 的積代數(shù)V=, , S1S2 , = 例 V1=, V2=, 積代數(shù) , ZM2(R) , = 積代數(shù)的性質(zhì)設(shè) V1=和 V2=是代數(shù)系統(tǒng)，其中和 是二元運算. V1 與 V2 的積代數(shù)是 V=

21、(1) 若 和 運算是可交換的，那么 運算也是可交換的 (2) 若 和 運算是可結(jié)合的，那么 運算也是可結(jié)合的 (3) 若 和 運算是冪等的，那么 運算也是冪等的 (4) 若 和 運算分別具有單位元 e1 和 e2，那么 運算 也具有單位元 (5) 若 和 運算分別具有零元 1 和 2，那么 運算 也具有零元 (6) 若 x 關(guān)于 的逆元為 x1, y 關(guān)于 的逆元為 y1，那么 關(guān)于 運算也具有逆元 9.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)同態(tài)映射的定義同態(tài)映射的分類單同態(tài)、滿同態(tài)、同構(gòu)自同態(tài)同態(tài)映射的實例滿同態(tài)映射的性質(zhì)定義 設(shè) V1=和 V2=是代數(shù)系統(tǒng)，其中 和 是二元運算. f : S1S2,

22、且x,yS1 f (x y) = f(x) f( y) 則稱 f 為V1到 V2 的同態(tài)映射，簡稱同態(tài). 同態(tài)映射的定義同態(tài)映射的定義(續(xù))例1 V=, 判斷下面的哪些函數(shù)是V 的同態(tài)？ (1) f(x)=|x| (2) f(x)=2x (3) f(x)=x2 (4) f(x)=1/x (5) f(x)= x (6) f(x)=x+1解 (1) 是同態(tài), f(xy) = |xy| = |x| |y| = f(x) f(y) (4) 是同態(tài), f(xy) = 1/(xy) =1/x 1/y = f(x) f(y) (3) 是同態(tài), f(xy) = (xy)2 = x2 y2 = f(x) f(y

23、) (2) 不是同態(tài)，f(22)=f(4)=8, f(2) f(2)=4 4=16 (5) 不是同態(tài)，f(11)=f(1)= 1, f(1) f(1)=(1)(1)=1(6) 不是同態(tài)，f(11)=f(1)=2, f(1) f(1)=22=4 特殊同態(tài)映射的分類同態(tài)映射如果是單射，則稱為單同態(tài)；如果是滿射，則稱為滿同態(tài)，這時稱V2是V1的同態(tài)像，記作 V1V2；如果是雙射，則稱為同構(gòu)，也稱代數(shù)系統(tǒng)V1同構(gòu)于V2，記作 V1V2. 對于代數(shù)系統(tǒng) V，它到自身的同態(tài)稱為自同態(tài). 類似地可以定義單自同態(tài)、滿自同態(tài)和自同構(gòu). 例2 (1) 設(shè)V=，aZ，令 fa : ZZ，fa(x)=ax那么 fa是

24、V的自同態(tài). 因為x,yZ，有 fa(x+y) = a(x+y) = ax+ay = fa(x)+fa(y) 當(dāng) a = 0 時稱 f0為零同態(tài)；當(dāng)a=1時，稱 fa為自同構(gòu)；除此之外其他的 fa 都是單自同態(tài). (2) 設(shè)V1=, V2=，其中Q*=Q0，令 f: QQ*, f(x)=ex 那么 f 是V1到V2的同態(tài)映射，因為x,yQ有 f(x+y)=ex+y=exey=f(x) f(y). 不難看出 f 是單同態(tài). 同態(tài)映射的實例(3) V=, fp：ZnZn, fp(x) = (xp) mod n，p = 0, 1, , n1. x, yZn, fp(xy)=(xy)p) mod n

25、= (xp) mod n (yp) mod n = fp(x) fp(y) 例如，n=6. f0(x)=0, f1(x)=x, f2(0) = f2(3) = 0, f2(1) = f2(4) = 2, f2(2) = f2(5) = 4 f3(0) = f3(2) = f3(4) = 0, f3(1) = f3(3) = f3(5) = 3 f4(0) = f4(3) = 0, f4(1) = f4(4) = 4, f4(2) = f4(5) = 2 f5(0) = 0, f5(1) = 5, f5(2) = 4, f5(3) = 3, f5(4) = 2, f5(5) = 1 同態(tài)映射的實例(續(xù))(4) V1=, V2=,