《離散數(shù)學(xué)》第4章 二元關(guān)系和函數(shù)

第4章二元關(guān)系和函數(shù)4.1序偶與笛卡兒積4.2關(guān)系及表示4.3關(guān)系的運(yùn)算4.4關(guān)系的性質(zhì)4.5關(guān)系的閉包4.6等價關(guān)系和劃分4.7序關(guān)系4.8函數(shù)的定義和性質(zhì)4.9函數(shù)的復(fù)合和反函數(shù)4.10集合的基數(shù)4.11例題選解習(xí)題四4.1序偶與笛卡兒積定義4.1.1（有序?qū)Γɑ蛐蚺迹?，ordered

pairs）由兩個元素x和y（允許x=y）按一定次序排列組成的二元組<x，y>稱為一個有序?qū)蛐蚺?，記?lt;x，y>，其中x是它的第一元素，y是它的第二元素。注意，第一、二元素未必不同。如平面直角坐標(biāo)系中的任意一點(diǎn)坐標(biāo)（x,y）均是序偶，而全體這種實(shí)數(shù)對的集合{(x,y)|x∈R∧y∈R}就表示整個平面。有序?qū)Α磝,y〉具有以下性質(zhì)：

(1)當(dāng)x≠y

時，〈x,y〉≠〈y,x〉。

(2)〈x,y〉=〈u,v〉的充要條件是x=u

且y=v。

(3)〈x,x〉也是序偶。這些性質(zhì)是二元集{x,y}所不具備的。例如當(dāng)x≠y

時有{x,y}={y,x},原因是有序?qū)χ械脑厥怯行虻?，而集合中的元素是無序的。再例如，{x,x}={x}，原因是集合中的元素是互異的。由性質(zhì)(２)可推出〈x,y〉=〈y,x〉的充要條件是x=y。有序?qū)Φ母拍羁梢赃M(jìn)一步推廣到多元有序組。定義4.1.2（n元有序組）若n∈N且n＞1，x1,x2,…,xn

是n

個元素，則n元組〈x1,x2,…,xn〉定義為：當(dāng)n=2時，二元組是有序?qū)Α磝1,x2〉；

當(dāng)n≠2時，〈x1,x2,…,xn〉=〈〈x1,x2,…，xn-1〉,xn〉

本質(zhì)上，

n元有序組依然是序偶。

n元有序組有如下性質(zhì)：〈x1,x2,…，

xi,

…,xn〉=〈y1,y2,…，

yi，…，yn〉的充要條件是

x1=y1,x2=y2,…,xi=yi,…,xn=yn。

前面提到，一個序偶〈x,y〉的兩個元素可來自不同的集合，若第一元素取自集合A,第二元素取自集合B，則由A、B中的元素，可得若干個序偶，這些序偶構(gòu)成的集合，描繪出集合A與B的一種特征，稱為笛卡兒乘積。其具體定義如下：定義4.1.3設(shè)Α,Β

為集合，用Α中元素為第一元素，Β中元素為第二元素構(gòu)成有序?qū)ΑＫ羞@樣的有序?qū)M成的集合稱為集合Α和Β的笛卡兒積(cartesianproduct)，又稱作直積，記作Α×Β。

Α和Β

的笛卡兒積的符號化表示為

A×B={〈x,y〉|x∈A∧y∈B}定義4.1.4（n階笛卡兒積（cartesianproduct））若n∈N，且n＞1，A1,A2,…,An是n

個集合，它們的n

階笛卡兒積記作A1×A2×…×An,并定義為:A1×A2×…×An={〈x1,x2,…,xn〉|x1∈A1∧x2∈A2,…,xn∈An}

當(dāng)A1=A2=…=An=A時，A1×A2×…×An簡記為A

n。

【例4.1.1】設(shè)A=｛1,2｝，B=｛a,b,c｝，

C=｛｝,R為實(shí)數(shù)集，則（1）

A×B=｛〈1,a〉，〈1,b〉，〈1,c〉，

〈2,a〉，〈2,b〉，〈2,c〉｝

B×A＝｛〈a,1〉，〈b,1〉，〈c,1〉，

〈a,2〉，〈b,2〉，〈c,2〉｝

Φ×A=Φ

