1、1,第4章二元關(guān)系與函數(shù),4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運(yùn)算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價(jià)關(guān)系和偏序關(guān)系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù),2,4.1集合的笛卡兒積和二元關(guān)系,有序?qū)Φ芽▋悍e及其性質(zhì)二元關(guān)系的定義二元關(guān)系的表示,3,有序?qū)?定義由兩個(gè)元素x和y，按照一定的順序組成的二元組稱(chēng)為有序?qū)?或序偶)，記作或(x,y)實(shí)例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)有序?qū)哂幸韵绿攸c(diǎn)：(1)當(dāng)xy時(shí)，(2)兩個(gè)有序?qū)ο嗟鹊某浞直匾獥l件是x=u且y=v即=x=uy=v,4,有序n元組,定義一個(gè)有序n(n3)元組是一個(gè)有序?qū)Γ渲械谝粋€(gè)元素是一個(gè)有序n-1元組，即=,xn當(dāng)

2、n=1時(shí),形式上可以看成有序1元組.例有序三元組：空間直角坐標(biāo)系中點(diǎn)的坐標(biāo),5,笛卡兒積,定義設(shè)A,B為集合，A與B的笛卡兒積記作AB，即AB=|xAyB若|A|=m,|B|=n,則|AB|=mn,例A=1,2,3,B=a,b,cAB=,BA=,6,笛卡兒積的性質(zhì),若A或B中有一個(gè)為空集，則AB就是空集.A=B=若AB且A和B都不是空集時(shí)：ABBA(不適合交換律)若A、B和C都不是空集時(shí)：(AB)CA(BC)(不適合結(jié)合律),7,笛卡兒積的性質(zhì),對(duì)于并或交運(yùn)算滿足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA),8,性質(zhì)的證

3、明,證明A(BC)=(AB)(AC)證任取，則有A(BC)xAyBCxA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以A(BC)=(AB)(AC).,9,性質(zhì)的證明(續(xù)),證明(BC)A=(BA)(CA)證任取，則有(BC)Ax(BC)yA(xBxC)yA(xByA)(xCyA)BACA(BA)(CA)所以(BC)A=(BA)(CA),10,證明(AB)(CD)=(AC)(BD)證任取，則有(AB)(CD)x(AB)y(CD)(xAxB)(yCyD)(xAyC)(xByD)ACBD(AC)(BD)所以(AB)(CD)=(AC)(BD)注：(AB)(CD)=(AD)(BC),1

4、1,解(1)任取ACxAyCxByDBD,例(1)證明A=BC=DAC=BD(2)AC=BD是否推出A=BC=D?為什么？,(2)不一定.反例如下：A=1，B=2,C=D=,則AC=BD但是AB.,12,n階笛卡兒積,定義設(shè)A1,A2,An是集合，它們的n階笛卡兒積記作A1A2An，即A1A2An=|x1A1x2A2xnAn特別地，當(dāng)A1=A2=An=A時(shí)，可簡(jiǎn)記為An例A=0,1時(shí)，A3=,13,二元關(guān)系的定義,定義如果一個(gè)集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集則稱(chēng)該集合為一個(gè)二元關(guān)系,簡(jiǎn)稱(chēng)為關(guān)系，記作R.如R,可記作xRy；如果R,則記作xy例：R=,S

5、=,a,b.R是二元關(guān)系,當(dāng)a,b不是有序?qū)r(shí)，S不是二元關(guān)系根據(jù)上面的記法，可以寫(xiě)1R2,aRb,ac等.,14,從A到B的關(guān)系與A上的關(guān)系,定義設(shè)A,B為集合,AB的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)則叫做A上的二元關(guān)系.例A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=.那么R1,R2,R3,R4是從A到B的二元關(guān)系,R3和R4同時(shí)也是A上的二元關(guān)系.計(jì)數(shù)|A|=n,|AA|=n2,AA的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,則A上有=512個(gè)不同的二元關(guān)系.,15,A上重要關(guān)系的實(shí)例,設(shè)A為任意集合，是A上的關(guān)系，稱(chēng)為空關(guān)系EA,I

