離散數(shù)學(xué)關(guān)系.PPT

1、1第二章關(guān)系2在現(xiàn)實(shí)生活中, 集合與集合之間還存在著某種聯(lián)系，如同學(xué)關(guān)系、朋友關(guān)系等。這些關(guān)系正是各門(mén)學(xué)科所要研究的主要內(nèi)容。離散數(shù)學(xué)從集合出發(fā)，主要研究集合之間的關(guān)系。本章內(nèi)容主要研究二元關(guān)系。3本章主要內(nèi)容：n關(guān)系的基本概念n關(guān)系的表示方法 n關(guān)系的運(yùn)算 n關(guān)系的性質(zhì) n關(guān)系的閉包n等價(jià)關(guān)系與劃分n偏序關(guān)系42.1關(guān)系的基本概念為了討論關(guān)系，首先引入有序?qū)偷芽▋悍e兩個(gè)概念。為了討論關(guān)系，首先引入有序?qū)偷芽▋悍e兩個(gè)概念。由兩個(gè)元素由兩個(gè)元素a, b組成的集合組成的集合a, b中，中，a和和b是沒(méi)有是沒(méi)有次序的。有時(shí)需要考慮有次序的兩個(gè)元素，所以需次序的。有時(shí)需要考慮有次序的兩個(gè)元素，所以

2、需要由兩個(gè)元素組成新的東西，并且兩個(gè)元素是有次要由兩個(gè)元素組成新的東西，并且兩個(gè)元素是有次序的。序的。定義定義2.1兩個(gè)元素a, b 有次序地放在一起，稱為一個(gè)有有序?qū)π驅(qū)蛐蚺夹蚺迹洖?a, b)。在有序?qū)?a, b)中，a 稱為第一元素第一元素，b稱為第二元素第二元素。且(a1, b1) = (a2, b2)當(dāng)且僅當(dāng)a1 = a2 且b1 = b2。5定義定義2.2 設(shè)A, B 是兩個(gè)集合，集合(x, y) | xA 且yB稱為A 和B 的笛卡兒積笛卡兒積，也稱卡氏積卡氏積，記為AB。用屬于關(guān)系來(lái)表示就是：(x, y)AB 當(dāng)且僅當(dāng)xA 且yB和(x, y) AB 當(dāng)且僅當(dāng)x A或y B

3、。其中A 稱為第一集合第一集合，B 稱為第二集合第二集合。 6例例2.1 設(shè)A=1,2,3, B=a,b，求AB。由笛卡兒積的定義可知有A=A= 。又由有序?qū)Φ男再|(zhì)可知，一般沒(méi)有ABBA。AB也是一個(gè)集合，所以可以和另一集合C作笛卡兒積(AB)C，類似地有A(BC)。但是，一般沒(méi)有(AB)C=A(BC)，且AB中的元素既不是A 中的元素，也不是B中的元素。7定理定理2.1 2.1 如果B1A1，B2A2，則B1B2 A1A2。8證明證明 對(duì)(x, y)B1B2，有xB1 且yB2，又因?yàn)锽1 A1 ，B2 A2 ，則xA1 且yA2，所以(x, y)A1A2，即B1B2 A1A2。 9定理定理

4、2.2 A, B, C 是任意集合，則：(1) A(BC) = (AB)(AC)，(BC)A = (BA)(CA)。(2) A(BC) = (AB)(AC)，(BC)A = (BA)(CA)。(3) A(B -C) = (AB)- (AC)， (B -C)A = (BA) - (CA)。10證明證明 (1) 對(duì)(x, y)A(BC)，有xA 且yBC，因此xA 且(yB 或yC)，當(dāng)y B 時(shí)，由xA 和yB 得(x, y)AB，當(dāng)yC 時(shí)，由xA 和yC 得(x, y)AC，所以(x, y)(AB)(AC)，即A(BC) (AB)(AC)。因?yàn)锳 A，B BC 和C BC 得AB A(BC)

5、和AC A(BC)，因此(AB)(AC) A(BC)。因此A(BC) = (AB)(AC)成立。同理可證(BC)A = (BA)(CA)。11(2) 對(duì)(x,y)(AB)(AC)，有(x,y)AB且(x,y)AC，所以（xA且yB）且（xA且yC）。由yB且yC得yBC，由xA且yBC 得(x,y)A(BC)。因此(AB)(AC)A(BC)。因?yàn)锳 A，BC B和BC C，所以有A(BC) AB和A(BC) AC成立，因此A(BC) (AB)(AC)。因此A(BC)=(AB)(AC)。同理可證(BC)A=(BA)(CA)。12(3) 對(duì)(x,y)A(B-C)，有xA且yB-C，所以xA且yB且

6、yC。由xA且yB得(x,y)AB，由y C得(x,y) AC，所以(x,y)(AB)-(AC)。因此A(B-C) (AB)-(AC)。對(duì)(x,y)(AB)-(AC)，有(x,y)AB且(x,y) AC，由(x,y)AB 得xA且yB，由xA和(x,y) AC得y C，所以xA且yB且y C。由yB且y C得yB-C，所以(x,y)A(B-C)。因此(AB)-(AC) A(B-C)。因此A(B-C)=(AB)-(AC)。同理可證(B-C)A=(BA)-(CA)。13定義定義2.3 任給n2，n 個(gè)元素a1，, an 有次序地放在一起，稱為一個(gè)n 元有序組元有序組，記為(a1，an)。為了體現(xiàn)n

7、 元有序組的次序，規(guī)定(a1，an)= (b1,，bn)當(dāng)且僅當(dāng)任給1in，都有ai = bi。n 元有序組可以組成集合，特別地有n 個(gè)集合的卡氏積。 14定義定義2.4 任給n2，A1，An 是n 個(gè)集合，集合(x1, , xn)| 任給1in，都有xiAi稱為A1， An 的卡氏積，記為A1An。任給1in，Ai 稱為這個(gè)卡氏積的第i 個(gè)集合。 15定義定義2.5 如果一個(gè)集合滿足以下條件之一：（1）集合非空，且它的元素都是有序?qū)?；?）集合是空集。則稱該集合為一個(gè)二元關(guān)系二元關(guān)系，記作R。二元關(guān)系也可簡(jiǎn)稱為關(guān)系關(guān)系。對(duì)于二元關(guān)系R，如果(x,y)R，可記作xRy；如果(x,y)R，則記作

