第4章關系背景本章研究集合內元素間的關系和集合間元素的關系，即關系和函數。從本質上認識集合。離散數學中的關系理論廣泛應用于計算機科學的很多方面，如數據結構、數據庫、算法分析等，是一個非常重要的數學概念。關系和函數4.1關系的概念4.2關系的表示法4.3關系的運算4.4關系的性質4.5關系的閉包4.6等價關系和等價類4.7偏序關系4.1關系的概念4.1.4序偶和有序n元組定義4.1.4由兩個元素a和b按一定的順序排列成的二元組叫做一個有序對(也稱序偶)，記作(a，b)，其中a是它的第一元素，b是它的第二元素。一般說來有序偶具有以下特點：1.當a

b時，則(a，b)

(b，a)。2.兩個有序偶相等，即(a，b)=(c，d)的充分必要條件是a=c且b=d。注意：區別(a,b)和{a,b}。例如，當a

b時，有{a,b}={b,a}。有序n元組定義4.1.2

由n個元素a1，a2，…an按一定的順序排列成的一個序列(a1，a2，…an)，稱為有序n元組，其中a1為第一元素，a2為第二元素，…an為第n元素。例如n維空間中點的坐標或n維向量都是有序n元組，(1，2，5)，(?1，?2，3)等是三維空間直角坐標系中點的坐標。

(a1，a2，…，an)=(b1，b2，…，bn)，當且僅當

ai=bi

，i=1，2，…，n。4.1.2集合的直積（笛卡兒積）定義4.1.3

設A，B為集合，取A中的元素作為第一元素，取B中的元素做為第二元素構成有序對，所有這樣的有序對組成的集合，稱為A和B的笛卡兒積(直積)，表示為A

B。于是A

B={(x,y)|x

A

y

B}

例題例4.1.1

A={a,b,c},B={1,3}。求A

B，B

A，A

，

BA

B={(a,1),(a,3),(b,1),(b,3),(c,1),(c,3)}BA={(1,a),(1,b),(1,c),(3,a),(3,b),(3,c)}A=，B=例4.1.2已知A={a,b,c},B={1,3}，C={x}。求(A

B)

C，A

(B

C)。解(A

B)

C={((a,1),x),((a,3),x),((b,1),x),((b,3),x),((c,1),x),((c,3),x)}A

(B

C)={(a,(1,x)),(a,(3,x)),(b,(1,x)),(b,(3,x)),(c,(1,x)),(c,(3,x))}笛卡兒積當A，B為非空集合且A

B時，笛卡爾積運算不滿足交換律，即

A

B

B

AA

B=

，當且僅當A=

或B=

。當A，B，C均為非空集合時，笛卡爾積運算不滿足結合律，即(A

B)

C

A

(B

C)當集合A和B都是有限集時，根據乘法原理，有|A

B|=|A|

|B|。定理定理4.1.1

設A，B，C為任意集合，則A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)(A

B)

C=(A

C)

(B

C)(A

B)

C=(A

C)

(B

C)例題例4.1.3設A,B,C為任意集合，證明A

(B

C)=(A

B)

(A

C)證明

對于任意有序對(x，y)(x，y)

A

(B

C)

x

A

y

(B

C)

x

A

(y

B

y

C)

(x

A

y

B)

(x

A

y

C)

(x，y)

(A

B)

(x，y)

(A

C)

(x，y)

(A

B)

(A

C)

所以有A

(B

C)=(A

B)

(A

C)。n個集合的直積定義4.1.4

設A1，A2，…An為任意n個集合,它們的笛卡爾積(又稱n階直積)為

當A1=A2=…=An=A時，A1

A2

…

An=An。若|A1|=n1，|A2|=n2，…|An|=nn，，則n個集合的笛卡爾積中的元素個數為例題證明：對于任意有序對(x，y)，例題例4.1.5設Ａ，Ｂ，Ｃ，Ｄ是任意集合，判斷下列命題是否為真？(1)(2)(3)解

(1)不一定為真。

(2)為真。

(3)不一定為真。

4.1.3關系的概念定義4.1.5如果一個集合非空且它的元素都是有序對，或集合為空，則稱該集合為一個二元關系，記作R。二元關系也可簡稱為關系。對于二元關系R，如果有序對(a，b)

R，稱a與b有R關系，記作aRb；當(a，b)

R時，稱a與b沒有R關系，記作a

Rb。例如，R={(0,a),(0,b),(1,a),(2,b)}是一個二元關系，其中0Ra,1Ra,0Rb，2Rb，而1Rb，2Ra。R={(1,2)，(1,3)，2，3}不是一個二元關系。

例如：集合A={0，1，2}，B={a,b}，則R1={(0,a),(1,b),(1,a),(2,b)}是從A

到B的一個二元關系；R2={(0,1),(1,2),(0,2)}是A上的一個二元關系。

二元關系定義4.1.6

設A、B為集合，A

B的任意一個子集是集合A到B的一個二元關系。當A=B時稱為A上的二元關系。空關系

AA全域關系EA=AA={（x，y）|xA

y

A}恒等關系IA={（x，x）|x

A}例如，設A={a，b}

A上的全域關系：EA={(a，a)，(a，b)，(b，a)，(b，b)}，A上的恒等關系：IA={(a，a)，(b，b)}

空關系、全域關系、恒等關系二元關系對于集合A、B，如果|A|=n，|B|=m，則|A

