離散數(shù)學(xué)關(guān)系課件

章

2021/5/91在現(xiàn)實(shí)生活中,集合與集合之間還存在著某種聯(lián)系，如同學(xué)關(guān)系、朋友關(guān)系等。這些關(guān)系正是各門學(xué)科所要研究的主要內(nèi)容。離散數(shù)學(xué)從集合出發(fā)，主要研究集合之間的關(guān)系。本章內(nèi)容主要研究二元關(guān)系。2021/5/92本章主要內(nèi)容：關(guān)系的基本概念關(guān)系的表示方法關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系與劃分偏序關(guān)系2021/5/932.1關(guān)系的基本概念為了討論關(guān)系，首先引入有序?qū)偷芽▋悍e兩個(gè)概念。由兩個(gè)元素a,b組成的集合{a,b}中，a和b是沒有次序的。有時(shí)需要考慮有次序的兩個(gè)元素，所以需要由兩個(gè)元素組成新的東西，并且兩個(gè)元素是有次序的。定義2.1兩個(gè)元素a,b有次序地放在一起，稱為一個(gè)有序?qū)蛐蚺?，記?a,b)。在有序?qū)?a,b)中，a稱為第一元素，b稱為第二元素。且(a1,b1)=(a2,b2)當(dāng)且僅當(dāng)a1=a2

且b1=b2。2021/5/94定義2.2

設(shè)A,B

是兩個(gè)集合，集合{(x,y)|x∈A

且y∈B}稱為A

和B

的笛卡兒積，也稱卡氏積，記為A×B。用屬于關(guān)系來表示就是：(x,y)∈A×B

當(dāng)且僅當(dāng)x∈A

且y∈B和(x,y)?A×B

當(dāng)且僅當(dāng)x?A或y?B。其中A

稱為第一集合，B

稱為第二集合。2021/5/95例2.1

設(shè)A={1,2,3},B={a,b}，求A×B。由笛卡兒積的定義可知有A×=×A=

。又由有序?qū)Φ男再|(zhì)可知，一般沒有A×B≠B×A。A×B也是一個(gè)集合，所以可以和另一集合C作笛卡兒積(A×B)×C，類似地有A×(B×C)。但是，一般沒有(A×B)×C=A×(B×C)，且A×B中的元素既不是A中的元素，也不是B中的元素。2021/5/96定理2.1如果B1A1，B2A2，則B1×B2

A1×A2。2021/5/97證明對(duì)(x,y)∈B1×B2，有x∈B1

且y∈B2，又因?yàn)锽1

A1

，B2

A2

，則x∈A1

且y∈A2，所以(x,y)∈A1×A2，即B1×B2

A1×A2。2021/5/98定理2.2

A,B,C

是任意集合，則：(1)A×(B∪C)=(A×B)∪(A×C)，(B∪C)×A=(B×A)∪(C×A)。(2)A×(B∩C)=(A×B)∩(A×C)，(B∩C)×A=(B×A)∩(C×A)。(3)A×(B-C)=(A×B)-(A×C)，

(B-C)×A=(B×A)-(C×A)。2021/5/99證明

(1)對(duì)(x,y)∈A×(B∪C)，有x∈A

且y∈B∪C，因此x∈A且(y∈B

或y∈C)，當(dāng)y

∈B時(shí)，由x∈A

和y∈B

得(x,y)∈A×B，當(dāng)y∈C

時(shí)，由x∈A

和y∈C得(x,y)∈A×C，所以(x,y)∈(A×B)∪(A×C)，即A×(B∪C)?(A×B)∪(A×C)。因?yàn)锳?A，B?B∪C

和C?B∪C

得A×B?A×(B∪C)和A×C?A×(B∪C)，因此(A×B)∪(A×C)?A×(B∪C)。因此A×(B∪C)=(A×B)∪(A×C)成立。同理可證(B∪C)×A=(B×A)∪(C×A)。2021/5/910(2)對(duì)(x,y)∈(A×B)∩(A×C)，有(x,y)∈A×B且(x,y)∈A×C，所以（x∈A且y∈B）且（x∈A且y∈C）。由y∈B且y∈C得y∈B∩C，由x∈A且y∈B∩C得(x,y)∈A×(B∩C)。因此(A×B)∩(A×C)A×(B∩C)。因?yàn)锳?A，B∩C?B和B∩C?C，所以有A×(B∩C)?A×B和A×(B∩C)?A×C成立，因此A×(B∩C)?(A×B)∩(A×C)。因此A×(B∩C)=(A×B)∩(A×C)。同理可證(B∩C)×A=(B×A)∩(C×A)。2021/5/911(3)對(duì)(x,y)∈A×(B-C)，有x∈A且y∈B-C，所以x∈A且y∈B且yC。由x∈A且y∈B得(x,y)∈A×B，由y

C得(x,y)A×C，所以(x,y)∈(A×B)-(A×C)。因此A×(B-C)?(A×B)-(A×C)。對(duì)(x,y)∈(A×B)-(A×C)，有(x,y)∈A×B且(x,y)A×C，由(x,y)∈A×B得x∈A且y∈B，由x∈A和(x,y)A×C得y

C，所以x∈A且y∈B且yC。由y∈B且y