8、xRy。設(shè)A，B為集合，AB的任何子集所定義的二元關(guān)系叫做從從A到到B的二元關(guān)系的二元關(guān)系，特別當(dāng)A=B時(shí)則叫做A上的二元關(guān)系上的二元關(guān)系。16例例2.2 設(shè)集合A=0,1，B=1,2,3，那么R1=(0,2)，R2=AB，R3= ，R4=(0,1)等都是從A到B的二元關(guān)系，而R3和R4同時(shí)也是A上的二元關(guān)系。17定義定義2.6笛卡爾積A1A2 An的任意一個(gè)子集R稱為A1，A2，An上的一個(gè)n元關(guān)系。當(dāng)A1=A2= =An=A時(shí)，稱R為A上的n元關(guān)系元關(guān)系。定義定義2.7 空集上定義一個(gè)二元關(guān)系，簡(jiǎn)稱空關(guān)空關(guān)系系；若一個(gè)n元關(guān)系R本身是笛卡兒積A1A2 An ，則稱R為全關(guān)系全關(guān)系，用符號(hào)U

9、A表示，即UA=(ai，aj)| ai，aj A為A上的全關(guān)系。 符號(hào)IA=(x,x)|x A為A上的恒等恒等關(guān)系關(guān)系 18例2.3 設(shè)A=1,2,3,4，下面各式定義的R都是A上的關(guān)系，試用列元素法表示R。(1) R=(x,y)|x是y的倍數(shù)(2) R=(x,y)|(x-y)2A(3) R=(x,y)|x/y是素?cái)?shù)(4) R=(x,y)|xy19解解： (1) R=(4,4), (4,2), 4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2) R=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,3),(1,2)(3

10、) R=(2,1),(3,1),(4,2)(4) R=UA-IA =(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)20定義定義2.8 RAB中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域定義域，記為domR。形式化表示為：domR=x|x A,y B,使得(x,y)R。 RAB中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域值域，記作ranR。形式化表示為ranR=y| yB ,xA,使得(x,y)R。21定義定義2.9 設(shè)R為二元關(guān)系，R的的逆關(guān)系逆關(guān)系，簡(jiǎn)稱R的的逆逆，記作R-1,其中R-1=(y

11、, x)|(x, y)R。例例2.4 整除關(guān)系設(shè)A=2, 3, 4,8, B=3, 4, 5, 6, 7, 定義從A到B的二元關(guān)系R: (a, b)Ra整除b。則 R=(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)，Dom R=2, 3, 4, Ran R=3, 4, 6，R-1=(4, 2), (6, 2), (3, 3), (6, 3), (4, 4) 22關(guān)系從本質(zhì)上講，仍是集合，只是這個(gè)集合中的元素都是以有序?qū)Φ男问匠霈F(xiàn)。既然關(guān)系是一個(gè)集合，那么集合的表示方法就可以用來(lái)表示關(guān)系，又因?yàn)殛P(guān)系是一個(gè)特殊的集合，其中的元素均以序偶的形式出現(xiàn)，除了可以用集合的表示

12、方法外，還可以用其他的表示方法。這里主要介紹如下幾種表示方法。 2.2 關(guān)系的表示方法 231. 用列舉法表示二元關(guān)系如果二元關(guān)系中的序偶個(gè)數(shù)是有限的，可以用列舉法將其所包含的全部元素一一列舉出來(lái)。例例2.5 設(shè)集合A=1,2,3，在集合A上定義的小于等于關(guān)系，LA=(a,b)|a,bA,ab，則LA=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)。242. 用描述法表示二元關(guān)系用確定的條件表示某些序偶是否屬于這個(gè)關(guān)系，并把這個(gè)條件寫(xiě)在大括號(hào)內(nèi)表示關(guān)系的方法。 格式是： LR=(x,y)|xR且yR且xy。例例2.6設(shè)A=1，2，3，4，下面兩式定義的R1和R2都是A上

13、的關(guān)系，分別列出R1與R2的元素如下： (1) R1 =(x,y)|x是y的倍數(shù) (2) R2 =(x,y)|(x-y)2A25解解： (1) R1=(4,4),(4,2),(4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2) R2=(2,1),(1,2),(3,1),(1,3),(2,3),(3,2),(4,2),(2,4),(3,4),(4,3)263.用關(guān)系矩陣表示關(guān)系定義定義2.10設(shè)A和B是兩個(gè)有限集A=a1, , am，B=b1, , bn，R是從A到B的二元關(guān)系，稱mn階矩陣MR=(rij)為R的關(guān)系矩陣，其中 rij = 1 ，當(dāng)且僅當(dāng)(ai, bj)R

14、 rij = 0 ，當(dāng)且僅當(dāng)(ai, bj) R27例例2.7 例2.5中的關(guān)系R的關(guān)系矩陣為：例例2.8 例2.6中的關(guān)系R1與R2的關(guān)系矩陣分別為：RM1001101111RM10110101001100012RM0110101111010110， 28 4.用關(guān)系圖表示二元關(guān)系 設(shè)A=a1, , an，R是A上的二元關(guān)系。A中每個(gè)元素ai用一個(gè)點(diǎn)表示，稱該點(diǎn)為頂點(diǎn)ai 。R的關(guān)系圖是一個(gè)有向圖，A中每個(gè)元素分別用一個(gè)頂點(diǎn)表示，當(dāng)且僅當(dāng)(ai,aj)R時(shí)，用弧或線段聯(lián)結(jié)ai和aj； 若(ai,aj) R，則在ai處畫(huà)一條自封閉的弧線,其中1i,jn。這樣表示R中關(guān)系的圖形，稱為R的關(guān)系圖關(guān)

15、系圖，用GR表示。29例例2.9設(shè)集合A=1,2,3,4，在集合A上定義關(guān)系R=(1,1)，(1,2)，(2,3)，(2,4)，(4,2)，則R的關(guān)系圖如圖2.1所示。30n關(guān)系R的集合表達(dá)式、關(guān)系矩陣MR、關(guān)系圖GR三者均可唯一相互確定31定義定義2.11 設(shè)關(guān)系R和S是從A到B的兩個(gè)二元關(guān)系，對(duì)于aA，bB，定義：（1） RS： (a,b)RS (a,b)R或(a,b)S。（2） RS： (a,b)RS (a,b)R且(a,b)S。（3） R-S： (a,b)R-S (a,b)R且(a,b)S。（4） R： (a,b)R (a,b)AB-R。2.3 關(guān)系的運(yùn)算 32例例2.10 設(shè)集合A=