B|=nm，A

B的子集有

個,所以集合A到集合B有

個不同的二元關系。如果B=A，則|A

A|=n2，A

A的子集有

個,所以A上有

不同的二元關系。例題設集合A={0，1}，B={a，b}，寫出集合A到集合B的所有二元關系。解

因為A={0，1}，B={a，b}，所以A

B={(0,a),(0,b),(1,a),(1,b)}。A

B的所有不同子集為：0元子集：

；1元子集：{(0,a)},{(0,b)},{(1,a)},{(1,b)}；2元子集：{(0,a),(0,b)},{(0,a),(1,a)},{(0,a),(1,b)},{(0,b),(1,a)},{(0,b),(1,b)},{(1,a),(1,b)};3元子集：{(0,a),(0,b),(1,a)},{(0,a),(0,b),(1,b)},{(0,a),(1,a),(1,b)},{(0,b),(1,a),(1,b)}；4元子集：{(0,a),(0,b),(1,a),(1,b)}。例題已知集合A={0，1，2}，寫出集合A上的整除關系DR和小于或等于關系LA。解

集合A上的整除關系：DR={(1,1),(1,2),(2,2)}。集合A上的小于或等于關系：LA={(0,0),(0,1),(0,2),(1,1),(1,2),(2,2)}。寫出實數集上的小于等于關系和正整數集上的整除關系。解：

實數集R上的小于等于關系為

L={（x，y）|x,yR

x

y}

正整數集Z+上的整除關系為

D={（x，y）|x,yZ+

x|y}

例題定義域(前域)、值域(后域)定義4.1.7

設A、B是兩個集合，R是從A到B的二元關系，R的所有有序對的第一個元素構成的集合稱為R的定義域(或前域)，記為domR；R的所有有序對的第二個元素構成的集合稱為R的值域(或后域)，記為ranR；R的定義域和值域的并集稱為R的域，記為fldR。二元關系R的定義域domR和值域ranR又可表示為：

domR={x|

y(x，y)

R)}

ranR={y|

x(x，y)

R)}

fldR=domR

ranR例題A={甲，乙，丙，丁}，B={a，b，c}。R={(甲，a)，(乙，b)，(丁，c)}是從A到B的二元關系，寫出R的定義域和值域。解

R的定義域domR={甲，乙，丁}，值域ranR={a，b，c}。設Z是整數集合。Z上的關系R={(x，y)|x，y

Z

(y=x2)}。寫出R的定義域和值域。解

R的定義域domR=Z，值域ranR={y|x，y

Z

(y=x2)}。集合A到B的二元關系R的定義域domR

A，值域ranR

B。n元關系定義4.1.8

設A1，A2，…An是n個集合。A1

A2

…

An的任一子集，稱為A1，A2，…An間的一個n元關系。關系的應用數據結構中的線性關系和非線性關系；在關系數據庫中數據按二維表的形式存放，這種二維表就叫關系。表4.1.1二維表

學號

姓名

課程

成績02001張明

物理學

優秀02002李強

數學

良好02008王華

英語

優秀02010李力

數學

良好

4.2關系的表示法4.2.1用集合表示關系由定義4.1.5可知，關系是一個集合，因此可用列出集合的所有元素的列舉法或描述集合元素的特性的描述法表示關系。如：描述法表示關系：R={(a，b，c)|a、b和c是整數且0

a

b

c

5}列舉法表示關系：R={(1，2，3)，(1，2，4)，(1，3，4)，(2，3，4)}

定義4.2.1設集合A={a1，a2，a3，

am}，B={b1，b2，b3，

bn}，R是從A到B上的一個二元關系。把集合A和B

的每個元素表示成一個結點，關系R的每一個有序對表示成一條有向邊，有向邊的方向由有序對的第一元素指向第二元素。這樣得到的圖就是表示關系R的關系圖。4.2.2用關系圖表示關系例題例4.2.3設集合X={x1，x2，x3，x4}，Y={y1，y2，y3}，R是從X到Y上的二元關系，R={(x1，y2)，(x2，y3)，(x3，y3)，(x4，y1)}，畫出R的關系圖。例4.2.3設集合A={1，2，3，4}，R={(1，1)，(1，4)，(2，1)，(2，3)，(2，4)，(3，1)，(4，1)，(4，2)}，R的關系圖。

例題在關系圖中，結點a是有向邊(a，b)的起點，結點b是終點。若aRa，則從a到自身有一條有向邊，稱為環。定義4.2.2

設A={a1，a2，a3，

am}，B={b1，b2，b3，

bn}，R是從A到B上的一個二元關系。關系R可以用一個m行n列的矩陣MR=[mij]來表示，稱MR為關系R的鄰接矩陣，其中4.2.3用矩陣表示關系

例題例4.2.4

設集合A={1，2，3}，B={1，2}。R是A到B上的大于關系，試求出R的關系矩陣。

解

由題意可知，關系R={(a，b)|a

A

b

B

a>b}。R的關系矩陣為例題例4.2.5

已知集合A={a，b，c}上的關系R的關系矩陣寫出關系R的集合表達式。解

因為mij=1對應的(ai，bj)

R。所以R={(a，a)，(a，b)，(b，a)，(b，c)，(c，a)，(ｃ，ｂ)}4.3關系的運算R和S是集合A到B的兩個二元關系，則R

S，R

S，R

S，S

R，

R，

S等也是A到B的二元關系。

