七章二元關(guān)系ppt課件

1、1第七章第七章: 二元關(guān)系二元關(guān)系q主要內(nèi)容主要內(nèi)容q有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q二元關(guān)系的定義與表示法二元關(guān)系的定義與表示法q關(guān)系的運(yùn)算關(guān)系的運(yùn)算q關(guān)系的性質(zhì)關(guān)系的性質(zhì)q關(guān)系的閉包關(guān)系的閉包q等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q偏序關(guān)系偏序關(guān)系q本章與后面各章的關(guān)系本章與后面各章的關(guān)系q是函數(shù)的根底是函數(shù)的根底q是圖論的根底是圖論的根底2第七章第七章: 二元關(guān)系二元關(guān)系 第一節(jié)：有序?qū)εc笛卡兒積第一節(jié)：有序?qū)εc笛卡兒積3引言引言q關(guān)系是數(shù)學(xué)中最重要的概念之一關(guān)系是數(shù)學(xué)中最重要的概念之一q父子關(guān)系、師生關(guān)系父子關(guān)系、師生關(guān)系q等于、大于、小于關(guān)系等于、大于、小于關(guān)系q直線的平行、垂直關(guān)系直線的

2、平行、垂直關(guān)系q在計(jì)算機(jī)科學(xué)中有廣泛運(yùn)用在計(jì)算機(jī)科學(xué)中有廣泛運(yùn)用q人工智能人工智能q程序設(shè)計(jì)程序設(shè)計(jì)q數(shù)據(jù)庫管理數(shù)據(jù)庫管理關(guān)系數(shù)據(jù)庫關(guān)系數(shù)據(jù)庫47.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q有序?qū)π蚺迹河蓛蓚€(gè)元素有序?qū)π蚺迹河蓛蓚€(gè)元素x x，y(y(允許允許x=y)x=y)按給定順序陳列組成的二元組合按給定順序陳列組成的二元組合q符號化：符號化：xyqx x為第一元素，為第一元素，y y為第二元素為第二元素q例：平面直角坐標(biāo)系中的一個(gè)點(diǎn)的坐標(biāo)例：平面直角坐標(biāo)系中的一個(gè)點(diǎn)的坐標(biāo)q1,31,3和和3,13,1是表示平面上兩個(gè)不同的點(diǎn)是表示平面上兩個(gè)不同的點(diǎn)qx = = v當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x=u x=u

3、 ，y=vy=vq假設(shè)假設(shè)x xy y，那么，那么x x，y yy y ，x x57.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q例：知例：知=，求，求x,yx,yq解：根據(jù)有序?qū)Φ仁蕉x，只需求解方程式解：根據(jù)有序?qū)Φ仁蕉x，只需求解方程式q x+2=5 x+2=5 和和 2x+y=4 2x+y=4q 得到：得到： x=3, y=-2 x=3, y=-267.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積77.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q例：設(shè)集合例：設(shè)集合A=1A=1，22，求，求P(A)P(A)A Aq解：解：qP(A)=P(A)=，11，22，11，22qP(A)P(A)A A q=1， 2

4、，11，12，21，22， 1 1，1287.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積97.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q笛卡兒積的性質(zhì)：笛卡兒積的性質(zhì)：q對于恣意集合對于恣意集合A，A=，A=q普通不滿足交換律，當(dāng)普通不滿足交換律，當(dāng)A，B，AB時(shí)時(shí)，q AB BAq普通不滿足結(jié)合律，即當(dāng)普通不滿足結(jié)合律，即當(dāng)A，B，C均非空時(shí)，均非空時(shí)，(AB)CA(BC)107.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q笛卡兒積的性質(zhì)續(xù)：笛卡兒積的性質(zhì)續(xù)：q對恣意三個(gè)集合對恣意三個(gè)集合A，B，C有有q 1A(BC)=(AB) (AC)q 2A(BC)=(AB)(AC)q 3(BC)A=(BA) (CA)

5、q 4(BC)A=(BA)(CA)q 5A C B D ABCD117.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q證明：證明：q對恣意三個(gè)集合對恣意三個(gè)集合A，B，C有有q A(BC)=(AB) (AC)q證明：證明： A(BC) q xA yBCq xA (yB yC)q (xA yB) (xA yC)q AB ACq (AB) (AC)127.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q例：設(shè)例：設(shè)A，B，C，D是恣意集合，判別以下命是恣意集合，判別以下命題能否正確？題能否正確？qABAC BCq不正確。取不正確。取A，BC，AB=AC=qA-(BC)=(A-B) (A-C)q不正確。取不正確。取A

6、=B=1，C=2，q A-(BC)=1-=1q 而而(A-B) (A-C)=1=137.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積q例：設(shè)例：設(shè)A，B，C，D是恣意集合，判別以下命是恣意集合，判別以下命題能否正確？題能否正確？qA=B，C=D ACBD q正確。正確。q存在集合存在集合A使得使得A AAq正確。取正確。取A=時(shí)，時(shí)，AAA14第七章第七章: 二元關(guān)系二元關(guān)系 第二節(jié)：二元關(guān)系第二節(jié)：二元關(guān)系 157.2 二元關(guān)系二元關(guān)系q關(guān)系是指事物之間個(gè)體之間的相互聯(lián)絡(luò)關(guān)系是指事物之間個(gè)體之間的相互聯(lián)絡(luò)q二元關(guān)系二元關(guān)系R R：滿足以下條件之一的集合：滿足以下條件之一的集合q集合非空，且它的元素都

7、是有序?qū)戏强?，且它的元素都是有序?qū)集合為空集集合為空集q定義：定義：A A，B B是集合，是集合，A AB B的子集叫做從的子集叫做從A A到到B B的的一個(gè)二元關(guān)系一個(gè)二元關(guān)系q例：例：A=0A=0，11，B=1B=1，2 2，33qR1=R1=，R2=R2=qR3=R3=167.2 二元關(guān)系二元關(guān)系q幾類特殊關(guān)系：幾類特殊關(guān)系：q全域關(guān)系全域關(guān)系EAEAA AA Aq恒等關(guān)系恒等關(guān)系IAIAx|xA x|xA q空關(guān)系空關(guān)系177.2 二元關(guān)系二元關(guān)系q例：例： A=0,1,2 A=0,1,2qEA=,EA=,q , ,q恒等關(guān)系恒等關(guān)系IA =,IA =,187.2 二元關(guān)系二元關(guān)

8、系q包含關(guān)系包含關(guān)系qA是一個(gè)集合是一個(gè)集合,定義定義P(A)上的一個(gè)關(guān)系上的一個(gè)關(guān)系qR =uP(A)，vP(A)，且，且uvqA=a，b，P(A)= ，a，b，AqR=，q例：例： A=2，3，4，5，6qR=a是是b的倍數(shù)的倍數(shù)qR= ，197.2 二元關(guān)系二元關(guān)系q 關(guān)系表示方法關(guān)系表示方法q 枚舉法直觀法、列舉法枚舉法直觀法、列舉法q xRyxRy表示特定的序偶表示特定的序偶x x，y y R Rq 謂詞公式表示法暗含法謂詞公式表示法暗含法q 關(guān)系矩陣表示法關(guān)系矩陣表示法q 關(guān)系圖表示法關(guān)系圖表示法207.2 二元關(guān)系二元關(guān)系q 關(guān)系表示方法關(guān)系表示方法q 枚舉法直觀法、列舉法枚舉法

