離散數(shù)學(xué)代數(shù)系統(tǒng)PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1離散數(shù)學(xué)代數(shù)系統(tǒng)離散數(shù)學(xué)代數(shù)系統(tǒng)q本章的主要內(nèi)容本章的主要內(nèi)容一元和二元運(yùn)算定義及其實(shí)例一元和二元運(yùn)算定義及其實(shí)例二元運(yùn)算的性質(zhì)二元運(yùn)算的性質(zhì)代數(shù)系統(tǒng)定義及其實(shí)例代數(shù)系統(tǒng)定義及其實(shí)例子代數(shù)子代數(shù) q與后面各章的關(guān)系與后面各章的關(guān)系是后面典型代數(shù)系統(tǒng)的基礎(chǔ)是后面典型代數(shù)系統(tǒng)的基礎(chǔ)第1頁(yè)/共71頁(yè)第2頁(yè)/共71頁(yè)驗(yàn)證一個(gè)運(yùn)算是否為集合驗(yàn)證一個(gè)運(yùn)算是否為集合S S上的二元運(yùn)算主要考慮兩點(diǎn)：上的二元運(yùn)算主要考慮兩點(diǎn)：q S S中任何兩個(gè)元素都可以進(jìn)行這種運(yùn)算，且運(yùn)算的結(jié)果中任何兩個(gè)元素都可以進(jìn)行這種運(yùn)算，且運(yùn)算的結(jié)果是唯一的。是唯一的。q S S中任何兩個(gè)元素的運(yùn)算結(jié)果都屬于中任何兩個(gè)元素的運(yùn)

2、算結(jié)果都屬于S S，即，即S S對(duì)該運(yùn)算是對(duì)該運(yùn)算是封閉的。封閉的。第3頁(yè)/共71頁(yè)不是。（4）設(shè)Sa1,a2,an，aiaj =ai為S上二元運(yùn)算。第4頁(yè)/共71頁(yè)111212122212( ), ,1,2,.,nnnijnnnnaaaaaaMRaR i jnaaa 則矩陣加法和乘法都是則矩陣加法和乘法都是Mn(R)上的二元運(yùn)算上的二元運(yùn)算。（6）S為任意集合，則為任意集合，則、 為為P(S)上的二元上的二元運(yùn)算。運(yùn)算。（7）SS為為S上的所有函數(shù)的集合，則合成運(yùn)算上的所有函數(shù)的集合，則合成運(yùn)算 為為SS上上的二元運(yùn)算。的二元運(yùn)算。第5頁(yè)/共71頁(yè)集合Q*、非零實(shí)數(shù)集合R*上的一元運(yùn)算。（3

3、）求一個(gè)復(fù)數(shù)的共軛復(fù)數(shù)是復(fù)數(shù)集合C上的一元運(yùn)算。第6頁(yè)/共71頁(yè)（4 4）在冪集）在冪集P(S)上，如果規(guī)定全集為上，如果規(guī)定全集為S，則，則求集合的絕對(duì)補(bǔ)求集合的絕對(duì)補(bǔ)運(yùn)算是運(yùn)算是P(S)上的一元運(yùn)算。上的一元運(yùn)算。 （5 5）設(shè)）設(shè)S為集合，令為集合，令A(yù)為為S上所有雙射函數(shù)的上所有雙射函數(shù)的集合，集合，A SS，求一個(gè)雙射函數(shù)的反函數(shù)求一個(gè)雙射函數(shù)的反函數(shù)為為A上的一元運(yùn)算。上的一元運(yùn)算。（6 6）在）在n(n2)階實(shí)矩陣的集合階實(shí)矩陣的集合Mn(R)上上，求求一個(gè)矩陣的轉(zhuǎn)置矩陣一個(gè)矩陣的轉(zhuǎn)置矩陣是是Mn(R)上的一元運(yùn)算。上的一元運(yùn)算。第7頁(yè)/共71頁(yè)那么 3 4 = 3，0.5 (3

4、) = 0.5。第8頁(yè)/共71頁(yè) 二元運(yùn)算的運(yùn)算表二元運(yùn)算的運(yùn)算表an an an a2 an a1 ana2 an a2 a2 a2 a1 a2a1 an a1 a2 a1 a1 a1an a2a1 一元運(yùn)算的運(yùn)算表一元運(yùn)算的運(yùn)算表 an an a2 a2 a1 a1 ai ai第9頁(yè)/共71頁(yè) 的的運(yùn)算表運(yùn)算表121,21,211,22221,2111,221 1,221 的運(yùn)算表的運(yùn)算表1,212211,2 ai ai解解答答第10頁(yè)/共71頁(yè)解解答答 1 12 23 34 41 11 12 23 34 42 22 24 41 13 33 33 31 14 42 24 44 43 32

