離散數(shù)學(xué)第十二章 代數(shù)結(jié)構(gòu)基本概念及性質(zhì)

1、離散數(shù)學(xué)第十二章 代數(shù)結(jié)構(gòu)基本概念及性質(zhì)第1頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五12.1 代數(shù)結(jié)構(gòu)的定義與例在正式給出代數(shù)結(jié)構(gòu)的定義之前，先來說明什么是在一個(gè)集合上的運(yùn)算，因?yàn)檫\(yùn)算這個(gè)概念是代數(shù)結(jié)構(gòu)中不可缺少的基本概念。定義 設(shè)S是個(gè)非空集合且函數(shù) 或 f : Sn S，則稱 f 為一個(gè)n元運(yùn)算。其中n是自然數(shù)，稱為運(yùn)算的元數(shù)或階。當(dāng)n=1時(shí)，稱f為一元運(yùn)算，當(dāng)n=2時(shí)，稱f為二元運(yùn)算，等等。第2頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五注意，n元運(yùn)算首先是一個(gè)函數(shù)，其次是個(gè)閉運(yùn)算(所謂閉運(yùn)算是指：集合上的運(yùn)算，其運(yùn)算結(jié)果都在原來的集合中，我們把具有這種特

2、征的運(yùn)算稱作封閉的，簡(jiǎn)稱閉運(yùn)算)。封閉性表明了n元運(yùn)算與一般函數(shù)的區(qū)別之處。此外，有些運(yùn)算存在幺元或零元，它在運(yùn)算中起著特殊的作用，稱它為S中的特異元或常數(shù)。第3頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五運(yùn)算的例子很多，例如，在數(shù)理邏輯中，否定是謂詞集合上的一元運(yùn)算，合取和析取是謂詞集合上的二元運(yùn)算；在集合論中，并與交是集合上的二元運(yùn)算；在整數(shù)算術(shù)中，加、減、乘運(yùn)算是二元運(yùn)算，而除運(yùn)算便不是二元運(yùn)算，因?yàn)樗粷M足封閉性。第4頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五在下面討論的代數(shù)結(jié)構(gòu)中，主要限于一元和二元運(yùn)算，將用、或等符號(hào)表示一元運(yùn)算符；用、等表示二元運(yùn)算符

3、，一元運(yùn)算符常常習(xí)慣于前置、頂置或肩置，如x、 、x；而二元運(yùn)算符習(xí)慣于前置、中置或后置，如：+xy，x+y，xy+。有了集合上運(yùn)算的概念后，便可定義代數(shù)結(jié)構(gòu)了。第5頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(shè)S是個(gè)非空集合且fi是S上的ni元運(yùn)算，其中i=1，2，m。由S及f1，f2，fm組成的結(jié)構(gòu)，稱為代數(shù)結(jié)構(gòu)，記作。例：設(shè)Z是整數(shù)集， “”是Z上的普通加法運(yùn)算，則是一個(gè)代數(shù)結(jié)構(gòu)。例：設(shè)R是實(shí)數(shù)集 ，“”與“”是實(shí)數(shù)集R上的普通加法和乘法運(yùn)算，則是一個(gè)代數(shù)結(jié)構(gòu)。第6頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：我們可以構(gòu)造下述的一個(gè)代數(shù)結(jié)構(gòu)：設(shè)有一個(gè)由

4、有限個(gè)字母組成的集合 ，叫字母表，在上任意長(zhǎng)的字母串，叫做上句子或字符串，串中字母的個(gè)數(shù)m叫這個(gè)串的長(zhǎng)度，我們假定當(dāng)一個(gè)字的長(zhǎng)度m=0時(shí)用符號(hào)表示，它叫做空串。這樣我們可以構(gòu)造一個(gè)在上的所有串的集合*。其次，我們定義一個(gè)在*上的運(yùn)算“/”并置運(yùn)算或者連接運(yùn)算，設(shè)， *，則 /。通過并置運(yùn)算將兩個(gè)串聯(lián)成一個(gè)新的串，而此聯(lián)成的新串也在*內(nèi)，這樣構(gòu)造的 是一個(gè)代數(shù)結(jié)構(gòu)第7頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五如果令+ *，則也是一個(gè)代數(shù)結(jié)構(gòu)。這兩種代數(shù)結(jié)構(gòu)都是計(jì)算機(jī)科學(xué) 中經(jīng)常要用到的代數(shù)結(jié)構(gòu)。第8頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：設(shè)有一計(jì)算機(jī)它的字長(zhǎng)

