《離散數(shù)學(xué)》課件第七章

1、抽象代數(shù)Abstract Algebra本部分所要探討的數(shù)學(xué)結(jié)構(gòu)是由集合上定義若干運(yùn)算而組成的系統(tǒng)稱為代數(shù)系統(tǒng)(代數(shù)結(jié)構(gòu))。 幾個(gè)問題6.項(xiàng)鏈問題：用n種顏色的珠子做成有m顆珠子的項(xiàng)鏈，問可做成多少種不同類型的項(xiàng)鏈?2.正多面體著色問題：對一個(gè)正多面體的項(xiàng)點(diǎn)或面用n種顏色進(jìn)行著色，問有多少 種不同的著色方法?3.圖的構(gòu)造與計(jì)數(shù)問題 4.開關(guān)線路的構(gòu)造與計(jì)數(shù)問題：用n個(gè)開關(guān)可以構(gòu)造出多少種不同的開關(guān)線路?5.數(shù)字通信的可靠性：如何設(shè)計(jì)高效的檢錯(cuò)碼與糾錯(cuò)碼？6.代數(shù)方程根式求解問題：五次方程有根嗎？7.網(wǎng)絡(luò)規(guī)劃8.信息安全9.語言：某語言L的語法語義？程序的結(jié)構(gòu)（數(shù)據(jù)表示？算法構(gòu)造？），根據(jù)L編寫

2、的程序是正確的嗎？10.計(jì)算復(fù)雜性：該問題可計(jì)算嗎？計(jì)算機(jī)能/不能計(jì)算嗎？計(jì)算復(fù)雜性如何？主要內(nèi)容第6講 代數(shù)結(jié)構(gòu)第7講 群代數(shù)第8講 格與布爾代數(shù) 第6講 代數(shù)結(jié)構(gòu)重點(diǎn)：代數(shù)結(jié)構(gòu)的判定與構(gòu)造代數(shù)結(jié)構(gòu)關(guān)系：同態(tài)、同構(gòu)特殊關(guān)系：同余關(guān)系難點(diǎn)：同余關(guān)系、同態(tài)基本定理6.6.1 集合運(yùn)算代數(shù)結(jié)構(gòu)定義例1Z;+,*,-,N,-, T,F; , P(A); ,，*; * 需要滿足的條件？1) 有一個(gè)非空集合S，稱為載體()； 2）一些定義在載體S上的運(yùn)算。某個(gè)集合上的運(yùn)算在某個(gè)集合下的封閉性？運(yùn)算封閉性：若x，yA，有x * yA，稱*在A上是封閉的設(shè)o是集合A上的一個(gè)n元運(yùn)算，非空集合S A，如果對于

3、每一個(gè)(a1，a2，an)S，都有o(a1，a2，an)S，則稱S在運(yùn)算o下是封閉的，或o在集合S上是封閉的。 代數(shù)結(jié)構(gòu)？S;O集合S？ 運(yùn)算O？ 6.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)例2 ： A=xx=2n，nN， 問一般乘法運(yùn)算*在A上封閉否，加法+、除法/ 呢？ 解：2r，2sA， 2r * 2s=2r+sA （） *在A上運(yùn)算封閉 2，4A，2+4A，+在A上不封閉 2，4A，2/4A， /在A上不封閉 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu) 定義7.4 設(shè)V=, SS, 如果運(yùn)算*1,*2,*n在S上封閉，則稱為V的子代數(shù)結(jié)構(gòu)，簡稱為V的子代數(shù)(Subalgebra)。 根據(jù)上述子代數(shù)的定義，

4、代數(shù)結(jié)構(gòu)V上運(yùn)算滿足的性質(zhì)，其子代數(shù)結(jié)構(gòu)也滿足。 例7.7 設(shè)N為自然數(shù)集合，為非負(fù)奇數(shù)集，E為非負(fù)偶數(shù)集，則對于代數(shù)結(jié)構(gòu)（+為一般加法運(yùn)算），為其子代數(shù)，但不是其子代數(shù)，因?yàn)楹笳?在上不滿足封閉性。 7.1 什么是代數(shù)結(jié)構(gòu)？運(yùn)算性質(zhì)、特殊元素滿足封閉性結(jié)合律交換律(左/右)分配律、消去律、吸收律冪等元(Idempotent element)(左/右)單位元(Identity element) (左/右)零元 (Zero element) (左/右)逆元 (Inverse) 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu) 類似于初等代數(shù)以及集合論、數(shù)理邏輯中討論的運(yùn)算之性質(zhì)，對于二元運(yùn)算以及*： 若對于任意