5、21 1第11頁(yè)/共71頁(yè)(x+y)+(u+v) x+y+u+v。第12頁(yè)/共71頁(yè)第13頁(yè)/共71頁(yè)集合集合運(yùn)算運(yùn)算交換律交換律結(jié)合律結(jié)合律冪等律冪等律Z,Q,R普通加法普通加法+ +普通乘法普通乘法 有有有有有有有有無(wú)無(wú)無(wú)無(wú)Mn(R)矩陣加法矩陣加法+ +矩陣乘法矩陣乘法 有有無(wú)無(wú)有有有有無(wú)無(wú)無(wú)無(wú)P(B)并并交交相對(duì)補(bǔ)相對(duì)補(bǔ) 對(duì)稱差對(duì)稱差 有有有有無(wú)無(wú)有有有有有有無(wú)無(wú)有有有有有有無(wú)無(wú)無(wú)無(wú)AA函數(shù)復(fù)合函數(shù)復(fù)合 無(wú)無(wú)有有無(wú)無(wú)第14頁(yè)/共71頁(yè)2n(y1 y2 yn)x (y1x) (y2x) (ynx) 第15頁(yè)/共71頁(yè)第16頁(yè)/共71頁(yè)Z, Q, R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；分別為整數(shù)、

6、有理數(shù)、實(shí)數(shù)集；Mn(R)為為n階實(shí)矩陣階實(shí)矩陣集合集合，n 2；P(B)為冪集為冪集；AA為從為從A到到A的函數(shù)集的函數(shù)集，|A| 2 。 集合集合運(yùn)算運(yùn)算分配律分配律吸收律吸收律Z,Q,R普通加法普通加法+與乘法與乘法 對(duì)對(duì)+可分配可分配+對(duì)對(duì) 不分配不分配無(wú)無(wú)Mn(R)矩陣加法矩陣加法+與乘法與乘法 對(duì)對(duì)+可分配可分配+對(duì)對(duì) 不分配不分配無(wú)無(wú)P(B)并并與交與交 對(duì)對(duì)可分配可分配對(duì)對(duì)可分配可分配有有交交與對(duì)稱差與對(duì)稱差 對(duì)對(duì) 可分配可分配無(wú)無(wú)第17頁(yè)/共71頁(yè)定義定義5.85.8 設(shè)設(shè) 為為S上的二元運(yùn)算，上的二元運(yùn)算，q 如果存在元素如果存在元素el（或或er） S，使得對(duì)任意使得對(duì)任

7、意xS都有都有el x = x (或或x er = x)則稱則稱el (或或er)是是S中關(guān)于中關(guān)于 運(yùn)算的一個(gè)運(yùn)算的一個(gè)左單位左單位元元(或或右單位元右單位元)。q 若若eS關(guān)于關(guān)于 運(yùn)算既是左單位元又是右單位運(yùn)算既是左單位元又是右單位元元，則稱則稱e為為S上關(guān)于上關(guān)于 運(yùn)算的運(yùn)算的單位元單位元。單位。單位元也叫做元也叫做幺元幺元。 q運(yùn)算可以沒有左單位元和右單位元。運(yùn)算可以沒有左單位元和右單位元。q運(yùn)算可以只有左單位元。運(yùn)算可以只有左單位元。q運(yùn)算可以只有右單位元。運(yùn)算可以只有右單位元。q運(yùn)算可以既有左單位元，又有右單位元。運(yùn)算可以既有左單位元，又有右單位元。 第18頁(yè)/共71頁(yè)q運(yùn)算可以