9、直觀法、列舉法q xRyxRy表示特定的序偶表示特定的序偶x x，y y R Rq 謂詞公式表示法暗含法謂詞公式表示法暗含法q 關(guān)系矩陣表示法關(guān)系矩陣表示法q 關(guān)系圖表示法關(guān)系圖表示法217.2 二元關(guān)系二元關(guān)系q 關(guān)系矩陣表示法關(guān)系矩陣表示法q 設(shè)集合設(shè)集合A=a1,am,B=b1,bn,RA=a1,am,B=b1,bn,R是是A A到到B B的關(guān)系的關(guān)系, ,那么那么R R的關(guān)系矩陣是一個(gè)的關(guān)系矩陣是一個(gè)m mn n階的矩階的矩陣陣q MR=(rij)m MR=(rij)mn nq 其中其中rij =1,rij =1,當(dāng)當(dāng)R Rq ri j =0, ri j =0,當(dāng)當(dāng)R Rq 假設(shè)假設(shè)R

10、 R是是A A上的關(guān)系時(shí)上的關(guān)系時(shí), ,那么其關(guān)系矩陣是一個(gè)那么其關(guān)系矩陣是一個(gè)方陣方陣227.2 二元關(guān)系二元關(guān)系例：例：A=a,b,c,d,B=x,y,z,A=4，B=3,R=,那么那么MR是是43的矩陣的矩陣 1 0 1 1 0 1MR = 0 1 0MR = 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0其中其中r13=1表示表示R,而而r23=0,表示表示R237.2 二元關(guān)系二元關(guān)系q 關(guān)系表示方法關(guān)系表示方法q 枚舉法直觀法、列舉法枚舉法直觀法、列舉法q xRyxRy表示特定的序偶表示特定的序偶x x，y y R Rq 謂詞公式表示法暗含法謂詞公式表示法暗含法q 關(guān)系

11、矩陣表示法關(guān)系矩陣表示法q 關(guān)系圖表示法關(guān)系圖表示法247.2 二元關(guān)系二元關(guān)系q 關(guān)系圖：關(guān)系圖：A=a1,am，B=b1,bnq 結(jié)點(diǎn)：結(jié)點(diǎn)：m+n個(gè)空心點(diǎn)分別表示個(gè)空心點(diǎn)分別表示a1,am和和b1,bnq 有向邊：假設(shè)有向邊：假設(shè)R,那么由結(jié)點(diǎn)那么由結(jié)點(diǎn)ai向結(jié)向結(jié)點(diǎn)點(diǎn)bj通一條有向弧通一條有向弧,箭頭指向箭頭指向bjq 自回路：自回路：R,那么畫一條以那么畫一條以ai到本身的到本身的一條有向弧一條有向弧q 這樣構(gòu)成的圖稱為關(guān)系這樣構(gòu)成的圖稱為關(guān)系R的關(guān)系圖的關(guān)系圖257.2 二元關(guān)系二元關(guān)系q 例：例：A=2,3,4,5,6q (1)R1=a是是b的倍數(shù)的倍數(shù)q (2)R2=(a-b)

12、2A 536425364226第七章第七章: 二元關(guān)系二元關(guān)系 第三節(jié)：關(guān)系的運(yùn)算第三節(jié)：關(guān)系的運(yùn)算277.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q二元關(guān)系的定義域和值域二元關(guān)系的定義域和值域q定義域：定義域：q值域：值域：q例例qX=1,2,3,4,5,6,Y=a,b,c,d,e,fX=1,2,3,4,5,6,Y=a,b,c,d,e,fqR=,R=,qdomR=1,2,3,4domR=1,2,3,4qranR=a,b,c,dranR=a,b,c,d),(|RyxyxdomR),(|RyxxyranR287.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q二元關(guān)系的逆關(guān)系二元關(guān)系的逆關(guān)系qR-1R-1就是將就是將R R中的一切有

13、序?qū)Φ膬蓚€(gè)元素交換次中的一切有序?qū)Φ膬蓚€(gè)元素交換次序成為序成為R-1 R-1 ，故，故|R|=| R-1 | |R|=| R-1 | q闡明闡明qR-1 R-1 的關(guān)系矩陣是的關(guān)系矩陣是R R的關(guān)系矩陣的轉(zhuǎn)置，即的關(guān)系矩陣的轉(zhuǎn)置，即 MR-1=(MR)TMR-1=(MR)TqR-1R-1的關(guān)系圖就是將的關(guān)系圖就是將R R的關(guān)系圖中的弧改動方向的關(guān)系圖中的弧改動方向即可以即可以,|,1RxyyxR297.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q例：例：qR=，qR-1=， q 1 0 0 1 1 0 1 0q 0 0 0 1 0 0 1 0 q MR= 1 1 0 0 MR-1=MRT= 0 0 0 1 q

