課件代數(shù)結(jié)構(gòu)第七章

1、 DM抽象代數(shù)Abstract Algebra本部分所要探討的數(shù)學(xué)結(jié)構(gòu)本部分所要探討的數(shù)學(xué)結(jié)構(gòu)是是由集合上定義若干運算而由集合上定義若干運算而組成的系統(tǒng)組成的系統(tǒng)稱為代數(shù)系稱為代數(shù)系統(tǒng)統(tǒng)( (代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)) )。 幾個問題用用n n種顏色的珠子做成有種顏色的珠子做成有m m顆珠子的項鏈，問可做成多少顆珠子的項鏈，問可做成多少種不同類型的項鏈種不同類型的項鏈? ?：對一個正多面體的項點或面用對一個正多面體的項點或面用n n種顏色進行著種顏色進行著色，問有多少色，問有多少 種不同的著色方法種不同的著色方法? ? ：用：用n n個開關(guān)可以構(gòu)造出多少種不同的個開關(guān)可以構(gòu)造出多少種不同的開關(guān)線路開關(guān)

2、線路? ?如何設(shè)計高效的檢錯碼與糾錯碼？如何設(shè)計高效的檢錯碼與糾錯碼？：五次方程有根嗎？：五次方程有根嗎？某語言某語言L L的語法語義？程序的結(jié)構(gòu)（數(shù)據(jù)表示？算法構(gòu)的語法語義？程序的結(jié)構(gòu)（數(shù)據(jù)表示？算法構(gòu)造？），根據(jù)造？），根據(jù)L L編寫的程序是正確的嗎？編寫的程序是正確的嗎？該問題可計算嗎？計算機能該問題可計算嗎？計算機能/ /不能計算嗎？計算復(fù)雜不能計算嗎？計算復(fù)雜性如何？性如何？重點：重點：難點：難點：6.6.1 集合集合運算運算代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)定義定義例例1Z;+,*,-,N,-, T,F; , P(A); ,，*; * 需要滿足的條件？需要滿足的條件？1) 有一個有一個非空集合非空集

3、合S，稱為，稱為載體載體()； 2）一些定義在載體）一些定義在載體S上的運算。上的運算。某個集合上的某個集合上的運算運算在某個集合下的在某個集合下的封閉性封閉性？運算封閉性運算封閉性：若：若 x，yA，有，有x * yA，稱，稱*在在A上是封閉的上是封閉的設(shè)設(shè)o是集合是集合A上的一個上的一個n元運算，非空集合元運算，非空集合S A，如果對于每一個，如果對于每一個(a1，a2，an)S，都有，都有o(a1，a2，an)S，則稱，則稱S在運算在運算o下是封閉的下是封閉的，或，或o在集合在集合S上是封閉的上是封閉的。 代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)？S;O集合集合S？ 運算運算O？例例2 ： A=xx=2n，n

4、N， 問一般乘法運算問一般乘法運算*在在A上封閉否，加法上封閉否，加法+、除法、除法/ 呢？呢？ 解：解： 2r，2sA， 2r * 2s=2r+sA （） *在在A上運算封閉上運算封閉 2，4A，2+4 A，+在在A上不封閉上不封閉 2，4A，2/4 A， /在在A上不封閉上不封閉 定義定義7.47.4 設(shè)設(shè)V=, S S, 如果運如果運算算*1,*2,*n在在S上封上封閉閉， ，則則稱稱為為V的的子代數(shù)子代數(shù)結(jié)結(jié)構(gòu)構(gòu)， ，簡簡稱稱為為V的的子代數(shù)子代數(shù)(Subalgebra)。 。 根據(jù)上述子代數(shù)的定根據(jù)上述子代數(shù)的定義義，代數(shù)，代數(shù)結(jié)結(jié)構(gòu)構(gòu)V上運上運算算滿滿足的性足的性質(zhì)質(zhì)，其子代數(shù)，其

5、子代數(shù)結(jié)結(jié)構(gòu)也構(gòu)也滿滿足。足。 例例7.77.7 設(shè)設(shè)N為為自然數(shù)集合，自然數(shù)集合，為為非非負(fù)負(fù)奇數(shù)集，奇數(shù)集，E為為非非負(fù)負(fù)偶數(shù)集，偶數(shù)集，則對則對于代數(shù)于代數(shù)結(jié)結(jié)構(gòu)構(gòu)（ （+為為一一般加法運算），般加法運算），為為其子代數(shù)，但其子代數(shù)，但不不是其子代數(shù)，因是其子代數(shù)，因為為后者后者+在在上不上不滿滿足封足封閉閉性。性。 運算性質(zhì)、特殊元素運算性質(zhì)、特殊元素滿足封閉性滿足封閉性結(jié)合律結(jié)合律交換律交換律(左左/右右)分配律、消去律、吸收律分配律、消去律、吸收律冪等元冪等元(Idempotent element)(左左/右右)單位元單位元(Identity element) (左左/右右)零元零