6、A分別稱(chēng)為全域關(guān)系與恒等關(guān)系，定義如下：EA=|xAyA=AAIA=|xA例如,A=1,2,則EA=,IA=,16,A上重要關(guān)系的實(shí)例（續(xù)）,小于等于關(guān)系LA,整除關(guān)系DA,包含關(guān)系R定義：LA=|x,yAxy,AR，R為實(shí)數(shù)集合DB=|x,yBx整除y,BZ*,Z*為非0整數(shù)集R=|x,yAxy,A是集合族.類(lèi)似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.,17,實(shí)例,例如A=1,2,3,B=a,b,則LA=,DA=,A=P(B)=,a,b,a,b,則A上的包含關(guān)系是R=,18,關(guān)系的表示,表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖關(guān)系矩陣：若A=a1,a2,am，B=b

7、1,b2,bn，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR=rijmn,其中rij=1R.關(guān)系圖：若A=x1,x2,xm，R是從A上的關(guān)系，R的關(guān)系圖是GR=,其中A為頂點(diǎn)集，R為有向邊集.如果屬于關(guān)系R，在圖中就有一條從xi到xj的有向邊.注意：A,B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖適于表示A上的關(guān)系,19,實(shí)例,A=1,2,3,4,R=,R的關(guān)系矩陣MR和關(guān)系圖GR如下：,20,基本運(yùn)算定義定義域、值域、域逆、合成、限制、像基本運(yùn)算的性質(zhì)冪運(yùn)算定義求法性質(zhì),4.2關(guān)系的運(yùn)算,21,關(guān)系的基本運(yùn)算定義,定義域、值域和域domR=x|y(R)ranR=y|x(

8、R)fldR=domRranR,例R=,則domR=1,2,4ranR=2,3,4fldR=1,2,3,4,22,關(guān)系的基本運(yùn)算定義（續(xù)）,逆與合成R1=|xRyRS=|y(xSyyRz),例R=,S=,R1=,RS=,SR=,23,限制與像,定義F在A上的限制FA=|xFyxAA在F下的像FA=ran(FA)例R=,R1=,R1=2,4R=R1,2=2,3,4注意：FAF,FAranF,24,關(guān)系基本運(yùn)算的性質(zhì),定理1設(shè)F是任意的關(guān)系,則(1)(F1)1=F(2)domF1=ranF,ranF1=domF證(1)任取,由逆的定義有(F1)1F1F所以有(F1)1=F(2)任取x,xdomF1

9、y(F1)y(F)xranF所以有domF1=ranF.同理可證ranF1=domF.,25,定理2設(shè)F,G,H是任意的關(guān)系,則(1)(FG)H=F(GH)(2)(FG)1=G1F1證(1)任取,(FG)Ht(HFG)t(Hs(GF)ts(HGF)s(t(HG)F)s(GHF)F(GH)所以(FG)H=F(GH),關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,26,(2)任取,(FG)1FGt(GF)t(G1F1)t(F1G1)G1F1所以(FG)1=G1F1,關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,27,定理3設(shè)F,G,H是任意的關(guān)系,則(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)FGFH(4)(GH

10、)FGFHF注意：合成運(yùn)算對(duì)于并運(yùn)算是可分配的，但對(duì)交運(yùn)算分配后得到只是包含關(guān)系,關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,28,證明(1)任取,F(GH)t(GHF)t(GH)F)t(GF)t(HF)(對(duì)的分配律)FGFHFGFH所以F(GH)=FGFH,關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,29,例(3)設(shè)如下關(guān)系F=,G=H=則有F(GH)=F=FGFH=所以F(GH)FGFH,關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,30,A上關(guān)系的冪運(yùn)算,設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：(1)R0=|xA=IA(2)Rn+1=RnR注意：對(duì)于A上的任何關(guān)系R1和R2都有R10=R20=IA對(duì)于A上的任何關(guān)系R都有R0R=RR

11、0=RR1=R,31,冪的求法,對(duì)于集合表示的關(guān)系R，計(jì)算Rn就是n個(gè)R左復(fù)合.3種方法：集合運(yùn)算、關(guān)系矩陣和關(guān)系圖.關(guān)系矩陣法就是n個(gè)R的關(guān)系矩陣相乘,其中矩陣相乘時(shí)與計(jì)算普通矩陣類(lèi)似，但是相加時(shí)的加法是邏輯加，即0+0=0,0+1=1,1+0=0,1+1=1.,32,冪的求法（續(xù)）,例設(shè)A=a,b,c,d,R=,求R的各次冪,分別用矩陣和關(guān)系圖表示.解R與R2的關(guān)系矩陣分別為,33,同理，R0=IA,R3和R4的矩陣分別是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=,冪的求法（續(xù)）,34,R0,R1,R2,R3,的關(guān)系圖如下圖所示,冪的求法（續(xù)）,R0

