數(shù)理邏輯二元關(guān)系.ppt

《數(shù)理邏輯二元關(guān)系.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)理邏輯二元關(guān)系.ppt（148頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第7章 二元關(guān)系,離 散 數(shù) 學(xué),六度空間理論,六度空間理論：你和任何一個(gè)陌生人之間的關(guān)系不會(huì)超過六層，也就是說(shuō)，最多通過六個(gè)人你就能夠認(rèn)識(shí)任何一個(gè)陌生人。,X,眾里尋她千百度,關(guān)系理論歷史悠久。它與集合論、數(shù)理邏輯、組合學(xué)、圖論和布爾代數(shù)都有密切的聯(lián)系。 關(guān)系是日常生活以及數(shù)學(xué)中的一個(gè)基本概念，例如： 兄弟關(guān)系，師生關(guān)系、位置關(guān)系、大小關(guān)系、等于關(guān)系、包含關(guān)系等。,,另外，關(guān)系理論還廣泛用于計(jì)算機(jī)科學(xué)技術(shù)，如 計(jì)算機(jī)程序的輸入、輸出關(guān)系； 數(shù)據(jù)庫(kù)的數(shù)據(jù)特性關(guān)系； 數(shù)據(jù)結(jié)構(gòu)本身就是一個(gè)關(guān)系等。 在某種意義下，關(guān)系是有聯(lián)系的一些對(duì)象相互之間的各種比較行為。,本章說(shuō)明,本章的主要內(nèi)容 有序?qū)εc笛卡

2、爾集 二元關(guān)系的定義和表示法 關(guān)系的運(yùn)算 關(guān)系的性質(zhì) 關(guān)系的閉包 等價(jià)關(guān)系與劃分 偏序關(guān)系 本章與后續(xù)各章的關(guān)系 本章是函數(shù)的基礎(chǔ) 本章是圖論的基礎(chǔ),7.1 有序?qū)εc笛卡爾積,定義7.1 由兩個(gè)元素x和y按一定順序排列成的二元組叫做一個(gè)有序?qū)?ordered pair)或序偶，記作，其中x是它的第一元素，y是它的第二元素。 有序?qū)哂幸韵滦再|(zhì)： （1）當(dāng)xy時(shí)，。 （2）的充分必要條件是xu且yv。,說(shuō)明,有序?qū)χ械脑厥怯行虻?集合中的元素是無(wú)序的,定義7.2 設(shè)A，B為集合,以A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)?，所有這樣的有序?qū)M成的集合叫做A和B的笛卡爾積(Cartesia

3、n product)，記作AB。 笛卡爾積的符號(hào)化表示為 AB|xAyB,,笛卡爾積的定義,A表示某大學(xué)所有學(xué)生的集合，B表示大學(xué)開設(shè)的所有課程的集合， 則AB可以用來(lái)表示該校學(xué)生選課的所有可能情況。 令A(yù)是直角坐標(biāo)系中x軸上的點(diǎn)集，B是直角坐標(biāo)系中y軸上的點(diǎn)集， 于是AB就和平面點(diǎn)集一一對(duì)應(yīng)。,舉例,笛卡爾 (RenDescartes，15961650) 在數(shù)學(xué)史上，笛卡爾因與費(fèi)馬共同創(chuàng)立解析幾何而聞名于世。與此同時(shí)，笛卡爾還是一位哲學(xué)家、物理學(xué)家、生物學(xué)家，尤其在哲學(xué)上的杰出貢獻(xiàn)使他成為當(dāng)之無(wú)愧的一代哲學(xué)大師。,笛卡爾是法國(guó)人，出生于一個(gè)貴族家庭，因家境富裕從小多病，學(xué)校允許他在床上早讀，

4、使得他有更多的時(shí)間獨(dú)自靜靜地思考各種關(guān)于自然、科學(xué)與人的問題，從而養(yǎng)成沉思的習(xí)慣和孤僻的性格。 1628年，笛卡爾移居荷蘭，潛心從事哲學(xué)、數(shù)學(xué)、 天文學(xué)、物理學(xué)、化學(xué)和生理學(xué)等領(lǐng)域的研究。他的主要著作都是在荷蘭完成的，其中1637年出版的方法論 一書成為哲學(xué)經(jīng)典。這本書中的3個(gè)著名附錄幾何、折光和氣象更奠定了笛卡爾在數(shù)學(xué)、物理和天文學(xué)中的地位。,在幾何中，笛卡爾分析了幾何學(xué)與 代數(shù)學(xué)的優(yōu)缺點(diǎn)，指出：希臘人的幾何過多的依賴于圖形，總是要尋求一些奇妙的想法。代數(shù)卻完全受法則和公式的控制，以致于阻礙了自由的思想和創(chuàng)造。他同時(shí)看到了幾何的直觀與推理的優(yōu)勢(shì)和代數(shù)機(jī)械化運(yùn)算的力量。于是笛卡爾著手解決這個(gè)問

5、題，并由此創(chuàng)立了解析幾何。 1649年冬，笛卡爾應(yīng)瑞典女王克里斯蒂安的邀請(qǐng)，來(lái)到了斯德哥爾摩，任宮廷哲學(xué)家，為瑞典女王授課。由于他身體孱弱，不能適應(yīng)那里的氣候，1650年初便患肺炎抱病不起，同年二月病逝。終年54歲。1799年法國(guó)大革命后，笛卡爾的骨灰被送到了法國(guó)歷史博物館。 (補(bǔ)充：瑞典女王為了顯示對(duì)知識(shí)的尊重,專門派一艘軍艦接笛卡爾到瑞典),笛卡爾積舉例,設(shè)A=a,B=b,c,C=,D=1,2，請(qǐng)分別寫出下列笛卡爾積中的元素。 （1）AB,BA； （2）AC,CA； （3）A(BD),(AB)D。 解 根據(jù)笛卡爾積的定義，有 （1）AB=,, BA=,； （2）AC=,CA=；,笛卡爾積運(yùn)

6、算不滿足交換律,AB=當(dāng)且僅當(dāng)A=或者B=,（3）因?yàn)锽D=,,,， 所以A(BD)=,, ,。 同理，(AB)D=,1,,2, ,1,,2。,笛卡爾積運(yùn)算不滿足結(jié)合律,對(duì)有限集A,B，有|AB|=|BA|=|A||B|,,笛卡爾積的運(yùn)算性質(zhì),(1)對(duì)任意集合A，根據(jù)定義有 A, A (2)一般的說(shuō)，笛卡爾積運(yùn)算不滿足交換律，即 ABBA (當(dāng) A B AB 時(shí)) (3)笛卡爾積運(yùn)算不滿足結(jié)合律，即 (AB)CA(BC)(當(dāng) A B C 時(shí)) (4)笛卡爾積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即 A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(

7、CA) (5)AC BD AB CD,A(BC)=(AB)(AC)的證明,任取 A(BC) xA yBC xA (yByC) (xAyB) (xAyC) AB AC (AB)(AC) 所以 A(BC)=(AB)(AC),關(guān)于ACBD ABCD的討論,該性質(zhì)的逆命題不成立，可分以下情況討論。 （1）當(dāng)A=B=時(shí)，顯然有AC 和 BD 成立。 （2）當(dāng)A且B時(shí)，也有AC和BD成立，證明如下： 任取xA，由于B,必存在yB,因此有 xAyB AB，又因?yàn)?ABCD CD xCyD xC 從而證明了 AC。 同理可證 BD。,關(guān)于ACBD ABCD的討論,（3）當(dāng)A而B時(shí)，有AC成立，但不一定有BD

