數理邏輯二元關系.ppt

《數理邏輯二元關系.ppt》由會員分享，可在線閱讀，更多相關《數理邏輯二元關系.ppt（148頁珍藏版）》請在裝配圖網上搜索。

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

2、爾集 二元關系的定義和表示法 關系的運算 關系的性質 關系的閉包 等價關系與劃分 偏序關系 本章與后續(xù)各章的關系 本章是函數的基礎 本章是圖論的基礎,7.1 有序對與笛卡爾積,定義7.1 由兩個元素x和y按一定順序排列成的二元組叫做一個有序對(ordered pair)或序偶，記作，其中x是它的第一元素，y是它的第二元素。 有序對具有以下性質： （1）當xy時，。 （2）的充分必要條件是xu且yv。,說明,有序對中的元素是有序的 集合中的元素是無序的,定義7.2 設A，B為集合,以A中元素為第一元素，B中元素為第二元素構成有序對，所有這樣的有序對組成的集合叫做A和B的笛卡爾積(Cartesia

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

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

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

6、算不滿足交換律,AB=當且僅當A=或者B=,（3）因為BD=,,,， 所以A(BD)=,, ,。 同理，(AB)D=,1,,2, ,1,,2。,笛卡爾積運算不滿足結合律,對有限集A,B，有|AB|=|BA|=|A||B|,,笛卡爾積的運算性質,(1)對任意集合A，根據定義有 A, A (2)一般的說，笛卡爾積運算不滿足交換律，即 ABBA (當 A B AB 時) (3)笛卡爾積運算不滿足結合律，即 (AB)CA(BC)(當 A B C 時) (4)笛卡爾積運算對并和交運算滿足分配律，即 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),關于ACBD ABCD的討論,該性質的逆命題不成立，可分以下情況討論。 （1）當A=B=時，顯然有AC 和 BD 成立。 （2）當A且B時，也有AC和BD成立，證明如下： 任取xA，由于B,必存在yB,因此有 xAyB AB，又因為 ABCD CD xCyD xC 從而證明了 AC。 同理可證 BD。,關于ACBD ABCD的討論,（3）當A而B時，有AC成立，但不一定有BD

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

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

10、2， AA的子集就有 個。 每一個子集代表一個A上的二元關系，所以A上有 個不同的二元關系。 例如|A|=3，則A上有 個不同的二元關系。,7.2 二元關系,定義7.4 設A，B為集合，AB的任何子集所定義的二元關系叫做從A到B的二元關系；特別當A=B時，則叫做A上的二元關系。,A=0,1，B=1,2,3，那么 R1=，R2=AB，R3= ，R4= 等都是從A到B的二元關系，而R3和R4同時也是A上的二元關系。,舉例,說明,常用的關系,定義7.5 對任意集合A，定義 全域關系 EA=|xAyA=AA 恒等關系 IA=|xA 空關系 ,設 A=1,2，那么 EA=,,, IA=,,舉例,其它常

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

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

13、)R中所有有序對的第一元素構成的集合稱為R的定義域(domain)，記為dom R。形式化表示為：dom R x | y(R ) (2)R中所有有序對的第二元素構成的集合稱為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,關系的逆,定義7.7 設R為二元關系，R的逆關系，簡稱R的逆(inverse)，記作R-1,其中 R-1|R

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

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

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

17、R2由所有的有序對構成，其中課程b是a的必修課。則關系R1R2、R1R2、R1R2、R1R2、R2R1的含義為 R1R2：a是一個學生，他或者選修了課程b，或者課程b是他的必修課。 R1R2：a是一個學生，他選修了課程b并且課程b也是a的必修課。 R1R2：學生a已經選修了課程b，但課程b不是a的選修課，或者課程b是a的必修課，但是a沒有選修它。 R1R2：學生a已經選修了課程b，但課程b不是a的選修課。 R2R1：課程b是學生a的必修課，但是a沒有選修它。,課堂練習題,設A表示工人的集合,B表示工作的集合. 設R1 表示A到B的二元關系: R1=(a,b)aA,bB, a分配去做工作b.