12、,R1,R2=R4=,R3=R5=,35,冪運(yùn)算的性質(zhì),定理設(shè)A為n元集,R是A上的關(guān)系,則存在自然數(shù)s和t,使得Rs=Rt.證R為A上的關(guān)系,由于|A|=n,A上的不同關(guān)系只有個(gè).當(dāng)列出R的各次冪R0,R1,R2,必存在自然數(shù)s和t使得Rs=Rt.,36,定理設(shè)R是A上的關(guān)系,m,nN,則(1)RmRn=Rm+n(2)(Rm)n=Rmn證用歸納法(1)對(duì)于任意給定的mN,施歸納于n.若n=0,則有RmR0=RmIA=Rm=Rm+0假設(shè)RmRn=Rm+n,則有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以對(duì)一切m,nN有RmRn=Rm+n.,冪運(yùn)算的性質(zhì)（續(xù)）,37,(2)對(duì)

13、于任意給定的mN,施歸納于n.若n=0,則有(Rm)0=IA=R0=Rm0假設(shè)(Rm)n=Rmn,則有(Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1)所以對(duì)一切m,nN有(Rm)n=Rmn.,冪運(yùn)算的性質(zhì)（續(xù)）,38,4.3關(guān)系的性質(zhì),自反性反自反性對(duì)稱(chēng)性反對(duì)稱(chēng)性傳遞性,39,自反性與反自反性,定義設(shè)R為A上的關(guān)系,(1)若xA,有R,則稱(chēng)R在A上是自反的.(2)若xA,有R,則稱(chēng)R在A上是反自反的.例：自反關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA小于等于關(guān)系LA,整除關(guān)系DA反自反關(guān)系：實(shí)數(shù)集上的小于關(guān)系冪集上的真包含關(guān)系,40,實(shí)例,例A=1,2,3,R1,R2,R

14、3是A上的關(guān)系,其中R1,R2,R3,R2自反,R3反自反,R1既不是自反也不是反自反的,41,對(duì)稱(chēng)性與反對(duì)稱(chēng)性,定義設(shè)R為A上的關(guān)系,(1)若R,則R,那么稱(chēng)R為A上的對(duì)稱(chēng)關(guān)系.(2)若R并且xy,則R),那么稱(chēng)R為A上的反對(duì)稱(chēng)關(guān)系.例：對(duì)稱(chēng)關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對(duì)稱(chēng)關(guān)系：恒等關(guān)系IA，空關(guān)系是A上的反對(duì)稱(chēng)關(guān)系.,42,實(shí)例,例設(shè)A1,2,3,R1,R2,R3和R4都是A上的關(guān)系,其中R1,，R2,R3,，R4,R1對(duì)稱(chēng)、反對(duì)稱(chēng).R2對(duì)稱(chēng)，不反對(duì)稱(chēng).R3反對(duì)稱(chēng)，不對(duì)稱(chēng).R4不對(duì)稱(chēng)、也不反對(duì)稱(chēng).,43,傳遞性,定義設(shè)R為A上的關(guān)系,若R且R,則R,那么稱(chēng)R是A上的傳遞

15、關(guān)系.例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系小于等于關(guān)系,小于關(guān)系，整除關(guān)系，包含關(guān)系，真包含關(guān)系,44,實(shí)例,例設(shè)A1,2,3,R1,R2,R3是A上的關(guān)系,其中R1,R2,R3,R1和R3是A上的傳遞關(guān)系R2不是A上的傳遞關(guān)系,45,關(guān)系性質(zhì)的充要條件,設(shè)R為A上的關(guān)系,則(1)R在A上自反當(dāng)且僅當(dāng)IAR(2)R在A上反自反當(dāng)且僅當(dāng)RIA=(3)R在A上對(duì)稱(chēng)當(dāng)且僅當(dāng)R=R1(4)R在A上反對(duì)稱(chēng)當(dāng)且僅當(dāng)RR1IA(5)R在A上傳遞當(dāng)且僅當(dāng)RRR,46,關(guān)系性質(zhì)判別,47,實(shí)例,例判斷下圖中關(guān)系的性質(zhì),并說(shuō)明理由.,(b)反自反，不是自反的；反對(duì)稱(chēng)，不是對(duì)稱(chēng)的；是傳遞的.,(a)不自反也