(2)A×B×C=(A×B)×C={〈1,a,Φ〉，〈1,b,Φ〉，〈1,c,Φ〉，

〈2,a,Φ〉，〈2,b,Φ〉，〈2,c,Φ〉｝

A×(B×C)=｛〈1,〈a,Φ〉〉，〈1,〈b,Φ〉〉，

〈1,〈c,Φ〉〉，〈2,〈a,Φ〉〉，

〈2,〈b,Φ〉〉，〈2,〈c,Φ〉〉｝(3)A2={〈1,1〉,〈1,2〉,〈2,1〉,〈2,2〉}(4)B2={〈a,a〉,〈a,b〉,〈a,c〉,〈b,a〉,〈b,b〉,〈b,c〉,〈c,a〉,〈c,b〉,〈c,c〉}(5)R

2=｛〈x,y〉|x,y是實(shí)數(shù)｝，R

2為笛卡兒平面。顯然R

3為三維笛卡兒空間。顯然A×B與B×A所含元素的個數(shù)相同（A,B是有限集合），但A×B≠B×A。定理4.1.1

若A，B是有窮集合，則有

|A×B|=|A|·|B|(·為數(shù)乘運(yùn)算)

該定理由排列組合的知識不難證明。定理4.1.2

對任意有限集合A1，A2,…，An，有

|A1×A2×…×An|＝|A1|·…·|An|(·為數(shù)乘運(yùn)算)

這是十分直觀的，可用歸納法證明之。

定理4.1.4(笛卡兒積與運(yùn)算的性質(zhì)1)

對任意的集合A，B

和C，若C≠Φ，

則

(A

B)(A×C

B×C)(C×A

C×B)

該定理中的條件C≠Φ是必須的，否則不能由A×C

B×C或C×A

C×A推出A

B。定理4.1.5(笛卡兒積與運(yùn)算的性質(zhì)2)

對任意的集合A，B，C和D，有

(A×B

C×D)(A

C∧B

D)4.2關(guān)系及表示關(guān)系是客觀世界存在的普遍現(xiàn)象，它描述了事物之間存在的某種聯(lián)系。例如，人類集合中的父子、兄弟、同學(xué)、同鄉(xiāng)等，兩個實(shí)數(shù)間的大于、小于、等于關(guān)系，集合中二直線的平行、垂直等等，集合間的包含，元素與集合的屬于……都是關(guān)系在各個領(lǐng)域中的具體表現(xiàn)。表述兩個個體之間的關(guān)系，稱為二元關(guān)系；表示三個以上個體之間的關(guān)系，稱為多元關(guān)系。我們主要討論二元關(guān)系。我們常用符號R表示關(guān)系，如個體a與b之間存在關(guān)系R，則記作aRb，或〈a,b〉∈R，否則ab

或〈a,b〉∈R。R只是關(guān)系的一種表示符號，至于是什么關(guān)系，需要時需附注。同時關(guān)系并不限于同一類事物之間，也存在于不同物體之間。如旅客住店，張、王、李、趙四人，1，2，3號房間，張住1號，李住1號，王住2號，趙住3號。若分別以a,b，c,d表示四人，R表示住宿關(guān)系，則有R={〈a,1〉,〈c,1〉,〈b,2〉,〈d,3〉}。因此我們看到住宿關(guān)系R是序偶的集合。

定義4.2.1任何序偶的集合，確定了一個二元關(guān)系，并稱該集合為一個二元關(guān)系，記作R

。二元關(guān)系也簡稱關(guān)系。對于二元關(guān)系R，如果〈x,y〉∈R，也可記作xRy。定義并不要求R中的元素〈x,y〉中的x，y取自哪個個體域。因此，R={〈2,a〉，〈u,狗〉，〈錢幣，思想〉}也是一個二元關(guān)系。因?yàn)樗详P(guān)系的定義，但是無意義，顯然對毫無意義的關(guān)系的研究也無甚意義。若規(guī)定關(guān)系R中序偶〈x,y〉的x∈A，y∈B，如上面的住店關(guān)系，這樣的序偶構(gòu)成的關(guān)系R，稱為從A到B的一個二元關(guān)系。由A×B的定義知，從A到B的任何二元關(guān)系，均是A×B的子集，因此有下面的定義。

定義4.2.2R稱為集合A1，A2，…，An-1到An上的n元關(guān)系（n-arrayrelations），如果R是A1×A2×…×An-1×An的一個子集。當(dāng)A1＝A2＝…＝An-1＝An時，也稱R為A上的n元關(guān)系。當(dāng)n=2時，稱R為A1到A2的二元關(guān)系。

n元關(guān)系也可視為A1×A2×…×An-1到An的二元關(guān)系。由于關(guān)系是集合（只是以序偶為元素），因此，所有規(guī)定集合的方式均適用于關(guān)系的確定。

當(dāng)A，B均是有限集合時，因?yàn)閨A×B|=|A|·|B|，而其子集的個數(shù)是冪集P(A×B)的元素個數(shù)，

|P(A×B)|=2

|A|·|B|，所以由A到B共有2

|A|·|B|個不同的二元關(guān)系。下面介紹一些特殊的二元關(guān)系:

Φ

A×B，稱Φ為A到B的空關(guān)系。

A×BA×B，稱A×B

為A到B的全域關(guān)系。

IA=｛〈x,x〉|x∈A｝，稱為A上的恒等關(guān)系。若A是實(shí)數(shù)集合或其子集，R是A上的二元關(guān)系，可定義下面幾種常見的二元關(guān)系：若R={〈x,y〉|x∈A∧y∈B∧x≤y}，則稱R為小于等于關(guān)系，常記為≤。若R={〈x,y〉|x∈A∧y∈B∧x|y}，則稱R為整除關(guān)系，常記為|，其中x|y表示x整除y。另外還有包含、真包含關(guān)系等。定義4.2.3設(shè)R是A到B的二元關(guān)系。（1）用xRy表示〈x,y〉∈R，意為x，y有R關(guān)系（為使可讀性好，我們將分場合使用這兩種表達(dá)方式中的某一種）。xy表示〈x,y〉R。

（2）由〈x,y〉∈R的所有x組成的集合稱為關(guān)系R的定義域（domain）記作DomR，即

DomR=｛x|x∈A∧y(y∈B∧〈x,y〉∈R)｝（3）由〈x,y〉∈R的所有y組成的集合稱為關(guān)系R的值域（range），記作RanR，即

RanR＝{y|y∈B∧x(x∈A∧〈x,y〉∈R)｝（4）R的定義域和值域的并集稱為R的域，記作FldR。形式化表示為：

FldR=DomR∪RanR**一般地，若R是A到B的二元關(guān)系，則有

DomR

A，RanR

B。

【例4.2.1】設(shè)A=｛1，2，3，4，5，6｝，

B＝｛a

，b

，c，d｝，則

R＝｛〈2，a〉，〈2，b〉，〈3，b〉，

〈4，c〉，〈6，c〉｝那么如圖4.2.1所示：

DomR＝｛2，3，4，6｝，RanR=｛a

，b

，c｝

FldR={2，3，4，6，a，b，c}

各箭頭分別表示2Ra，2Rb，3Rb，4Rc，6Rc。圖4.2.1在此引入關(guān)系的表示法。因?yàn)殛P(guān)系是一種特殊的集合，所以關(guān)系仍然能使用集合的表示方法。如集合的列舉法和描述法。除此之外，有限集合的二元關(guān)系亦可用圖形來表示，這就是關(guān)系圖。

定義4.2.4設(shè)集合A={x1,x2,…,xm}到B={y1,y2,…,ym}上的一個二元關(guān)系為R，以集合A、B中的元素為頂點(diǎn)，在圖中用“?！北硎卷旤c(diǎn)。若xiRyj，則可自頂點(diǎn)xi向頂點(diǎn)yj引有向邊〈xi,yj〉，其箭頭指向yj。用這種方法畫出的圖稱為關(guān)系圖（graphofrelation）。