6、元 (Zero element) (左左/右右)逆元逆元 (Inverse) 類類似于初等代數(shù)以及集合似于初等代數(shù)以及集合論論、數(shù)理、數(shù)理邏輯邏輯中中討討論論的運算之性的運算之性質(zhì)質(zhì)， ，對對于二元運算于二元運算以及以及*： ： 若若對對于任意于任意a, bA有：有：ab=ba, 則則稱稱在在A上是上是可交可交換換的的(或稱或稱滿滿足交足交換換律律)。 。 若若對對于任意于任意aA有：有：aa=a, 則則稱稱在在A上是上是滿滿足足冪冪等律等律的。的。 若若對對于任意于任意a, b, cA有：當(dāng)有：當(dāng)ab=ac時時，有，有b=c, 則則稱稱在在A上是上是左可消去的左可消去的(或稱或稱滿滿足左消足

7、左消去律去律)，若，若在在A上是上是滿滿足左可消去律與右可消去足左可消去律與右可消去律，律，則則稱稱在在A上是上是可消去的可消去的(或稱或稱滿滿足消去律足消去律)。 。 若若對對于任意于任意a, b, cA, 有：有：a(b*c)=(ab)*(ac); (b*c)a=(ba)*(ca)。 。則則稱稱對對于于*是是可分配的可分配的(或稱或稱滿滿足分配律足分配律)。 。 若若對對于任意于任意a, b, cA有：有：a(bc)=(ab)c, 則則稱稱為為在在A上是上是可可結(jié)結(jié)合的合的(或稱或稱滿滿足足結(jié)結(jié)合律合律)。若集合。若集合A上的二元運算上的二元運算*滿滿足足結(jié)結(jié)合律合律, 則則我我們們常用常

8、用a*b*c來表示來表示(a*b)*c=a*(b*c)。 。 7.2.37.2.3 代數(shù)結(jié)構(gòu)的特殊元素代數(shù)結(jié)構(gòu)的特殊元素 1. 1. 單位元單位元 定義定義7.57.5 設(shè)設(shè)是集合是集合A上的二元運算，如果上的二元運算，如果存在一個元素存在一個元素elA， ，使得使得對對于任意的于任意的aA滿滿足足ela=a， ，則則稱稱el是是A上關(guān)于運算上關(guān)于運算的的左左單單位元位元； ；如果存在一個元素如果存在一個元素erA， ，使得使得對對于任意的于任意的aA有有aer=a， ，則則稱稱er是是A上關(guān)于運算上關(guān)于運算的的右右單單位元位元；如果存在一個元素；如果存在一個元素eA， ，使得使得對對于任意于

9、任意的的aA有有ea=ae=a， ，則則稱稱e是是A上關(guān)于運算上關(guān)于運算的的單單位元位元。 。 定理定理7.17.1 設(shè)設(shè)是集合是集合A上的二元運算，上的二元運算，又設(shè)又設(shè)el和和er分別是分別是的左單位元和右單位的左單位元和右單位元，則元，則el=er=e，且，且e是是的惟一的單位元。的惟一的單位元。 2. 2. 逆元逆元 定義定義7.67.6 設(shè)設(shè)是集合是集合A上有上有單單位元位元e的二元運的二元運算，算，對對于元素于元素aA， ，如果存在一元素如果存在一元素al-1A， ，使使得得al-1a=e， ，則則稱稱a是是左可逆的左可逆的，并稱，并稱al-1是是a的一的一個左逆元；如果存在一元素

10、個左逆元；如果存在一元素ar-1A， ，使得使得aar-1=e， ，則則稱元素稱元素a是是右可逆的右可逆的，并稱，并稱ar-1是是a的一個的一個右逆元，如果存在一元素右逆元，如果存在一元素a-1A， ，使得使得a-1a=aa-1=e， ，則則稱元素稱元素a關(guān)于運算關(guān)于運算是是可逆的可逆的， ，而稱而稱a-1是是a的一個的一個逆元逆元。 。 定理定理7.27.2 設(shè)設(shè)是集合是集合A上的具有上的具有單單位元位元e且可且可結(jié)結(jié)合的二元運算，如果元素合的二元運算，如果元素aA有左逆元和右逆有左逆元和右逆元，元，則則其左、右逆元相等，并且若令其左、右逆元相等，并且若令al-1=ar-1= a-1， ，則