16、a,b,c，集合B=1,2，且R和S是從A到B的兩個(gè)二元關(guān)系， R=(a,1),(b,2),(c,1) S=(a,1),(b,1),(c,2) 則 RS=(a,1),(b,2),(c,1),(b,1),(c,2) RS=(a,1) R-S=(b,2),(c,1) R=ABR=(a,2),(b,1),(c,2)33因?yàn)殛P(guān)系可以用矩陣的形式表示，當(dāng)我們用矩陣的形式求關(guān)系的并、交、補(bǔ)及對(duì)稱差的運(yùn)算時(shí)，可以用如下形式表示：MRS=MRMS （矩陣的對(duì)應(yīng)分量做邏輯析取運(yùn)算）MRS=MRMS （矩陣的對(duì)應(yīng)分量做邏輯合取運(yùn)算）MR-S=MRS=MRMS MR=MR （矩陣的對(duì)應(yīng)分量做邏輯非運(yùn)算）34例例2.

17、11對(duì)例2.10中的關(guān)系的運(yùn)算采用矩陣的形式表示如下： 根據(jù)題意，關(guān)系R與S的關(guān)系矩陣分別表示為011001RM100101SM則SRSRMMM111101SRSRMMM000001SRSRMMM011000RRBARMMM10011035定理定理2.3 設(shè)關(guān)系R、S是集合A到集合B的二元關(guān)系，則有下列性質(zhì)成立：(1) (R-1)-1=R, (R)=R (雙重否定律)(2) (R)-1= (R-1), -1 = (可換性) (3) (RS)-1=R-1S-1 (分配律) (RS)-1=R-1S-1 (R-S)-1=R-1-S-1 (4) SR S-1 R-1 (單調(diào)性) SR S R (5)d

18、omR-1=ranR，ranR-1=domR(6) (AB)-1= BA 36證明證明：這里只證明（1）和（5）。(1)任取(x,y)，由逆的定義有(x,y)(R-1)-1 (y,x)R-1 (x,y)R。所以有(R-1)-1=R。(5)任取x, xdomR-1 y(x,y)R-1) y(y,x)R) xranR 所以有domR-1=ranR。同理可證 ranR-1=domR。37合成關(guān)系定義定義2.12設(shè)R是從集合A到集合B的二元關(guān)系，S是從集合B到集合C的二元關(guān)系，則R與S的復(fù)合關(guān)系復(fù)合關(guān)系（合成關(guān)系合成關(guān)系）RS是從A到C的關(guān)系，并且，RS=(x,z)|xA且zC且存在yB使得(x,y)

19、R,(y,z)S，運(yùn)算“”稱為復(fù)合復(fù)合運(yùn)算運(yùn)算或合成運(yùn)算合成運(yùn)算。38例例2.12 設(shè)A上的二元關(guān)系R=(x,y)|x,yA, x是y的父親，S=(x,y)| x,yA, x是y的母親 (1)說(shuō)明RR，R-1 S1 ，R-1 S的含義。(2)表示以下關(guān)系：(x,y)|x,yA, y是x的外祖母(x,y)|x,yA, x是y的祖母39解解：(1) RR表示關(guān)系(x,y)|x,yA, x是 y的祖父 R-1 S1 表示關(guān)系(x,y)|x,yA, y是x的祖母 tA(x,t)R-1 (t,y)S-1)R-1 S表示空關(guān)系(2)(x,y)|x,yA, y是x的外祖母表示為S-1 S1 (x,y)|x,

20、yA, x是y的祖母表示為SR40例例2.13設(shè)Z是整數(shù)集合，R，S是Z到Z的兩個(gè)關(guān)系：R=(x,3x)|xZ； S=(x,5x)|xZ。計(jì)算RS； SR；RR； SS； (RR)R； (RS)R。41解解RS=(x,15x)|xZ； SR=(x,15x)|xZ； RR=(x,9x)|xZ； SS=(x,25x)|xZ； (RR)R=(x,27x)|xZ； (RS)R=(x,45x)|xZ。42定理定理2.4 R為定義在集合A上的關(guān)系,則RIA=IAR=R43證明證明 任取(x,y)，有(x,y)RIAt(x,t)R且(t,y)IA) t(x,t)R且t=y) (x,y)R又有(x,y)R (

21、x,y)R且x,yA (x,y)R且(y,y)IA (x,y)RIA所以，RIA=R。同理可證 IAR=R。44定理定理2.5 設(shè)R1 A1A2 ，R2 A2A3 ， R3 A3A4，則(1)(R1R2)R3 = R1(R2R3) (2)(R1R2)-1=R2-1R1-1不滿足交換律，即R1R2 R2R145證明： (1)任取(x,y), (x,y)(R1R2)R3(tA3) (使得(x,t) R1R2且(t,y)R3)(tA3)(sA2),使得(x,s)R1且(s,t)R2)且(t,y)R3)(tA3) (sA2)(使得(x,s)R1且(s,t)R2且(t,y)R3) (sA2)(使得(x,

22、s)R1且(tA3) (使得(s,t)R2且(t,y)R3) (sA2)(使得(x,s)R1且(s,y)R2R3) (x,y)R1(R2R3)所以(R1 R2) R3 =R1(R2R3)46由歸納法，任意n個(gè)關(guān)系的合成也是可結(jié)合的特別，當(dāng)A1= A2 = =An+1 =A且R1= R2 = =Rn =R，合成關(guān)系R R R=Rn 是集合A上的一個(gè)關(guān)系。47（2） 任取(z,x)(R1R2)-1，則（x,z)R1R2，由“”的定義知，至少存一個(gè)yB，使得(x,y)R1，(y,z)R2，即(y,x)R-11，(z,y)R-12。由(z,y) R-12和(y,x) R-11 ，有(z,x) R-12

23、 R-11 。所以，(R1R2)-1 R-12 R-11 。反之，任取(z,x) R-12 R-11 ，由“”的定義知： 則至少存在一個(gè)yB，使得(z,y) R-12和(y,x) R-11 ，所以 (x,y)R1，(y,z)R2。由“”知(x,z)R1R2。即有(z,x)(R1R2)-1。所以， R-12 R-11 (R1R2)-1。由集合的性質(zhì)知： (R1R2)-1= R-12 R-11 。48例例2.14 設(shè)A=a,b,c,d,e,f，R=(a,a),(a,b),(b,c),(c,d),(d,e),(e,f)。求Rn(n=1,2,3,4,)49解解： R1=R； R2=RR=(a,a),(

24、a,b),(a,c),(b,d),(c,e),(d,f)； R3=RRR=R2R=(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)； R4=R3R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)； R5=R4R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)； R6=R5R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)=R5； R7=R6R=R5； Rn=R5（n5）。50n冪集Rn的基數(shù)|Rn|并非隨著n的增加而增加，而是呈遞減趨勢(shì)，而且，當(dāng) 時(shí)，有An AiinRR1512.4關(guān)系的性質(zhì)有了關(guān)系