8、沒有左零元和右零元。運(yùn)算可以沒有左零元和右零元。q運(yùn)算可以只有左零元。運(yùn)算可以只有左零元。q運(yùn)算可以只有右零元。運(yùn)算可以只有右零元。q運(yùn)算可以既有左零元，又有右零元。運(yùn)算可以既有左零元，又有右零元。 第19頁(yè)/共71頁(yè)q運(yùn)算可以沒有左逆元和右逆元。運(yùn)算可以沒有左逆元和右逆元。q運(yùn)算可以只有左逆元。運(yùn)算可以只有左逆元。q運(yùn)算可以只有右逆元。運(yùn)算可以只有右逆元。q運(yùn)算可以既有左逆元，又有右逆元。運(yùn)算可以既有左逆元，又有右逆元。 第20頁(yè)/共71頁(yè)集合集合運(yùn)算運(yùn)算單位元單位元零元零元逆元逆元Z,Q,R普通加法普通加法普通乘法普通乘法01無(wú)無(wú)0 x的逆元的逆元 xx的逆元的逆元x 1Mn(R)矩陣加法

9、矩陣加法矩陣乘法矩陣乘法n階全階全0矩陣矩陣n階單位矩陣階單位矩陣無(wú)無(wú)n階全階全0矩陣矩陣x逆元逆元 xx的逆元的逆元x 1（x可逆可逆）P(B)并并交交BB的逆元為的逆元為B的逆元為的逆元為B第21頁(yè)/共71頁(yè) el el er (er為右單位元為右單位元) el er er (el為左單位元為左單位元)所以所以el = er，將這個(gè)單位元記作將這個(gè)單位元記作e。假設(shè)假設(shè)e 也是也是S中的單位元，則有中的單位元，則有 e = e e = e所以，所以，e 是是S中關(guān)于中關(guān)于 運(yùn)算的唯一的單位元運(yùn)算的唯一的單位元。證證明明第22頁(yè)/共71頁(yè) l l r ( r為左零元為左零元) l r r (

10、 l為右零元為右零元)所以所以 l = r，將這個(gè)零元記作將這個(gè)零元記作 。假設(shè)假設(shè) 也是也是S中的零元，則有中的零元，則有 = = 所以，所以， 是是S中關(guān)于中關(guān)于 運(yùn)算的唯一的零元。運(yùn)算的唯一的零元。證證明明第23頁(yè)/共71頁(yè)用反證法。用反證法。假設(shè)假設(shè) e = ，則則 xS有有x x e x 這與這與S中至少含有兩個(gè)元素矛盾。中至少含有兩個(gè)元素矛盾。所以，假設(shè)不所以，假設(shè)不 成立，即成立，即e 。證證明明第24頁(yè)/共71頁(yè)由由 yl x = e 和和 x yr = e ，得得證證明明yl = yl e令令yl = yr = y，則則y是是x的逆元。的逆元。= yl (x yr) = (y

11、l x) yr= e yr= yr假若假若yS也是也是x的逆元，則的逆元，則y = y e = y (x y) = (y x) y = e y= y所以所以y是是x唯一的逆元，記作唯一的逆元，記作x 1。第25頁(yè)/共71頁(yè)去律。冪集P(S)上的并和交運(yùn)算一般不滿足消去律。第26頁(yè)/共71頁(yè)解解答答（1） 運(yùn)算可交換、可結(jié)合、是冪等的。運(yùn)算可交換、可結(jié)合、是冪等的。 x Z+，x 1=x ， 1 x=x ，1為單位元。為單位元。 不存在零元。不存在零元。 只有只有1有逆元，是它自己，其他正整數(shù)無(wú)逆元。有逆元，是它自己，其他正整數(shù)無(wú)逆元。第27頁(yè)/共71頁(yè) y-z = x y-z y=z由于是可交

12、換的，所以右消去律成立。同理可證明左消去律成立，所以消去律成立。第28頁(yè)/共71頁(yè)x+y-xy = 0得(1)xyxx=-1所以，所以，1(1)xxxx=-1第29頁(yè)/共71頁(yè)abcaabcbbcaccab 運(yùn)算滿足交換律、結(jié)合律和消去律，不滿足冪等律。單運(yùn)算滿足交換律、結(jié)合律和消去律，不滿足冪等律。單位元是位元是a，沒有零元，且，沒有零元，且a-1=a，b-1=c，c-1=b。 運(yùn)算滿足交換律、結(jié)合律和冪等律，不滿足消去律。單運(yùn)算滿足交換律、結(jié)合律和冪等律，不滿足消去律。單位元是位元是a，零元是，零元是b，只有只有a有逆元有逆元，a-1=a。 運(yùn)算滿足結(jié)合律和冪等律，不滿足交換律和消去律。沒