11、則a-1就是就是a惟一的逆元。惟一的逆元。 由逆元的定由逆元的定義義我我們們得知得知， ，如果如果aA有逆元有逆元 a-1， ，則則aa-1=a-1a=e， ，因此因此(a-1)-1=a(即即a是是 a-1的逆的逆元元)。 。 例如，每一個例如，每一個實實數(shù)數(shù)rR均有一個關(guān)于加法運均有一個關(guān)于加法運算的逆元算的逆元-r， ，每一個非零每一個非零實實數(shù)數(shù)rR， ，均有一個關(guān)均有一個關(guān)于乘法運算的逆元于乘法運算的逆元1/r。 。 顯顯然，然，對對于任何二元運算，于任何二元運算，單單位元是可逆的，位元是可逆的，其逆元就是其逆元就是單單位元本身。位元本身。 3. 3. 零元零元 定義定義7.77.7

12、設(shè)設(shè)是集合是集合A上的二元運算，如果上的二元運算，如果存在一個元素存在一個元素zlA，使得對于所有的，使得對于所有的aA，有有zla=zl，則稱，則稱zl是是A上關(guān)于運算上關(guān)于運算的的左零元左零元；如果存在一個元素如果存在一個元素zrA，使得對于所有的，使得對于所有的aA均有均有azr=zr，則稱，則稱zr是是A上關(guān)于運算上關(guān)于運算的的右零元右零元；如果存在一個元素；如果存在一個元素zA，使得對于所，使得對于所有的有的aA均有均有za=az=z，則稱，則稱z是是A上關(guān)于上關(guān)于運算運算的的零元零元(Zero Element)。 定理定理7.37.3 若若是集合是集合A上的二元運算，上的二元運算，

13、又設(shè)又設(shè)zl和和zr分別是分別是的左零元和右零元，的左零元和右零元，則則zl=zr=z，且，且z是是的惟一的一個零元。的惟一的一個零元。 4. 冪等元冪等元 定義定義7.87.8 設(shè)設(shè)是集合是集合A上的二元運算，如上的二元運算，如果果aa=a，則稱，則稱a是是A上的二元運算上的二元運算的的一個一個冪等元冪等元(Idempotent element)。 顯然，單位元和零元均是冪等元。顯然，單位元和零元均是冪等元。 c) 代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)A=a，b，c； 。 用下表用下表定義：定義：。abcaabbbabccaba從運算表可以看出，從運算表可以看出，b是是左單位元，無右單位元；左單位元，無右單位元

14、；a是右零元，是右零元，b是右零元，是右零元，無左零元無左零元; 運算：不滿足交換律？運算：不滿足交換律？ d) 代數(shù)代數(shù)R，*中，除零元中，除零元0外所有元素均有逆元外所有元素均有逆元 e) A=a，b，c，*由下表定義：由下表定義： *a b ca a a bb a b cc a c cb是單位元是單位元,a的右逆元為的右逆元為c，無左逆元，無左逆元，b的逆元為的逆元為b，c的右逆元為空，左逆元為的右逆元為空，左逆元為a 運算性質(zhì)、特殊元素運算性質(zhì)、特殊元素滿足封閉性：滿足封閉性：運算表中每一個元素運算表中每一個元素aS結(jié)合律：結(jié)合律：構(gòu)造表來判斷構(gòu)造表來判斷交換律：交換律：關(guān)于主對角線對

15、稱關(guān)于主對角線對稱(左左/右右)分配律、消去律、分配律、消去律、吸收律吸收律等冪律等冪律(冪等元冪等元)：主對角線上元素與其所在表頭元素同主對角線上元素與其所在表頭元素同(左左/右右)單位元單位元:某元素某元素x，其相應(yīng)行，其相應(yīng)行/列與表列列與表列/行頭元素同行頭元素同(左左/右右)零元零元:某元素某元素x，與其所在的行，與其所在的行/列元素全相同列元素全相同(左左/右右)逆元逆元:首先首先,是否存在單位元？元素是否存在單位元？元素x所在的列所在的列/行的單位元行的單位元相應(yīng)的行相應(yīng)的行/列頭元素即其逆元列頭元素即其逆元例例3a）P（S）；）；,對運算對運算，是單位元，是單位元， S是零元，

16、是零元，對運算對運算，S是單位元是單位元 ，是零元。是零元。b）N；+有單位元有單位元0，無零元。，無零元。f）代數(shù)結(jié)構(gòu)：）代數(shù)結(jié)構(gòu)：A= *k稱為模稱為模k乘法求余（乘法求余（x*ky或記為或記為resk(x*y)。 零元？單位元？關(guān)于逆元？零元？單位元？關(guān)于逆元？當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x與與k互質(zhì)時，互質(zhì)時，x有逆元有逆元實數(shù)集實數(shù)集R上的二元運算上的二元運算*：a*b=a+b-ab是否有單位元、是否有單位元、零元與冪等元，如果有單位元，哪些元素有逆元？零元與冪等元，如果有單位元，哪些元素有逆元？半群半群(Semigroup)、單位半群、單位半群(獨異點獨異點,Monoid)結(jié)合性、單位元結(jié)合性