16、不反自反；對(duì)稱(chēng),不反對(duì)稱(chēng)；不傳遞.,(c)自反，不反自反；反對(duì)稱(chēng)，不是對(duì)稱(chēng)；不傳遞.,48,自反性證明,證明模式證明R在A上自反任取x,xA.R前提推理過(guò)程結(jié)論,例證明若IAR，則R在A上自反.證任取x,xAIAR因此R在A上是自反的.,49,對(duì)稱(chēng)性證明,證明模式證明R在A上對(duì)稱(chēng)任取R.R前提推理過(guò)程結(jié)論,例證明若R=R1,則R在A上對(duì)稱(chēng).證任取RR1R因此R在A上是對(duì)稱(chēng)的.,50,反對(duì)稱(chēng)性證明,證明模式證明R在A上反對(duì)稱(chēng)任取RR.x=y前提推理過(guò)程結(jié)論,例證明若RR1IA,則R在A上反對(duì)稱(chēng).證任取RRRR1RR1IAx=y因此R在A上是反對(duì)稱(chēng)的.,51,傳遞性證明,證明模式證明R在A上傳遞任

17、取，RR.R前提推理過(guò)程結(jié)論,例證明若RRR,則R在A上傳遞.證任取，RRRRR因此R在A上是傳遞的.,52,運(yùn)算與性質(zhì)的關(guān)系,53,4.4關(guān)系的閉包,閉包定義閉包的構(gòu)造方法集合表示矩陣表示圖表示閉包的性質(zhì),54,閉包定義,定義設(shè)R是非空集合A上的關(guān)系,R的自反（對(duì)稱(chēng)或傳遞）閉包是A上的關(guān)系R,使得R滿足以下條件：（1）R是自反的（對(duì)稱(chēng)的或傳遞的）（2）RR（3）對(duì)A上任何包含R的自反（對(duì)稱(chēng)或傳遞）關(guān)系R有RR.一般將R的自反閉包記作r(R),對(duì)稱(chēng)閉包記作s(R),傳遞閉包記作t(R).,55,閉包的構(gòu)造方法,定理設(shè)R為A上的關(guān)系,則有(1)r(R)=RR0(2)s(R)=RR1(3)t(R)

18、=RR2R3說(shuō)明：對(duì)于有窮集合A(|A|=n)上的關(guān)系,(3)中的并最多不超過(guò)Rn.若R是自反的，則r(R)=R;若R是對(duì)稱(chēng)的，則s(R)=R;若R是傳遞的，則t(R)=R.,設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,Mr,Ms和Mt,則Mr=M+EMs=M+MMt=M+M2+M3+E是和M同階的單位矩陣,M是M的轉(zhuǎn)置矩陣.注意：上述等式中矩陣的元素相加時(shí)使用邏輯加,56,閉包的構(gòu)造方法（續(xù)）,57,閉包的構(gòu)造方法（續(xù)）,設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系圖分別記為G,Gr,Gs,Gt,則Gr,Gs,Gt的頂點(diǎn)集與G的頂點(diǎn)集相等.除了G的邊以外,以下述方法添加新邊：考

19、察G的每個(gè)頂點(diǎn),如果沒(méi)有環(huán)就加上一個(gè)環(huán)，最終得到Gr.考察G的每條邊,如果有一條xi到xj的單向邊,ij,則在G中加一條xj到xi的反方向邊，最終得到Gs.考察G的每個(gè)頂點(diǎn)xi,找從xi出發(fā)的每一條路徑，如果從xi到路徑中任何結(jié)點(diǎn)xj沒(méi)有邊，就加上這條邊.當(dāng)檢查完所有的頂點(diǎn)后就得到圖Gt.,58,例設(shè)A=1,2,3,R=,則有r(R)=RR0=,=,s(R)=RR-1=,=,t(R)=RR2=,=,59,例設(shè)A=1,2,R=,R和r(R),s(R),t(R)的關(guān)系矩陣如下,60,例設(shè)A=a,b,c,d,R=,R和r(R),s(R),t(R)的關(guān)系圖如下圖所示.,61,4.5等價(jià)關(guān)系與偏序關(guān)系,

