第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等價(jià)關(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ū)?或序偶)，orderedpairs)由兩個(gè)元素x和y（允許x=y）按一定次序排列組成的二元組｛｛x｝，｛x,y｝｝稱為一個(gè)有序?qū)蛐蚺迹涀鳌磝,y〉，其中x是它的第一元素，y是它的第二元素。注意，第一、二元素未必不同。如平面直角坐標(biāo)系中的任意一點(diǎn)坐標(biāo)（x,y）均是序偶，而全體這種實(shí)數(shù)對(duì)的集合{(x,y）|x∈R∧y∈R}就表示整個(gè)平面。有序?qū)Α磝,y〉具有以下性質(zhì)：(1)當(dāng)x≠y

時(shí)，〈x,y〉≠〈y,x〉。(2)〈x,y〉=〈u,v〉的充要條件是x=u

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

時(shí)有{x,y}={y,x},原因是有序?qū)χ械脑厥怯行虻模现械脑厥菬o序的。再例如，｛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

個(gè)元素，則n元組〈x1,x2,…,

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

當(dāng)n≠2時(shí)，〈x1,x2,…,

xn〉=〈〈x1,x2,…，x

n-1〉,

xn〉

本質(zhì)上,n元有序組依然是序偶。

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

xi,…,

xn〉=〈y1,y2,…，

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

x1=y1,x2=y2,…,

xi=yi,…,

xn=yn。

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

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

的笛卡兒積的符號(hào)化表示為

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

個(gè)集合，它們的n

階笛卡兒積記作A1×A2×…×An,并定義為:

A1×A2×…×An={〈x1,x2,…,

xn〉|x1∈A1∧x2∈A2,…,

xn∈An}

當(dāng)A1=A2=…=An=A時(shí)，A1×A2×…×An簡記為An?！纠?.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所含元素的個(gè)數(shù)相同（A,B是有限集合），但A×B≠B×A。

定理4.1.1若A,B是有窮集合，則有|A×B|=|A|·|B|(·為數(shù)乘運(yùn)算)該定理由排列組合的知識(shí)不難證明。定理4.1.2對(duì)任意有限集合A1，A2,…，An，有|A1×A2×…×An|＝|A1|·…·|An|(·為數(shù)乘運(yùn)算)

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

定理4.1.3(笛卡兒積與∪，∩，～運(yùn)算的性質(zhì))對(duì)任意的集合A,B

和C，有（1）A×(B∪C)=(A×B)∪(A×C)（2）A×(B∩C)=(A×B)∩(A×C)（3）(B∪C)×A=(B×A)∪(C×A)（4）(B∩C)×A=(B×A)∩(C×A)（5）A×(B-C)＝(A×B)-(A×C)（6）(B-C)×A＝(B×A)-(C×A)證明我們僅證明（1）和（5），其余完全類似。（1）對(duì)任意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)為證（5）式，設(shè)〈x,y〉為A×(B-C)中任一序偶，那么x∈A,y∈B，y

C，從而〈x,y〉∈A×B，〈x,y〉A(chǔ)×C，即〈x,y〉∈A×B-A×C,A×(B-C)(A×B)-(A×C)得證。另一方面，設(shè)〈x,y〉為(A×B)-(A×C)中任一序偶，那么〈x,y〉∈A×B，〈x,y〉A(chǔ)×C，從而x∈A，y∈B,y

C（否則由于x∈A，〈x,y〉∈A×C），故可知y∈B-C，〈x,y〉∈A×(B-C)，于是(A×B)-(A×C)A×(B-C)得證。這就完成了A×(B-C)＝(A×B)-(A×C)的證明。定理4.1.4(笛卡兒積與運(yùn)算的性質(zhì)1)對(duì)任意的集合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)對(duì)任意的集合A,B,C和D，有(A×B

C×D)(A

C∧B

D)

這兩個(gè)定理留給讀者自己完成證明。定理4.16對(duì)任意非空集合A，B，有(A×B)P(P(A∪B))