17、、單位元例例5a) 代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)N；*,0，1；*是半群，是獨異點嗎？是是半群，是獨異點嗎？是R; *的子半群的子半群,子獨異點嗎？子獨異點嗎？代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)R; -是半群嗎？是半群嗎？*，-為一般乘法、減法為一般乘法、減法b) 設(shè)設(shè)s=a，b，*定義如右表，定義如右表，是半群嗎是半群嗎? 注意到注意到a，b都是右零元都是右零元 x,y,z s x*y s 運算封閉運算封閉 x*（y*z）=x*z=z （x*y）*z=z 結(jié)合律成立結(jié)合律成立 是一半群，該半群稱為二元素右零半群是一半群，該半群稱為二元素右零半群*abaabbab練習(xí)練習(xí)1 獨異點運算表中任何兩行兩列均不相同獨異點運算表中

18、任何兩行兩列均不相同.2 是一個半群嗎是一個半群嗎?3 若半群若半群A，*的單位元為的單位元為e, a，b A，若若a，b均有均有逆元，則逆元，則 1)（a-1）-1=a; 2)（a*b）-1=b-1*a-1 。 試證明之試證明之.4 有限半群必有冪等元有限半群必有冪等元? 有限有限半群必有冪等元半群必有冪等元.證明證明 設(shè)設(shè)是有限半群，需證是有限半群，需證 a S，有，有a*a=a。對對 b S，由運算封閉性，有，由運算封閉性，有b2=b*b S,進一步可得進一步可得b3，b4， S。又又S有限，故存在有限，故存在i，j N，j 使得使得bi=bj。從而利用半群的可結(jié)合性有從而利用半群的可結(jié)

19、合性有 bi=bj=bj-i*bi。現(xiàn)令現(xiàn)令p=j-i，則對任意，則對任意q N，qi時時, 有有bq= bq-i*bi=bq-i*bj=bq- i*bj-i*bi=bq-i*bp*bi=bp*bq。又又p1，則存在，則存在qi，q N，且有，且有k N，使，使 q=kp，從而有從而有bkp=bp*bkp=bp*(bp*bkp)=bkp*bkp，令令a=bkp S 則則a*a=a，即，即a=bkp是是的冪等元。的冪等元。為什么需要研究代數(shù)結(jié)構(gòu)之間的關(guān)系？為什么需要研究代數(shù)結(jié)構(gòu)之間的關(guān)系？ 在研究代數(shù)結(jié)構(gòu)的過程中，所關(guān)心的常常是代數(shù)結(jié)過中運算所滿足在研究代數(shù)結(jié)構(gòu)的過程中，所關(guān)心的常常是代數(shù)結(jié)過中

20、運算所滿足的性質(zhì)，不關(guān)心具體的運算，而對于遵循相同運算規(guī)律的系統(tǒng)只需要研的性質(zhì)，不關(guān)心具體的運算，而對于遵循相同運算規(guī)律的系統(tǒng)只需要研究其中一個就可以了解其它的系統(tǒng)究其中一個就可以了解其它的系統(tǒng).抽象抽象代數(shù)代數(shù)！考察下列代數(shù)考察下列代數(shù): A1= I; ; A2= Q;+ ; A3= R+;min ;A4= P(S); ; A5= P(S); . 此此5個代數(shù)都有相同的構(gòu)成成分個代數(shù)都有相同的構(gòu)成成分:同樣個數(shù)的運算且對應(yīng)運算元數(shù)相同樣個數(shù)的運算且對應(yīng)運算元數(shù)相 (1個二元運算個二元運算); 滿足同樣的公理規(guī)則滿足同樣的公理規(guī)則(交換律交換律,結(jié)合律結(jié)合律);存在單位元。存在單位元。 稱具有

21、上述性質(zhì)的代數(shù)是同一類稱具有上述性質(zhì)的代數(shù)是同一類(代數(shù)結(jié)構(gòu)的類代數(shù)結(jié)構(gòu)的類) 映射 例例 5V1=與V2=兩個代數(shù)結(jié)構(gòu)之間存在一個映射：g：0,1 M,H對于 a,b 0,1,有有g(shù)(a Vb)=g(a)*g(b)V01001111*MHMMHHHH 對于兩代數(shù)結(jié)構(gòu)設(shè)對于兩代數(shù)結(jié)構(gòu)設(shè)V1=和和 V2= 1)是是的代數(shù)結(jié)構(gòu)的代數(shù)結(jié)構(gòu)（運算個數(shù)、對應(yīng)的運算的元數(shù)都相同）（運算個數(shù)、對應(yīng)的運算的元數(shù)都相同） 2)存在從存在從A到到B的一個的一個/f 3)運算性質(zhì)保持（保運算性，滿足運算性質(zhì)保持（保運算性，滿足：對于：對于ki元運算元運算Oi(i=1，2，r)，若任意，若任意(x1，x2，xki)A