C得y∈B-C，所以(x,y)∈A×(B-C)。因此(A×B)-(A×C)?A×(B-C)。因此A×(B-C)=(A×B)-(A×C)。同理可證(B-C)×A=(B×A)-(C×A)。2021/5/912定義2.3

任給n≥2，n個(gè)元素a1，…,an

有次序地放在一起，稱為一個(gè)n元有序組，記為(a1，…，an)。為了體現(xiàn)n元有序組的次序，規(guī)定(a1，…，an)=

(b1,，…，bn)當(dāng)且僅當(dāng)任給1≤i≤n，都有ai=bi。n元有序組可以組成集合，特別地有n個(gè)集合的卡氏積。2021/5/913定義2.4

任給n≥2，A1，…，An

是n個(gè)集合，集合{(x1,?,xn)|任給1≤i≤n，都有xi∈Ai}稱為A1，…，An

的卡氏積，記為A1×…×An。任給1≤i≤n，Ai

稱為這個(gè)卡氏積的第i

個(gè)集合。2021/5/914定義2.5

如果一個(gè)集合滿足以下條件之一：（1）集合非空，且它的元素都是有序?qū)?；?）集合是空集。則稱該集合為一個(gè)二元關(guān)系，記作R。二元關(guān)系也可簡稱為關(guān)系。對(duì)于二元關(guān)系R，如果(x,y)∈R，可記作xRy；如果(x,y)R，則記作xRy。設(shè)A，B為集合，A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)則叫做A上的二元關(guān)系。2021/5/915例2.2

設(shè)集合A={0,1}，B={1,2,3}，那么R1={(0,2)}，R2=A×B，R3=，R4={(0,1)}等都是從A到B的二元關(guān)系，而R3和R4同時(shí)也是A上的二元關(guān)系。2021/5/916定義2.6笛卡爾積A1×A2×…×An的任意一個(gè)子集R稱為A1，A2，…，An上的一個(gè)n元關(guān)系。當(dāng)A1=A2=…=An=A時(shí)，稱R為A上的n元關(guān)系。定義2.7

空集上定義一個(gè)二元關(guān)系，簡稱空關(guān)系；若一個(gè)n元關(guān)系R本身是笛卡兒積A1×A2×…×An

，則稱R為全關(guān)系，用符號(hào)UA表示，即UA={(ai，aj)|ai，aj∈A}為A上的全關(guān)系。符號(hào)IA={(x,x)|x∈A}為A上的恒等關(guān)系

2021/5/917例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)2∈A}(3)R={(x,y)|x/y是素?cái)?shù)}(4)R={(x,y)|x≠y}2021/5/918解：(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)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)}2021/5/919定義2.8RA×B中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域，記為domR。形式化表示為：domR={x|x∈A,y∈B,使得(x,y)∈R}。RA×B中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域，記作ranR。形式化表示為ranR={y|y∈B,x∈A,使得(x,y)∈R}。2021/5/920定義2.9

設(shè)R為二元關(guān)系，R的逆關(guān)系，簡稱R的逆，記作R-1,其中R-1={(y,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)}，DomR={2,3,4},RanR={3,4,6}，R-1={(4,2),(6,2),(3,3),(6,3),(4,4)}2021/5/921關(guān)系從本質(zhì)上講，仍是集合，只是這個(gè)集合中的元素都是以有序?qū)Φ男问匠霈F(xiàn)。既然關(guān)系是一個(gè)集合，那么集合的表示方法就可以用來表示關(guān)系，又因?yàn)殛P(guān)系是一個(gè)特殊的集合，其中的元素均以序偶的形式出現(xiàn)，除了可以用集合的表示方法外，還可以用其他的表示方法。這里主要介紹如下幾種表示方法。2.2關(guān)系的表示方法2021/5/9221.用列舉法表示二元關(guān)系如果二元關(guān)系中的序偶個(gè)數(shù)是有限的，可以用列舉法將其所包含的全部元素一一列舉出來。例2.5

設(shè)集合A={1,2,3}，在集合A上定義的小于等于關(guān)系，LA={(a,b)|a,b∈A,a≤b}，則LA={(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}。2021/5/9232.用描述法表示二元關(guān)系用確定的條件表示某些序偶是否屬于這個(gè)關(guān)系，并把這個(gè)條件寫在大括號(hào)內(nèi)表示關(guān)系的方法。格式是：LR={(x,y)|x∈R且y∈R且x≥y}。例2.6設(shè)A={1，2，3，4}，下面兩式定義的R1和R2都是A上的關(guān)系，分別列出R1與R2的元素如下：

(1)R1={(x,y)|x是y的倍數(shù)}(2)R2={(x,y)|(x-y)2∈A}2021/5/924解：(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)}2021/5/9253.用關(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

rij=0，當(dāng)且僅當(dāng)(ai,bj)R2021/5/926例2.7

例2.5中的關(guān)系R的關(guān)系矩陣為：例2.8

例2.6中的關(guān)系R1與R2的關(guān)系矩陣分別為：，2021/5/9274.用關(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處畫一條自封閉的弧線,其中1≤i,j≤n。這樣表示R中關(guān)系的圖形，稱為R的關(guān)系圖，用GR表示。2021/5/928例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所示。2021/5/929關(guān)系R的集合表達(dá)式、關(guān)系矩陣MR、關(guān)系圖GR三者均可唯一相互確定2021/5/930定義2.11

設(shè)關(guān)系R和S是從A到B的兩個(gè)二元關(guān)系，對(duì)于aA，bB，定義：（1）R∪S：(a,b)∈R∪S(a,b)∈R或(a,b)∈S。（2）R∩S：(a,b)∈R∩S(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)∈A×B-R。2.3關(guān)系的運(yùn)算2021/5/931例2.10

設(shè)集合A={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)}

則

R∪S={(a,1),(b,2),(c,1),(b,1),(c,2)}

R∩S={(a,1)}

R-S={(b,2),(c,1)}

R=A×B－R={(a,2),(b,1),(c,2)}2021/5/932因?yàn)殛P(guān)系可以用矩陣的形式表示，當(dāng)我們用矩陣的形式求關(guān)系的并、交、補(bǔ)及對(duì)稱差的運(yùn)算時(shí)，可以用如下形式表示：MR∪S=MRMS

