第3章集合與關(guān)系

1、第三章集合與關(guān)系第三章集合與關(guān)系 集合的概念和表示法集合的概念和表示法 集合的運算集合的運算 序偶與笛卡爾積序偶與笛卡爾積 關(guān)系及其表示關(guān)系及其表示 關(guān)系的性質(zhì)關(guān)系的性質(zhì) 復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系 關(guān)系的閉包運算關(guān)系的閉包運算 等價關(guān)系與等價類等價關(guān)系與等價類 序關(guān)系序關(guān)系3-1集合的概念和表示法集合的概念和表示法 集合是一基本概念，廣泛用于數(shù)學(xué)、計算機(jī)科學(xué)等領(lǐng)域，如集合是一基本概念，廣泛用于數(shù)學(xué)、計算機(jī)科學(xué)等領(lǐng)域，如程序設(shè)計語言，數(shù)據(jù)結(jié)構(gòu)等。程序設(shè)計語言，數(shù)據(jù)結(jié)構(gòu)等。 集合是數(shù)學(xué)中的基本概念，無法定義，只做說明：集合是數(shù)學(xué)中的基本概念，無法定義，只做說明：1. 我們把具有相同性質(zhì)的不

2、同對象的全體稱為我們把具有相同性質(zhì)的不同對象的全體稱為集合集合，這些對，這些對象稱為象稱為元素元素。通常用大寫字母。通常用大寫字母A,B,C,D表示集合，小寫字表示集合，小寫字母母a,b,c,d表示元素。對集合有幾點說明：表示元素。對集合有幾點說明：（1） 任一對象任一對象a，對某一集合，對某一集合A來說，來說，a屬于屬于A或或a不屬于不屬于A，兩者必居其一，且僅居其一。并且當(dāng)兩者必居其一，且僅居其一。并且當(dāng)a屬于屬于A時，稱時，稱a是是A的成的成員，或員，或A包含包含a，a在在A之中，之中，a屬于屬于A。即。即（2）集合中）集合中元素元素具有互異性和無序性。如具有互異性和無序性。如a,b,c

3、,d=a,b,b,c,daAaA(3) 集合的元素個數(shù)可以是集合的元素個數(shù)可以是有限個有限個也可以是也可以是無限個無限個，具有有限個元素的集，具有有限個元素的集合的為有限集，否則稱為無限集。合的為有限集，否則稱為無限集。2. 集合的表示法集合的表示法(2) 敘述法敘述法-用集合中元素共同性質(zhì)來表示用集合中元素共同性質(zhì)來表示 A=x|x是奇數(shù)是奇數(shù),B=x|x是中國的省是中國的省,C=y|y=2或或y=4.一般一般的的, S=x|P(x), P(x):應(yīng)滿足的謂詞應(yīng)滿足的謂詞.(1) 列舉法列舉法-將某集合的元素列舉出將某集合的元素列舉出A=a,b,c,d,B=2,4,6,8,2n,C= ,當(dāng)當(dāng)

4、然然,有些集合不能用列舉法來表示有些集合不能用列舉法來表示,如如B=(0,1)不可數(shù)集不可數(shù)集.naaaa,.,323-1集合的概念和表示法集合的概念和表示法對對b,若若P(b)為為T,則則bS; 對對c，若，若P(c)為為F,則則c S3. 集合間的關(guān)系集合間的關(guān)系(1) 相等相等. 集合集合A和和B，若，若A和和B中的中的所有元素所有元素都相同，則稱都相同，則稱 為為A和和B相等。記作相等。記作A=B，否則，否則AB(2) 包含包含. Set A和和B,如果如果A中的所有元素均是中的所有元素均是B中的元素中的元素,稱稱Set B包含包含Set A,記作記作B A,或稱為或稱為A是是B的子集

5、的子集,記作記作A B.即即A包含于包含于B.)(BxAxxBAABBA或(4) 另外另外,再定義兩個特殊的集合再定義兩個特殊的集合:E, (3) 若若A是是B的子集且存在的子集且存在x B，但，但x A，則稱，則稱A是是B的的真子集真子集，記作，記作A B或或B A(真包含真包含)3-1集合的概念和表示法集合的概念和表示法定義：定義：若一個若一個Set沒有任何元素，這個集合稱為沒有任何元素，這個集合稱為空集空集，記作記作 ， =x|p(x) p(x)，p(x)是是任意謂詞任意謂詞。定義：定義：全集全集E，在一定的范圍內(nèi)，若所有的集合均為某一集合的子集，則稱該，在一定的范圍內(nèi)，若所有的集合均為

6、某一集合的子集，則稱該集合為集合為全集全集。如。如E為為“地球上的人類地球上的人類”，則，則“某班學(xué)生某班學(xué)生”、“某學(xué)校老師某學(xué)校老師”均均是子集。是子集。 E=x|p(x) p(x),p(x)是任何謂詞。是任何謂詞。 (5) 用文氏圖來表示集合之間關(guān)系，用一個正方形表示全集，圓用文氏圖來表示集合之間關(guān)系，用一個正方形表示全集，圓表表 示集合，這樣集合之間的關(guān)系就可用文氏圖來形象地表示。示集合，這樣集合之間的關(guān)系就可用文氏圖來形象地表示。 A=BEAEBA=BAB3-1集合的概念和表示法集合的概念和表示法ABBAiff且(6)定理：定理：集合集合A和和B是相等的。是相等的。 ABBABA且有

7、相同元素。與則若證：必要性BABA ECB傳遞性傳遞性ACACBBA且3-1集合的概念和表示法集合的概念和表示法* 以后判斷兩集合相等就主要用這一重要定理。以后判斷兩集合相等就主要用這一重要定理。AASet，定理：對任一ABTAxBxxBATBxAxxx即為且，即為,)()|(ABAxBxxBABxAxxBAABBA，或，則，用反證法，假設(shè)且若充分性)()()()(.BA 矛盾，3-1集合的概念和表示法集合的概念和表示法）。（的冪集，記作稱為的集合的所有子集為元素組成冪集：由集合AASA. 4, ,)(,cbacbcabacbaAScbaA，則如例：若例：若A=a,b,c,寫出其所有子集。寫出

8、其所有子集。解：解： 、a、b、c、a，b、a，c、b，c、a，b，c均是均是A的子的子 集集 這些子集也可以構(gòu)成一集合。這些子集也可以構(gòu)成一集合。 個。的子集數(shù)為個元素，即有個元素，有定理：nnAAnA22)(時中元素總數(shù)為數(shù)為個元素構(gòu)成的子集合個個元素中取證：由0)(kNACknkn3-1集合的概念和表示法集合的概念和表示法二項式展開公式nkknknnnCCCCN0211nnkknnknknkknnNCyxyxCyx221)(00，則取又)()2)(1）集例：確定下列集合的冪12010，）的冪集為（個元）有（個元，有）（）解： ,)()2，其冪集數(shù)為3-1集合的概念和表示法集合的概念和表示