22、ki，都有，都有 f(Oi(x1，x2，xki)= *i(f(x1)，f(xki)， 則稱則稱f是是V1到到V2的一個同態(tài)的一個同態(tài)/滿同態(tài)滿同態(tài)/單同態(tài)單同態(tài)/同構(gòu)映射，并稱同構(gòu)映射，并稱V1與與V2 同態(tài)同態(tài)(Homomorphic) /滿同態(tài)滿同態(tài)/單同態(tài)單同態(tài)/同構(gòu)的同構(gòu)的(Isomorphic) 。 例例6：代數(shù)代數(shù)結(jié)結(jié)構(gòu)構(gòu) R+; * , R;+ 同構(gòu)同構(gòu)嗎嗎？ 證明：證明：顯然，顯然， 與與為為同型代數(shù)結(jié)構(gòu)同型代數(shù)結(jié)構(gòu)，下面證明二者之間存在雙射關(guān)系且滿足同態(tài)方程。下面證明二者之間存在雙射關(guān)系且滿足同態(tài)方程。i)建立雙射關(guān)系：建立雙射關(guān)系： 令令h:R+R,h(x)=lnx 顯然，

23、顯然，h是單射是單射 y R, x=ey使使y=lney =lnx=h(x) h是滿射是滿射 h是從是從R+到到R的雙射的雙射ii)h滿足同態(tài)方程：滿足同態(tài)方程： a,bR+ ,h(a*b)=ln(a*b)=lna+lnb=h(a)+h(b)綜上綜上，同構(gòu)于同構(gòu)于這樣，利用同態(tài)這樣，利用同態(tài)/ /同構(gòu)同構(gòu)關(guān)系，可以關(guān)系，可以轉(zhuǎn)移運算轉(zhuǎn)移運算，復(fù)雜的代數(shù)系統(tǒng)可以壓復(fù)雜的代數(shù)系統(tǒng)可以壓縮為另一簡單的代數(shù)系縮為另一簡單的代數(shù)系統(tǒng)。統(tǒng)。AABBff*+思考思考：請你舉例說明上述：請你舉例說明上述系統(tǒng)轉(zhuǎn)換思想。系統(tǒng)轉(zhuǎn)換思想。數(shù)學(xué)、信號處理中的一些變換：數(shù)學(xué)、信號處理中的一些變換：l拉普拉斯變換拉普拉斯變

24、換l時頻分析時頻分析l坐標(biāo)變換坐標(biāo)變換l離散余弦變換離散余弦變換l小波變換小波變換例例7a) 請判斷請判斷T,F; ,T,F; 是否同構(gòu)。是否同構(gòu)。b) 請判斷請判斷*; ,N;+是否同構(gòu)，運算是否同構(gòu)，運算“”表示字符串的連接，表示字符串的連接， “+” 為一般的加法運算。為一般的加法運算。c) 代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)I;+,*,Nm;+m, *m是否同態(tài)？其中，是否同態(tài)？其中， 運算運算+m, *m分別是模分別是模m加、乘。加、乘。d)I;+,2I;+同構(gòu)嗎？同構(gòu)嗎？e) 設(shè)設(shè)與與是代數(shù)結(jié)構(gòu)，其中是代數(shù)結(jié)構(gòu)，其中I+為正整數(shù)集，為正整數(shù)集，E+為正偶為正偶數(shù)集，數(shù)集，*分別為一般的乘法運算，分別

25、為一般的乘法運算，h為為R上的映射，對任意上的映射，對任意xI+， h(x)=2x。試證明：。試證明：h不是不是到到的同構(gòu)映射，并證明的同構(gòu)映射，并證明與與不同構(gòu)。不同構(gòu)。 b) b) 代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)與與是同態(tài)關(guān)系。是同態(tài)關(guān)系。 證明：顯然它們是同型函數(shù)，并存在一個映證明：顯然它們是同型函數(shù)，并存在一個映射：射：f(s)=|s|，其中，其中s為由為由*中元素所組成的串，中元素所組成的串，|s|為串為串s的長度。此映射是多一對應(yīng)的，且對任的長度。此映射是多一對應(yīng)的，且對任意意s1，s2*, 顯然有：顯然有： f(s1s2)=|s1s2|=| s1|+| s2|=f(s1)+f(s2)， 所以所

26、以與與同態(tài)，并且還是滿同同態(tài)，并且還是滿同態(tài)。態(tài)。 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)映射。的同構(gòu)映射。h不是不是到到的同構(gòu)的同構(gòu)映射映射能說明能說明與與就一定不同構(gòu)嗎？就一定不同構(gòu)嗎？ 不一定，因不一定，因為為，同構(gòu)定，同構(gòu)定義義中只要求中只要求“ “保持運算保持運算” ”的的映射存在，但未要求所有雙射都是映射存在，但未要求所有雙射都是“ “保持運算保持運算” ”的，因的，因此，必此，必須證須證明明這這種種“ “保持