5、是32位，它以定點(diǎn)加、減、乘、除及邏輯加、邏輯乘為運(yùn)算指令，并分別用01，02，06表示之。則在該計(jì)算機(jī)中由232有限個(gè)不同的數(shù)字所組成的集合S以及計(jì)算機(jī)的運(yùn)算型機(jī)器指令就構(gòu)成了一個(gè)代數(shù)結(jié)構(gòu)。第9頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五因此，一個(gè)代數(shù)結(jié)構(gòu)需要滿足二個(gè)條件：(1)有一個(gè)非空集合S(2) 在集合S上定義的運(yùn)算一定是封閉的第10頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五此外，我們把集合S的基數(shù)即|S|，定義為代數(shù)結(jié)構(gòu)的基數(shù)。如果S是有限集合，則說代數(shù)結(jié)構(gòu)是有限代數(shù)結(jié)構(gòu)；否則便說是無窮代數(shù)結(jié)構(gòu).有時(shí)，要考察兩個(gè)或多個(gè)代數(shù)結(jié)構(gòu)，這里就有個(gè)是否同類型之說，

6、請(qǐng)看下面定義：第11頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(shè)兩個(gè)代數(shù)結(jié)構(gòu)和，如果fi和gi(1im)具有相同的元數(shù)，則稱這兩個(gè)代數(shù)結(jié)構(gòu)是同類型的?？梢?，判定兩個(gè)代數(shù)結(jié)構(gòu)是否同類型，主要是對(duì)其運(yùn)算進(jìn)行考察：兩個(gè)代數(shù)結(jié)構(gòu)是否有相同個(gè)數(shù)的運(yùn)算符；每個(gè)相對(duì)應(yīng)的運(yùn)算符是否有相同的元數(shù)。第12頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：代數(shù)結(jié)構(gòu)與代數(shù)結(jié)構(gòu)是相同類型的，因?yàn)樗鼈兌加幸粋€(gè)二元運(yùn)算符。例：代數(shù)結(jié)構(gòu)與的類型是不相同的，因?yàn)樗鼈兊倪\(yùn)算符的個(gè)數(shù)不同。第13頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：設(shè)S是非空集合，P(S)是它的冪集。對(duì)任意

7、集合A，BP(S)上的運(yùn)算和如下:AB =(AB)(BA)AB = AB則是一代數(shù)結(jié)構(gòu)。因?yàn)?，顯然和是閉運(yùn)算。 與是同類型代數(shù)結(jié)構(gòu)的。有時(shí)還需要在代數(shù)結(jié)構(gòu)中集合的某個(gè)子集上討論其性質(zhì)，這就引出子代數(shù)結(jié)構(gòu)的概念.第14頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(shè)是一代數(shù)結(jié)構(gòu)，且非空集TS在運(yùn)算f1，f2，fm作用下是封閉的，且T含有與S中相同的特異元，則稱為代數(shù)結(jié)構(gòu)的子代數(shù)。記為。例：設(shè) E是所有偶數(shù)所組成的集合，則代數(shù)結(jié)構(gòu)是的一個(gè)子代數(shù)結(jié)構(gòu)例： 顯然， .第15頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五12.2 代數(shù)結(jié)構(gòu)的基本性質(zhì)所謂代數(shù)結(jié)構(gòu)的性質(zhì)即是結(jié)構(gòu)

8、中任何運(yùn)算所具有的性質(zhì)。以下我們均假設(shè)運(yùn)算為二元運(yùn)算。1.結(jié)合律給定，則運(yùn)算“”滿足結(jié)合律或“”是可結(jié)合的，即(x)(y)(z)(x,y,zS(xy)z=x(yz)第16頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定且對(duì)任意a，bA有ab=b。證明運(yùn)算“”是可結(jié)合的。 證明：因?yàn)閷?duì)任意a，b，cA(ab)c=bc=ca(bc)=ac=c故 (ab)c=a(bc)注意，不是任何代數(shù)結(jié)構(gòu)上的運(yùn)算都滿足結(jié)合律，如整數(shù)集上“”運(yùn)算就不滿足結(jié)合律。如：5(21)4,但是(52)12.第17頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五2.交換律給定，則運(yùn)算“”滿足交換律或

9、“”是可交換的，即(x)(y)(x,ySxy=yx)。例 給定，其中Q為有理數(shù)集合，并且對(duì)任意a，bQ有ab = a + b - ab，問運(yùn)算是否可交換?證： ab = a + b - ab= b + a - ba b a ，故運(yùn)算是可交換的。第18頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五同樣，并不是所有代數(shù)結(jié)構(gòu)上運(yùn)算均滿足交換律，如矩陣的乘法就不滿足交換律。易見，如果一代數(shù)結(jié)構(gòu)中的運(yùn)算是可結(jié)合和可交換的，那么，在計(jì)算a1a2am時(shí)可按任意次序計(jì)算其值。特別當(dāng)a1a2ama時(shí)，則a1a2amam。稱am為a的m次冪，m稱a的指數(shù)。下面給出am的歸納定義：第19頁，共98頁，2