例題例4.3.1設整數集合A={3，6，9}，R是A上的整除關系，S是A上的小于關系，試求R

S，R

S，R

S，S

R，

R，

S。解根據題意R={(3，3)，(3，6)，(3，9)，(6，6)，(9，9)}，S={(3，6)，(3，9)，(6，9)}。R

S={(3，3)，(3，6)，(3，9)，(6，6)，(9，9)，(6，9)}；R

S={(3，6)，(3，9)}；R

S={(3，3)，(6，6)，(9，9)}；

S

R={(3，3)，(6，6)，(9，9)，(6，9)}；

R=A

A

R={(6，3)，(6，9)，(9，3)，(9，6)}；

S=A

A

S={(3，3)，(6，3)，(6，6)，(9，3)，(9，6)，(9，9)}。4.3.1關系的逆運算定義4.3.1R是從集合A到B的關系，R的所有有序對的元素順序交換得到的有序對的集合是從B到A的關系，該關系稱為R的逆關系。記為R-1，即R-1={(x，y)|yRx}

例題例4.3.1設關系R={(1,a),(2,c),(3,d),(4,a),(4,b)}。(1)計算R-1，并畫出R和R-1的關系圖。(2)寫出R和R-1的關系矩陣。解(1)R的逆關系R-1={(a,1),(c,2),(d,3),(a,4),(b,4)}。R和R-1的關系圖

例題（續）R和R-1的關系矩陣為

(1)將R的關系圖中有向邊的方向改變成相反方向即得R-1的關系圖，反之亦然。(2)R和R-1的關系矩陣互為轉置矩陣。(3)dom

R-1=ranR

，ran

R-1=domR。(4)|R|=|R-1|逆關系的性質定理4.3.1設R和S是任意關系。則有(1)(R-1)-1=R(2)(R

S)-1=R-1

S-1(3)(R

S)-1=R-1

S-1(4)(~R)-1=~(R-1)(5)(R

S)-1=R-1

S-1(6)若R

S，則R-1

S-1逆關系的性質證明(1)對任意的(x，y)

(R-1)-1

(y，x)

R-1

(x，y)

R

所以(R-1)-1=R(2)對任意的(x，y)

(R

S)-1

(y，x)

R

S

(y，x)

R

(y，x)

S

(x，y)

R-1

(x，y)

S-1

(x，y)

R-1

S-1

所以(R

S)-1=R-1

S-1逆關系的性質證明

(5)(R

S)-1=(R

~S)-1=R-1

(~S)-1=R-1

~S-1=R-1

S-1

所以(R

S)-1=R-1

S-1(6)任取(y，x)

R-1，則(x，y)

R

。若R

S，根據集合包含的定義，則有(x，y)

S，那么(y，x)

S-1，因而有R-1

S-1。任取(x，y)

R，則(y，x)

R-1。若R-1

S-1，根據集合包含的定義，則有(y，x)

S-1，那么(x，y)

S，因而有R

S。所以R

S

R-1

S-1。4.3.2關系的復合運算定義4.3.2設R是集合A到集合B上的一個二元關系，S是集合B到集合C上的一個二元關系，則R和S的復合關系SoR為集合A到集合C上的一個二元關系，定義如下SoR={(x，z)|x

A

z

C

y(y

B

(x，y)

R

(y，z)

S)}。從R和S求SoR的運算，稱為關系的復合運算，又稱關系的合成運算。有些書中可能表示的方法相反，將R和S的復合關系寫成RoS。例題例4.3.3設集合X={x1，x2，x3}，Y={y1，y2，y3，y4}，Z={z1，z2，z3}，集合X到Y上的關系R={(x1，y2)，(x1，y3)，(x2，y1)，(x2，y4)，(x3，y2)}，集合Y到Z上的關系S={(y1，z2)，(y2，z3)，(y3，z1)，(y4，z3)}，求R和S的復合關系SoR。解

SoR={(x1，z3)，(x1，z1)，(x2，z2)，(x2，z3)，(x3，z3)}。例題例4.3.4集合X={0，1，2，3，4}上的關系R={(1，1)，(1，4)，(2，3)，(3，1)，(3，4)}和S={(1，0)，(2，0)，(3，1)，(3，2)，(4，1)}，求復合關系SoR和RoS。解

SoR={(1，0)，(1，1)，(2，1)，(2，2)，(3，0)，(3，1)}RoS={(3，1)，(3，4)，(3，3)，(4，1)，(4，4)}顯然，SoR

RoS，關系的復合運算不滿足交換律。定理4.3.2定理4.3.2設R、S、P是從任意二元關系，則Po(SoR)=(PoS)oR

。證明

對任意(x，w)

Po(SoR)

z((x，z)

(SoR)

(z，w)

P)

z

y((x，y)

R

(y，z)

S

(z，w)

P)

y((x，y)

R

(y，w)

PoS)

(x，w)

(PoS)oR所以

Po(SoR)=(PoS)oR

。定理4.3.3定理4.3.3設R、S、P為任意二元關系，則有(S

P)oR=(SoR)

(PoR)Ro(S

P)=RoS

RoP(S

P)oR

SoR

PoRRo(S

P)

RoS

RoP注意，復合運算對并運算是可分配的，對交運算分配后是包含關系式。定理4.3.3（續）證明：(1)對任意(x，y)

(S

P)oR

z((x，z)

R

(z，y)

(S

P))