20、等價(jià)關(guān)系的定義與實(shí)例等價(jià)類(lèi)及其性質(zhì)商集與集合的劃分等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)偏序關(guān)系與偏序集哈斯圖偏序集中的特定元素,62,等價(jià)關(guān)系的定義與實(shí)例,定義設(shè)R為非空集合上的關(guān)系.如果R是自反的、對(duì)稱(chēng)的和傳遞的,則稱(chēng)R為A上的等價(jià)關(guān)系.設(shè)R是一個(gè)等價(jià)關(guān)系,若等價(jià)關(guān)系R,稱(chēng)x等價(jià)于y,記做xy.,例設(shè)A=1,2,8,如下定義A上的關(guān)系R：R=|x,yAxy(mod3)其中xy(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等(或者3整除x-y).,63,等價(jià)關(guān)系的驗(yàn)證,驗(yàn)證模3相等關(guān)系R為A上的等價(jià)關(guān)系,因?yàn)閤A,有xx(mod3)x,yA,若xy(mod3),則有yx(mod3)x,

21、y,zA,若xy(mod3),yz(mod3),則有xz(mod3)自反性、對(duì)稱(chēng)性、傳遞性得到驗(yàn)證,64,A上模3等價(jià)關(guān)系的關(guān)系圖,設(shè)A=1,2,8,R=|x,yAxy(mod3),65,等價(jià)類(lèi),定義設(shè)R為非空集合A上的等價(jià)關(guān)系,xA，令xR=y|yAxRy稱(chēng)xR為x關(guān)于R的等價(jià)類(lèi),簡(jiǎn)稱(chēng)為x的等價(jià)類(lèi),簡(jiǎn)記為x.,例A=1,2,8上模3等價(jià)關(guān)系的等價(jià)類(lèi)：1=4=7=1,4,72=5=8=2,5,83=6=3,6,66,等價(jià)類(lèi)的性質(zhì),定理設(shè)R是非空集合A上的等價(jià)關(guān)系,對(duì)任意的x,yA,則(1)x是A的非空子集.(2)如果xRy,則x=y.(3)如果xy,則x與y不交.(4)所有等價(jià)類(lèi)的并集就是A.

