歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > PPT文檔下載  

大學(xué)課件 離散數(shù)學(xué)(第二版)(蔡英) 第5章 代數(shù)系統(tǒng)的基本概念

  • 資源ID:23973955       資源大?。?span id="1616111" class="font-tahoma">2MB        全文頁數(shù):87頁
  • 資源格式: PPT        下載積分:12積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺(tái)登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要12積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請(qǐng)知曉。

大學(xué)課件 離散數(shù)學(xué)(第二版)(蔡英) 第5章 代數(shù)系統(tǒng)的基本概念

大學(xué)課件(第二版)()第5章 代數(shù)系統(tǒng)的基本概念 5.1 二元運(yùn)算及性質(zhì)5.2 代數(shù)系統(tǒng)5.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)5.4 例題選解習(xí)題五第三篇 幅代數(shù)結(jié)構(gòu) 集合中的代數(shù)運(yùn)算實(shí)質(zhì)上是集合中的一類函數(shù)。定義5.1.1 設(shè)A是集合,函數(shù)f: AnA稱為集合A上的n元代數(shù)運(yùn)算(operators), 整數(shù)n稱為運(yùn)算的階(order)。當(dāng)n=1時(shí),f: AA稱為集合A中的一元運(yùn)算。當(dāng)n=2時(shí),f: AAA稱為集合A中的二元運(yùn)算。 5.1 二元運(yùn)算及其性質(zhì) 一般地,二元運(yùn)算用算符 。,* ,等等表示,并將其寫于兩個(gè)元素之間,如ZZZ的加法: F(2,3)=+(2,3)=2+3=5注意到Ran f A,即運(yùn)算結(jié)果是A中的元素,這稱為運(yùn)算的封閉性。另外,運(yùn)算是函數(shù),要具備函數(shù)所具有的對(duì)每一個(gè)自變?cè)形ㄒ坏南竦奶匦浴?【例5.1.1】下面均是一元運(yùn)算的例子。(1) 在Z集合上(或Q,或R),f: ZZ, x Z,f(x)=-x。(2) 在A=0,1集合上,f: AA, p A,f(p)=p,表示否定。(3) 在R+集合上,f: R+R+, x R+,f(x)= (但在R上,倒數(shù)不是一元運(yùn)算,因?yàn)?無像)。 x1 【例5.1.2】下面均是二元運(yùn)算的例子。(1) 在Z集合上(或Q,或R),f: ZZZ,x, y Z2,f(x,y)=x+y(或f(x,y)=x-y或f(x,y)=xy),如f(2,3)=5。注意在N集合上,“減法”因其不封閉性,而不是N上的二元運(yùn)算。 (2) A為集合,P(A)為其冪集。f: P(A)P(A)P(A)。 f可以是、 、 -、 。(3) A=0,1。f: AAA。f可以是、 、 、 。(4) AA=f|f: AA?!?。(復(fù)合)”是AA上的二元運(yùn)算。當(dāng)A是有窮集合時(shí),運(yùn)算可以用運(yùn)算表給出。如A=0,1,2,3,4,5,二元運(yùn)算“?!钡亩x見表5.1.1。 表5.1.1表5.1.2 事實(shí)上,對(duì)于表5.1.1,通過觀察我們可看出其運(yùn)算為(x,y )=xy(mod 3)其中,“”是普通乘法。而對(duì)于表5.1.2,此時(shí)的“*”運(yùn)算應(yīng)是在集合0,1上的 (邏輯合取運(yùn)算符)。下面介紹二元運(yùn)算的性質(zhì)。 定義5.1.2設(shè)*,均為集合S上的二元運(yùn)算。(1) 若 x y z(x,y,z Sx*(y*z)=(x*y)*z),則稱“*”運(yùn)算滿足結(jié)合律。(2) 若 x y(x,y Sx*y=y*x),則稱“*”運(yùn)算滿足交換律。(3) 若 x y z(x,y,z Sx*(y z)=(x*y) (x*z),則稱“*”運(yùn)算對(duì)運(yùn)算滿足左分配律; 若 x y z(x,y,z S(y z)*x=(y*x) (z*x),則稱“*”運(yùn)算對(duì)運(yùn)算滿足右分配律。若二者均成立,則稱“*”運(yùn)算對(duì)“”運(yùn)算滿足分配律。 (4) 設(shè)*,均可交換,若 x, y A,有x*(x y)=xx (x*y)=x則稱“*”運(yùn)算和“”運(yùn)算滿足吸收律。(5) 若 x(x A,x*x=x),則稱“*”運(yùn)算滿足冪等律。 【例5.1.3】加法、 乘法運(yùn)算是自然數(shù)集上的二元運(yùn)算,減法和除法便不是。但是減法是有理數(shù)集、 實(shí)數(shù)集上的二元運(yùn)算,除法卻仍不是。加法、 乘法滿足結(jié)合律、 交換律,乘法對(duì)加法、 減法滿足分配律,減法不滿足這些定律。乘法“”對(duì)加法“+”運(yùn)算滿足分配律(對(duì)“-”也滿足)。但加法“+”對(duì)乘法“”運(yùn)算不滿足分配律。 【例5.1.4】設(shè)A是集合,在A的冪集P(A)上的二元運(yùn)算并、 交滿足交換律、 結(jié)合律、 吸收律、 冪等律且彼此滿足分配律?!纠?.1.5】設(shè)A=a,b,A上的運(yùn)算*、 分別如表5.1.3和表5.1.4所示。 表 5.1.3表 5.1.4 解從*運(yùn)算表可知,*是可交換的。因?yàn)?(a*a)*b=a*b=ba*(a*b)=a*b=b (a*b)*b=b*b=a a*(b*b)=a*a=a所以*是可結(jié)合的。 從運(yùn)算表可知,是可交換的。因?yàn)?(a a) b=a b=aa (a b)=a a=a (a b) b=a b=a a (b b)=a b=a 所以是可結(jié)合的。 (1) b (a*b)=b b=b (b a)*(b b)=a*b=b (2) a (a*b)=a b=a (a a)*(a b)=a*a=a b (a*a)=b a=a (b a)*(b a)=a*a=a b (b*b)=b a=a (b b)*(b b)=b*b=a a (a*a)=a a=a (a a)*(a a)=a*a=a a (b*b)=a a=a (a b)*(a b)=a*a=a所以對(duì)*是可分配的。(由于運(yùn)算滿足交換律成立,因此右分配也成立。) (3) b*(a b)=b*a=b (b*a) (b*b)=b a=a故*對(duì)是不可分配的。又由a*(a b)=a*a=a 及上面(1)、 (2)、 (3)式可知和*滿足吸收律。由運(yùn)算表可知,滿足冪等律,而*不滿足冪等律。下面我們來定義與集合A中的二元運(yùn)算有關(guān)的集合A中的特異元素。 定義5.1.3設(shè)*是集合S中的一種二元運(yùn)算,如果存在er S(el S)且對(duì)任意元素x S 均有x*er=x(el*x=x),則稱元素er(el)為S中關(guān)于運(yùn)算*的右幺元(左幺元)或右單位元(左單位元)。定理5.1.1設(shè)*是S中的二元運(yùn)算且er與el分別是對(duì)于*的右幺元和左幺元,則er=el=e, 使對(duì)任意元素x S有x*e=e*x=x, 稱元素e為關(guān)于運(yùn)算*的幺元(identity elements)且唯一。 證明因?yàn)閑r和el分別是*的右幺元和左幺元,故有 el*er=el,el*er=er,所以er=el。 令其為e,有x*e=e*x=x設(shè)另有一幺元為右幺元e,那么e=e*e=e故e對(duì)*是唯一的幺元。證畢顯然,對(duì)于可交換的二元運(yùn)算來說,左幺元即為右幺元,反之亦然。因此對(duì)于可交換的二元運(yùn)算,左(右)幺元即幺元。另外,我們必須強(qiáng)調(diào)是對(duì)哪一個(gè)運(yùn)算而言的幺元。 【例5.1.6】在實(shí)數(shù)集R中,對(duì)加法“+”運(yùn)算,0是幺元; 在實(shí)數(shù)集R中,對(duì)乘法“”運(yùn)算,1是幺元; 對(duì)于全集E的子集的并“”運(yùn)算,是幺元; 對(duì)于全集E的子集的交“”運(yùn)算,E是幺元;在命題集合中,對(duì)于析取“”運(yùn)算,矛盾式是幺元; 在命題集合中,對(duì)于合取“”運(yùn)算,重言式是幺元; 在AA=f|f:AA中,對(duì)于復(fù)合“”運(yùn)算,I A是幺元。 定義5.1.4設(shè)*是集合S中的一種二元運(yùn)算,如果存在r S(l S)且對(duì)任意元素x S均有x*r=r(l*x=l),則稱元素r(l)是S中關(guān)于運(yùn)算*的右零元(左零元)。定理5.1.2設(shè)*是S中的二元運(yùn)算且r 與l分別是對(duì)于*的右零元和左零元,則r=l=, 使對(duì)任意元素x S有x*=*x=, 稱元素是S中關(guān)于運(yùn)算*的零元(zero)且唯一。 證明因?yàn)閞 和l分別是*的右零元和左零元,故有 l*r=l,l*r=r,所以r=l。 令其為,有x*=*x=設(shè)另有一零元為右零元,那么=*=故對(duì)S中的*運(yùn)算是唯一的零元。證畢同樣,需強(qiáng)調(diào)零元是針對(duì)于哪個(gè)運(yùn)算的。 【例5.1.7】在實(shí)數(shù)集R中,對(duì)加法“+”運(yùn)算,沒有零元; 在實(shí)數(shù)集R中,對(duì)乘法“”運(yùn)算,0是零元; 對(duì)于全集E的子集的并“”運(yùn)算,E是零元; 對(duì)于全集E的子集的交“”運(yùn)算,是零元;在命題集合中,對(duì)于析取“”運(yùn)算,重言式是零元; 在命題集合中,對(duì)于合取“”運(yùn)算,矛盾式是零元。【例5.1.8】設(shè)Sa,b,c, S上*運(yùn)算由運(yùn)算表(如表5.1.5所示)確定,那么b是右零元, a是幺元。 表 5.1.5 我們注意到,關(guān)于同一運(yùn)算可能同時(shí)有幺元和零元,甚至可能有這樣的元素,它關(guān)于同一運(yùn)算既是左(右)幺元,又是右(左)零元,例如表5.1.5第一行(不計(jì)表頭)改為三個(gè)a時(shí),那么*運(yùn)算有左零元a和右幺元a。 我們強(qiáng)調(diào)以下幾點(diǎn): (1) 左、 右幺元,幺元,左、 右零元,零元都是常元。 (2) 左、 右幺元,幺元,左、 右零元,零元都是依賴于運(yùn)算的。例如,在代數(shù)結(jié)構(gòu) N,+,中,0關(guān)于數(shù)加 + 是幺元,關(guān)于數(shù)乘是零元; 1關(guān)于是幺元,關(guān)于+則既非幺元又非零元。又如在P(A)中,是關(guān)于的幺元,是關(guān)于的零元; A是關(guān)于的零元,又是關(guān)于的幺元。 (3) 今后,在不致造成混淆時(shí),特殊元素是關(guān)于什么運(yùn)算的不再一一指出,但當(dāng)有兩個(gè)或兩個(gè)以上的運(yùn)算時(shí)仍將對(duì)此作出申明。這時(shí),常常出現(xiàn)這樣的情況,一個(gè)運(yùn)算與數(shù)加的性質(zhì)接近,另一個(gè)運(yùn)算與數(shù)乘的性質(zhì)接近,為了簡(jiǎn)明、 直觀,我們把前一種運(yùn)算叫做加法運(yùn)算,關(guān)于它的幺元、 零元稱為加法幺元、 加法零元; 常把后一種運(yùn)算叫做乘法運(yùn)算,關(guān)于它的幺元、 零元稱為乘法幺元、 乘法零元。例如,在P(A),中可稱為P(A)的加法幺元、 乘法零元, 稱A為P(A)的乘法幺元、 加法零元。 定義5.1.5設(shè)*是集合S中的一種二元運(yùn)算,且S中對(duì)于*有e為幺元,x,y為S中元素。若x*ye,那么稱x為y的左逆元,y為x的右逆元,若x對(duì)于*運(yùn)算既有左逆元又有右逆元,則稱x是左、 右可逆的。若x左右均可逆,稱x可逆。顯然對(duì)于二元運(yùn)算*,若*是可交換的,則任何左(右)可逆的元素均可逆。 定理5.1.3設(shè)*是集合S中的一個(gè)可結(jié)合的二元運(yùn)算,且S中對(duì)于*有e為幺元,若x S是可逆的,則其左、 右逆元相等,記作x-1,稱為元素x對(duì)運(yùn)算*的逆元(inverse elements)且是唯一的。(x的逆元通常記為x-1; 但當(dāng)運(yùn)算被稱為“加法運(yùn)算”(記為+)時(shí), x的逆元可記為-x。) 證明設(shè)xr 和xl分別是x對(duì)*運(yùn)算的右逆元和左逆元,故有xl*x=x*xr=e由于*可結(jié)合,于是xl=xl*e=xl*(x*xr)=(xl*x)*xr=e*xr=xr故xl=xr。假設(shè) , 均是x對(duì)*的逆元,則=*e=*(x*)=(*x)*=e*=由,故唯一性成立。由逆元定義知,若x -1存在,則x-1*x=x*x-1=e。證畢11x 12x11x 11x 11x 11x11x 12x12x 12x1211 xx 定理5.1.4設(shè)*是集合S中的一個(gè)可結(jié)合的二元運(yùn)算,且e為S中對(duì)于*的幺元,x有逆元x-1,則(x-1)-1=x。證明(x-1)-1=(x-1)-1*e=(x-1)-1*(x-1*x)=(x-1)-1*x-1)*x=e*x=x。證畢 由以上討論可得結(jié)論: (1) e-1=e。(2) 并非每個(gè)元素均可逆。 【例5.1.9】(1) 在自然數(shù)集合N上,對(duì)于數(shù)乘“”運(yùn)算,只有數(shù) 1有逆元 1,對(duì)于數(shù)加“+”運(yùn)算,只有數(shù)0有逆元0??傊?,任何代數(shù)結(jié)構(gòu)其幺元恒有逆元,逆元為其自身。 (2) 在整數(shù)集合I上(+,的定義同上),I上每個(gè)元素均有加法逆元,但除1以外的數(shù)都沒有乘法逆元。對(duì)任意x I,x的逆元是-x。 (3) 在有理數(shù)集合Q上(+,的定義同上),Q上每個(gè)元素x,都有加法逆元-x,除0以外的每個(gè)元素x都有乘法逆元x -1=1/x。 (4) 在P(A)中,對(duì)于運(yùn)算,其幺元為,每個(gè)元素B(B )均無逆元; 對(duì)于運(yùn)算,其幺元為A,每個(gè)元素B(BA)均無逆元。 (5) 在集合AA(其中 AA f|f: AA)中,為函數(shù)的合成運(yùn)算,恒等函數(shù)IA為幺元,從而A中所有雙射函數(shù)都有逆元,所有單射函數(shù)都有左逆元, 所有滿射函數(shù)都有右逆元。定理5.1.5設(shè)*是S上的二元運(yùn)算,e為幺元,為零元,并且|S|2,那么無左(右)逆元。證明首先證 e,否則=e,則S中另有元素a,a不是幺元和零元,從而*ae*aa與a不是零元矛盾,故e得證。 再用反證法證無左(右)逆元,即可設(shè)有左(右)逆元x,那么=x*=e(=*x=e)與e矛盾,故無左(右)逆元。得證。 證畢注意逆元是對(duì)某個(gè)元素而言的,它并不是常元,它不僅依賴于運(yùn)算,而且更依賴于是哪個(gè)元素的逆元。 【例5.1.10】有理數(shù)集合Q上的加法“+”運(yùn)算與乘法“”運(yùn)算,10的加法逆元是 -10, 乘法逆元是1/10; 而-10的加法逆元是10,乘法逆元是-1/10。當(dāng)一個(gè)集合中每一元素都有逆元時(shí),可以認(rèn)為該集合上定義了一個(gè)一元求逆運(yùn)算。與逆元概念密切相關(guān)的是可約性概念。定義5.1.6設(shè)*是集合S中的一個(gè)二元運(yùn)算, a S,a,如果a滿足: 對(duì)任意x,y S 均有 a*x=a*y x=y(1) x*a=y*a x=y(2) 則稱元素a對(duì)*是可約(可消去)的(cancelable),當(dāng)a滿足(1)式時(shí),也稱a是左可約(左可消去)的,當(dāng)a滿足(2)式時(shí),也稱a是右可約(右可消去)的。 特別地,若對(duì)任意x,y,z S,有(x*y=x*z) x y=z (y*x=z*x) x y=z 則稱運(yùn)算*滿足消去律(可約律)。定理5.1.6若*是 S中滿足結(jié)合律的二元運(yùn)算,且元素a有逆元(左逆元,右逆元),則a必定是可約的(左可約的,右可約的)。證明設(shè)a的逆元為a-1,對(duì)任意元素x,y S,設(shè)a*x=a*y及x*a=y*a,可得a-1*(a*x)=a-1*(a*y) (x*a)*a-1=(y*a)*a-1即(a-1*a)*x=(a-1*a)*y x*(a*a-1)=y*(a*a-1) 均可推得x=y。因此,a是可約的。 證畢 注意 定理5.1.6的逆并不成立。即a可約推不出a可逆。例如整數(shù)集合I中的乘法運(yùn)算,任一非零元素a均可約,但a除1外其余元素均無逆元。 當(dāng)S是有窮集合時(shí),其上的二元運(yùn)算??捎眠\(yùn)算表給出,運(yùn)算的一些性質(zhì)可直接由運(yùn)算表看出。(1) 二元運(yùn)算滿足可交換性的充分必要條件是運(yùn)算表關(guān)于主對(duì)角線對(duì)稱。(2) 二元運(yùn)算滿足冪等性的充分必要條件是運(yùn)算表主對(duì)角線上的每個(gè)元素與它所在行、 列的表頭元素相同。 (3) 二元運(yùn)算有幺元的充分必要條件是該元素對(duì)應(yīng)的行和列依次與該表表頭的行、 列相一致。(4) 二元運(yùn)算有零元的充分必要條件是運(yùn)算表中該元素所對(duì)應(yīng)的行、 列元素均與該元素相同。(5) 二元運(yùn)算中a與b互為逆元素的充分必要條件是運(yùn)算表中位于a所在行、 b所在列的元素及b所在行、 a所在列的元素都是幺元。 【例5.1.11】N4是整數(shù)中模4同余產(chǎn)生的等價(jià)類集合,N4=0,1,2,3, N4上運(yùn)算+4,4定義為 m+4n=(m+n)mod4 m4n=(mn)mod4其中m,n 0,1,2,3,運(yùn)算表如表5.1.6、 5.1.7所示。 表 5.1.6 表 5.1.7 解由表5.1.6可知, 0為幺元,1-1=3,2-1=2,無零元。由表5.1.7可知, 1為幺元,3-1=3,0、 2無逆元,0為零元。 什么是代數(shù)系統(tǒng)?粗略地說,代數(shù)系統(tǒng)是由一個(gè)特定的集合,以及定義于該集合上的若干“運(yùn)算”所組成的。換言之,它是一個(gè)“有組織的集合”?,F(xiàn)代科學(xué)在研究各種不同的現(xiàn)象時(shí),為了探索它們之間的共同特點(diǎn),常常利用代數(shù)系統(tǒng)這個(gè)框架研究,以得出深刻的結(jié)果。目前,代數(shù)系統(tǒng)的理論已經(jīng)在理論物理、 生物學(xué)、 計(jì)算機(jī)科學(xué)以及社會(huì)科學(xué)中得到廣泛的應(yīng)用。5.2 代 數(shù) 系 統(tǒng) 定義5.2.1代數(shù)結(jié)構(gòu)是由以下三個(gè)部分組成的數(shù)學(xué)結(jié)構(gòu): (1) 非空集合S。 (2) 集合S上的若干運(yùn)算。 (3) 一組刻畫集合上各運(yùn)算所具有的性質(zhì)。 代數(shù)結(jié)構(gòu)常用一個(gè)多元序組S,*, 來表示,其中 S是集合,*,為各種運(yùn)算。S稱為基集,各運(yùn)算組成的集合稱為運(yùn)算集,代數(shù)結(jié)構(gòu)也稱為代數(shù)系統(tǒng)。 【例5.2.1】 (1) 以實(shí)數(shù)集R為基集,數(shù)加運(yùn)算“”為二元運(yùn)算,組成一代數(shù)系統(tǒng),記為R,。 (2) 以全體nn實(shí)數(shù)矩陣組成的集合M為基集,矩陣加“”為二元運(yùn)算,組成一代數(shù)系統(tǒng),記為M,。 (3) 以集合A的冪集P(A)為基集,以集合并、 交、 補(bǔ)為其二元運(yùn)算和一元運(yùn)算,組成一代數(shù)結(jié)構(gòu),記為P(A),。有時(shí)為了突出全集E及空集在P(A)中的特殊地位,也可將這一代數(shù)結(jié)構(gòu)記為 P(A),A,。這個(gè)系統(tǒng)就是常說的冪集代數(shù)系統(tǒng)。 以上的(1),(2),(3)均稱為具體代數(shù)系統(tǒng),其運(yùn)算滿足的性質(zhì)未列出。 (4) 設(shè)S為一非空集合,*為S上滿足結(jié)合律、 交換律的二元運(yùn)算,那么S,*為代數(shù)結(jié)構(gòu),稱為一個(gè)抽象代數(shù)系統(tǒng),即一類具體代數(shù)結(jié)構(gòu)的抽象。例如R,+,M, P(A), , P(A), 都是S,*的具體例子。(5) R,+,-,Z,+,-,均是代數(shù)系統(tǒng),但我們不能寫Z,R, N,-,因?yàn)樗鼈儾皇谴鷶?shù)系統(tǒng),它們的運(yùn)算不封閉。注意代數(shù)系統(tǒng)S,*, ,中的這些代數(shù)運(yùn)算可以是不同階的,但我們討論的一般是一、 二階(一元、 二元)運(yùn)算。 由上節(jié)可知,某些代數(shù)系統(tǒng)中存在著一些特異元素,它們對(duì)系統(tǒng)中的運(yùn)算起著重要的作用,如冪集代數(shù)中的和全集E,命題代數(shù)中的重言式和矛盾式,二元運(yùn)算的幺元和零元等,我們稱這些元素為該系統(tǒng)的特異元素或代數(shù)常數(shù)。有時(shí)為了強(qiáng)調(diào)它們的特殊地位,也可將它們列入這種代數(shù)系統(tǒng)的多元序組的末尾,如 P(A),A,。定義5.2.2如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同,對(duì)應(yīng)的階數(shù)也相同,且代數(shù)常數(shù)的個(gè)數(shù)也相同,則稱這兩個(gè)代數(shù)系統(tǒng)具有相同的構(gòu)成成分,也稱它們是同類型的代數(shù)系統(tǒng)。 例如命題代數(shù)與冪集代數(shù): P(A), A,與R,+,-,0, 1(這里“-”指一元運(yùn)算相反數(shù))。定義5.2.3設(shè)*是S上的n元運(yùn)算(n1,2,),T S,如果對(duì)任意元素x1,x2,xn T,*(x1,x2,xn) T,稱*運(yùn)算對(duì)T封閉(c1osed)。 【例5.2.2】設(shè)E為非負(fù)偶數(shù)集,M為非負(fù)奇數(shù)集,那么定義于N上的數(shù)加運(yùn)算對(duì)E封閉,對(duì)M不封閉,數(shù)乘運(yùn)算對(duì)E和M都封閉。定義5.2.4設(shè)S,*是代數(shù)系統(tǒng),如果有非空集合T滿足 (1) T S, (2) 運(yùn)算*對(duì)T封閉,則稱T,*為代數(shù)系統(tǒng)S,*的子代數(shù)系統(tǒng),或子代數(shù)(subalgebra)。根據(jù)定義,子代數(shù)必為一代數(shù)系統(tǒng),*運(yùn)算所滿足的性質(zhì)顯然在子代數(shù)中仍能得到滿足。注意由于T只是S的子集,S中關(guān)于*運(yùn)算的特殊元素,T中未必仍然具有。 常把S,*叫做S,*的平凡子代數(shù); 若S含幺元e,那么也把e,*叫做S,*,e 的平凡子代數(shù)。若T是S的真子集,則T構(gòu)成的子代數(shù)稱為S的真子代數(shù)?!纠?.2.3】在例5.2.2中,對(duì)N,+而言,E,+為其子代數(shù),N,0,為其平凡子代數(shù),M,不構(gòu)成其子代數(shù)。 本節(jié)將討論代數(shù)系統(tǒng)之間的聯(lián)系,研究?jī)蓚€(gè)同類型的代數(shù)系統(tǒng)之間的關(guān)系,即同態(tài)與同構(gòu)。同態(tài)與同構(gòu)映射是研究代數(shù)系統(tǒng)的重要工具。兩個(gè)看起來似乎不同的代數(shù)系統(tǒng),往往具有一些共同的性質(zhì),或進(jìn)一步它們還會(huì)有相同的結(jié)構(gòu),僅僅是元素的名稱和標(biāo)記運(yùn)算用的符號(hào)不同而已。在這種情況下,對(duì)其中一個(gè)代數(shù)系統(tǒng)所得的結(jié)論,在改變符號(hào)之后,對(duì)另一個(gè)代數(shù)系統(tǒng)也有效。由于我們只討論含一元運(yùn)算、 二元運(yùn)算的代數(shù)系統(tǒng),因此下文(直至本章末)常用 S,*表示一個(gè)一般的代數(shù)系統(tǒng),*表示二元運(yùn)算。為簡(jiǎn)明起見,有時(shí)也僅用基集S表示一個(gè)代數(shù)系統(tǒng)。5.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) 定義5.3.1設(shè)S,*及T,均為代數(shù)系統(tǒng),如果函數(shù) f: ST對(duì)S中任何元素a,b,有f(a*b)f(a) f(b) 稱函數(shù) f為(代數(shù)系統(tǒng) S到T的)同態(tài)映射,或同態(tài)(homomorphism),當(dāng)同態(tài)f為單射時(shí),又稱f為單一同態(tài); 當(dāng)f為滿射時(shí),又稱f為滿同態(tài); 當(dāng)f為雙射時(shí),又稱f為同構(gòu)映射,或同構(gòu)(isomorphism)。當(dāng)兩個(gè)代數(shù)系統(tǒng)間存在同構(gòu)映射時(shí),也稱這兩個(gè)代數(shù)系統(tǒng)同構(gòu),記為S T。當(dāng)f為S,*到S,*的同態(tài)(同構(gòu))時(shí),稱f為S的自同態(tài)(自同構(gòu))。 f(a*b)=f(a) f(b)稱為同態(tài)f的同態(tài)方程。 【例5.3.1】 (1) 設(shè) f: RR為 f(x)=ex(R為實(shí)數(shù)集),那么,f為R,+到R,的同態(tài)。因?yàn)閷?duì)任意實(shí)數(shù)x,y,有f(x+y)ex+y=exey=f(x)f(y)由f的定義還可知f為單一同態(tài)。 由f的定義還可知f為單一同態(tài)。 但是當(dāng)f: RR+為 f(x)ex(R+為正實(shí)數(shù)集),那么 f為R,+到R+,的同構(gòu)映射,換言之,R,+與R+,同構(gòu)。 (2) 設(shè)h: RR為h(x)=2x,那么h為R,+到R,+的自同態(tài),因?yàn)閷?duì)任何實(shí)數(shù)x,y,有h(x+y)=2(x+y)2x + 2y=h(x)+ h(y)并且h為自同構(gòu)。 識(shí)別和證明兩個(gè)代數(shù)系統(tǒng)是否同構(gòu)是十分重要的代數(shù)學(xué)基本技能。 【例5.3.2】有代數(shù)系統(tǒng)Z,和代數(shù)系統(tǒng)B,其中是普通乘法,定義見表5.3.1,B=1,0,-1。定義映射f: ZB, n Z, 0 1 0 0 0 1)( nnnnf 表 5.3.1 則 a,b Z,有所以f(ab)=f(a) f(b)。f是Z,到B,的同態(tài),且f(Z)=B。異號(hào)至少有一個(gè)為同正或同負(fù)ba bababaf , 1 0, 0 , 1)( 0)()( 1 0)(),( 0 0)()( 1)( )(且非至少有一個(gè)為bfaf bfaf bfafbfaf 異號(hào)至少有一個(gè)為同正或同負(fù)ba baba , 1 0, 0 , 1 需要指出的是,同態(tài)映射并不是唯一的。如例5.3.1中(1)的同態(tài)映射可取不同的底數(shù)?!纠?.3.3】設(shè)A=a,b,c,d, B=0,1,2,3,*,+4定義見表5.3.2和5.3.3。證明: A,*和B,+4是同構(gòu)的。 表 5.3.2 表 5.3.3 證明設(shè) f: AB,f(a)=0,f(b)=1,f(c)=2,f(d)=3。顯然f是雙射,又*,+4均是可交換的。f(a*b)=f(b)=1 f(a)+4f(b)=0+41=1f(a*c)=f(c)=2 f(a)+4f(c)=0+42=2 f(a*d)=f(d)=3 f(a)+4f(d)=0+43=3 f(a*a)=f(a)=0 f(a)+4f(a)=0+40=0 f(b*b)=f(c)=2 f(b)+4f(b)=1+41=2 f(b*c)=f(d)=3 f(b)+4f(c)=1+42=3 f(b*d)=f(a)=0 f(b)+ 4f(d)=1+43=0 f(c*c)=f(a)=0 f(c)+4f(c)=2+42=0 f(c*d)=f(b)=1 f(c)+4f(d)=2+43=1 f(d*d)=f(c)=2 f(d)+4f(d)=3+43=2 故f是A,*到B,+4的同構(gòu)。證畢同構(gòu)是一個(gè)重要的概念,由上例可以說明不同形式的代數(shù)系統(tǒng),如果它們之間存在同構(gòu), 可以抽象地將它們看為本質(zhì)上是一樣的代數(shù)系統(tǒng),不同之處只是所使用的符號(hào)不一樣。注意到例5.3.3中,A對(duì)于*運(yùn)算,a是幺元,b、 d互逆,a、 c均以自身為逆元;B對(duì)于+4運(yùn)算,0(=f(a)是幺元,1(=f(b)、 3(=f(d)互逆,0(=f(a)、 2(=f(c)均以自身為逆元。 由此猜想: 同態(tài)保持性質(zhì),并把幺元映射成幺元。 為了進(jìn)一步討論同態(tài)的性質(zhì),我們引入同態(tài)像的概念。 定義5.3.2設(shè)f為代數(shù)系統(tǒng)S,*到T,的同態(tài)映射,那么稱f(S)為f的同態(tài)像(image under homomorphism)。定理5.3.1設(shè)f為代數(shù)系統(tǒng)S,*到T,的同態(tài),那么同態(tài)像 f(S)與構(gòu)成T,的一個(gè)子代數(shù)。證明只要證f(S)對(duì)運(yùn)算封閉即可。為此設(shè)a,b為f(S)中任意兩個(gè)元素,且f(a)=a , f(b)=b,那么a b=f(a) f(b)=f(a*b) f(S) 故f(S)對(duì)運(yùn)算封閉,f(S),為T的子代數(shù)。證畢很顯然, f為單射時(shí)S,*與同態(tài)像 f(S),同構(gòu),這使我們想到,同態(tài)像應(yīng)同S,*有許多共同的性質(zhì)。 定理5.3.2 設(shè)f是代數(shù)系統(tǒng)S,* 到 T,的滿同態(tài)(這里*, 均為二元運(yùn)算),那么(1) 當(dāng)運(yùn)算*滿足結(jié)合律、 交換律時(shí),T中運(yùn)算也滿足結(jié)合律、 交換律。(2) 如果S,* 關(guān)于*有幺元e,那么f(e)是T,中關(guān)于的幺元。 (3) 如果x-1是S,* 中元素x關(guān)于*的逆元,那么f(x-)=(f(x)-1是T,中元素f(x)關(guān)于的逆元。(4) 如果S,* 關(guān)于*有零元,那么f()是T,中關(guān)于的零元。證明僅證(2)、 (3)。 (2) 設(shè)S,*有關(guān)于*的幺元e??紤]T中任一元素b ,因?yàn)閒是滿射,所以必存在一個(gè)元素a S使b=f(a),那么b f(e)=f(a) f(e)=f(a*e)=f(a)=bf(e) b=f(e) f(a)=f(e*a)=f(a)=b 因此f(e)為T中關(guān)于的幺元。 (3) 設(shè)S,*中元素x有關(guān)于*的逆元x-1,考慮f(x)與f(x-1),那么f(x) f(x-1)=f(x*x-1)=f(e)f(x-1) f(x)=f(x-1*x)=f(e)這就是說,T中f(x)有關(guān)于的逆元f(x-1),即(f(x)-1f(x-1)這表明,同態(tài)也是保持一元求逆運(yùn)算的。證畢 (4) 關(guān)于零元的證明可仿上進(jìn)行,留給讀者完成。需要強(qiáng)調(diào)指出,上述定理中滿同態(tài)的條件是必要的,否則性質(zhì)只在同態(tài)像上有效,決不能隨意擴(kuò)大到T,上,下面將舉例說明這一點(diǎn)。對(duì)于具有多個(gè)代數(shù)運(yùn)算的兩個(gè)同類型系統(tǒng),同態(tài)是指相應(yīng)的n個(gè)同態(tài)方程均成立。一般同態(tài)無法保持消去律。因?yàn)橥瑯?gòu)映射是雙射,所以不僅保持性質(zhì)而且可逆,此時(shí)可將兩個(gè)代數(shù)系統(tǒng)視為一個(gè),只是運(yùn)算、 元素符號(hào)不同。 下面我們要討論同態(tài)核的概念。 定義5.3.3如果f為代數(shù)系統(tǒng)S ,*到T ,的同態(tài),并且T中有幺元e,那么稱下列集合為同態(tài)f的核(kernel of homomorphism),記為K(f)。K(f)=x|x S f(x)e 關(guān)于同態(tài)核我們有定理5.3.3。定理5.3.3設(shè)f為代數(shù)系統(tǒng)S,*到T,的同態(tài),如果K(f),那么 K(f),*為S,*的子代數(shù)。證明只要證K(f)對(duì)*運(yùn)算封閉即可。設(shè)K(f)中任意元素x,y,于是f(x)=f(y)=e 。 考慮f(x*y)=f(x) f(y)=e e=e 因此x*y K(f),故 K(f),*為S ,*的子代數(shù)。證畢 至此我們看到,一個(gè)同態(tài)映射f可導(dǎo)致兩個(gè)子代數(shù),一個(gè)是T ,的子代數(shù)f(S) ,另一個(gè)是S,*的子代數(shù) K(f),*。 【例5.4.1】設(shè)*和+是集合S上的兩個(gè)二元運(yùn)算,并滿足吸收律。證明: *和+均滿足冪等律。證明x,y S, 因?yàn)槲章沙闪?,所以x*x=x*(x+(x*y)=xx+x=x+(x*(x+y)=x因此,*和+均滿足冪等律。證畢5.4 例 題 選 解 【例5.4.2】設(shè)*和+是集合S上的兩個(gè)二元運(yùn)算, x,y S,均有x+y=x。證明: *對(duì)于+是可分配的。證明x,y,z S, 因?yàn)閤+y=x,所以x*(y+z)=x*y而 (x*y)+(x*z)=x*y故 x*(y+z)=(x*y)+(x*z) 左分配律成立。 又因?yàn)?(y+z)*x=y*x而 (y*x)+(z*x)=y*x故 (y+z)*x=(y*x)+(z*x)右分配律成立。 因此,*對(duì)于+是可分配的。證畢 【例5.4.3】(1) 設(shè)N4=0,1,2,3,f: N4N4定義如下:令F=f0,f1,f2,f3,其中f0為N4上的恒等函數(shù)。易證F, 為一代數(shù)系統(tǒng),且fi fj=fi+4j, 試證F,與N 4,+4同構(gòu)。 (2) 證明代數(shù)系統(tǒng)N,+與N,不同構(gòu)。 41 0 41 1)( xxxxf當(dāng)當(dāng) 解(1) 證明: 建立雙射h: FN4,使h(fi)i(i=0,1,2,3)由于對(duì)任何fi,fj F,h(fi fj)=h(fi+4j)=i+4j=h(fi)+4h(fj)故h為一同構(gòu)映射,F(xiàn),與N4,+4同構(gòu)得證。(2) 證明: (用反證法)設(shè)N,+與N,同構(gòu),f為任一同構(gòu)映射。 不失一般性,設(shè)有n,n2,f(n)為一質(zhì)數(shù)p。于是p=f(n)=f(n+0)=f(n)f(0) (5.4.1)p=f(n)=f(n-1+1)=f(n-1)f(1) (5.4.2)由f(n)為質(zhì)數(shù),據(jù)式(5.4.1),f(n)=1或f(0)=1; 據(jù)式(5.4.2), f(n-1)=1或f(1)=1。 總之,至少在兩處f的值為1,這與f為同構(gòu)映射(雙射)沖突。因此N,+與N,不同構(gòu)。 【例5.4.4】代數(shù)系統(tǒng)0,1,是否是代數(shù)系統(tǒng)N,+的同態(tài)像?(說明理由)解是。理由如下: 作映射f: N0,1,n N,令f(0)=0,f(n)=1(n0),則 n,m N ,當(dāng)n,m0時(shí), f(n+m)=1=1 1=f(n) f(m)當(dāng)n=0,m0時(shí), f(n+m)=1=0 1=f(n) f(m)當(dāng)n0,m=0時(shí), f(n+m)=1=1 0=f(n) f(m)當(dāng)n=0,m=0時(shí), f(n+m)=0=0 0=f(n) f(m) 即 n,m N, 均有 f(n+m)=f(n) f(m),故f是N,+到0,1,的同態(tài),因?yàn)閒是滿射,所以0,1,是N,+的同態(tài)像。 1. 設(shè)集合S=1,2,3,4,5,6,7,8,9,10,問下面定義的二元運(yùn)算*關(guān)于集合S是否封閉?習(xí)題五 (1) x*y=x-y(2) x*y=x+y-xy(3) x*y=(4) x*y=2xy(5) x*y=min(x,y)(6) x*y=max(x,y) (7) x*y=x(8) x*y=GCD(x,y),GCD(x,y)是x與y的最大公約數(shù)(9) x*y=LCM(x,y),LCM(x,y)是x與y的最小公倍數(shù)(10) x*y=質(zhì)數(shù)p的個(gè)數(shù),其中xpy2 yx 2 已知S上運(yùn)算*滿足結(jié)合律與交換律,證明: 對(duì)S中任意元素a,b,c,d有(a*b)*(c*d)(d*c)*a)*b3 設(shè)*是集合S上的可結(jié)合的二元運(yùn)算。 x,y S,若x*y=y*x,則x=y。證明:*滿足冪等律(對(duì)一切x S有x*x=x)。 4 S及其S上的運(yùn)算*如下定義,問各種定義下*運(yùn)算是否滿足結(jié)合律、 交換律,S, *中是否有幺元、 零元,S中哪些元素有逆元,哪些元素沒有逆元? (1) S為I(整數(shù)集),x*y=x-y (2) S為I(整數(shù)集),x*y=x+y-xy (3) S為Q(有理數(shù)集),x*y= (4) S為N(自然數(shù)集),x*y=2xy (5) S為N(自然數(shù)集),x*y=max(x,y)(min(x,y)(6) S為N(自然數(shù)集),x*y=x 2 yx 5 下列說法正確嗎?為什么? (1) 代數(shù)系統(tǒng)中的幺元與零元總不相等。 (2) 一代數(shù)系統(tǒng)中可能有三個(gè)右幺元,而只有一個(gè)左幺元。 (3) 代數(shù)系統(tǒng)中可能有一個(gè)元素,它既是左零元,又是右幺元。 (4) 幺元總有逆元。6 設(shè)A0,1,S為AA,即S=f1,f2,f3,f4,諸f由表5.1給出。 (1) 給出S上函數(shù)復(fù)合運(yùn)算的運(yùn)算表。 (2) S, 是否有幺元、 零元? (3) S,中哪些元素有逆元? 逆元是什么? 表 5.1 7 下面各集合都是N的子集,它們能否構(gòu)成代數(shù)系統(tǒng)N,+的子代數(shù)? (1) x|x N x的某次冪可以被16整除 (2) x|x N x與5互質(zhì) (3) x|x N x是30的因子 (4) x|x N x是30的倍數(shù) 8 證明: f: R+R,f(x)=lbx為代數(shù)系統(tǒng)R+,到R,的同態(tài)(這里R+為正實(shí)數(shù)集,R為實(shí)數(shù)集,為數(shù)乘運(yùn)算)。它是否為一同構(gòu)映射? 為什么? 9 設(shè)f: N0,1定義如下:證明: f為代數(shù)系統(tǒng)N,到0,1,的同態(tài)。它是單一同態(tài)、 滿同態(tài)嗎? 否則是自然數(shù)當(dāng) 0 )(2 1)( knnf k 10 設(shè)A=a,b,c。問代數(shù)系統(tǒng),A,和a,b,A,是否同構(gòu)?11 假定f是S,*到T,的同態(tài),試舉例說明: (1) f(S),的幺元(零元),可能不是T,的幺元(零元)。 (2) f(S),的成員的逆元,可能不是它在T,中的逆元。12 設(shè)f,g都是S,*到T,的同態(tài),并且*與運(yùn)算均滿足交換律和結(jié)合律。證明: 如下定義的函數(shù)h: STh(x)=f(x) g(x)是S,*到T,的同態(tài)。 13 設(shè)f,g分別是S,*到T,的同態(tài)和T,到H,的同態(tài)。證明: f g是S,*到H,的同態(tài)。 14 設(shè)f是R,+到C,的映射(這里R為實(shí)數(shù)集,C為復(fù)數(shù)集,+為普通加法運(yùn)算,為數(shù)乘運(yùn)算),且f: xe2ix, x R。問f是否同態(tài)? 如果是,請(qǐng)寫出同態(tài)像和同態(tài)核。

注意事項(xiàng)

本文(大學(xué)課件 離散數(shù)學(xué)(第二版)(蔡英) 第5章 代數(shù)系統(tǒng)的基本概念)為本站會(huì)員(燈火****19)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!