如圖4.2.1就表示了例4.2.1中的關(guān)系R。如關(guān)系R是定義在一個集合A上，即R

A×A，只需要畫出集合A中的每個元素即可。起點(diǎn)和終點(diǎn)重合的有向邊稱為環(huán)（loop）?！纠?.2.2】求集合A=｛1,2,3,4｝上的恒等關(guān)系、空關(guān)系、全關(guān)系和小于關(guān)系的關(guān)系圖。解恒等關(guān)系

IA={〈1,1〉,〈2,2〉,〈3,3〉,〈4,4〉}

空關(guān)系Φ={}

全關(guān)系A(chǔ)×A={〈1,1〉,〈2,2〉,〈3,3〉,〈4,4〉,〈1,2〉,〈2,1〉,〈3,1〉,〈4,1〉,〈1,3〉,〈2,3〉,〈3,2〉,〈4,2〉,〈1,4〉,〈2,4〉,〈3,4〉,〈4,3〉}小于關(guān)系LA={〈1,2〉,〈1,3〉,〈2,3〉,〈1,4〉,〈2,4〉,〈3,4〉}

其關(guān)系圖分別見圖4.2.2、圖4.2.3、圖4.2.4、圖4.2.5。圖4.2.2圖4.2.3圖4.2.4圖4.2.5當(dāng)A中元素的次序標(biāo)定后，對于任何關(guān)系R，R的關(guān)系圖與R的集合表達(dá)式是可以唯一相互確定的。我們也可看出關(guān)系圖直觀清晰，是分析關(guān)系性質(zhì)的方便形式，但是對它不便于進(jìn)行運(yùn)算。關(guān)系還有一種便于運(yùn)算的表示形式，稱為關(guān)系矩陣（matrixofrelation）。定義4.2.5設(shè)R

A×B，A=｛a1,a2,…,am｝,

B=｛b1,b2,…,bn｝，那么R的關(guān)系矩陣MR為一m×n矩陣，它的第i

，

j分量rij只取值0或1，而當(dāng)且僅當(dāng)aiRbj

當(dāng)且僅當(dāng)例如，圖4.2.1所示關(guān)系R的關(guān)系矩陣為例4.2.2中的圖4.2.2、圖4.2.3、圖4.2.4、圖4.2.5所示關(guān)系的關(guān)系矩陣分別是L關(guān)系R的集合表達(dá)式與R的關(guān)系矩陣也可以唯一相互確定，因此R的集合表達(dá)式、關(guān)系圖、關(guān)系矩陣三者均可以唯一相互確定，并且它們各有各的特點(diǎn)，可以根據(jù)不同的需要選用不同的表達(dá)方式。4.3關(guān)系的運(yùn)算

A到B的二元關(guān)系R是A×B的子集，亦即關(guān)系是序偶的集合。故在同一集合上的關(guān)系，可以進(jìn)行集合的所有運(yùn)算。作為集合對關(guān)系作并、交、差、補(bǔ)運(yùn)算是理所當(dāng)然的，但為了運(yùn)算結(jié)果作為關(guān)系的意義更明確，我們也要求運(yùn)算對象應(yīng)有相同的域，從而運(yùn)算結(jié)果是同一域間的關(guān)系。同前所述，這一要求也不是本質(zhì)的。因此，在討論關(guān)系運(yùn)算時，我們有時忽略它們的域。定義4.3.1設(shè)R和S為A到B的二元關(guān)系，其并、交、差、補(bǔ)運(yùn)算定義如下：

R∪S＝｛〈x,y〉|xRy∨xSy｝

R∩S＝｛〈x,y〉|xRy∧xSy｝

R-S＝｛〈x,y〉|xRy∧?xSy｝～R＝A×B-R＝｛〈x,y〉|?xRy｝【例4.3.1】設(shè)A={1,2,3,4}，若R={〈x,y〉|(x-y)/2是整數(shù),x,y∈A}，S={〈x,y〉|(x-y)/3是正整數(shù),x,y∈A}，求R∪S，R∩S，S-R，～R，R

S。解

R={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉,〈3,1〉,〈3,3〉,〈4,2〉,〈4,4〉}

S={〈4,1〉}

R∪S={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉,〈3,1〉,〈3,3〉,〈4,2〉,〈4,4〉,〈4,1〉}

R∩S=Φ

S-R=S={〈4,1〉}

～R=A×A-R={〈1,2〉,〈1,4〉,〈2,1〉,〈2,3〉,〈3,2〉,〈3,4〉,〈4,1〉,〈4,3〉}

R

S=(R∪S)-(R∩S)={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉,〈3,1〉,〈3,3〉,〈4,2〉,〈4,4〉,〈4,1〉}A上的二元關(guān)系共有2個，|A|=n,|A×A|=n2,|P(A×A)|=2n2由定義很顯然，對任意x∈A，y∈B，有

xRyyR-1x

定義4.3.2設(shè)R是A到B的關(guān)系，R的逆關(guān)系或逆（converse）是B到A的關(guān)系，記為R

-1，規(guī)定

R

-1=｛〈y,x〉|x∈A,y∈B,xRy｝M′表示轉(zhuǎn)置矩陣?yán)纾篒A-1=IA，“≤”的逆是“≥”，Φ-1=Φ，（A×B）-1=B×A

【例4.3.3】設(shè)R表示父子關(guān)系，即〈x,y〉∈R說明x是y的父親，R。R就表示祖孫關(guān)系。

定義4.3.3設(shè)R是A到B的二元關(guān)系，S是B到C的二元關(guān)系

，

R。S稱為R與S的復(fù)合，是A到C的關(guān)系，定義為：

R。S=｛<x,z>|x∈A∧z∈C∧

y(y

∈B∧

xRy

∧ySz)｝【例4.3.5】設(shè)A＝｛0,1,2,3,4,5｝，B＝｛2,4,6｝，C＝｛1,3,5｝，R

A×B，S