證明設(shè)〈x,y〉為A×B中任一序偶，即x∈A，y∈B?，F(xiàn)需證〈x,y〉=｛｛x｝,｛x,y｝｝∈P(P(A∪B))

由于x∈A,故｛x｝∈P(A∪B)；又由于x∈A，y∈B，故｛x,y｝∈P(A∪B)。因此，有

｛｛x｝,｛x,y｝｝P(A∪B)

即｛｛x｝,｛x,y｝｝∈P(P(A∪B))。

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

或〈a,b〉R。R只是關(guān)系的一種表示符號(hào)，至于是什么關(guān)系，需要時(shí)需附注。同時(shí)關(guān)系并不限于同一類事物之間，也存在于不同物體之間。如旅客住店，張、王、李、趙四人，1，2，3號(hào)房間，張住1號(hào)，李住1號(hào)，王住2號(hào)，趙住3號(hào)。若分別以a,b，c,d表示四人，R表示住宿關(guān)系，則有R={〈a,1〉,〈c,1〉,〈b,2〉,〈d,3〉}。因此我們看到住宿關(guān)系R是序偶的集合。定義4.2.1任何序偶的集合，確定了一個(gè)二元關(guān)系，并稱該集合為一個(gè)二元關(guān)系，記作R。二元關(guān)系也簡稱關(guān)系。對(duì)于二元關(guān)系R，如果〈x,y〉∈R，也可記作xRy。

定義并不要求R中的元素〈x,y〉中的x,y取自哪個(gè)個(gè)體域。因此，R={〈2,a〉，〈u,狗〉，〈錢幣，思想〉}也是一個(gè)二元關(guān)系。因?yàn)樗详P(guān)系的定義，但是無意義，顯然對(duì)毫無意義的關(guān)系的研究也無甚意義。若規(guī)定關(guān)系R中序偶〈x,y〉的x∈A,y∈B，如上面的住店關(guān)系，這樣的序偶構(gòu)成的關(guān)系R，稱為從A到B的一個(gè)二元關(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的一個(gè)子集。當(dāng)A1＝A2＝…＝An-1＝An時(shí)，也稱R為A上的n元關(guān)系。當(dāng)n=2時(shí)，稱R為A1到A2的二元關(guān)系。n元關(guān)系也可視為A1×A2×…×An-1

到An的二元關(guān)系。由于關(guān)系是集合（只是以序偶為元素），因此，所有規(guī)定集合的方式均適用于關(guān)系的確定。當(dāng)A,B均是有限集合時(shí)，因?yàn)閨A×B|=|A|·|B|,而其子集的個(gè)數(shù)恰是冪集P(A×B)的元素個(gè)數(shù),|P(A×B)|=2

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

|A|·|B|

個(gè)不同的二元關(guān)系。下面介紹一些特殊的二元關(guān)系。設(shè)R是A到B的二元關(guān)系：

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

A×B

A×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。若A是任意集合，R是A上的二元關(guān)系，下面的關(guān)系也常見：若R={〈x,y〉|x∈P(A)∧y∈P(B)∧x

y}，則稱R為包含關(guān)系，常記為。若R={〈x,y〉|x∈P(A)∧y∈P(B)∧x

y}，則稱R為真包含關(guān)系，常記為。定義4.2.3設(shè)R是A到B的二元關(guān)系。（1）用xRy表示〈x,y〉∈R，意為x，y有R關(guān)系（為使可讀性好，我們將分場(chǎng)合使用這兩種表達(dá)方式中的某一種）。xy表示〈x,y〉R。

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

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

R，即

Ran

