1、第二篇 集合論1. 集合與關(guān)系2. 函數(shù)第三章 集合與關(guān)系2014-2015 學(xué)年第二學(xué)期陳磊3.1 集合的概念和表示法 把具有共同性質(zhì)的一些東西, 匯集成一個整體, 就形成一個集合【例】1. 教室內(nèi)的桌椅 2. 自然數(shù)的全體 3. 圖書館的藏書 通常用大寫的英文字母表示集合的名稱 組成集合的對象叫做集合的元素或成員, 常用小寫的英文字母表示。 若元素a屬于集合A, 記作aA, 也稱為A包含a, a在A之中, a是A的成員 若元素a不屬于集合A, 記作a A, 也稱為A不包含a, a不在A之中, a不是A的成員 若組成集合的元素個數(shù)是有限個, 則稱作有限集, 否則稱作無限集【例】1. 集合A:

2、 計算機(jī)專業(yè)14級全體學(xué)生 2.集合B: 全體自然數(shù) 集合的性質(zhì) 集合的元素必須是確定的。所謂確定的，是指任何一個對象是不是集合的元素是明確的、確定的，不能模棱兩可。 集合的元素又是能區(qū)分的，能區(qū)分的是指集合中的元素是互不相同的。如果一個集合中有幾個元素相同，算做一個。 集合的元素又是無序的，即1,2,3和3,1,2是同一集合。 集合的表示方法 列舉法：在花括號“”中列舉出該集合的元素，元素之間用逗號隔開。 【例】 I5=1,2,3,4,5 I+=1,2,3, I =0,1,-1,2,-2, S=T,F 描述法：用謂詞界定集合的元素。【例】 Q=x | x是有理數(shù) 若用P(x)表示x是有理數(shù)，

3、那么Q又可表示為： Q=x | P(x) 集合的元素可以是一個集合【例】1. S = a, 1,2, p, q q q 但 q S 2. S =1, 2, 1,2 1, 2 S 且 1, 2 S 羅素悖論 設(shè)命題函數(shù)P(x)表示“x x”，現(xiàn)假設(shè)由性質(zhì)P確定了一個類A, 也就是說“A=x|x x”。 那么現(xiàn)在的問題是：AA是否成立？ 首先，若AA，則A是A的元素，那么A具有性質(zhì)P，由命題函數(shù)P知A A； 其次，若A A，也就是說A具有性質(zhì)P，而A是由所有具有性質(zhì)P的類組成的，所以AA。 理發(fā)師悖論 在某個城市中有一位理發(fā)師，他的廣告詞是這樣寫的：“本人的理發(fā)技藝十分高超，譽(yù)滿全城。我將為本城所

4、有不給自己刮臉的人刮臉，我也只給這些人刮臉。我對各位表示熱誠歡迎！”來找他刮臉的人絡(luò)繹不絕，自然都是那些不給自己刮臉的人?？墒?，有一天，這位理發(fā)師從鏡子里看見自己的胡子長了，他本能地抓起了剃刀，你們看他能不能給他自己刮臉呢？ 如果他不給自己刮臉，他就屬于“不給自己刮臉的人”，他就要給自己刮臉，而如果他給自己刮臉呢？他又屬于“給自己刮臉的人”，他就不該給自己刮臉。 子集 定義 3-1.1 設(shè)A，B是任意的集合，當(dāng)A的每一元素都是B的元素時，則稱A是B的子集，也稱A包含在B內(nèi)或B包含A。記為A B或B A。 當(dāng)A不是B的子集時，記為A B。 AB用謂詞公式表示為：A B (x)(xAxB) A B

5、用謂詞公式表示為： A B (x)(xAxB)【例】設(shè)A=1，B=1,2，C=1,2,3 則 AA; AB，BC，AC ; C B 集合的包含有下列性質(zhì)： 自反性。即對任意集合A，AA。 傳遞性。即對任意集合A、B、C，當(dāng)AB和BC時，AC。 兩個集合相等 外延性原理: 兩個集合A和B是相等的, 當(dāng)且僅當(dāng)它們有相同的成員, 記為A = B. 如果兩個集合不相等, 則記為A B 由集合相等的定義可以看出，集合相等有下列性質(zhì)：自反性: 即對任意集合A，A=A。對稱性: 即對任意集合A、B, 當(dāng)A=B時，B=A。傳遞性: 即對任意集合A、B、C，當(dāng)A=B和B=C時，A=C。 定理3-1.1 設(shè)A，B

6、是集合，A與B相等的充分必要條件為A B且B A. 集合相等也可用謂詞公式表示為： A=BABBA (x)(xAxB)(x)(xBxA) (x)(xAxB) 證明兩個集合相等, 主要利用上述定理中互為子集的判斷條件 真子集 定義3-1.2 設(shè)A，B是集合，如果AB且AB，則稱A是B的真子集。記為A B。如果A不是B的真子集，記為A B。 真子集用謂詞公式表示為： ABABAB (x)(xAxB)(x)(xBxA)【例】1. 設(shè) A=a，B=a,b，C=a,b,c 則 A B，BC，AC AA 2. 自然數(shù)集是整數(shù)集合的真子集，也是有理數(shù)集合和實數(shù)集合的真子集，即N I ，NQ，NR。 空集 定

7、義3-1.3 不包含任何元素的集合叫空集, 記為 空集可以表示為： =x | P(x)P(x) 其中，P(x)為任意謂詞 注:1. 2. 定理3-1.2 對于任意一個集合A, A 證明：設(shè)A是任意集合。對任意對象x，由空集的定義知，x為假，由條件聯(lián)結(jié)詞的定義知，xxA為真。根據(jù)全稱推廣規(guī)則有 (x)( xxA) 為真，故A 任意非空集合A至少有兩個不同的子集，一個是空集，另一個是它本身A, 它們被稱為平凡子集. 全集 定義3-1.4 在一定范圍內(nèi), 如果所有集合均為某一個集合的子集, 則稱該集合為全集, 記作E. 全集的謂詞表示: E=x | P(x) P(x), P(x) 為任何謂詞【例】全