B×C，且

R＝｛〈1,2〉,〈2,4〉,〈3,4〉,〈5,6〉｝，

S＝｛〈2,l〉,〈2,5〉,〈6,3〉｝

R。S＝｛〈l,l〉,〈1,5〉,〈5,3〉｝A×C

用圖表示R。S，如圖4.3.1所示。圖4.3.1

【例4.3.6】設(shè)集合A＝｛0,1,2,3,4｝，R，S均為A上的二元關(guān)系，且

R＝｛〈x,y〉|x+y＝4｝＝｛〈0,4〉,〈4,0〉,〈1,3〉,〈3,1〉,〈2,2〉｝

S＝｛〈x,y〉|y-x＝1｝＝｛〈0,1〉,〈1,2〉,〈2,3〉,〈3,4〉｝求RοS，SοR，RοR，SοS，(RοS)οR，

Rο

(SοR)。解

RοS＝｛〈4,l〉,〈1,4〉,〈3,2〉,〈2,3〉｝＝｛〈x,z〉|x+z＝5｝

SοR＝｛〈0,3〉,〈1,2〉,〈2,1〉,〈3,0〉｝＝｛〈x,z〉|x+z＝3｝

RοR＝｛〈0,0〉,〈4,4〉,〈1,1〉,〈3,3〉,〈2,2〉｝＝｛〈x,z〉|x-z＝0｝

SοS＝｛〈0,2〉,〈1,3〉,〈2,4〉｝＝｛〈x,z〉|z-x＝2｝

(Rο

S)οR

＝｛〈4,3〉,〈1,0〉,〈3,2〉,〈2,1〉｝

Rο

(SοR)＝｛〈4,3〉,〈1,0〉,〈3,2〉,〈2,1〉｝從上例已可看出，一般地Rο

S≠SοR。但:(Rο

S)οR=Rο

(SοR)復(fù)合運(yùn)算的性質(zhì)由下面兩個定理介紹。定理4.3.2

設(shè)IA

，

IB為集合A，B上的恒等關(guān)系，

R

A×B，那么（1）IAοR=RοIB=R

（2）ΦοR=Rο

Φ=Φ證明（1）為證IAοR

R

，設(shè)

〈x,y〉∈IAοR。

〈x,y〉∈IAοR

u(u∈A∧〈x,u〉∈IA∧〈u,y〉∈R)

u(u∈A∧x=u∧〈u,y〉∈R)

〈x,y〉∈R

所以IAοR

R得證。設(shè)〈x,y〉∈R，〈x,x〉∈IA∧〈x,y〉∈R〈x,y〉∈IAοR

所以R

IAοR得證。（2)顯然Φ

ΦοR，下證ΦοR

Φ。設(shè)〈x,y〉∈ΦοR。

〈x,y〉∈ΦοR

u(u∈A∧〈x,u〉∈Φ∧〈u,y〉∈R)〈x,u〉∈Φ

說明命題的前件為假，整個蘊(yùn)含式為真，所以

ΦοR

Φ。因此ΦοR=Φ。

同理可證RοΦ=Φ。定理4.3.3設(shè)R，S，T均為A上二元關(guān)系，那么（1）Rο(S∪T)=(RοS)∪(RοT)（2）(S∪T)οR=(SοR)∪(TοR)（3）Rο(S∩T)(RοS)∩(RοT)（4）(S∩T)οR(SοR)∩(TοR)（5）Rο(SοT)=(RοS)οT（6）(RοS)

-1=S-1οR-1關(guān)于復(fù)合運(yùn)算的關(guān)系矩陣有下列結(jié)果。

設(shè)A是有限集合，|A|=n。關(guān)系R和S都是A上的關(guān)系，R和S的關(guān)系矩陣MR=［rij］和MS=［sij］都是n×n

的方陣。于是R與S的復(fù)合R

S的關(guān)系矩陣可以用下述的矩陣邏輯乘計(jì)算(類似于矩陣乘法)得到，記作M

=MR·MS＝［tij］n×n，其各分量tij可采用下式求?。?/p>

(i=1,2,…，n;j=1,2,…,n)這里，f(k)=f(1)∨f(2)∨…∨f(n)?！艦檎嬷滴鋈∵\(yùn)算?！こ伺c普通矩陣乘的不同在于，各分量計(jì)算中用代替。例如，例4.3.6中R

S的關(guān)系矩陣為Rn滿足下列性質(zhì)。定理4.3.4設(shè)R為A上二元關(guān)系，m，n為自然數(shù)，那么

(1)Rn+1=RnοR=RοRn=RmοRn-m+1(2)RmοRn＝Rm+n(3)(Rm)

n＝Rmn(4)(R-1)

n=(Rn)

-1定義4.3.4設(shè)R是A上的關(guān)系，n個R的復(fù)合稱為R的n次冪。由于關(guān)系復(fù)合運(yùn)算有結(jié)合律，因此用“冪”表示集合上關(guān)系對自身的復(fù)合是適當(dāng)?shù)?，，?guī)定R0＝IA（R為A上二元關(guān)系）【例4.3.7】設(shè)A={0,1,2,3,4}，R={〈0,0〉,〈0,1〉,〈1,3〉,〈2,4〉,〈3,1〉,〈4,4〉}

解R2={〈0,0〉,〈0,1〉,〈0,3〉,〈1,1〉,〈2,4〉,〈3,3〉,〈4,4〉}R3={〈0,0〉,〈0,1〉,〈0,3〉,〈1,3〉,〈2,4〉,〈3,1〉,〈4,4〉}

R4={〈0,0〉,〈0,1〉,〈0,3〉,〈1,1〉,〈2,4〉,〈3,3〉,〈4,4〉}=R2R、R2、R3、R4的關(guān)系圖如圖4.3.2所示。

R、R2、R3、R4所對應(yīng)的關(guān)系矩陣為P91

R、R2、R3、R4的關(guān)系圖如圖4.3.2所示。R、R2、R3、R4所對應(yīng)的關(guān)系矩陣為圖4.3.2