22、,67,例,A=1,2,8上模3等價(jià)關(guān)系的等價(jià)類(lèi)：1=4=7=1,4,7，2=5=8=2,5,8，3=6=3,6以上3類(lèi)兩兩不交，1,4,72,5,83,6=1,2,8,68,商集,定義設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類(lèi)作為元素的集合稱(chēng)為A關(guān)于R的商集,記做A/R,即A/R=xR|xA,例A=1,2,8,A關(guān)于模3等價(jià)關(guān)系R的商集為A/R=1,4,7,2,5,8,3,6A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：A/IA=1,2,8A/EA=1,2,8,69,集合的劃分,定義設(shè)A為非空集合,若A的子集族(P(A)滿足下面條件：(1)(2)中任意兩個(gè)元素不交(3)中所有元素的并集為A則稱(chēng)是A的

23、一個(gè)劃分,稱(chēng)中的元素為A的劃分塊.,70,例題,例設(shè)Aa,b,c,d,給定1,2,3,4,5,6如下：1=a,b,c,d，2=a,b,c,d3=a,a,b,c,d,4=a,b,c5=,a,b,c,d,6=a,a,b,c,d則1和2是A的劃分,其他都不是A的劃分.,71,等價(jià)關(guān)系與劃分的一一對(duì)應(yīng),商集A/R就是A的一個(gè)劃分不同的商集對(duì)應(yīng)于不同的劃分任給A的一個(gè)劃分,如下定義A上的關(guān)系R：R=|x,yAx與y在的同一劃分塊中則R為A上的等價(jià)關(guān)系,且該等價(jià)關(guān)系確定的商集就是.,例給出A1,2,3上所有的等價(jià)關(guān)系先做出A的所有劃分,然后根據(jù)劃分寫(xiě)出對(duì)應(yīng)的等價(jià)關(guān)系.,72,等價(jià)關(guān)系與劃分之間的對(duì)應(yīng),2,

24、3和3分別對(duì)應(yīng)等價(jià)關(guān)系R2,R3和R4.R2=,IA，R3=,IAR4=,IA,1對(duì)應(yīng)于全域關(guān)系EA，5對(duì)應(yīng)于恒等關(guān)系IA,73,偏序關(guān)系與偏序集,定義非空集合A上的自反、反對(duì)稱(chēng)和傳遞的關(guān)系，稱(chēng)為A上的偏序關(guān)系，記作.設(shè)為偏序關(guān)系,如果,則記作xy,讀作“x小于等于y”.集合A與A上的偏序關(guān)系R一起稱(chēng)作偏序集，記作,74,偏序關(guān)系與偏序集(續(xù)),例集合A上的恒等關(guān)系IA是A上的偏序關(guān)系.小于或等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.例整數(shù)集和小于等于關(guān)系構(gòu)成偏序集，冪集P(A)和包含關(guān)系構(gòu)成偏序集.,75,相關(guān)概念,設(shè)偏序集,若任意x,yA，如果xy或者yx成立，則稱(chēng)x與y是可比

25、的.如果xy(xyxy)且不存在zA使得xzy,則稱(chēng)y覆蓋x.例1,2,3,4,5集合上的整除關(guān)系,則有1和1,2,3,4,5都是可比的,2和4是可比的.2和3、2和5、3和5都是不可比的.2,3,5都覆蓋1.4不覆蓋1.,76,全序關(guān)系：設(shè)偏序集,若對(duì)任意x,yA,x與y都可比，則稱(chēng)為A上的全序關(guān)系，且稱(chēng)為全序集(或線序集).例數(shù)集上的小于或等于關(guān)系是全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系,相關(guān)概念（續(xù)）,77,哈斯圖,哈斯圖：利用偏序自反、反對(duì)稱(chēng)、傳遞性簡(jiǎn)化的關(guān)系圖特點(diǎn)：每個(gè)結(jié)點(diǎn)沒(méi)有環(huán)，兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過(guò)結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前，具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間

26、連邊,78,哈斯圖實(shí)例,例,79,A=a,b,c,d,e,f,g,hR=,IA,哈斯圖實(shí)例（續(xù)）,例已知偏序集的哈斯圖如右圖所示,試求出集合A和關(guān)系R的表達(dá)式.,80,偏序集的特定元素,定義設(shè)為偏序集,BA,yB.(1)若x(xByx)成立,則稱(chēng)y為B的最小元.(2)若x(xBxy)成立,則稱(chēng)y為B的最大元.(3)若x(xBxy)成立,則稱(chēng)y為B的極小元.(4)若x(xByx)成立,則稱(chēng)y為B的極大元.,81,特殊元素的性質(zhì),對(duì)于有窮集，極小元和極大元必存在，可能存在多個(gè).最小元和最大元不一定存在，如果存在一定惟一.最小元一定是極小元；最大元一定是極大元.孤立結(jié)點(diǎn)既是極小元，也是極大元.,82

27、,定義設(shè)為偏序集,BA,yA.(1)若x(xBxy)成立,則稱(chēng)y為B的上界.(2)若x(xByx)成立,則稱(chēng)y為B的下界.(3)令Cy|y為B的上界,則稱(chēng)C的最小元為B的最小上界或上確界.(4)令Dy|y為B的下界,則稱(chēng)D的最大元為B的最大下界或下確界.,偏序集的特定元素(續(xù)),83,下界、上界、下確界、上確界不一定存在下界、上界存在不一定惟一下確界、上確界如果存在，則惟一集合的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì).,特殊元素的性質(zhì),84,實(shí)例,例設(shè)偏序集如下圖所示，求A的極小元、最小元、極大元、最大元.設(shè)Bb,c,d,求B的下界、上界、下確界、上確界.,極小元：a,b,c,g