25、的定義，可以來(lái)定義關(guān)系的某些特殊性質(zhì)，這些性質(zhì)在以后的討論中，將起到極其重要的作用。本節(jié)主要討論關(guān)系的五種性質(zhì)，即自反性自反性、反自反性反自反性、對(duì)稱性對(duì)稱性、反對(duì)稱性反對(duì)稱性和傳遞性傳遞性。52自反、反自反定義定義2.14設(shè)R為集合A上的二元關(guān)系： （1） 若對(duì)任意的xA，都有(x,x)R，則稱關(guān)系R在集合A上是自反自反的或稱關(guān)系R具有自反性自反性； 否則，稱R是非自反的。（2） 若對(duì)任意的xA，都有(x,x)R，則稱關(guān)系R在集合A上是反自反反自反的或稱關(guān)系R具有反自反自反性反性。自反關(guān)系：全關(guān)系、恒等關(guān)系、小于等于關(guān)系、整除關(guān)系、包含關(guān)系反自反關(guān)系：小于關(guān)系、真包含關(guān)系53例例2.15 設(shè)

26、A=1,2,3，R1=(1,1),(2,2)，R2=(1,1),(2,2),(3,3),(1,2)，R3=(1,3)，說(shuō)明R1，R2，R3是否為A上自反的關(guān)系。54解解： 只有R2是A上自反的關(guān)系，因?yàn)镮A R2； 而R1和R3都不是A上的自反關(guān)系，因?yàn)?3,3)R1 ，所以R1不是自反的，而(1,1),(2,2),(3,3)都不屬于R3 ，因此R3不是自反的。關(guān)系R是否為自反關(guān)系是相對(duì)集合A來(lái)說(shuō)的。同一個(gè)關(guān)系在不同的集合上具有不同的性質(zhì)。55例例2.16設(shè)A=a,b,c,d，在集合A上定義如下三個(gè)二元關(guān)系R,S,T分別如下： R=(a,a),(a,d),(b,b),(b,d),(c,c),(

27、d,d)S=(a,b),(a,d),(b,c),(b,d),(c,a),(d,c)T=(a,a),(a,b),(a,c),(b,d),(c,a),(c,c),(d,c)說(shuō)明R,S,T在A上的自反性與反自反性。56解解： 因?yàn)锳中每個(gè)元素x，都有(x,x)R，所以R在A具備自反性。因?yàn)锳中每個(gè)元素x，都有(x,x)S，所以S在A具備反自反性。因?yàn)锳中有元素b，使(b,b)T，所以T在A上不具備自反性； 因?yàn)锳中有元素a，使(a,a)T，所以T在A上也不具備反自反性。任何不是自反的關(guān)系未必一定是反自反的關(guān)系，反之亦然。即存在既不是自反的也不是反自反的關(guān)系。57定理定理2.6 設(shè)R是定義在集合A上的

28、二元關(guān)系，R是自反的當(dāng)且僅當(dāng)IA R。58證明證明 （1）必要性必要性 設(shè)R在A上是自反的，則IA R。根據(jù)恒等關(guān)系的定義，對(duì)任意的xA有(x,x)IA，又因?yàn)镽在A上是自反的，即對(duì)于任意的xA有(x,x)R，因此IA R 。 （2）充分性）充分性 設(shè)IA R，則R在A上是自反的。對(duì)任意的xA有(x,x)IA，而IA R ，因此對(duì)任意的xA有(x,x)R，即R在A上是自反的。59定理定理2.7 設(shè)R是定義在集合A上的二元關(guān)系，R是反自反的當(dāng)且僅當(dāng)RIA=。60證明證明 （1）必要性必要性 設(shè)R在A上是反自反的，則RIA=。 假設(shè)RIA，比如存在（x，y）RIA，即（x，y）R且（x，y） IA

29、 ，也即（x，y）R且x=y，即（x，x）R，與R在A上是反自反的相矛盾。因此RIA=。充分性充分性 設(shè)RIA=，則R在A上是反自反的。對(duì)任意的xA，有 ( x, x) IA ，由于RIA=，因此( x, x)R，即R在A上是反自反的。61對(duì)稱、反對(duì)稱定義定義2.15 設(shè)R為A上的關(guān)系。 (1) 若對(duì)任意的x與y，都有x,yA且(x,y)R，則有(y,x)R，則稱R為A上對(duì)稱對(duì)稱關(guān)系； 否則，稱R是非對(duì)稱的。(2) 若對(duì)任意的x與y，都有x,yA且當(dāng)(x,y)R，(y,x)R時(shí)，有x=y，則稱R為A上的反對(duì)稱反對(duì)稱關(guān)系。對(duì)稱：全關(guān)系、恒等關(guān)系、空關(guān)系反對(duì)稱：恒等關(guān)系、空關(guān)系62例例2.17 設(shè)

30、A=a,b,c，定義A上的二元關(guān)系如下： R=(a,a),(b,b)S=(a,a),(a,b),(b,a)T=(a,c),(a,b),(b,a)試說(shuō)明R，S，T是否是A上的對(duì)稱關(guān)系和反對(duì)稱關(guān)系。63解解： 根據(jù)定義R上A上的對(duì)稱關(guān)系與反對(duì)稱關(guān)系。S是A上的對(duì)稱關(guān)系。S不是A上的反對(duì)稱關(guān)系，因?yàn)?a,b)與(b,a)都是S中的元素，但是ab，所以S不是A上的反對(duì)稱關(guān)系。T既不是A上的對(duì)稱關(guān)系，也不是A上的反對(duì)稱關(guān)系。因?yàn)?a,c)是T中的元素，但是(c,a)不是T中的元素，因此不滿足對(duì)稱性，又因?yàn)?a,b)與(b,a)都是T中的元素，但是ab，因此也不滿足反對(duì)稱性。64定理定理2.8 設(shè)R是A上