9、法合取運算不同交與數(shù)理邏輯中注意集合)()( |BxAxxS交運算性質(zhì)：結(jié)合律，交換律)().(6. 3. 5. 2. 4. 1CBACBAAEABBAABAAABBAAAASBABASBABA的交集，記作和稱為的元素組成的集合又屬于是集合，由所有既屬于和定義：(1) 交3-2集合的運算集合的運算(2) 并并定義：定義：所有屬于所有屬于A or屬于屬于B的元素組成的集合的元素組成的集合S,稱為稱為A和和B的的并集并集.記作記作AB=S.S=x(xA)(xB),不同不同可兼或可兼或ABE有結(jié)合性有結(jié)合性有有n n個集合個集合A A1 1,A,A2 2, ,A,An n. . A A1 1AA2

10、2A An n= = A Ai ini 13-2集合的運算集合的運算并運算性質(zhì)并運算性質(zhì)：書上有證明！書上有證明！AA=AAA=AAE=EAE=EA =AA =AAB=BAB=BA A 交換律交換律（A AB)B)C=A A (B(BC) C) 結(jié)合律結(jié)合律nn個集合個集合A A1 1,A,A2 2,A,An n. A. A1 1AA2 2A An n= A= Ai i ni 1A AB,B ABA AB,B ABA B,C D A B,C D 則則 AC BDAC BD3-2集合的運算集合的運算，關(guān)系：關(guān)系： 定理定理：設(shè)設(shè)A,B,C,則下列則下列分配律分配律成立成立a). A(BC)=(A

11、B)(AC)b). A(BC)=(AB)(AC)證證: a) 書上有書上有,只證只證 b). b) 設(shè)設(shè)S=A(BC), T=(AB)(AC) 證證 S T. 設(shè)設(shè)xS ,xA或或 xBC. (xB)且且(xC) 若若xA 則則 xAB,且且xAC xT.xT.3-2集合的運算集合的運算若若xBCBC則則xBxB且且xCxCxABxAB且且xACxACxT故故 S T.證證T S設(shè)設(shè)xT,即即xAB 且且xACxxA或或xB且且xA或或xC若若xA,則則xA(BC)=S若若x A,則則xB且且xC,3-2集合的運算集合的運算xxBC.xxS 故故T S所以所以 S=T.定理定理:下列下列吸收律

12、吸收律成立成立 a) A(AB)=A b) A(AB)=A書上有證書上有證明明,不證了不證了!BAEBAE3-2集合的運算集合的運算書上有證明書上有證明(3) 補(bǔ)補(bǔ) a)定義定義:所有屬于所有屬于A而不屬于而不屬于B的元素組成的集合的元素組成的集合S,稱為稱為B關(guān)于關(guān)于A的的補(bǔ)集補(bǔ)集,記作記作A-B,也稱也稱A和和B的的差差或或相對補(bǔ)相對補(bǔ).包含與包含與,之間關(guān)系之間關(guān)系.定理定理:A B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) AB=B或或AB=A.ABES=x(xA)(xA)（x Bx B） =x =x（xAxA） （xBxB） 3-2集合的運算集合的運算b）集合）集合A關(guān)于全集關(guān)于全集E的的補(bǔ)補(bǔ)。 E-A稱為

13、稱為A的的絕對補(bǔ)絕對補(bǔ)，記作記作A。AEA=x(xE(xE）（x Ax A） A A有下列性質(zhì)：有下列性質(zhì)： （ A）=A E=3-2集合的運算集合的運算 =EAA=EAA=3-2集合的運算集合的運算定理：定理：A，B是集合，則是集合，則a) B 類類似于似于De.Morgan定律定律b) B ()()ABABAA定理定理:A,B,C集合集合a)b)BAABAABABBABxAxxBxAxxBAxBAxxBAxxBAb)()( |)()|)(|)()中中或不在不在即證證：證：a)已有已有3-2集合的運算集合的運算CABACBAc)()EBA(4) 對稱差對稱差 定義：所有屬于定義：所有屬于A或