z((x，z)

R

((z，y)

S

(z，y)

P))

z(((x，z)

R

(z，y)

S)

((x，z)

R

(z，y)

P)))

z((x，z)

R

(z，y)

S)

z((x，z)

R

(z，y)

P))

(x，y)

S

oR

(x，y)

P

oR

(x，y)

(SoR)

(PoR)所以(S

P)oR=(SoR)

(PoR)。定理4.3.3（續）(3)對任意(x，y)

(S

P)oR

z((x，z)

R

(z，y)

(S

P))

z((x，z)

R

((z，y)

S

(z，y)

P))

z(((x，z)

R

(z，y)

S)

((x，z)

R

(z，y)

P)))

z((x，z)

R

(z，y)

S)

z((x，z)

R

(z，y)

P))

(x，y)

S

oR

(x，y)

P

oR

(x，y)

(SoR)

(PoR)所以(S

P)oR

(SoR)

(PoR)。定理4.3.4定理4.3.4設R和S是任意關系，則有(SoR)-1=R-1oS-1。證明：對任意(x，y)

(SoR)-1

（y，x）

SoR

z（（y，z）

R

（z，x）

S）

z（（z，y）

R-1

（x，z）

S-1）

（x，y）

R-1oS-1

所以(SoR)-1=R-1oS-1。定理4.3.5定理4.3.5設R是A上的關系，則證明

任取(x,y),R的n次冪定義4.3.3設R為A上的關系，n為非負整數，則R的n次冪定義如下：(1)R0={(x，x)|x

A}=IA(2)Rn=Rn-1oR

，n

1這個定義說明R2=RoR，R3=R2oR=(RoR)oR，

等。定理定理4.3.6R為A上的關系，m，n為非負整數，有（1）RmoRn=Rm+n

（2）(Rm)n=Rmn證明

（1）對任意的非負整數m,對n用數學歸納法可以證明。若n=0，則有RmoRn=RmoR0=RmoIA=Rm=Rm+0假設RmoRn=Rm+n，則有RmoRn+1=Rmo(RnoR)=(RmoRn)oR=Rm+noR=Rm+n+1。（2）若n=0，則有(Rm)0=IA=Rm

0假設(Rm)n=Rmn，則有(Rm)n+1=Rmo(Rm)n

=RmoRmn

=Rm+mn=Rm(n+1).例題例4.3.5設A={1,2,3,4}，R={(1,1),(2,1),(3,2),(4,3)}求:Rn，n=2,3,…解

R2=RoR={(1,1),(2,1),(3,1),(4,2)}R3=R2oR={(1,1),(2,1),(3,1),(4,1)}R4=R3oR=R3Rn=R3

for

n=5,6,……

實際上，對于有限集A和A上的關系R，R的不同的冪只有有限個。定理4.3.7定理4.3.7R為A上的關系，|A|=n，則存在自然數數s、t，使（1）Rs=Rt，(T=t?s為周期)。（2）對任何k∈N有Rs+k=Rt+k。證明

（1）由于|A|=n,故|A

A|=n2，A

A的子集有

個，即A上有

個二元關系。R為A上的關系，對任何自然數k，Rk都是A

A的子集，當列出R的各次冪

時，共有

個，根據鴿巢原理，其中至少有兩個是相同的，即有s，t()，使得Rs=Rt。（2）若Rs=Rt，則Rs+k=RsoRk=RtoRk=Rt+k。用矩陣表示兩個關系的復合設R={(1,2),(3,4),(2,2)}S={(4,2),(2,5),(3,1),(1,3)}是A={1,2,3,4,5}上的關系，求SoR。解：集合A有5個元素，用5行5列的矩陣表示關系R和S，矩陣的行和列分別對應A中的元素1,2,3,4,5，則有例題例題（續）

4.4關系的性質自反性反自反性對稱性反對稱性傳遞性自反關系定義4.4.1設R是集合A上的一個關系，如果對A中的每一個元素x，均有(x，x)

R,則稱R是自反關系，即Ｒ是自反的

x(x

A

(x，x)

R)。例如，整數集合上的整除關系，相等關系等都是自反的關系；而整數集合上的大于關系，小于關系等都不是自反的關系。例題例4.4.1集合Ａ＝｛１，２，３，４｝上的關系R={(1，1)，(1，2)，(1，4)，(2，1)，(2，2)，(3，3)，(4，1)，(4，4)}，判斷Ｒ是否自反關系？寫出R的關系矩陣并畫出R的關系圖。解因為Ａ中的每個元素都和自己有關系Ｒ，所以Ｒ是自反的關系。關系R的關系矩陣：

關系R的關系圖：反自反關系定義4.4.2設R是集合A上的一個關系，如果對A中的每一個元素x，均有(x,x)

R,則稱R是反自反關系，即Ｒ是反自反的

x(x

A

(x,x)

R)。例如，整數集合上的大于關系，小于關系等都是反自反的關系；而整數集合上的整除關系，大于等于關系等都不是反自反的關系。例題例4.4.2集合Ａ＝{1，2，3，4}上的關系R={(1，2)，(1，4)，(2，1)，(2，3)，(3，2)，(4，1)，(4，2)}，S={(1，2)，(1，3)，(2，2)，(3，1)，(4，3)}，判斷Ｒ和S是否反自反關系？是否自反關系？解

Ｒ是反自反的關系，不是自反關系。S不是反自反關系，也不是自反關系。關系矩陣：