31、的二元關(guān)系，R是對(duì)稱的當(dāng)且僅當(dāng)R=R-1。65證明證明 (1)必要性必要性 設(shè)R是對(duì)稱的，則R=R-1。(x，y)R(y，x)R(x，y) R-1 R=R-1。(2)充分性充分性 設(shè)R=R-1，則R是對(duì)稱的。(x，y)R(y，x) R-1(y，x)R，因此R是對(duì)稱的。 66定理定理2.9 設(shè)R是A上的二元關(guān)系，R是反對(duì)稱的當(dāng)且僅當(dāng)RR-1IA。67證明證明 (1)必要性必要性 設(shè)R是反對(duì)稱的，則RR-1IA。(x，y)RR-1(x，y)R且(x，y)R-1（x，y）R且(y，x)R，因?yàn)镽是反對(duì)稱的，根據(jù)反對(duì)稱的定義，則x=y，因此(x，y)=(y，x)=(x，x) IA，所以RR-1IA。(

32、2)充分性充分性 設(shè)RR-1IA，則R是反對(duì)稱的。(x，y)R且(y，x)R (x，y)R 且 (x，y)R-1 (x，y)RR-1因?yàn)镽R-1IA，所以(x，y) IA，顧x=y，因此R是反對(duì)稱的。68傳遞定義定義2.16 設(shè)R為A上的關(guān)系，若對(duì)任意的x，y，z有x,y,zA且當(dāng)(x,y)R，(y,z)R時(shí)，有(x,z)R,則稱R是A上的傳遞關(guān)系，否則稱R是非傳遞關(guān)系。傳遞關(guān)系：全關(guān)系、空關(guān)系、小于、包含69例例2.18 設(shè)A=1,2,3，R1=(1,1)，R2=(1,3),(2,3)，R3=(1,1),(1,2),(2,3)，說(shuō)明R1，R2，R3是否為集合A上傳遞的關(guān)系。70解解： 根據(jù)定

33、義2.16，R1，R2是A上傳遞的關(guān)系； 但R3不是傳遞的，因?yàn)?1,2)R3，(2,3)R3，而(1,3)R3，由傳遞關(guān)系的定義知R3不是傳遞的關(guān)系。71定理定理2.10 設(shè)R是集合A上的二元關(guān)系，則R是傳遞的當(dāng)且僅當(dāng)R.RR 72證明證明(1） 必要性必要性 設(shè)R是傳遞的，則R.RR。設(shè)(x，y)R.R，zA，使得(x，z) R且(z，y) R。因?yàn)镽是傳遞的，所以(x，y) R，即有R.RR。(2)充分性充分性 設(shè)R.RR，則R是傳遞的。(x，y) R且(y，z) R。由復(fù)合關(guān)系的定義可得(x，z) R.R，因?yàn)镽.RR，所以(x，z) R，即R是傳遞的。 732.4.2關(guān)系性質(zhì)的證明在

34、二元關(guān)系中，除了對(duì)一個(gè)具體的關(guān)系判斷它具有哪些性質(zhì)外，更多的是針對(duì)一個(gè)抽象的關(guān)系，利用它的特點(diǎn)來(lái)證明它具有某個(gè)性質(zhì)。由于關(guān)系性質(zhì)的定義全部都是按“如果那么”來(lái)描述的，在證明這類問(wèn)題時(shí)，一般采用按照定義證明的方法。這種證明問(wèn)題的方法在于： 證明時(shí)不能僅僅利用題目所給的已知條件，還要同時(shí)結(jié)合定義中的“已知”，并且推出的并非整個(gè)定義，而是定義中的結(jié)論。另外，由于關(guān)系是特殊的集合，當(dāng)用集合的手段來(lái)描述關(guān)系的性質(zhì)時(shí)，其證明的方法也是按集合中的按定義證明方法來(lái)證。74例例2.19設(shè)R1，R2是定義在集合A上的兩個(gè)關(guān)系，并且R1，R2具有傳遞性，則R1R2也具有傳遞性。75證明證明： 對(duì)任意x,yA，則若(

35、x,y) R1R2且(y,z) R1R2(x,y)R1且(x,y)R2且(y,z)R1且(y,z)R2(x,y)R1且(y,z)R1)且(x,y)R2 且(y,z)R2)又因?yàn)镽1，R2具有傳遞性，因此(x,y)R1且(y,z)R1)且(x,y)R2且(y,z)R2)(x,z)R1且(x,z)R2 (x,z)R1R2根據(jù)定義2.16， R1R2具有傳遞性。76關(guān)系性質(zhì)與集合運(yùn)算運(yùn)算性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性RSRSR-SR-1RS772.5關(guān)系的閉包對(duì)于在非空集合上定義的關(guān)系R不一定具備某種性質(zhì)或某幾種性質(zhì)，而這些性質(zhì)對(duì)研究某些具體的問(wèn)題時(shí)又非常重要，這時(shí)就需要構(gòu)造一個(gè)基于此關(guān)系的

36、新關(guān)系，使其具備所需要的性質(zhì)，即往該關(guān)系中添加一些適量的元素以改變?cè)嘘P(guān)系的性質(zhì)，得到新的關(guān)系，使得新關(guān)系具有所需要的性質(zhì)，但又不希望新關(guān)系與R相差太多，也就是說(shuō)，要盡可能少地來(lái)添加有序?qū)?，滿足這些要求的新關(guān)系就稱為R的閉包。本節(jié)介紹關(guān)系的自自反反、對(duì)稱對(duì)稱和傳遞閉包傳遞閉包。78定義定義2.17設(shè)R是非空集合A上的關(guān)系，R的自反自反（對(duì)稱對(duì)稱或傳遞傳遞）閉包是A上的關(guān)系Rc，使得Rc滿足以下條件： (1) Rc是自反自反的（對(duì)稱對(duì)稱的或傳遞傳遞的）； (2) R Rc； (3) 對(duì)A上任何包含R的自反（對(duì)稱或傳遞）關(guān)系Rp有Rc Rp。一般將R的自反閉包記作r(R)，對(duì)稱閉包記作s(R)，傳

37、遞閉包記作t(R)。79定理定理2.11 設(shè)R為定義在非空集合A上的二元關(guān)系，則有（1）r（R）= RIA（2）s（R）= RR-1（3）t（R）= RR2R380證明證明（1） 令R=RIA，則有 IA R IA ，而R IA =R，因此R是自反的。 R R IA ，而R IA =R，因此R R。 假設(shè)R是A上的任意自反關(guān)系并且R R，因?yàn)镽是自反的，所以IAR，因此有R=RIA R。由自反閉包的定義，R=R IA是R的自反閉包，即r(R)=R=R IA 。 81（2）令R= RR-1(R) -1=(RR-1)-1= R-1(R-1) -1= R-1R= RR-1= R,因此R是對(duì)稱的。R

