離散數(shù)學(xué)第九章代數(shù)系統(tǒng).ppt

1,第三部分代數(shù)結(jié)構(gòu),主要內(nèi)容代數(shù)系統(tǒng)-二元運(yùn)算及其性質(zhì)、代數(shù)系統(tǒng)和子代數(shù)半群與群-半群、獨(dú)異點(diǎn)、群環(huán)與域-環(huán)、整環(huán)、域格與布爾代數(shù)-格、布爾代數(shù),2,第九章代數(shù)系統(tǒng),主要內(nèi)容二元運(yùn)算及其性質(zhì)一元和二元運(yùn)算定義及其實(shí)例二元運(yùn)算的性質(zhì)代數(shù)系統(tǒng)代數(shù)系統(tǒng)定義及其實(shí)例子代數(shù)積代數(shù)代數(shù)系統(tǒng)的同態(tài)與同構(gòu),3,9.1二元運(yùn)算及其性質(zhì),定義9.1設(shè)S為集合，函數(shù)f：SSS稱為S上的二元運(yùn)算，簡(jiǎn)稱為二元運(yùn)算S中任何兩個(gè)元素都可以進(jìn)行運(yùn)算，且運(yùn)算的結(jié)果惟一S中任何兩個(gè)元素的運(yùn)算結(jié)果都屬于S，即S對(duì)該運(yùn)算封閉,例1(1)自然數(shù)集合N上的加法和乘法是N上的二元運(yùn)算，但減法和除法不是(2)整數(shù)集合Z上的加法、減法和乘法都是Z上的二元運(yùn)算，而除法不是(3)非零實(shí)數(shù)集R*上的乘法和除法都是R*上的二元運(yùn)算，而加法和減法不是,4,實(shí)例,(4)設(shè)Mn(R)表示所有n階(n2)實(shí)矩陣的集合，即則矩陣加法和乘法都是Mn(R)上的二元運(yùn)算.(5)S為任意集合，則、為P(S)上二元運(yùn)算.(6)SS為S上的所有函數(shù)的集合，則合成運(yùn)算為SS上二元運(yùn)算.,5,一元運(yùn)算的定義與實(shí)例,定義9.2設(shè)S為集合，函數(shù)f:SS稱為S上的一元運(yùn)算，簡(jiǎn)稱一元運(yùn)算.例2(1)求相反數(shù)是整數(shù)集合Z,有理數(shù)集合Q和實(shí)數(shù)集合R上的一元運(yùn)算(2)求倒數(shù)是非零有理數(shù)集合Q*,非零實(shí)數(shù)集合R*上一元運(yùn)算(3)求共軛復(fù)數(shù)是復(fù)數(shù)集合C上的一元運(yùn)算(4)在冪集P(S)上規(guī)定全集為S，則求絕對(duì)補(bǔ)運(yùn)算是P(S)上的一元運(yùn)算.(5)設(shè)S為集合，令A(yù)為S上所有雙射函數(shù)的集合，ASS，求一個(gè)雙射函數(shù)的反函數(shù)為A上的一元運(yùn)算.(6)在n(n2)階實(shí)矩陣的集合Mn(R)上，求轉(zhuǎn)置矩陣是Mn(R)上的一元運(yùn)算.,6,二元與一元運(yùn)算的表示,1算符可以用,等符號(hào)表示二元或一元運(yùn)算，稱為算符.對(duì)二元運(yùn)算，如果x與y運(yùn)算得到z，記做xy=z對(duì)一元運(yùn)算,x的運(yùn)算結(jié)果記作x.,2表示二元或一元運(yùn)算的方法:解析公式和運(yùn)算表公式表示例設(shè)R為實(shí)數(shù)集合，如下定義R上的二元運(yùn)算：x,yR,xy=x.那么34=3，0.5(3)=0.5,7,運(yùn)算表：表示有窮集上的一元和二元運(yùn)算,運(yùn)算表,二元運(yùn)算的運(yùn)算表一元運(yùn)算的運(yùn)算表,8,例3設(shè)S=P(a,b)，S上的和運(yùn)算的運(yùn)算表如下,運(yùn)算表的實(shí)例,9,二元運(yùn)算的性質(zhì),定義9.3設(shè)為S上的二元運(yùn)算,(1)若對(duì)任意x,yS有xy=yx,則稱運(yùn)算在S上滿足交換律.(2)若對(duì)任意x,y,zS有(xy)z=x(yz),則稱運(yùn)算在S上滿足結(jié)合律.(3)若對(duì)任意xS有xx=x,則稱運(yùn)算在S上滿足冪等律.,定義9.4設(shè)和為S上兩個(gè)不同的二元運(yùn)算,(1)若對(duì)任意x,y,zS有(xy)z=(xz)(yz)，z(xy)=(zx)(zy),則稱運(yùn)算對(duì)運(yùn)算滿足分配律.(2)若和都可交換,且對(duì)任意x,yS有x(xy)=x，x(xy)=x,則稱和運(yùn)算滿足吸收律.,10,實(shí)例,Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2,11,實(shí)例,Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2,12,特異元素：?jiǎn)挝辉?、零?定義9.5設(shè)為S上的二元運(yùn)算,(1)如果存在el(或er)S，使得對(duì)任意xS都有elx=x(或xer=x)，則稱el(或er)是S中關(guān)于運(yùn)算的左(或右)單位元.若eS關(guān)于運(yùn)算既是左單位元又是右單位元，則稱e為S上關(guān)于運(yùn)算的單位元.單位元也叫做幺元.(2)如果存在l(或r)S，使得對(duì)任意xS都有l(wèi)x=l(或xr=r)，則稱l(或r)是S中關(guān)于運(yùn)算的左(或右)零元.若S關(guān)于運(yùn)算既是左零元又是右零元，則稱為S上關(guān)于運(yùn)算的零元.,13,可逆元素和逆元,(3)設(shè)為S上的二元運(yùn)算,令e為S中關(guān)于運(yùn)算的單位元.對(duì)于xS，如果存在yl(或yr)S使得ylx=e（或xyr=e）則稱yl(或yr)是x的左逆元（或右逆元）.關(guān)于運(yùn)算，若yS既是x的左逆元又是x的右逆元，則稱y為x的逆元.如果x的逆元存在，就稱x是可逆的.,14,實(shí)例,15,惟一性定理,定理9.1設(shè)為S上的二元運(yùn)算，el和er分別為S中關(guān)于運(yùn)算的左和右單位元，則el=er=e為S上關(guān)于運(yùn)算的惟一的單位元.證：el=eler(er為右單位元)eler=er(el為左單位元)所以el=er,將這個(gè)單位元記作e.假設(shè)e也是S中的單位元，則有e=ee=e.惟一性得證.類似地可以證明關(guān)于零元的惟一性定理.注意：當(dāng)|S|2，單位元與零元是不同的；當(dāng)|S|=1時(shí)，這個(gè)元素既是單位元也是零元.,16,定理9.2設(shè)為S上可結(jié)合的二元運(yùn)算,e為該運(yùn)算的單位元,對(duì)于xS如果存在左逆元yl和右逆元yr,則有yl=yr=y,且y是x的惟一的逆元.證：由ylx=e和xyr=e得yl=yle=yl(xyr)=(ylx)yr=eyr=yr令yl=yr=y,則y是x的逆元.假若yS也是x的逆元,則y=ye=y(xy)=(yx)y=ey=y所以y是x惟一的逆元.說(shuō)明：對(duì)于可結(jié)合的二元運(yùn)算，可逆元素x只有惟一的逆元，記作x1,惟一性定理,17,9.2代數(shù)系統(tǒng),定義9.6非空集合S和S上k個(gè)一元或二元運(yùn)算f1,f2,fk組成的系統(tǒng)稱為代數(shù)系統(tǒng),簡(jiǎn)稱代數(shù)，記做.實(shí)例：(1),是代數(shù)系統(tǒng)，+和分別表示普通加法和乘法.(2)是代數(shù)系統(tǒng)，和分別表示n階(n2)實(shí)矩陣的加法和乘法.(3)是代數(shù)系統(tǒng)，Zn0,1,n-1，和分別表示模n的加法和乘法，對(duì)于x,yZn，xy=(xy)modn，xy=(xy)modn(4)是代數(shù)系統(tǒng)，和為并和交，為絕對(duì)補(bǔ),18,代數(shù)系統(tǒng)的成分與表示,構(gòu)成代數(shù)系統(tǒng)的成分：集合（也叫載體，規(guī)定了參與運(yùn)算的元素）運(yùn)算（這里只討論有限個(gè)二元和一元運(yùn)算）代數(shù)常數(shù)（通常是與運(yùn)算相關(guān)的特異元素：如單位元等）研究代數(shù)系統(tǒng)時(shí)，如果把運(yùn)算具有的特異元素也作為系統(tǒng)的性質(zhì)之一，那么這些特異元素可以作為系統(tǒng)的成分，叫做代數(shù)常數(shù).例如：代數(shù)系統(tǒng)：集合Z,運(yùn)算+,代數(shù)常數(shù)0代數(shù)系統(tǒng)：集合P(S),運(yùn)算和，無(wú)代數(shù)常數(shù),19,代數(shù)系統(tǒng)的表示,(1)列出所有的成分：集合、運(yùn)算、代數(shù)常數(shù)（如果存在）如,(2)列出集合和運(yùn)算，在規(guī)定系統(tǒng)性質(zhì)時(shí)不涉及具有單位元的性質(zhì)（無(wú)代數(shù)常數(shù)）如,(3)用集合名稱簡(jiǎn)單標(biāo)記代數(shù)系統(tǒng)在前面已經(jīng)對(duì)代數(shù)系統(tǒng)作了說(shuō)明的前提下使用如代數(shù)系統(tǒng)Z,P(B),20,同類型與同種代數(shù)系統(tǒng),定義9.7(1)如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對(duì)應(yīng)運(yùn)算的元數(shù)相同，且代數(shù)常數(shù)的個(gè)數(shù)也相同，則稱它們是同類型的代數(shù)系統(tǒng).(2)如果兩個(gè)同類型的代數(shù)系統(tǒng)規(guī)定的運(yùn)算性質(zhì)也相同，則稱為同種的代數(shù)系統(tǒng).例如V1=,V2=V1,V2是同類型的代數(shù)系統(tǒng)，它們都含有2個(gè)二元運(yùn)算,2個(gè)代數(shù)常數(shù).,21,運(yùn)算性質(zhì)比較,V1=,V2=,所以,V1,V2是同類型的代數(shù)系統(tǒng),但不是同種的代數(shù)系統(tǒng).,22,子代數(shù)系統(tǒng),定義9.8設(shè)V=是代數(shù)系統(tǒng)，B是S的非空子集，如果B對(duì)f1,f2,fk都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱是V的子代數(shù)系統(tǒng)，簡(jiǎn)稱子代數(shù).有時(shí)將子代數(shù)系統(tǒng)簡(jiǎn)記為B.,實(shí)例N是的子代數(shù)，N也是的子代數(shù)N0是的子代數(shù)，但不是的子代數(shù)說(shuō)明：子代數(shù)和原代數(shù)是同種的代數(shù)系統(tǒng)對(duì)于任何代數(shù)系統(tǒng)V=，其子代數(shù)一定存在.,23,關(guān)于子代數(shù)的術(shù)語(yǔ),(1)最大的子代數(shù)：就是V本身(2)最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構(gòu)成的集合是B，且B對(duì)V中所有的運(yùn)算都是封閉的，則B就構(gòu)成了V的最小的子代數(shù)(3)最大和最小的子代數(shù)稱為V的平凡的子代數(shù)(4)若B是S的真子集，則B構(gòu)成的子代數(shù)稱為V的真子代數(shù).例設(shè)V=,令nZ=nz|zZ,n為自然數(shù)，則nZ是V的子代數(shù)當(dāng)n=1和0時(shí)，nZ是V的平凡的子代數(shù)，其他的都是V的非平凡的真子代數(shù).,24,積代數(shù),定義9.9設(shè)V1=和V2=是同類型的代數(shù)系統(tǒng)，和為二元運(yùn)算，在集合AB上如下定義二元運(yùn)算，,AB，有=稱V=為V1與V2的積代數(shù)，記作V1V2.這時(shí)也稱V1和V2為V的因子代數(shù).,實(shí)例Z2=0,1，V=，V1V2=Z2Z2=,=注意：積代數(shù)的定義可以推廣到具有多個(gè)運(yùn)算的同類型的代數(shù)系統(tǒng),模2的加法:x,yZ2xy=(x+y)mod2,25,積代數(shù),實(shí)例已知Z2=0,1，V=，其中為模2的加法:x,yZ2,有xy=(x+y)mod2.求V1V2=,注意：積代數(shù)的定義可以推廣到具有多個(gè)運(yùn)算的同類型的代數(shù)系統(tǒng),解:Z2Z2=,26,積代數(shù),例V1=,V2=,積代數(shù)為,ZM2(R),o=,27,積代數(shù)的性質(zhì),定理9.3設(shè)V1=和V2=是同類型的代數(shù)系統(tǒng)，V1V2=是它們的積代數(shù).(1)如果和運(yùn)算是可交換（可結(jié)合、冪等）的，那么運(yùn)算也是可交換（可結(jié)合、冪等）的(2)如果e1和e2（1和2）分別為和運(yùn)算的單位元（零元），那么（）也是運(yùn)算的單位元（零元）(3)如果x和y分別為和運(yùn)算的可逆元素，那么也是運(yùn)算的可逆元素，其逆元就是,即積代數(shù)能夠保持因子代數(shù)中的許多良好的性質(zhì).,28,9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu),引言,在現(xiàn)實(shí)社會(huì)中，存在著很多代數(shù)系統(tǒng)，但仔細(xì)分析這些眾多的代數(shù)系統(tǒng)發(fā)現(xiàn)，有些代數(shù)系統(tǒng)，他們之間表面上似乎不相同，但他們實(shí)際上“相同”。如有兩個(gè)代數(shù)系統(tǒng)和，其運(yùn)算“*”和“。”分別定義如下表,29,9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu),代數(shù)系統(tǒng)V1=和V2=,若把表1中的奇和偶分別替換成正和負(fù),就可以得到表2,表1,表2,這個(gè)替換可以表示成函數(shù):,F=,在雙射F的作用下,代數(shù)系統(tǒng)V1轉(zhuǎn)換成了代數(shù)系統(tǒng)V2.,它們是同構(gòu)的,都是抽象代數(shù)系統(tǒng)a,b的實(shí)例.,30,9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu),定義9.10設(shè)V1=和V2=是同類型的代數(shù)系統(tǒng)，f:AB，且x,yA有f(xy)=f(x)f(y),則稱f是V1到V2的同態(tài)映射，簡(jiǎn)稱同態(tài).,31,9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu),同態(tài)分類：,(1)f如果是單射，則稱為單同態(tài)(2)如果是滿射，則稱為滿同態(tài)，這時(shí)稱V2是V1的同態(tài)像，記作V1V2(3)如果是雙射，則稱為同構(gòu)，也稱代數(shù)系統(tǒng)V1同構(gòu)于V2，記作V1V2(4)如果V1=V2，則稱作自同態(tài),32,實(shí)例(判斷自同態(tài)),例V=,判斷下面的哪些函數(shù)是V的自同態(tài)？(1)f(x)=|x|(2)f(x)=2x(3)f(x)=x2(4)f(x)=1/x(5)f(x)=x(6)f(x)=x+1,解(2),(5),(6)不是自同態(tài).(1)是同態(tài)，f(xy)=|xy|=|x|y|=f(x)f(y)(3)是同態(tài)，f(xy)=(xy)2=x2y2=f(x)f(y)(4)是同態(tài)，f(xy)=1/(xy)=1/x1/y=f(x)f(y),33,實(shí)例(課本P177例9.11),(1)設(shè)V1=,V2=其中Z為整數(shù)集，+為普通加法；Zn=0,1,n1，為模n加.令f:ZZn，f(x)=(x)modn那么f是V1到V2的滿同態(tài),(3)設(shè)V=，其中Z為整數(shù)集，+為普通加法.aZ，令fa:ZZ，fa(x)=ax，那么fa是V的自同態(tài).當(dāng)a=0時(shí)稱f0為零同態(tài)；當(dāng)a=1時(shí)，稱fa為自同構(gòu)；除此之外其他的fa都是單自同態(tài).,(2)設(shè)V1=,V2=，其中R和R*分別為實(shí)數(shù)集與非零實(shí)數(shù)集，+和分別表示普通加法與乘法令f:RR*，f(x)=ex則f是V1到V2的單同態(tài).,34,第九章習(xí)題課,主要內(nèi)容代數(shù)系統(tǒng)的構(gòu)成：非空集合、封閉的二元和一元運(yùn)算、代數(shù)常數(shù)二元運(yùn)算性質(zhì)和特異元素：交換律、結(jié)合律、冪等律、分配律、吸收律、單位元、零元、可逆元和逆元同類型的與同種的代數(shù)系統(tǒng)子代數(shù)的定義與實(shí)例積代數(shù)的定義與性質(zhì)代數(shù)系統(tǒng)的同態(tài)與同構(gòu),35,基本要求,判斷給定集合和運(yùn)算能否構(gòu)成代數(shù)系統(tǒng)判斷給定二元運(yùn)算的性質(zhì)求而二元運(yùn)算的特異元素了解同類型和同種代數(shù)系統(tǒng)的概念了解子代數(shù)的基本概念計(jì)算積代數(shù)判斷函數(shù)是否為同態(tài)映射和同構(gòu)映射,36,練習(xí)1,1設(shè)運(yùn)算為Q上的二元運(yùn)算，x,yQ,xy=x+y+2xy,(1)判斷運(yùn)算是否滿足交換律和結(jié)合律，并說(shuō)明理由.(2)求出運(yùn)算的單位元、零元和所有可逆元素的逆元.,(1)運(yùn)算可交換，可結(jié)合.任取x,yQ,xy=x+y+2xy=y+x+2yx=yx,任取x,y,zQ,(xy)z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyzx(yz)=x+(y+z+2yz)+2x(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz,37,(2)設(shè)運(yùn)算的單位元和零元分別為e和，則對(duì)于任意x有xe=x成立，即x+e+2xe=xe=0由于運(yùn)算可交換，所以0是幺元.對(duì)于任意x有x=成立，即x+2x=x+2x=0=1/2給定x，設(shè)x的逆元為y,則有xy=0成立，即x+y+2xy=0(x1/2)因此當(dāng)x1/2時(shí)，是x的逆元.,練習(xí)1解答,38,2下面是三個(gè)運(yùn)算表(1)說(shuō)明那些運(yùn)算是可交換的、可結(jié)合的、冪等的.(2)求出每個(gè)運(yùn)算的單位元、零元、所有可逆元素的逆元,練習(xí)2,39,解,練習(xí)2解答,(1)*滿足交換律，滿足結(jié)合律，不滿足冪等律.不滿足交換律，滿足結(jié)合律，滿足冪等律.滿足交換律，滿足結(jié)合律，不滿足冪等律.(2)*的單位元為b，沒有零元，a1=c,b1=b,c1=a的單位元和零元都不存在，沒有可逆元素.的單位元為a，零元為c，a1=a，b,c不是可逆元素.說(shuō)明：關(guān)于結(jié)合律的判斷需要針對(duì)運(yùn)算元素的每種選擇進(jìn)行驗(yàn)證，若|A|=n，一般需要驗(yàn)證n3個(gè)等式.單位元和零元不必參與驗(yàn)證.通過對(duì)具體運(yùn)算性質(zhì)的分析也可能簡(jiǎn)化驗(yàn)證的復(fù)雜性.,40,判別運(yùn)算性質(zhì)的方法,通過運(yùn)算表可以判別運(yùn)算性質(zhì),也可以求運(yùn)算的特異元素.具體辦法如下:如果運(yùn)算表的元素關(guān)于主對(duì)角線對(duì)稱分布,那么運(yùn)算可交換的.如果主對(duì)角線元素的排列順序與表頭元素的順序一樣,那么運(yùn)算是冪等的.如果一個(gè)元素所在行和列的元素排列順序都與表頭元素排列順序一致,那么這個(gè)元素是單位元.如果一個(gè)元素的行和列元素都是這個(gè)元素自身,那么這個(gè)元素是零元.,41