8、成立。 反例：令A(yù),B1,C3,D4。 （4）當(dāng)A而B時(shí)，有BD成立，但不一定有AC成立。 反例略。,例7.2,例7.2 設(shè)A=1,2,求P(A)A。,P(A)A ,1,2,1,21,2 ,, ,, ,, ,,解答,例7.3,例7.3 設(shè)A，B，C，D為任意集合，判斷以下命題是否為真，并說(shuō)明理由。(1) ABAC BC(2) A-(BC)(A-B)(A-C)(3) ABCD ACBD(4) 存在集合A，使得A AA,(1) 不一定為真。當(dāng)A，B1,C2時(shí)，有 ABAC，但BC。 (2) 不一定為真。當(dāng)A=B=1,C2時(shí)，有 A-(BC)11 (A-B)(A-C)1 (3) 為真。由代入

9、原理可證。 (4) 為真。當(dāng)A時(shí)，有 A AA 成立。,解答,7.2 二元關(guān)系(binary relation),定義7.3 如果一個(gè)集合滿足以下條件之一： （1）集合非空，且它的元素都是有序?qū)Γ?）集合是空集 則稱該集合為一個(gè)二元關(guān)系，記作R。二元關(guān)系也可簡(jiǎn)稱為關(guān)系。對(duì)于二元關(guān)系R，如果R，可記作xRy；如果R，則記作xRy。,設(shè)R1,，R2,a,b。 則R1是二元關(guān)系，R2不是二元關(guān)系，只是一個(gè)集合，除非將a和b定義為有序?qū)Α?根據(jù)上面的記法可以寫1R12，aR1b，aR1c等。,舉例,,,R,,,是否為二元關(guān)系？,集合A上的二元關(guān)系的數(shù)目依賴于A的基數(shù)。 如果|A|=n，那么|AA|=n

10、2， AA的子集就有 個(gè)。 每一個(gè)子集代表一個(gè)A上的二元關(guān)系，所以A上有 個(gè)不同的二元關(guān)系。 例如|A|=3，則A上有 個(gè)不同的二元關(guān)系。,7.2 二元關(guān)系,定義7.4 設(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= 等都是從A到B的二元關(guān)系，而R3和R4同時(shí)也是A上的二元關(guān)系。,舉例,說(shuō)明,常用的關(guān)系,定義7.5 對(duì)任意集合A，定義 全域關(guān)系 EA=|xAyA=AA 恒等關(guān)系 IA=|xA 空關(guān)系 ,設(shè) A=1,2，那么 EA=,,, IA=,,舉例,其它常

11、用的關(guān)系,小于或等于關(guān)系：LA=|x,yAxy，其中 AR。 整除關(guān)系：DB=|x,yBx整除y，其中 AZ* Z*是非零整數(shù)集 包含關(guān)系：R|x,yAxy，其中 A是集合族。,(1)設(shè) A=1,2,3，Ba,b則 LA=,,,,, DA=,,,, (2)令A(yù)=P(B)=,a,b,a,b，則A上的包含關(guān)系是 R,,,, ,,, ,,舉例,例7.4,例7.4 設(shè)A=1,2,3,4，下面各式定義的R都是A上的關(guān)系，試用列元素法表示R。 (1) R= | x是y的倍數(shù)(2) R= | (x-y)2A(3) R= | x/y是素?cái)?shù)(4) R= | xy,解答,(1)R=,,,,,,, (2)R=,

12、,,,,,,,, (3)R=,, (4)R=EA-IA=,,,,,,, ,,,,,關(guān)系的表示方法,關(guān)系的三種表示方法： 集合表達(dá)式 關(guān)系矩陣 關(guān)系圖 關(guān)系矩陣和關(guān)系圖可以表示有窮集上的關(guān)系。,關(guān)系矩陣和關(guān)系圖的定義,設(shè)A=x1,x2,,xn,R是A上的關(guān)系。令,則,是R的關(guān)系矩陣，記作MR。,設(shè)A=x1,x2,,xn,R是A上的關(guān)系。令圖G=，其中頂點(diǎn)集合V=A，邊集為E。對(duì)于 xi,xjV，滿足 E xiRxj 稱圖G為R的關(guān)系圖，記作 GR。,關(guān)系矩陣和關(guān)系圖的實(shí)例,設(shè) A=1,2,3,4，R=,,,,，則R的關(guān)系矩陣和關(guān)系圖分別是,7.3 關(guān)系的運(yùn)算,定義7.6 設(shè)R是二元關(guān)系。 (1

13、)R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域(domain)，記為dom R。形式化表示為：dom R x | y(R ) (2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域(range) ，記作ran R。形式化表示為ran Ry | x(R) (3)R的定義域和值域的并集稱為R的域(field)，記作fld R。形式化表示為fld Rdom R ran R,例7.5 求R=,,,的定義域、值域和域。 解答dom R1,2,4 ran R2,3,4 fld R1,2,3,4,關(guān)系的逆,定義7.7 設(shè)R為二元關(guān)系，R的逆關(guān)系，簡(jiǎn)稱R的逆(inverse)，記作R-1,其中 R-1|R

14、將R的關(guān)系圖中每條有向弧的方向反過來(lái)就得到R-1的關(guān)系圖 MR-1為MR的轉(zhuǎn)置矩陣 例如，小于關(guān)系的逆關(guān)系是大于關(guān)系，大于關(guān)系的逆關(guān)系是小于關(guān)系，相等關(guān)系的逆關(guān)系仍是相等關(guān)系。 例：R=(a,b),(b,c),(a,c),(b,d),則 R-1 = (b,a),(c,b),(c,a),(d,b),關(guān)系的復(fù)合運(yùn)算,定義7.8 設(shè)F,G為二元關(guān)系，G對(duì)F的右復(fù)合(composite)記作FG，其中 FG | t(FG) 例7.6 設(shè)F,,G=，則 FGGF 例：兄弟關(guān)系和父子關(guān)系的複合是叔侄關(guān)系， 姐妹關(guān)系和母子關(guān)系的複合是姨與外甥關(guān)系。,說(shuō)明,可以把二元關(guān)系看作一種作用，R可以解釋為x通過

15、R的作用變換到y(tǒng)。 FG表示兩個(gè)作用的連續(xù)發(fā)生。,還可使用關(guān)系圖或關(guān)系矩陣求解 在關(guān)系矩陣中,若對(duì)0,1中的元素的加法使用邏輯加（析?。?則對(duì)A上的任意的關(guān)系R,S,都有: MRS = MR MS 結(jié)論： 關(guān)系的復(fù)合不滿足交換律。,關(guān)系的復(fù)合運(yùn)算,課堂練習(xí),設(shè)A=a,b,c,d,B=b,c,d,C=a,b,d, R=,,是A到B的關(guān)系，S=,,是B到C的關(guān)系。 試用關(guān)系的三種表示方法求RS。,解（1）RS=,,；,（2）RS的關(guān)系圖如右1圖所示，得RS=,,；,解（3）,,關(guān)系的限制和像,定義7.9 設(shè)R為二元關(guān)系，A是集合 (1) R在A上的限制(restriction)記作RA，其中 RA

16、=|xRyxA (2) A在R下的像(image)記作RA，其中 RA=ran(RA),說(shuō)明,R在A上的限制RA是R的子關(guān)系。 A在R下的像RA是ran R的子集。,例7.7,設(shè)R，，，，,R1,，,R ,,R2,3,，，,R1,2,3,R ,,R3,2,關(guān)系與集合的說(shuō)明,關(guān)系是集合，集合運(yùn)算對(duì)于關(guān)系也是適用的。 規(guī)定： 關(guān)系運(yùn)算中逆運(yùn)算優(yōu)先于其它運(yùn)算 所有的關(guān)系運(yùn)算都優(yōu)先于集合運(yùn)算， 未規(guī)定優(yōu)先級(jí)的運(yùn)算以括號(hào)決定運(yùn)算順序。 例如： ran F-1 FGFH ran (FA),例題,設(shè)A表示是學(xué)校的所有學(xué)生的集合，B表示學(xué)校的所有課程的集合，并設(shè)R1由所有有序?qū)M成，其中a是選修課程b的學(xué)生。