定理4.3.5設(shè)集合A的基數(shù)為n

，R是A上二元關(guān)系，那么存在自然數(shù)i，j使得

(0≤i＜j≤)

證明我們知道，當(dāng)|A|=n時，A上不同二元關(guān)系共計(jì)

個，令

，因此，在R0，R1，R2，…，

R

K

這K+l個關(guān)系中，至少有兩個是相同的（鴿巢原理），即有i，

j(0≤i＜j≤)，使Ri＝Rj

。定義4.3.5設(shè)R為A到B的二元關(guān)系，A在R下的像R［A］為集合

R［A］={y|(x)(x∈A∧〈x,y〉∈R)}

集合在關(guān)系下的像的性質(zhì)：定理4.3.6R是X到Y(jié)的關(guān)系和集合A、B，AX，BY，則（1）R［A∪B］=R［A］∪R［B］（2）R［∪A

］=∪{R［B］|B∈A}（3）R［A∩B］R［A］∩R［B］（4）R［∩A

］∩{R［B］|B∈A}(A≠Φ)（5）R［A］-R［B］R［A-B］補(bǔ)充：(1)設(shè)定義在A={1,2,3}中的二元關(guān)系：R1={<1,2>,<2,3>,<1,1>}，R2={<2,2>,<2,3>,<1,3>}，試求R1∪R2

，R1∩R2

，R1-R2

，～R1

，R1

R2

，R1οR2

(2)設(shè)關(guān)系R、S的關(guān)系矩陣為：試求R∪S，R∩S，R-S，～R，R

S，RοS的關(guān)系矩陣4.4關(guān)系的性質(zhì)本節(jié)總假定關(guān)系是某一非空集合上的二元關(guān)系，這一假定不失一般性。因?yàn)槿我籄到B的關(guān)系R，即R

A×B,A×B(A∪B)×(A∪B)，所以關(guān)系R總可看成是A∪B上的關(guān)系，它與原關(guān)系R具有完全相同的序偶，對它的討論代替對R的討論無損于問題的本質(zhì)。定義4.4.1設(shè)R是A上的二元關(guān)系，即

R

A×A。（1）稱R是自反的（reflexive），如果對任意x∈A，均有xRx。即R在A上是自反的當(dāng)且僅當(dāng)x(x∈A→xRx)。（2）稱R是反自反的（irreflexive），如果對任意x∈A，xRx均不成立。即R在A上是反自反的當(dāng)且僅當(dāng)x(x∈A→xRx)。（3）稱R是對稱的（symmetric），如果對任意x∈A，y∈A，xRy蘊(yùn)涵yRx。即R在A

上是對稱的當(dāng)且僅當(dāng)x

y(x∈A∧y∈A∧xRy→yRx)。（4）稱R是反對稱的（antisymmetric），如果對任意x∈A

，y∈A，xRy且yRx蘊(yùn)涵

x＝y(tǒng)。即R在A

上是反對稱的當(dāng)且僅當(dāng)

x

y(x∈A∧y∈A∧xRy∧yRx→x=y)。反對稱性的另一種等價的定義為：R在A上是反對稱的當(dāng)且僅當(dāng)

x

y(x∈A∧y∈A∧xRy∧x≠y→〈y,x〉R)。（5）稱R是傳遞的（transitive），如果對任意x∈A，y∈A

，z∈A

，

xRy且yRz蘊(yùn)涵xRz

。即R在A

上是傳遞的當(dāng)且僅當(dāng)

x

y

z(x∈A∧y∈A∧z∈A∧xRy∧yRz→xRz)。

【例4.4.1】設(shè)A=｛a,b,c｝，以下各關(guān)系

Ri（i＝1,2,…,8）均為A上二元關(guān)系。（1）R1＝｛〈a,a〉,〈a,c〉,〈b,b〉,〈c,c〉｝是自反的，而R2＝｛〈a,c〉,〈c,a〉｝不是自反的，是反自反的。存在既不自反也不反自反的二元關(guān)系，例如R3＝｛〈a,a〉｝。顯然A上的Φ關(guān)系是反自反的，不是自反的。值得注意的是，當(dāng)A＝Φ時（這時A上只有一個關(guān)系Φ），A上空關(guān)系既是自反的，又是反自反的，因?yàn)锳＝Φ使兩者定義的前提總為假。（2）R4＝｛〈a,b〉,〈b,a〉｝是對稱的；R5＝｛〈a,c〉,〈c,a〉,〈a,b〉,〈a,a〉｝不是對稱的；R6＝｛〈a,b〉,〈a,c〉｝是反對稱的。其實(shí)R5既不是對稱的，也不是反對稱的。特別有意思的是，存在既對稱又反對稱的二元關(guān)系，例如A上的恒等關(guān)系IA。（3）R7＝｛〈a,b〉,〈b,c〉,〈a,c〉,〈c,c〉｝是傳遞的，但R7-｛〈a,c〉｝便不是傳遞的了。應(yīng)當(dāng)注意，A上的空關(guān)系Φ，R8＝｛〈a,b〉｝等是傳遞的，因?yàn)閭鬟f性定義的前提對它們而言均為假。（4）任何非空集合上的空關(guān)系都是反自反、對稱、反對稱、傳遞的；其上的相等關(guān)系是自反、對稱、反對稱、傳遞的；其上的全關(guān)系是自反、對稱、傳遞的。（5）三角形的相似關(guān)系、全等關(guān)系是自反、對稱、傳遞的。（6）正整數(shù)集合上的整除關(guān)系是自反、反對稱、傳遞的；但整數(shù)集合上的整除關(guān)系只有傳遞性。判斷一個關(guān)系是否具有上述某種的性質(zhì)，除直接用定義，還有下面的充要條件。定理4.4.1設(shè)R為集合A上二元關(guān)系，即

R

A×A，則（1）R是自反的當(dāng)且僅當(dāng)IA

R。（2）R是反自反的當(dāng)且僅當(dāng)IA∩R=Φ。（3）R是對稱的當(dāng)且僅當(dāng)R=R-1

。