13、運(yùn)算滿足結(jié)合律和冪等律，不滿足交換律和消去律。沒有單位元，沒有零元，沒有可逆元。有單位元，沒有零元，沒有可逆元。解解答答abcaabcbbbbccbcabcaabcbabccabc復(fù)習(xí)復(fù)習(xí)分析分析第30頁(yè)/共71頁(yè)第31頁(yè)/共71頁(yè)第32頁(yè)/共71頁(yè)n有時(shí)為了強(qiáng)調(diào)某個(gè)代數(shù)系統(tǒng)是含有代數(shù)常數(shù)的系統(tǒng)，也可以把這些代數(shù)常數(shù)列到系統(tǒng)的表達(dá)式中。例如：代數(shù)系統(tǒng)。第33頁(yè)/共71頁(yè)q 列出所有的成分列出所有的成分：集合、運(yùn)算、代數(shù)常數(shù)：集合、運(yùn)算、代數(shù)常數(shù)(如果存在如果存在)例如例如 ，q 列出集合和運(yùn)算列出集合和運(yùn)算，在規(guī)定系統(tǒng)性質(zhì)時(shí)不涉及，在規(guī)定系統(tǒng)性質(zhì)時(shí)不涉及具有單位元的性質(zhì)（無(wú)代數(shù)常數(shù)）具有單位元

14、的性質(zhì)（無(wú)代數(shù)常數(shù)） 例如例如 ，q 用集合名稱簡(jiǎn)單標(biāo)記代數(shù)系統(tǒng)用集合名稱簡(jiǎn)單標(biāo)記代數(shù)系統(tǒng)例如例如 在前面已經(jīng)對(duì)代數(shù)系統(tǒng)作了說明的前在前面已經(jīng)對(duì)代數(shù)系統(tǒng)作了說明的前提下，上述兩個(gè)代數(shù)系統(tǒng)可以簡(jiǎn)記為提下，上述兩個(gè)代數(shù)系統(tǒng)可以簡(jiǎn)記為Z, P(S) 第34頁(yè)/共71頁(yè)第35頁(yè)/共71頁(yè)V1=V2=+ 和和可交換、可結(jié)合可交換、可結(jié)合 對(duì)對(duì) + 可分配可分配+ 和和不滿足冪等律不滿足冪等律+ 與與 沒有吸收律沒有吸收律+ 和和滿足消去律滿足消去律和和可交換、可結(jié)合可交換、可結(jié)合和和互相可分配互相可分配和和都有冪等律都有冪等律和和滿足吸收律滿足吸收律和和一般不滿足消去律一般不滿足消去律 第36頁(yè)/共71

15、頁(yè)q在規(guī)定了一個(gè)代數(shù)系統(tǒng)的構(gòu)成成分，即集合、運(yùn)算以在規(guī)定了一個(gè)代數(shù)系統(tǒng)的構(gòu)成成分，即集合、運(yùn)算以及代數(shù)常數(shù)以后，如果在對(duì)這些性質(zhì)所遵從的算律加及代數(shù)常數(shù)以后，如果在對(duì)這些性質(zhì)所遵從的算律加以限制，那么滿足這些條件的代數(shù)系統(tǒng)就具有完全相以限制，那么滿足這些條件的代數(shù)系統(tǒng)就具有完全相同的性質(zhì)，從而構(gòu)成了一類特殊的代數(shù)系統(tǒng)。同的性質(zhì)，從而構(gòu)成了一類特殊的代數(shù)系統(tǒng)。例如：代數(shù)系統(tǒng)例如：代數(shù)系統(tǒng)V，如果，如果*是可結(jié)合的，則稱是可結(jié)合的，則稱V為半群。如為半群。如、等都是半群。等都是半群。q從代數(shù)系統(tǒng)的構(gòu)成成分和遵從的算律出發(fā)，將代數(shù)系從代數(shù)系統(tǒng)的構(gòu)成成分和遵從的算律出發(fā)，將代數(shù)系統(tǒng)分類，然后研究每一類