38、RR-1，而RR-1= R，因此R R。設(shè)R是A上的任意對(duì)稱關(guān)系并且R R，又(x，y) R-1(y，x) R(y，x) R，從而有R= RR-1 R。因此R是R的對(duì)稱閉包，即s(R)= RR-1。（3）分兩部分來(lái)證所要的結(jié)論。先證RR2R3 t（R）用數(shù)學(xué)歸納法來(lái)證，對(duì)任意自然數(shù)i，有Ri t（R）當(dāng)i=1時(shí)，由傳遞閉包的定義，R1=R t（R）。假設(shè)當(dāng)i=n時(shí)，Rn t（R）,下證Rn+1 t（R）。對(duì)任意的(x,y)Rn+1，存在cA，使得(x,c)Rn且(c,y)R，即存在cA，使得(x,c)t(R)且(c,y)t(R)，則(x,y)t(R)。即Rn+1 t(R)，因此，RR2R3 t

39、(R)。再證明t(R) RR2R3 。顯然，有R RR2R3成立，下證 RR2R3是傳遞的。(x,y) RR2R3 t(R)且(y,z) RR2R3 tA，使得(x,y)Rt且sA，使得(y,z)Rs(x,z)RtRs=Rt+s RR2R3 (x,z) RR2R3由傳遞關(guān)系的定義， RR2R3是傳遞的。綜上所述， RR2R3是包含R的傳遞關(guān)系。而R的傳遞閉包是包含R的最小傳遞關(guān)系，因此t(R) RR2R3 。即t(R)= RR2R3成立。83推論推論 設(shè)R是有限集合A上的關(guān)系，|A|=n，此時(shí)t（R）=RR2R3Rn有。 84例2.20設(shè)集合A=a, b, c，R是A上的二元關(guān)系，且R=(a,

40、 b), (b, c), (c, a)，求出關(guān)系R的自反、對(duì)稱和傳遞閉包。85解： r(R)=RIA=(a,a),(b,b),(c,c),(a,b),(b,c),(c,a)s(R)=RR-1=(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)R2=(a,c),(b,a),(c,b)R3=(a,a),(b,b),(c,c)R4=(a,b),(b,c),(c,a)因此，有R=R4R2=R5R3=R6t(R)=RR2R3 =RR2R3 =(a,a),(b,b),(c,c),(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)86例2.21設(shè)集合A=a,b,c，R

41、是A上的二元關(guān)系，且R=(a,b),(b,c),(c,a)，用關(guān)系矩陣求關(guān)系R的自反、對(duì)稱和傳遞閉包。87解 關(guān)系的關(guān)系矩陣為： 001100010RM0100011000011000100011000102RRRMMM111111111)(32RRRMMMRt10001000100110001001000110023RRRMMM88定理定理2.12 設(shè)R是非空集合A上的關(guān)系，（1）若R是自反的，則s(R)與t(R)也是自反的。（2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的。（3）若R是傳遞的，則r(R)是傳遞的，而s(R)不一定傳遞。證明(1)若R是自反的，則有IA R。又因?yàn)镽s(R)

42、，且Rt(R)，所以IAs(R)且IA t(R)，因此s(R)與t(R)是自反的。(2)因?yàn)镽對(duì)稱，有R=R-1。由于r(R)=RIA ，而(r(R) -1=(R IA)-1= R-1 IA-1= RIA= r(R),因此r(R)對(duì)稱。因?yàn)镽對(duì)稱，因此(Ri)-1=(R-1)i= Ri。由于t(R)= RR2R3,于是(t(R)-1=(RR2R3)-1= R-1(R2)-1(R3)-1= RR2R3=t(R)所以t(R)也對(duì)稱。90(3)因?yàn)镽傳遞，所以R.RR，而r(R)=RIA ，則有r(R).r(R)=( R IA)( R IA) =R.( R IA)IA. ( R IA) = R .R

43、R IA IA. ( R IA) = R .RR( R IA) RR( R IA) = R IA = r(R)即r(R)具有傳遞性。91下面舉一個(gè)反例來(lái)說(shuō)明s(R)不具備傳遞性。假設(shè)集合A=1,2,3，R=(1,2)是定義在集合A上的且具有傳遞性，而s(R)=(1,2),(2,1)卻不具備傳遞性。92定理定理2.13 設(shè)R1,R2AA，且R1R2，則r(R1)r(R2) s(R1)s(R2)t(R1)t(R2) 93證明：(1)因?yàn)镽1R2，因此R1IA R2IA ，所以r(R1)r(R2)。反證法：假設(shè)(x, y)r(R1), 但(x, y)r(R2)，則r(R1) (x, y)也是自反的，

44、即xy; 如果(x, y)R1，則(x, y)R2，那么(x, y)r(R2)，導(dǎo)致矛盾，因此(x, y) R1，所以R1 r(R1) (x, y)，那么r(R1)不是R1的自反閉包，矛盾。因此 (x, y) r(R2)。所以r(R1) r(R2)。94(2)因?yàn)镽1R2，R2s(R2)，因此R1s(R2)。由s(R1)是包含R1的最小對(duì)稱關(guān)系，所以s(R1)s(R2)。(3)因?yàn)镽1R2，R2t(R2)，因此R1t(R2)。由t(R1)是包含R1的最小傳遞關(guān)系，所以t(R1)t(R2)。95定理定理2.14 設(shè)R1和R2是集合A上的關(guān)系，則以下各式成立。（1）r（ R1 R2 ）=r（ R1

45、 ）r（ R2 ）（2）s（ R1 R2 ）=s（ R1 ）s（ R2 ）（3）t（ R1 ）t（ R2 ）t（ R1 R2 ）96證明證明： （1） r(R1R2)=IA(R1 R2)=(IAR1)(IA R2)=r(R1)r(R2)（2） s(R1R2)=(R1 R2)(R1 R2)-1=(R1 R2)(R-11R-12)=(R1 R-11)(R2 R-12)=s(R1)s(R2)（3） 因?yàn)镽1R1 R2 ， R2 R1 R2 ，所以t(R1) t(R1 R2)，t(R2) t(R1R2)，得出t(R1)t(R2) t(R1 R2)。一般地，t(R1)t(R2)t(R1 R2)。97例2