14、0 0 1 0 1 1 0 0 307.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q例：例：qR=，qR-1=， dbcabcadR的關(guān)系圖R-1的關(guān)系圖317.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 關(guān)系的右復(fù)合關(guān)系的右復(fù)合q 例例q A=1,2,3,4,5,B=3,4,5,C=1,2,3q R=|x+y=6q =,q S=y-z=2 q =,q RS=,),(|,GytFtxtyxGFo327.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 例續(xù)例續(xù)5435432132154321321從而從而RS的關(guān)系圖的關(guān)系圖337.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 例：例： A=a,b,c,d,eq R=,q S=,q RS=,q SR=,q RR=,q

15、 SS=q 留意：留意：RSSR 347.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定義：定義：R是二元關(guān)系，是二元關(guān)系，A是集合是集合q R在在A上的限制上的限制q q A在在R下的像下的像,|RAx yxRyxA )(ARranARARA357.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q例：R = , , , , , 求：q R 1R 2,3R R 1R2,3R367.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q優(yōu)先順序：優(yōu)先順序：q逆運(yùn)算優(yōu)先于其他運(yùn)算逆運(yùn)算優(yōu)先于其他運(yùn)算q關(guān)系運(yùn)算優(yōu)先于集合運(yùn)算關(guān)系運(yùn)算優(yōu)先于集合運(yùn)算q沒有規(guī)定優(yōu)先權(quán)的運(yùn)算以括號決議運(yùn)算順序沒有規(guī)定優(yōu)先權(quán)的運(yùn)算以括號決議運(yùn)算順序377.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理：

16、設(shè)定理：設(shè)F是恣意的關(guān)系，那么是恣意的關(guān)系，那么q (F-1)-1=Fq domF-1 =ranF, ranF-1 =domF387.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理：設(shè)定理：設(shè)F，G，H是恣意的關(guān)系是恣意的關(guān)系q (FG)H = F(GH)q (FG)-1 =G-1F-1q 證明：證明： (FG)-1 q FGq t(F G)q t(G-1 F-1)q G-1F-1397.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 例例q R=,q S=,q RS=, ,q (RS)-1=, ,q R-1=, ,q S-1=, q S-1R-1=, ,407.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理定理: 設(shè)設(shè)R為為A上關(guān)系，那么

17、上關(guān)系，那么q RIAIARRq 定理定理:q R(ST)=RSRTq R(ST)RSRTq (ST)X=SXTXq (ST)XSXTX417.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 證明證明 R(ST)=RSRTq R(ST)q y(RST)q y(R(ST)q y(RS) (RT)q y(RS) y(RT)q RS RTq RSRT427.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q證明證明 R(ST)RSRTq R(ST) t (RST)q t (RST) t (RS)q (RT) t (RS)q t (RT)q RSRT RSRT437.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理定理:q R (AB) = R AR Bq R

18、AB = RARBq R (AB) = R AR Bq RAB RARB447.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理定理: RAB RARBq 證明：證明：yRAB q x(RxAB)q x(RxAxB)q x(RxA)(R xB)q x(RxA) x(R xB)q yRAyRB q yRARB457.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q R的的n次冪次冪q記為記為Rnq R0 =Aq Rn+1=RnRq定理定理: 設(shè)設(shè)R是集合是集合A上的關(guān)系，上的關(guān)系，m,nNq RmRn=Rm+nq (Rm)n=Rmnq證明思緒：運(yùn)用歸納法并利用復(fù)合關(guān)系的結(jié)證明思緒：運(yùn)用歸納法并利用復(fù)合關(guān)系的結(jié)合律合律467.3 關(guān)系

19、的運(yùn)算關(guān)系的運(yùn)算q 例例R=,q R0= ,q R1=Rq R2=,q R3=R2Rq =,q R4=R3Rq =,q R5=R4Rq =,477.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算從關(guān)系圖來看關(guān)系的從關(guān)系圖來看關(guān)系的n次冪次冪 R： 1 2 3 4 5R2就是一切在就是一切在R中經(jīng)過二條弧銜接的點(diǎn)，那么中經(jīng)過二條弧銜接的點(diǎn)，那么在在R2這兩點(diǎn)間直接有條弧。這兩點(diǎn)間直接有條弧。 1 2 3 4 5R3,R4487.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理：定理：R是是A上的二元關(guān)系，假設(shè)存在自然數(shù)上的二元關(guān)系，假設(shè)存在自然數(shù)s和和t，且，且st，使，使Rs=Rt，那么，那么q 對一切的對一切的k0，那么，那么R

20、s+k=Rt+kq 對一切的對一切的k,i0 ，那么有，那么有Rs+kp+i=Rs+iq p=t-sq 設(shè)設(shè)S=R0,R1,R2,Rt-1，那么，那么R的每的每一次冪都是一次冪都是S的元素，即對恣意的元素，即對恣意qN, RqS 497.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理：定理：R是是A上的二元關(guān)系，假設(shè)存在自然數(shù)上的二元關(guān)系，假設(shè)存在自然數(shù)s和和t，且，且st，使，使Rs=Rtq 對一切的對一切的k0，那么，那么Rs+k=Rt+kq 對一切的對一切的k,i0 ，那么有，那么有Rs+kp+i=Rs+iq p=t-sq 設(shè)設(shè)S=R0,R1,R2,Rt-1，那么，那么R的每的每一次冪是一次冪是S的元

21、素，即對恣意的元素，即對恣意qN, RqS 507.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算證明：對證明：對k進(jìn)展歸納。進(jìn)展歸納。k=0時(shí)時(shí)Rs+kp+i=Rs+i顯然成立顯然成立假設(shè)假設(shè)Rs+kp+i=Rs+i，這里，這里p=t-s ，那么，那么Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp=Rs+iRp =Rs+p+i =Rs+t-s+i =Rt+i=Rs+i517.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算q 定理：定理：R是是A上的二元關(guān)系，假設(shè)存在自然數(shù)上的二元關(guān)系，假設(shè)存在自然數(shù)s和和t，且，且st，使，使Rs=Rtq 對一切的對一切的k0，那么，那么Rs+k=Rt+kq 對一切的對一切的k,i0

22、，那么有，那么有Rs+kp+i=Rs+iq p=t-sq 設(shè)設(shè)S=R0,R1,R2,Rt-1，那么，那么R的每的每一次冪是一次冪是S的元素，即對恣意的元素，即對恣意qN, RqS 527.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算證明：假設(shè)證明：假設(shè)qt，那么，那么RqS 。假設(shè)假設(shè)qt，那么存在自然數(shù)，那么存在自然數(shù)k，i使得使得 q=s+kp+i其中其中0 ip-1，所以，所以 Rq= Rs+kp+i = Rs+i由于由于0 ip-1 s+i s+p-1 = s+t-s-1=t-153第七章第七章: 二元關(guān)系二元關(guān)系 第四節(jié)：關(guān)系的性質(zhì)第四節(jié)：關(guān)系的性質(zhì)547.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q自反性自反性qaA，

23、有，有R，那么，那么R為為A上的自反關(guān)系上的自反關(guān)系q反自反性反自反性qaA，有，有 R，R為為A上的反自反關(guān)系上的反自反關(guān)系q例例 A=a,b,cqR1=,qR2=,qR3=,557.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q例：例：R是是I+上的整除關(guān)系，那么上的整除關(guān)系，那么R具有自反性具有自反性q證明：證明：xI+，x能整除能整除x，qR，R具有自反性具有自反性q例：例：R是是I上的同余關(guān)系，那么上的同余關(guān)系，那么R具有自反性具有自反性q證明：證明：xI，(x-x)/k=0I, qx與與x同余同余RR具有自反性具有自反性q其它其它，關(guān)系，均是自反關(guān)系關(guān)系，均是自反關(guān)系567.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q

24、例：例：N上的互質(zhì)關(guān)系是反自反關(guān)系上的互質(zhì)關(guān)系是反自反關(guān)系q證明：證明：xN，x與與x是不互質(zhì)的，是不互質(zhì)的，q R，R具有反自反關(guān)系具有反自反關(guān)系q實(shí)數(shù)上的實(shí)數(shù)上的,關(guān)系關(guān)系,均是反自反關(guān)系均是反自反關(guān)系577.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q關(guān)系矩陣的特點(diǎn)？關(guān)系矩陣的特點(diǎn)？q自反關(guān)系的關(guān)系矩陣的對角元素均為自反關(guān)系的關(guān)系矩陣的對角元素均為1q反自反關(guān)系的關(guān)系矩陣的對角元素均為反自反關(guān)系的關(guān)系矩陣的對角元素均為0q關(guān)系圖的特點(diǎn)？關(guān)系圖的特點(diǎn)？q自反關(guān)系的關(guān)系圖中每個(gè)頂點(diǎn)都有環(huán)自反關(guān)系的關(guān)系圖中每個(gè)頂點(diǎn)都有環(huán)q反自反關(guān)系的關(guān)系圖中每個(gè)頂點(diǎn)都沒有環(huán)反自反關(guān)系的關(guān)系圖中每個(gè)頂點(diǎn)都沒有環(huán)q定理：定理：R是

25、是A上的關(guān)系，那么：上的關(guān)系，那么：qR是自反關(guān)系的充要條件是是自反關(guān)系的充要條件是IARqR是反自反關(guān)系的充要條件是是反自反關(guān)系的充要條件是RIA=587.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q對稱關(guān)系對稱關(guān)系Rqa,bA,假設(shè)假設(shè)R,那么必有那么必有R q例例qR1,qR1是對稱的是對稱的qR2,qR2是對稱的是對稱的qR3,qR3不是對稱的不是對稱的 597.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q關(guān)系矩陣特點(diǎn)？關(guān)系矩陣特點(diǎn)？q對稱關(guān)系的關(guān)系矩陣是對稱矩陣對稱關(guān)系的關(guān)系矩陣是對稱矩陣q關(guān)系圖特點(diǎn)？關(guān)系圖特點(diǎn)？q假設(shè)兩個(gè)頂點(diǎn)之間有邊，一定是一對方向相反假設(shè)兩個(gè)頂點(diǎn)之間有邊，一定是一對方向相反的邊無單邊的邊無單邊q定

26、理：定理： R在在A上對稱當(dāng)且僅當(dāng)上對稱當(dāng)且僅當(dāng)R=R-1q證明：必要性證明：必要性qRRR-1q充分性充分性qRR-1R607.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q反對稱關(guān)系反對稱關(guān)系Rqa,bA,假設(shè)假設(shè)R且且R,那那么必有么必有abqa,bA,假設(shè)假設(shè)ab,R,那么必有那么必有Rq例例: Aa,b,cqR,qS,qT,qR,S是反對稱的是反對稱的,T不是反對稱的不是反對稱的617.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q例例: 實(shí)數(shù)集合上實(shí)數(shù)集合上關(guān)系是反對稱關(guān)系關(guān)系是反對稱關(guān)系qx,y實(shí)數(shù)集實(shí)數(shù)集,如如xy,且且xy,那么那么yx不不成立成立q例：例：,關(guān)系關(guān)系,均是反對稱關(guān)系均是反對稱關(guān)系q反對稱關(guān)系矩陣和

27、關(guān)系圖特點(diǎn)？反對稱關(guān)系矩陣和關(guān)系圖特點(diǎn)？q假設(shè)假設(shè)rij=1，且，且ij， 那么那么rji=0q假設(shè)兩個(gè)頂點(diǎn)之間有邊，一定是一條有向邊假設(shè)兩個(gè)頂點(diǎn)之間有邊，一定是一條有向邊無雙向邊無雙向邊q定理：定理： R在在A上反對稱當(dāng)且僅當(dāng)上反對稱當(dāng)且僅當(dāng)RR-1 IA627.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q傳送關(guān)系傳送關(guān)系qa,b,cA,假設(shè)假設(shè)R,R, 必有必有Rq例例qR1,q是傳送關(guān)系是傳送關(guān)系qR2,q是傳送關(guān)系是傳送關(guān)系qR3,q不是傳送關(guān)系不是傳送關(guān)系637.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q例例:整除關(guān)系整除關(guān)系DI是是I上的傳送關(guān)系上的傳送關(guān)系qx,y,zI,如如DI,DI,即即x能整除能整除y,且且

28、y能整除能整除z,那那么必有么必有x能整除能整除z, DIq例例:P(A)上的包含關(guān)系上的包含關(guān)系具有傳送性具有傳送性q假設(shè)假設(shè)uv,vw,那么必有那么必有uwq例例:實(shí)數(shù)集上的實(shí)數(shù)集上的關(guān)系具有傳送性關(guān)系具有傳送性q假設(shè)假設(shè)xy,yz必有必有xz647.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q傳送關(guān)系關(guān)系圖特點(diǎn)？傳送關(guān)系關(guān)系圖特點(diǎn)？q假設(shè)結(jié)點(diǎn)假設(shè)結(jié)點(diǎn)a能經(jīng)過有向弧組成的有向途徑通向能經(jīng)過有向弧組成的有向途徑通向結(jié)點(diǎn)結(jié)點(diǎn)x,那么那么a必需有有向弧直接指向必需有有向弧直接指向x,否那么否那么R就不是傳送的就不是傳送的q例：例：R=,q定理：定理：R在在A上傳送當(dāng)且僅當(dāng)上傳送當(dāng)且僅當(dāng)RR Rdcba657.4

29、關(guān)系的性質(zhì)關(guān)系的性質(zhì)自自 反：反：反自反：反自反： 對對 稱：稱：反對稱：反對稱：傳傳 遞：遞： )(xRxXxx xRx)Xx(x )(yRxxRyXyXxyx )(yxyRxxRyXyXxyx )(xRzyRzxRyXzXyXxzyx 667.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q 設(shè)設(shè)A是集合，是集合，R1和和R2是是A上的關(guān)系上的關(guān)系q 假設(shè)假設(shè)R1，R2是自反和對稱的，那么是自反和對稱的，那么R1R2也是自反的和對稱的也是自反的和對稱的q 假設(shè)假設(shè)R1和和R2是傳送的，那么是傳送的，那么R1R2也是傳也是傳送的送的677.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q 設(shè)設(shè)A是集合，是集合，R1和和R2是是A上的關(guān)

30、系上的關(guān)系q 假設(shè)假設(shè)R1，R2是自反的和對稱的，那么是自反的和對稱的，那么R1R2也是自反也是自反q 的和對稱的的和對稱的q 證明：證明：R1，R2是自反的是自反的 IA R1，IA R2q 所以所以IA R1R2q R1，R2是對稱的是對稱的 R1=R1-1和和R2=R2-1q 所以所以(R1R2)-1=R1-1R2-1= R1R2687.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)q例：例： X=1,2,3，判別關(guān)系的性質(zhì)，判別關(guān)系的性質(zhì)qR1=,n R2=, n反對稱反對稱n反自反反自反n反對稱反對稱n可傳送可傳送697.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)qR3=,qR4= Ex q自反，對稱，可傳送的自反，對稱，