R＝{y|y∈B∧x(x∈A∧〈x,y〉∈R)｝（4）R的定義域和值域的并集稱為R的域，記作Fld

R。形式化表示為：

Fld

R=DomR∪Ran

R

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

A,Ran

R

B?！纠?.2.1】設(shè)A=｛1，2，3，4，5，6｝，

B＝｛a,b，c,d｝，則

R＝｛〈2,a〉，〈2,b〉，〈3,b〉，〈4c〉，

〈6,c〉｝

那么如圖4.2.1所示：

DomR＝｛2，3，4，6｝，Ran

R=｛a,b,c｝

Fld

R={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}上的一個(gè)二元關(guān)系為R,以集合A、B中的元素為頂點(diǎn)，在圖中用“."表示頂點(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是定義在一個(gè)集合A

上，即R

A×A，只需要畫出集合A中的每個(gè)元素即可。起點(diǎn)和終點(diǎn)重合的有向邊稱為環(huán)（loop）。【例4.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)定后，對(duì)于任何關(guān)系R，R的關(guān)系圖與R的集合表達(dá)式是可以唯一相互確定的。我們也可看出關(guān)系圖直觀清晰，是分析關(guān)系性質(zhì)的方便形式，但是對(duì)它不便于進(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)系矩陣分別是關(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)算。作為集合對(duì)關(guān)系作并、交、差、補(bǔ)運(yùn)算是理所當(dāng)然的，但為了運(yùn)算結(jié)果作為關(guān)系的意義更明確，我們也要求運(yùn)算對(duì)象應(yīng)有相同的域，從而運(yùn)算結(jié)果是同一域間的關(guān)系。同前所述，這一要求也不是本質(zhì)的。因此，在討論關(guān)系運(yùn)算時(shí)，我們有時(shí)忽略它們的域。定義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∧?xS

y｝～R＝A×B-R＝｛〈x,y〉|?xR

y｝【例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)=R∪S

={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉,〈3,1〉,〈3,3〉,〈4,2〉,〈4,4〉,〈4,1〉}關(guān)系并、交、差、補(bǔ)的矩陣可用如下方法求?。?/p>

MR∪S=MR∨MS（矩陣對(duì)應(yīng)分量作邏輯析取運(yùn)算）

MR∩S=MR∧MS（矩陣對(duì)應(yīng)分量作邏輯合取運(yùn)算）

MR-S=MR∩～S=MR∧M～S

M～S=～(MS)（矩陣各分量作邏輯非運(yùn)算）定義4.3.2設(shè)R是A到B的關(guān)系，R的逆關(guān)系或逆（converse）是B到A的關(guān)系，記為R-1，規(guī)定為

R-1=｛〈y,x〉|xRy｝

由定義很顯然，對(duì)任意x∈A,y∈B，有

xRyyR-1

x

若

MR為R的關(guān)系矩陣，那么

（M′表示矩陣M的轉(zhuǎn)置矩陣）【例4.3.3】設(shè)R表示父子關(guān)系，即〈x,y〉∈R說明x是y的父親，R

R就表示祖孫關(guān)系。

【例4.3.4】設(shè)R表示朋友關(guān)系，S表示直接后門關(guān)系，R

S就表示間接后門關(guān)系。【例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。

解

R.S＝｛〈l，l〉，〈1，5〉，〈5，3〉｝A×C

用圖表示R

S，如圖4.3.1所示。圖4.3.1【例4.3.6】設(shè)集合A＝｛1，2，3，4，5｝，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〉｝

求Sο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〉，〈3，2〉，〈2，1〉,〈1,0〉｝

從上例已可看出，一般地RοS≠SοR。

復(fù)合運(yùn)算的性質(zhì)由下面兩個(gè)定理介紹。定理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?！磝,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得證。（2)顯然Φ

ΦοR，下證ΦοR

Φ。

設(shè)〈x,y〉∈ΦοR?！磝,y〉∈ΦοR