46、.22 設(shè)集合A=1,2,3，R1=(1,2),(2,3)，R2=(3,2)，有t(R1)=(1,2),(1,3),(2,3) t(R2)=(3,2)而t(R1R2)=(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)t(R1)t(R2)=(1,2),(1,3),(2,3),(3,2)由此可見(jiàn)t(R1)t(R2)t(R1R2)。98定理定理2.15 設(shè)R是集合A上的關(guān)系，則（1）rs(R)=sr(R)；（2）rt(R)=tr(R)；（3）st(R)ts(R)。99證明證明 （1）)()(AIRsRsr1)()(AAIRIR)()(1AAIRIRAIRR1AIRs)()( R

47、rs100(2)()(AIRtRtriAiIR)(1 11iijAjIR111iAiijjIR1iAiIRAIRt)()(Rrt 101(3)若RS，則顯然有s(R)s(S)，t(R)t(S)。根據(jù)對(duì)稱閉包的定義，Rs(R)，于是t(R)ts(R)st(R) sts(R)若s(R)對(duì)稱，則ts(R)也對(duì)稱。 所以，由(1)可得sts(R)=ts(R)，即st(R) ts(R)。102例2.23設(shè)A=1,2，R=(1,2)，求st(R)與ts(R)。103例2.23設(shè)A=1,2，R=(1,2)，求st(R)與ts(R)。解： st(R)=s(t(R)=s(1,2)=(1,2),(2,1)ts(R

48、)=t(s(R)=t(1,2),(2,1)=(1,2),(2,1),(1,1),(2,2)1042.6等價(jià)關(guān)系與劃分在日常生活中或者在數(shù)學(xué)等學(xué)科中，常常需要對(duì)某個(gè)集合上的元素按照某種方式進(jìn)行分類，即集合的劃分，這是一個(gè)非常重要的而且應(yīng)用十分廣泛的概念，集合的劃分與一種重要的關(guān)系等價(jià)關(guān)系密切相關(guān)。利用等價(jià)關(guān)系，可以將集合中的元素分類，將一個(gè)大的集合分成若干個(gè)等價(jià)類，其主要意義在于它證實(shí)了應(yīng)用抽象的一般原理的正確性，即在某方面等價(jià)的個(gè)體產(chǎn)生等價(jià)類，對(duì)全體的等價(jià)類進(jìn)行分析常常比對(duì)全體本身進(jìn)行分析更簡(jiǎn)單。1052.6.1等價(jià)關(guān)系定義定義2.18設(shè)R為非空集合A上的關(guān)系。如果R是自反的、對(duì)稱的和傳遞的，

49、則稱R為A上的等價(jià)等價(jià)關(guān)系關(guān)系。設(shè)R是一個(gè)等價(jià)關(guān)系，若(x，y)R，稱x等價(jià)于等價(jià)于y，記做xy。 106例2.24以下關(guān)系是等價(jià)關(guān)系： (1) 集合A上的恒等關(guān)系、全域關(guān)系是等價(jià)關(guān)系。(2) 三角形的全等關(guān)系、三角形的相似關(guān)系是等價(jià)關(guān)系。(3) 在一個(gè)班級(jí)里“年齡相等”的關(guān)系是等價(jià)關(guān)系。107例2.25設(shè)關(guān)系R是定義在有理數(shù)集Q上的關(guān)系，并且(x,y)R，當(dāng)且僅當(dāng)x-y是整數(shù)，試證R是等價(jià)關(guān)系。108例2.25設(shè)關(guān)系R是定義在有理數(shù)集Q上的關(guān)系，并且(x,y)R，當(dāng)且僅當(dāng)x-y是整數(shù)，試證R是等價(jià)關(guān)系。證明證明： (1) 自反性自反性： 對(duì)任意一個(gè)有理數(shù)xQ，有x-x=0是整數(shù)，即對(duì)所有的有

50、理數(shù)有(x,x)R，因此R滿足自反性。 (2) 對(duì)稱性對(duì)稱性： 假設(shè)x,yQ， 并且(x,y)R，即x-y是整數(shù)，則y-x=-(x-y)也是整數(shù)，即(y,x)R，因此R滿足對(duì)稱性。 (3) 傳遞性傳遞性： 假設(shè)x,y,zQ，并且(x,y)R，(y,z)R，即x-y與y-z都是整數(shù)，則x-z=x-y+y-z=(x-y)+(y-z)也是整數(shù)，即(x,z)R，因此R滿足傳遞性。所以，R是等價(jià)關(guān)系。109例2.26 設(shè)集合 A=a,b,c,d,，R=(a,a)，(a,d)，(b,b)，(b,c)，(c,b)，(c,c) ，(d,a)，(d,d)。試證R是A上的等價(jià)關(guān)系。110證明： 寫(xiě)出關(guān)系R關(guān)系矩陣

51、如下：1001011001101001RM由關(guān)系矩陣可以看出，該矩陣的主對(duì)角線的元素都是1，即關(guān)系R滿足自反性。該關(guān)系矩陣是對(duì)稱的，即R滿足對(duì)稱性。求出R2的關(guān)系矩陣為：10010110011010012RM即R2的關(guān)系矩陣與R的關(guān)系矩陣相同，并且有R3，Rn都與R的關(guān)系矩陣相同，因此，t(R)=RR2R3Rn的關(guān)系矩陣也與R的關(guān)系矩陣相同，所以R是傳遞的。綜上所述，R是A 上的等價(jià)關(guān)系。111例2.27設(shè)A=1,2,8, 定義A上的關(guān)系R=(x，y)|x，yA且xy(mod 3)，其中xy(mod 3)叫做x與y模3相等，即x除以3的余數(shù)與y除以3的余數(shù)相等。試證R為A上的等價(jià)關(guān)系。 112

52、證明證明： R=(1,4),(4,1),(1,7),(7,1),(2,5),(5,2),(2,8),(8,2),(3,6),(6,3)IA因?yàn)镮AR，因此R滿足自反性。對(duì)x,yA，若(x,y)R，即xy mod 3，則有yx mod 3，即(y,x)R，因此R滿足對(duì)稱性。對(duì)x,y,zA，若(x,y)R，(y,z)R，即xy mod 3，yz mod 3，則有xz mod 3，即(x,z)R，因此R滿足傳遞性。綜上所述，R是等價(jià)關(guān)系。113定理定理2.16 設(shè)R是定義在集合A上的關(guān)系，則R為等價(jià)關(guān)系R * R-1=R。 114定理定理2.16 設(shè)R是定義在集合A上的關(guān)系，則R為等價(jià)關(guān)系R * R

53、-1=R。 證明證明 (1)必要性必要性: R為等價(jià)關(guān)系 R * R-1=R令x, y是集合A中的任意元素，且(x,y)R, 則 (x,y)R (x,y)R 且(y,x)R (x,y)R且(y,x)R-1 (z)使得(x,y)R 且(z,y)R-1 (x,y)RR-1 于是, RR R-1. 另一方面， (x,y)RR-1 z使得(x,z) R且(z,y)R-1 (x,z) R且(y,z)R (x,z) R且(z,y)R (x,y) R因此, R R-1 R. 綜上可知, 必要性得證.(2)充分性充分性: 由假設(shè)R R-1=R可知, (x,y) R (x,y) R R-1 z使得(x,z) R

54、且(z,y)R-1 z使得(x,z) R且(z,y)R由此可推知R為對(duì)稱和傳遞時(shí)方使上式成立, 從而R也必為自反, 充分性得證。115定義定義2.19設(shè)設(shè)R為集合A上的等價(jià)關(guān)系，對(duì)集合A中的任意元素a,稱A中與a等價(jià)的全體元素所組成的集合為由a生成的等價(jià)類，記作aR。即aR=b|bA且(a,b)R,a稱為這一等價(jià)類的代表元代表元或生成元生成元。116例2.28設(shè)A=1,2,8,如下定義A上的二元關(guān)系R=(x，y)|x，yA且xy(mod 3)，其中xy(mod 3)叫做x與y模3相等，求R的等價(jià)類。117解 1R=1，4，7 2R=2，5，8 3R=3，6 4R=1，4，7 5R=2，5，8

55、6R=3，6 7R=1，4，7 8R=2，5，8即1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6所以不同的等價(jià)類只有3個(gè)1R、2R 、3R。 118定義定義2.20設(shè)R為非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集商集，記做A/R，即A/R=aR|aAA/R的基數(shù)（即不同類的個(gè)數(shù)）稱為R的秩秩。 119例2.29 在例2.28中的商集為A/R=1,4,7,2,5,8,3,6,關(guān)系R的秩為3。120例2.30 整數(shù)集Z上模m的等價(jià)關(guān)系R=(x,y)|x,yZ且xy(mod) m其等價(jià)類是： 0R=km|kZ1R=km+1|kZm-1R=km+(m-1)

56、|kZ因此商集為Z/R=0R，1R，m-1R121定理定理2.17 設(shè)R為非空集合A上的等價(jià)關(guān)系,則：（1） aA，aR是A的非空子集。（2） a,bA，如果(a,b)R，則aR=bR。（3） a,bA，如果(a,b)R，則aRbR=。（4）aR|aA=A 122證明證明 （1）aA，由R的自反性，有(a,a)R，所以aaR，因此aR非空；再由等價(jià)類定義，aRA。（2）對(duì)于xaR，則(a,x)R ，又因?yàn)?a,b)R ，由R的對(duì)稱性與傳遞性，可得(b,x)R ，于是xbR，因此aRbR。同樣可證bRaR 所以aR=bR（3）反證法：如果有元素xaRbR，則(a,x)R且(b,x)R ，由R的對(duì)

57、稱性和傳遞性，可得(a,b)R ，與(a,b)R矛盾，所以aR與bR不交。123 (4)先證aR|aAA 任取b，baR|aA a使得aA且baR) bA (因?yàn)閍R A)aR|aAA 再證 AaR|aA 任取b， bA bbR baR |aA AaR|aA成立。綜上所述得aR|aA=A。1242.6.2 集合的劃分定義定義2.21 ：設(shè)A是任意非空集合， A1，A2，Am是集合A的子集,滿足：（1）Ai (i=1,2,m)；（2） AiAj= (ij)； （3）A1A2 Am=A。則集合族=A1，A2，Am為A的一個(gè)劃分劃分，而A1，A2，Am為這個(gè)劃分的劃分塊劃分塊。125例例2.31設(shè)集