10、022年，5月20日，11點(diǎn)13分，星期五設(shè)有且aS，對(duì)于mZ+，其中Z+表示正整數(shù)集合，可有：(1) a1=a(2)am+1=ama由此利用歸納法不難證明指數(shù)定律：(1)aman=am+n(2)(am)n=amn這里，m,nZ+。類似地定義某代數(shù)結(jié)構(gòu)中的負(fù)冪和給出負(fù)指數(shù)定律。第20頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五3.分配律一個(gè)代數(shù)結(jié)構(gòu)若具有兩個(gè)運(yùn)算時(shí)，則分配律可建立這兩個(gè)運(yùn)算之間的某種聯(lián)系。給定，稱運(yùn)算對(duì)于滿足左分配律，或者對(duì)于是可左分配的，如果有(x)(y)(z)(x,y,zSx(yz)=(xy)(xz)同理，稱運(yùn)算對(duì)于滿足右分配律或?qū)τ谑强捎曳峙涞?，如果?x)

11、(y)(z)(x,y,zS(yz)x=(yx)(zx)第21頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五類似地可定義對(duì)于是滿足左或右分配律.若對(duì)于既滿足左分配律又滿足右分配律，則稱對(duì)于滿足分配律或是可分配的。同樣可定義對(duì)于滿足分配律。由定義不難證明下面定理：定理 給定且是可交換的。如果對(duì)于滿足左或右分配律，則對(duì)于滿足分配律。第22頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中B=0,1。表分別定義了運(yùn)算和，問運(yùn)算對(duì)于是可分配的嗎？對(duì)于呢？第23頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五形如表的表常常被稱為運(yùn)算表或復(fù)合表，它由運(yùn)算符、行表頭

12、元素、列表頭元素及復(fù)合元素四部分組成。當(dāng)集合S的基數(shù)很小，特別限于幾個(gè)時(shí)，代數(shù)結(jié)構(gòu)中運(yùn)算常常用這種表給出。其優(yōu)點(diǎn)簡(jiǎn)明直觀，一目了然。解 可以驗(yàn)證對(duì)于是可分配的，但對(duì)于并非如此。因?yàn)?(01)(10)(11) 1 0 1 0 0第24頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五4.吸收律給定，則對(duì)于滿足左吸收律:=(x)(y)(x,ySx(xy)=x)對(duì)于滿足右吸收律:=(x)(y)(x,yS(xy)x=x)第25頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五若對(duì)于既滿足左吸收律又滿足右吸收律，則稱對(duì)于滿足吸收律或可吸收的。對(duì)于 和吸收律類似地定義。若對(duì)于是可吸收的且對(duì)

13、于也是可吸收的，則和是互為吸收的或和同時(shí)滿足吸收律。第26頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中N是自然數(shù)集合，和定義如下：對(duì)任意a，bN有ab = maxa，b，a b = mina，b，試證，和互為吸收的。證明：不妨假設(shè)aba(ab) = maxa， mina，b= a(ab)a = maxmina，b ，a= a故對(duì)于滿足吸收律。同理可證， 對(duì)于滿足吸收律。故和互為吸收的。第27頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五5.等冪律與等冪元給定，則“”是等冪的或“”滿足等冪律:=( x)(xSxx=x)給定且xS，則x是關(guān)于“”的等冪元:=

14、xx=x于是，不難證明下面定理：定理 若x是中關(guān)于的等冪元，對(duì)于任意正整數(shù)n，則xn=x。第28頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中P(S)是集合S的冪集，和分別為集合的并和交運(yùn)算。驗(yàn)證：和是等冪的。證：對(duì)任意A P(S)，有AA=A和AA=A，故和是等冪的。第29頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五6. 幺元或單位元給定且el，er，eS，則el為關(guān)于的左幺元:=( x)(xSelx=x)er為關(guān)于的右幺元:=( x)(xSxer=x)若e既為的左幺元又為的右幺元，稱e為關(guān)于的幺元。亦可定義如下：e為關(guān)于的幺元:=( x)(xSex=

15、xe=x)。第30頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定理 給定且el和er分別是關(guān)于的左、右幺元，則el=er=e且幺元e唯一。例：實(shí)數(shù)集R上的代數(shù)結(jié)構(gòu)的“”運(yùn)算的幺元為1，因?yàn)閷?duì)任意xR有x11xx。而“”運(yùn)算的幺元為0，因?yàn)閷?duì)任意xR有x00 xx。例：前面例子中關(guān)于串的并置運(yùn)算，它的單位元素是空串，因?yàn)閷?duì)任一串A，均有 / A = A / = A。第31頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五7.零元給定及l(fā)，r，S，則l為關(guān)于的左零元:=( x)(xSlx=l)r為關(guān)于的右零元:=( x)(xSxr=r)為關(guān)于的零元:=( x)(xSx=x=)