27、運算保持運算” ”的雙射不存在，才能的雙射不存在，才能說說明明與與不同構(gòu)。不同構(gòu)。7.2.2 同態(tài)與同構(gòu)的性質(zhì)同態(tài)與同構(gòu)的性質(zhì)定理定理7.4 設(shè)設(shè)g為代數(shù)結(jié)構(gòu)為代數(shù)結(jié)構(gòu)到到的同構(gòu)映射，的同構(gòu)映射，即存在一個一即存在一個一一映射一映射g:XY，使得，使得 x1,x2 X，則有，則有g(shù)(x1x2)=g(x1)*g(x2)。 若若存在單位元存在單位元ex，則則亦存在單位元亦存在單位元ey，且有，且有ey = g(ex) 。 證明：證明：對對 y Y， x Y，使得，使得y=g(x),于是，由于是，由與與同構(gòu)，且同構(gòu)，且有單位元有單位元ex，有有 g(ex)*y= g(ex)*g(x)=g(exx)=

28、g(x),且且y*g(ex)= g(x)*g(ex) =g(xex)=g(x)，故故g(ex)*y= y*g(ex)=y。所以所以的存在單位元的存在單位元ey且且 g(ex)= ey。性質(zhì)保持性質(zhì)保持1 對于同構(gòu)：對于同構(gòu)： 保持結(jié)合律、交換律、分配律；單位元、逆元、零元相應(yīng)存在保持結(jié)合律、交換律、分配律；單位元、逆元、零元相應(yīng)存在（教材的證明請自學(xué)）（教材的證明請自學(xué)）同構(gòu)關(guān)系是一種等價關(guān)系？同構(gòu)關(guān)系是一種等價關(guān)系？2 對于同態(tài)對于同態(tài) 滿同態(tài)滿同態(tài)單向保持性質(zhì)單向保持性質(zhì)XYf 集合上的等價關(guān)系？集合上的等價關(guān)系？ 等價類等價類商集商集添加運算之后添加運算之后？ 1 為什么研究為什么研究同

29、余關(guān)系同余關(guān)系？等價關(guān)系等價關(guān)系同余關(guān)系同余關(guān)系補碼、隨機數(shù)、文件系統(tǒng)、補碼、隨機數(shù)、文件系統(tǒng)、hashhash、密碼、檢錯碼密碼、檢錯碼歐拉函數(shù)和費馬定理歐拉函數(shù)和費馬定理同態(tài)三角形同態(tài)三角形（同態(tài)基本定理）（同態(tài)基本定理）V=V=V/h=h(滿同態(tài)滿同態(tài))g (自然滿同態(tài)自然滿同態(tài))f (同構(gòu)同構(gòu))集合論：集合論： 函數(shù)函數(shù)等價關(guān)系等價關(guān)系劃分劃分代數(shù)結(jié)構(gòu)：代數(shù)結(jié)構(gòu)： 同態(tài)同態(tài)同余關(guān)系同余關(guān)系可允許劃分可允許劃分變換變換6.3.1 同余關(guān)系同余關(guān)系 原始含義（示例）：原始含義（示例）： 代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)在在Z上的關(guān)系上的關(guān)系R定義如下：定義如下： xRy xy(mod k)， 且滿足如下推

30、理：且滿足如下推理： xRy且且 zRw (x+z)R(y+w)（*） 這樣，上述利用這樣，上述利用余數(shù)相等余數(shù)相等建立的滿足（建立的滿足（*）推理式的）推理式的關(guān)系關(guān)系R稱為稱為同余關(guān)系同余關(guān)系。推廣推廣1 命題邏輯公式的等值關(guān)系是邏輯代數(shù)上的同余關(guān)命題邏輯公式的等值關(guān)系是邏輯代數(shù)上的同余關(guān)系嗎？系嗎？2 恒等關(guān)系是集合代數(shù)上的同余關(guān)系嗎？恒等關(guān)系是集合代數(shù)上的同余關(guān)系嗎？3 , R=(x, y)|x/y=2m, mZ同余關(guān)系同余關(guān)系(Congruence) 是一個代數(shù)系統(tǒng)是一個代數(shù)系統(tǒng),R是是A上的等價關(guān)系上的等價關(guān)系,若若 R, R R，稱，稱R是是A上的上的同余關(guān)系同余關(guān)系(R對對于運

31、算于運算*滿足滿足代換性質(zhì)代換性質(zhì)).同余關(guān)系將同余關(guān)系將A劃分得到的等價類稱為劃分得到的等價類稱為 可允許劃分可允許劃分(同余類同余類)： 對于代數(shù)結(jié)構(gòu)對于代數(shù)結(jié)構(gòu), =A1,A2,An是是A上的一個劃分，若對于上的一個劃分，若對于任意的劃分塊任意的劃分塊Ai, Aj ,存在存在Ak ,使得：使得：Ai*Aj Ak,則稱為可允許劃則稱為可允許劃分。分。例例12：，在，在I上定義上定義R: R|x|=|y|, 問問R是是的等價關(guān)系嗎？是否是同余關(guān)系的等價關(guān)系嗎？是否是同余關(guān)系?解解: 1)自反性自反性： x I, |x|=|x| ，從而，從而 R 2)對稱性對稱性： x,y I，若，若 R則則