u(u∈A∧〈x,u〉∈

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

說明命題的前件為假，整個(gè)蘊(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證明我們僅證明（1）、（4）、（5），另外三式的證明留給讀者完成。（1）對(duì)任意x,y∈A〈x,y〉∈Rο(S∪T)

u(〈x,u〉∈R∧〈u,y〉∈S∪T)

u(〈x,u〉∈R∧(〈u,y〉∈S∨〈u,y〉∈T))

u((〈x,u〉∈R∧〈u,y〉∈S)∨(〈x,u〉∈R∧〈u,y〉∈T))

u(〈x,u〉∈R∧〈u,y〉∈S)∨u(〈x,u〉∈R∧〈u,y〉∈T)

〈x,y〉∈RοS∨〈x,y〉∈RοT

〈x,y〉∈RοS∪RοT故Rο(S∪T)=(RοS)∪(RοT)。（４）對(duì)任意x,y∈A〈x,y〉∈(S∩T)οR

u(〈x,u〉∈(S∩T)∧〈u,y〉∈R)

u(〈x,u〉∈S∧〈x,u〉∈T∧〈u,y〉∈R)

u(〈x,u〉∈S∧〈u,y〉∈R∧〈x,u〉∈T∧〈u,y〉∈R)

u(〈x,u〉∈S∧〈u,y〉∈R)∧u∈〈x,u〉∈T∧〈u,y〉∈R)

〈x,y〉∈(SοR)∧〈x,y〉∈(TοR)

〈x,y〉∈(SοR)∩(TοR)

故(S∩T)οR(SοR)∩(TοR)。定義4.3.4設(shè)R是A上的關(guān)系，n個(gè)R的復(fù)合稱為R的n次冪。由于關(guān)系復(fù)合運(yùn)算有結(jié)合律，因此用“冪”表示集合上關(guān)系對(duì)自身的復(fù)合是適當(dāng)?shù)模?/p>

Rn=Rο…οR

，規(guī)定R0＝IA（R為A上二元關(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＝R

mn

(4)(R-1)

n=(Rn)

-1

【例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所對(duì)應(yīng)的關(guān)系矩陣為圖4.3.2定理4.3.5設(shè)集合A的基數(shù)為n,R是A上二元關(guān)系，那么存在自然數(shù)i,j使得證明我們知道，當(dāng)|A|=n時(shí)，A上不同二元關(guān)系共計(jì)

個(gè),令，因此，在R0，R1，R2，…，

R

K

這K+l個(gè)關(guān)系中，至少有兩個(gè)是相同的（鴿巢原理），即有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，則（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］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具有完全相同的序偶，對(duì)它的討論代替對(duì)R的討論無損于問題的本質(zhì)。定義4.4.1設(shè)R是A上的二元關(guān)系,即R

A×A。（1）稱R是自反的（reflexive），如果對(duì)任意x∈A，均有xRx。即R在A上是自反的當(dāng)且僅當(dāng)x(x∈A→xRx)。（2）稱R是反自反的（irreflexive）,如果對(duì)任意x∈A，

xRx均不成立。即R在A

上是反自反的當(dāng)且僅當(dāng)x(x∈A→--------

xRx)。（3）稱R是對(duì)稱的（Symmetric），如果對(duì)任意x∈A,y∈A，

xRy蘊(yùn)涵yRx。即R在A

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

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

xRy且yRx蘊(yùn)涵

x＝y(tǒng)。

即R在A

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

x

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

x

y(x∈A∧y∈A∧xRy∧x≠y→〈y,x〉R)。（5）稱R是傳遞的（transitive），如果對(duì)任意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＝Φ時(shí)（這時(shí)A上只有一個(gè)關(guān)系Φ），A上空關(guān)系既是自反的，又是反自反的，因?yàn)锳＝Φ使兩者定義的前提總為假。（2）R4＝｛〈a，b〉，〈b，a〉｝是對(duì)稱的；R5＝｛〈a，c〉，〈c，a〉，〈a，b〉，〈a，a〉｝不是對(duì)稱的；R6＝｛〈a，b〉，〈a，c〉｝是反對(duì)稱的。其實(shí)R5既不是對(duì)稱的，也不是反對(duì)稱的。特別有意思的是，存在既對(duì)稱又反對(duì)稱的二元關(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性定義的前提對(duì)它們而言均為假。（4）任何非空集合上的空關(guān)系都是反自反、對(duì)稱、反對(duì)稱、傳遞的；其上的相等關(guān)系是自反、對(duì)稱、反對(duì)稱、傳遞的；其上的全關(guān)系是自反、對(duì)稱、傳遞的。(5)三角形的相似關(guān)系、全等關(guān)系是自反、對(duì)稱、傳遞的。（6）正整數(shù)集合上的整除關(guān)系是自反、反對(duì)稱、傳遞的；但整數(shù)集合上的整除關(guān)系只有傳遞性。判斷一個(gè)關(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是對(duì)稱的當(dāng)且僅當(dāng)R=R-1。（4）R是反對(duì)稱的當(dāng)且僅當(dāng)R∩R-1

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

R。證明（1）先證必要性：因?yàn)镽是自反的，設(shè)對(duì)任意的〈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對(duì)稱，那么對(duì)任意x,y∈A，有〈x,y〉∈R〈y,x〉∈R（因?yàn)镽在A上對(duì)稱）〈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上是對(duì)稱的。（4）先證必要性：設(shè)R反對(duì)稱，那么對(duì)任意x,y∈A，有〈x,y〉∈R∩R-1〈x,y〉∈R∧〈x,y〉∈R-1

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