關系圖：

RS自反性和反自反性如果關系R是自反的，則關系R一定不是反自反的，反之亦然。如果關系R不是自反的，則關系R不一定就是反自反的，反之亦然。也就是存在既不是自反也不是反自反的關系。如果關系R是自反的，當且僅當R的關系圖中每個結點都有環；如果關系R是反自反的，當且僅當R的關系圖中每個結點都沒有環。如果關系R是自反的，當且僅當R的關系矩陣中主對角線上都為1；如果關系R是反自反的，當且僅當R的關系關系矩陣中主對角線上都為0。對稱關系定義4.4.3

設R是A上的一個關系，如果對A中的元素x和y，如有(x，y)

R，必有(y，x)

R，則稱R是對稱關系，即

R是對稱的

x

y(x

A

y

A

(x，y)

R

(y，x)

R)

例如，整數集合上的等于關系，任意集合上的全域關系，同學關系，朋友關系等都是對稱的；而整數集合上的整除關系，大于關系等都不是對稱的。例題例4.4.3集合Ａ＝{1，2，3，4}上的關系R={(1，2)，(1，4)，(2，1)，(2，2)，(2，3)，(3，2)，(4，1)}，判斷Ｒ是否對稱關系？解

Ｒ是對稱的關系。R的關系矩陣

R的關系圖反對稱關系定義4.4.4

設R是A上的一個關系，如果對A中的元素x和y，若(x，y)

R和(y，x)

R，就必有x=y，則稱R是反對稱關系，即

R是反對稱的

x

y(x

A

y

A

(x，y)

R

(y，x)

R

x=y)若關系R是反對稱的，當x≠y時，(x，y)

R，則(y，x)

R。實數集合上的大于等于關系，大于關系，集合的冪集上的包含關系等都是反對稱的。例題例4.4.4集合Ａ＝｛１，２，３，４｝上的關系R={(1，2)，(1，4)，(2，2)，(2，3)，(3，1)，(4，3)}，判斷Ｒ是否反對稱關系？解

Ｒ是反對稱的關系。R的關系矩陣為

R的關系圖

例題集合Ａ＝｛１，２，３，４｝上的關系S={(1，2)，(1，4)，(2，1)，(2，2)，(3，1)，(4，3)}，判斷S是否反對稱關系？是否對稱關系？

解因為在S中，有(1，2)

S，也有(2，1)

S，所以S不是反對稱關系，又因為(1，4)

S

，而(4，1)

S，所以S也不是對稱關系。

對稱性和反對稱性(1)對稱性和反對稱性的概念不是對立的，一個關系可以不具有對稱性的同時也不具有反對稱性，且存在既對稱也反對稱的關系。(2)關系R是對稱的當且僅當在其關系圖上，若兩點之間有邊，則必定是成對出現的方向相反的兩條邊；關系R是反對稱關系當且僅當在其關系圖上，若兩點之間有邊，只有一條邊。(3)對稱關系R的關系矩陣是對稱矩陣，即mij=mji，i,j=1,2，，…，n；反對稱關系R的關系矩陣中，不在主對角線上的關于主對角線對稱的元素不能同時為1，即若mij=1，i,j=1,2，…，n，i≠j，則mji=0。傳遞關系定義4.4.5

設R是A上的一個關系，x、y、z是A中的元素，若(x，y)

R，(y，z)

R，必有(x，z)

R，則稱R是傳遞關系，即

R是傳遞的

x

y

z(x

A

y

A

z

A

(x，y)

R

(y，z)

R

(x，z)

R)例如，實數集上的大于關系、小于關系等是傳遞關系，而同學關系、朋友關系等不一定是傳遞的。例題例4.4.6

判斷集合A=｛１，２，３，４｝上的關系R={(2，1)，(3，1)，(3，2)，(4，1)，(4，2)，(4，3)}是否傳遞關系？解

R是傳遞的。R的關系矩陣

R的關系圖(1)關系R是傳遞關系當且僅當在關系圖中，若存在從結點a到結點b的有向邊和從結點b到結點c的有向邊，則一定有從結點a到結點c的有向邊。(2)關系R是傳遞關系當且僅當在關系矩陣中，若mij=1且mjk=1，則mik=1，i,j,k=1,2，…n。例題例4.4.7

若集合A非空且非單元集，判斷下列關系具有哪些性質？（1）A上的全域關系；（2）A上的恒等關系；（3）A上的空關系。解(1)A上的全域關系是自反的、對稱的和傳遞的;(2)A上的恒等關系是自反的、對稱的、反對稱的和傳遞的;(3)A上的空關系是反自反的、對稱的、反對稱的和傳遞的。

需要注意的是，空集上的空關系還具有自反性，單元集上的全域關系還具有反對稱性。定理4.4.1定理4.4.1

設R是集合A上的關系，則（1）R是自反的當且僅當IA

R；（2）R是反自反的當且僅當R

IA=

；（3）R是對稱的當且僅當R=R-1；（4）R是反對稱的當且僅當R

R-1

IA；（5）R是傳遞的當且僅當R

oR

R。可用于判斷或證明關系的性質定理4.4.1證明R是自反的當且僅當IA

R；必要性：對任意的(x，x)

IA，因為R是自反的，所以(x，x)

R，即IA

R；充分性：對任意x

A，有(x，x)

IA。因為IA

R，所以(x，x)