（4）R是反對稱的當(dāng)且僅當(dāng)R∩R-1

IA。（5）R是傳遞的當(dāng)且僅當(dāng)RοR

R。證明（1）先證必要性：因?yàn)镽是自反的，設(shè)對任意的

〈x,y〉∈IA

x∈A∧y∈A∧x=y〈x,y〉∈R。再證充分性：任取x∈A，有〈x,x〉∈IA，因?yàn)镮A

R，所以〈x,x〉∈R，因此R是自反的。（2）先證必要性：用反證法。假設(shè)R∩IA≠Φ，必存在〈x,y〉∈R∩IA〈x,y〉∈IA，由于IA是A上的恒等關(guān)系，從而有x=y，所以

〈x,x〉∈R，這與R

在A上是反自反的相矛盾。再證充分性：任取x∈A，則有x∈A〈x,x〉∈IA〈x,x〉R(由于IA∩R=Φ)，從而證明了R在A上是反自反的。（3）先證必要性：設(shè)R對稱，那么對任意x，y∈A，有

〈x,y〉∈R〈y,x〉∈R

（因?yàn)镽在A上對稱）

〈x,y〉∈R-1

故R=R-1

。

再證充分性：任取〈x,y〉∈R，由R=R-1

，有〈x,y〉∈R〈x,y〉∈R-1

〈y,x〉∈R

所以R在A上是對稱的。（4）先證必要性：設(shè)R反對稱，那么對任意x，y∈A，有

〈x,y〉∈R∩R-1〈x,y〉∈R∧〈x,y〉∈R-1

〈x,y〉∈R∧〈y,x〉∈R

x=y

（R反對稱）

〈x,y〉∈IA

因此R∩R

-1

IA。再證充分性：設(shè)R∩R-1

IA。為證R反對稱，又設(shè)〈x,y〉∈R∧〈y,x〉∈R,由R∩R-1

IA，有〈x,y〉∈R∧〈y,x〉∈R〈x,y〉∈R∧〈x,y〉∈R

-1 〈x,y〉∈R∩R

-1〈x,y〉∈IA

因而x=y。所以R在A上是反對稱的，得證。（5）先證必要性：設(shè)R傳遞，那么對任意x，y∈A，有〈x,y〉∈RοR

u(u∈A∧〈x,u〉∈R∧〈u,y〉∈R)

u(u∈A∧〈x,y〉∈R)（R是傳遞的）

〈x,y〉∈R

故RοR

R。再證充分性：設(shè)RοR

R。為證R傳遞，設(shè)有

〈x,y〉∈R,〈y,z〉∈R。

〈x,y〉∈R∧〈y,z〉∈R〈x,z〉∈RοR

〈x,z〉∈R(RοR

R)

所以R在A上是傳遞的，得證。

表4.4.1關(guān)系的基本性質(zhì)與關(guān)系圖、關(guān)系矩陣有怎樣的聯(lián)系呢？表4.4.1詳解之。

【例4.4.2】設(shè)Ri是A={1,2,3}上的二元關(guān)系（如圖4.4.1所示），判斷它們各具有什么性質(zhì)？并說明理由。

解根據(jù)關(guān)系圖的特征，我們可判斷下列各關(guān)系具有的性質(zhì)。

R1具有反自反性、對稱性、反對稱性、傳遞性。因?yàn)槊恳唤Y(jié)點(diǎn)處均無環(huán)，既無雙邊又無單邊，既無雙邊又無三角形。

R2具有自反性、對稱性、反對稱性、傳遞性。因?yàn)槊恳唤Y(jié)點(diǎn)處有一環(huán)，既無雙邊又無單邊，既無雙邊又無三角形。

R3具有自反性、對稱性、傳遞性。因?yàn)槊恳唤Y(jié)點(diǎn)處有一環(huán)，有邊就有雙邊，有雙邊又有雙環(huán)，有三角形就是向量三角形。

R4具有反對稱性、傳遞性。因?yàn)闊o雙邊，無三角形。

R5具有對稱性。因?yàn)闊o單邊。

R6具有反自反性、反對稱性。因?yàn)槊恳唤Y(jié)點(diǎn)處均無環(huán)。

R7具有自反性、傳遞性。因?yàn)槊恳唤Y(jié)點(diǎn)處有一環(huán)，有三角形，且是向量三角形。

R8具有反自反性、反對稱性、傳遞性。因?yàn)槊恳唤Y(jié)點(diǎn)處均無環(huán)，有三角形，且是向量三角形。

R9均不具備。圖4.4.1關(guān)系是序偶的集合，可作交、并、差、逆、復(fù)合運(yùn)算。如果已知某些關(guān)系具有某一性質(zhì)，經(jīng)過關(guān)系運(yùn)算后的結(jié)果是否仍具有這一性質(zhì)，是一個令人關(guān)注的問題。如果是，我們稱該性質(zhì)對這一運(yùn)算封閉?，F(xiàn)在我們來討論五大特性對基本運(yùn)算的封閉性。定理4.4.2設(shè)R1、R2是A上的自反關(guān)系，則R1-1、R1∩R2、R1∪R2、R1οR2也是A上的自反關(guān)系。證明留給讀者。定理4.4.3設(shè)R1、R2是A上的對稱關(guān)系，則R1-1

、R1∩R2、R1∪R2、R1-R2也是A上的對稱關(guān)系。證明僅證對稱性對并運(yùn)算封閉。設(shè)R1，R2對稱要證R1∪R2對稱。任取〈x，y〉∈R1∪R2，那么〈x，y〉∈R1或〈x，y〉∈R2。由R1，R2對稱知〈y，x〉∈R1或〈y，x〉∈R2，因而〈y，x〉∈R1∪R2。R1∪R2對稱性得證。定理4.4.4設(shè)R1、R2是A上的傳遞關(guān)系，則

R1

-1、R1∩R2是A上的傳遞關(guān)系。但R1∪R2不一定是傳遞的。證明(1)證傳遞性對求逆運(yùn)算封閉。設(shè)R1傳遞，要證R1