x=y（R反對(duì)稱）〈x,y〉∈IA

因此R∩R

-1

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

IA。為證R反對(duì)稱，又設(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上是反對(duì)稱的，得證。（5）先證必要性：設(shè)R傳遞，那么對(duì)任意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上是傳遞的，得證。關(guān)系的基本性質(zhì)與關(guān)系圖、關(guān)系矩陣有怎樣的聯(lián)系呢？表4.4.1詳解之。表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具有反自反性、對(duì)稱性、反對(duì)稱性、傳遞性。因?yàn)槊恳唤Y(jié)點(diǎn)處均無環(huán)，既無雙邊又無單邊，既無雙邊又無三角形。

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

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

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

R5具有對(duì)稱性。因?yàn)闊o單邊。R6具有反自反性、反對(duì)稱性。因?yàn)槊恳唤Y(jié)點(diǎn)處均無環(huán)。R7具有自反性、對(duì)稱性、反對(duì)稱性、傳遞性。因?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ì)，是一個(gè)令人關(guān)注的問題。如果是，我們稱該性質(zhì)對(duì)這一運(yùn)算封閉。現(xiàn)在我們來討論五大特性對(duì)基本運(yùn)算的封閉性。定理4.4.2設(shè)R1、R2是A上的自反關(guān)系，則R-11、R1∩R2、R1∪R2、R1οR2也是A上的自反關(guān)系。證明留給讀者。定理4.4.3設(shè)R1、R2是A上的對(duì)稱關(guān)系，則R-11、R1∩R2、R1∪R2、R1-R2也是A上的對(duì)稱關(guān)系。證明僅證對(duì)稱性對(duì)并運(yùn)算封閉。設(shè)R1，R2對(duì)稱，要證R1∪R2對(duì)稱。任取〈x，y〉∈R1∪R2,那么〈x，y〉∈R1或〈x，y〉∈R2。由R1，R2對(duì)稱知〈y，x〉∈R1或〈y，x〉∈R2,因而〈y，x〉∈R1∪R2。R1∪R2對(duì)稱性得證。定理4.4.4設(shè)R1、R2是A上的傳遞關(guān)系，則

R-11、R1∩R2是A上的傳遞關(guān)系。但R1∪R2不一定是傳遞的。證明(1)證傳遞性對(duì)求逆運(yùn)算封閉。設(shè)R1傳遞，要證R-11傳遞，設(shè)有〈x,y〉∈R-11,〈y,z〉∈R-11，那么〈y,x〉∈R1,〈z,y〉∈R1。由R1具有傳遞性可得〈z,x〉∈R1,即〈x,z〉∈R-11。