16、第32頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定理 給定且l和r分別為關(guān)于的左零元和右零元，則l=r=且零元是唯一的。定理 給定且|S|1。如果，eS，其中和e分別為關(guān)于的零元和幺元，則e。第33頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：代數(shù)結(jié)構(gòu)上的零元是“0”，因?yàn)閷?duì)于任何整數(shù)x，均有x00 x0。例：正整數(shù)集Z+上的運(yùn)算“min”，叫“取最小”運(yùn)算。min(a,b)為取a,b的最小者。代數(shù)結(jié)構(gòu)中對(duì)應(yīng)于運(yùn)算“min”的零元為1。第34頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五8逆元給定且幺元e，xS，則x為關(guān)于的左逆元:=(y)(ySxy

17、=e)x為關(guān)于的右逆元:=(y)(ySyx=e)x為關(guān)于可逆的:=(y)(ySyx=xy=e)第35頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五給定及幺元e；x，yS，則y為x的左逆元:=yx=ey為x的右逆元:=xy=ey為x的逆元:=yx=xy=e第36頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五顯然，若y是x的逆元，則x也是y的逆元，因此稱x與y互為逆元。通常x的逆元表示為x-1。一般地說來，一個(gè)元素的左逆元不一定等于該元素的右逆元。而且，一個(gè)元素可以有左逆元而沒有右逆元，反之亦然。甚至一個(gè)元素的左或右逆元還可以不是唯一的。第37頁，共98頁，2022年，5月

18、20日，11點(diǎn)13分，星期五定理 給定及幺元eS。如果是可結(jié)合的并且一個(gè)元素x的左逆元xl-1和右逆元xr-1存在，則xl-1=xr-1。定理 給定及幺元eS。如果是可結(jié)合的并且x的逆元x-1存在，則x-1是唯一的。第38頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：代數(shù)結(jié)構(gòu)上的幺元是“0”，對(duì)于任何整數(shù)x，它的逆元是x，因?yàn)?x(x)0。例：代數(shù)結(jié)構(gòu)中0和1分別為和的幺元。對(duì)于“”，對(duì)每個(gè)元素rR都有逆元r；對(duì)于“”，對(duì)每個(gè)元素 rR都有逆元1/r(r 0) 。第39頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五9.可約律與可約元給定且零元S，則滿足左可約律或是左

19、可約的:=( x)( y)( z)(x,y,zSxxy=xz)y=z)，并稱x是關(guān)于的左可約元。滿足右可約律或是右可約的:=( x)( y)( z)(x,y,zSxyx=zx)y=z)，并稱x是關(guān)于的右可約元。第40頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五若既滿足左可約律又滿足右可約律或既是左可約又是右可約的，則稱滿足可約律或是可約的。若x既是關(guān)于的左可約元又是關(guān)于的右可約元，則稱x是關(guān)于的可約元。可約律與可約元也可形式地定義如下：第41頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五滿足可約律:=( x)( y)( z)(x,y,zSx(xy=xzyx=zx)y=

20、z)x是關(guān)于的可約元:=( y)( z)(y,zSx(xy)=xzyx=zx)y=z)第42頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例：給定，其Z是整數(shù)集合，是一般乘法運(yùn)算。顯然，每個(gè)非零整數(shù)都是可約元，而且運(yùn)算滿足可約律。第43頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定理 給定且是可結(jié)合的，如果x是關(guān)于可逆的且x，則x也是關(guān)于的可約元。證明 設(shè)任意y,zS且有xy=xz或yx=zx。因?yàn)槭强山Y(jié)合的及x是關(guān)于可逆的，則有x-1(xy)=(x-1x)y=ey=yx-1(xz)=(x-1x)z=ez=z第44頁，共98頁，2022年，5月20日，11點(diǎn)13分，星

21、期五故得xy=xzy=z，故x是關(guān)于的左可約元。同樣可證得yx=zxy=z，故x是關(guān)于的右可約元。故x是關(guān)于的可約元。最后，作一補(bǔ)充說明，用運(yùn)算表定義一代數(shù)結(jié)構(gòu)的運(yùn)算，從表上很能反映出關(guān)于運(yùn)算的各種性質(zhì)。為確定起見，假定及x，y，eS。第45頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五(1)運(yùn)算具有封閉性，當(dāng)且僅當(dāng)表中的每個(gè)元素都屬于S。(2)運(yùn)算滿足交換律，當(dāng)且僅當(dāng)表關(guān)于主對(duì)角線是對(duì)稱的。第46頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五(3)運(yùn)算是等冪的，當(dāng)且僅當(dāng)表的主對(duì)角線上的每個(gè)元素與所在行或列表頭元素相同。abcaabbcc第47頁，共98頁，2022年，