8、集E = a, b, c, 則其所有可能的子集有: S0= S1= a S2= b S3= c S4=a,b S5= b,c S6=c,a S7=a,b,c 冪集 定義3-1.5 設(shè)A是集合，A的所有子集構(gòu)成的集合稱為A的冪集合，記為P (A)【例】 A= a, b, c, 則其冪集為 P(A) =, a, b, c, a,b, b,c, c,a, a,b,cP ()= P (P () = , 定理3-1.3 設(shè)A為有n個元素的有限集合，則其冪集P (A)有2n個元素 證明: 設(shè)A有n個元素，A的子集有： 不含元素的子集一個，即 個。 含一個元素的子集n個，即 個。 含兩個元素的子集 個。 含

9、n個元素的子集 個。 |P (A)|= + + + =2n0nC1nC2nCnnC0nC1nCnnC 用二進(jìn)制編碼表示一個有限集的冪集【例】S=a, b, c S中每個元素與一個三位二進(jìn)制數(shù)中一位對應(yīng)，1表示該元素在冪集的一個集合中， 0表示不在 S100 = a, S011 = b, c 每個二進(jìn)制數(shù)還可以化為一個十進(jìn)制數(shù) S4 = S100 = a, S3 = S011 = b, c P(S) = S0, S1, S2, S3, S4, S5, S6, S7 一般的， P(S) = S0, S1, , S2n-1 作業(yè): (4) (6) a) (10) 3.2 集合運(yùn)算 集合的交 定義3-

10、2.1設(shè)A，B是任意兩個集合，由集合A與B的公共元素組成的集合S，稱為A和B的交集，記為AB。 S = AB=x | (xA) (xB)【例】令A(yù)=a,b,c，B=d,e，C=a, e 則AB=，A和B是互不相交的 A C=a 集合的交運(yùn)算具有以下性質(zhì) A A=A A = A E=A A B = B A (A B) C = A (B C) A B A, A B B【例】設(shè)A B, 求證A C B C 集合交運(yùn)算有結(jié)合律, 故niinAAAAP121= 集合的并 定義3-2.2 設(shè)A，B是任意兩個集合，由A中的元素或B中的元素組成的集合S，稱為A和B的并集，記為AB S= AB =x | (xA

11、)(xB)【例】設(shè)A=1, 2, 3, 4, B=2, 4, 5 則A B=1,2,3,4,5 集合的并運(yùn)算具有以下性質(zhì) A A=A A = A A E= E A B = B A (A B) C = A (B C) A A B, B A B【例】設(shè)A B,C D, 求證A C B D 集合并運(yùn)算有結(jié)合律, 故niinAAAAW121= 定理3-2.1設(shè)A,B,C為三個集合, 則下列分配律成立 a) A (B C) = (A B) (A C) b) A (B C) = (A B) (A C) 定理3-2.2 設(shè)A,B為任意兩個集合, 則下列關(guān)系式成立(吸收律) a) A (A B) = A b)

12、 A (A B) = A 定理3-2.3 A B, 當(dāng)且僅當(dāng)A B=B或A B=A 集合的補(bǔ) 定義3-2.3 設(shè)A，B是任意兩個集合，屬于A的而不屬于B的元素組成的集合S，稱為B對于A的補(bǔ)集，也叫B對于A的相對補(bǔ)集。記為A-B S = A-B=x |xAxB【例】設(shè)A=2, 5, 6, B=1, 2, 4, 7, 9 則A-B=5, 6 定義3-2.4 設(shè)E是全集, 對任一集合A關(guān)于E的補(bǔ)E-A，稱為集合A的絕對補(bǔ)，記為A。 A=E-A=x |xExA=x | xA 集合補(bǔ)運(yùn)算的一些性質(zhì)a) (A)= Ab)E= c) =Ed)A A=Ee)A A= 定理3-2.4 設(shè)A,B為任意兩個集合,

13、則下列關(guān)系成立 a) (A B) = A B b) (A B) = A B 定理3-2.5 設(shè)A,B為任意兩個集合, 則下列關(guān)系成立 a) A-B = A B b) A-B = A-(A B) 定理3-2.6 設(shè)A, B, C為三個集合, 則 A (B-C) = (A B) (A C) 定理3-2.7 設(shè)A, B為兩個集合, 若A B, 則 a) B A b) (B-A) A=B 集合的對稱差 定義3-2.5 設(shè)A，B是任意兩個集合，由 A中元素或B中元素，但不是A與B的公共元素組成的集合S，稱為A和B的對稱差，記為A B。 S=A B=x |(xA) (xB) =(A-B) (B-A)=(A

14、B)-(AB)【例】令A(yù)=1,2,3,4， B= 1,2,5,6，則 A B=3,4,5,6 集合的對稱差運(yùn)算有如下性質(zhì) a) A B=B A b) A = A c) A A= d) A B = (A B) (B A) e) (A B) C = A (B C) 作業(yè) (3) (4) (8) 3.3 包含排斥原理 有限個元素的計數(shù)問題 - 包含排斥原理 設(shè)A1,A2是兩個有限集, 元素個數(shù)定義為|A1|和|A2|, 則 |A1 A2| |A1|+|A2| |A1 A2| min(|A1|, |A2|) |A1-A2| |A1|-|A2| | A1 A2 | = |A1|+|A2|-2 |A1 A

15、2| l定理3-3.1 設(shè)A1,A2為有限集合, 其元素個數(shù)分別為|A1|和|A2|, 則 |A1 A2| = |A1|+|A2|- |A1 A2| 【例】有100名程序員，其中47名熟悉Fortran語言，35名熟悉Pascal語言，23名熟悉這兩種語言。問有多少人對這兩種語言都不熟悉。 解: 設(shè)A、B分別表示熟悉Fortran和Pascal語言的程序員集合, 則 |A| = 47; |B| = 35; |A B| = 23 |A B| = |A|+|B|- |A B| = 47+35-23=59 | (A B)| = 100-59=41 三個集合有沒有類似的結(jié)果? 對于任意三個集A1，A2

16、，A3, 有： A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2A3【例】某工廠裝配30輛汽車, 可供選擇的設(shè)備有收音機(jī), 空氣調(diào)節(jié)器和對講機(jī). 現(xiàn)已知其中15輛汽車有收音機(jī), 8輛有空氣調(diào)節(jié)器, 6輛有對講機(jī), 而且其中3輛汽車這三樣設(shè)備都有, 則至少有幾輛汽車什么設(shè)備都沒有? 推廣到一般情況 定理3-3.2 設(shè)A1,A2, , An為有限集, 其元素個數(shù)分別為|A1|, |A2|,|An|, 則【例】求1到250之間能被2,3,5,7任何一個整除的整數(shù)個數(shù)=njijiniinAAAAAA1121|nkjikjiAAA1|) 1(211nnAAA 作業(yè) (4

17、) (5) 3.4 序偶與笛卡爾積 在日常生活中, 許多事物是成對出現(xiàn)的, 且具有一定的順序 【例】上,下; 左,右; 34; 平面上的點(diǎn)坐標(biāo) 具有固定次序的客體組成一個序偶 序偶表達(dá)兩個客體之間的關(guān)系【例】; ; ; 序偶可以看作有兩個元素的集合, 但其具有次序, 即a,b=b,a 但 定義3-4.1兩個序偶和相等, 當(dāng)且僅當(dāng)x=u, y=v 序偶的次序一旦確定就不能再變了.序偶中, a 稱為第一元素, b 稱為第二元素 序偶的推廣 三元組 三元組是一個序偶, 其第一元素本身也是一個序偶, 表示為,z 兩個三元組,z和,w相等, 當(dāng)且僅當(dāng)x=u, y=v, z=w 簡記為 四元組 四元組是一

18、個序偶, 其第一元素是一個三元組, 表示為,w 兩個四元組,w和,s相等, 當(dāng)且僅當(dāng)x=p, y=q, z=r, w=s 簡記為 n元組 n元組是一個序偶, 其第一元素是一個n-1元組, 表示為,xn 兩個n元組,xn和,yn相等, 當(dāng)且僅當(dāng)x1=y1, x2=y2, , xn=yn 簡記為 序偶其元素可以屬于兩個不同的集合, 任給兩個集合A,B, 可以定義一種序偶的集合 定義3-4.2 令A(yù)和B是任意兩個集合, 若序偶的第一元素屬于A, 而第二元素屬于B, 所有這樣的序偶構(gòu)成的集合稱為集合A和B的笛卡爾積或直積, 記作A B , A B= | (x A) (xB)【例】A=a,b, B=1,

19、2,3, 則A B, B A, A A, B B 注 A B B A 若A= 或B= , 則A B = (A B ) C A ( B C) 定理3-4.1 設(shè)A,B,C為任意三個集合, 則 a) A (B C)=(A B ) (A C ) b) A (B C)=(A B ) (A C ) c) (A B) C= (A C) (B C) d) (A B) C= (A C) (B C) 定理3-4.2 若C , 則 A B (A C B C ) (C A C B) 定理3-4.3 設(shè)A,B,C,D為四個非空集合, 則 A B C D當(dāng)且僅當(dāng)A C, B D 兩個集合的笛卡爾積仍然是集合，故可以和其

20、它集合繼續(xù)做笛卡爾積 約定 A1 A2 A3= (A1 A2) A3; A1 A2 A3 A4= (A1 A2 A3) A4 一般地， A1 A2 An= (A1 A2 An-1) An = | (x1 A1) (x2 A2) (xn An) A1 A2 An可以看成是n元組構(gòu)成的集合 AA簡記為A2； 一般地，A A A簡記為An 作業(yè) (3) a)、b)、c) (4) 3.5 關(guān)系及其表示 日常生活中我們常用如：兄弟關(guān)系， 上下級關(guān)系等來表示集合中兩個元素的關(guān)系 序偶可以表達(dá)兩個客體，甚至n個客體間的關(guān)系 可以用序偶表示關(guān)系【例】電影票與座位之間的關(guān)系 X表示電影票集合 Y 座位集合 則對

21、任意的x X和y Y, 必有x與y有 “對號”關(guān)系或x與y無 “對號”關(guān)系 令R表示“對號”關(guān)系，則上述問題可表述為xRy或x y 對號關(guān)系是序偶的集合，也是X Y的子集R 定義3-5.1 任一序偶的集合S確定了一個二元關(guān)系R，R中任一序偶可記作 R或xRy. 不在S中的任一序偶可記作 R或x y【例】實數(shù)中“”關(guān)系可記作 | x,y是實數(shù)且xy 定義3-5.2 令R為二元關(guān)系，由 R的所有x組成的集合dom R稱為R的前域，即 dom R= x | (y)( R) 使 R的所有y組成的集合ran R稱為R的值域，即 ran R= y | (x)( R) R的前域和值域一起稱作R的域，記作FL

22、D R, 即 FLD R= dom R ran R R 【例】A=1,2,3,5, B=1,2,4, H=, 則 dom H=1,2,3 ran H=2,4 FLD H=1,2,3,4 定義 3-5.3 令X和Y是任意兩個集合，直積X Y的子集R稱為X到Y(jié)的關(guān)系 如R是X到Y(jié)的關(guān)系，則 dom R X ran R Y R X Y FLD R X Y 特例 R= ，則R稱為空關(guān)系 R= X Y, 則R稱為全域關(guān)系 當(dāng)X=Y時，關(guān)系R是X X的子集，R稱為在X上的二元關(guān)系【例】X=1,2,3,4, 求X上的關(guān)系 “” 所求的二元關(guān)系為, , , , , 定義3-5.4 設(shè)IX是X上的二元關(guān)系且滿足

23、Ix= | x X, 則稱IX是X上的恒等關(guān)系【例】A=1,2,3,4, 則IA=, , , 【例】設(shè)X=1,2,3,4，X上的二元關(guān)系H和S定義如下： H=x,y | 是整數(shù) S=x,y | 是正整數(shù) 試求HS，HS，H，S-H 解：解：H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2 S=4,1 HS=1,1,1,3,2,2,2,4,3,3,3,1,4,4, 4,2,4,1 HS= H=X2- H=1,2,1,4,2,1,2,3,3,2,3,4, 4,3,4,1 SH=4,1 定理3-5.1 若Z和S是從集合X到集合Y的兩個關(guān)系，則Z,S的并、交、補(bǔ)、差仍為X到集合Y的關(guān)

24、系2yx 3yx 設(shè)R是從X到Y(jié)的一個二元關(guān)系，如果X和Y都是有限集，則除了用序偶集合表示之外，還有如下兩種表示法 矩陣表示法 如果X，Y是有限集， X=a1,a2,am， Y=b1,b2,bn， R是X到Y(jié)的二元關(guān)系，R的關(guān)系矩陣定義為： MR= rijmn 其中，RRbbaarjjiiij=,01【例】設(shè)A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元關(guān)系，定義為： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2 則R的關(guān)系矩陣為MR= 011001110101【例】設(shè)A=1,2,3,4，R是A的二元關(guān)系，定義為：R=1,1,1,2

25、,2,1,3,2,3,1,4,3,4,2,4,1則R的關(guān)系矩陣為： 上例中的二元關(guān)系R是A上的二元關(guān)系，只需看成A到A的二元關(guān)系，利用上述定義，就可以方便地寫出它的關(guān)系矩陣。A上的二元關(guān)系和A到B的二元關(guān)系的關(guān)系矩陣的定義是相同的。=0111001100010011RM 圖表示法 如果A和B是有限集，R是A到B二元關(guān)系，還可以用圖表示二元關(guān)系R。表示二元關(guān)系R的圖叫做R的關(guān)系圖。A到B二元關(guān)系的關(guān)系圖和A上的二元關(guān)系的關(guān)系圖的定義是不一樣的。分別描述如下： A到B二元關(guān)系R的關(guān)系圖 設(shè)A=a1,a2,am，B=b1,b2,bn，R是A到B二元關(guān)系，R的關(guān)系圖的繪制方法如下： 畫出m個小圓圈表示

26、A的元素，再畫出n個小圓圈表示B的元素。這些小圓圈叫做關(guān)系圖的結(jié)點(diǎn)。 如果ai,bj R，則從ai到bj畫一根有方向(帶箭頭)的線。這些有方向(帶箭頭)的線叫做關(guān)系圖的弧。 【例】設(shè)A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元關(guān)系，定義為： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2 則R的關(guān)系圖如下圖所示A上的二元關(guān)系R的關(guān)系圖設(shè)A=a1,a2,am，R是A上的二元關(guān)系，其關(guān)系圖如下繪制:畫出m個小圓圈表示A的元素。如果ai,ajR，則從ai到aj畫一根有方向(帶箭頭)的線?！纠吭O(shè)A=1,2,3,4，R是A的二元關(guān)系，定義為

27、：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1則R的關(guān)系圖為： 作業(yè) (5) b)、d) (6) (7) 3.6 關(guān)系的性質(zhì) 有些關(guān)系具有比較特別的性質(zhì), 如恒等關(guān)系1. 自反的 定義3-6.1 設(shè)R為定義在集合X上的二元關(guān)系, 如果對于每個xX, 有 R, 則稱R是自反的 R是自反的當(dāng)且僅當(dāng)(x)(xXx,xR) 自反關(guān)系R的關(guān)系矩陣和關(guān)系圖 R的關(guān)系矩陣MR的主對角線全為1 R的關(guān)系圖中每一個結(jié)點(diǎn)上都有自回路。【例】設(shè)X=1,2,3，X上的二元關(guān)系 R=1,1,2,2,3,3,1,2R是自反的,它的關(guān)系圖如下圖所示，關(guān)系矩陣如下： 注意：對于自反關(guān)系R, 必須是對于每

28、個xA,都去檢驗是否有 R 定理 設(shè)R是X上的二元關(guān)系，R是自反的當(dāng)且僅當(dāng)IXR。1000100112. 對稱的 定義3-6.2 設(shè)R為定義在集合X上的二元關(guān)系, 如果對于每個x,yX, 每當(dāng) R, 就有 R, 則稱R是對稱的。 R在X上對稱當(dāng)且僅當(dāng) (x)(y)(xXyXx,yRy,xR) 對稱關(guān)系R的關(guān)系矩陣和關(guān)系圖 R的關(guān)系矩陣MR是對稱矩陣 在R的關(guān)系圖中，如果兩個不同的結(jié)點(diǎn)間有弧，一定有方向相反的弧【例】設(shè)X=1,2,3，X上的二元關(guān)系R=1,2,2,1,3,3，R是對稱的。它的關(guān)系圖如下圖所示，關(guān)系矩陣如下：【例】設(shè)A=1,3,5,7，定義A上的二元關(guān)系如下： R=a,b|(ab)

29、/2是整數(shù) 試證明R在A上是自反的和對稱的。1000010103. 傳遞的 定義3-6.3 設(shè)R為定義在集合X上的二元關(guān)系, 如果對于任意x,y,zX, 每當(dāng) R和 R, 就有 R, 則稱R是傳遞的。 R在X上是傳遞的當(dāng)且僅當(dāng) (x)(y)(z)(xXyXzXx,yRy,zR x,zR)【例】設(shè)R是實數(shù)集合， S=x,y|xRyRxy 是實數(shù)集合上的大于關(guān)系。 證明實數(shù)集合上的大于關(guān)系是傳遞的。4. 反自反 定義3-6.4 設(shè)R為定義在集合X上的二元關(guān)系, 如果對于每個xX, 有 R, 則稱R是反自反的 R是反自反的當(dāng)且僅當(dāng)(x)(xXx,xR) 反自反關(guān)系R 的關(guān)系矩陣和關(guān)系圖 R的關(guān)系矩陣

30、MR的主對角線全為0 在R的關(guān)系圖中每一個結(jié)點(diǎn)上都沒有自回路【例】設(shè)X=1,2,3，X上的二元關(guān)系R=1,2,2,3,3,1，R是反自反的,它的關(guān)系圖如下圖所示，關(guān)系矩陣如下：【例】設(shè)R是實數(shù)集合， =x,y| xRyRxy是實數(shù)集合上的小于關(guān)系。證明實數(shù)集合上的小于關(guān)系是反自反的。001100010 注 一個關(guān)系若是自反的，則一定不是反自反。反之亦然。 一個關(guān)系可以既不是自反的，也不是反自反的。 定理 設(shè)R是X上的二元關(guān)系, R是反自反的當(dāng)且僅當(dāng)RIX=。【例】設(shè)A=1,2,3，定義A上的二元關(guān)系如下： R=1,1,2,2,3,3,1,3 S=1,3 T=1,1試說明R，S，T是否是A上的自

31、反關(guān)系或反自反關(guān)系。自反的反自反的不是自反的,也不是反自反的5. 反對稱 定義3-6.5 設(shè)R為定義在集合X上的二元關(guān)系, 如果對于每個x,yX, 每當(dāng) R和 R,必有x=y, 則稱R是反對稱的。 R在X上反對稱當(dāng)且僅當(dāng) (x)(y)(xXyXx,yRy,xR(x=y)x,yRy,xR(x=y) (x=y)(x,yRy,xR) (x=y)(x,yRy,xR) (x=y)x,yR)y,xR (xy)x,yR)y,xR (xy)x,yRy,xR x,yR(xy)y,xR由此，反對稱的定義又可以等價的描述為： (x)(y)(xXyXx,yR(xy)y,xR) 反對稱關(guān)系R 的關(guān)系矩陣和關(guān)系圖 在R的

32、關(guān)系矩陣MR中以主對角線為軸的對稱位置上不能同時為1(主對角線除外) 在R的關(guān)系圖中每兩個不同的結(jié)點(diǎn)間不能有方向相反的兩條弧【例】設(shè)X=1,2,3，X上的二元關(guān)系R=1,2,2,3,3,3，R是反對稱的。它的關(guān)系圖如下圖所示，關(guān)系矩陣如下：100100010 注 一個關(guān)系可以既是對稱的，又是反對稱的。 一個關(guān)系可以既不是對稱的，又不是反對稱的。 【例】 設(shè)A=1,2,3，定義A上的二元關(guān)系如下： R=1,1,2,2 S=1,1,1,2,2,1 T=1,2,1,3 U=1,3,1,2,2,1試說明R，S，T，U是否是A上的對稱關(guān)系和反對稱關(guān)系。既是對稱的,也是反對稱的對稱的,不是反對稱的反對稱的

33、,不是對稱的既不是對稱的,也不是反對稱的【例】設(shè)R，S是X上的二元關(guān)系，證明 若R，S是自反的，則RS和RS也是自反的。 若R，S是對稱的，則RS和RS也是對稱的。 若R，S是傳遞的，則RS也是傳遞的。 注若R，S是傳遞的，則RS不一定是傳遞的?！纠?X=1,2,3,4 S=, , R=, , 則R，S是傳遞的，但RS不是傳遞的 作業(yè) (1) (6) 3.7 復(fù)合關(guān)系和逆關(guān)系 二元關(guān)系是以序偶為元素的集合 對其進(jìn)行集合的運(yùn)算（并、交、補(bǔ)、對稱差等）可以得到新的集合，即可得到新的二元關(guān)系 對于二元關(guān)系還可以進(jìn)行其它運(yùn)算關(guān)系的復(fù)合關(guān)系的逆1.關(guān)系的復(fù)合運(yùn)算 定義 3-7.1 設(shè)R為X到Y(jié)的關(guān)系，

34、S為從Y到Z的關(guān)系，則R S稱為R和S的復(fù)合關(guān)系，表示為 R S =x,zxXzZ(y)(yYx,yRy,zS)【例】 X=1,2,3,4,5，X上的二元關(guān)系R和S定義如下： R=1,2,3,4,2,2 S=4,2,2,5,3,1,1,3試求R S，S R可以類推得到兩個以上關(guān)系的復(fù)合, 并有結(jié)合律, 即(R S) P = R (S P) 【例】 求上例的R (S R)，(R S) R，R R，S S，R R R 注 復(fù)合運(yùn)算不滿足交換律，即R SS R 關(guān)系R本身所組成的復(fù)合關(guān)系可以寫成： R R， R R R，, 簡記為R(2), R(3), R(m), 一般地，R(m-1) R=R(m)

35、mRRR 復(fù)合關(guān)系用矩陣表示設(shè)R是從X=x1,x2, ,xm到Y(jié)=y1,y2, ,yn的一個二元關(guān)系，則其關(guān)系矩陣MR=uij為設(shè)S是從Y=y1,y2, ,yn到Z=z1,z2, ,zP的一個二元關(guān)系，則其關(guān)系矩陣MS=vij為RRyyxxujjiiij=,01SSzzyyvjjiiij=,01R S表示R和S的復(fù)合關(guān)系，表示從X到Z的二元關(guān)系，其關(guān)系矩陣 MR S =wijwij和uij、vij的關(guān)系如下：將上述關(guān)系用矩陣符號記為： MR S =MR MS 矩陣運(yùn)算“ ”叫做關(guān)系矩陣MR和MS的布爾乘法。SSRRzzxxwjjiiij=,01)(1kjiknkijvuw= 代表邏輯乘，滿足：

36、 0 0=0， 01=0， 10=0， 11=1 代表邏輯加，滿足 0 0=0， 0 1=1， 1 0=1， 1 1=1 把關(guān)系矩陣的布爾乘法公式 與線性代數(shù)中的矩陣乘法公式相比，發(fā)現(xiàn)，只要把矩陣乘法公式中的數(shù)乘改為邏輯乘，把數(shù)加改為邏輯加，就得到了關(guān)系矩陣的布爾乘法公式。)(1kjiknkijvuw=【例】A=1,2,3,4,5，A上的二元關(guān)系R和S定義如下： R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2試求MR S和MR MS，它們是否相等 ? 解：按照R 和S的定義，求出 R S=1,5,3,2,2,5 寫出R 、S和R S關(guān)系矩陣如下： MR= MS= MR S=00

37、0000000001000000100001000000000100000110000001000000000000000101000010000 MR MS= = M R S =所以MR S=MR MS 00000000000100000010000100000000010000011000000100000000000000010100001000000000000000001010000100002. 關(guān)系的逆 定義 3-7.2 設(shè)R為從X到Y(jié)的二元關(guān)系，如將R中每一序偶的元素順序互換，所得到的集合稱為R的逆關(guān)系，記為Rc, 即 Rc =y,xx,yR【例】1. 自然數(shù)集合上的關(guān)系“”

38、2. 設(shè)X=1,2,3,4，Y=a,b,c，X到Y(jié)二元關(guān)系 R=1,a,2,b,4,c， 則 Rc=a,1,b,2,c,4注 (Rc)c = R 定理 3-7.1 設(shè)R,R1,R2是從A到B的二元關(guān)系，則下列各式成立 a) (R1R2)c = R1c R2c b) (R1R2)c = R1c R2c c) (AB)c = BA d) , 其中 e) (R1-R2)c = R1c - R2c 定理 3-7.2 設(shè)T為從X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，證明(T S)c = Sc TcccRR=)(RBAR= 定理 3-7.3 設(shè)R為X上的二元關(guān)系，則 a) R是對稱的，當(dāng)且僅當(dāng)R = Rc b)

39、 R是反對稱的，當(dāng)且僅當(dāng)RRc IX 關(guān)系的逆用矩陣表示和圖表示 Rc的關(guān)系矩陣 是R的關(guān)系矩陣MR的轉(zhuǎn)置矩陣，即 將R關(guān)系圖中的弧線的箭頭反置，就可以得到Rc關(guān)系圖?！纠吭O(shè)X=1,2,3,4，Y=a,b,c，X到Y(jié)二元關(guān)系 R=1,a,2,b,4,c， 試求Rc，寫出MR和 ，驗證cRMTRRMMc=CRMTRRMMc=R和Rc的關(guān)系矩陣是：R和Rc的關(guān)系圖是：=100000010001RM=100000100001cRM 作業(yè) (1) (3) (6) 3.8 關(guān)系的閉包運(yùn)算 給定一個集合上的關(guān)系，擴(kuò)充一些序偶可以得到一些具有特殊性質(zhì)的關(guān)系 閉包運(yùn)算 定義 3-8.1 設(shè)R是X上的二元關(guān)系

40、，如果有另一個關(guān)系R滿足： a) R是自反的(對稱的，可傳遞的) b) R R c) 對于任何自反的(對稱的，可傳遞的)關(guān)系R ，如果有R R, 就有R R 則稱關(guān)系R 為R的自反(對稱，傳遞)閉包，記為 r(R) (s(R), t(R) 對于一個不是自反的(對稱的，可傳遞的)二元關(guān)系，可以通過擴(kuò)充序偶的方法得到它的自反(對稱，傳遞)閉包 自反(對稱，傳遞)閉包是包含R的最小的自反(對稱，傳遞)閉包 當(dāng)二元關(guān)系R是自反(對稱，傳遞)的，求R的自反(對稱，傳遞)閉包方法由下面的定理給出了。 定理3-8.1 設(shè)R是X上的二元關(guān)系，那么 a) R是自反的，當(dāng)且僅當(dāng)r(R) = R b) R是對稱的，

41、當(dāng)且僅當(dāng)s(R) = R c) R是傳遞的，當(dāng)且僅當(dāng)t(R) = R 當(dāng)二元關(guān)系R不是自反的時候，下面的定理給出了求其自反閉包的方法 定理3-8.2 設(shè)R是集合X上的二元關(guān)系，則 r(R) = R IX 當(dāng)二元關(guān)系R不是對稱的時候，下面的定理給出了求其對稱閉包的方法 定理3-8.3 設(shè)R是集合X上的二元關(guān)系，則 s(R) = R Rc 當(dāng)二元關(guān)系R不是傳遞的時候，下面的定理給出了求其傳遞閉包的方法 定理3-8.4 設(shè)R是集合X上的二元關(guān)系，則 t(R) =RR(2)R(3)=R+【例】設(shè)A=1,2,3，定義A上的二元關(guān)系R為： R=1,2,2,3,3,1 試求：r(R)，s(R)，t(R) 解

42、：r(R)= RIA=1,2,2,3,3,1,1,1,2,2,3,3 s(R)=RRc=1,2,2,3,3,1,2,1,3,2,1,3 R(2)= R R=1,3,2,1,3,2 R(3)= R(2) R =1,1,2,2,3,3=IA R(4)= R3 R = IA R=R t(R)= RR(2) R(3) = 1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3 定理3-8.5 設(shè)X是含有n個元素的集合，R是X上的二元關(guān)系，則存在一個整數(shù)kn，使得 t(R) =RR(2)R(3) R(k) 求一個二元關(guān)系R的傳遞閉包可以簡單的求RR(2)R(3) R(n)【例】設(shè)A=1

43、,2,3，定義A上的二元關(guān)系R為：R=1,2,2,3,3,1試用關(guān)系矩陣求傳遞閉包t(R)。=001100010RM=010001100001100010001100010)2(RRRMMM=100010001001100010010001100)2()3(RRRMMM=111111111)3()2()(RRRRtMMMM其中，表示矩陣的對應(yīng)元素進(jìn)行析取運(yùn)算。 求傳遞閉包的簡易算法1.置新矩陣A:=M;2.置i:=1;3.對所有j如果Aj,i = 1, 則對k=1,2,n Aj,k:=Aj,kAi,k 4.i加1;5.如果in, 轉(zhuǎn)步驟3, 否則停止【例】已知關(guān)系矩陣 求t(R)=001010

44、0001010010M0010100001110010011110000111011111111000111111111111111111111111 定理3-8.6 設(shè)X是集合，R是X上的二元關(guān)系，則 a) rs(R)=sr(R) b) rt(R)=tr(R) c) st(R)ts(R) 作業(yè) (2) (5) c) (7) 3.9 集合的劃分和覆蓋 對集合的研究，有時要把一個集合分成若干子集進(jìn)行討論 定義3-9.1 若把一個集合A分成若干個叫做分塊的非空子集，使得A中每個元素至少屬于一個分塊，那么這些分塊的全體構(gòu)成的集合叫做A的一個覆蓋。如果A中每個元素屬于且僅屬于一個分塊，那么這些分塊的全

45、體構(gòu)成的集合叫做A的一個劃分(或分劃)【例】A=1,2,3,4,5,6,7,8,9 S1=1,2,3 S2=2,3,4,5,6 S3=4,5,6,7 S4=6,7,8 S5=8,9 則 S1,S2,S3,S4,S5是A的一個覆蓋 而S1,S3,S5是A的一個劃分 形式化定義 定義3-9.1 令A(yù)為給定非空集合，S=S1,S2,Sm, 其中Si A, Si(i=1,2,m)且 , 集合S稱為集合A的覆蓋 如果附加條件SiSj=(ij), 則稱S是A的劃分(或分劃)【例】A=a,b,c S=a,b, b,c Q=a, a,b, a,c D=a, b,c G=a,b,c E=a, b, c F=a,

46、 a,c 則S,Q,D,G,E是A的覆蓋 其中D,G,E是A的劃分 F既不是劃分也不是覆蓋ASmii=1 注 若是劃分則必是覆蓋 一個集合的最小劃分是由這個集合的全部元素組成的一個分塊集合 一個集合的最大劃分是由每個元素構(gòu)成一個單元素分塊的集合 一個集合的劃分不唯一 定義3-9.2 若A1,A2,Ar與B1,B2,Bs是同一個集合A的兩種劃分，則其中所有AiBj組成的集合，稱為是原來兩種劃分的交叉劃分?！纠克猩锏募蟈，可分割為P,A, 其中P表示植物的集合，A表示動物的集合。 X也可分割為E,F, 其中E表示史前生物的集合，F(xiàn)表示史后生物的集合。 則它們的交叉劃分為P E, P F,

47、A E, A F, 其中 P E：史前植物的集合 P F：史后植物的集合 A E：史前動物的集合 A F：史后動物的集合 定理3-9.1設(shè)A1,A2,Ar與B1,B2,Bs是同一集合X的兩種劃分，則其交叉劃分也是X的一種劃分 定義3-9.3 給定X的任意兩個劃分A1,A2,Ar與B1,B2,Bs，若對于每個Aj均有Bk使得Aj Bk，則A1,A2,Ar稱為是B1,B2,Bs的加細(xì)【例】X=a,b,c,d,e,f,g S = a,b,c, d,e, f,g 和 D = a,b, c, d,e, f, g 是X的兩 個劃分 則D是S的加細(xì) 定理3-9.2 任何兩種劃分的交叉劃分，都是原來劃分的一種

48、加細(xì) 作業(yè) (2) (5) 3.10 等價關(guān)系與等價類 等價關(guān)系是最重要、最常見的二元關(guān)系之一。它有良好的性質(zhì)。在計算機(jī)科學(xué)和計算機(jī)技術(shù)、信息科學(xué)和信息工程中都有廣泛的應(yīng)用。 定義3-10.1 設(shè)R為定義在集合A上的一個關(guān)系，若R是自反的，對稱的和傳遞的，則R稱為等價關(guān)系 等價關(guān)系的關(guān)系矩陣和關(guān)系圖 關(guān)系矩陣主對角線全為1且是對稱陣； 關(guān)系圖每一個結(jié)點(diǎn)上都有自回路且每兩個結(jié)點(diǎn)間如果有弧，一定有方向相反的兩條弧。 【例】設(shè)A=1,2,3,4,5，R是A上的二元關(guān)系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， 證明R是A上的等價關(guān)系。 證法一：用關(guān)系矩陣說明R是

49、等價關(guān)系 R的關(guān)系矩陣MR如下： MR的主對角線全為1且是對稱陣，所以R是自反的和對稱的；還可以用二元關(guān)系傳遞性的定義證明R是傳遞的。故R是A上的等價關(guān)系。=1000001100011000001100011RM證法二：用關(guān)系圖說明R是等價關(guān)系 在R的關(guān)系圖中每一個結(jié)點(diǎn)上都有自回路；每兩個結(jié)點(diǎn)間如果有弧，一定有方向相反的兩條弧。所以R是自反的和對稱的。與前面一樣，也可以用二元關(guān)系傳遞性的定義證明R是傳遞的。故R是A上的等價關(guān)系等價關(guān)系R的關(guān)系圖被分為三個互不連通的部分。每部分中的結(jié)點(diǎn)兩兩都有關(guān)系，不同部分中的任意兩個結(jié)點(diǎn)則沒有關(guān)系?！纠?設(shè)R=x,y xIyIx y mod k是整數(shù)集合I上

50、的二元關(guān)系。證明R是等價關(guān)系。 證明：設(shè)a,b,c是任意的整數(shù)。 因為 a-a=k0，所以 aa mod k，a,aR。故R是自反的。 若a,bR，a b mod k，a-b = kt，tI，b-a =-(a-b)=k(t)，tI，ba mod k，b,aR。故R是對稱的。 若a,bR且b,cR， a-b = kt1，t1I，b-c = kt2， t2 I， a-c=(a-b)+(b-c)=kt1+kt2=k(t1+t2)，t1+t2I，a,cR，故R是傳遞的。 所以R是整數(shù)集合I上的等價關(guān)系。 定義3-10.2 設(shè)R是集合A上的等價關(guān)系，對任何aA，集合aR = x xAaRx 稱為元素a形

51、成的R等價類 任意一個元素的等價類非空，包含該元素【例】設(shè)A=1,2,3,4,5，R是A上的二元關(guān)系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， R是A上的一個等價關(guān)系 其等價類為1R=2R=1,2; 3R=4R=3,4; 5R=5【例】 設(shè)R=x,y xIyIx y mod 3是整數(shù)集合I上的二元關(guān)系。 R是等價關(guān)系, 其等價類為 0R=,-6,-3,0,3,6, 1R=,-5,-2,1,4,7, 2R=,-4,-1,2,5,8, 定理3-10.1設(shè)給定集合A上的等價關(guān)系R，對于a,b A有 R當(dāng)且僅當(dāng)aR=bR 定義3-10.3 集合A上的等價關(guān)系R,

52、其等價類集合aR | a A稱作A關(guān)于R的商集，記作A/R【例】設(shè)A=1,2,3,4,5，R是A上的二元關(guān)系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， R是A上的一個等價關(guān)系 A的關(guān)于R的商集A/R為1R, 3R, 5R【例】 設(shè)R=x,y xIyIx y mod 3是整數(shù)集合I上的二元關(guān)系。 R是等價關(guān)系,I關(guān)于R的商集I/R為0R,1R, 2R 在商集I/R中，0R 1R,2R=I, 且任意兩個等價類的交為 定理3-10.2 集合A上的等價關(guān)系R，決定了A的一個劃分，該劃分就是商集A/R 定理3-10.3 集合A的一個劃分確定A的元素間的一個等價關(guān)系【

53、例】設(shè)X=1,2,3,4，X的劃分S=1，2,3，4，試寫出S導(dǎo)出的等價關(guān)系R。 解：R=1,1,2,2,2,3,3,2,3,3,4,4 =112,32,344可以驗證R是X上的等價關(guān)系。 定理3-10.4 設(shè)R1和R2為非空集合A上的等價關(guān)系, 則R1=R2當(dāng)且僅當(dāng)A/R1=A/R2【例】設(shè)X=1,2,3，寫出集合X上的所有等價關(guān)系。 解：先寫出集合X上的所有劃分，它們是： S1=1,2,3， S2=1,2,3， S3=1,3,2 S4=2,3,1, S5=1,2,3 對應(yīng)的等價關(guān)系為： R1=1,2,31,2,3 R2=1,21,233 =1,1,1,2,2,1,2,2, 3,3 R3=1

54、,31,322 =1,1,1,3,3,1,3,3,2,2 R4=2,32,311 =2,2,2,3,3,2,3,3,1,1 R5=112233=1,1,2,2,3,3 作業(yè) (3) (4) (10) 3.11 相容關(guān)系 定義3-11.1 給定集合A上的關(guān)系r，若r是自反的，對稱的，則稱r是相容關(guān)系 所有的等價關(guān)系都是相容關(guān)系 相容關(guān)系的關(guān)系矩陣和關(guān)系圖 相容關(guān)系的關(guān)系矩陣主對角線全為1且是對稱陣。 相容關(guān)系的關(guān)系圖每一個結(jié)點(diǎn)上都有自回路且每兩個結(jié)點(diǎn)間如果有邊，一定有方向相反的兩條邊?！纠吭O(shè)A=316,347,204,678,770，A上的二元關(guān)系r定義為：r=x,y| xAyAx和y有相同數(shù)

55、碼，證明r是A上的相容關(guān)系。寫出關(guān)系矩陣和關(guān)系圖。用關(guān)系矩陣和關(guān)系圖驗證r是A上的相容關(guān)系。 證明證明: (1) 集合A中的每個數(shù)自己和自己有相同數(shù)碼，故r是自反的； (2) 對于集合A中任意x和y，如果x和y有相同數(shù)碼，則y和x也有相同數(shù)碼。故r是對稱的。于是，r是相容關(guān)系。 令a=316，b=347，c=204，d=678，e=770 用列舉法將R表示為： r=a,a,a,b,a,d,b,a,b,b,b,c,b,d, b,e,c,b,c,c,c,e,d,a,d,b,d,d, d,e,e,b,e,c,e,d,e,er的關(guān)系矩陣Mr如下：Mr是一個對角線全為1的對稱矩陣，所以r是相容關(guān)系r的關(guān)

56、系圖如上圖：關(guān)系圖每一個結(jié)點(diǎn)上都有自回路且每兩個結(jié)點(diǎn)間如果有邊，一定有方向相反的兩條邊。所以r是相容關(guān)系=1111011011101101111101011RM 對于相容關(guān)系的關(guān)系矩陣一般用梯形表示，如上例中的相容關(guān)系r的關(guān)系矩陣就可表示為 1111011011101101111101011111011110101111 對于相容關(guān)系的關(guān)系圖也可簡化 省去每一個結(jié)點(diǎn)上的自回路，將兩個結(jié)點(diǎn)間方向相反的兩條有向邊改為一條無向邊，得到一個簡化圖。此圖叫做R的相容關(guān)系圖。 如上例中的相容關(guān)系r的關(guān)系圖可表示為 定義3-11.2 設(shè)r是集合A上的相容關(guān)系，若C A, 如果對于C中任意兩個元素a1和a2，

57、有a1ra2，則稱C是由相容關(guān)系r產(chǎn)生的相容類 注 相容類C一定是A的子集。 aA，因為相容關(guān)系r是自反的，a,ar，所以a是由相容關(guān)系r產(chǎn)生的一個相容類。即A中的任何元素組成的單元素集是由相容關(guān)系r產(chǎn)生的一個相容類?！纠肯嗳蓐P(guān)系r=a,a,a,b,a,d,b,a,b,b,b,c,b,d, b,e,c,b,c,c,c,e,d,a,d,b,d,d, d,e,e,b,e,c,e,d,e,e a,a,b,b,c,b,d,e都是R產(chǎn)生的相容類。 a,bd=a,b,d和b,ce=b,c,e也是R產(chǎn)生的相容類。 但b,d,e與任何非空集合的并集都不再是R產(chǎn)生的相容類 定義 3-11.3 設(shè)r是集合A上的

58、相容關(guān)系，不能真包含在任何其它相容類中的相容類，稱為最大相容類，記為Cr 注 Cr中任意元素x與Cr中的所有元素都有相容關(guān)系r。 X-Cr中沒有一個元素與Cr中的所有元素都有相容的關(guān)系r。 利用相容關(guān)系的簡化關(guān)系圖可以求最大相容類，方法如下： (1) 最大完全多邊形的頂點(diǎn)構(gòu)成的集合是最大相容類。 (2) 孤立點(diǎn)構(gòu)成的集合是最大相容類。 (3) 如果一條邊不是任何完全多邊形的邊，則它的兩個端點(diǎn)構(gòu)成的集合是最大相容類。 【例】設(shè)X=1,2,3,4,5,6，r是X上的相容關(guān)系，它的相容關(guān)系圖如下圖所示，試找出所有最大相容類。1. 最大完全3邊形的頂點(diǎn)構(gòu)成的集合：2,3,5和2,3,4。2. 孤立點(diǎn)構(gòu)

59、成的集合：6。3. 不是任何完全多邊形的邊的兩個端點(diǎn)構(gòu)成的集合1,5。最大相容類為:2,3,5，2,3,4，1,5和6。 定理3-11.1 設(shè)r是有限集A上的相容關(guān)系，C是一個相容類，那么比存在一最大相容類Cr，使得C Cr A的任意元素a可以組成相容類a，所以由上述定理可知一定存在一個最大相容類包含a A的所有最大相容類組成的集合構(gòu)成A的一個覆蓋 定義3-11.4 在集合A上給定相容關(guān)系r，其最大相容的集合稱作集合A的完全覆蓋，記作Cr(A)【例】設(shè)X=1,2,3,4,5,6，r是X上的相容關(guān)系，它的相容關(guān)系圖如下圖所示，最大相容類為:2,3,5，2,3,4，1,5和6。這些集合也是X的一個

60、覆蓋，即為集合X的完全覆蓋 定理3-11.2 給定集合A的覆蓋A1,A2,An，由它確定的關(guān)系R=A1A1A2A2 AnAn是相容關(guān)系【例】設(shè)X=1,2,3,4，S1=1,2,3,3,4，S2=1,2,2,3,1,3,3,4是X的兩個覆蓋。試寫出S1和S2 導(dǎo)出的相容關(guān)系R1和R2。 解：R1=1,2,31,2,33,43,4 =1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3,3,4,4, 3,4,4 R2=1,21,22,32,3 1,31,33,43,4 =1,1,1,2,2,1,2,2,2,3,3,2, 3,3,1,3,3,1,3,4,4, 3,4,4 在上例中