（矩陣的對(duì)應(yīng)分量做邏輯析取運(yùn)算）MR∩S=MRMS

（矩陣的對(duì)應(yīng)分量做邏輯合取運(yùn)算）MR-S=MR∩S=MRMS

MR=MR

（矩陣的對(duì)應(yīng)分量做邏輯非運(yùn)算）2021/5/933例2.11對(duì)例2.10中的關(guān)系的運(yùn)算采用矩陣的形式表示如下：根據(jù)題意，關(guān)系R與S的關(guān)系矩陣分別表示為則2021/5/934定理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)(R∪S)-1=R-1∪S-1(分配律)(R∩S)-1=R-1∩S-1(R-S)-1=R-1-S-1 (4)SRS-1

R-1(單調(diào)性) SRS

R (5)domR-1=ranR，ranR-1=domR (6)(AB)-1=BA2021/5/935證明：這里只證明（1）和（5）。(1)任取(x,y)，由逆的定義有(x,y)∈(R-1)-1

(y,x)∈R-1

(x,y)∈R。

所以有(R-1)-1=R。(5)任取x,x∈domR-1

y((x,y)∈R-1)

y((y,x)∈R))

x∈ranR

所以有domR-1=ranR。

同理可證ranR-1=domR。2021/5/936合成關(guān)系定義2.12設(shè)R是從集合A到集合B的二元關(guān)系，S是從集合B到集合C的二元關(guān)系，則R與S的復(fù)合關(guān)系（合成關(guān)系）R·S是從A到C的關(guān)系，并且，R·S={(x,z)|x∈A且z∈C且存在y∈B使得(x,y)∈R,(y,z)∈S}，運(yùn)算“·”稱為復(fù)合運(yùn)算或合成運(yùn)算。2021/5/937例2.12

設(shè)A上的二元關(guān)系R={(x,y)|x,yA,x是y的父親}，S={(x,y)|x,yA,x是y的母親}

(1)說明R?R，R-1

?S–1

，R-1?S的含義。(2)表示以下關(guān)系：

{(x,y)|x,yA,y是x的外祖母}

{(x,y)|x,yA,x是y的祖母}2021/5/938解：

(1)R?R表示關(guān)系{(x,y)|x,yA,x是y的祖父}

R-1

?S–1

表示關(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

?S–1

{(x,y)|x,yA,x是y的祖母}表示為S?R2021/5/939例2.13設(shè)Z是整數(shù)集合，R，S是Z到Z的兩個(gè)關(guān)系：R={(x,3x)|x∈Z}；S={(x,5x)|x∈Z}。計(jì)算R·S；S·R；R·R；S·S；(R·R)·R；(R·S)·R。2021/5/940解R·S={(x,15x)|x∈Z}；S·R={(x,15x)|x∈Z}；R·R={(x,9x)|x∈Z}；S·S={(x,25x)|x∈Z}；(R·R)·R={(x,27x)|x∈Z}；(R·S)·R={(x,45x)|x∈Z}。2021/5/941定理2.4R為定義在集合A上的關(guān)系,則R·IA=IA·R=R2021/5/942證明任取(x,y)，有(x,y)∈R·IAt((x,t)∈R且(t,y)∈IA)t((x,t)∈R且t=y)(x,y)∈R又有(x,y)∈R(x,y)∈R且x,y∈A(x,y)∈R且(y,y)∈IA(x,y)∈R·IA所以，R·IA=R。同理可證IA·R=R。2021/5/943定理2.5

設(shè)R1A1A2

，R2

A2A3

，R3A3A4，則

(1)(R1?R2)?R3=R1?(R2?R3)

(2)(R1?R2)-1=R2-1?R1-1不滿足交換律，即R1?R2

R2?R12021/5/944證明：(1)任取(x,y),(x,y)∈(R1?R2)?R3(t∈A3)(使得(x,t)∈R1?R2且(t,y)∈R3)(t∈A3)(((s∈A2),使得(x,s)∈R1且(s,t)∈R2)且(t,y)∈R3)(t∈A3)(s∈A2)(使得(x,s)∈R1且(s,t)∈R2且(t,y)∈R3)

(s∈A2)(使得(x,s)∈R1且(t∈A3)(使得(s,t)∈R2且(t,y)∈R3))(s∈A2)(使得(x,s)∈R1且(s,y)∈R2?R3)(x,y)∈R1?(R2?R3)

所以(R1?R2)?R3=R1?(R2?R3)2021/5/945由歸納法，任意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)系。2021/5/946（2）任取(z,x)∈(R1·R2)-1，則（x,z)∈R1·R2，由“·”的定義知，至少存一個(gè)y∈B，使得(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·R-11

。所以，(R1·R2)-1R-12·R-11

。反之，任取(z,x)R-12·R-11

，由“·”的定義知：則至少存在一個(gè)y∈B，使得(z,y)∈R-12和(y,x)∈R-11

，所以(x,y)∈R1，(y,z)∈R2。由“·”知(x,z)∈R1·R2。即有(z,x)∈(R1·R2)-1。所以，R-12·R-11(R1·R2)-1。由集合的性質(zhì)知：(R1·R2)-1=R-12·R-11

。2021/5/947例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,……)2021/5/948解：