17、R2由所有的有序?qū)?gòu)成，其中課程b是a的必修課。則關(guān)系R1R2、R1R2、R1R2、R1R2、R2R1的含義為 R1R2：a是一個(gè)學(xué)生，他或者選修了課程b，或者課程b是他的必修課。 R1R2：a是一個(gè)學(xué)生，他選修了課程b并且課程b也是a的必修課。 R1R2：學(xué)生a已經(jīng)選修了課程b，但課程b不是a的選修課，或者課程b是a的必修課，但是a沒有選修它。 R1R2：學(xué)生a已經(jīng)選修了課程b，但課程b不是a的選修課。 R2R1：課程b是學(xué)生a的必修課，但是a沒有選修它。,課堂練習(xí)題,設(shè)A表示工人的集合,B表示工作的集合. 設(shè)R1 表示A到B的二元關(guān)系: R1=(a,b)aA,bB, a分配去做工作b.

18、設(shè)R2表示A到A的二元關(guān)系: R2=(a1,a2)a1,a2A,a1和a2不能友好相處. 請(qǐng)你用R1和R2表示關(guān)系 R,使得xRy表示 x,y分配去做 同樣工作且能友好相處.,解答：因?yàn)镽1是A到B的二元關(guān)系,故R1-1表示B到A的二元關(guān)系, 則R1R1-1表示從A到A的二元關(guān)系,即由分配做同一樣工作的兩個(gè)人構(gòu)成的序偶的全體.因此R=R1R1-1-R2,定理7.1,定理7.1 設(shè)F是任意的關(guān)系，則 (1)(F-1)-1F (2)dom F-1ran F，ran F-1dom F,(1)任取，由逆的定義有 (F-1)-1 F-1 F,(2)任取x xdom F-1 y(F-1) y(F) xra

19、n F 所以有 dom F-1ran F,證明,定理7.2,定理7.2 設(shè)F，G，H是任意的關(guān)系，則 (1)(FG)HF(GH) (2)(FG)-1G-1 F-1,證明,(1)任取， (FG)H t(FG(t,y)H) t(s(FG)H) ts(FGH) s(Ft(GH)) s(FGH) F(GH),定理7.2,定理7.2 設(shè)F，G，H是任意的關(guān)系，則 (1)(FG)HF(GH) (2)(FG)-1G-1F-1,證明,(2)任取， (FG)-1 FG t(FG) t(F-1G-1) G-1 F-1,定理7.3,定理7.3 設(shè)R為A上的關(guān)系，則 R IAIA RR,證明,(1)任取， R IA

20、 t(R(t,y)IA) t(Rty) R,R RyA RIA) R IA,綜上所述，有 RIAR 同理可證 IARR,定理7.4,定理7.4 設(shè)F，G，H是任意的關(guān)系，則(1) F(GH)FGFH(2) (GH)FGFHF(3) F(GH)FGFH(4) (GH)FGFHF,證明,(3) F(GH) t(F(t,y)GH) t(F(t,y)G(t,y)H) t((F(t,y)G) (F(t,y)H)) t(F(t,y)G) t(F(t,y)H) FG FH FGFH,定理7.4的推論,由數(shù)學(xué)歸納法不難證明定理7.4的結(jié)論對(duì)于有限多個(gè)關(guān)系的并和交也是成立的，即有 R(R1R2Rn)RR1RR2

21、RRn R1R2Rn)RR1RR2RRnR R(R1R2Rn)RR1RR2RRn R1R2Rn)RR1RR2RRnR,定理7.5,定理7.5 設(shè)F為關(guān)系，A,B為集合，則 (1) F(AB)FAFB (2) FABFAFB (3) F(AB)FAFB (4) FABFAFB,定理7.5 (1)的證明,(1) F(AB)FAFB,證明,任取， F(AB) F x(AB) F (xAxB) (FxA) (FxB) FA FB FAFB 所以有 F(AB)FAFB。,定理7.5 (4)的證明,(4) FABFAFB,證明,任取y， yFAB x(FxAB) x(FxAxB) x((FxA)(FxB

22、)) x(FxA) x(FxB) yFA yFB yFAFB 所以有 FABFAFB,關(guān)系的冪運(yùn)算,定義7.10 設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為： （1） R0|xAIA （2） Rn+1Rn R,說(shuō)明,對(duì)于A上的任何關(guān)系R1和R2都有 R10R20IA 即：A上任何關(guān)系的0次冪都相等，都等于A上的恒等關(guān)系IA。 對(duì)于A上的任何關(guān)系R都有R1R，因?yàn)?R1R0 RIA RR,Rn的計(jì)算,給定A上的關(guān)系R和自然數(shù)n，怎樣計(jì)算Rn呢？ 若n是0或1，結(jié)果是很簡(jiǎn)單的。下面考慮n2的情況。 如果R是用集合表達(dá)式給出的，可以通過n-1次復(fù)合計(jì)算得到Rn。 如果R是用關(guān)系矩陣M給出的，則

23、Rn的關(guān)系矩陣是Mn，即n個(gè)矩陣M之積。與普通矩陣乘法不同的是，其中的相加是邏輯加，即 1+11，1+00+11，0+00 如果R是用關(guān)系圖G給出的，可以直接由圖G得到Rn的關(guān)系圖G。G的頂點(diǎn)集與G相同?？疾霨的每個(gè)頂點(diǎn)xi，如果在G中從xi出發(fā)經(jīng)過n步長(zhǎng)的路徑到達(dá)頂點(diǎn)xj，則在G中加一條從xi到xj的邊。當(dāng)把所有這樣的邊都找到以后，就得到圖G。,例7.8,例7.8 設(shè)Aa,b,c,d，R,,,，求R的各次冪，分別用矩陣和關(guān)系圖表示。,解答,例7.8,因此M4M2，即R4R2。因此可以得到 R2R4R6 R3R5R7 用關(guān)系圖的方法得到R0, R1, R2, R3,的關(guān)系圖如圖7.2所示。,冪