-1傳遞，設(shè)有〈x，y〉∈R1

-1，〈y，z〉∈R1

-1

，那么〈y，x〉∈R1，〈z，y〉∈R1。由R1具有傳遞性可得〈z，x〉∈R1，即〈x，z〉∈R1

-1。

R1

-1在A上是傳遞的，得證。

(2)證傳遞性對交運(yùn)算封閉。設(shè)R1，R2傳遞，要證R1∩R2傳遞。設(shè)有〈x，y〉∈R1∩R2，〈y，z〉∈R1∩R2，那么〈x，y〉∈R1，〈x，y〉∈R2，〈y，z〉∈R1，〈y，z〉∈R2。由R1，R2具有傳遞性，可得〈x，z〉∈R1，〈x，z〉∈R2，從而〈x，z〉∈R1∩R2。故R1∩R2在A上是傳遞的，得證。

定理4.4.5設(shè)R1、R2是A上的反對稱關(guān)系，則

R1-1、R1∩R2、R1-R2是A上的反對稱關(guān)系。但R1∪R2不一定是反對稱的。證明僅證反對稱性對差運(yùn)算封閉。設(shè)R1，R2反對稱，要證R1-R2反對稱。設(shè)〈x，y〉∈(R1-R2)且〈y，x〉∈(R1-R2)，因而〈x，y〉∈R1，〈y，x〉∈R1，從而由R1的反對稱性得x=y。這就完成了R1-R2反對稱的證明。定理4.4.6設(shè)R1、R2是A上的反自反關(guān)系，則R1-1、R1∩R2、R1∪R2、R1-R2是A上的反自反關(guān)系。證明留給讀者。我們舉例說明反自反性、對稱性、反對稱性、傳遞性對合成運(yùn)算均不封閉。

【例4.4.3】A={a,b,c}，討論在下列各種情況下RοS具有的性質(zhì)。

(1)R={〈a,b〉},S={〈b,a〉}，

R、S是反自反的。

(2)R={〈a,b〉,〈b,a〉}，

S={〈b,c〉,〈c,b〉}，

R、S是對稱的。

(3)R={〈a,b〉,〈b,c〉}，

S={〈b,b〉,〈c,a〉}，

R、S是反對稱的。

(4)R={〈a,b〉,〈b,c〉,〈a,c〉}，

S={〈b,a〉,〈b,c〉,〈c,a〉}，R、S是傳遞的。解（1）RοS={〈a,a〉}，所以RοS不是反自反的。（2）RοS={〈a,c〉}，所以RοS不是對稱的。（3）RοS={〈a,b〉,〈b,a〉}，所以RοS是對稱的。（4）RοS={〈a,a〉,〈a,c〉,〈b,a〉}，因?yàn)椤碽,a〉∈RοS，〈a,c〉∈RοS，但〈b,c〉RοS，所以RοS不是傳遞的。補(bǔ)充(1)設(shè)A={1,2,3,4,6,12}，A中“整除”關(guān)系記為R，問：R是自反的？反自反的？對稱的？反對稱的？傳遞的？(2)設(shè)A={2,3,4,6,12,24,36}，A中“整除”關(guān)系記為R，求R-1及R的關(guān)系矩陣，說明R-1的屬性。(3)設(shè)A={a,b,c,d}，判定下列關(guān)系的性質(zhì)(可以畫關(guān)系圖說明)R1={<a,a>,<b,a>}R2={<a,a>,<b,c>,<d,a>}R3={<c,d>}R4={<a,a>,<b,b>,<c,c>}R5={<a,c>,<b,d>}4.5關(guān)系的閉包閉包運(yùn)算是關(guān)系運(yùn)算中一種比較重要的特殊運(yùn)算，是對原關(guān)系的一種擴(kuò)充。在實(shí)際應(yīng)用中，有時會遇到這樣的問題，給定了的某一關(guān)系并不具有某種性質(zhì)，要使其具有這一性質(zhì)，就需要對原關(guān)系進(jìn)行擴(kuò)充，而所進(jìn)行的擴(kuò)充又是“最小”的。這種關(guān)系的擴(kuò)充就是對原關(guān)系的這一性質(zhì)的閉包運(yùn)算。

【定義4.5.1】設(shè)R是非空集合A上的關(guān)系，如果A上有另一個關(guān)系R′滿足：

（1）R′是自反的（對稱的或傳遞的）；（2）R

R′；（3）對A上任何自反的（對稱的或傳遞的）關(guān)系R″，若R

R″，均有R′R″，則稱R′為R的自反（對稱或傳遞）閉包。一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。它們分別是具有自反性或?qū)ΨQ性或傳遞性的R的“最小”超集合。稱r、s、t為閉包運(yùn)算，它們作用于關(guān)系R后，分別產(chǎn)生包含R的、最小的具有自反性、對稱性、傳遞性的二元關(guān)系。這三個閉包運(yùn)算也可由下述定理來構(gòu)造。定理4.5.1設(shè)R是集合A上的二元關(guān)系，那么（1）r(R)=IA∪R

（2）s(R)=R∪R-1

（3）證明（1）IA∪R自反且R

IA∪R是顯然的。為證IA∪R為自反閉包，還需證它的“最小性”。為此，令R′自反，且R

R′，欲證IA∪R

R′。由于R′自反，據(jù)定理4.4.1，IA

R′，連同R

R′，即得IA∪R

R′。（2）本式證明留給讀者。（3）是顯然的。

【例4.5.1】設(shè)A＝{1,2,3}，R1={〈1,2〉,〈2,1〉,〈1,3〉,〈1,1〉}，R2={〈1,2〉,〈2,1〉}，

R3={〈1,2〉}，求它們的閉包。解r(R1)=IA∪R

={〈1,1〉,〈2,2〉,〈3,3〉,〈1,2〉,〈2,1〉,〈1,3〉}

s(R1)=R∪R-1={〈1,2〉,〈2,1〉,〈1,3〉,〈3,1〉,〈1,1〉}t(R1)={〈1,2〉,〈2,1〉,〈1,1〉,〈2,2〉,〈1,3〉,〈2,3〉}