R-11在A上是傳遞的，得證。(2)證傳遞性對(duì)交運(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上的反對(duì)稱關(guān)系，則

R-11、R1∩R2、R1-R2是A上的反對(duì)稱關(guān)系。但R1∪R2不一定是反對(duì)稱的。證明僅證反對(duì)稱性對(duì)差運(yùn)算封閉。設(shè)R1，R2反對(duì)稱，要證R1-R2反對(duì)稱。設(shè)〈x,y〉∈(R1-R2)且〈y,x〉∈(R1-R2),因而〈x,y〉∈R1,〈y,x〉∈R1,從而由R1的反對(duì)稱性得x=y。這就完成了R1-R2反對(duì)稱的證明。定理4.4.6設(shè)R1、R2是A上的反自反關(guān)系，則

R-11、R1∩R2、R1∪R2、R1-R2是A上的反自反關(guān)系。證明留給讀者。我們舉例說明反自反性、對(duì)稱性、反對(duì)稱性、傳遞性對(duì)合成運(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是對(duì)稱的。(3)R={〈a,b〉，〈b,c〉},S={〈b,b〉,〈c,a〉}，R、S是反對(duì)稱的。(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不是對(duì)稱的。（3）RοS={〈a,b〉,〈b,a〉}，所以RοS是對(duì)稱的。（4）RοS={〈a,a〉,〈a,c〉,〈b,a〉}，因?yàn)椤碽,a〉∈RοS,〈a,c〉∈RοS,但〈b,c〉RοS，所以RοS不是傳遞的。4.5關(guān)系的閉包閉包運(yùn)算是關(guān)系運(yùn)算中一種比較重要的特殊運(yùn)算，是對(duì)原關(guān)系的一種擴(kuò)充。在實(shí)際應(yīng)用中，有時(shí)會(huì)遇到這樣的問題，給定了的某一關(guān)系并不具有某種性質(zhì)，要使其具有這一性質(zhì)，就需要對(duì)原關(guān)系進(jìn)行擴(kuò)充，而所進(jìn)行的擴(kuò)充又是"最小"的。這種關(guān)系的擴(kuò)充就是對(duì)原關(guān)系的這一性質(zhì)的閉包運(yùn)算。【定義4.5.1】設(shè)R是非空集合A

上的關(guān)系，如果A上有另一個(gè)關(guān)系R′滿足：

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

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

R″，均有R′R″，則稱R′為R的自反（對(duì)稱或傳遞）閉包。一般將R的自反閉包記作r(R)，對(duì)稱閉包記作s(R)，傳遞閉包記作t(R)。它們分別是具有自反性或?qū)ΨQ性傳遞性的R的"最小"超集合。稱r、s、t為閉包運(yùn)算，它們作用于關(guān)系R后，分別產(chǎn)生包含R的、最小的具有自反性、對(duì)稱性、傳遞性的二元關(guān)系。這三個(gè)閉包運(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），并畫出對(duì)應(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〉}其對(duì)應(yīng)的關(guān)系圖分別如圖4.5.1(a)、(b)、(c)所示。圖4.5.1從以上討論可以看出，傳遞閉包的求取是很復(fù)雜的。但是，當(dāng)集合A為有限集時(shí)，A上二元關(guān)系的傳遞閉包的求取便可大大簡化。推論A為非空有限集合，|A|=n。R是A上的關(guān)系，則存在正整數(shù)k≤n，使得

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

k下列算法是求取R+的有效算法。

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

W。（1）置

W為M。（2）置i=1。（3）對(duì)所有j，1≤j≤n，做①如果W［j,i］=1，則對(duì)每一k=1,2,…,n，置W［j,k］為W［j,k］∨W［i,k］，即當(dāng)?shù)趈行、第i列為1時(shí)，對(duì)第j行每個(gè)分量重新置值，取其當(dāng)前值與第i行的同列分量之析取。②否則對(duì)下一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時(shí)，由于

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

W［1,k］∨

W［1,k］=

W［1,k］，但

W

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

W

［1，2］＝

W

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

W

［1,k］∨

W［2，k］和

W

［4，k］∨

W

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

W

［1，3］＝

W

［2，3］＝W

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

W

［1，