28、；極大元：a,f,h；沒(méi)有最小元與最大元.B的下界和下確界都不存在,上界有d和f,上確界為d.,85,4.6函數(shù)的定義與性質(zhì),函數(shù)的定義函數(shù)定義從A到B的函數(shù)函數(shù)的像函數(shù)的性質(zhì)函數(shù)的單射、滿射、雙射性構(gòu)造雙射函數(shù)應(yīng)用實(shí)例：?jiǎn)栴}描述,86,函數(shù)定義,定義設(shè)F為二元關(guān)系,若xdomF都存在唯一的yranF使xFy成立,則稱(chēng)F為函數(shù).對(duì)于函數(shù)F,如果有xFy,則記作y=F(x),并稱(chēng)y為F在x的值.,例F1=,F2=,F1是函數(shù),F2不是函數(shù),87,函數(shù)相等,定義設(shè)F,G為函數(shù),則F=GFGGF如果兩個(gè)函數(shù)F和G相等,一定滿足下面兩個(gè)條件：(1)domF=domG(2)xdomF=domG都有F(x

29、)=G(x)實(shí)例函數(shù)F(x)=(x21)/(x+1),G(x)=x1不相等,因?yàn)閐omFdomG.,88,從A到B的函數(shù),定義設(shè)A,B為集合,如果函數(shù)f滿足：(1)domf=A(2)ranfB,則稱(chēng)f為從A到B的函數(shù),記作f：AB.例f：NN,f(x)=2x是從N到N的函數(shù)g：NN,g(x)=2也是從N到N的函數(shù),89,B上A,定義所有從A到B的函數(shù)的集合記作BA,讀作“B上A”，符號(hào)化表示為BA=f|f：AB計(jì)數(shù)：|A|=m,|B|=n,且m,n不全為0,|BA|=nm.,90,例設(shè)A=1,2,3,B=a,b,求BA.解BA=f0,f1,f7,其中f0=,f1=,f2=,，f3=,f4=,，

30、f5=,f6=,f7=,91,函數(shù)的像,定義設(shè)函數(shù)f：AB,A1A.A1在f下的像：f(A1)=f(x)|xA1函數(shù)的像f(A)注意：函數(shù)值f(x)B,而像f(A1)B.,例設(shè)f：NN,且令A(yù)=0,1,B=2,那么有f(A)=f(0,1)=f(0),f(1)=0,2,92,函數(shù)的性質(zhì),定義設(shè)f：AB,（1）若ranf=B,則稱(chēng)f：AB是滿射的.（2）若yranf都存在唯一的xA使得f(x)=y,則稱(chēng)f：AB是單射的.（3）若f：AB既是滿射又是單射的,則稱(chēng)f：AB是雙射的f滿射意味著：yB,都存在xA使得f(x)=y.f單射意味著：f(x1)=f(x2)x1=x2,93,判斷下面函數(shù)是否為單射

31、,滿射,雙射的,為什么?(1)f：RR,f(x)=x2+2x1(2)f：Z+R,f(x)=lnx,Z+為正整數(shù)集(3)f：RZ,f(x)=x(4)f：RR,f(x)=2x+1(5)f：R+R+,f(x)=(x2+1)/x,其中R+為正實(shí)數(shù)集.,94,解(1)f：RR,f(x)=x2+2x1在x=1取得極大值0.既不單射也不滿射.(2)f：Z+R,f(x)=lnx單調(diào)上升,是單射.但不滿射,ranf=ln1,ln2,.(3)f：RZ,f(x)=x滿射,但不單射,例如f(1.5)=f(1.2)=1.(4)f：RR,f(x)=2x+1滿射、單射、雙射,因?yàn)樗菃握{(diào)的并且ranf=R.(5)f：R+R

32、+,f(x)=(x2+1)/x有極小值f(1)=2.該函數(shù)既不單射也不滿射.,95,常函數(shù)、恒等函數(shù)、單調(diào)函數(shù),1.設(shè)f：AB,若存在cB使得xA都有f(x)=c,則稱(chēng)f：AB是常函數(shù).2.稱(chēng)A上的恒等關(guān)系IA為A上的恒等函數(shù),對(duì)所有的xA都有IA(x)=x.3.設(shè)f：RR，如果對(duì)任意的x1,x2R，x1x2,就有f(x1)f(x2),則稱(chēng)f為單調(diào)遞增的；如果對(duì)任意的x1,x2A,x1x2,就有f(x1)f(x2),則稱(chēng)f為嚴(yán)格單調(diào)遞增的.類(lèi)似可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù).,96,集合的特征函數(shù),設(shè)A為集合,AA,A的特征函數(shù)A：A0,1定義為,實(shí)例集合：X=A,B,C,D,E,F,G,H,子集：T=A,C,F,G,HT的特征函數(shù)T：xABCDEFGHT(x)10100111,97,設(shè)R是A上的等價(jià)關(guān)系,令g：AA/Rg(a)=a,aA稱(chēng)g是從A到商集A/R的自然映射