18、設R2表示A到A的二元關系: R2=(a1,a2)a1,a2A,a1和a2不能友好相處. 請你用R1和R2表示關系 R,使得xRy表示 x,y分配去做 同樣工作且能友好相處.,解答：因為R1是A到B的二元關系,故R1-1表示B到A的二元關系, 則R1R1-1表示從A到A的二元關系,即由分配做同一樣工作的兩個人構成的序偶的全體.因此R=R1R1-1-R2,定理7.1,定理7.1 設F是任意的關系，則 (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 設F，G，H是任意的關系，則 (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 設F，G，H是任意的關系，則 (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 設R為A上的關系，則 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 設F，G，H是任意的關系，則(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的推論,由數學歸納法不難證明定理7.4的結論對于有限多個關系的并和交也是成立的，即有 R(R1R2Rn)RR1RR2

21、RRn R1R2Rn)RR1RR2RRnR R(R1R2Rn)RR1RR2RRn R1R2Rn)RR1RR2RRnR,定理7.5,定理7.5 設F為關系，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,關系的冪運算,定義7.10 設R為A上的關系，n為自然數，則R的n次冪定義為： （1） R0|xAIA （2） Rn+1Rn R,說明,對于A上的任何關系R1和R2都有 R10R20IA 即：A上任何關系的0次冪都相等，都等于A上的恒等關系IA。 對于A上的任何關系R都有R1R，因為 R1R0 RIA RR,Rn的計算,給定A上的關系R和自然數n，怎樣計算Rn呢？ 若n是0或1，結果是很簡單的。下面考慮n2的情況。 如果R是用集合表達式給出的，可以通過n-1次復合計算得到Rn。 如果R是用關系矩陣M給出的，則

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

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

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

26、Rt，則 (1) 對任何kN有 Rs+k=Rt+k (2) 對任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s (3) 令S=R0，R1，，Rt-1，則對于任意的qN有 RqS,證明,(1) Rs+kRs RkRt RkRt+k (2)對k歸納。 若k=0，則有 Rs+0 p+iRs+i 假設 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 設R是A上的關系，若存在自然數s,t(s

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

28、數m和n，使得m

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

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

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

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

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

34、再由R1和R2的對稱性有 R1R1-1 和 R2R2-1 根據練習七第20題的結果有 (R1R2)-1R1-1R2-1R1R2 從而證明了R1R2也是A上對稱的關系。,例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上的傳遞關系。,關系性質的特點,例7.14,例7.14 判斷下圖中關系的性質，并說明理由。,（

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

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

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

38、)RR-1。,設R是包含R的對稱關系， 任取，有 RR-1 RR-1 RR RR RR R 所以 RR-1 R。,定理7.10 (3)的證明,（3）t(R)RR2R3,證明,先證RR2 t(R)成立，為此只需證明對任意的正整數n有 Rn t(R)即可。用歸納法。 n1時，有 R1R t(R)。 假設Rnt(R)成立，那么對任意的有 Rn+1Rn R t(RnR) t(t(R)t(R)) t(R) （因為t(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是傳遞的。,為什么？,根據t(R)的定義，t(R)是任意一個包含R的傳遞的關系的子集。,推論,推論 設R為有窮集A上的關系，則存在正整數r使得 t(R)=RR2Rr 證明 由定理7.6和7.10(3)得證。 例題 求整數集合Z上的關系R | a|a|ab |ab s(R)RR-1|a|b|ab,通過關系矩陣求閉包的方法,設關系R，r(R)，s(R)，t(R)的關系矩陣分別為M，Mr，Ms和Mt，則 Mr ME對角線上的值都改為1 Ms MM若a

40、ij1，則令aji1 Mt MM2M3沃舍爾算法 其中E是和M同階的單位矩陣，M是M的轉置矩陣。 注意在上述等式中矩陣的元素相加時使用邏輯加。,通過關系圖求閉包的方法,設關系R，r(R)，s(R)，t(R)的關系圖分別記為G，Gr，Gs，Gt，則Gr，Gs，Gt的頂點集與G的頂點集相等。 除了G的邊以外，以下述方法添加新的邊。 1)考察G的每個頂點，如果沒有環(huán)就加上一個環(huán)。最終得到的是Gr。 2)考察G的每一條邊，如果有一條xi到xj的單向邊，ij，則在G中加一條邊xj到xi的反方向邊。最終得到Gs。 3)考察G的每個頂點xi，找出從xi出發(fā)的所有2步，3步，，n步長的路徑（n為G中的頂點數）

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

42、r(R)。 由于R是包含R的自反關系，根據自反閉包定義有r(R)R。 從而得到r(R)=R。,閉包的主要性質,定理7.12 設R1和R2是非空集合A上的關系，且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),關系性質與閉包運算之間的聯系,定理7.13 設R是非空集合A上的關系， （1）若R是自反的，則s(R)與t(R)也是自反的。 （2）若R是對稱的，則r(R)與t(R)也是對稱的。 （3）若R是傳遞的，則r(R)是傳遞的。 證明：只證（2）。,

43、定理7.13 (2)的證明,（2）若R是對稱的，則r(R)與t(R)也是對稱的。 證明r(R)是對稱的。 由于R是A上的對稱關系，所以RR-1，同時IAIA-1。 r(R)-1(RR0)-1 (RIA)-1 R-1IA-1 RIA r(R) 所以，r(R)是對稱的。,定理7.13 (2)的證明,（2）若R是對稱的，則r(R)與t(R)也是對稱的。 下面證明t(R)的對稱性。 任取 t(R) n(Rn) n(Rn) （因為Rn是對稱的，證明見課本） t(R) 所以，t(R)是對稱的。,課堂練習,證明定理7.13的（3） 若R是傳遞的，則r(R)是傳遞的。 證明：根據傳遞性的充要條件，證明 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的討論,從這里可以看出，如果計算關系R的自反、對稱、傳遞的閉包，為了不失去傳遞性，傳遞閉包運算應該放在對稱閉包運算的后邊，若令tsr(R)表示R的自反、對稱、傳遞閉包，則 tsr(R)=t(s(r(R))),反例 A=1，2，3，R= 是傳遞的 s(R)=, 顯然s(R)不是傳遞的。,判定下列關系具有哪些性質,1、在全體中國人所組成的集合上定義的“同姓”關系； 2、對任何非空集合A，A上的全關系； 3、三角形的“相似

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