R。根據自反性的定義知，R是自反的。定理4.4.1證明（續）（2）R是反自反的當且僅當R

IA=

；必要性：用反證法。假設R

IA≠

，則存在(x，y)

R

IA

(x，y)

R

(x，y)

IA

(x，y)

R

(x=y)

(x，x)

R，和R是反自反的矛盾。充分性：任取x

A，則有x

A

(x，x)

IA

(x，x)

R(由于R

IA=

)，所以R是反自反的。定理4.4.1證明（續）（4）R是反對稱的當且僅當R

R-1

IA；必要性：對任意(x，y)

R

R-1，則有(x，y)

R

R-1

(x，y)

R

(x，y)

R-1

(x，y)

R

(y，x)

R

(x，y)

R

x=y(由于R是反對稱的)

(x，y)

IA所以R

R-1

IA。

充分性：對任意(x，y)，則有(x，y)

R

(y，x)

R

(x，y)

R

(x，y)

R-1

(x，y)

R

R-1

(x，y)

IA(因為R

R-1

IA)

x=y從而證明了R是反對稱的。定理4.4.1證明（續）(5)R是傳遞的當且僅當R

oR

R。必要性：對任意(x，z)

RoR，根據關系復合運算的定義，則存在y

A，使得(x，y)

R并且(y，z)

R。由于R是傳遞的，有(x,z)

R。因此R

oR

R。充分性：對任意x,y,z

A，若(x，y)

R并且(y，z)

R，則(x，z)

RoR。因為R

oR

R，所以(x，z)

R，因而R是傳遞的。關系性質的保持定理4.4.2

設R、S是集合A上的二元關系，則：若R、S是自反的，則R-1，R

S，R

S，RoS也是自反的；若R、S是反自反的，則R-1，R

S，R

S，R?S也是反自反的；若R、S是對稱的，則R-1，R

S，R

S，R?S也是對稱的；若R、S是反對稱的，則R-1，R

S，R?S也是反對稱的；若R、S是傳遞的，則R-1，R

S也是傳遞的。例題例4.4.9

設A是集合，R1和R2是A上的關系，若R1和R2是自反的、對稱的和傳遞的，R1

R2也是自反的、對稱的和傳遞的嗎？解

R1

R2是自反的。

R1

R2是A上的對稱關系。R1

R2不一定是傳遞的。例如，假設R1={(1,2)}，R2={(2,3)}是集合A={1,2,3}上的關系，R1和R2是傳遞關系，但R1

R2={(1,2)，(2,3)}不是傳遞的。

設R是非空集合A上的關系，

R可能不具有某種性質，如自反性、對稱性或傳遞性。有時我們需要R具有某種性質，因此，可以通過關系的閉包運算，在R中添加最少的有序對構成新關系R

，使R

具有所需的性質。

關系閉包定義4.5.1設R是非空集合A上的二元關系，如果A上的關系R'滿足

(1)R'是自反的(對稱的或傳遞的)；

(2)R'

R；

(3)對A上的任何包含R的自反(對稱或傳遞)關系R"，都有R"

R'。稱R'是R的自反(對稱或傳遞)閉包。一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。閉包例題例4.5.1集合A={1，2，3}上的關系R={(1，1)，(1，2)，(2，1)，(3，2)}，求R的自反閉包、對稱閉包和傳遞閉包。解

R的自反閉包r(R)={(1，1)，(1，2)，(2，1)，(3，2)，(2，2)，(3，3)}

R的對稱閉包s(R)={(1，1)，(1，2)，(2，1)，(3，2)，(2，3)}

R的傳遞閉包t(R)={(1，1)，(1，2)，(2，1)，(3，2)，(2，2)，(3，1)}。定理4.5.1定理4.5.1設R是非空集合A上的二元關系，有（1）R是自反的，當且僅當r(R)=R，（2）R是對稱的，當且僅當s(R)=R，（3）R是傳遞的，當且僅當t(R)=R。證明(1)顯然有R

r(R)。若R是自反的，由于R包含R，根據自反閉包的定義有r(R)

R。因此r(R)=R。定理4.5.2

設R為非空集合A上的關系，則有

(1)r(R)=R

IA；(2)s(R)=R

R-1；

(3)

閉包的構造方法證明(1)設R'=R

IA。對任意的x

A，(x，x)

R

IA，所以R'=R

IA是自反的，且R

IA

R。設R"是A中包含R的任一自反關系，即R"

R，且R"

IA，所以有R"

R'=R

IA，因此，R

IA是R的自反閉包，即r(R)=R

IA。證明（續）(2)對任意的(x，y)

R

R-1，即(x，y)

R或(x，y)

R-1，有(y，x)

R-1或(y，x)

R，因而(y，x)

R

R-1，所以R

R-1是對稱的，R

R-1

R顯然成立。設R"是A中包含R的任一對稱關系，對任一(x，y)

R-1，必有(y，x)

R，從而有(y，x)

R"。由于R"是對稱關系，因而(x，y)

R"，所以R"

R-1。因此有R"

R

R-1。綜上所述，R的對稱閉包s(R)=R

R-1。（3）先證以下對n進行歸納證明。根據傳遞閉包的定義有R

t(R)。假定n

1時,Rn

t(R)。設(x,y)

Rn+1,因為Rn+1=RoRn,故必有某個z

A,使(x,z)

Rn,(z,y)

R，所以有(x,z)

t(R),(z,y)