R1=R；R2=R·R={(a,a),(a,b),(a,c),(b,d),(c,e),(d,f)}；R3=R·R·R=R2·R={(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)}；R4=R3·R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)}；R5=R4·R={(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)}；R6=R5·R={(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)}=R5；R7=R6·R=R5；…Rn=R5（n＞5）。2021/5/949冪集Rn的基數(shù)|Rn|并非隨著n的增加而增加，而是呈遞減趨勢，而且，當(dāng)時(shí)，有

2021/5/9502.4關(guān)系的性質(zhì)有了關(guān)系的定義，可以來定義關(guān)系的某些特殊性質(zhì)，這些性質(zhì)在以后的討論中，將起到極其重要的作用。本節(jié)主要討論關(guān)系的五種性質(zhì)，即自反性、反自反性、對(duì)稱性、反對(duì)稱性和傳遞性。2021/5/951自反、反自反定義2.14設(shè)R為集合A上的二元關(guān)系：（1）若對(duì)任意的x∈A，都有(x,x)∈R，則稱關(guān)系R在集合A上是自反的或稱關(guān)系R具有自反性；否則，稱R是非自反的。（2）若對(duì)任意的x∈A，都有(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)系2021/5/952例2.15

設(shè)A={1,2,3}，R1={(1,1),(2,2)}，R2={(1,1),(2,2),(3,3),(1,2)}，R3={(1,3)}，說明R1，R2，R3是否為A上自反的關(guān)系。2021/5/953解：只有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來說的。同一個(gè)關(guān)系在不同的集合上具有不同的性質(zhì)。2021/5/954例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),(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)}說明R,S,T在A上的自反性與反自反性。2021/5/955解：因?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)系。2021/5/956定理2.6

設(shè)R是定義在集合A上的二元關(guān)系，R是自反的當(dāng)且僅當(dāng)IA

R。2021/5/957證明（1）必要性設(shè)R在A上是自反的，則IA

R。根據(jù)恒等關(guān)系的定義，對(duì)任意的x∈A有(x,x)∈IA，又因?yàn)镽在A上是自反的，即對(duì)于任意的x∈A有(x,x)∈R，因此IA

R。

（2）充分性設(shè)IA

R，則R在A上是自反的。對(duì)任意的x∈A有(x,x)∈IA，而IA

R，因此對(duì)任意的x∈A有(x,x)∈R，即R在A上是自反的。2021/5/958定理2.7設(shè)R是定義在集合A上的二元關(guān)系，R是反自反的當(dāng)且僅當(dāng)R∩IA=。2021/5/959證明（1）必要性設(shè)R在A上是反自反的，則R∩IA=。假設(shè)R∩IA，比如存在（x，y）R∩IA，即（x，y）R且（x，y）

IA

，也即（x，y）R且x=y，即（x，x）R，與R在A上是反自反的相矛盾。因此R∩IA=。充分性設(shè)R∩IA=，則R在A上是反自反的。對(duì)任意的xA，有(x,x)IA

，由于R∩IA=，因此(x,x)R，即R在A上是反自反的。2021/5/960對(duì)稱、反對(duì)稱定義2.15設(shè)R為A上的關(guān)系。(1)若對(duì)任意的x與y，都有x,y∈A且(x,y)∈R，則有(y,x)∈R，則稱R為A上對(duì)稱關(guān)系；否則，稱R是非對(duì)稱的。(2)若對(duì)任意的x與y，都有x,y∈A且當(dāng)(x,y)∈R，(y,x)∈R時(shí)，有x=y，則稱R為A上的反對(duì)稱關(guān)系。對(duì)稱：全關(guān)系、恒等關(guān)系、空關(guān)系反對(duì)稱：恒等關(guān)系、空關(guān)系2021/5/961例2.17