22、5月20日，11點(diǎn)13分，星期五(4)元素x是關(guān)于的左零元，當(dāng)且僅當(dāng)x所對(duì)應(yīng)的行中的每個(gè)元素都與x相同；元素y是關(guān)于的右零元，當(dāng)且僅當(dāng)y所對(duì)應(yīng)的列中的每個(gè)元素都與y相同；元素是關(guān)于的零元，當(dāng)且僅當(dāng)所對(duì)應(yīng)的行和列中的每個(gè)元素都與相同。lmnaxxxxc左零元xmnyaybycy右零元ymnac零元第48頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五(5)元素x為關(guān)于的左幺元，當(dāng)且僅當(dāng)x所對(duì)應(yīng)的行中元素依次與行表頭元素相同；元素y為關(guān)于的右幺元，當(dāng)且僅當(dāng)y所對(duì)應(yīng)的列中元素依次與列表頭元素相同；元素e是關(guān)于的幺元，當(dāng)且僅當(dāng)e所對(duì)應(yīng)的行和列中元素分別依次與行表頭元素和列表頭元素相同。lmn

23、axlmnc左幺元xmnyaabbcc右幺元ymneaaemnecc幺元e第49頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五(6)x為關(guān)于的左逆元，當(dāng)且僅當(dāng)位于x所在行的元素中至少存在一個(gè)幺元，y為關(guān)于的右逆元，當(dāng)且僅當(dāng)位于y所在列的元素中至少存在一個(gè)幺元；x與y互為逆元，當(dāng)且僅當(dāng)位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是幺元。lmnaxec左逆元mnyaebc右逆元mxyxebye逆元第50頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中S=，且的定義如表所示。試指出該代數(shù)結(jié)構(gòu)中各元素的左、右逆元情況。表解：是幺元；的左逆元和右逆元都是

24、，即與互為逆元；的左逆元是而右逆元是；有兩個(gè)左逆元和；的右逆元是，但沒有左逆元。 e e e e e e e e 第51頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五12.3 同態(tài)與同構(gòu)本節(jié)將闡明兩個(gè)重要概念同態(tài)與同構(gòu)。在以后各節(jié)中，它們會(huì)經(jīng)常被使用到。第52頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(shè)與是同類型的。稱同態(tài)于或?yàn)榈耐瑧B(tài)象，記為 ，其定義如下： :=(f)(fYX(x1)(x2)(x1,x2Xf(x1x2)=f(x1)f(x2)同時(shí)，稱f為從到的同態(tài)映射.可以看出，同態(tài)映射f不必是惟一的。第53頁，共98頁，2022年，5月20日，11點(diǎn)13分，

25、星期五 X x1x2x3 x1x3f(X)y1=f(x1)f(x1)=f(x2)y3=f(x3)y1y3Y同態(tài)示意圖f第54頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定和，其中R是實(shí)數(shù)集合，和分別是加法和乘法運(yùn)算，試證 。證：關(guān)鍵是找一個(gè)同態(tài)映射。今構(gòu)造函數(shù)fRR如下：f(x)=ax , 其中a0, xR則f為所求的同態(tài)映射，這是因?yàn)閷?duì)任意y,zR，有f(yz)= ayz ay az f(y)f(z)因此， 第55頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五兩個(gè)同類型的代數(shù)結(jié)構(gòu)間的同態(tài)定義不僅適用于具有一個(gè)二元運(yùn)算的代數(shù)結(jié)構(gòu)，也可以推廣到具有多個(gè)二元運(yùn)算的任