24、運(yùn)算的性質(zhì),定理7.6 設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt。,R為A上的關(guān)系，對(duì)任何自然數(shù)k，Rk都是AA的子集。,證明,又知|AA|=n2，|P(AA)|= ，,即AA的不同子集僅 個(gè)。,當(dāng)列出R的各次冪R0，R1，R2，， ，時(shí)，,必存在自然數(shù)s和t使得Rs=Rt。,說(shuō)明,該定理說(shuō)明有窮集上只有有窮多個(gè)不同的二元關(guān)系。當(dāng)t足夠大時(shí)，Rt必與某個(gè)Rs(s

25、所以對(duì)一切m,nN有 Rm RnRm+n。,Rm R0,Rm IA,Rm,Rm+0,假設(shè)Rm Rn=Rm+n，則有,Rm Rn+1,Rm (Rn R),(Rm Rn)R,Rm+n+1，,定理7.7,定理7.7 設(shè)R是A上的關(guān)系，m,nN，則 (1)Rm RnRm+n (2)(Rm)nRmn,證明,(2)對(duì)于任意給定的mN,施歸納于n。 若n=0，則有,所以對(duì)一切m,nN 有(Rm)n=Rmn。,(Rm)0,IA,R0,Rm0,假設(shè)(Rm)nRmn，則有,(Rm)n+1,(Rm)n Rm,Rmn+m,Rm(n+1),定理7.8,定理7.8 設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(s

26、Rt，則 (1) 對(duì)任何kN有 Rs+k=Rt+k (2) 對(duì)任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s (3) 令S=R0，R1，，Rt-1，則對(duì)于任意的qN有 RqS,證明,(1) Rs+kRs RkRt RkRt+k (2)對(duì)k歸納。 若k=0，則有 Rs+0 p+iRs+i 假設(shè) Rs+kp+iRs+i，其中pt-s，則,Rs+(k+1)p+i,Rs+kp+i+p,Rs+i Rp=Rs+p+i,Rs+t-s+i,Rt+i,Rs+i,由歸納法命題得證。,Rs+kp+i Rp,定理7.8,定理7.8 設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(s

27、任何kN有 Rs+k=Rt+k (2) 對(duì)任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s (3) 令S=R0，R1，，Rt-1，則對(duì)于任意的qN有 RqS,證明,(3)任取qN，若q

28、數(shù)m和n，使得m

29、eflexivity)的。 (2)若x(xAR)，則稱R在A上是反自反(irreflexivity)的。 例如 全域關(guān)系EA，恒等關(guān)系IA，小于等于關(guān)系LA，整除關(guān)系DA都是為A上的自反關(guān)系。 包含關(guān)系R是給定集合族A上的自反關(guān)系。 小于關(guān)系和真包含關(guān)系都是給定集合或集合族上的反自反關(guān)系。,例7.10,例7.10 設(shè)A=1,2,3，R1，R2，R3是A上的關(guān)系，其中 R1, R2,,, R3 說(shuō)明R1，R2和R3是否為A上的自反關(guān)系和反自反關(guān)系。 解答 R1既不是自反的也不是反自反的， R2是自反的， R3是反自反的。,對(duì)稱性和反對(duì)稱性,定義7.12 設(shè)R為A上的關(guān)系， （1）若xy(x,yA

30、RR)，則稱R為A上對(duì)稱(symmetry)的關(guān)系。 （2）若xy(x,yARRx=y)，則稱R為A上的反對(duì)稱(antisymmetry)關(guān)系。 例如 A上的全域關(guān)系EA，恒等關(guān)系IA和空關(guān)系都是A上的對(duì)稱關(guān)系。 恒等關(guān)系IA和空關(guān)系也是A上的反對(duì)稱關(guān)系。 但全域關(guān)系EA一般不是A上的反對(duì)稱關(guān)系，除非A為單元集或空集。,例7.11,例7.11 設(shè)A1,2,3，R1，R2，R3和R4都是A上的關(guān)系，其中 R1, R2,, R3, R4,, 說(shuō)明R1，R2，R3和R4是否為A上對(duì)稱和反對(duì)稱的關(guān)系。 解答 R1既是對(duì)稱也是反對(duì)稱的。 R2是對(duì)稱的但不是反對(duì)稱的。 R3是反對(duì)稱的但不是對(duì)稱的。 R4既

31、不是對(duì)稱的也不是反對(duì)稱的。,傳遞性,定義7.13 設(shè)R為A上的關(guān)系，若 xyz(x,y,zARRR) 則稱R是A上的傳遞(transitivity)關(guān)系。 例如 A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系都是A上的傳遞關(guān)系。 小于等于關(guān)系，整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的傳遞關(guān)系。 小于關(guān)系和真包含關(guān)系仍舊是相應(yīng)集合上的傳遞關(guān)系。,例7.12,例7.12 設(shè)A1,2,3，R1，R2，R3是A上的關(guān)系，其中 R1, R2, R3 說(shuō)明R1，R2和R3是否為A上的傳遞關(guān)系。 解答 R1和R3是A上的傳遞關(guān)系， R2不是A上的傳遞關(guān)系。,關(guān)系性質(zhì)的等價(jià)描述,定理7.9 設(shè)R為A上的關(guān)系，則 （1）R

32、在A上自反當(dāng)且僅當(dāng) IA R （2）R在A上反自反當(dāng)且僅當(dāng) RIA （3）R在A上對(duì)稱當(dāng)且僅當(dāng) RR-1 （4）R在A上反對(duì)稱當(dāng)且僅當(dāng) RR-1 IA （5）R在A上傳遞當(dāng)且僅當(dāng) RRR,說(shuō)明,利用該定理可以從關(guān)系的集合表達(dá)式來(lái)判斷或證明關(guān)系的性質(zhì)。,定理7.9 (4)的證明,（4） R在A上反對(duì)稱當(dāng)且僅當(dāng) RR-1 IA 必要性。 任取，有 RR-1 R R-1 R R xy (R是反對(duì)稱的) IA 所以 RR-1 IA,充分性。 任取, 則有 R R R R-1 RR-1 IA (RR-1 IA) xy 所以 R在A上是反對(duì)稱的。,定理7.9 (5)的證明,（5） R在A上傳遞當(dāng)且僅當(dāng)

33、RRR 必要性。任取，有 RR t(RR) R (因?yàn)镽在A上是傳遞的) 所以 RRR。 充分性。任取,R，則 RR RR R (因?yàn)镽RR) 所以 R在A上是傳遞的。,例7.13,例7.13 設(shè)A是集合，R1和R2是A上的關(guān)系，證明： (1)若R1，R2是自反的和對(duì)稱的，則R1R2也是自反的和對(duì)稱的。 (2)若R1和R2是傳遞的，則R1R2也是傳遞的。,例7.13 (1)的證明,(1)若R1，R2是自反的和對(duì)稱的，則R1R2也是自反的和對(duì)稱的。,證明,由于R1和R2是A上的自反關(guān)系，故有 IA R1 和 IA R2 從而得到 IA R1R2。 根據(jù)定理7.9可知 R1R2在A上是自反的。

34、再由R1和R2的對(duì)稱性有 R1R1-1 和 R2R2-1 根據(jù)練習(xí)七第20題的結(jié)果有 (R1R2)-1R1-1R2-1R1R2 從而證明了R1R2也是A上對(duì)稱的關(guān)系。,例7.13 (2)的證明,(2)若R1和R2是傳遞的，則R1R2也是傳遞的。,證明,由R1和R2的傳遞性有 R1 R1 R1 和 R2 R2 R2 再使用定理7.4得 (R1R2)(R1R2) R1 R1R1 R2R2 R1R2 R2 (R1R2)(R1 R2R2 R1) (將前面的包含式代入) R1R2 從而證明了R1R2也是A上的傳遞關(guān)系。,關(guān)系性質(zhì)的特點(diǎn),例7.14,例7.14 判斷下圖中關(guān)系的性質(zhì)，并說(shuō)明理由。,（