5、a, bA有：ab=ba, 則稱在A上是可交換的(或稱滿足交換律)。 若對于任意aA有：aa=a, 則稱在A上是滿足冪等律的。 若對于任意a, b, cA有：當(dāng)ab=ac時(shí)，有b=c, 則稱在A上是左可消去的(或稱滿足左消去律)，若在A上是滿足左可消去律與右可消去律，則稱在A上是可消去的(或稱滿足消去律)。 7.1 什么是代數(shù)結(jié)構(gòu)？ 若對于任意a, b, cA, 有：a(b*c)=(ab)*(ac); (b*c)a=(ba)*(ca)。則稱對于*是可分配的(或稱滿足分配律)。 若對于任意a, b, cA有：a(bc)=(ab)c, 則稱為在A上是可結(jié)合的(或稱滿足結(jié)合律)。若集合A上的二元運(yùn)算

6、*滿足結(jié)合律, 則我們常用a*b*c來表示(a*b)*c=a*(b*c)。 7.1 什么是代數(shù)結(jié)構(gòu)？ 7.2.3 代數(shù)結(jié)構(gòu)的特殊元素 1. 單位元 定義7.5 設(shè)是集合A上的二元運(yùn)算，如果存在一個(gè)元素elA，使得對于任意的aA滿足ela=a，則稱el是A上關(guān)于運(yùn)算的左單位元；如果存在一個(gè)元素erA，使得對于任意的aA有aer=a，則稱er是A上關(guān)于運(yùn)算的右單位元；如果存在一個(gè)元素eA，使得對于任意的aA有ea=ae=a，則稱e是A上關(guān)于運(yùn)算的單位元。7.1 什么是代數(shù)結(jié)構(gòu)？ 定理7.1 設(shè)是集合A上的二元運(yùn)算，又設(shè)el和er分別是的左單位元和右單位元，則el=er=e，且e是的惟一的單位元。

7、2. 逆元 定義7.6 設(shè)是集合A上有單位元e的二元運(yùn)算，對于元素aA，如果存在一元素al-1A，使得al-1a=e，則稱a是左可逆的，并稱al-1是a的一個(gè)左逆元；如果存在一元素ar-1A，使得aar-1=e，則稱元素a是右可逆的，并稱ar-1是a的一個(gè)右逆元，如果存在一元素a-1A，使得a-1a=aa-1=e，則稱元素a關(guān)于運(yùn)算是可逆的，而稱a-1是a的一個(gè)逆元。7.1 什么是代數(shù)結(jié)構(gòu)？ 定理7.2 設(shè)是集合A上的具有單位元e且可結(jié)合的二元運(yùn)算，如果元素aA有左逆元和右逆元，則其左、右逆元相等，并且若令al-1=ar-1= a-1，則a-1就是a惟一的逆元。 由逆元的定義我們得知，如果aA

8、有逆元 a-1，則aa-1=a-1a=e，因此(a-1)-1=a(即a是 a-1的逆元)。 例如，每一個(gè)實(shí)數(shù)rR均有一個(gè)關(guān)于加法運(yùn)算的逆元-r，每一個(gè)非零實(shí)數(shù)rR，均有一個(gè)關(guān)于乘法運(yùn)算的逆元1/r。 顯然，對于任何二元運(yùn)算，單位元是可逆的，其逆元就是單位元本身。 7.1 什么是代數(shù)結(jié)構(gòu)？ 3. 零元 定義7.7 設(shè)是集合A上的二元運(yùn)算，如果存在一個(gè)元素zlA，使得對于所有的aA，有zla=zl，則稱zl是A上關(guān)于運(yùn)算的左零元；如果存在一個(gè)元素zrA，使得對于所有的aA均有azr=zr，則稱zr是A上關(guān)于運(yùn)算的右零元；如果存在一個(gè)元素zA，使得對于所有的aA均有za=az=z，則稱z是A上關(guān)于運(yùn)