14、屬于或?qū)儆贐但不能同時屬于但不能同時屬于A和和B的的元素，組成的集合元素，組成的集合S稱為稱為A和和B的對稱差。記作的對稱差。記作BA)()(BxAxxBAS，則定理：若BABAABb)()ABa)3-2集合的運算集合的運算()()ABBAEAACBACBABABABAAAAAABBA6)(. 5)()(. 4. 3. 2. 1結(jié)合律交換律對于結(jié)合律，書上有證明我們僅用文氏圖來給予說明)()(CBACBA3-2集合的運算集合的運算對稱差有下列性質(zhì)：對稱差有下列性質(zhì)：CB3-2集合的運算集合的運算BA()ABC()ABC）（）（利用文氏圖可以看出BABABA）（練習(xí)695分為四個部分的并分為四個

15、部分的并CBABACCBACBA3-2集合的運算集合的運算確定以下各式：確定以下各式：)6(95P , , , , 上節(jié)課我們介紹了集合的概念，表示法，集合間一些主要關(guān)系：相等、包含等，以及集合的運算：交，并，補(bǔ)，對稱差。 在集合這些基本概念的基礎(chǔ)上，我們將進(jìn)一步討論一些具有特殊性質(zhì)的集合，我們將討論關(guān)系，復(fù)合關(guān)系，逆關(guān)系，笛卡爾積等概念與性質(zhì)。 簡要回顧簡要回顧1.序偶 在日常生活中，許多事物是成對出現(xiàn)的，并且具有一定的順序，如上，下，左，右；3 8，大，小，多少等等。有固定次序的客體a，b組成的一個有序序列稱為序偶，記作. 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積注意：1.次序是非常重

16、要的。與不等的，而a，b與b，a是相等的2.序偶中兩個元素可來自不同集合。如a,b,c,1,2,3. 序偶。序偶通常用來表達(dá)兩個客體之間的關(guān)系。3.序偶的概念推廣到三元組。三元組是序偶，其第一個元素本身是序偶，第二個元素是客體， ，c= ,c =,w iff a=u,b=v,c=w 三元組,c a,，因為后者不是三元組。2.序偶相等 有兩個序偶= iff a=u,b=v. 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積)(,.,.,.,.,.,2211212112121元組相等定義元組相等定義且且nyxyxyxiffyyyxxxxxxxxxxnnnnnnn 同樣推廣到四元組：是序偶，第一個元素是

17、三元組，第二個元素是客體。,d =,c,d記作。n元組是序偶，第一元素是n-1元組，第二元素是客體。 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積4、笛卡爾乘積（直積）：A、B是集合，A中的元素作為序偶的第一個元素，B中的元素作為序偶的第二個元素，所有的這種序偶構(gòu)成的集合稱為A和B的笛卡爾積，記作：AB)()( |,BbAabaBA ，例例： A323 ,2 ,1 ,3 ,2 ,1 , BA, 3, 2, 1, 3, 2, 1 AB不不滿滿足足交交換換律律ABBA )()(ABBA BABA則則或或規(guī)定：若規(guī)定：若, 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積323 , 3,2 , 3,1

18、, 3,3 , 2,2 , 2,1 , 2,3 , 1,2 , 1,1 , 1, BBAA 考慮直積AB中元素個數(shù)？若A中元素個數(shù)為m，B中元素個數(shù)為n，則AB中元素個數(shù)為mn中有多少個元素？)(BAT 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積仍可再作笛卡爾積：仍可再作笛卡爾積：合，合，是笛卡爾乘積，也是集是笛卡爾乘積，也是集是集合，是集合，21321AAAAA 、多重直積：、多重直積：5,|,|,)(332211321332211321321AAAAAAAAA ,|,|,)(332211321332211321321AAAAAAAAA 不是三元組不是三元組不滿足結(jié)合性！不滿足結(jié)合性！（)