16、代數(shù)系統(tǒng)的共同性質(zhì)，并將統(tǒng)分類，然后研究每一類代數(shù)系統(tǒng)的共同性質(zhì)，并將研究的結(jié)果運(yùn)用到具體的代數(shù)系統(tǒng)中去。研究的結(jié)果運(yùn)用到具體的代數(shù)系統(tǒng)中去。(抽象代數(shù)抽象代數(shù)的基本方法的基本方法)第37頁(yè)/共71頁(yè)nN0是的子代數(shù)，但不是的子代數(shù)。q子代數(shù)和原代數(shù)具有相同的成分，運(yùn)算性質(zhì)也相同，子代數(shù)和原代數(shù)具有相同的成分，運(yùn)算性質(zhì)也相同，是同類型的代數(shù)系統(tǒng)，在許多方面與原代數(shù)非常相似是同類型的代數(shù)系統(tǒng)，在許多方面與原代數(shù)非常相似，不過可能小一些。，不過可能小一些。 q對(duì)于任何代數(shù)系統(tǒng)，其子代數(shù)一定存在。對(duì)于任何代數(shù)系統(tǒng)，其子代數(shù)一定存在。第38頁(yè)/共71頁(yè)第39頁(yè)/共71頁(yè)例例5.85.8 設(shè)設(shè)V=，令令

17、 nZ=nz | z Z，n為自然數(shù)，為自然數(shù)， 則則nZ是是V的子代數(shù)。的子代數(shù)。 任取任取nZ中的兩個(gè)元素中的兩個(gè)元素nz1和和nz2(z1,z2 Z )，則有則有nz1+nz2 n(z1+z2 ) nZ即即nZ對(duì)對(duì)+運(yùn)算是封閉的。又運(yùn)算是封閉的。又0=n0 nZ所以，所以，nZ是是V的子代數(shù)。的子代數(shù)。 證證明明q當(dāng)當(dāng)n=1和和0時(shí)，時(shí)，nZ是是V的平凡子代數(shù)，其他的都是的平凡子代數(shù)，其他的都是V的非的非平平 凡的真子代數(shù)。凡的真子代數(shù)。第40頁(yè)/共71頁(yè)bababa),(Q試討論 的運(yùn)算性質(zhì),有單位元例 在 中, 為有理數(shù)Q),(Q零元、逆元嗎？Qcba,解: 對(duì)任意集. 對(duì)Qba ,

18、第41頁(yè)/共71頁(yè)abbaba)1abbaab)()()2cbcbacba)(cbcbacba)(cabbacabba)()(cbcba第42頁(yè)/共71頁(yè)aeaeaeaa0)1 ( ae0e)3設(shè)單位元為e)4設(shè)零元為aa0)1 (a1第43頁(yè)/共71頁(yè),)5Qa0axxa0exa逆元1aax1a時(shí)11aaa設(shè)a的逆元為x第44頁(yè)/共71頁(yè)單位元也是零元,問A是什么集合?例 * 為 上的二元運(yùn)算,它的A解: 設(shè)aA, 且a為A上*的單位元和零元,對(duì)任意xA, 有xaxxaaaxxa單位元零 元 必為單元素集.Aax 即aA 第45頁(yè)/共71頁(yè)A例 設(shè) 上 滿足結(jié)合律,且對(duì)試證 對(duì)任意的自然數(shù) , 有naan證明: 對(duì) 用歸納法n,Aba由, abba得ba 第46頁(yè)/共71頁(yè)當(dāng) 時(shí),aa 11naaaaaa)()(, abba得ba aaakn 時(shí)aa 2aak成立時(shí),aaa22n結(jié)合第47頁(yè)/共71頁(yè)aaaaaakk1所以對(duì)任意的 ,有. aann第48頁(yè)/共71頁(yè)5.3代數(shù)系統(tǒng)的同構(gòu)與同態(tài)兩個(gè)代數(shù)系統(tǒng)(0,1, )和(a,b,*)0 10 11 101*a ba bb bab0 a 1 b第49頁(yè)/共71頁(yè)第50頁(yè)/共71頁(yè)第51頁(yè)/共71頁(yè)g(xg(x1 1) )g(xg(x2 2 ) )g(xg(x1 1) ) * *g