設(shè)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)}試說明R，S，T是否是A上的對(duì)稱關(guān)系和反對(duì)稱關(guān)系。2021/5/962解：根據(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中的元素，但是a≠b，所以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中的元素，但是a≠b，因此也不滿足反對(duì)稱性。2021/5/963定理2.8

設(shè)R是A上的二元關(guān)系，R是對(duì)稱的當(dāng)且僅當(dāng)R=R-1。2021/5/964證明

(1)必要性設(shè)R是對(duì)稱的，則R=R-1。(x，y)R(y，x)R(x，y)R-1R=R-1。(2)充分性設(shè)R=R-1，則R是對(duì)稱的。(x，y)R(y，x)R-1(y，x)R，因此R是對(duì)稱的。2021/5/965定理2.9

設(shè)R是A上的二元關(guān)系，R是反對(duì)稱的當(dāng)且僅當(dāng)R∩R-1IA。2021/5/966證明

(1)必要性設(shè)R是反對(duì)稱的，則R∩R-1IA。(x，y)R∩R-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，所以R∩R-1IA。(2)充分性設(shè)R∩R-1IA，則R是反對(duì)稱的。(x，y)R且(y，x)R(x，y)R且(x，y)R-1(x，y)R∩R-1因?yàn)镽∩R-1IA，所以(x，y)IA，顧x=y，因此R是反對(duì)稱的。2021/5/967傳遞定義2.16

設(shè)R為A上的關(guān)系，若對(duì)任意的x，y，z有x,y,z∈A且當(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)系、小于、包含2021/5/968例2.18

設(shè)A={1,2,3}，R1={(1,1)}，R2={(1,3),(2,3)}，R3={(1,1),(1,2),(2,3)}，說明R1，R2，R3是否為集合A上傳遞的關(guān)系。2021/5/969解：根據(jù)定義2.16，R1，R2是A上傳遞的關(guān)系；但R3不是傳遞的，因?yàn)?1,2)∈R3，(2,3)∈R3，而(1,3)R3，由傳遞關(guān)系的定義知R3不是傳遞的關(guān)系。2021/5/970定理2.10

設(shè)R是集合A上的二元關(guān)系，則R是傳遞的當(dāng)且僅當(dāng)R.RR2021/5/971證明(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是傳遞的。2021/5/9722.4.2關(guān)系性質(zhì)的證明在二元關(guān)系中，除了對(duì)一個(gè)具體的關(guān)系判斷它具有哪些性質(zhì)外，更多的是針對(duì)一個(gè)抽象的關(guān)系，利用它的特點(diǎn)來證明它具有某個(gè)性質(zhì)。由于關(guān)系性質(zhì)的定義全部都是按“如果……那么……”來描述的，在證明這類問題時(shí)，一般采用按照定義證明的方法。這種證明問題的方法在于：證明時(shí)不能僅僅利用題目所給的已知條件，還要同時(shí)結(jié)合定義中的“已知”，并且推出的并非整個(gè)定義，而是定義中的結(jié)論。另外，由于關(guān)系是特殊的集合，當(dāng)用集合的手段來描述關(guān)系的性質(zhì)時(shí)，其證明的方法也是按集合中的按定義證明方法來證。2021/5/973例2.19設(shè)R1，R2是定義在集合A上的兩個(gè)關(guān)系，并且R1，R2具有傳遞性，則R1∩R2也具有傳遞性。2021/5/974證明：對(duì)任意x,y∈A，則若(x,y)∈R1∩R2且(y,z)∈R1∩R2(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)∈R1∩R2根據(jù)定義2.16，R1∩R2具有傳遞性。2021/5/975關(guān)系性質(zhì)與集合運(yùn)算運(yùn)算性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R∪S√√√××R∩S√√√√√R-S×√√√×R-1√√√√√R?S√××××2021/5/9762.5關(guān)系的閉包對(duì)于在非空集合上定義的關(guān)系R不一定具備某種性質(zhì)或某幾種性質(zhì)，而這些性質(zhì)對(duì)研究某些具體的問題時(shí)又非常重要，這時(shí)就需要構(gòu)造一個(gè)基于此關(guān)系的新關(guān)系，使其具備所需要的性質(zhì)，即往該關(guān)系中添加一些適量的元素以改變?cè)嘘P(guān)系的性質(zhì)，得到新的關(guān)系，使得新關(guān)系具有所需要的性質(zhì)，但又不希望新關(guān)系與R相差太多，也就是說，要盡可能少地來添加有序?qū)?，滿足這些要求的新關(guān)系就稱為R的閉包。本節(jié)介紹關(guān)系的自反、對(duì)稱和傳遞閉包。2021/5/977定義2.17設(shè)R是非空集合A上的關(guān)系，R的自反（對(duì)稱或傳遞）閉包是A上的關(guān)系Rc，使得Rc滿足以下條件：(1)Rc是自反的（對(duì)稱的或傳遞的）；(2)RRc；(3)對(duì)A上任何包含R的自反（對(duì)稱或傳遞）關(guān)系Rp有Rc

Rp。一般將R的自反閉包記作r(R)，對(duì)稱閉包記作s(R)，傳遞閉包記作t(R)。2021/5/978定理2.11

設(shè)R為定義在非空集合A上的二元關(guān)系，則有（1）r（R）=R∪IA（2）s（R）=R∪R-1（3）t（R）=R∪R2∪R3∪…2021/5/979證明（1）令R′=R∪IA，則有①IA

R∪IA

，而R∪IA=R′，因此R′是自反的。②RR∪IA

，而R∪IA=R′，因此RR′。③假設(shè)R″是A上的任意自反關(guān)系并且RR″，因?yàn)镽″是自反的，所以IAR″，因此有R′=R∪IA

R″。由自反閉包的定義，R′=R∪IA是R的自反閉包，即r(R)=R′=R∪IA