35、1）對(duì)稱的，不是自反的，不是反自反的，不是反對(duì)稱的，不是傳遞的。 （2）是反自反的，不是自反的，是反對(duì)稱的，不是對(duì)稱的，是傳遞的。 （3）是自反的，不是反自反的，是反對(duì)稱的，不是對(duì)稱的，不是傳遞的。,關(guān)系的性質(zhì)和運(yùn)算之間的關(guān)系,閉包運(yùn)算,一般來(lái)說(shuō)，A上的關(guān)系不一定具有上面討論過的某些性質(zhì)，所以想到在給定的關(guān)系R的基礎(chǔ)上，擴(kuò)充一些序偶得到一個(gè)新的關(guān)系R，使新關(guān)系具有所要求的性質(zhì)，但又不希望它太大。因此，討論最小的包含R的R，使它具有所要求的性質(zhì)，這就是關(guān)系的閉包 。,問題,已知有如上的電話網(wǎng)絡(luò) 如何增加線路構(gòu)造任意兩地之間都能通信(可能不直接)的電話網(wǎng)絡(luò)，且構(gòu)造代價(jià)最低？ 構(gòu)造包含R的最小的傳遞

36、關(guān)系（ R的傳遞閉包）即可。,7.5 關(guān)系的閉包,閉包（closure）的定義 閉包的構(gòu)造方法 閉包的性質(zhì) 閉包的相互關(guān)系,讓世界充滿愛,閉包的定義,定義7.14 設(shè)R是非空集合A上的關(guān)系，R的自反（對(duì)稱或傳遞）閉包是A上的關(guān)系R，使得 R滿足以下條件： （1）R是自反的（對(duì)稱的或傳遞的） （2）RR （3）對(duì)A上任何包含R的自反（對(duì)稱或傳遞）關(guān)系R有R R。 一般將R的自反閉包記作r(R)，對(duì)稱閉包記作s(R)，傳遞閉包記作t(R)。,閉包的構(gòu)造方法,定理7.10 設(shè)R為A上的關(guān)系，則有 （1）r(R)RR0 （2）s(R)RR-1 （3）t(R)RR2R3 證明思路 (1)和(2)：證明右

37、邊的集合滿足閉包定義的三個(gè)條件。 (3)采用集合相等的證明方法。 證明左邊包含右邊，即t(R)包含每個(gè)Rn。 證明右邊包含左邊，即RR2具有傳遞的性質(zhì)。,定理7.10 (1)的證明,（1）r(R)RR0,證明,由IAR0 RR0，可知RR0是自反的， RRR0。 設(shè)R是A上包含R的自反關(guān)系， 則有RR和IAR。 任取，必有 RR0 RIA RRR 所以 RR0 R。 綜上所述，r(R)RR0。,定理7.10 (2)的證明,（2）s(R)RR-1,證明, RRR-1。,證明RR-1是對(duì)稱的， 任取，有 RR-1 RR-1 R-1R RR-1 所以 RR-1 是對(duì)稱的。,綜上所述，s(R

38、)RR-1。,設(shè)R是包含R的對(duì)稱關(guān)系， 任取，有 RR-1 RR-1 RR RR RR R 所以 RR-1 R。,定理7.10 (3)的證明,（3）t(R)RR2R3,證明,先證RR2 t(R)成立，為此只需證明對(duì)任意的正整數(shù)n有 Rn t(R)即可。用歸納法。 n1時(shí)，有 R1R t(R)。 假設(shè)Rnt(R)成立，那么對(duì)任意的有 Rn+1Rn R t(RnR) t(t(R)t(R)) t(R) （因?yàn)閠(R)是傳遞的） 這就證明了Rn+1 t(R)。 由歸納法命題得證。,定理7.10 (3)的證明,（3）t(R)RR2R3,證明,再證t(R)RR2成立，為此只須證明RR2

39、是傳遞的。 任取,，則 RR2 RR2 t(Rt) s(Rs) ts(Rt Rs) ts(Rt Rs) ts(Rt+s) RR2 從而證明了RR2是傳遞的。,為什么？,根據(jù)t(R)的定義，t(R)是任意一個(gè)包含R的傳遞的關(guān)系的子集。,推論,推論 設(shè)R為有窮集A上的關(guān)系，則存在正整數(shù)r使得 t(R)=RR2Rr 證明 由定理7.6和7.10(3)得證。 例題 求整數(shù)集合Z上的關(guān)系R | a|a|ab |ab s(R)RR-1|a|b|ab,通過關(guān)系矩陣求閉包的方法,設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系矩陣分別為M，Mr，Ms和Mt，則 Mr ME對(duì)角線上的值都改為1 Ms MM若a

40、ij1，則令aji1 Mt MM2M3沃舍爾算法 其中E是和M同階的單位矩陣，M是M的轉(zhuǎn)置矩陣。 注意在上述等式中矩陣的元素相加時(shí)使用邏輯加。,通過關(guān)系圖求閉包的方法,設(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的邊以外，以下述方法添加新的邊。 1)考察G的每個(gè)頂點(diǎn)，如果沒有環(huán)就加上一個(gè)環(huán)。最終得到的是Gr。 2)考察G的每一條邊，如果有一條xi到xj的單向邊，ij，則在G中加一條邊xj到xi的反方向邊。最終得到Gs。 3)考察G的每個(gè)頂點(diǎn)xi，找出從xi出發(fā)的所有2步，3步，，n步長(zhǎng)的路徑（n為G中的頂點(diǎn)數(shù)）

41、。 設(shè)路徑的終點(diǎn)為 。如果沒有從xi到 (l=1,2,,k)的邊，就加上這條邊。當(dāng)檢查完所有的頂點(diǎn)后就得到圖Gt。,例7.15,例7.15 設(shè)A=a,b,c,d，R=,,,,，則R和r(R)，s(R)，t(R)的關(guān)系圖如下圖所示。其中r(R)，s(R)，t(R)的關(guān)系圖就是使用上述方法直接從R的關(guān)系圖得到的。,Warshall 算法,自學(xué)。,閉包的主要性質(zhì),定理7.11 設(shè)R是非空集合A上的關(guān)系，則 （1）R是自反的當(dāng)且僅當(dāng)r(R)R。 （2）R是對(duì)稱的當(dāng)且僅當(dāng)s(R)R。 （3）R是傳遞的當(dāng)且僅當(dāng)t(R)R。 證明 （1）充分性。 因?yàn)镽r(R)，所以R是自反的。 必要性。 顯然有R

42、r(R)。 由于R是包含R的自反關(guān)系，根據(jù)自反閉包定義有r(R)R。 從而得到r(R)=R。,閉包的主要性質(zhì),定理7.12 設(shè)R1和R2是非空集合A上的關(guān)系，且R1 R2，則 （1）r(R1) r(R2) （2）s(R1) s(R2) （3）t(R1) t(R2) 證明：(1)任取，有 r(R1) R1IA R1 IA R2 IA R2IA r(R2),關(guān)系性質(zhì)與閉包運(yùn)算之間的聯(lián)系,定理7.13 設(shè)R是非空集合A上的關(guān)系， （1）若R是自反的，則s(R)與t(R)也是自反的。 （2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的。 （3）若R是傳遞的，則r(R)是傳遞的。 證明：只證（2）。,