9、算的零元(Zero Element)。 7.1 什么是代數(shù)結(jié)構(gòu)？ 定理7.3 若是集合A上的二元運(yùn)算，又設(shè)zl和zr分別是的左零元和右零元，則zl=zr=z，且z是的惟一的一個(gè)零元。 7.1 什么是代數(shù)結(jié)構(gòu)？4. 冪等元 定義7.8 設(shè)是集合A上的二元運(yùn)算，如果aa=a，則稱a是A上的二元運(yùn)算的一個(gè)冪等元(Idempotent element)。 顯然，單位元和零元均是冪等元。 7.1 什么是代數(shù)結(jié)構(gòu)？c) 代數(shù)結(jié)構(gòu)A=a，b，c； 。 用下表定義：。abcaabbbabccaba從運(yùn)算表可以看出，b是左單位元，無右單位元；a是右零元，b是右零元，無左零元; 運(yùn)算：不滿足交換律？ 7.1 什么

10、是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)d) 代數(shù)R，*中，除零元0外所有元素均有逆元 e) A=a，b，c，*由下表定義： *abcaaabbabccaccb是單位元,a的右逆元為c，無左逆元，b的逆元為b，c的右逆元為空，左逆元為a 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)運(yùn)算性質(zhì)、特殊元素滿足封閉性：運(yùn)算表中每一個(gè)元素aS結(jié)合律：構(gòu)造表來判斷交換律：關(guān)于主對角線對稱(左/右)分配律、消去律、吸收律等冪律(冪等元)：主對角線上元素與其所在表頭元素同(左/右)單位元:某元素x，其相應(yīng)行/列與表列/行頭元素同(左/右)零元:某元素x，與其所在的行/列元素全相同(左/右)逆元:首先,是否存在單位元？元素x所在的列/行的單位

11、元相應(yīng)的行/列頭元素即其逆元7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)請思考：如何應(yīng)用運(yùn)算表（矩陣）來判斷左述性質(zhì)？例3a）P（S）；,對運(yùn)算，是單位元， S是零元，對運(yùn)算，S是單位元 ，是零元。b）N；+有單位元0，無零元。 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)f）代數(shù)結(jié)構(gòu)：A= *k稱為模k乘法求余（x*ky或記為resk(x*y)。 零元？單位元？關(guān)于逆元？當(dāng)且僅當(dāng)x與k互質(zhì)時(shí)，x有逆元 7.1 什么是代數(shù)結(jié)構(gòu)？實(shí)數(shù)集R上的二元運(yùn)算*：a*b=a+b-ab是否有單位元、零元與冪等元，如果有單位元，哪些元素有逆元？代數(shù)結(jié)構(gòu)半群(Semigroup)、單位半群(獨(dú)異點(diǎn),Monoid)結(jié)合性、單位元 7.1

12、 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)例5a) 代數(shù)結(jié)構(gòu)N；*,0，1；*是半群，是獨(dú)異點(diǎn)嗎？是R; *的子半群,子獨(dú)異點(diǎn)嗎？代數(shù)結(jié)構(gòu)R; -是半群嗎？*，-為一般乘法、減法b) 設(shè)s=a，b，*定義如右表，是半群嗎? 注意到a，b都是右零元 x,y,zs x*ys 運(yùn)算封閉 x*（y*z）=x*z=z （x*y）*z=z 結(jié)合律成立 是一半群，該半群稱為二元素右零半群*abaabbab 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)練習(xí)1 獨(dú)異點(diǎn)運(yùn)算表中任何兩行兩列均不相同.2 是一個(gè)半群嗎?3 若半群A，*的單位元為e,a，bA，若a，b均有逆元，則 1)（a-1）-1=a; 2)（a*b）-1=b-1*a-1 。

13、 試證明之.4 有限半群必有冪等元? 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)有限半群必有冪等元.證明設(shè)是有限半群，需證 aS，有a*a=a。對bS，由運(yùn)算封閉性，有b2=b*bS,進(jìn)一步可得b3，b4，S。又S有限，故存在i，jN，j 使得bi=bj。從而利用半群的可結(jié)合性有 bi=bj=bj-i*bi。現(xiàn)令p=j-i，則對任意qN，qi時(shí), 有bq= bq-i*bi=bq-i*bj=bq- i*bj-i*bi=bq-i*bp*bi=bp*bq。又p1，則存在qi，qN，且有kN，使 q=kp，從而有bkp=bp*bkp=bp*(bp*bkp)=bkp*bkp，令a=bkpS 則a*a=a，即a=b