。2021/5/980（2）令R=R∪R-1①(R)-1=(R∪R-1)-1=R-1∪(R-1)-1=R-1∪R=R∪R-1=R,因此R是對(duì)稱的。②RR∪R-1，而R∪R-1=R，因此RR。③設(shè)R是A上的任意對(duì)稱關(guān)系并且RR，又(x，y)R-1(y，x)R(y，x)R，從而有R=R∪R-1R。因此R是R的對(duì)稱閉包，即s(R)=R∪R-1。2021/5/981（3）分兩部分來證所要的結(jié)論。先證R∪R2∪R3∪…t（R）用數(shù)學(xué)歸納法來證，對(duì)任意自然數(shù)i，有Rit（R）①當(dāng)i=1時(shí)，由傳遞閉包的定義，R1=Rt（R）。②假設(shè)當(dāng)i=n時(shí)，Rnt（R）,下證Rn+1t（R）。對(duì)任意的(x,y)∈Rn+1，存在c∈A，使得(x,c)∈Rn且(c,y)∈R，即存在c∈A，使得(x,c)∈t(R)且(c,y)∈t(R)，則(x,y)∈t(R)。即Rn+1

t(R)，因此，R∪R2∪R3∪…t(R)。再證明t(R)R∪R2∪R3∪…。顯然，有RR∪R2∪R3∪…成立，下證R∪R2∪R3∪…是傳遞的。(x,y)∈R∪R2∪R3∪…t(R)且(y,z)∈R∪R2∪R3∪…t∈A，使得(x,y)∈Rt且s∈A，使得(y,z)∈Rs(x,z)∈Rt·Rs=Rt+sR∪R2∪R3∪…(x,z)∈R∪R2∪R3∪…由傳遞關(guān)系的定義，R∪R2∪R3∪…是傳遞的。綜上所述，R∪R2∪R3∪…是包含R的傳遞關(guān)系。而R的傳遞閉包是包含R的最小傳遞關(guān)系，因此t(R)R∪R2∪R3∪…。即t(R)=R∪R2∪R3∪…成立。2021/5/982推論

設(shè)R是有限集合A上的關(guān)系，|A|=n，此時(shí)t（R）=R∪R2∪R3∪…Rn有。2021/5/983例2.20設(shè)集合A={a,b,c}，R是A上的二元關(guān)系，且R={(a,b),(b,c),(c,a)}，求出關(guān)系R的自反、對(duì)稱和傳遞閉包。2021/5/984解：r(R)=R∪IA={(a,a),(b,b),(c,c),(a,b),(b,c),(c,a)}s(R)=R∪R-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=R6…t(R)=R∪R2∪R3∪…=R∪R2∪R3={(a,a),(b,b),(c,c),(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)}2021/5/985例2.21設(shè)集合A={a,b,c}，R是A上的二元關(guān)系，且R={(a,b),(b,c),(c,a)}，用關(guān)系矩陣求關(guān)系R的自反、對(duì)稱和傳遞閉包。2021/5/986解關(guān)系的關(guān)系矩陣為：2021/5/987定理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)不一定傳遞。2021/5/988證明(1)若R是自反的，則有IA

R。又因?yàn)镽s(R)，且Rt(R)，所以IAs(R)且IA

t(R)，因此s(R)與t(R)是自反的。(2)因?yàn)镽對(duì)稱，有R=R-1。由于r(R)=R∪IA

，而(r(R))-1=(R∪IA)-1=R-1∪IA-1=R∪IA=r(R),因此r(R)對(duì)稱。因?yàn)镽對(duì)稱，因此(Ri)-1=(R-1)i=Ri。由于t(R)=R∪R2∪R3∪…,于是(t(R))-1=(R∪R2∪R3∪…)-1=R-1∪(R2)-1∪(R3)-1∪…=R∪R2∪R3∪…=t(R)所以t(R)也對(duì)稱。2021/5/989(3)因?yàn)镽傳遞，所以R.RR，而r(R)=R∪IA

，則有r(R).r(R)=(R∪IA)(R∪IA)=R.(R∪IA)∪IA.(R∪IA)=R.R∪RIA∪IA.(R∪IA)=R.R∪R∪(R∪IA)

R∪R∪(R∪IA)=R∪IA=r(R)即r(R)具有傳遞性。2021/5/990下面舉一個(gè)反例來說明s(R)不具備傳遞性。假設(shè)集合A={1,2,3}，R={(1,2)}是定義在集合A上的且具有傳遞性，而s(R)={(1,2),(2,1)}卻不具備傳遞性。2021/5/991定理2.13

設(shè)R1,R2A×A，且R1R2，則

r(R1)r(R2) s(R1)s(R2) t(R1)t(R2)2021/5/992證明：(1)因?yàn)镽1R2，因此R1∪IAR2∪IA，所以r(R1)r(R2)。反證法： 假設(shè)(x,y)r(R1),但(x,y)r(R2)，則r(R1)–{(x,y)}也是自反的，即xy;如果(x,y)R1，則(x,y)R2，那么(x,y)r(R2)，導(dǎo)致矛盾，因此(x,y)R1，所以R1r(R1)–{(x,y)}，那么r(R1)不是R1的自反閉包，矛盾。因此(x,y)r(R2)。所以r(R1)r(R2)。2021/5/993(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)。2021/5/994定理2.14