31、可傳送的 n自反，對稱，反對稱，可傳送的自反，對稱，反對稱，可傳送的707.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)qX=1,2,3, R5= q反自反的，對稱的，反對稱的，可傳送的反自反的，對稱的，反對稱的，可傳送的q假設(shè)假設(shè)X= ，X上的空關(guān)系上的空關(guān)系q自反的，反自反的，對稱的，反對稱的，可傳自反的，反自反的，對稱的，反對稱的，可傳送的送的71第七章第七章: 二元關(guān)系二元關(guān)系 第五節(jié)：關(guān)系的閉包第五節(jié)：關(guān)系的閉包727.5 關(guān)系的閉包關(guān)系的閉包q定義：定義：R是非空集合是非空集合A上的關(guān)系上的關(guān)系,假設(shè)假設(shè)A上另外上另外有一個(gè)關(guān)系有一個(gè)關(guān)系R滿足如下三條：滿足如下三條：qR是自反的是自反的(對稱的，傳送

32、的對稱的，傳送的qRRqA上任何一個(gè)滿足以上兩條的關(guān)系上任何一個(gè)滿足以上兩條的關(guān)系R，均有，均有RR，q稱關(guān)系稱關(guān)系R為為R的自反的自反(對稱對稱,傳送傳送)閉包閉包,記作記作r(R) (s(R),t(R)737.5 關(guān)系的閉包關(guān)系的閉包q解釋解釋qR是在是在R的根底上添加有序?qū)Φ母咨咸砑佑行驅(qū)添加元素的目的是使添加元素的目的是使R具有自反性具有自反性(對稱性對稱性,傳傳送性送性)q添加后使之具有自反性添加后使之具有自反性(對稱性對稱性,傳送性傳送性)的一的一切關(guān)系中切關(guān)系中R是最小的一個(gè)是最小的一個(gè)747.5 關(guān)系的閉包關(guān)系的閉包q例例A=a,b,c，R=,q自反閉包自反閉包r(R)q,

33、q對稱閉包對稱閉包s(R)q,q傳送閉包傳送閉包t(R)q,r(R)r(R)a b ccbaacbcbabac757.5 關(guān)系的閉包關(guān)系的閉包q定理：定理：R是非空集合是非空集合A上的關(guān)系上的關(guān)系,那么那么qr(R)=RAq證明證明: RRA，RA是自反的是自反的q設(shè)設(shè)R滿足滿足RR,R是自反的是自反的qRAq那么那么R或或A q如如R,由由RR知知Rq如如A,由由R的自反性知的自反性知Rq均有均有RqRAR 767.5 關(guān)系的閉包關(guān)系的閉包q定理定理: 設(shè)設(shè)R是非空集是非空集A的關(guān)系的關(guān)系,那么那么qs(R)=RR-1 q證明證明:qRRR-1滿足定義第滿足定義第2條條qRR-1qRR-1q

34、R-1RqRR-1 qRR-1是對稱的是對稱的777.5 關(guān)系的閉包關(guān)系的閉包v如如RR,且且R是對稱的是對稱的vRR-1vR或或R-1v如如R,由由RR,那么那么Rv如如R-1,那么那么R,那么那么Rv因因R對稱對稱vR,RR-1Rv滿足定義第滿足定義第3條條787.5 關(guān)系的閉包關(guān)系的閉包q例例:設(shè)設(shè)A=1,2,3,A上的關(guān)系上的關(guān)系R如圖如圖,求求r(R),s(R)q解解:R=,qr(R)= RA q=,qs(R)= RR-1 q=, 1 2 3797.5 關(guān)系的閉包關(guān)系的閉包定理: 設(shè)R是非空集合A上的關(guān)系, 那么t(R)= R1R2 證明：首先證明R1R2 t(R)，運(yùn)用歸納法。n=

35、1，顯然R1= R t(R)假設(shè)Rk t(R)，對恣意有 Rk+1 =Rk R1 t(Rk R1) t(t(R) t(R) t(R)其次， t(R) R1R2即證R1R2傳送推論: 設(shè)A是非空有限集，R是集合A上的二元關(guān)系，那么存在正整數(shù)n，使得t(R)=RR2 Rn807.5 關(guān)系的閉包關(guān)系的閉包q例例 A=a,b,c,dqR=,qS=,求求t(R),t(S)q解解:R2=,R3=qt(R)=R,qS2=,S3=,S4=qt(S)=S, a b c dR a b c d S817.5 關(guān)系的閉包關(guān)系的閉包q給定關(guān)系給定關(guān)系R，r(R)，s(R)，t(R)的關(guān)系矩陣的關(guān)系矩陣分別為分別為M，M

36、r，Ms，Mt，那么：，那么：qMr=M+EqMs=M+MqMt=M+M2+M3+827.5 關(guān)系的閉包關(guān)系的閉包q關(guān)系圖分別為關(guān)系圖分別為G，Gr，Gs，Gt，那么：，那么：q調(diào)查調(diào)查G的每個(gè)頂點(diǎn)，假設(shè)沒有環(huán)就加上一個(gè)的每個(gè)頂點(diǎn)，假設(shè)沒有環(huán)就加上一個(gè)環(huán)，最終得到的是環(huán)，最終得到的是Grq調(diào)查調(diào)查G的每一條邊，假設(shè)有一條從的每一條邊，假設(shè)有一條從xi到到xj的的單向邊，那么在單向邊，那么在G中加一條中加一條xj到到xi的反方向的反方向邊，最終得到邊，最終得到Gsq調(diào)查調(diào)查G的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn)xi，找出從，找出從xi出發(fā)的一切出發(fā)的一切2步，步，3步，步，n步長的途徑。設(shè)途徑的終點(diǎn)步長的途徑。

37、設(shè)途徑的終點(diǎn)為為xj1， xj2， ， xjk。假設(shè)沒有從。假設(shè)沒有從xi到到xjl的邊，就加上這條邊，最終得到的邊，就加上這條邊，最終得到Gt837.5 關(guān)系的閉包關(guān)系的閉包q定理：設(shè)定理：設(shè)A是一集合，是一集合，R是是A上的二元關(guān)系，上的二元關(guān)系，那么有：那么有：qR是自反的當(dāng)且僅當(dāng)是自反的當(dāng)且僅當(dāng)r(R)RqR是對稱的當(dāng)且僅當(dāng)是對稱的當(dāng)且僅當(dāng)s(R)RqR是可傳送的當(dāng)且僅當(dāng)是可傳送的當(dāng)且僅當(dāng)t(R)RqR是自反的當(dāng)且僅當(dāng)是自反的當(dāng)且僅當(dāng)r(R)Rq證明：證明：Rr(R)。由自反閉包定義，。由自反閉包定義，r(R)R。847.5 關(guān)系的閉包關(guān)系的閉包q定理：設(shè)定理：設(shè)A是集合，是集合，R1

38、和和R2是是A上的二元關(guān)上的二元關(guān)系，系，R1R2，那么有：，那么有：qr(R1)r(R2)qs(R1)s(R2)qt(R1)t(R2)qr(R1)r(R2)q證明：證明： r(R1)=R1A ，r(R2)=R2A857.5 關(guān)系的閉包關(guān)系的閉包q定理：設(shè)定理：設(shè)X是一集合，是一集合，R是是X上的二元關(guān)系，上的二元關(guān)系，那么有：那么有：q假設(shè)假設(shè)R是自反的，那么是自反的，那么s(R),t(R)也自反也自反q假設(shè)假設(shè)R是對稱的，那么是對稱的，那么r(R),t(R)也對稱也對稱q假設(shè)假設(shè)R是可傳送的，那么是可傳送的，那么r(R)也可傳送也可傳送867.5 關(guān)系的閉包關(guān)系的閉包q定理：設(shè)定理：設(shè)X是

39、一集合，是一集合，R是是X上的二元關(guān)系，上的二元關(guān)系，那么有：那么有：q假設(shè)假設(shè)R是對稱的，那么是對稱的，那么t(R)也對稱也對稱q證明：歸納法證明假設(shè)證明：歸納法證明假設(shè)R是對稱，那么是對稱，那么Rn也對也對稱稱qn=1，顯然成立，顯然成立q假設(shè)假設(shè)Rn對稱，對恣意對稱，對恣意q Rn+1q t(RnR)q t(RnR)q RRn Rn+1 877.5 關(guān)系的閉包關(guān)系的閉包q定理：設(shè)定理：設(shè)X是一集合，是一集合，R是是X上的二元關(guān)系，上的二元關(guān)系，那么有：那么有：q假設(shè)假設(shè)R是對稱的，那么是對稱的，那么t(R)也對稱也對稱q證明：證明：RRn Rn+1 q任取任取，有，有q t(R)q n(

40、Rn)q n(Rn)q t(R)887.5 關(guān)系的閉包關(guān)系的閉包q假設(shè)假設(shè)R是傳送的，是傳送的，s(R)不一定是傳送的不一定是傳送的q反例：反例：R=,，qR是傳送的是傳送的q s(R)=,q s(R)不是傳送的不是傳送的89第七章第七章: 二元關(guān)系二元關(guān)系q q 第六節(jié)：等價(jià)關(guān)系與劃分第六節(jié)：等價(jià)關(guān)系與劃分907.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q等價(jià)關(guān)系：非空集合等價(jià)關(guān)系：非空集合A上的關(guān)系，滿足：上的關(guān)系，滿足：q自反的自反的q對稱的對稱的q可傳送的可傳送的q例例q實(shí)數(shù)實(shí)數(shù)(或或I、N集上集上)集合上的集合上的“=關(guān)系關(guān)系q選集上集合的相等關(guān)系選集上集合的相等關(guān)系q命題集合上的命題等價(jià)關(guān)

41、系命題集合上的命題等價(jià)關(guān)系917.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分例：設(shè)例：設(shè)A=1,2,3,4,5,6,7R=|x,yA(x-y)可被可被3整除整除試證明試證明R是等價(jià)關(guān)系是等價(jià)關(guān)系解：解：(1)R=， ，927.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分(2) R的關(guān)系矩陣的關(guān)系矩陣1001001001001001001001001001001001001001001001001RMn R滿足自反、對稱和可傳送的滿足自反、對稱和可傳送的937.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q等價(jià)類：設(shè)等價(jià)類：設(shè)R是非空是非空A集合上的等價(jià)關(guān)系，對集合上的等價(jià)關(guān)系，對于任何于任何xA，令：，令：qxR =y|yA

42、xRyqxR是由是由xA生成的生成的R等價(jià)類等價(jià)類qx為等價(jià)類為等價(jià)類xR的表示元素的表示元素947.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q討論討論q等價(jià)類等價(jià)類xR是一個(gè)集合，是一個(gè)集合，xR A (xR是是A的子集的子集)qxR中的元素是在中的元素是在A中，一切與中，一切與x具有等價(jià)關(guān)具有等價(jià)關(guān)系系R的元素所組成的集合的元素所組成的集合q在等價(jià)關(guān)系中的關(guān)系圖中，一個(gè)最大連通子圖在等價(jià)關(guān)系中的關(guān)系圖中，一個(gè)最大連通子圖中的點(diǎn)就是一個(gè)等價(jià)類中的點(diǎn)就是一個(gè)等價(jià)類957.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q例：例：qA=a,b,c,dqR=，qaR =a,b= bR qcR =c,d= dR967.6

43、等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q例：設(shè)例：設(shè)A=NqR=|xAyA(x-y)可被可被3整整除除q等價(jià)類等價(jià)類q0R =0，3，6，9 q1R =1，4，7，10 q2R=2，5，8，11977.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q定理定理 設(shè)設(shè)A是一個(gè)集合，是一個(gè)集合，R是是A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，xRy當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x=yq證明：證明：q充分性，由于充分性，由于xx=y,即即xy ，所以，所以xRy。q必要性，知必要性，知xRy，思索，思索x的恣意元素的恣意元素z，有，有zRx。根據(jù)。根據(jù)R的傳送性，有的傳送性，有zRy，因此，因此zy。證明。證明xy。類似可證明。類似可證明yx ，所，

44、所以以x=y987.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q定理：設(shè)定理：設(shè)A是一個(gè)集合，是一個(gè)集合，R是是A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，q對于一切對于一切x,yA，或者，或者x=y，或者，或者 x y=q證明：只需證明假設(shè)證明：只需證明假設(shè)xRy，那么，那么xy=q反證法：假設(shè)反證法：假設(shè)xy，那么，那么zxyq R Rq R (矛盾矛盾!)997.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q定理：設(shè)定理：設(shè)R是集合是集合A上的等價(jià)關(guān)系，那么上的等價(jià)關(guān)系，那么q A=x | xAq證明：首先易證證明：首先易證x | xA Aq 其次，對恣意其次，對恣意yAq yA yy yAq yx | xAq 所以：所以

45、： A x | xA1007.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q商集：商集：R是是A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，qR的一切等價(jià)類構(gòu)成的集合的一切等價(jià)類構(gòu)成的集合q記為記為A/R：xR | x Aq例：例：A為全班同窗的集合，為全班同窗的集合，|A|=n，(nN)q按指紋的一樣關(guān)系按指紋的一樣關(guān)系R1是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系qA/R1=x1R1,xnR1 q同姓關(guān)系同姓關(guān)系R2是一等價(jià)關(guān)系是一等價(jià)關(guān)系qA/ R2 =張張，李李，1017.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q 劃分：給定一非空集合劃分：給定一非空集合A，A的一個(gè)劃分為非的一個(gè)劃分為非空子集族空子集族S=A1, A2, Am，滿足

46、：，滿足：q Sq xy(x, ySxyxy=)q A1A2 Am= A1027.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q例：例：A=a,b,c,以下哪些以下哪些Ai為為A的一個(gè)劃分？的一個(gè)劃分？qA1=a,b,c qA2=a,c,bqA3=a,a,b,cqA4=a,b,c, qA5=a,a,b,c1037.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q等價(jià)關(guān)系與劃分有一一對應(yīng)關(guān)系等價(jià)關(guān)系與劃分有一一對應(yīng)關(guān)系q劃分到等價(jià)關(guān)系轉(zhuǎn)化：劃分到等價(jià)關(guān)系轉(zhuǎn)化：A是一非空集合，是一非空集合，S是是A的一個(gè)劃分，下述關(guān)系必定是一個(gè)等價(jià)關(guān)系的一個(gè)劃分，下述關(guān)系必定是一個(gè)等價(jià)關(guān)系qR= | x, y A x,y在在S的同一劃的同

47、一劃分分q等價(jià)關(guān)系到劃分的轉(zhuǎn)化：設(shè)等價(jià)關(guān)系到劃分的轉(zhuǎn)化：設(shè)A是非空集合，是非空集合，R是是A上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。R的商集是的商集是A的劃分的劃分1047.6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分q例：例：A =a,b,c,d,eqS=a,b,c,d,eq 對應(yīng)劃分對應(yīng)劃分S的等價(jià)關(guān)系為的等價(jià)關(guān)系為 qR=a,ba,bccd,ed,e=,105第七章第七章: 二元關(guān)系二元關(guān)系q 第七節(jié)：偏序關(guān)系第七節(jié)：偏序關(guān)系1067.7 偏序關(guān)系偏序關(guān)系q次序在現(xiàn)實(shí)生活中常見：次序在現(xiàn)實(shí)生活中常見：q小于，包含等小于，包含等q研討序?qū)嶋H的動機(jī)：研討序?qū)嶋H的動機(jī)：q研討普通次序關(guān)系研討普通次序關(guān)系q推導(dǎo)出普通序