43、定理7.13 (2)的證明,（2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的。 證明r(R)是對(duì)稱的。 由于R是A上的對(duì)稱關(guān)系，所以RR-1，同時(shí)IAIA-1。 r(R)-1(RR0)-1 (RIA)-1 R-1IA-1 RIA r(R) 所以，r(R)是對(duì)稱的。,定理7.13 (2)的證明,（2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的。 下面證明t(R)的對(duì)稱性。 任取 t(R) n(Rn) n(Rn) （因?yàn)镽n是對(duì)稱的，證明見課本） t(R) 所以，t(R)是對(duì)稱的。,課堂練習(xí),證明定理7.13的（3） 若R是傳遞的，則r(R)是傳遞的。 證明：根據(jù)傳遞性的充要條件，證明 r(

44、R) r(R) r(R) r(R) r(R) = (RIA) (RIA) = R R R IA IA R IA IA R R R IA = R IA = r(R),定理7.13的討論,從這里可以看出，如果計(jì)算關(guān)系R的自反、對(duì)稱、傳遞的閉包，為了不失去傳遞性，傳遞閉包運(yùn)算應(yīng)該放在對(duì)稱閉包運(yùn)算的后邊，若令tsr(R)表示R的自反、對(duì)稱、傳遞閉包，則 tsr(R)=t(s(r(R))),反例 A=1，2，3，R= 是傳遞的 s(R)=, 顯然s(R)不是傳遞的。,判定下列關(guān)系具有哪些性質(zhì),1、在全體中國(guó)人所組成的集合上定義的“同姓”關(guān)系； 2、對(duì)任何非空集合A，A上的全關(guān)系； 3、三角形的“相似

45、關(guān)系”、“全等關(guān)系”； 4、直線的“平行關(guān)系”； 5、“朋友”關(guān)系；,解：1，2，3都具有自反性，對(duì)稱性和傳遞性； 4 具有反自反性、對(duì)稱性、傳遞性，不具有自反性 5 具有對(duì)稱性，不具有自反性和傳遞性。,等價(jià)關(guān)系,7.6 等價(jià)關(guān)系與劃分,定義7.15 設(shè)R為非空集合上的關(guān)系。如果R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系(equivalent relation)。設(shè)R是一個(gè)等價(jià)關(guān)系，若R，稱x等價(jià)于y，記做xy。,1. 冪集上定義的“”關(guān)系； 2. 整數(shù)集上定義的“<”關(guān)系； 3. 全體中國(guó)人所組成的集合上定義的“同性別”關(guān)系。,判定下列關(guān)系是否是等價(jià)關(guān)系?,不具有對(duì)稱性,不具有對(duì)稱性

46、，自反性,是等價(jià)關(guān)系,例,在時(shí)鐘集合A1,,24上定義整除關(guān)系：R|x,yA)((x-y)被12所整除)。（1）寫出R中的所有元素；（2）畫出R的關(guān)系圖；（3）證明R是一個(gè)等價(jià)關(guān)系。,（2）此等價(jià)關(guān)系的關(guān)系圖：,（1）R=, , , , , , , ,, , , ,,,,,,,1,13,,,,,,,,2,14,,,,,,,3,15,,,,,,,12,24,（3）等價(jià)關(guān)系的證明： 1、對(duì)xA，有(x-x)被12所整除，所以R，即R是自反的。 2、對(duì)x,yA,若R,有(x-y)被12整除，則(y-x)-(x-y)被12整除,所以,R,即R是對(duì)稱的。 3、對(duì)x,y,zA,若R且R,有(x-y)被12

47、所整除且(y-z)被12所整除,所以(x-z)(x-y)(y-z)被12所整除,所以,R,即R是傳遞的. 由1,2,3知R是等價(jià)關(guān)系。,從本例可以看出,關(guān)系R將集合A分成了如下的12個(gè)子集： 1, 13, 2,14, 3,15, 4,16, 5,17, 6, 18, 7,19, 8,20, 9,21, 10,22, 11,23, 12,24。,這12個(gè)A的子集具有如下特點(diǎn)： 1、在同一個(gè)子集中的元素之間都有關(guān)系R； 2、不同子集的元素之間無(wú)關(guān)系R。,等價(jià)類,定義7.16 設(shè)R為非空集合A上的等價(jià)關(guān)系，xA，令 xR=y|yAxRy稱xR為x關(guān)于R的等價(jià)類，簡(jiǎn)稱為x的等價(jià)類，簡(jiǎn)記為x或 x 。,

48、,x的等價(jià)類是A中所有與x等價(jià)的元素構(gòu)成的集合。 前例中的等價(jià)類是： 1131,132142,14 3153,154164,16 ,整數(shù)集合Z上的模n等價(jià)關(guān)系,設(shè)x是任意整數(shù)，n為給定的正整數(shù)，則存在唯一的整數(shù)q和r，使得xqn+r其中0rn-1，稱r為x除以n的余數(shù)。 例如n3，那么8除以3的余數(shù)為1，因?yàn)?-8-33+1 對(duì)于任意的整數(shù)x和y，定義模n相等關(guān)系xy xy(mod n) 不難驗(yàn)證它是整數(shù)集合Z上的等價(jià)關(guān)系。 將Z中的所有整數(shù)根據(jù)它們除以n的余數(shù)分類如下： 余數(shù)為0的數(shù)，其形式為nz，zZ余數(shù)為1的數(shù)，其形式為nz+1，zZ 余數(shù)是n-1的數(shù)，其形式為nz+n-1，zZ 以上構(gòu)

49、成了n個(gè)等價(jià)類，使用等價(jià)類的符號(hào)可記為inz+i|zZ，i=0，1，，n-1,等價(jià)類的性質(zhì),定理7.14 設(shè)R是非空集合A上的等價(jià)關(guān)系，則 （1）xA，x是A的非空子集。 （2）x,yA，如果xRy，則xy。 （3）x,yA，如果R，則x與y不交。 （4）x|xAA。 證明（1） 由等價(jià)類的定義可知， xA有xA。 又由于等價(jià)關(guān)系的自反性有xx，即x非空。,定理7.14,（2）x,yA，如果xRy，則x=y。 任取z，則有 zx R R(因?yàn)镽是對(duì)稱的) R R R (因?yàn)镽是傳遞的) R (因?yàn)镽是對(duì)稱的) zy。 所以 xy。 同理可證 yx。 因此，x=y。,定理7.14,（3）x,yA

50、，如果R，則x與y不交。 假設(shè) xy ， 則存在 zxy， 從而有 zxzy， 即RR成立。 根據(jù)R的對(duì)稱性和傳遞性，必有R，與R矛盾， 即假設(shè)錯(cuò)誤，原命題成立。,定理7.14,（4）x|xAA。 先證 x|xAA 任取y，yx|xA x(xAyx) yA (因?yàn)閤A) 從而有x|xA A。 再證 Ax|xA 任取y，yA yyyA yx|xA 從而有Ax|xA成立。 綜上所述得 x|xAA。,商集,定義7.17 設(shè)R為非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集(quotient set)，記做A/R，即 A/R=xR|xA 例7.16中的商集為 1,4

51、,7,2,5,8,3,6 整數(shù)集合Z上模n等價(jià)關(guān)系的商集是 nz+i|zZ|i=0,1,,n-1,計(jì)算商集A/R的通用過程：,（1）任選A中一個(gè)元素a，計(jì)算aR； （2）如果aRA，任選一個(gè)元素bA-aR，計(jì)算bR； （3）如果aRbRA，任選一個(gè)元素cA-aR-bR，計(jì)算cR； 以此類推，直到A中所有元素都包含在計(jì)算出的等價(jià)類中。,劃分,定義7.18 設(shè)A為非空集合，若A的子集族(P(A)，是A的子集構(gòu)成的集合) 滿足下面的條件： （1） （2）xy(x,yxyxy) （3）=A 則稱是A的一個(gè)劃分(partition)，稱中的元素為A的劃分塊。,說(shuō)明,設(shè)集合是A的非空子集的集合，若這些非空