14、kp是的冪等元。 7.1 什么是代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)為什么需要研究代數(shù)結(jié)構(gòu)之間的關(guān)系？ 在研究代數(shù)結(jié)構(gòu)的過程中，所關(guān)心的常常是代數(shù)結(jié)過中運(yùn)算所滿足的性質(zhì)，不關(guān)心具體的運(yùn)算，而對于遵循相同運(yùn)算規(guī)律的系統(tǒng)只需要研究其中一個(gè)就可以了解其它的系統(tǒng).抽象代數(shù)！ 考察下列代數(shù): A1=I; A2=Q;+; A3=R+;min;A4=P(S); A5=P(S);. 此5個(gè)代數(shù)都有相同的構(gòu)成成分:同樣個(gè)數(shù)的運(yùn)算且對應(yīng)運(yùn)算元數(shù)相 (1個(gè)二元運(yùn)算); 滿足同樣的公理規(guī)則(交換律,結(jié)合律);存在單位元。 稱具有上述性質(zhì)的代數(shù)是同一類(代數(shù)結(jié)構(gòu)的類) 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系映射代數(shù)結(jié)構(gòu)例 5 邏輯代數(shù)開關(guān)電路V1=與

15、V2=兩個(gè)代數(shù)結(jié)構(gòu)之間存在一個(gè)映射：g：0,1 M,H對于a,b 0,1,有g(shù)(a Vb)=g(a)*g(b)V01001111*MHMMHHHH7.2.1 同態(tài)關(guān)系、同構(gòu)關(guān)系 對于兩代數(shù)結(jié)構(gòu)設(shè)V1=和 V2= 1)是同型的代數(shù)結(jié)構(gòu)（運(yùn)算個(gè)數(shù)、對應(yīng)的運(yùn)算的元數(shù)都相同） 2)存在從A到B的一個(gè)映射/滿射/單射/雙射f 3)運(yùn)算性質(zhì)保持（保運(yùn)算性，滿足同態(tài)方程）：對于ki元運(yùn)算Oi(i=1，2，r)，若任意(x1，x2，xki)Aki，都有 f(Oi(x1，x2，xki)= *i(f(x1)，f(xki)， 則稱f是V1到V2的一個(gè)同態(tài)/滿同態(tài)/單同態(tài)/同構(gòu)映射，并稱V1與V2 同態(tài)(Homomo

16、rphic) /滿同態(tài)/單同態(tài)/同構(gòu)的(Isomorphic) 。 例6：代數(shù)結(jié)構(gòu)R+; *,R;+同構(gòu)嗎？ 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu)證明：顯然， 與為同型代數(shù)結(jié)構(gòu)，下面證明二者之間存在雙射關(guān)系且滿足同態(tài)方程。i)建立雙射關(guān)系： 令h:R+R,h(x)=lnx 顯然，h是單射 yR,x=ey使y=lney =lnx=h(x) h是滿射 h是從R+到R的雙射ii)h滿足同態(tài)方程： a,bR+ ,h(a*b)=ln(a*b)=lna+lnb=h(a)+h(b)綜上，同構(gòu)于 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu)這樣，利用同態(tài)/同構(gòu)關(guān)系，可以轉(zhuǎn)移運(yùn)算，復(fù)雜的代數(shù)系統(tǒng)可以壓縮為另一簡單的代數(shù)系統(tǒng)。A

17、ABBff*+思考：請你舉例說明上述系統(tǒng)轉(zhuǎn)換思想。 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu)數(shù)學(xué)、信號處理中的一些變換：拉普拉斯變換時(shí)頻分析坐標(biāo)變換離散余弦變換小波變換 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu)例7a) 請判斷T,F; ,T,F; 是否同構(gòu)。b) 請判斷*; ,N;+是否同構(gòu)，運(yùn)算“”表示字符串的連接， “+” 為一般的加法運(yùn)算。c) 代數(shù)結(jié)構(gòu)I;+,*,Nm;+m, *m是否同態(tài)？其中， 運(yùn)算+m, *m分別是模m加、乘。d)I;+,2I;+同構(gòu)嗎？e) 設(shè)與是代數(shù)結(jié)構(gòu)，其中I+為正整數(shù)集，E+為正偶數(shù)集，*分別為一般的乘法運(yùn)算，h為R上的映射，對任意xI+， h(x)=2x。試證明：h不是