t(R),即(x,y)

t(R)。所以Rn+1

t(R).因而有證明（續）證明（續）設:則必存在整數s和t,使得(x,y)

Rs,(y,z)

Rt,從而有(x,z)

RsoRt=Rs+t,即由于包含R的傳遞關系都包含t(R),再證:例題設集合A={a,b,c}，R是A上的二元關系，R={(a,b),(b,c),(c,a)},求r(R)、s(R)，和t(R)。

解

r(R)=R

IA={(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)}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)}=Rt(R)={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}。

例題求整數集Z上的關系R={(a，b)|a

b}的自反閉包、對稱閉包和傳遞閉包。解

R的自反閉包r(R)=R

IZ={(a，b)|a

b}

(a，a)|a

Z}={(a，b)|a

b}R的對稱閉包s(R)=R

R-1

={(a，b)|a

b}

{(b，a)|a

b}={(a，b)|a

b}R的傳遞閉包t(R)=R={(a，b)|a

b}，因為R是傳遞的。定理4.5.3定理4.5.3設R1和R2為非空集合A上的二元關系，且R1

R2則有

(1)r(R1)

r(R2)；

(2)s(R1)

s(R2)；(3)t(R1)

t(R2)。定理4.5.3（續）證明(3)先用數學歸納法證明，對任意正整數n，有

當n=1時，結論顯然成立。假設n=k時，當n=k+1時，有所以

因此對任意正整數n，有

于是，有

定理4.5.5定理4.5.5設R是非空集合A上的二元關系，有若R是自反的，則s(R)和t(R)也是自反的；若R是對稱的，則r(R)和t(R)也是對稱的；若R是傳遞的，則r(R)是傳遞的。定理4.5.5（續）證明：(2)由于R是對稱的,所以R=R-1又因為:IA=IA-1,(RIA)-1=R-1IA-1r(R)-1=(RIA)-1=R-1IA-1=RIA=r(R)所以r(R)是對稱的定理4.5.5（續）證t(R)是對稱的.先證:對任意正整數n,若R是對稱的,則Rn也是對稱的.當n=1時，結論顯然成立。假設n=k時，Rk是對稱的。當n=k+1時，有所以Rk+1是對稱的。因此，對任意正整數n，Rn是對稱的。

對任意x,y

A，所以t(R)是對稱的。定理4.5.6令tsr(R)=t(s(r(R)))，則有下面的定理：定理4.5.6設R是非空集合A上的二元關系，則tsr(R)是R的自反、對稱、傳遞的閉包。通過關系矩陣運算求關系的閉包設關系R、r(R)、s(R)、t(R)的關系矩陣分別為

則其中E是和M同階的單位矩陣，

是MR的轉置矩陣。例題已知集合A={1,2,3}上的關系R={(1,1),(1,3),(2,2),(3,1),(3,2)}，利用關系矩陣求R的r(R)、s(R)、t(R)。

解：r(R)={(1,1),(1,3),(2,2),(3,1),(3,2),(3,3)}s(R)={(1,1),(1,3),(2,2),(3,1),(3,2),(2,3)}例題（續）t(R)={(1,1),(1,2),(1,3),(2,2),(3,1),(3,2),(3,3)}Warshall算法Warshall算法求傳遞閉包比上例的算法計算量少得多。Warshall算法：設R是非空集合A上的二元關系，R的關系矩陣為MR：(1)M0=MR;(2)for

k:=1to

n

do(3)for

i:=1to

n

do(4)for

j:=1to

n

do(5)算法結束時得到的就是R的傳遞閉包的矩陣。

傳遞閉包的應用傳遞閉包在實際場景中有很多應用。在電子郵件網絡中，我們可以定義關系R={(x,y)|x能直接向y發送郵件}，其中x和y都是網絡中的個體，則傳遞閉包t(R)由所有可直接或間接（即經多次轉發）可發送到郵件的個體對(x,y)所組成。在課程設計中，我們可以定義關系R={(x,y)|x是y的直接先導課程}，則傳遞閉包t(R)可表示出課程間的所有先導和后續關系。傳遞閉包的應用例4.5.6設有一字母表V={A,B,C,D,e,d,f}，并給定下面六條規則：A

Af，B

Dde，C

e，A

B，B

De，D

BfR為定義在V上的二元關系，從xi出發用一條規則推出一串字符，使其第一個字符恰為xj，則(xi,xj)

R，說明每個字母連續運用上述規則可能推出的頭字符。解

t(R)={(A,A),(A,B),(A,D),(B,B),(B,D),(C,e),(D,B),(D,D)}由此說明，應用給定的六條規則，從A出發推導的頭字符有A,B,D三種可能，而從B出發推導的頭字符有B,D兩種可能，而從C出發推導的頭字符只有e，而從D出發推導的頭字符有B,D兩種可能。4.6等價關系和等價類定義4.6.1

設R為非空集合A上的關系，若R是自反的、對稱的和傳遞的，則稱R為A上的等價關系。若(x,y)

R，稱x等價于y，記作x~y。例如，集合上的恒等關系和全域關系都是等價關系。例題例4.6.1

在某班同學的集合上，判斷下列關系中哪些是等價關系？R1={(a，b)|a和b選修同一門課}，R2={(a，b)|a和b畢業于同一所中學}，R3={(a，b)|a和b年齡相同}，解