32、|x|=|y|，從而，從而 R 3)傳遞性傳遞性： x,y,z I，若，若 R, R 由由|x|=|y|=|z| 知知 R 所以所以 R是一等價關(guān)系。是一等價關(guān)系。 對對 x1,y1,x2,y2 I，若，若 R, R， 但但 R不一定成立，例如，不一定成立，例如， R, R但但 R 綜上，綜上，R是等價關(guān)系但不是同余關(guān)系是等價關(guān)系但不是同余關(guān)系定理定理 設(shè)設(shè)R是代數(shù)結(jié)構(gòu)是代數(shù)結(jié)構(gòu)上的上的等價關(guān)系等價關(guān)系，*為為二元運算，對于二元運算，對于 a，b S/R, 其中其中S/R是是可允許劃分可允許劃分定義定義a ob=a*b則則o為為S/R上的上的二元運算二元運算當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)R為為上上同余關(guān)系同

33、余關(guān)系。 證明證明 必要性必要性 設(shè)設(shè)o為為上二元運算。對上二元運算。對 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)系。上同余關(guān)系。充分性充分性 設(shè)設(shè)R為為上同余關(guān)系，任意上同余關(guān)系，任意a,b S/R， 顯然顯然a ob=a*b S/R，即，即o在在S/R上滿足封閉性，還需證對任意上滿足封閉性，還需證對任意a,b S/R，a ob值唯一。值唯一。注意到，注意到，a ob=a*b，a*b值是惟一的，值是惟一的，a*b是惟一的。

34、因此，需要證明若是惟一的。因此，需要證明若a，b取其它代表元，如取其它代表元，如a,b，其值，其值a*b與與a*b是否相等。是否相等。對對 a a, b b,有有aRa, bRb, 則則a*bRa*b 。于是。于是a ob=a*b =a*b=a ob。這說明。這說明a ob的運算結(jié)果與等價類的代表元無關(guān)，值是唯一的運算結(jié)果與等價類的代表元無關(guān)，值是唯一的。的。故故o是是S/R上的二元運算。上的二元運算。綜上，命題得證。綜上，命題得證。6.3.2 同余關(guān)系同余關(guān)系商代數(shù)商代數(shù)(Quotient Algebra)思考思考是否可以根據(jù)是否可以根據(jù) 上的同余關(guān)系定義一個上的同余關(guān)系定義一個的滿同的滿同

35、態(tài)代數(shù)結(jié)構(gòu)（商代數(shù)）？態(tài)代數(shù)結(jié)構(gòu)（商代數(shù)）？同余關(guān)系同余關(guān)系商代數(shù)商代數(shù)(Quotient algebra) 代數(shù)結(jié)構(gòu)：代數(shù)結(jié)構(gòu)：V= （o為一元運算）為一元運算）V上同余關(guān)系：上同余關(guān)系：商代數(shù)：商代數(shù)：V/=運算運算o的定義？的定義？ o(x)=o(x)代數(shù)結(jié)構(gòu)：代數(shù)結(jié)構(gòu)：V= （o為二元運算）為二元運算）V上同余關(guān)系：上同余關(guān)系：商代數(shù)：商代數(shù)：V/=運算運算*的定義？的定義？ x o y=xoy6.3.2 同同態(tài)態(tài)基本定理基本定理設(shè)代數(shù)結(jié)構(gòu)設(shè)代數(shù)結(jié)構(gòu)V=, V=, h是從是從V到到V的滿同態(tài)映射，的滿同態(tài)映射，則則1) 在在S上定義一個關(guān)系上定義一個關(guān)系h，使得當(dāng)且僅當(dāng)，使得當(dāng)且僅當(dāng)h