19、()321321AAAAAA 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積321321AAAAAA 為為）規(guī)定記（規(guī)定記（432143214321)(AAAAAAAAAAAA ）（nnAAAAAAA )(32121類類似似的的：nnAAAAAAAAAAABA 個個，記，記若若32 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積6、笛卡爾積是集合間的一個運算，有如下性質(zhì)：定理：的的分分配配律律，關(guān)關(guān)于于 A、B、C均為集合）（）（）、（、（）（）（）、（、（）（）（）（、）（）（）（、CBCACBAdCBCACBAcCABACBAbCABACBAa )書上有證明，不講了)()(,BCACCBCAB

20、AC 則則定理：若定理：若 未必成立未必成立時，則時，則注意：當(dāng)注意：當(dāng) C 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積定理：A、B、C、D是非空集合，則 DBCA 且且當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)必必要要性性證證： ByAx ,BAyxByAx ,)()(DCBA )()(DyCx DBCA 且且充充分分性性)()(,ByAxBAyx )()(DyCx DCyx ,DCBA DCyx ,DCBA DBCA 且且 3-4 3-4 序偶和笛卡爾積序偶和笛卡爾積關(guān)系是一個基本概念，在現(xiàn)實生活中，就有許多例子。例如大家很熟悉的兄弟關(guān)系，上下級關(guān)系，父子關(guān)系。數(shù)學(xué)中大于、小于關(guān)系等等。前面提到，序偶可以表達(dá)兩個

21、客體、三個客體或n個客體之間的聯(lián)系，因此可以考慮用序偶來表達(dá)關(guān)系這個概念。3-5關(guān)系及其表示關(guān)系及其表示舉例：電影院里，集合A：所有電影票，集合B：所有座位， R：“對號”關(guān)系Ry, xyxRy, xyxyx ,By,Ax對不上對上，也即：要么沒有“對號”關(guān)系，要么存在“對號”關(guān)系和“對號”關(guān)系。確定了一個二元關(guān)系構(gòu)成的集合，對上可見，由所有的序偶R)yx(y, x3-5關(guān)系及其表示關(guān)系及其表示（1）定義：某些序偶的集合構(gòu)成了一個二元關(guān)系R。張票張票100,10021aaaA ?；蚧蚩捎涀骺捎涀髦械男蚺贾械男蚺疾辉诓辉??；蚧蚩捎涀骺捎涀髦械男蚺贾械男蚺紉RyRyxyxRxRyRyxyxR ,個

22、元素1001001001個元素，1001001002211對號,j , i,Bb ,Aa|b ,aBA,b ,a,b ,a,b ,ajijiR座位號座位號,10021bbbB “對號”關(guān)系，則：RBAR 顯然：顯然：3-5關(guān)系及其表示關(guān)系及其表示又如：實數(shù)中關(guān)系，。集合的笛卡爾積的子集集合的笛卡爾積的子集即關(guān)系也可看作是兩個即關(guān)系也可看作是兩個實數(shù)集，則實數(shù)集，則是實數(shù)，且是實數(shù)，且,:,|,CCCyxyxyx (2)前域、值域、域ranRdomRRFLDRFLDRRRyxxyranRRranRyRyxRyxyxdomRRdomRxRyxR 的域，記為的域，記為的前域和值域一起稱作的前域和值域

23、一起稱作的前域，即的前域，即稱為稱為組成的集合組成的集合的所有的所有由由的前域，即的前域，即稱為稱為組成的集合組成的集合的所有的所有是二元關(guān)系，由是二元關(guān)系，由),)( |,),)( |,3-5關(guān)系及其表示關(guān)系及其表示例：4 , 2 , 1 ,5 , 4 , 3 , 2 , 1 BA4 , 3,4 , 2,4 , 1,2 , 1 H關(guān)系關(guān)系則：4 , 3 , 2 , 1 ,4 , 2,3 , 2 , 1 FLDHranHdomH(3)令x、y是集合，YX 的子集構(gòu)成一個關(guān)系R稱作x到y(tǒng)的關(guān)系XYx1x2x3y1y2XdomR YranR 若x、y有限，則從X到Y(jié)的關(guān)系有個2| y | x |

24、YXranRdomR3-5關(guān)系及其表示關(guān)系及其表示關(guān)系。關(guān)系。上的上的，求，求，例：例： XX43 , 2 , 1342423141312 ，4 , 3 , 2dom3 , 2 , 1ran4321，F(xiàn)LD為：為：則其全域關(guān)系則其全域關(guān)系例：例：1,HdsmfH ,1 ddsdmdfddfsfmfffHHH互不相識關(guān)系空關(guān)系：2H3-5關(guān)系及其表示關(guān)系及其表示上的恒等關(guān)系上的恒等關(guān)系稱為稱為恒等關(guān)系：恒等關(guān)系：AAxxxIA|,)4( 3 , 3,2 , 2,1 , 1,3 , 2 , 1 AIA如：如：AIR不是不是而：而：2 , 2,1 , 1 關(guān)系也是集合，故也可以進(jìn)行集合的運算。特別注

25、意，必須包含所有x3-5關(guān)系及其表示關(guān)系及其表示2、關(guān)系的運算：對同一域上的關(guān)系，可以有交、并、補(bǔ)、差運算2 ,1 ,1 ,1 ,2 ,1 , cbaScbaR，2 ,1 ,1 ,2 ,1 , ccbbaSR的關(guān)系，的關(guān)系，到到是從是從和和如：如：YXSRYcbaX,2 , 1, 1 , aSR為全集為全集YXRYXcbaR 2 ,1 ,2 ,1 ,2 , cbSR3-5關(guān)系及其表示關(guān)系及其表示定理：若Z和S是從集合X到Y(jié)的兩個關(guān)系，則SZSZSZSZ ,也是X到Y(jié)的關(guān)系。（書上有證明）。我們用序偶集合表示關(guān)系，R是從X到Y(jié)上的關(guān)系，當(dāng)X、Y為有限集時，可用關(guān)系矩陣和關(guān)系圖來表示。3-5關(guān)系及

26、其表示關(guān)系及其表示,2121yyyxxxnmYX R是從X到Y(jié)的關(guān)系，X和Y是有限集合， rrrrrrrrrrMijnmmnmmnnR ,211222111211R的關(guān)系矩陣其中： RRyxyxriiij,0,1任意兩個元素間用1或者0表示有關(guān)系R或沒有關(guān)系R。（3）關(guān)系矩陣和關(guān)系圖：3-5關(guān)系及其表示關(guān)系及其表示的關(guān)系圖。得到的圖就是畫一條有向弧，至結(jié)點則自結(jié)點。如果個結(jié)點畫個結(jié)點在平面上畫的關(guān)系到是從若關(guān)系可以用圖形表示。關(guān)系圖：有限集的二元21212121Ryx,Ryxy,y,yn,x,x,xm,y,y,yY,x,x,xX,YXRjijinmnm,13214321yyyYxxxxX ，：

27、例例,24141332223111 yxyxyxyxyxyxyxR MRx1x2x3x4y3y1y23-5關(guān)系及其表示關(guān)系及其表示3 , 4,2 , 4,2 , 3,1 , 4,1 , 3,1 , 24 , 3 , 2 , 12 關(guān)系。關(guān)系。上的上的：例例AA M13243-5關(guān)系及其表示關(guān)系及其表示x1AIA關(guān)系，則上的但若求圖為：1234結(jié)束畫一條弧從出發(fā)到11 ,3-5關(guān)系及其表示關(guān)系及其表示有限集合、要求關(guān)系圖關(guān)系矩陣序偶關(guān)系表示有三種方法YX)()(,YYXYXYXYXRRX 而而的關(guān)系的關(guān)系到到由于由于一集合上的關(guān)系。一集合上的關(guān)系。因而我們以后僅討論同因而我們以后僅討論同)()(

28、YXYXR 3-5關(guān)系及其表示關(guān)系及其表示),)(RxxXxxXR 上自反上自反在在”“，”，”，“，”關(guān)系，”關(guān)系，如：實數(shù)域上的“如：實數(shù)域上的“ 222211113-6關(guān)系的性質(zhì)這里我們僅討論在集合X上的二元關(guān)系。（對于X到Y(jié)的關(guān)系可以改為此類）。R是X上的二元關(guān)系等。等。，三角形自身與自身全，三角形自身與自身全三角形全等關(guān)系三角形全等關(guān)系 ）上的所有元素而言，上的所有元素而言，（注：對（注：對RxxX ,RIA 也即也即1、自反性2、對稱性：，則也稱具有對稱性。，則也稱具有對稱性。注：若沒有注：若沒有Ryxyx ,是對稱的。是對稱的。則則如：如：RRX2 , 3,3 , 2,1 , 2

29、,2 , 1,3 , 2 , 1 如：R=IA，R是對稱的1221 ，：兩個三角形的相似關(guān)系兩個三角形的相似關(guān)系。是整數(shù)是整數(shù)例：例：2|,7 , 5 , 3 , 2yxyxRA 是自反的。是自反的。是整數(shù)是整數(shù)RRxxxxAxx ,)02)()()(yRxxRyYyXxyxXR 上對稱上對稱在在也是整數(shù)也是整數(shù)則則是整數(shù)，是整數(shù)，若若RxyxyRyxyx ,2,2。是對稱的。是對稱的。RRR 5 , 3,3 , 53、傳遞性：上傳遞上傳遞在在XRRzxRzyRyxXzXyXxzyx ),)()()(313221 ，”如：“如：“3132 , 2, ”“”“zxzyyx又如：日常工作中，同事關(guān)

30、系：甲、乙是同事，乙、丙是同事甲、丙是同事，傳遞性成立。、反自反性：具有反自反性。具有反自反性。RRxxXxx ),)(如：父子關(guān)系，自己與自己不能是父子；。關(guān)系：關(guān)系：xx 反自反。反自反。所以自反的否定不同于所以自反的否定不同于不等價不等價和和,),)(),)(RxxXxxRxxXxx ),)(),)(RxxXxxRxxXxx 自反的否定：自反的否定：提問：反自反是否就是自反的否定？也即是否不是自反就一定是反自反的？3 , 3,3 , 2,2 , 3,2 , 1,1 , 13 , 2 , 1 RA，如：如：RRRR 3 , 3112 , 2，也不是反自反的，也不是反自反的，不是自反的，不是

31、自反的，不是自反的與反自反的不是等價的，不是同一回事。5、反對稱性：BAABBAyxxyyxRyxRxyRyx ”，”，如：“如：“為反對稱的為反對稱的稱稱必有：必有：若若,的。的。是對稱的，也是反對稱是對稱的，也是反對稱如：如：3 , 3,2 , 2,1 , 1,3 , 2 , 1 RA1、關(guān)系既可以對稱的，又可以是反對稱的。2、關(guān)系可以既不是對稱的，又不是反對稱的。2 , 3,3 , 3,1 , 2,2 , 1,3 , 2 , 1 RA如：如：),)()()(),)()(RxyRyxyxYyXxyxyxRxyRyxYyXxyx 的另一種等價定義：的另一種等價定義：反對稱性反對稱性給出兩個簡

32、單結(jié)論：RxyRyxyxRxyRyxyxRxyRyxyxRxyRyxyxyxRxyRyx ,)(),(),)(),(),()(),()()(,下面我們討論關(guān)系的五種性質(zhì)與關(guān)系圖、關(guān)系矩陣之間的聯(lián)系。4 , 4,3 , 4,4 , 3,1 , 3,3 , 3,2 , 2,3 , 1,1 , 1,4 , 3 , 2 , 1 RI討論R的性質(zhì)。 44MR4123首先，R是自反的，R是對稱的，RRRRR 3 , 443R4 , 14 , 3,3 , 1、，不是反對稱的，不是反對稱的，不是反自反的，不是反自反的，不是傳遞的。不是傳遞的。但但從關(guān)系矩陣、關(guān)系圖來判斷五個性質(zhì)：1、自反的：關(guān)系矩陣的對角線上

33、元素全為1， 關(guān)系圖中每個結(jié)點均有自回路。2、對稱的：關(guān)系矩陣是對稱矩陣， 關(guān)系圖中若兩個結(jié)點之間有有向弧，則必成對出現(xiàn)3、反自反的：關(guān)系矩陣中對角線元素全為0， 關(guān)系圖中每個結(jié)點都沒有自回路。4、反對稱的：關(guān)系矩陣以對角線對稱的元素不能同時為1， （但可為對稱陣，同時為0）， 關(guān)系圖中如果兩個結(jié)點之間有有向弧，則不能成 對出現(xiàn)。5、傳遞性：不能明確判斷，只能用定義。3.7復(fù)合關(guān)系和逆關(guān)系 a,b是兄弟關(guān)系R, b,c是父子關(guān)系S,則a,c是叔侄關(guān)系T,T可以看作是R和S的復(fù)合關(guān)系。1、復(fù)合關(guān)系 R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則R和S的復(fù)合關(guān)系RoS稱為R和S的復(fù)合關(guān)系，定義為：),)(

34、|,SzyRyxYyyZzXxzxSR 3 , 1,1 , 3,5 , 2,2 , 42 , 2,4 , 3,2 , 1 SR如：如：從左至右復(fù)合。從左至右復(fù)合。則：則：5 , 2,2 , 3,5 , 1 SR5 , 2,1 , 3,2 , 3,5 , 1,1 , 4 SRSS則：則：如：如：有限集合、要求關(guān)系圖關(guān)系矩陣序偶關(guān)系表示有三種方法YX結(jié)束畫一條弧從出發(fā)到 1 , 1)()(,YYXYXYXYXRRX而的關(guān)系到由于一集合上的關(guān)系。因而我們以后僅討論同)()(YXYXR圖為：12343-5關(guān)系及其表示關(guān)系及其表示前一節(jié)我們介紹了關(guān)系，它是某些序偶的集合，或者若R是構(gòu)成了一個關(guān)系的子集，

35、則RBA是具有自反性則稱RRxxXx),(”“，”，“，”關(guān)系，如：實數(shù)域上的“22221111今天我們繼續(xù)來討論關(guān)系的性質(zhì)。3-63-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)這里我們僅討論在集合這里我們僅討論在集合X上的二元關(guān)系。（對于上的二元關(guān)系。（對于X到到Y(jié)的關(guān)系的關(guān)系可以改為此類）?？梢愿臑榇祟悾?、自反性自反性：R是是X上的二元關(guān)系，若上的二元關(guān)系，若等。，三角形自身與自身全三角形全等關(guān)系）上的所有元素而言，（注：對RxxX ,3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)2 2、對稱性對稱性：()()(,)RXxy xXyXx yRy xR 是 上的二元關(guān)系，若成立，則也稱具有對稱性。（注：若沒有Ryxyx,是對稱