52、子集兩兩不相交，且它們的并等于A，則稱是集合A的劃分。,試給出非空集合A上2個(gè)不同的劃分 解（1）在A中設(shè)定一個(gè)非空子集A1，令A(yù)2=A-A1，則根據(jù)集合劃分的定義，A1,A2就構(gòu)成了集合A的一個(gè)劃分，見圖 (a)； （2）在A中設(shè)定兩個(gè)不相交非空子集A1和A2，令A(yù)3=A-(A1A2)，則根據(jù)集合劃分的定義，A1,A2,A3就構(gòu)成了集合A的一個(gè)劃分，見圖 (b)。,,例7.17,例7.17 設(shè)Aa,b,c,d，給定1,2,3,4,5,6,如下： 1=a,b,c,d 2=a,b,c,d 3=a,a,b,c,d 4=a,b,c 5=,a,b,c,d 6=a,a,b,c,d判斷哪一個(gè)是A的劃分 1

53、和2是A的劃分，其它都不是A的劃分。 因?yàn)?中的子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A的子集族。,商集與劃分,商集就是A的一個(gè)劃分，并且不同的商集將對(duì)應(yīng)于不同的劃分。 反之，任給A的一個(gè)劃分，如下定義A上的關(guān)系R： R=|x,yAx與y在的同一劃分塊中 則不難證明R為A上的等價(jià)關(guān)系，且該等價(jià)關(guān)系所確定的商集就是。 由此可見，A上的等價(jià)關(guān)系與A的劃分是一一對(duì)應(yīng)的。,例7.18,例7.18 給出A1,2,3上所有的等價(jià)關(guān)系,這些劃分與A上的等價(jià)關(guān)系之間的一一對(duì)應(yīng)是：1對(duì)應(yīng)于全域關(guān)系EA，5的對(duì)應(yīng)于恒等關(guān)系IA，2，3和4分別對(duì)應(yīng)于等價(jià)關(guān)系R2，R3和R4。 其中 R2=,

54、IA R3=,IA R4=,IA,例題,例題 問集合Aa,b,c,d上有多少個(gè)不同的等價(jià)關(guān)系？ 解答 只要求出A上的全部劃分，即為等價(jià)關(guān)系。 劃分為一個(gè)塊的情況：1種，即a,b,c,d 劃分為兩個(gè)塊的情況：7種，即 a,b,c,d，a,c,b,d，a,d,b,c a,b,c,d，b,a,c,d，c,a,b,d，d,a,b,c 劃分為三個(gè)塊的情況：6種，即 a,b,c,d，a,c,b,d，a,d,b,c, a,b,c,d，a,c,b,d，a,d,b,c 劃分為四個(gè)塊的情況：1種，即a,b,c,d 因此，共有15種不同的等價(jià)關(guān)系。,7.7 偏序(partial order)關(guān)系,定義7.19 設(shè)R

55、為非空集合A上的關(guān)系。如果R是自反的、反對(duì)稱的和傳遞的，則稱R為A上的偏序關(guān)系，記作。 設(shè)為偏序關(guān)系，如果，則記作xy，讀作“x小于或等于y”。 注意 這里的“小于或等于”不是指數(shù)的大小，而是在偏序關(guān)系中的順序性。x“小于或等于”y的含義是：依照這個(gè)序，x排在y的前邊或者x就是y。根據(jù)不同偏序的定義，對(duì)序有著不同的解釋。 偏序關(guān)系舉例 集合A上的恒等關(guān)系IA小于或等于關(guān)系整除關(guān)系,等價(jià)關(guān)系 人人平等 偏序關(guān)系天尊地卑，乾坤定矣；卑高以陳，貴賤位矣,可比,定義7.20 設(shè)R為非空集合A上的偏序關(guān)系，定義 (1) x,yA，xy xyxy。 (2) x,yA，x與y可比 xyyx。 其中xy讀作x

56、“小于”y。這里所說(shuō)的“小于”是指在偏序中x排在y的前邊。 在具有偏序關(guān)系的集合A中任取兩個(gè)元素x和y，可能有下述幾種情況發(fā)生： xy(或yx)，xy，x與y不是可比的。 例如A1，2，3，是A上的整除關(guān)系，則有 12，13， 1=1，2=2，3=3， 2和3不可比。,全序關(guān)系,定義7.21 設(shè)R為非空集合A上的偏序關(guān)系，如果x,yA，x與y都是可比的，則稱R為A上的全序關(guān)系(或線序關(guān)系)。 例如 數(shù)集上的小于或等于關(guān)系是全序關(guān)系，因?yàn)槿魏蝺蓚€(gè)數(shù)總是可比大小的。 整除關(guān)系一般來(lái)說(shuō)不是全序關(guān)系，如集合1,2,3上的整除關(guān)系就不是全序關(guān)系，因?yàn)?和3不可比。,擬序關(guān)系選讀,設(shè)R是集合A上的一

57、個(gè)關(guān)系。如果R具有反自反性，傳遞性，則稱R為一個(gè)擬序關(guān)系。記為，讀做“小于”。 注意，擬序關(guān)系的定義中隱含了其具有反對(duì)稱性。 例：數(shù)間的小于（“”）關(guān)系；集合間的真包含（“”）關(guān)系。,擬序關(guān)系是反對(duì)稱的,求證：R是非空集合A上的擬序關(guān)系，則R是反對(duì)稱的。 證明： 若R= ，則R是反自反的、傳遞的，而且是反對(duì)稱的； 若R不是空集，則有xRy, 而且xy，否則與R是反自反的矛盾; 假設(shè)有yRx，則由R是傳遞的，有xRx，與R是反自反的矛盾；故而對(duì)任意xRy都沒有yRx，所以R是反對(duì)稱的。,偏序集,定義7.22 集合A和A上的偏序關(guān)系一起叫做偏序集，記作。 例如 整數(shù)集合Z和數(shù)的小于或等于關(guān)系構(gòu)成偏

58、序集 集合A的冪集P(A)和包含關(guān)系R構(gòu)成偏序集。,覆蓋(cover),定義7.23 設(shè)為偏序集。 x,yA，如果 xy 且不存在 zA使得xzy，則稱y覆蓋x。 例如 1,2,4,6集合上的整除關(guān)系， 有2覆蓋1，4和6都覆蓋2。但4不覆蓋1，因?yàn)橛?24。6也不覆蓋4，因?yàn)?6不成立。,哈斯圖(Hasse diagram),利用偏序關(guān)系的自反性、反對(duì)稱性和傳遞性所得到的此偏序關(guān)系的簡(jiǎn)化的關(guān)系圖，稱為哈斯圖。 畫偏序集的哈斯圖的方法,（1）用小圓圈或點(diǎn)表示A中的元素，省掉關(guān)系圖中所有的環(huán)； （因自反性) （2）對(duì)任意x,yA，若xy，則將x畫在y的下方，可省掉關(guān)系圖中所有邊的箭頭；