36、(x)=h(y)時時xhy，則，則h是是V上的同余關(guān)系（上的同余關(guān)系（同余定理同余定理）；）；2) 由由h可以得到可以得到V的商代數(shù)的商代數(shù)，記為，記為V/h，且存在，且存在V到到V/h的滿同態(tài)映射的滿同態(tài)映射(自然同態(tài)自然同態(tài))g；3) V/h與與V同構(gòu)。同構(gòu)。同同態(tài)態(tài)三角形三角形V=V=V/h=h(滿同態(tài)滿同態(tài))g (自然滿同態(tài)自然滿同態(tài))f (同構(gòu)同構(gòu))集合論：集合論： 函數(shù)函數(shù)等價關(guān)系等價關(guān)系劃分劃分代數(shù)結(jié)構(gòu)：代數(shù)結(jié)構(gòu)： 同態(tài)同態(tài)同余關(guān)系同余關(guān)系可允許劃分可允許劃分 同態(tài)三角形的同構(gòu)性的證明：同態(tài)三角形的同構(gòu)性的證明：1 同型：同型：Vh 與與 V同型？同型？2 雙射：雙射： 定義映射

37、定義映射f，并證明其為雙射，并證明其為雙射定義映射定義映射f：因為因為h是一個從是一個從S到到S的滿射，的滿射， S/h為可允許劃分，所以為可允許劃分，所以對于每一個對于每一個xh S/h必存在唯一必存在唯一xS，使得，使得x=h(x)，于是可以，于是可以如下定義函數(shù)：如下定義函數(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，于是，于是x

38、h=yh，所以，所以f是單射是單射3 滿足同態(tài)方程滿足同態(tài)方程由于由于 f(xh yh)=f(xoyh)=h(xoy)=h(x)*h(y)=f(xh)*f(yh)所以，前述運算與雙射滿足同態(tài)方程。所以，前述運算與雙射滿足同態(tài)方程。綜上，綜上， Vh 與與 V同構(gòu)。同構(gòu)。思考思考如果上述同構(gòu)證明過程中，將映射改f改為從S 到S/h ，則如何描述具體證明過程？補充例題補充例題1 設(shè)設(shè)*是自然數(shù)集合是自然數(shù)集合N中的二元運算，并定義中的二元運算，并定義x*y=x。試證明。試證明*是可結(jié)合的，但不是可交換的。是可結(jié)合的，但不是可交換的。2 M為單位半群，證明為單位半群，證明b=a-1的充分必要條件是的

39、充分必要條件是aba=a和和ab2a=e。3 代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價關(guān)系。代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價關(guān)系。4 考慮代數(shù)結(jié)構(gòu)考慮代數(shù)結(jié)構(gòu)V=Z3 ； 3， 3和和Z3上的等價關(guān)系上的等價關(guān)系。1) 證明若證明若對于對于 3滿足代換性質(zhì)，則它對滿足代換性質(zhì)，則它對 3一定也滿足代換一定也滿足代換性質(zhì)。性質(zhì)。2) 找出一個找出一個Z3上的等價關(guān)系，它對于上的等價關(guān)系，它對于 3滿足代換性質(zhì)，但對滿足代換性質(zhì)，但對 3不滿足。不滿足。補充例題補充例題2 M為單位半群，證明為單位半群，證明b=a-1的充分必要條件是的充分必要條件是aba=a和和ab2a=e。證 必要性：將b代入即可得。充分性：利用結(jié)

40、合律作以下運算：ab=ab(ab2a)=(aba)b2a=ab2a=e，ba=(ab2a)ba=ab2 (aba)=ab2a=e，所以b=a-1。 證畢補充例題補充例題3 代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價關(guān)系。代數(shù)結(jié)構(gòu)間的同構(gòu)關(guān)系是等價關(guān)系。證明證明 設(shè)設(shè)X；，Y；*，Z；+是任意的三個代數(shù)結(jié)構(gòu)，是任意的三個代數(shù)結(jié)構(gòu)，并設(shè)同構(gòu)關(guān)系用并設(shè)同構(gòu)關(guān)系用“ ”表示，下面表示，下面 證明滿足自反性、對稱性以及證明滿足自反性、對稱性以及傳遞性。傳遞性。補充例題補充例題 (1) 自反性自反性：顯然有：顯然有X； X；)，即是自反的。，即是自反的。 (2) 對稱性對稱性：如果：如果X； Y；*則必存在一個雙射則必存

41、在一個雙射 g: XY，使，使得若得若x1，x2X，并有：，并有：g(x1x2)=g(x1)*g(x2)根據(jù)雙射的定義，必存在一個雙射的逆映射根據(jù)雙射的定義，必存在一個雙射的逆映射g-1: YX?，F(xiàn)要證對現(xiàn)要證對g-1: YX，若，若y1，y2Y，必有：，必有： g-1(y1*y2)=g-1(y1)g-1(y2)設(shè)對任意的設(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；，所以，所以 是對稱的。是對稱的。補充例題補充例題 (3) 傳遞性：傳遞性：如果有如果有X； Y；*，且，且Y；* Z；+，要證明要證明X；