48、關(guān)系的性質(zhì)推導(dǎo)出普通序關(guān)系的性質(zhì)q這些關(guān)系可以運(yùn)用于一切特定的序關(guān)系這些關(guān)系可以運(yùn)用于一切特定的序關(guān)系1077.7 偏序關(guān)系偏序關(guān)系q偏序關(guān)系偏序關(guān)系R (記作記作 )q自反性自反性: aA，有，有Rq反對稱性反對稱性: a,bR,假設(shè)假設(shè)R且且R,那么必有那么必有abq傳送性傳送性: a,b,cA,假設(shè)假設(shè)R,R, 必有必有Rq例例:偏序關(guān)系偏序關(guān)系qAa,b,cqR, ,abc1087.7 偏序關(guān)系偏序關(guān)系q 例：例：A是非零自然數(shù)集是非零自然數(shù)集, 是是A上的整除關(guān)系上的整除關(guān)系。q aA, a能整除能整除a q 具有自反性具有自反性q a,bA,如如a能整除能整除b,且且b能整除能整除

49、a,那么那么abq 具有反對稱性具有反對稱性 q a,b,cA,如如a能整除能整除b,b能整除能整除c,那么那么a能能整除整除c, q 具有傳送性具有傳送性q 是是A上的偏序關(guān)系上的偏序關(guān)系1097.7 偏序關(guān)系偏序關(guān)系q小于小于 ：a ba babq可比：可比：a與與b可比可比 a bb aq可比不同于等于可比不同于等于q例：例：A=1，2，3， 是是A上的整除關(guān)系上的整除關(guān)系q1，3可比可比q全序關(guān)系全序關(guān)系R：R是是A上的偏序關(guān)系上的偏序關(guān)系, 滿足：滿足：qa,bA, a與與b可比可比 q例：實(shí)數(shù)上的例：實(shí)數(shù)上的,關(guān)系是全序關(guān)系關(guān)系是全序關(guān)系1107.7 偏序關(guān)系偏序關(guān)系q哈斯圖哈斯圖