r(R2)=IA∪R

={〈1,1〉,〈2,2〉,〈3,3〉,〈1,2〉,〈2,1〉}

s(R2)=R∪R-1={〈1,2〉,〈2,1〉}=R2

t(R2)={〈1,2〉,〈2,1〉,〈1,1〉,〈2,2〉}

r(R3)=IA∪R={〈1,2〉,〈1,1〉,〈2,2〉,〈3,3〉}

s(R3)=R∪R-1={〈1,2〉,〈2,1〉}

t(R3)={〈1,2〉}=R3

【例4.5.2】設(shè)R是集合A={a,b,c,d}上的二元關(guān)系R={〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉}。求R的閉包：r（R）、s（R）、t（R），并畫出對應(yīng)的關(guān)系圖。解r(R)={〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉,〈a,a〉,〈b,b〉,〈c,c〉,〈d,d〉}

s(R)={〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉,〈c,b〉,〈d,c〉}

t(R)={〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉,〈a,a〉,〈a,c〉,〈b,b〉,〈b,d〉,〈a,d〉}其對應(yīng)的關(guān)系圖分別如圖4.5.1(a)、(b)、(c)所示。圖4.5.1從以上討論可以看出，傳遞閉包的求取是很復(fù)雜的。但是，當(dāng)集合A為有限集時，A上二元關(guān)系的傳遞閉包的求取便可大大簡化。推論A為非空有限集合，|A|=n。R是A上的關(guān)系，則存在正整數(shù)k≤n，使得

t(R)=R+=R∪R2∪…∪R

k補(bǔ)充：設(shè)A={1,2,3,4,5}，A中關(guān)系R={<1,2>,<2,3>,<4,5>,<5,2>}，求t(R)解：R2={<1,3>,<4,2>,<5,3>}R3={<4,3>}R4=Φt(R)=R∪R2∪R3∪R4

={<1,2>,<2,3>,<4,5>,<5,2>,<1,3>,<4,2>,<5,3>,<4,3>}下列算法是求取R+的有效算法。

Warshall(沃夏爾)算法：設(shè)R為有限集A上的二元關(guān)系，|A|=n，M為R的關(guān)系矩陣，可如下求取R+的關(guān)系矩陣

W。（1）置

W為M。（2）置i=1。(指的是i列)

（3）對所有j，1≤j≤n，做①

如果W［j,i］=1，則對每一k=1,2,…,n，置W［j,k］為W［j,k］∨W［i,k］，即當(dāng)?shù)趈行、第i列為1時，對第j行每個分量重新置值，取其當(dāng)前值與第i行的同列分量之析取。②

否則對下一j值進(jìn)行①。（4）置i為i+1。（5）若i≤n，回到步驟（3），否則停止?！纠?.5.3】設(shè)A={1,2,3,4},R={〈1,1〉,〈1,2〉,〈2,3〉,〈3,4〉,〈4,2〉},則

R2={〈1,1〉,〈1,2〉,〈1,3〉,〈2,4〉,〈3,2〉,〈4,3〉}

R3={〈1,1〉,〈1,2〉,〈1,3〉,〈1,4〉,〈2,2〉,〈3,3〉,〈4,4〉}

R4={〈1,1〉,〈1,2〉,〈1,3〉,〈1,4〉,〈2,3〉,〈3,4〉,〈4,2〉}因此R

+=R∪R2∪R3∪R

4={〈1,1〉,〈1,2〉,〈1,3〉,〈1,4〉,〈2,2〉,〈2,3〉,〈2,4〉,〈3,2〉,〈3,3〉,〈3,4〉,〈4,2〉,〈4,3〉,〈4,4〉}

現(xiàn)用Warshall算法求取R+。顯然，以下使用Warshall算法求取

W。（1）

W以M為初值。（2）當(dāng)i＝1時，由于

W中只有W［1，1］＝l，故需將第一行各元素與其本身作邏輯和，并把結(jié)果送第一行。即重新置值為

W［1,k］∨

W［1,k］=W［1,k］，但

W事實(shí)上無改變。（3）當(dāng)i=2時，由于

W［1，2］＝

W［4，2］＝1，故需將第一行和第四行各分量重新置值為

W［1,k］∨

W［2,k］和

W［4,k］∨

W［2,k］。于是有：（4）當(dāng)i=3時，由于

W［1，3］＝W［2，3］＝W［4，3］=1，故需將第一、二、四行各分量重新置值，分別為

W［1，k］∨

W［3,k］＝W［1，k］,W［2，k］∨

W［3，k］=W［2，k］，W［4，k］∨

W［3，k］=W［3，k］。于是有：（5）當(dāng)i＝4時，由于

W［1，4］＝

W［2,4］=W［3,4］=W［4，4］=1，故需將第一、二、三、四行各分量重新置值，分別為

W［1，k］∨

W［4,k］＝

W［1，k］，W［2，k］∨

W［4，k］=W［2，k］，W［3，k］∨

W［4，k］=W［3，k］，

W［4，k］∨

W［4，k］=W［4，k］。最終

W

為故R+＝{〈1,1〉,〈1,2〉,〈1,3〉,〈1,4〉,〈2,2〉,〈2,3〉,〈2,4〉,〈3,2〉,〈3,3〉,〈3,4〉,〈4,2〉,〈4,3〉,〈4,4〉}。下面幾個定理給出了閉包的主要性質(zhì)。定理4.5.2設(shè)R是集合A上任一關(guān)系，那么（1）R自反當(dāng)且僅當(dāng)R=r(R)。（2）R對稱當(dāng)且僅當(dāng)R=s(R)。（3）R傳遞當(dāng)且僅當(dāng)R=t(R)。證明（1）、（3）的證明留給讀者，現(xiàn)證（2）。（2）的充分性由s(R)定義立得。為證必要性，設(shè)R對稱,那么R＝R-1（據(jù)定理4.4.1）。另一方面，s(R)=R∪R-1=R∪R=R，故s(R)=R。