36、的。則如：RRX2 , 3,3 , 2,1 , 2,2 , 1,3 , 2 , 1稱R具有對稱性。如：R=IA，則R是對稱的）。1221，似兩個三角形的關(guān)系：相例：。是整數(shù)2|,7 , 5 , 3 , 2yxyxRA是自反的。是整數(shù)RRxxxxAxx,)02)(3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)也是整數(shù)則是整數(shù)，若RxyxyRyxyx,2,2。是對稱的。RRR5 , 3,3 , 5,x yRy zRx zRR必有，則稱 具有傳遞性。3 3、傳遞性傳遞性：R是X上的二元關(guān)系，若RzyRyxXzXyXxzyx,)()()(即：),Rzx313221，”如：“3132 , 2,”“”“zxzyyx3-6關(guān)系

37、的性質(zhì)關(guān)系的性質(zhì)、反自反性反自反性：是上的二元關(guān)系，是上的二元關(guān)系，具有反自反性。則稱RRxxXxx),)(不同于反自反。,RxxXx,xRxxx其否定為，對注意：任意的x，不是自反的否定，自反如：父子關(guān)系，自己與自己如：父子關(guān)系，自己與自己不能是父子；不能是父子；。關(guān)系：xx 自反性與反自反性的關(guān)系：是否不是自反的就一定是反自反性與反自反性的關(guān)系：是否不是自反的就一定是反自反的？不是。自反的？不是。3 , 3,3 , 2,2 , 3,2 , 1,1 , 13 , 2 , 1RA，如：RRRR3 , 3112 , 2，也不是反自反的，不是自反的，不是自反的與反自反的不是等價的，不是同一回事。不

38、是自反的與反自反的不是等價的，不是同一回事。3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)R是X上的二元關(guān)系，若BAABBAyxxyyxRyxRxyRyx”，如：“為反對稱的稱必有：若,的。是對稱的，也是反對稱如：3 , 3,2 , 2,1 , 1,3 , 2 , 1RA即表示為：、一個集合既可以對稱的，又可以是反對稱的。、也有關(guān)系既不是對稱的，又不是反對稱的，如：2 , 3,3 , 3,1 , 2,2 , 1R3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)5、反對稱性：RxyRyxyxRxyRyxyxyxRxyRyxRxyRyxyxYyXxyxyxRxyRyxYyXxyx,)(),()()(,),)()()(),)()(的另一種等

39、價定義：反對稱性下面我們討論介紹的關(guān)系的五種性質(zhì)與關(guān)系矩陣、關(guān)系圖之間的聯(lián)系。3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)對自反性與反自反性的總結(jié)：3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)對稱性與反對稱性的總結(jié)：3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)4 , 4,3 , 4,4 , 3,1 , 3,3 , 3,2 , 2,3 , 1,1 , 1,4 , 3 , 2 , 1RI討論R的性質(zhì)。44MR4123首先，R是自反的，R是對稱的，RRRRR3 , 443R4 , 14 , 3,3 , 1、，不是反對稱的，不是反自反的，不是傳遞的。但3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)例如：從關(guān)系矩陣、關(guān)系圖來判斷五個從關(guān)系矩陣、關(guān)系圖來判斷五個性質(zhì)：性質(zhì)：1、