50、q得名于德國數(shù)學(xué)家得名于德國數(shù)學(xué)家Helmut Hasseq用來表示有限偏序集的一種數(shù)學(xué)圖表用來表示有限偏序集的一種數(shù)學(xué)圖表q偏序集：偏序集：1117.7 偏序關(guān)系偏序關(guān)系q 覆蓋：覆蓋：，b覆蓋覆蓋a假設(shè)假設(shè)q a b，不存在，不存在cA，a c bq 哈斯圖思緒：哈斯圖思緒：q 一切結(jié)點(diǎn)的自回路均省略一切結(jié)點(diǎn)的自回路均省略q 省略一切弧上的箭頭省略一切弧上的箭頭,適當(dāng)陳列適當(dāng)陳列A中元素的位中元素的位置置,如如a b,那么那么a畫在畫在b的下方的下方q 如如a b,b c,那么必有那么必有a c, a到到b有邊有邊, b到到c有邊有邊,那么那么a到到c的無向弧省略的無向弧省略q 條件條件2

51、，3等于說假設(shè)等于說假設(shè)b覆蓋覆蓋a,那么畫一條從那么畫一條從a到到b的弧線，否那么不畫的弧線，否那么不畫1127.7 偏序關(guān)系偏序關(guān)系q例：畫出以下偏序集的哈斯圖。例：畫出以下偏序集的哈斯圖。qqR整除整除=,1253461137.7 偏序關(guān)系偏序關(guān)系q例：例：A=a,b,c,包含關(guān)系包含關(guān)系R是是P(A)上的偏上的偏序關(guān)系序關(guān)系,哈斯圖如下哈斯圖如下:qP(A)=,a,b,c,a,b,a,c,b,c,a,b,c aaa,ba,bbba,b,ca,b,cb,cb,ccca,ca,c1147.7 偏序關(guān)系偏序關(guān)系q最小最小(大大)元：設(shè)元：設(shè)是偏序集是偏序集,集合集合BAq最大元最大元bB：a