18、到的同構(gòu)映射，并證明與不同構(gòu)。 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu) b) 代數(shù)結(jié)構(gòu)與是同態(tài)關(guān)系。 證明：顯然它們是同型函數(shù)，并存在一個(gè)映射：f(s)=|s|，其中s為由*中元素所組成的串，|s|為串s的長度。此映射是多一對應(yīng)的，且對任意s1，s2*, 顯然有： f(s1s2)=|s1s2|=| s1|+| s2|=f(s1)+f(s2)， 所以與同態(tài)，并且還是滿同態(tài)。 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系e)證明 顯然，h是I+到E的雙射，對任意x，yI+，有h(x*y)=2xy，但h(x)*h(y)=4xy, 顯然h(x*y)h(x)*h(y)。故，h不是到的同構(gòu)映射。h不是到的同構(gòu)映射能說明與就一定不同

19、構(gòu)嗎？ 不一定，因?yàn)?，同?gòu)定義中只要求“保持運(yùn)算”的映射存在，但未要求所有雙射都是“保持運(yùn)算”的，因此，必須證明這種“保持運(yùn)算”的雙射不存在，才能說明與不同構(gòu)。 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu)7.2.2 同態(tài)與同構(gòu)的性質(zhì)定理7.4 設(shè)g為代數(shù)結(jié)構(gòu)到的同構(gòu)映射，即存在一個(gè)一一映射g:XY，使得x1,x2X，則有g(shù)(x1x2)=g(x1)*g(x2)。 若存在單位元ex，則亦存在單位元ey，且有ey = g(ex) 。 證明：對 yY，x Y，使得y=g(x),于是，由與同構(gòu)，且有單位元ex，有 g(ex)*y= g(ex)*g(x)=g(exx)=g(x),且y*g(ex)= g(x)*g(e

20、x) =g(xex)=g(x)，故g(ex)*y= y*g(ex)=y。所以的存在單位元ey且 g(ex)= ey。 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系代數(shù)結(jié)構(gòu)7.2.2 性質(zhì)保持1 對于同構(gòu)： 保持結(jié)合律、交換律、分配律；單位元、逆元、零元相應(yīng)存在（教材的證明請自學(xué)）同構(gòu)關(guān)系是一種等價(jià)關(guān)系？2 對于同態(tài) 滿同態(tài)單向保持性質(zhì) 7.2 代數(shù)結(jié)構(gòu)間的關(guān)系XYf代數(shù)結(jié)構(gòu)6.3 同余關(guān)系 集合上的等價(jià)關(guān)系？等價(jià)類商集添加運(yùn)算之后？ 1 為什么研究同余關(guān)系？等價(jià)關(guān)系同余關(guān)系補(bǔ)碼、隨機(jī)數(shù)、文件系統(tǒng)、hash、密碼、檢錯(cuò)碼歐拉函數(shù)和費(fèi)馬定理代數(shù)結(jié)構(gòu)同態(tài)三角形（同態(tài)基本定理）V=V=V/h=h(滿同態(tài))g (自然滿同態(tài)

21、)f (同構(gòu))集合論： 函數(shù)等價(jià)關(guān)系劃分代數(shù)結(jié)構(gòu)： 同態(tài)同余關(guān)系可允許劃分如何尋找一個(gè)代數(shù)結(jié)構(gòu)的壓縮結(jié)構(gòu)？變換6.3 同余關(guān)系代數(shù)結(jié)構(gòu)6.3.1 同余關(guān)系原始含義（示例）： 代數(shù)結(jié)構(gòu)在Z上的關(guān)系R定義如下： xRy xy(mod k)， 且滿足如下推理： xRy且 zRw (x+z)R(y+w)（*） 這樣，上述利用余數(shù)相等建立的滿足（*）推理式的關(guān)系R稱為同余關(guān)系。6.3 同余關(guān)系代數(shù)結(jié)構(gòu)推廣1 命題邏輯公式的等值關(guān)系是邏輯代數(shù)上的同余關(guān)系嗎？2 恒等關(guān)系是集合代數(shù)上的同余關(guān)系嗎？3 , R=(x, y)|x/y=2m, mZ6.3 同余關(guān)系代數(shù)結(jié)構(gòu)同余關(guān)系(Congruence) 是一個(gè)代