59、（因反對(duì)稱性） （3）對(duì)任意x,yA，若y覆蓋x，則x與y之間用一條線相連，否則無(wú)線相連。（因傳遞性）,例,設(shè)A=2,3,6,12,24,36，“”是A上的整除關(guān)系R，畫出其一般的關(guān)系圖和哈斯圖。 解 由題意可得 R=,,,,,,,,,,,,,,,,,,， 從而得出該偏序集的一般關(guān)系圖和哈斯圖如下：,關(guān)系圖,哈斯圖,,,,,,,,,,,,2,3,6,12,36,24,,,,,,,2,3,6,12,36,24,,,,,,,,,,,,,,,,,,,,例7.19,例7.19 畫出偏序集和的哈斯圖。,a,例7.20,例7.20 已知偏序集的哈斯圖如右圖所示，試求出集合A和關(guān)系R的表達(dá)式。,解答 A=a

60、,b,c,d,e,f,g,h R=,,,,,,,,IA,偏序集中的特殊元素,定義7.24 設(shè)為偏序集，BA，yB。 （1）若x(xByx)成立，則稱y為B的最小元。 （2）若x(xBxy)成立，則稱y為B的最大元。 （3）若x(xBxyxy)成立，則稱y為B的極小元。 （4）若x(xByxxy)成立，則稱y為B的極大元。,無(wú) 無(wú) 24,26 2,3,12 6 12 6,6 無(wú) 6 2,3,6 6 6 6,特殊元素的性質(zhì),最小元是B中最小的元素，它與B中其它元素都可比。 極小元不一定與B中元素可比，只要沒有比它小的元素，它就是極小元。 對(duì)于有窮集B，極小元一定存在，但

61、最小元不一定存在。最小元如果存在，一定是唯一的。 極小元可能有多個(gè)，但不同的極小元之間是不可比的（無(wú)關(guān)系）。 如果B中只有一個(gè)極小元，則它一定是B的最小元。 哈斯圖中，集合B的極小元是B中各元素中的最底層。,例7.21,例7.21 設(shè)偏序集如右圖所示，求A的極小元、最小元、極大元、最大元。,解答 極小元：a,b,c,g 極大元：a,f,h。 沒有最小元與最大元,說(shuō)明,哈斯圖中的孤立頂點(diǎn)既是極小元也是極大元。,例7.22,例7.22 設(shè)X為集合，AP(X)X，且A。若|X|n，問：（1）偏序集是否存在最大元？（2）偏序集是否存在最小元？（3）偏序集中極大元和極小元的一般形式是什么？并說(shuō)明理由。

62、解答 不存在最小元和最大元。原因如下： 因?yàn)锳 ，所以n2?？疾靸缂疨(X)的哈斯圖，最底層的頂點(diǎn)是空集，記作第0層。由底向上，第1層是單元集，第2層是二元子集，由|X|=n，則第n1層是X的n1元子集，第n層，也就是最高層只有一個(gè)頂點(diǎn)X。偏序集與相比，恰好缺少第0層與第n層(因?yàn)閄是n元集)。因此的極小元就是X的所有單元集，即x，xX；而極大元恰好少一個(gè)元素，即X-x，xX。,上界、下界,定義7.25 設(shè)為偏序集，BA，yA。 （1）若 x(xBxy)成立，則稱y為B的上界。 （2）若 x(xByx)成立，則稱y為B的下界。 （3）令Cy|y為B的上界，則稱C的最小元為B的最小上界或上確界。

63、 （4）令Dy|y為B的下界，則稱D的最大元為B的最大下界或下確界。,上界與下界舉例,無(wú) 無(wú) 無(wú) 無(wú),12,24,36 2,3,6 12 6,6,12,24,36 無(wú) 6 無(wú),6,12,24,36 2,3,6 6 6,考慮右圖中的偏序集。令Bb，c，d，則B的下界和最大下界都不存在，上界有d和f，最小上界為d。,討論,最大元，最小元未必存在，如果存在必唯一。,討論,極大元，極小元對(duì)有限偏序集必存在，但未必唯一。,討論,上下界未必存在，存在時(shí)又未必唯一。,,,討論,即使有上下界時(shí)，最小上界和最大下界也未必存在。,,,,,,,,,a, b, c, d,a, b, c, e,a

64、,b,,,上界與下界的性質(zhì),B的最小元一定是B的下界，同時(shí)也是B的最大下界。 B的最大元一定是B的上界，同時(shí)也是B的最小上界。 B的下界不一定是B的最小元，因?yàn)樗赡懿皇荁中的元素。 B的上界也不一定是B的最大元。 B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界與最大下界是唯一的。,偏序關(guān)系的實(shí)例調(diào)度問題,給定有窮的任務(wù)集T和m臺(tái)相同的機(jī)器，T上存在偏序關(guān)系， 如果t1

65、個(gè)調(diào)度方案， 其中 f(t)表示任務(wù)t的開始時(shí)間。 D表示完成所有任務(wù)的最終時(shí)間。,偏序關(guān)系的實(shí)例調(diào)度問題,假設(shè)每項(xiàng)任務(wù)都可以安排在任何一臺(tái)機(jī)器上進(jìn)行工作， 如果f滿足下述三個(gè)條件，則稱T為可行調(diào)度。 (1)tT，f(t)+l(t)d(t)（表示每項(xiàng)任務(wù)都要在截至?xí)r間內(nèi)完成） (2)i，0iD，|tT:f(t)if(t)+l(t)|m（表示任何時(shí)刻同時(shí)工作的機(jī)器臺(tái)數(shù)不超過m） (3)t,tT,ttf(t)+l(t)f(t)（表示任務(wù)安排必須滿足任務(wù)集的偏序約束） 求使得D最小的可行調(diào)度。,例7.23,設(shè)m2，Tt1,t2,,t6，每項(xiàng)任務(wù)的截止時(shí)間都等于7。去掉自反成分，T的偏序約束如右圖所示

66、。每個(gè)任務(wù)結(jié)點(diǎn)中的數(shù)字表示完成該任務(wù)所有的時(shí)間。,下圖中給出了兩個(gè)可行的調(diào)度方案。,D6,D5,本章主要內(nèi)容,有序?qū)εc卡氏積 二元關(guān)系（包括空關(guān)系，恒等關(guān)系，全域關(guān)系等）及其表示（關(guān)系矩陣，關(guān)系圖） 關(guān)系的五種性質(zhì)（自反性，反自反性，對(duì)稱性，反對(duì)稱性，傳遞性） 二元關(guān)系的冪運(yùn)算 關(guān)系的三種閉包（自反閉包，對(duì)稱閉包，傳遞閉包） 等價(jià)關(guān)系和劃分（包括等價(jià)類，商集，劃分塊等） 偏序關(guān)系（包括哈斯圖，最大元，最小元，極大元，極小元，上界，下界，最小上界，最大下界等）,本章學(xué)習(xí)要求,掌握：有序?qū)翱ㄊ戏e的概念及卡氏積的性質(zhì) 掌握：二元關(guān)系，A到B的二元關(guān)系，A上的二元關(guān)系，關(guān)系的定義域和值域，關(guān)系的逆，關(guān)系的合成，關(guān)系在集合上的限制，集合在關(guān)系下的象等概念，掌握關(guān)系的定義域、值域、逆、合成、限制、象等的主要性質(zhì) 掌握：關(guān)系矩陣與關(guān)系圖的概念及求法 掌握：集合A上的二元關(guān)系的主要性質(zhì)（自反性，反自反性，對(duì)稱性，反對(duì)稱性，傳遞性）的定義及判別法，對(duì)某些關(guān)系證明它們有或沒有中的性質(zhì),本章學(xué)習(xí)要求,掌握：A上二元關(guān)系的n次冪的定義及主要性質(zhì) 掌握A上二元關(guān)系的自反閉包、對(duì)稱閉包、傳遞閉包的定義及求法 掌