46、，自反性,是等價關系,例,在時鐘集合A1,,24上定義整除關系：R|x,yA)((x-y)被12所整除)。（1）寫出R中的所有元素；（2）畫出R的關系圖；（3）證明R是一個等價關系。,（2）此等價關系的關系圖：,（1）R=, , , , , , , ,, , , ,,,,,,,1,13,,,,,,,,2,14,,,,,,,3,15,,,,,,,12,24,（3）等價關系的證明： 1、對xA，有(x-x)被12所整除，所以R，即R是自反的。 2、對x,yA,若R,有(x-y)被12整除，則(y-x)-(x-y)被12整除,所以,R,即R是對稱的。 3、對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是等價關系。,從本例可以看出,關系R將集合A分成了如下的12個子集： 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個A的子集具有如下特點： 1、在同一個子集中的元素之間都有關系R； 2、不同子集的元素之間無關系R。,等價類,定義7.16 設R為非空集合A上的等價關系，xA，令 xR=y|yAxRy稱xR為x關于R的等價類，簡稱為x的等價類，簡記為x或 x 。,

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

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

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

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

52、子集兩兩不相交，且它們的并等于A，則稱是集合A的劃分。,試給出非空集合A上2個不同的劃分 解（1）在A中設定一個非空子集A1，令A2=A-A1，則根據集合劃分的定義，A1,A2就構成了集合A的一個劃分，見圖 (a)； （2）在A中設定兩個不相交非空子集A1和A2，令A3=A-(A1A2)，則根據集合劃分的定義，A1,A2,A3就構成了集合A的一個劃分，見圖 (b)。,,例7.17,例7.17 設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判斷哪一個是A的劃分 1

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

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

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

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

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

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

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

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

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

62、解答 不存在最小元和最大元。原因如下： 因為A ，所以n2?？疾靸缂疨(X)的哈斯圖，最底層的頂點是空集，記作第0層。由底向上，第1層是單元集，第2層是二元子集，由|X|=n，則第n1層是X的n1元子集，第n層，也就是最高層只有一個頂點X。偏序集與相比，恰好缺少第0層與第n層(因為X是n元集)。因此的極小元就是X的所有單元集，即x，xX；而極大元恰好少一個元素，即X-x，xX。,上界、下界,定義7.25 設為偏序集，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的最大下界或下確界。,上界與下界舉例,無 無 無 無,12,24,36 2,3,6 12 6,6,12,24,36 無 6 無,6,12,24,36 2,3,6 6 6,考慮右圖中的偏序集。令Bb，c，d，則B的下界和最大下界都不存在，上界有d和f，最小上界為d。,討論,最大元，最小元未必存在，如果存在必唯一。,討論,極大元，極小元對有限偏序集必存在，但未必唯一。,討論,上下界未必存在，存在時又未必唯一。,,,討論,即使有上下界時，最小上界和最大下界也未必存在。,,,,,,,,,a, b, c, d,a, b, c, e,a

64、,b,,,上界與下界的性質,B的最小元一定是B的下界，同時也是B的最大下界。 B的最大元一定是B的上界，同時也是B的最小上界。 B的下界不一定是B的最小元，因為它可能不是B中的元素。 B的上界也不一定是B的最大元。 B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界與最大下界是唯一的。,偏序關系的實例調度問題,給定有窮的任務集T和m臺相同的機器，T上存在偏序關系， 如果t1

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

66、。每個任務結點中的數字表示完成該任務所有的時間。,下圖中給出了兩個可行的調度方案。,D6,D5,本章主要內容,有序對與卡氏積 二元關系（包括空關系，恒等關系，全域關系等）及其表示（關系矩陣，關系圖） 關系的五種性質（自反性，反自反性，對稱性，反對稱性，傳遞性） 二元關系的冪運算 關系的三種閉包（自反閉包，對稱閉包，傳遞閉包） 等價關系和劃分（包括等價類，商集，劃分塊等） 偏序關系（包括哈斯圖，最大元，最小元，極大元，極小元，上界，下界，最小上界，最大下界等）,本章學習要求,掌握：有序對及卡氏積的概念及卡氏積的性質 掌握：二元關系，A到B的二元關系，A上的二元關系，關系的定義域和值域，關系的逆，關系的合成，關系在集合上的限制，集合在關系下的象等概念，掌握關系的定義域、值域、逆、合成、限制、象等的主要性質 掌握：關系矩陣與關系圖的概念及求法 掌握：集合A上的二元關系的主要性質（自反性，反自反性，對稱性，反對稱性，傳遞性）的定義及判別法，對某些關系證明它們有或沒有中的性質,本章學習要求,掌握：A上二元關系的n次冪的定義及主要性質 掌握A上二元關系的自反閉包、對稱閉包、傳遞閉包的定義及求法 掌