40、自反的：關(guān)系矩陣的對角線上元素全為、自反的：關(guān)系矩陣的對角線上元素全為1， 關(guān)系圖中關(guān)系圖中 每個結(jié)點均有自回路。每個結(jié)點均有自回路。2、對稱的：關(guān)系矩陣是對稱矩陣，、對稱的：關(guān)系矩陣是對稱矩陣， 關(guān)系圖中若兩個結(jié)點之間有有向弧，則必成對出現(xiàn)關(guān)系圖中若兩個結(jié)點之間有有向弧，則必成對出現(xiàn)3、反自反的：關(guān)系矩陣中對角線元素全為、反自反的：關(guān)系矩陣中對角線元素全為0， 關(guān)系圖中每個結(jié)點都沒有自回路。關(guān)系圖中每個結(jié)點都沒有自回路。4、反對稱的：關(guān)系矩陣以對角線對稱的元素不能同時為、反對稱的：關(guān)系矩陣以對角線對稱的元素不能同時為1， （但可為對稱陣，同時為（但可為對稱陣，同時為0），）， 關(guān)系圖中如果兩

41、個結(jié)點之間有有向弧，則不能成關(guān)系圖中如果兩個結(jié)點之間有有向弧，則不能成 對出現(xiàn)。對出現(xiàn)。5、傳遞性：不能明確判斷，只能用定義。、傳遞性：不能明確判斷，只能用定義。3-6關(guān)系的性質(zhì)關(guān)系的性質(zhì)為了確切表示復(fù)合關(guān)系，我們舉一實例： a,b是兄弟關(guān)系R, b,c是父子關(guān)系S,則a,c是叔侄關(guān)系T,T是R和S的復(fù)合關(guān)系。1、復(fù)合關(guān)系：為了明確地表示復(fù)合關(guān)系，給出定義：定義：R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則R和S的復(fù)合關(guān)系RS稱為R和S的復(fù)合關(guān)系，表示為：),)(|,SzyRyxYyyZzXxzxSR3 , 1,1 , 3,5 , 2,2 , 42 , 2,4 , 3,2 , 1SR如：從左至右復(fù)合

42、。則：5 , 2,2 , 3,5 , 1SR5 , 2,1 , 3,2 , 3,5 , 1,1 , 4SRSS則：如：3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系不滿足交換律RSSRRS,4 , 1,2 , 3,2 , 4求復(fù)合關(guān)系，也稱為合成運算。合成運算具有結(jié)合律2 , 3)(2 , 3)(RSRRSR又例：,321321321zzzyyyxxxZYX,333221222111zyzyzyyxyxyxSR,323121zxzxzxSR通過關(guān)系圖來求復(fù)合y1x1x2x3y2y3z1z2z3SRx1x2x3z1z2z3SR3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系MMsR通過關(guān)系矩陣求復(fù)合MMMMSRS

43、RSR有：再邏輯相加得到。第一列元素相乘第一行元素與是第一行第一列元素sRSRMMM0相加所得。列元素邏輯相乘再邏輯第行元素與第jSRMMMsRjii:一般地：MMMSRSR3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系 RRyxyxuuMjijiijijR,0,1SSzyzyvvMkjkjjkjks,0,11()nR SikikijjkjVwwuvM111101110000:111001010000:3 , 1,1 , 3,5 , 2,2 , 42 , 2,4 , 3,2 , 15 , 4 , 3 , 2 , 1SRA如：3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系MMsRMMSR2 , 3,5 , 2,

44、5 , 1SR2 2、逆關(guān)系逆關(guān)系：R R是是X X到到Y(jié) Y的二元關(guān)系，把的二元關(guān)系，把R R中每一序偶的元素次序顛倒，得中每一序偶的元素次序顛倒，得到的關(guān)系稱為到的關(guān)系稱為R R的逆關(guān)系，記作：的逆關(guān)系，記作：。,|,RyxxyRRcc3 ,2 , 3, 3223，”逆“如：“,312312133221321321,xyxyxyRyxyxyxyyyxxxcRYX如：3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系XXX321YYY321YYY321反向關(guān)系XXX321RcR性質(zhì)：下面討論逆關(guān)系的一些的關(guān)系到轉(zhuǎn)置關(guān)系。關(guān)系矩陣XYTRRMMMMRRcc.,010001100,0011000103-7復(fù)

45、合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系的關(guān)系，則：到都是從BARRcRRRc21,)2(.)1()().),),),2121),)()2121)2121)()()()(dbebaeRBARRRdABcbaRRRRBARRRRRRRRcccccccccccc明均有證明，這里我們證書上對這里3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系RRRRRRRRRRRRRRccccccccyxyxyxxyxyxyyxb212121,2,1,21,.):)()(2121相等，要證相等即證兩集合首先兩端仍是序偶集合證.,.,)()(RRRRRcccyxyxRxyRxycyxdc.)4(:)3()(RTSSTccccRRaXRZ

46、YsYXT是對稱的上的二元關(guān)系，則：為關(guān)系，則關(guān)系，是3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系.,.,:),)IRIRRIRxcxccxcRxxyxyxRRxyRyxyxRyxRyxyxRxyRyxRbbRRb反對稱性質(zhì)：根據(jù)即則若是反對稱的，即證外其它書上都有證明：除是反對稱的是反對稱的。故時有且對，因為RyxRxyRyxyxRRRxyRyxRyxRyxRRyxRRIIxcccxc,.,3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系是傳遞的是傳遞的，則若是對稱的是對稱的，則若是反自反的是反自反的，則若是自反的是自反的，則若題正確性上的關(guān)系，判斷下列命是）（書212121212121212121,),)