58、合A=1,2,3,4,則1=1,2,3,4, 2=1,2,3,4, 3=1,2,3,4, 4=1,2,3,4均為對(duì)集合A的劃分。例例2.32設(shè)集合A=a,b,c,d，判斷下列子集是否是A的劃分。(1) a,b,c,d,b,d(2) a,b,c,d(3) a,b,c,(4) a,b,c,d(5) a,b,c,d解： 根據(jù)劃分的定義有（1），（3）不是A的劃分，（2），（4），（5）是A的劃分。126細(xì)分、真細(xì)分定義定義2.22設(shè)1=A1,A2,An和2=B1,B2,Bm是集合S的兩種劃分,如果1中的每個(gè)Ai都是2中某個(gè) Bj的子集,則稱劃分1是劃分2的一個(gè)細(xì)分細(xì)分。如果1是2的細(xì)分，且1中至少有

59、一個(gè)Ai是某個(gè)Bj的真子集，則稱1是2的真細(xì)分真細(xì)分。127例例2.33 設(shè)集合A=1,2,3,4，則在例2.31中： (1) 劃分1=1,2,3,4是2=1，2,3,4的細(xì)分，也是真細(xì)分。（2） 劃分3=1,2,3,4是4=1,2,3,4的細(xì)分，也是真細(xì)分。對(duì)集合A=1,2,3,4，有1=1,2,3,4是對(duì)集合A的任意一個(gè)劃分的細(xì)分，而對(duì)集合A的任意一個(gè)劃分都是劃分4=1,2,3,4的細(xì)分。128最大劃分、最小劃分、交叉劃分定義定義2.23設(shè)A是非空集合，G=a|aA稱為A的最大劃分最大劃分，S=A稱為A的最小最小劃分劃分。例例2.34 在例2.31中的劃分1=1,2,3,4是對(duì)集合A的最大

60、劃分，劃分4=1,2,3,4是對(duì)集合A的最小劃分。129最大劃分、最小劃分、交叉劃分定義定義2.24設(shè)1=A1,A2,An和2=B1,B2,Bm是集合S的兩種劃分，稱AiBj|AiBj ,1i n,1j m為1和2的交叉劃分交叉劃分。例例2.35設(shè)集合A=1,2,3,4,則在例2.31中的劃分2=1,2,3,4與劃分3=1,2,3,4的交叉劃分為23=1,2,3,4。130定理定理2.18 ：設(shè)1=A1,A2,An和2=B1,B2,Bm是集合S的兩種劃分，則其交叉劃分= 12也是S的一個(gè)劃分。131證明證明 交叉劃分= AiBj|AiBj ,1in,1jm 。在中任取兩個(gè)元素AiBh，AjBk