52、B,均有均有a bq最小元最小元bB：aB,均有均有b aq闡明闡明q假設(shè)假設(shè)A的子集的子集B存在最大存在最大(小小)元素元素,那么最大那么最大(小小)元素是獨(dú)一的元素是獨(dú)一的q最大最大(小小)元能夠不存在元能夠不存在1157.7 偏序關(guān)系偏序關(guān)系例例:A1,2,3,4,5,6,R是整除關(guān)系是整除關(guān)系,哈斯圖為哈斯圖為125346 A中不存在最大元中不存在最大元1167.7 偏序關(guān)系偏序關(guān)系q極大極大(小小)元：設(shè)元：設(shè)是偏序集是偏序集,BAq極大元極大元bB：aB,如如b a,那么那么abq不存在不存在aB，b aq極小元極小元bB：aB,如如a b,那么那么abq不存在不存在aB，a bq

53、闡明闡明q極大元未必是最大元極大元未必是最大元q極大元未必是獨(dú)一的極大元未必是獨(dú)一的q假設(shè)假設(shè)B是有限集是有限集,那么那么B必存在極大元必存在極大元q最大元就是極大元最大元就是極大元1253461177.7 偏序關(guān)系偏序關(guān)系q例：以下哈斯圖表示的偏序集能否有最大例：以下哈斯圖表示的偏序集能否有最大(小小)元？能否有極大元？能否有極大(小小)元？元？ aaa,ba,bbba,b,ca,b,cb,cb,ccca,ca,c1187.7 偏序關(guān)系偏序關(guān)系q上上(下下)界：設(shè)界：設(shè)是偏序集是偏序集, BA, aAqB的上界的上界a：對每個(gè)：對每個(gè)bB,有有b aqB的下界的下界a：對每個(gè)：對每個(gè)bB,有