26、何兩個(gè)同類型代數(shù)結(jié)構(gòu)。例如，對(duì)于具有兩個(gè)二元運(yùn)算的兩個(gè)同類型代數(shù)結(jié)構(gòu)和的同態(tài)定義如下： :=(f)(fYX(x1)(x2)(x1,x2X(f(x1x2)=f(x1)f(x2)f(x1x2)=f(x1)f(x2)第56頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定理 如果 且f為其同態(tài)映射，則 。由于函數(shù)fYX的不同性質(zhì)，將給出不同種類的同態(tài)定義。第57頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(shè) 且f為其同態(tài)映射。(i)如果 f 為滿射，則稱 f 是從到的滿同態(tài)映射。(ii)如果f為單射(或一對(duì)一映射)，則稱f為從到的單一同態(tài)映射。第58頁，共98頁，202

27、2年，5月20日，11點(diǎn)13分，星期五(iii)如果f為雙射(或一一對(duì)應(yīng))，則稱f為從到的同構(gòu)映射。記為 。顯然，若 f 是從到的同構(gòu)映射，則 f 為從到的滿同態(tài)映射及單一同態(tài)映射，反之亦然。第59頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 設(shè)與是同類型的，其中*為有限字母表上的字母串集合，為并置運(yùn)算，N為自然數(shù)集合，+為普通加法。若定義 f：*N為 f(x)= | x | 其中x*，| x |表示字母串的長(zhǎng)度。因?yàn)閷?duì)任意 x，y*，有f(xy )= | xy | = | x | + | y | = f(x)+ f(y)，故 。顯然，f是滿射，因此，f為從到的滿同態(tài)映射。第6

28、0頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中Z為整數(shù)集合，+為一般加法。作函數(shù)fZZ：f(x)=kx，(此處乘法是一般乘法)其中x,kZ則當(dāng)k0時(shí)，由于f(y+z)=k(y+z)=ky+kz=f(y)+f(z)，故f為到的同態(tài)映射。又易知f為單射，故f為到的單一同態(tài)映射。當(dāng)k=-1或k=1時(shí)，f為從到的同構(gòu)映射(我們稍后再來證明)。第61頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五綜上可以看出，同態(tài)映射具有一個(gè)特性，即“保持運(yùn)算”。對(duì)于滿同態(tài)映射來說，它能夠保持運(yùn)算的更多性質(zhì)，為此，給出如下定理：定理 給定 且 f 為其滿同態(tài)映射，則(a)如果和滿足

29、結(jié)合律，則和也滿足結(jié)合律。(b)如果和滿足交換律，則和也滿足交換律。第62頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五(c)如果對(duì)于或?qū)τ跐M足分配律，則對(duì)于或?qū)τ谝蚕鄳?yīng)滿足分配律。(d)如果對(duì)于或?qū)τ跐M足吸收律，則對(duì)于或?qū)τ谝矟M足吸收律。(e)如果和滿足等冪律，則和也滿足等冪律。(f)如果e1和e2分別是關(guān)于和的幺元，則f(e1)和f(e2)分別為關(guān)于和的幺元。第63頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五(g)如果1和2分別是關(guān)于和的零元，則f(1)和f(2)分別為關(guān)于和的零元。(h)如果對(duì)每個(gè)xX均存在關(guān)于的逆元x-1，則對(duì)每個(gè)f(x)Y也均存在關(guān)于的逆元f

30、(x-1)；如果對(duì)每個(gè)zX均存在關(guān)于的逆元z-1，則對(duì)每個(gè)f(z)Y也均存在關(guān)于的逆元f(z-1)。第64頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定理告訴我們，對(duì)于滿同態(tài)映射來說，代數(shù)結(jié)構(gòu)的許多性質(zhì)都能保持，如結(jié)合律、交換律、分配律、等冪律、幺元、零元、逆元等，但這種保持性質(zhì)是單向的，即如果滿同態(tài)于，則所具有的性質(zhì)，均具有。但反之不然，即所具有的某些性質(zhì)，不一定具有。不盡要問，在怎樣條件下，所具有的性質(zhì)都完全具有呢?為了回答這個(gè)問題，需要引出兩個(gè)代數(shù)結(jié)構(gòu)同構(gòu)的概念。第65頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(shè)與是同類型的。稱同構(gòu)于，記為 ，其定義如

31、下：:=(f)(f為從到的同構(gòu)映射)或更詳細(xì)地定義為：:=(f)(fYXf為雙射f為從到的同態(tài)映射)第66頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五 x1x2 x1x2f(x1) f(x2)f(x1)f(x2)同構(gòu)示意圖f第67頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 代數(shù)結(jié)構(gòu)與是同構(gòu)的。其中R為實(shí)數(shù)，R+為正實(shí)數(shù)。證：關(guān)鍵是找一個(gè)雙射。對(duì) 與，有一個(gè)函數(shù)h：R+R，h(x)=lnx此函數(shù)是雙射的。因?yàn)閷?duì)每個(gè)x0,均存在一個(gè)y=lnxR，同時(shí)，對(duì)每個(gè)yR，均存在一個(gè)x=ey R+.又因?yàn)閔(yz)=ln(yz)=lnylnz=h(y)h(z)故與是同構(gòu)的。注

32、：當(dāng)然，我們也可以取函數(shù)h(x)=lgx，第68頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五續(xù)例 給定，其中Z為整數(shù)集合，+為一般加法。作函數(shù)fZZ：f(x)=kx，(此處乘法是一般乘法)其中x,kZ，則當(dāng)k=-1或k=1時(shí)，f為從到的同構(gòu)映射。證：先證明當(dāng)k=-1或k=1時(shí)f為雙射。因?yàn)閷?duì)每個(gè)xZ,均存在一個(gè)y=kx(即y=x或y=-x)Z，同時(shí)，對(duì)每個(gè)yZ，均存在一個(gè)x=y/k (即x=y或x=-y) Z。(顯然，若k取1以外的值，y/k不一定是整數(shù)，或者y/k無意義，此時(shí)f 就不是雙射了.)又由于f(y+z)=k(y+z)=ky+kz=f(y)+f(z)，故f為到的同構(gòu)映射