R1不是等價關系。因為這個關系不是傳遞的。R2和R3都是自反的、對稱的和傳遞的，所以都是等價關系。同余關系設x和y為整數，n為正整數。如果x除以n的余數和y除以n的余數相等，則稱x與y模n同余，用x

y(mod

n)表示。R={(x，y)|x

y(mod

n)}，稱R為模n同余關系。例題例4.6.2

若R是整數集Z上的模n同余關系，R={(x，y)|x

y(mod

n)}，證明R是等價關系。證明(1)對

x

Z，有x

x(mod

n)，即xRx。所以R是自反的。(2)假設xRy，即x

y(mod

n)成立，則有x?y=kn，其中k是整數，從而有y?x=?kn，即y

x(mod

n)，因此yRx，R是對稱的。（3）設xRy，yRz，即x

y(mod

n)，y

z(mod

n)，也就是x?y=kn，y?z=ln，即x?z=(k+l)n，于是有x

z(mod

n)，即xRz。所以R是傳遞的。綜上所述，關系R是等價關系。等價類定義4.6.2

設R是非空集合A上的等價關系，x是集合A中的一個元素，所有與x有R關系的元素組成的集合叫做x的等價類，記作[x]R

，則有[x]R={y|y∈A?xRy}。例題A={1,2,…，8},A上的模3同余關系R為A上的等價關系，它的關系圖如圖所示，

A中各元素的等價類：

[1]R=[4]R=[7]R={1，4，7}，[2]R=[5]R=[8]R={2，5，8}，[3]R=[6]R={3，6}。等價類的性質定理4.6.1設R是非空集合A上的等價關系，對任意的x，y∈A，下面的結論成立.

(1)

x

A，[x]R≠

且[x]R

A

；

(2)

x，y

A，若(x，y)

R，則[x]R=[y]R；

(3)

x，y

A，若(x，y)

R，則[x]R

[y]R=

；(4)商集定義4.6.3

設R為非空集合A上的等價關系，以R的所有等價類為元素構成的集合，叫做A在R下的商集，記作A/R，即

A/R={[x]R|x

∈A}。例題例4.6.4

整數集Z上的模n同余關系R={(a，b)|a

b(mod

n)}是等價關系，求Z在R下的商集Z/R。解

整數集Z上的模n同余關系的等價類為[0]R

={

，-3n，-2n，-n，0，n，2n，3n，

}[1]R

={

，-2n+1，-n+1，1，n+1，2n+1，3n+1，

}[2]R

={

，-2n+2，-n+2，2，n+2，2n+2，3n+2，

}…[n-1]R

={

，-2n+n-1，-n+n-1，n-1，n+n-1，2n+n-1，

}={

，-n-1，-1，n-1，2n-1，3n-1，

}所以商集Z/R={[0]R，[1]R，[2]R，

[n-1]R}。覆蓋和劃分定義4.6.4

設A是非空集合，A的一簇子集A1，A2，….Am，滿足以下條件

(1)Ai

(i=1，2，3….)

(2)

(3)Ai

Aj=

(i

j)。若滿足條件(1)(2)，稱{A1，A2，….Am}是A的覆蓋。若滿足條件(1)(2)(3)，稱{A1，A2，….Am}是A的一個劃分，且稱{A1，A2，….Am}中的任一元素為A的一個類或劃分的一個塊。例題例如:S={a,b,c,d}{{a},{b,c},t1wkxuk}劃分(2){{a,b},{c},{a,d}}覆蓋(3){{a},{b},{c},r1n9fea}最大劃分(4){{a,b,c,d}}最小劃分(5){

,{a,b},{c,d}}不是覆蓋不是劃分例題例4.6.6

假設{A1，A2，….Am}是A的一個劃分，R是A上的關系，R={(x，y)|x和y屬于這個劃分的同一子集Ai(i=1，2，….m)}。證明R是等價關系。證明(1)對于每一個x∈A，有(x，x)

R，因此R是自反的。(2)假設(x，y)

R，那么x和y屬于這個劃分的同一子集，則有(y，x)

R。因此，R是對稱的。(3)如果(x，y)

R，(y，z)

R，假設x和y屬于這個劃分的一個子集Ai，y和z屬于這個劃分的一個子集Aj，即y

Ai

Aj。由于劃分的不同子集是不相交的，必有Ai=Aj。所以x和z屬于這個劃分的同一子集，即(x，z)

R。因而R是傳遞的。綜上所述，R是等價關系。

S的劃分{A1，A2，….Am}的每一個劃分塊Ai(i=1，2，….m)中的任兩個元素都有R關系，因而每一個劃分塊都是R的一個等價類。

集合A上的等價關系是對集合A中的元素做劃分，使得同一劃分塊中的元素之間有等價關系。

由一個劃分可以確定唯一的一個等價關系，這個等價關系的等價類就是劃分的劃分塊。

結論：集合A上的等價關系與集合A的劃分是一一對應的。

等價關系和劃分例題

設A的劃分{A1，A2，….Am}，求笛卡爾積Ai

Ai，和這些笛卡爾積的并集:(A1

A1)

(A2

A2)

…

Am

Am，，即為由此劃分確定的等價關系。例4.6.7

設A={a，b，c，d，e}，A上的劃分

={{a，b，c}，{d，e}}，試求由此劃分確定的等價關系R。解

R={a，b，c}

{a，b，c}

{d，e}

{d，e}={(a，a)，(a，b)，(a，c)，(b