54、有a bq闡明闡明q上下界不一定獨(dú)一上下界不一定獨(dú)一1197.7 偏序關(guān)系偏序關(guān)系q例：例：, A=2,3,6,12,24,36q B:2,3,2,3,6,6,12,6,12,24,36A 上界上界下界下界B2,36,12,24,36 6,12,24,36 2,3,66,12,24,366,12,24,366,1212,24,36 12,24,36 2,3,6 2,3,6 6,12,24,362,3,6 2,3,6 1207.7 偏序關(guān)系偏序關(guān)系q上上(下下)確界：設(shè)確界：設(shè)是偏序集是偏序集, BAq最小上界：最小上界：C=b|b為為B的上界的上界的最小元的最小元q最大下界：最大下界：D=b|

55、b為為B的下界的下界的最大元的最大元q闡明闡明qB的最小元一定是的最小元一定是B的下界，同時(shí)也是的下界，同時(shí)也是B的最大下的最大下界；界；B的最大元一定是的最大元一定是B的上界，同時(shí)也是的上界，同時(shí)也是B的最的最小上界小上界q最小上界或最大下界能夠不存在最小上界或最大下界能夠不存在q假設(shè)存在最小上界或最大下界，是獨(dú)一的假設(shè)存在最小上界或最大下界，是獨(dú)一的1217.7 偏序關(guān)系偏序關(guān)系例例:A，R整除整除, A=2,3,6,12,24,36 B:2,3,2,3,6,6,12,6,12,24,36A 上確界上確界下確界下確界B2 2,3 3 6 62 2,3 3,6 6 6 66 6,1212 1

56、2126 6 6 6,1212,2424,3636 6 6 1227.7 偏序關(guān)系偏序關(guān)系q拓?fù)渑判颍航o定一個(gè)非空有限的偏序集合拓?fù)渑判颍航o定一個(gè)非空有限的偏序集合，構(gòu)造出一個(gè)全序集合，構(gòu)造出一個(gè)全序集合 ，使得每當(dāng)使得每當(dāng)a b有有a b，方法如下：，方法如下：q選取選取A的極小元的極小元a，使，使a是是列表表示列表表示中的第一個(gè)元素中的第一個(gè)元素q對子集對子集A-a反復(fù)這一過程，每次一個(gè)新的反復(fù)這一過程，每次一個(gè)新的極小元素被找到，它在極小元素被找到，它在的列表表示中的列表表示中成為下一個(gè)元素成為下一個(gè)元素q反復(fù)這一過程，直到反復(fù)這一過程，直到A的元素被抽完的元素被抽完1237.7 偏序關(guān)

57、系偏序關(guān)系q例：求以下偏序集對應(yīng)的全序集例：求以下偏序集對應(yīng)的全序集 1 12 23 34 46 68 812122424 1 13 32 26 64 48 812122424124第七章第七章 習(xí)題課習(xí)題課 l 有序?qū)Γ河行驅(qū)Γ簂 由兩個(gè)元素由兩個(gè)元素x，y按給定順序陳列組成的二元組合按給定順序陳列組成的二元組合l 笛卡兒積：笛卡兒積：l 集合集合A中元素為第一元素，集合中元素為第一元素，集合B中元素為第二元素的有序?qū)性貫榈诙氐挠行驅(qū)痩 二元關(guān)系二元關(guān)系R：l 滿足以下條件之一的集合：滿足以下條件之一的集合：l 集合非空，且它的元素都是有序?qū)戏强?，且它的元素都是有序?qū) 集合

58、為空集集合為空集l 從從A到到B的關(guān)系：的關(guān)系：l A，B是集合，是集合，AB的任何子集所定義的二元關(guān)系的任何子集所定義的二元關(guān)系l A上的關(guān)系：上的關(guān)系：l A=Bl 空關(guān)系，全域關(guān)系，恒等關(guān)系，包含關(guān)系空關(guān)系，全域關(guān)系，恒等關(guān)系，包含關(guān)系l 關(guān)系的表示法：關(guān)系的表示法：l 集合表達(dá)式、關(guān)系矩陣、關(guān)系圖集合表達(dá)式、關(guān)系矩陣、關(guān)系圖125第七章第七章 習(xí)題課習(xí)題課l 關(guān)系的八種運(yùn)算：l 定義域：l 值域：l 域：l 逆：l 右復(fù)合：l 限制：l 像：l 冪：l R0 =A；Rn+1=RnRfldRdomRranR),(|RyxyxdomR),(|RyxxyranR,|,1RxyyxR),(|,

59、GytFtxtyxGFo,|RAx yxRyxA )(ARranAR126第七章第七章 習(xí)題課習(xí)題課l 關(guān)系運(yùn)算的五種性質(zhì)關(guān)系運(yùn)算的五種性質(zhì): u自自 反：反：u反自反：反自反： u對對 稱：稱：u反對稱：反對稱：u傳傳 遞：遞： )(xRxXxx xRx)Xx(x )(yRxxRyXyXxyx )(yxyRxxRyXyXxyx )(xRzyRzxRyXzXyXxzyx 127第七章第七章 習(xí)題課習(xí)題課l 關(guān)系的三種閉包：關(guān)系的三種閉包：l 自反閉包：自反閉包：l r(R)=RAl 對稱閉包：對稱閉包：l s(R)=RR-1 l 傳送閉包：傳送閉包：l t(R)= R1R2 128第七章第七章

60、 習(xí)題課習(xí)題課l A上的等價(jià)關(guān)系：上的等價(jià)關(guān)系：l自反的；對稱的；可傳送的自反的；對稱的；可傳送的l等價(jià)類：等價(jià)類：l xR =y|yA xRyl商集：商集：l R的一切等價(jià)類構(gòu)成的集合，的一切等價(jià)類構(gòu)成的集合，l記為記為A/R：xR | x Al劃分：劃分：l A的非空子集族的非空子集族S=A1, A2, Am，滿足：，滿足：lSlxy(x, ySxyxy=)l A1A2 Am= Al A上的偏序關(guān)系與偏序集上的偏序關(guān)系與偏序集129根本要求根本要求l 熟練掌握關(guān)系的三種表示法熟練掌握關(guān)系的三種表示法 l 可以斷定關(guān)系的性質(zhì)，以及等價(jià)關(guān)系、偏序關(guān)系可以斷定關(guān)系的性質(zhì)，以及等價(jià)關(guān)系、偏序關(guān)系l