47、,),):,173.118RRRRdRRRRcRRRRbRRRRaARRpa) b) c) d)3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系2121,)RRxxRxxRxxAxa,)2121aaRRabRbaRbaAb則若,)2121bccaRRbccbRccabbaRcbaAc則若212121,)RRcbabaacaRRabaccbRcacbbaRcbaAd而若3-7復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系和逆關(guān)系運算。說明什么叫關(guān)系的閉包，我們先舉一例子是一種非常重要的運算求關(guān)系的閉包運算，這我們介紹第三種運算：和求逆關(guān)系，今天的兩種運算：合成運算上次課我們介紹了關(guān)系. 83于對稱叫做閉包運算。另外對的自反閉包

48、，這一過程稱為的最小關(guān)系，且是自反是包含即自反的，則且若是自反的。則不是自反的，但顯然例：RRRRRRRRRRRRRRRX., ,.3 , 3,2 , 2,3 , 1,3 , 2,1 , 1.3 , 1,3 , 2,1 , 1,3 , 2 , 13-8關(guān)系的閉包運算關(guān)系的閉包運算義，給出定義：似求出，為明確表達(dá)含閉包，傳遞閉包也可類),).(),(),()(, , )().)(), )(transitionsymmetryreflectionRtRsRrRRRRRRRcRRbRaRRXR分別記作：閉包。對稱，傳遞的自反是則稱則若關(guān)系對稱的，傳遞的對任何自反的對稱的，傳遞的是自反的滿足，若有另一

49、關(guān)系上的二元關(guān)系一般不特指均是上的關(guān)系是定義：3-8關(guān)系的閉包運算關(guān)系的閉包運算且是充要的反時因而當(dāng)一個關(guān)系本身自遞的。是自反的，對稱的，傳如是傳遞閉包。是對稱閉包；的自反閉包；是關(guān)系，例如,)(.)(,)(,)(.,:RRrtsrXxxxXIIIIIIIIxxxxxxxx3-8關(guān)系的閉包運算關(guān)系的閉包運算).).()();)();)()XbaRRtRcRRsRbRRrRaR書上有證明，現(xiàn)證是傳遞的是對稱的是自反的上的關(guān)系，則是設(shè)定理是對稱的。是對稱的，已知證：RRsRRsb)(.)().)(., ,RRsRRRRRRRRRRR的對稱閉包，即是是對稱的，必有任一是對稱的，3-8關(guān)系的閉包運算關(guān)

50、系的閉包運算的三個定理。的下面給出求關(guān)系)(),(),(RtRsRrR 1）定理）定理IRRrRX)(X上的關(guān)系，則是),)(),IIxxxxXxxRaRR是自反的，用定義證明，證：令方法這就給出求自反閉包的從而則是自反的：且自反成立。).(, ,).).,)(RrRRRRRRRRcRRbRRxxXxxIIxx.)(X證明是由定義類似可證上的關(guān)系，則是CRRRsR2）定理3）定理可省略。滿足結(jié)合律，含義。首先解釋一下上的關(guān)系，則是)().()(.)(12TSRTSRRRRtXRiitRR3-8關(guān)系的閉包運算關(guān)系的閉包運算另一種方法證明之。不好用定義證明?，F(xiàn)用是一無窮序列。證：Rii1。集合的并

51、關(guān)系的并是無限對復(fù)合。)(,)(,211232RRRiiiiiRRRRRRRRRRRRRRRRR).(1).(),(1:)(,).()(),(111RtniRtniRtRiRtNiRtaRtRRRRRnniiiii證明歸納：假設(shè)：根據(jù)定義顯然成立?；A(chǔ)證明，其步驟是：我們通常用數(shù)學(xué)歸納法理。這是與自然數(shù)有關(guān)的定即證對任意。相互包含即可。，證明這兩個集合相等均是兩個關(guān)系是兩集合3-8關(guān)系的閉包運算關(guān)系的閉包運算)()(,)()(,),(,),(,.,111RtRtNiRtRtyxRtyzRtzxRyzzxXzRyxRRRRRRiiinnnn從而有故。由傳遞性，由假設(shè)且使的則.)(, )()()(

52、.)()1RRtRRRRRtRRtRtRtbRii則且是傳遞的，是傳遞閉包，對任意的最小傳遞關(guān)系。由包含是定義，用直接證明比較困難，利是傳遞的。要證成立RRiiiiR11.2.13-8關(guān)系的閉包運算關(guān)系的閉包運算可直接求出，有了這三個定理，從而有是傳遞的。故使得和使得是則由是否有若)(),(),()(,)(,.,.,111132111RtRsRrRtRtzxzxzySSyxttRzxzyyxRRRRRRIRIRRRRRiiiiiiiiststiiiiii,)()(),(),(,ccbbaaaccbbaRRrRtRsRraccbbaRcbaAIA解：求例：3-8關(guān)系的閉包運算關(guān)系的閉包運算,01

53、0001100001100010001100010,001100010,:)(,)(2132232bcabcaRMMMMMMRRRRRtcabcabaccbbaRRRsRRRRRRitC我們用關(guān)系矩陣來求EMMMRRR100010001233-8關(guān)系的閉包運算關(guān)系的閉包運算13414736245443,001100010,34nRRRRRRRRRRRRRRRRRRaccbbaRMMMccbbaaR故有：33632352nnRRRRRR,)(132bcabcaaccbbaccbbaaRRRRRtii3-8關(guān)系的閉包運算關(guān)系的閉包運算下定理：結(jié)論不是偶然的，有如次即可。我們至多只要求有時不必求出每

54、一個由上例可看出可記作對n,R,)(1111111111)(iiiRtRRRtM定理：的個數(shù)有關(guān)）與使得則存在一個正整數(shù)上的關(guān)系是個元素的集合是有XkRRRRtnRXk.()(,k,X,n2?)()(.),(),(R:22是否成立顯然成立首先證nkRRRRtRtRRRRtkk3-8關(guān)系的閉包運算關(guān)系的閉包運算)1,(.,.,Re,Re,Re,Re)(0,Re,Re,),(,:.,)(,.,),(,:111211110012112111212的個數(shù)多它比不是元素的個數(shù)的個數(shù)經(jīng)過中過程到除去存在這表明抽屜原理記為中必有兩個相同記個元素中有而個元素有而對應(yīng)到步經(jīng)過這使得則可找到序列假設(shè)是最小的而設(shè)有

55、用反證法求證的最小正整數(shù)使是且取知設(shè)有只需證個個個RReeyxRRyeeeexpqteeeeexenXnppeeexyxpRyeexeeeRRRRyxnppRyxRtyxnpRyxpRyxRRRtyxnkiRyxRtyxqtkqppqqtttqtpppppppkpi3-8關(guān)系的閉包運算關(guān)系的閉包運算)()()()(.1.,)(22nkRRRRtnkRRRRtnknnpppkRyxptqpqptkkkk故中可有最大的而盾是最小的正整數(shù)發(fā)生矛與個共有nRRRRt2)(:).(,次即可求雖有求例：nnkRtdccccbabbaRdcbaA推論推論: : ),(:反證法數(shù)歸法用的證明方法至此我們介紹了

56、兩個有注3-8關(guān)系的閉包運算關(guān)系的閉包運算0000010011100101000001000101111000000100111001010000110001010010:34232RRRRRRRRRRMMMMMMMMMM解3-8關(guān)系的閉包運算關(guān)系的閉包運算MRMMMMMMMRRRnnRRRtRMWarshallRRRRRRti的關(guān)系矩陣為設(shè)。其有效性，正確性不講一種簡單算法的計算介紹為高階矩陣，求).(.,0000110011111111.)(432)(432,: ,2 , 1, 1,) 3(. 1:)2(.:) 1 (kiAkjAkjAnkijAjiMA計算則對若對每個置置3-8關(guān)系的閉包

57、運算關(guān)系的閉包運算ARniiiM.),3(,)5(1:)4(否則停止轉(zhuǎn)轉(zhuǎn))(0000000000000000000000000010001000000010000000011RtMMR，求例：，第四行中去。將第二行加入到第一行第二列中不變加，則第一行與第一列邏輯第一列中只有解：. 12 , 42 , 1 , 2:, 1 1 , 1 , 1:,:AAiAAiMA3-8關(guān)系的閉包運算關(guān)系的閉包運算,0000000000000000000000001010001000000010000001011 A行中去。，第，第第四行加到第第四列中不變。，第三列都為421, 14 , 44 , 24 , 1 ,

58、 40, 3AAAiAi3-8關(guān)系的閉包運算關(guān)系的閉包運算110100001010000000100,0101000000000000000000000000AI=5 A中第5列，A3，5=1，將第5列加入到第3列，不變I=6,j=7，第6列，第7列全為0，A不變1,1,0,1,0,0,00,1,0,1,0,0,00,0,0,0,1,0,00,1,0,1,0,0,0RMA這一算法只是用來求 ，不是重點。RM3-8關(guān)系的閉包運算關(guān)系的閉包運算.0000000000000000000000001010001000000010100001011 A:相互復(fù)合。有如下定理還可，傳遞閉包仍是關(guān)系，的自反

59、閉包，對稱閉包另外，對 R定理上二元關(guān)系，則：是是集合，設(shè)XRX3-8關(guān)系的閉包運算關(guān)系的閉包運算)()()()()()()RstRtscRtrRrtbRsrRrsa)()()()()()()RstRtscRtrRrtbRsrRrsa).()(),()(,5127),212121RRRRRRttsscba則若）結(jié)論。頁（可利用書上第證：書上有證明。)()()()()(RstRstsRtRtsRRRsRc3-8關(guān)系的閉包運算關(guān)系的閉包運算,)(,)()().()(),()()().()(1RRRRiityxtRsRstRtsRtsRstsRtsRtsRsts也是對稱的。是對稱的，則若是對稱的，即

60、需要證明又是對稱的。從而有即要證明下面要證RxlRllRllRlRRlRllRlxlllRkkkkkyykyxk1122111211121,對稱的，而使即使則3-8關(guān)系的閉包運算關(guān)系的閉包運算,)(,)(,)(,)(,)()(,acabcabaRstcabaRtbbcbbcccaaaccaabbaRtsaccaabbaRscabaRcbaActtkxyRRR，則：不成立。如中而是對稱的。故。3-8關(guān)系的閉包運算關(guān)系的閉包運算3-9集合的劃分和覆蓋集合的劃分和覆蓋 內(nèi)部的關(guān)系內(nèi)部的關(guān)系.將將A分為若干非空的子集一分塊分為若干非空的子集一分塊,定義定義A的劃分與覆蓋的劃分與覆蓋.如如A=a,b,c