22、數(shù)系統(tǒng),R是A上的等價(jià)關(guān)系,若R, RR，稱R是A上的同余關(guān)系(R對于運(yùn)算*滿足代換性質(zhì)).同余關(guān)系將A劃分得到的等價(jià)類稱為 可允許劃分(同余類)： 對于代數(shù)結(jié)構(gòu), =A1,A2,An是A上的一個(gè)劃分，若對于任意的劃分塊Ai, Aj ,存在Ak ,使得：Ai*AjAk,則稱為可允許劃分。6.3 同余關(guān)系代數(shù)結(jié)構(gòu)例12：，在I上定義R:R|x|=|y|, 問R是的等價(jià)關(guān)系嗎？是否是同余關(guān)系?解: 1)自反性：xI, |x|=|x| ，從而R 2)對稱性：x,yI，若R則|x|=|y|，從而R 3)傳遞性：x,y,zI，若R,R 由|x|=|y|=|z| 知R 所以 R是一等價(jià)關(guān)系。 對x1,y1

23、,x2,y2I，若R,R， 但R不一定成立，例如， R,R但R 綜上，R是等價(jià)關(guān)系但不是同余關(guān)系6.3 同余關(guān)系代數(shù)結(jié)構(gòu)定理 設(shè)R是代數(shù)結(jié)構(gòu)上的等價(jià)關(guān)系，*為二元運(yùn)算，對于a，b S/R, 其中S/R是可允許劃分定義a ob=a*b則o為S/R上的二元運(yùn)算當(dāng)且僅當(dāng)R為上同余關(guān)系。 6.3 同余關(guān)系代數(shù)結(jié)構(gòu)證明 必要性 設(shè)o為上二元運(yùn)算。對a, b, c, d S,若aRb，cRd，即a=b,c=d, 則a oc=b od, 又有a oc=a*c, b od=b*d。從而a*c=b*d。于是a*cRb*d。故R為上同余關(guān)系。充分性 設(shè)R為上同余關(guān)系，任意a,b S/R， 顯然a ob=a*b S

24、/R，即o在S/R上滿足封閉性，還需證對任意a,b S/R，a ob值唯一。注意到，a ob=a*b，a*b值是惟一的，a*b是惟一的。因此，需要證明若a，b取其它代表元，如a,b，其值a*b與a*b是否相等。對aa, bb,有aRa, bRb, 則a*bRa*b 。于是a ob=a*b =a*b=a ob。這說明a ob的運(yùn)算結(jié)果與等價(jià)類的代表元無關(guān)，值是唯一的。故o是S/R上的二元運(yùn)算。綜上，命題得證。6.3 同余關(guān)系代數(shù)結(jié)構(gòu)6.3.2 同余關(guān)系商代數(shù)(Quotient Algebra)思考是否可以根據(jù) 上的同余關(guān)系定義一個(gè)的滿同態(tài)代數(shù)結(jié)構(gòu)（商代數(shù)）？6.3 同余關(guān)系代數(shù)結(jié)構(gòu)同余關(guān)系商代數(shù)