33、。第69頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 代數(shù)結(jié)構(gòu)與是同構(gòu)的。其中M, H分別表示低電平、高電平，“”表示或門，它們的運(yùn)算表如下。證：這兩個(gè)代數(shù)結(jié)構(gòu)間存在一個(gè)函數(shù)f:0,1M,H，且f(0)=M, f(1)=H，顯然這是一個(gè)雙射，而且有f(xy)=f(x)+f(y)。故它們是同構(gòu)的。01001111MHMMHHHH第70頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 設(shè)S=4,5,6,在S上的二元運(yùn)算“”其定義如下表所示。又有P=1,2,3及在P上的二元運(yùn)算“”，其運(yùn)算表如下表所示。這樣所構(gòu)成的兩個(gè)代數(shù)結(jié)構(gòu)與是同構(gòu)的。證：這兩個(gè)代數(shù)結(jié)構(gòu)間存在一個(gè)函數(shù)f

34、:4,5,61,2,3，f(x)=x-3，其中xS。顯然這是一個(gè)雙射，而且有f(xy)=f(x)f(y)。故它們是同構(gòu)的。456445454556456123112121223123第71頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五由定義可知，同構(gòu)的條件比同態(tài)強(qiáng)，關(guān)鍵是同構(gòu)映射是雙射，即一一對(duì)應(yīng)。而同態(tài)映射不一定要求是雙射。正因?yàn)槿绱?，同?gòu)不再僅僅象滿同態(tài)那樣對(duì)保持運(yùn)算是單向的了，而對(duì)保持運(yùn)算成為雙向的。兩個(gè)同構(gòu)的代數(shù)，表面上似乎很不相同，但在結(jié)構(gòu)上實(shí)際是沒有什么差別，只不過是集合中的元素名稱和運(yùn)算的標(biāo)識(shí)不同而已，而它們的所有發(fā)生“彼此相通”。第72頁，共98頁，2022年，5月

35、20日，11點(diǎn)13分，星期五這樣，當(dāng)探索新的代數(shù)結(jié)構(gòu)的性質(zhì)時(shí)，如果發(fā)現(xiàn)或者能夠證明該結(jié)構(gòu)同構(gòu)于另外一個(gè)性質(zhì)已知的代數(shù)結(jié)構(gòu)，便能直接地知道新的代數(shù)結(jié)構(gòu)的各種性質(zhì)了。對(duì)于同構(gòu)的兩個(gè)代數(shù)結(jié)構(gòu)來說，在它們的運(yùn)算表中除了元素和運(yùn)算的標(biāo)記不同外，其它一切都是相同的。因此，可以根據(jù)這些特征來識(shí)別同構(gòu)的代數(shù)結(jié)構(gòu)。第73頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五下面給出兩個(gè)二元運(yùn)算的代數(shù)結(jié)構(gòu)的同構(gòu)定義定義 設(shè)兩個(gè)代數(shù)結(jié)構(gòu)與，如果它們之間存在一個(gè)雙射f：XY，使得任意x1,x2X，有f(x1 x2)=f(x1) f(x2)f(x1 x2)=f(x1) f(x2)則說此兩個(gè)代數(shù)結(jié)構(gòu)是同構(gòu)的。第74頁

36、，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中S=，A，B，C，和是一般的集合運(yùn)算；又有，這里T = 1，2，5，10，且對(duì)于a，bT有a b = lcma，b(最小公倍數(shù))，a b = gcda，b(最大公約數(shù)) ，表至表給出四個(gè)運(yùn)算表。試說明.第75頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五表12.3.3表 表12.3.5表 ABC ABCAAACCBBCBCCCCCC ABC AAABBBCABC1 25101 1 25102221010551051010101010101 25101 1 11121212511551012510第76頁，共98頁

37、，2022年，5月20日，11點(diǎn)13分，星期五解：令fTS：f()=1，f(A)=2，f(B)=5，f(C)=10。顯然，f是從S到T的雙射。經(jīng)驗(yàn)證，對(duì)任意x1, x2S，又有f(x1x2)=f(x1) f(x2)f(x1x2)=f(x1) f(x2)故與是同構(gòu)的。第77頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五同構(gòu)是一個(gè)關(guān)系，而且可以證明它是個(gè)等價(jià)關(guān)系，對(duì)此有如下定理：定理 代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價(jià)關(guān)系。第78頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五證明 顯然，因?yàn)楹愕扔成涫峭瑯?gòu)映射。又若且f為其同構(gòu)映射，則f-1為從到的同構(gòu)映射。因此，。再令及，則。這里