設(shè)R1和R2是集合A上的關(guān)系，則以下各式成立。（1）r（R1∪R2

）=r（R1

）∪r（R2

）（2）s（R1∪R2

）=s（R1

）∪s（R2

）（3）t（R1

）∪t（R2

）t（R1∪R2

）2021/5/995證明：（1）r(R1∪R2)=IA∪(R1∪R2)=(IA∪R1)∪(IA∪R2)=r(R1)∪r(R2)（2）s(R1∪R2)=(R1∪R2)∪(R1∪R2)-1=(R1∪R2)∪(R-11∪R-12)=(R1∪R-11)∪(R2∪R-12)=s(R1)∪s(R2)（3）因?yàn)镽1R1∪R2

，R2R1∪R2

，所以t(R1)t(R1∪R2)，t(R2)t(R1∪R2)，得出t(R1)∪t(R2)t(R1∪R2)。一般地，t(R1)∪t(R2)≠t(R1∪R2)。2021/5/996例2.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(R1∪R2)={(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)}t(R1)∪t(R2)={(1,2),(1,3),(2,3),(3,2)}由此可見t(R1)∪t(R2)≠t(R1∪R2)。2021/5/997定理2.15

設(shè)R是集合A上的關(guān)系，則（1）rs(R)=sr(R)；（2）rt(R)=tr(R)；（3）st(R)ts(R)。2021/5/998證明（1）2021/5/999(2)

2021/5/9100(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)。2021/5/9101例2.23設(shè)A={1,2}，R={(1,2)}，求st(R)與ts(R)。2021/5/9102例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)=t(s(R))=t{(1,2),(2,1)}={(1,2),(2,1),(1,1),(2,2)}2021/5/91032.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)行分析更簡單。2021/5/91042.6.1等價(jià)關(guān)系定義2.18設(shè)R為非空集合A上的關(guān)系。如果R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。設(shè)R是一個(gè)等價(jià)關(guān)系，若(x，y)∈R，稱x等價(jià)于y，記做x～y。2021/5/9105例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)系。2021/5/9106例2.25設(shè)關(guān)系R是定義在有理數(shù)集Q上的關(guān)系，并且(x,y)∈R，當(dāng)且僅當(dāng)x-y是整數(shù)，試證R是等價(jià)關(guān)系。2021/5/9107例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ù)x∈Q，有x-x=0是整數(shù)，即對(duì)所有的有理數(shù)有(x,x)∈R，因此R滿足自反性。(2)對(duì)稱性：假設(shè)x,y∈Q，并且(x,y)∈R，即x-y是整數(shù)，則y-x=-(x-y)也是整數(shù)，即(y,x)∈R，因此R滿足對(duì)稱性。(3)傳遞性：假設(shè)x,y,z∈Q，并且(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)系。2021/5/9108例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)系。2021/5/9109證明：寫出關(guān)系R關(guān)系矩陣如下：由關(guān)系矩陣可以看出，該矩陣的主對(duì)角線的元素都是1，即關(guān)系R滿足自反性。該關(guān)系矩陣是對(duì)稱的，即R滿足對(duì)稱性。求出R2的關(guān)系矩陣為：即R2的關(guān)系矩陣與R的關(guān)系矩陣相同，并且有R3，…，Rn都與R的關(guān)系矩陣相同，因此，t(R)=R∪R2∪R3∪…∪Rn的關(guān)系矩陣也與R的關(guān)系矩陣相同，所以R是傳遞的。綜上所述，R是A上的等價(jià)關(guān)系。2021/5/9110例2.27設(shè)A={1,2,…,8},定義A上的關(guān)系R={(x，y)|x，y∈A且x≡y(mod3)}，其中x≡y(mod3)叫做x與y模3相等，即x除以3的余數(shù)與y除以3的余數(shù)相等。試證R為A上的等價(jià)關(guān)系。2021/5/9111證明：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,y∈A，若(x,y)∈R，即x≡ymod3，則有y≡xmod3，即(y,x)∈R，因此R滿足對(duì)稱性。對(duì)x,y,z∈A，若(x,y)∈R，(y,z)∈R，即x≡ymod3，y≡zmod3，則有x≡zmod3，即(x,z)∈R，因此R滿足傳遞性。綜上所述，R是等價(jià)關(guān)系。2021/5/9112定理2.16設(shè)R是定義在集合A上的關(guān)系，則R為等價(jià)關(guān)系R*R-1=R。2021/5/9113定理2.16設(shè)R是定義在集合A上的關(guān)系，則R為等價(jià)關(guān)系R*R-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)∈R·R-1

于是,RR·R-1.另一方面，(x,y)∈R·R-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-1R.綜上可知,必要性得證.(2)充分性:由假設(shè)R·R-1=R可知,(x,y)∈R(x,y)∈R·R-1

z使得(x,z)∈R且(z,y)∈R-1

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

所以不同的等價(jià)類只有3個(gè)[1]R、[2]R