25、(Quotient algebra) 代數(shù)結(jié)構(gòu)：V= （o為一元運(yùn)算）V上同余關(guān)系：商代數(shù)：V/=運(yùn)算o的定義？ o(x)=o(x)代數(shù)結(jié)構(gòu)：V= （o為二元運(yùn)算）V上同余關(guān)系：商代數(shù)：V/=運(yùn)算*的定義？ x o y=xoy6.3 同余關(guān)系代數(shù)結(jié)構(gòu)6.3.2 同態(tài)基本定理設(shè)代數(shù)結(jié)構(gòu)V=, V=, h是從V到V的滿同態(tài)映射，則1) 在S上定義一個(gè)關(guān)系h，使得當(dāng)且僅當(dāng)h(x)=h(y)時(shí)xhy，則h是V上的同余關(guān)系（同余定理）；2) 由h可以得到V的商代數(shù)，記為V/h，且存在V到V/h的滿同態(tài)映射(自然同態(tài))g；3) V/h與V同構(gòu)。6.3 同余關(guān)系同態(tài)三角形V=V=V/h=h(滿同態(tài))g (自

26、然滿同態(tài))f (同構(gòu))集合論： 函數(shù)等價(jià)關(guān)系劃分代數(shù)結(jié)構(gòu)： 同態(tài)同余關(guān)系可允許劃分6.3 同余關(guān)系代數(shù)結(jié)構(gòu) 同態(tài)三角形的同構(gòu)性的證明：1 同型：Vh 與 V同型？2 雙射： 定義映射f，并證明其為雙射定義映射f：因?yàn)閔是一個(gè)從S到S的滿射， S/h為可允許劃分，所以對于每一個(gè)xh S/h必存在唯一xS，使得x=h(x)，于是可以如下定義函數(shù)：f: S/h S ，使得f(xh)=x=h(x)。 f為滿射：對于任意xS ，必存在 xS，使得h(x) =x，從而存在x h S/h，使得f(xh)=h(x)=x ，所以f是滿射。f為單射：若h(x)=h(y)，則xhy，于是xh=yh，所以f是單射3

27、滿足同態(tài)方程由于 f(xh yh)=f(xoyh)=h(xoy)=h(x)*h(y)=f(xh)*f(yh)所以，前述運(yùn)算與雙射滿足同態(tài)方程。綜上， Vh 與 V同構(gòu)。6.3 同余關(guān)系代數(shù)結(jié)構(gòu)思考如果上述同構(gòu)證明過程中，將映射改f改為從S 到S/h ，則如何描述具體證明過程？代數(shù)結(jié)構(gòu)補(bǔ)充例題1 設(shè)*是自然數(shù)集合N中的二元運(yùn)算，并定義x*y=x。試證明*是可結(jié)合的，但不是可交換的。2 M為單位半群，證明b=a-1的充分必要條件是aba=a和ab2a=e。3 代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價(jià)關(guān)系。4 考慮代數(shù)結(jié)構(gòu)V=Z3 ；3，3和Z3上的等價(jià)關(guān)系。1) 證明若對于3滿足代換性質(zhì)，則它對3一定也滿足代換

28、性質(zhì)。2) 找出一個(gè)Z3上的等價(jià)關(guān)系，它對于3滿足代換性質(zhì)，但對3不滿足。代數(shù)結(jié)構(gòu)補(bǔ)充例題2 M為單位半群，證明b=a-1的充分必要條件是aba=a和ab2a=e。證 必要性：將b代入即可得。充分性：利用結(jié)合律作以下運(yùn)算：ab=ab(ab2a)=(aba)b2a=ab2a=e，ba=(ab2a)ba=ab2 (aba)=ab2a=e，所以b=a-1。 證畢代數(shù)結(jié)構(gòu)補(bǔ)充例題3 代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價(jià)關(guān)系。證明 設(shè)X；，Y；*，Z；+是任意的三個(gè)代數(shù)結(jié)構(gòu)，并設(shè)同構(gòu)關(guān)系用“”表示，下面證明滿足自反性、對稱性以及傳遞性。代數(shù)結(jié)構(gòu)補(bǔ)充例題 (1) 自反性：顯然有X；X；)，即是自反的。 (2) 對稱

29、性：如果X；Y；*則必存在一個(gè)雙射 g: XY，使得若x1，x2X，并有：g(x1x2)=g(x1)*g(x2)根據(jù)雙射的定義，必存在一個(gè)雙射的逆映射g-1: YX?，F(xiàn)要證對g-1: YX，若y1，y2Y，必有： g-1(y1*y2)=g-1(y1)g-1(y2)設(shè)對任意的y1，y2Y必存在x1，x2X，使得g(x1)=y1，g(x2)=y2，亦即g-1(y1)=x1，g-1(y2)=x2，故有： g-1(y1*y2) = g-1(g(x1)*g(x2) =g-1(g(x1x2) =x1x2 又g-1(y1)g-1(y2)=x1x2所以g-1(y1*y2)=g-1(y1)g-1(y2)因此，Y；*X；，所以是對稱的。代數(shù)結(jié)構(gòu)補(bǔ)充例題 (3) 傳遞性：如果有X；Y；*，且Y；*Z；+，要證明X；Z；+。由條件亦即存在雙射g: