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

2、14級全體學生 2.集合B: 全體自然數 集合的性質 集合的元素必須是確定的。所謂確定的，是指任何一個對象是不是集合的元素是明確的、確定的，不能模棱兩可。 集合的元素又是能區分的，能區分的是指集合中的元素是互不相同的。如果一個集合中有幾個元素相同，算做一個。 集合的元素又是無序的，即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是有理數 若用P(x)表示x是有理數，那么Q又可表

3、示為： 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 羅素悖論 設命題函數P(x)表示“x x”，現假設由性質P確定了一個類A, 也就是說“A=x|x x”。 那么現在的問題是：AA是否成立？ 首先，若AA，則A是A的元素，那么A具有性質P，由命題函數P知A A； 其次，若A A，也就是說A具有性質P，而A是由所有具有性質P的類組成的，所以AA。 理發師悖論 在某個城市中有一位理發師，他的廣告詞是這樣寫的：“本人的理發技藝十分高超，譽滿全城。我將為本城所有不給自己刮

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

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

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

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

8、c, 則其所有可能的子集有: S0= S1= a S2= b S3= c S4=a,b S5= b,c S6=c,a S7=a,b,c 冪集 定義3-1.5 設A是集合，A的所有子集構成的集合稱為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 設A為有n個元素的有限集合，則其冪集P (A)有2n個元素 證明: 設A有n個元素，A的子集有： 不含元素的子集一個，即 個。 含一個元素的子集n個，即 個。 含兩個元素的子集 個。 含n個元素的子集 個。

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

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

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

12、A 定理3-2.3 A B, 當且僅當A B=B或A B=A 集合的補 定義3-2.3 設A，B是任意兩個集合，屬于A的而不屬于B的元素組成的集合S，稱為B對于A的補集，也叫B對于A的相對補集。記為A-B S = A-B=x |xAxB【例】設A=2, 5, 6, B=1, 2, 4, 7, 9 則A-B=5, 6 定義3-2.4 設E是全集, 對任一集合A關于E的補E-A，稱為集合A的絕對補，記為A。 A=E-A=x |xExA=x | xA 集合補運算的一些性質 (A)= AE= =EA A=EA A= 定理3-2.4 設A,B為任意兩個集合, 則下列關系成立 a) (A B) = A B

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

14、B= 1,2,5,6，則 A B=3,4,5,6 集合的對稱差運算有如下性質 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) 作業 (3) (4) (8) 3.3 包含排斥原理 有限個元素的計數問題 - 包含排斥原理 設A1,A2是兩個有限集, 元素個數定義為|A1|和|A2|, 則 |A1 A2| |A1|+|A2| |A1 A2| min(|A1|, |A2|) |A1-A2| |A1|-|A2| | A1 A2 | = |A1|+|A2|-2 |A1 A2| l定理3-3.1 設A1,A2為有限集

15、合, 其元素個數分別為|A1|和|A2|, 則 |A1 A2| = |A1|+|A2|- |A1 A2| 【例】有100名程序員，其中47名熟悉Fortran語言，35名熟悉Pascal語言，23名熟悉這兩種語言。問有多少人對這兩種語言都不熟悉。 解: 設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 三個集合有沒有類似的結果? 對于任意三個集A1，A2，A3, 有： A1 A2 A3 A1 A2

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

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

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

19、 B 注 A B B A 若A= 或B= , 則A B = (A B ) C A ( B C) 定理3-4.1 設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 設A,B,C,D為四個非空集合, 則 A B C D當且僅當A C, B D 兩個集合的笛卡爾積仍然是集合，故可以和其它集合繼續做笛卡爾積 約定 A1 A2 A3

20、= (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元組構成的集合 AA簡記為A2； 一般地，A A A簡記為An 作業 (3) a)、b)、c) (4) 3.5 關系及其表示 日常生活中我們常用如：兄弟關系， 上下級關系等來表示集合中兩個元素的關系 序偶可以表達兩個客體，甚至n個客體間的關系 可以用序偶表示關系【例】電影票與座位之間的關系 X表示電影票集合 Y 座位集合 則對任意的x X和y Y, 必有x與y有 “對號

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

22、n 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的關系 如R是X到Y的關系，則 dom R X ran R Y R X Y FLD R X Y 特例 R= ，則R稱為空關系 R= X Y, 則R稱為全域關系 當X=Y時，關系R是X X的子集，R稱為在X上的二元關系【例】X=1,2,3,4, 求X上的關系 “” 所求的二元關系為, , , , , 定義3-5.4 設IX是X上的二元關系且滿足Ix= | x X, 則稱IX是X上的恒等關

23、系【例】A=1,2,3,4, 則IA=, , , 【例】設X=1,2,3,4，X上的二元關系H和S定義如下： H=x,y | 是整數 S=x,y | 是正整數 試求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的兩個關系，則Z,S的并、交、補、差仍為X到集合Y的關系2yx 3yx 設R是從X到Y的一個二元關

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

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

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

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

28、的二元關系，R是自反的當且僅當IXR。1000100112. 對稱的 定義3-6.2 設R為定義在集合X上的二元關系, 如果對于每個x,yX, 每當 R, 就有 R, 則稱R是對稱的。 R在X上對稱當且僅當 (x)(y)(xXyXx,yRy,xR) 對稱關系R的關系矩陣和關系圖 R的關系矩陣MR是對稱矩陣 在R的關系圖中，如果兩個不同的結點間有弧，一定有方向相反的弧【例】設X=1,2,3，X上的二元關系R=1,2,2,1,3,3，R是對稱的。它的關系圖如下圖所示，關系矩陣如下：【例】設A=1,3,5,7，定義A上的二元關系如下： R=a,b|(ab)/2是整數 試證明R在A上是自反的和對稱的。

29、1000010103. 傳遞的 定義3-6.3 設R為定義在集合X上的二元關系, 如果對于任意x,y,zX, 每當 R和 R, 就有 R, 則稱R是傳遞的。 R在X上是傳遞的當且僅當 (x)(y)(z)(xXyXzXx,yRy,zR x,zR)【例】設R是實數集合， S=x,y|xRyRxy 是實數集合上的大于關系。 證明實數集合上的大于關系是傳遞的。4. 反自反 定義3-6.4 設R為定義在集合X上的二元關系, 如果對于每個xX, 有 R, 則稱R是反自反的 R是反自反的當且僅當(x)(xXx,xR) 反自反關系R 的關系矩陣和關系圖 R的關系矩陣MR的主對角線全為0 在R的關系圖中每一個結

30、點上都沒有自回路【例】設X=1,2,3，X上的二元關系R=1,2,2,3,3,1，R是反自反的,它的關系圖如下圖所示，關系矩陣如下：【例】設R是實數集合， =x,y| xRyRxy是實數集合上的小于關系。證明實數集合上的小于關系是反自反的。001100010 注 一個關系若是自反的，則一定不是反自反。反之亦然。 一個關系可以既不是自反的，也不是反自反的。 定理 設R是X上的二元關系, R是反自反的當且僅當RIX=。【例】設A=1,2,3，定義A上的二元關系如下： R=1,1,2,2,3,3,1,3 S=1,3 T=1,1試說明R，S，T是否是A上的自反關系或反自反關系。自反的反自反的不是自反的

31、,也不是反自反的5. 反對稱 定義3-6.5 設R為定義在集合X上的二元關系, 如果對于每個x,yX, 每當 R和 R,必有x=y, 則稱R是反對稱的。 R在X上反對稱當且僅當 (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) 反對稱關系R 的關系矩陣和關系圖 在R的關系矩陣MR中以主對角線為軸的對稱位置上不能

32、同時為1(主對角線除外) 在R的關系圖中每兩個不同的結點間不能有方向相反的兩條弧【例】設X=1,2,3，X上的二元關系R=1,2,2,3,3,3，R是反對稱的。它的關系圖如下圖所示，關系矩陣如下：100100010 注 一個關系可以既是對稱的，又是反對稱的。 一個關系可以既不是對稱的，又不是反對稱的。 【例】 設A=1,2,3，定義A上的二元關系如下： 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上的對稱關系和反對稱關系。既是對稱的,也是反對稱的對稱的,不是反對稱的反對稱的,不是對稱的既不是對稱的,也不是反對稱的【例

33、】設R，S是X上的二元關系，證明 若R，S是自反的，則RS和RS也是自反的。 若R，S是對稱的，則RS和RS也是對稱的。 若R，S是傳遞的，則RS也是傳遞的。 注若R，S是傳遞的，則RS不一定是傳遞的。【例】 X=1,2,3,4 S=, , R=, , 則R，S是傳遞的，但RS不是傳遞的 作業 (1) (6) 3.7 復合關系和逆關系 二元關系是以序偶為元素的集合 對其進行集合的運算（并、交、補、對稱差等）可以得到新的集合，即可得到新的二元關系 對于二元關系還可以進行其它運算關系的復合關系的逆關系的復合運算 定義 3-7.1 設R為X到Y的關系，S為從Y到Z的關系，則R S稱為R和S的復合關系

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

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

36、 代表邏輯加，滿足 0 0=0， 0 1=1， 1 0=1， 1 1=1 把關系矩陣的布爾乘法公式 與線性代數中的矩陣乘法公式相比，發現，只要把矩陣乘法公式中的數乘改為邏輯乘，把數加改為邏輯加，就得到了關系矩陣的布爾乘法公式。)(1kjiknkijvuw=【例】A=1,2,3,4,5，A上的二元關系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關系矩陣如下： MR= MS= MR S=00000000000100000010000100

37、0000000100000110000001000000000000000101000010000 MR MS= = M R S =所以MR S=MR MS 00000000000100000010000100000000010000011000000100000000000000010100001000000000000000001010000100002. 關系的逆 定義 3-7.2 設R為從X到Y的二元關系，如將R中每一序偶的元素順序互換，所得到的集合稱為R的逆關系，記為Rc, 即 Rc =y,xx,yR【例】1. 自然數集合上的關系“” 2. 設X=1,2,3,4，Y=a,b,c，X到

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

39、矩陣表示和圖表示 Rc的關系矩陣 是R的關系矩陣MR的轉置矩陣，即 將R關系圖中的弧線的箭頭反置，就可以得到Rc關系圖。【例】設X=1,2,3,4，Y=a,b,c，X到Y二元關系 R=1,a,2,b,4,c， 試求Rc，寫出MR和 ，驗證cRMTRRMMc=CRMTRRMMc=R和Rc的關系矩陣是：R和Rc的關系圖是：=100000010001RM=100000100001cRM 作業 (1) (3) (6) 3.8 關系的閉包運算 給定一個集合上的關系，擴充一些序偶可以得到一些具有特殊性質的關系 閉包運算 定義 3-8.1 設R是X上的二元關系，如果有另一個關系R滿足： a) R是自反的(對

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

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

42、,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 設X是含有n個元素的集合，R是X上的二元關系，則存在一個整數kn，使得 t(R) =RR(2)R(3) R(k) 求一個二元關系R的傳遞閉包可以簡單的求RR(2)R(3) R(n)【例】設A=1,2,3，定義A上的二元關系R為：R=1,2,2

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

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

45、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為給定非空集合，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, a,c 則S,Q,D,G,E是A的覆蓋 其中D,G,E是A的劃

46、分 F既不是劃分也不是覆蓋ASmii=1 注 若是劃分則必是覆蓋 一個集合的最小劃分是由這個集合的全部元素組成的一個分塊集合 一個集合的最大劃分是由每個元素構成一個單元素分塊的集合 一個集合的劃分不唯一 定義3-9.2 若A1,A2,Ar與B1,B2,Bs是同一個集合A的兩種劃分，則其中所有AiBj組成的集合，稱為是原來兩種劃分的交叉劃分。【例】所有生物的集合X，可分割為P,A, 其中P表示植物的集合，A表示動物的集合。 X也可分割為E,F, 其中E表示史前生物的集合，F表示史后生物的集合。 則它們的交叉劃分為P E, P F, A E, A F, 其中 P E：史前植物的集合 P F：史后植

47、物的集合 A E：史前動物的集合 A F：史后動物的集合 定理3-9.1設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=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的加細 定理3-9.2 任何兩種劃分的交叉劃分，都是原來劃分的一種加細 作業 (2) (5) 3.10 等價關系與等價類 等價關系

48、是最重要、最常見的二元關系之一。它有良好的性質。在計算機科學和計算機技術、信息科學和信息工程中都有廣泛的應用。 定義3-10.1 設R為定義在集合A上的一個關系，若R是自反的，對稱的和傳遞的，則R稱為等價關系 等價關系的關系矩陣和關系圖 關系矩陣主對角線全為1且是對稱陣； 關系圖每一個結點上都有自回路且每兩個結點間如果有弧，一定有方向相反的兩條弧。 【例】設A=1,2,3,4,5，R是A上的二元關系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， 證明R是A上的等價關系。 證法一：用關系矩陣說明R是等價關系 R的關系矩陣MR如下： MR的主對角線全為1且是對稱陣

49、，所以R是自反的和對稱的；還可以用二元關系傳遞性的定義證明R是傳遞的。故R是A上的等價關系。=1000001100011000001100011RM證法二：用關系圖說明R是等價關系 在R的關系圖中每一個結點上都有自回路；每兩個結點間如果有弧，一定有方向相反的兩條弧。所以R是自反的和對稱的。與前面一樣，也可以用二元關系傳遞性的定義證明R是傳遞的。故R是A上的等價關系等價關系R的關系圖被分為三個互不連通的部分。每部分中的結點兩兩都有關系，不同部分中的任意兩個結點則沒有關系。【例】 設R=x,y xIyIx y mod k是整數集合I上的二元關系。證明R是等價關系。 證明：設a,b,c是任意的整數。

50、 因為 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是整數集合I上的等價關系。 定義3-10.2 設R是集合A上的等價關系，對任何aA，集合aR = x xAaRx 稱為元素a形成的R等價類 任意一個元素的等價類非空，包含該元素【例】設A=1

51、,2,3,4,5，R是A上的二元關系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， R是A上的一個等價關系 其等價類為1R=2R=1,2; 3R=4R=3,4; 5R=5【例】 設R=x,y xIyIx y mod 3是整數集合I上的二元關系。 R是等價關系, 其等價類為 0R=,-6,-3,0,3,6, 1R=,-5,-2,1,4,7, 2R=,-4,-1,2,5,8, 定理3-10.1設給定集合A上的等價關系R，對于a,b A有 R當且僅當aR=bR 定義3-10.3 集合A上的等價關系R, 其等價類集合aR | a A稱作A關于R的商集，記作A/R【例】

52、設A=1,2,3,4,5，R是A上的二元關系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， R是A上的一個等價關系 A的關于R的商集A/R為1R, 3R, 5R【例】 設R=x,y xIyIx y mod 3是整數集合I上的二元關系。 R是等價關系,I關于R的商集I/R為0R,1R, 2R 在商集I/R中，0R 1R,2R=I, 且任意兩個等價類的交為 定理3-10.2 集合A上的等價關系R，決定了A的一個劃分，該劃分就是商集A/R 定理3-10.3 集合A的一個劃分確定A的元素間的一個等價關系【例】設X=1,2,3,4，X的劃分S=1，2,3，4，試寫出S導

53、出的等價關系R。 解：R=1,1,2,2,2,3,3,2,3,3,4,4 =112,32,344可以驗證R是X上的等價關系。 定理3-10.4 設R1和R2為非空集合A上的等價關系, 則R1=R2當且僅當A/R1=A/R2【例】設X=1,2,3，寫出集合X上的所有等價關系。 解：先寫出集合X上的所有劃分，它們是： S1=1,2,3， S2=1,2,3， S3=1,3,2 S4=2,3,1, S5=1,2,3 對應的等價關系為： R1=1,2,31,2,3 R2=1,21,233 =1,1,1,2,2,1,2,2, 3,3 R3=1,31,322 =1,1,1,3,3,1,3,3,2,2 R4=

54、2,32,311 =2,2,2,3,3,2,3,3,1,1 R5=112233=1,1,2,2,3,3 作業 (3) (4) (10) 3.11 相容關系 定義3-11.1 給定集合A上的關系r，若r是自反的，對稱的，則稱r是相容關系 所有的等價關系都是相容關系 相容關系的關系矩陣和關系圖 相容關系的關系矩陣主對角線全為1且是對稱陣。 相容關系的關系圖每一個結點上都有自回路且每兩個結點間如果有邊，一定有方向相反的兩條邊。【例】設A=316,347,204,678,770，A上的二元關系r定義為：r=x,y| xAyAx和y有相同數碼，證明r是A上的相容關系。寫出關系矩陣和關系圖。用關系矩陣和關

55、系圖驗證r是A上的相容關系。 證明證明: (1) 集合A中的每個數自己和自己有相同數碼，故r是自反的； (2) 對于集合A中任意x和y，如果x和y有相同數碼，則y和x也有相同數碼。故r是對稱的。于是，r是相容關系。 令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的關系矩陣Mr如下：Mr是一個對角線全為1的對稱矩陣，所以r是相容關系r的關系圖如上圖：關系圖每一個結點上都有自回路且每兩個結點間如果有邊，

56、一定有方向相反的兩條邊。所以r是相容關系=1111011011101101111101011RM 對于相容關系的關系矩陣一般用梯形表示，如上例中的相容關系r的關系矩陣就可表示為 1111011011101101111101011111011110101111 對于相容關系的關系圖也可簡化 省去每一個結點上的自回路，將兩個結點間方向相反的兩條有向邊改為一條無向邊，得到一個簡化圖。此圖叫做R的相容關系圖。 如上例中的相容關系r的關系圖可表示為 定義3-11.2 設r是集合A上的相容關系，若C A, 如果對于C中任意兩個元素a1和a2，有a1ra2，則稱C是由相容關系r產生的相容類 注 相容類C一定

57、是A的子集。 aA，因為相容關系r是自反的，a,ar，所以a是由相容關系r產生的一個相容類。即A中的任何元素組成的單元素集是由相容關系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,e a,a,b,b,c,b,d,e都是R產生的相容類。 a,bd=a,b,d和b,ce=b,c,e也是R產生的相容類。 但b,d,e與任何非空集合的并集都不再是R產生的相容類 定義 3-11.3 設r是集合A上的相容關系，不能真包含在任何其它相容類中的相容類，稱為最大相容類，

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

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

60、1,A2,An，由它確定的關系R=A1A1A2A2 AnAn是相容關系【例】設X=1,2,3,4，S1=1,2,3,3,4，S2=1,2,2,3,1,3,3,4是X的兩個覆蓋。試寫出S1和S2 導出的相容關系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 在上例中，S1S2，但是R1=R2。這說明不同的覆蓋可以導出相同的相容關