、[3]R。2021/5/9117定義2.20設(shè)R為非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集，記做A/R，即A/R={[a]R|a∈A}A/R的基數(shù)（即不同類的個(gè)數(shù)）稱為R的秩。2021/5/9118例2.29在例2.28中的商集為A/R={{1,4,7},{2,5,8},{3,6}},關(guān)系R的秩為3。2021/5/9119例2.30整數(shù)集Z上模m的等價(jià)關(guān)系R={(x,y)|x,yZ且xy(mod)m}其等價(jià)類是：[0]R={km|kZ}[1]R={km+1|kZ}…[m-1]R={km+(m-1)|kZ}因此商集為Z/R={[0]R，[1]R，…，[m-1]R}2021/5/9120定理2.17

設(shè)R為非空集合A上的等價(jià)關(guān)系,則：（1）a∈A，[a]R是A的非空子集。（2）a,b∈A，如果(a,b)∈R，則[a]R=[b]R。（3）a,b∈A，如果(a,b)R，則[a]R∩[b]R=。（4）∪{[a]R|a∈A}=A2021/5/9121證明（1）a∈A，由R的自反性，有(a,a)∈R，所以a∈[a]R，因此[a]R非空；再由等價(jià)類定義，[a]RA。（2）對(duì)于x∈[a]R，則(a,x)∈R，又因?yàn)?a,b)∈R，由R的對(duì)稱性與傳遞性，可得(b,x)∈R，于是x∈[b]R，因此[a]R[b]R。 同樣可證[b]R[a]R

所以[a]R=[b]R（3）反證法：如果有元素x∈[a]R∩[b]R，則(a,x)∈R且(b,x)∈R，由R的對(duì)稱性和傳遞性，可得(a,b)∈R，與(a,b)R矛盾，所以[a]R與[b]R不交。2021/5/9122(4)先證∪{[a]R|a∈A}A

任取b，b∈∪{[a]R|a∈A}

a使得a∈A且b∈[a]R)

b∈A(因?yàn)閇a]R

A)

∴∪{[a]R|a∈A}A

再證A∪{[a]R|a∈A}

任取b，b∈Ab∈[b]R

b∈∪{[a]R|a∈A}

∴A∪{[a]R|a∈A}成立。

綜上所述得∪{[a]R|a∈A}=A。2021/5/91232.6.2集合的劃分定義2.21

：設(shè)A是任意非空集合，A1，A2，…，Am是集合A的子集,滿足：（1）Ai≠(i=1,2,…,m)；（2）Ai∩Aj=(i≠j)；（3）A1∪A2∪…∪Am=A。則集合族={A1，A2，…，Am}為A的一個(gè)劃分，而A1，A2，…，Am為這個(gè)劃分的劃分塊。2021/5/9124例2.31設(shè)集合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},5yyonlk}(5){{a,b,c,d}}解：根據(jù)劃分的定義有（1），（3）不是A的劃分，（2），（4），（5）是A的劃分。2021/5/9125細(xì)分、真細(xì)分定義2.22設(shè)1={A1,A2,…,An}和2={B1,B2,…,Bm}是集合S的兩種劃分,如果1中的每個(gè)Ai都是2中某個(gè)Bj的子集,則稱劃分1是劃分2的一個(gè)細(xì)分。如果1是2的細(xì)分，且1中至少有一個(gè)Ai是某個(gè)Bj的真子集，則稱1是2的真細(xì)分。2021/5/9126例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ì)分。2021/5/9127最大劃分、最小劃分、交叉劃分定義2.23設(shè)A是非空集合，G={{a}|a∈A}稱為A的最大劃分，S={A}稱為A的最小劃分。例2.34

在例2.31中的劃分1={{1},{2},{3},{4}}是對(duì)集合A的最大劃分，劃分4={{1,2,3,4}}是對(duì)集合A的最小劃分。2021/5/9128最大劃分、最小劃分、交叉劃分定義2.24設(shè)1={A1,A2,…,An}和2={B1,B2,…,Bm}是集合S的兩種劃分，稱{Ai∩Bj|Ai∩Bj≠,1≤i≤n,1≤j≤m}為1和2的交叉劃分。例2.35設(shè)集合A={1,2,3,4},則在例2.31中的劃分2={{1},{2,3,4}}與劃分3={{1,2},{3,4}}的交叉劃分為2∩3={{1},{2},{3,4}}。2021/5/9129定理2.18

：設(shè)1={A1,A2,…,An}和2={B1,B2,…,Bm}是集合S的兩種劃分，則其交叉劃分=1∩2也是S的一個(gè)劃分。2021/5/9130證明交叉劃分={Ai∩Bj|Ai∩Bj≠,1≤i≤n,1≤j≤m}。在中任取兩個(gè)元素Ai∩Bh，Aj∩Bk，考察(Ai∩Bh)∩(Aj∩Bk)是否滿足集合劃分定義中的三個(gè)條件：（1）若ij且h=k，由于Ai∩Aj=，則Ai∩Bh∩Aj∩Bk=；（2）若ij且hk，由于Ai∩Aj=，Bh∩Bk=，則Ai∩Bh∩Aj∩Bk=；（3）若i=j且hk，由于Bh∩Bk=，則Ai∩Bh∩Aj∩Bk=；由此可見，在交叉劃分中，任意兩個(gè)元素的交集均為，且有交叉劃分中所有元素的并集為：2021/5/9131(A1∩B1)∪(A1∩B2)∪…∪(A1∩Bm)∪(A2∩B1)∪(A2∩B2)∪…∪(A2∩Bm)∪…∪(An∩B1)