38、因?yàn)槿鬴為到的同構(gòu)映射，g為到的同構(gòu)映射，則gf為從到的同構(gòu)映射。可見同構(gòu)關(guān)系滿足自反性、對(duì)稱性和傳遞性。因此，同構(gòu)關(guān)系是等價(jià)關(guān)系。第79頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五由于同構(gòu)關(guān)系是等價(jià)關(guān)系，故令所有的代數(shù)結(jié)構(gòu)構(gòu)成一個(gè)集合S，于是可按同構(gòu)關(guān)系將其分類，得到商集S/ 。因?yàn)橥瑯?gòu)的代數(shù)結(jié)構(gòu)具有相同的性質(zhì)，故實(shí)際上代數(shù)結(jié)構(gòu)所需要研究的總體并不是S而是S/ 。在同態(tài)與同構(gòu)中有一個(gè)特例，即具有相同集合的任兩個(gè)代數(shù)結(jié)構(gòu)的同態(tài)與同構(gòu)，這便是自同態(tài)與自同構(gòu)。第80頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五定義 給定及fSS。f為自同態(tài)映射:=f為從到的同態(tài)映射。f為

39、自同構(gòu)映射:=f為從到的同構(gòu)映射。例 在例中，當(dāng)k 0時(shí)，f = kx是從到的自同態(tài)映射；當(dāng)k = 1或k = -1時(shí)，f = kx是從到的自同構(gòu)映射。第81頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五12.4 同余關(guān)系本節(jié)主要闡明同態(tài)與同余關(guān)系之間的聯(lián)系。主要內(nèi)容如下：定義 給定，且E為S中的等價(jià)關(guān)系。E有代換性質(zhì):=(x1)(x2)(y1)(y2)(x1,x2,y1,y2Sx1Ex2y1Ey2)(x1y1)E(x2y2)。E為中的同余關(guān)系:=E有代換性質(zhì)。第82頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五與此同時(shí)，稱同余關(guān)系E的等價(jià)類為同余類。由定義可知，同余關(guān)

40、系是代數(shù)結(jié)構(gòu)的集合中的一類特殊的等價(jià)關(guān)系，并且在運(yùn)算的作用下，能夠保持關(guān)系的等價(jià)類。即在x1y1中，如果用集合S中的與x1等價(jià)的任何其它元素x2代換x1，并且用與y1等價(jià)的任何其它元素y2代換y1，則所求的結(jié)果x2y2與x1y1位于同一等價(jià)類之中。第83頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五亦即若x1E=x2E并且y1E=y2E，則x1y1E=x2y2E。此外，同余關(guān)系與運(yùn)算密切相關(guān)。如果一個(gè)代數(shù)結(jié)構(gòu)中有多個(gè)運(yùn)算，則需要考察等價(jià)關(guān)系對(duì)于所有這些運(yùn)算是否都有代換性質(zhì)。如果有，則說該代數(shù)結(jié)構(gòu)存在同余關(guān)系；否則，同余關(guān)系不存在。第84頁，共98頁，2022年，5月20日，11點(diǎn)1

41、3分，星期五x1Ex1x2x1y1Ex1y1x2y2y1Ey1y2同余關(guān)系示意圖第85頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五例 給定，其中Z是整數(shù)集合，+和是一般加、乘法。假設(shè)Z中的關(guān)系R定義如下：i1Ri2:=|i1|=|i2|，其中i1、i2Z試問，R為該結(jié)構(gòu)的同余關(guān)系嗎？第86頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五解 顯然，R為Z中的等價(jià)關(guān)系。接著先考察R對(duì)于+運(yùn)算的代換性質(zhì)：若取i1,-i1,i2Z ，則有|i1|=|-i1|和|i2|=|i2|，于是，下式(i1R(-i1)(i2Ri2)(i1+i2)R(-i1+i2)不真。這是因?yàn)榍凹檎?，?/p>

42、件為假。故R對(duì)于+運(yùn)算不具有代換性質(zhì)。第87頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五至此可以說，R不是該結(jié)構(gòu)的同余關(guān)系。但為了熟悉驗(yàn)證一個(gè)關(guān)系是否為同余關(guān)系，還是來考察R對(duì)于的代換性質(zhì)。令i1,i2,j1,j2Z且i1Ri2和j1Rj2。于是，對(duì)任意i1,i2,j1,j2都有：(i1Ri2)和(j1Rj2)(i1j1)R(i2j2)因此，E對(duì)于具有代換性質(zhì)。第88頁，共98頁，2022年，5月20日，11點(diǎn)13分，星期五可見，考察一個(gè)等價(jià)關(guān)系E對(duì)于有多個(gè)運(yùn)算的代數(shù)結(jié)構(gòu)是否為同余關(guān)系，這里有個(gè)次序先后問題，選擇得好，馬上就考察到了E對(duì)某個(gè)運(yùn)算是不具有代換性質(zhì)，那么便可立刻斷定E不是該結(jié)構(gòu)的同余關(guān)系，否則驗(yàn)證應(yīng)繼續(xù)下去，直至遇到不具有