禁煙教案

學(xué)習(xí)目標(biāo)：

1．深刻理解序偶、笛卡爾積、關(guān)系、集合的劃分與覆蓋、等價(jià)關(guān)系、等價(jià)

類、商集、相容關(guān)系、（最大）相容類、偏序關(guān)系、極大元、極小元、上（下）

界、上（下）確界、最大（?。┰⑷蜿P(guān)系、良序關(guān)系等概念；

2．掌握集合的交、并、差、補(bǔ)、對稱差的運(yùn)算及其運(yùn)算規(guī)律；

3．掌握關(guān)系的交、并、逆、復(fù)合運(yùn)算、閉包運(yùn)算及其性質(zhì)；

4．掌握關(guān)系的矩陣表示和關(guān)系圖；

5．深刻理解關(guān)系的自反性、反自反性、對稱性、反對稱性和傳遞性，掌握

其判別方法；

6．掌握集合的覆蓋與劃分的聯(lián)系與區(qū)別；

7．掌握偏序關(guān)系的判別及其哈斯圖的畫法；會求偏序集中給定集合的極大

元、極小元、上（下）界、上（下）確界、最大（?。┰?/p>

主要內(nèi)容：

1．集合的基本概念及其運(yùn)算

2．序偶與笛卡爾積

3．關(guān)系及其表示

4．關(guān)系的性質(zhì)及其判定方法

5．復(fù)合關(guān)系和逆關(guān)系

6．關(guān)系的閉包運(yùn)算

7．等價(jià)關(guān)系與相容關(guān)系

8．偏序關(guān)系

頁腳內(nèi)容

禁煙教案

重點(diǎn)：

1．關(guān)系的性質(zhì)及其判別；

2．關(guān)系的復(fù)合運(yùn)算及其性質(zhì)；

3．等價(jià)關(guān)系與等價(jià)類、等價(jià)關(guān)系與集合的劃分的聯(lián)系；

4．偏序關(guān)系判別及其哈斯圖的畫法、偏序集中特異位置元素的理解。

難點(diǎn)：

1．關(guān)系的傳遞性及其判別；

2．等價(jià)關(guān)系的特性；

3．偏序關(guān)系的哈斯圖的畫法；偏序集中特異位置元素的求法。

教學(xué)手段：

通過多個(gè)實(shí)例的精講幫助同學(xué)理解重點(diǎn)和難點(diǎn)的內(nèi)容，并通過大量的練

習(xí)使同學(xué)們鞏固和掌握關(guān)系的性質(zhì)及其判別、關(guān)系的復(fù)合運(yùn)算及其性質(zhì)、等價(jià)

關(guān)系的特性、偏序關(guān)系的哈斯圖的畫法及偏序集中特異位置元素的求法。

習(xí)題：

習(xí)題3.1：4，6；習(xí)題3.2：3（8），4（12），6（m）；習(xí)題3.4：1（2）、

(4)，3；習(xí)題3.5：1，4；習(xí)題3.6：2，5，6；習(xí)題3.7：2，5，6；習(xí)題

3.8：1（1）-（6）；習(xí)題3.9：3（2）、（4），4（3）；習(xí)題3.10：1，4，5。

3.1集合的基本概念

集合(set)（或稱為集）是數(shù)學(xué)中的一個(gè)最基本的概念。所謂集合，就是指具有共同性

質(zhì)的或適合一定條件的事物的全體，組成集合的這些“事物”稱為集合的元素。

集合常用大寫字母表示，集合的元素常用小寫字母表示。若A是集合，a是A的元

頁腳內(nèi)容

禁煙教案

素，則稱a屬于A，記作aA；若a不是A的元素，則稱a不屬于A，記作。若組成集

合的元素個(gè)數(shù)是有限的，則稱該集合為有限集(FiniteSet)，否則稱為無限集(Infinite

Set)。

常見集合專用字符的約定：

N—自然數(shù)集合(非負(fù)整數(shù)集)I或Z整數(shù)集合I，I)

()—(

Q有理數(shù)集合Q，Q)R—實(shí)數(shù)集合(R，R)

—(

F分?jǐn)?shù)集合F，F(xiàn))腳標(biāo)+和-是對正、負(fù)的區(qū)分

—(

C—復(fù)數(shù)集合P—素?cái)?shù)集合

O—奇數(shù)集合E—偶數(shù)集合

冪集

定義3.1.1對于每一個(gè)集合A，由A的所有子集組成的集合，稱為集合A的冪集

(PowerSet)，記為P(A)或2A．即P(A){BBA}。

例如：A{a,b,c},P(A){,{a},,{c},{a,b},{b,c},{a,c},{a,b,c}}。

定理3.1.1如果有限集A有n個(gè)元素，則其冪集P(A)有2n個(gè)元素。

證明A的所有由k個(gè)元素組成的子集數(shù)為從n個(gè)元素中取k個(gè)的組合數(shù)。

n(n1)(n2)(nk1)

Ck

nk!

另外，因A，故P(A)的元素個(gè)數(shù)N可表示為

n

N1C1C2CkCnCk

nnnnn

k0

n

又因(xy)nCkxkynk

n

k0

令xy1

n

得2nCk

n

k0

故P(A)的元素個(gè)數(shù)是2n。

頁腳內(nèi)容

禁煙教案

人們常常給有限集A的子集編碼，用以表示A的冪集的各個(gè)元素。具體方法是：

設(shè)A{a,a,,a}，則A子集B按照含a記1、不含a記0(i1,2,,n)的規(guī)定

12nii

依次寫成一個(gè)n位二進(jìn)制數(shù)，便得子集B的編碼。

例如，若B{a,a}，則B的編碼是10001，當(dāng)然還可將它化成十進(jìn)制數(shù)。如果

1n

n4，那么這個(gè)十進(jìn)制數(shù)為9，此時(shí)特別記B{a,a}為B。

149

3.2集合的對稱差運(yùn)算

定義3.2.1設(shè)A、B是兩個(gè)集合，要么屬于A，要么屬于B，但不能同時(shí)屬于A

和B的所有元素組成的集合，稱為A和B的對稱差集，記為AB。即

AB(AB)(BA)xxAxB

例如，若A{1,2,c,d}，B{1,b,3,d}，則AB{2,c,b,3}。

對稱差的定義如圖3-1所示。

圖3-1

由對稱差的定義容易推得如下性質(zhì)：

（1）ABBA

（2）AA

（3）AA

（4）AB(AB)(AB)

（5）(AB)CA(BC)

頁腳內(nèi)容

禁煙教案

證明（5）(AB)C

[(AB)C](ABC)

{[(AB)(AB)]C}[(AB)(AB)C]

(ABC)(ABC){[(AB)(AB)]C}

但[(AB)(AB)]C

={[(AB)A][(AB)B]}C

[(AA)(AB)(AB)(BB)]C

[(AB)(AB)]C

(ABC)(ABC)

故(AB)C

(ABC)(ABC)(ABC)(ABC)

又A(BC)

(ABC)[A(BC)]

[A(BC)(BC)]{A[(BC)(BC)]}

{A[(BC)(BC)]}[(ABC)(ABC)]

因?yàn)锳[(BC)(BC)]

A[(BB)(BC)(CB)(CC)]

A[(BC)(CB)]

(ABC)(ACB)

故A(BC)

(ABC)(ABC)(ABC)(ABC)

因此(AB)CA(BC)

對稱差運(yùn)算的結(jié)合性亦可用圖3-2說明。

頁腳內(nèi)容

禁煙教案

ABBC

(AB)CA(BC)

圖3-2對稱差運(yùn)算的結(jié)合性

從文氏圖3-3亦可以看出以下關(guān)系式成立。

AB(AB)(BA)(AB)

(AB)(AB)

圖3-3AB

3.4序偶與笛卡爾積

3.4.1序偶

在日常生活中，有許多事物是成對出現(xiàn)的，而且這種成對出現(xiàn)的事物，具有一定的

順序。例如，上，下；12；男生9名而女生6；中國地處亞洲；平面上點(diǎn)的坐標(biāo)等。一

般的說，兩個(gè)具有固定次序的客體組成一個(gè)序偶(OrderedPair)，記作x,y。上述各例

可分別表示為〈上，下〉；1,2；9,6；〈中國，亞洲〉；a,b等。

序偶可以看作是具有兩個(gè)元素的集合，但它與一般集合不同的是序偶具有確定的次

序。在集合中，a,bb,a，但對序偶，當(dāng)ab時(shí)，a,bb,a。

定義3.4.1兩個(gè)序偶相等，x,yu,v，當(dāng)且僅當(dāng)xu,yv。

頁腳內(nèi)容

禁煙教案

這里指出：序偶a,b中兩個(gè)元素不一定來自同一個(gè)集合，它們可以代表不同類型的

事物。例如，a代表操作碼，b代表地址碼，則序偶a,b就代表一條單地址指令；當(dāng)然

亦可將a代表地址碼，b代表操作碼，a,b仍代表一條單地址指令。但上述這種約定，

一經(jīng)確定，序偶的次序就不能再予以變化了。在序偶a,b中，a稱第一元素，b稱第二

元素。

序偶的概念可以推廣到有序三元組的情況。

有序三元組是一個(gè)序偶，其第一元素本身也是一個(gè)序偶，可形式化表示為

x,y,z。由序偶相等的定義，可以知道x,y,zu,v,w當(dāng)且僅當(dāng)

x,yu,v,zw，即xu,yv,zw，我們約定有序三元組可記作x,y,z。注

意：x,y,zx,y,z，因?yàn)閤,y,z不是有序三元組。同理，有序四元組被定義

為一個(gè)序偶，其第一元素為有序三元組，故有序四元組有形式為x,y,z,w，可記作

x,y,z,w，且

x,y,z,wp,q,r,sxpyqzrws

這樣，有序n元組定義為x,x,,x,x，記作

(Orderedn-tuple)12n1n

x,x,,x,x，且

12n1n

x,x,,xy,y,,yxyxyxy

12n12n1122nn

一般地，有序n元組x,x,,x中的x稱作有序n元組的第i個(gè)坐標(biāo)。

12ni

3.4.2笛卡爾積

定義3.4.2設(shè)A和B是任意兩個(gè)集合，若序偶的第一個(gè)成員是A的元素，第二個(gè)

成員是B的元素，所有這樣的序偶集合，稱為集合A和B的笛卡爾乘積或直積(Cartesian

頁腳內(nèi)容

禁煙教案

Product)，記作AB。即

AB{x,yxAyB}

例3.4.1若A{1,2},B{a,b,c},求AB,BB以及(AB)(BA)

解AB{1,a,1,b,1,c,2,a,2,b,2,c}

BB{a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c}

BA{a,1,a,2,b,1,b,2,c,1,c,2}

(AB)(BA)

顯然，我們有：

（1）ABBA；

（2）如果Am,Bn，則ABBAABmn。

我們約定：若A或B，則AB。

由笛卡爾積定義可知：

(AB)C{x,y,zx,yABzC}

{x,y,zxAyBzC}

A(BC){x,y,zxAy,zBC}

由于x,y,z不是三元組，所以

(AB)CA(BC)

定理3.4.1設(shè)A、B和C為任意三個(gè)集合，則有

（1）A(BC)(AB)(AC)

（2）A(BC)(AB)(AC)

（3）(AB)C(AC)(BC)

（4）(AB)C(AC)(BC)

頁腳內(nèi)容

禁煙教案

證明（1）設(shè)x,yA(BC)xAyBC

xA(yByC)

(xAyB)(xAyC)

x,yABx,yAC

x,y(AB)(AC)

因此，A(BC)(AB)(AC)。

（4）設(shè)x,y(AB)CxAByC

(xAxB)yC

(xAyC)(xByC)

x,yACx,yBC

x,y(AC)(BC)

因此，(AB)C(AC)(BC)。

定理3.4.2設(shè)A、B和C為三個(gè)非空集合，則有

ABACBCCACB

證明設(shè)AB，對任意的x,y，

x,yACxAyC

xByC

x,yBC

因此，ACBC。

反之，若ACBC，取yC，則對x，有

xAxAyCx,yAC

x,yBCxByC

xB

因此，AB。

頁腳內(nèi)容

禁煙教案

定理的第二部分ABCACB，證明類似。

定理3.4.3設(shè)A、B、C和D為四個(gè)非空集合，則ABCD的充要條件為

AC且BD。

證明若ABCD，對任意的xA,yB，有

(xA)(yB)x,yABx,yCD

(xC)(yD)

即AC,BD。

反之，若AC且BD，設(shè)任意xA,yB，有

x,yAB(xA)(yB)

(xC)(yD)

x,yCD

因此，ABCD。

對于有限個(gè)集合可以進(jìn)行多次笛卡爾積運(yùn)算。為了與有序n元組一致，我們約

定：

AAA(AA)A

123123

AAAA(AAA)A

12341234

((AA)A)A

1234

一般地，AAA(AAA)A

12n12n1n

{x,x,,xxAxAxA}

12n1122nn

故AAA是有序n元組構(gòu)成的集合。

12n

特別地，同一集合的n次直積AAA，記為An,這里AnAn1A。

n

例如，{1,2}3{1,2}2{1,2}{1,1,1,2,2,1,2,2}{1,2}

{1,1,1,1,1,2,1,2,1,1,2,2,

頁腳內(nèi)容

禁煙教案

2,1,1,2,1,2,2,2,1,2,2,2}

{(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)}

此處，A2,A3238。一般地，若Am,則Anmn。

3.5關(guān)系及其表示

3.5.1關(guān)系的定義

在日常生活中我們都熟悉關(guān)系這詞的含義，例如，父子關(guān)系、上下級關(guān)系、朋友關(guān)

系等。我們知道，序偶可以表達(dá)兩個(gè)客體、三個(gè)客體或n個(gè)客體之間的聯(lián)系，因此可以用

序偶表達(dá)關(guān)系這個(gè)概念。

例如，機(jī)票與艙位之間有對號關(guān)系。設(shè)X表示機(jī)票的集合，Y表示艙位的集合，則對

于任意的xX和yY，必有x與y有對號關(guān)系和x與y沒有對號關(guān)系兩種情況的一

種。令R表示“對號”關(guān)系，則上述問題可以表達(dá)為xRy或xRy，亦可記為x,yR或

x,yR，因此，我們看到對號關(guān)系R是序偶的集合。

定義3.5.1設(shè)X、Y是任意兩個(gè)集合，則稱直積XY的任一子集為從X到Y(jié)的一

個(gè)二元關(guān)系(BinaryRelation)。二元關(guān)系亦簡稱關(guān)系，記為R，RXY。

X到Y(jié)的二元關(guān)系R，如圖3-4所示。

圖3-4

集合X到Y(jié)的二元關(guān)系是第一坐標(biāo)取自X、第二坐標(biāo)取自Y的序偶集合。如果序偶

x,yR，也說x與y有關(guān)系R，記為xRy；如果序偶x,yR，則說x與y沒有關(guān)

頁腳內(nèi)容

禁煙教案

系R，記為xRy。

當(dāng)XY時(shí)，關(guān)系R是XX的子集，這時(shí)稱R為集合X上的二元關(guān)系。

例3.5.1（1）設(shè)A{a,b}，B{2,5,8}，則

AB{a,2,a,5,a,8,b,2,b,5,b,8}，

令

R{a,2,a,8,b,2}

1

R{a,5,b,2,b,5}

2

R{a,2}

3

因?yàn)镽AB，RAB，RAB，所以R，R和R均是由A到B的關(guān)

123123

系。

（2）>={x,yx,y是實(shí)數(shù)且xy}是實(shí)數(shù)集上的大于關(guān)系。

定義3.5.2設(shè)R為X到Y(jié)的二元關(guān)系，由x,yR的所有x組成的集合稱為R的

定義域或前域(Domain)，記作domR或D(R)，即

domR{x(y)(x,yR)}

使x,yR的所有y組成的集合稱為R的值域(Range)，記作ranR，即

ranR{y(x)(x,yR)}。

R的定義域和值域一起稱作R的域(Field)，記作FLDR，即

FLDRdomRranR

顯然，domRX，ranRY，F(xiàn)LDRdomRranRXY

例3.5.2設(shè)A{1,3,7}，B{1,2,6}，H{1,2,1,6,7,2}，

求domH，ranH和FLDH。

頁腳內(nèi)容

禁煙教案

解domH{1,7}，ranH{2,6}，F(xiàn)LDH{1,2,6,7}。

例3.5.3設(shè)X{2,3,4,5}，求集合X上的關(guān)系“”、dom及ran。

解{2,3,2,4,2,5,3,4,3,5,4,5}

dom{2,3,4}

ran{3,4,5}

3.5.2幾種特殊的關(guān)系

1．空關(guān)系

對任意集合X，Y，XY，XX，所以是由X到Y(jié)的關(guān)系，也是X

上的關(guān)系，稱為空關(guān)系(EmptyRelation)。

2．全域關(guān)系

因?yàn)閄YXY，XXXX，所以XY是一個(gè)由X到Y(jié)的關(guān)系，稱為

由X到Y(jié)的全域關(guān)系(UniversalRelation)。XX是X上的一個(gè)關(guān)系，稱為X上的全

域關(guān)系，通常記作E，即

X

E{x,xx,xX}。

Xijij

例3.5.4若H{f,m,s,d}表示家庭中父、母、子、女四個(gè)人的集合，確定H上的

全域關(guān)系和空關(guān)系，另外再確定H上的一個(gè)關(guān)系，并指出該關(guān)系的前域和值域。

解設(shè)H上同一家庭的成員的關(guān)系為H，

1

H{f,f,f,m,f,s,f,d,m,f,m,m,m,s,m,d,

1

s,f,s,m,s,s,s,d,d,f,d,m,d,s,d,d}

設(shè)H上的互不相識的關(guān)系為H，H，則H為全域關(guān)系，H為空關(guān)系。

2212

設(shè)H上的長幼關(guān)系為H，

3

H{f,s,f,d,m,s,m,d}

3

頁腳內(nèi)容

禁煙教案

domH{f,m}

3

ranH{s,d}

3

3．恒等關(guān)系

定義設(shè)I是X上的二元關(guān)系且滿足Ix,xxX)，則稱I是X上

3.5.3XXX

的恒等關(guān)系(IdenticalRelation)。

例如，A{1,2,3}，則I1,1,2,2,3,3。

A

因?yàn)殛P(guān)系是序偶的集合，因此，可以進(jìn)行集合的所有運(yùn)算。

定理3.5.1若Q和S是從集合X到集合Y的兩個(gè)關(guān)系，則Q、S的并、交、補(bǔ)、

差仍是X到Y(jié)的關(guān)系。

證明因?yàn)镼XY,SXY,

故QSXY,QSXY

S(XYS)XY

QS(QS)XY

例若A{1,2,3,4}，R{x,y(xy)/2A,x,yA}，

3.5.51

R{x,y(xy)/3A,x,yA}，求RR，RR，RR和

2121212

R。

1

解R{3,1,4,2}，R{4,1}，

12

RR

12

RR{3,1,4,2,4,1}

12

RRR

121

RER

1A1

{1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,

3,2,3,3,3,4,4,1,4,3,4,4}

頁腳內(nèi)容

禁煙教案

3.5.3關(guān)系的表示

1．集合表示法

因?yàn)殛P(guān)系是序偶的集合，因此可用表示集合的列舉法或描述法來表示關(guān)系。例如，例

3.5.1的（1）中的關(guān)系R，R和R及例中的關(guān)系H，均是用列舉法表示的關(guān)

1233.5.2

系；而例的（）中的關(guān)系和例中的關(guān)系R，R都是用描述法表示的關(guān)

3.5.123.5.512

系。

有限集合間的二元關(guān)系R除了可以用序偶集合的形式表達(dá)以外，還可用矩陣和圖形表

示，以便引入線性代數(shù)和圖論的知識來討論。

2．矩陣表示法

設(shè)給定兩個(gè)有限集合X{x,x,,x}，Y{y,y,,y}，則對應(yīng)于從X到Y(jié)

12m12n

的二元關(guān)系R有一個(gè)關(guān)系矩陣Mr，其中

Rijmn

1當(dāng)x,yR

rij(i1,2,,m;j1,2,,n)。

ij0當(dāng)x,yR

ij

如果R是有限集合X上的二元關(guān)系或X和Y含有相同數(shù)量的有限個(gè)元素，則M

R

是方陣。

例若A{a,a,a,a,a}，B{b,b,b}，

3.5.612345123

R{a,b,a,b,a,b,a,b,a,b,a,b,a,b}，寫出關(guān)系矩陣M。

11132223314252R

解

101

011

M100

R

010

010

53

例3.5.7設(shè)X{1,2,3,4}，寫出集合X上的大于關(guān)系>的關(guān)系矩陣。

頁腳內(nèi)容

禁煙教案

解>{2,1,3,1,3,2,4,1,4,2,4,3}

0000

1000

M

1100

1110

3．關(guān)系圖表示法

有限集合的二元關(guān)系也可用圖形來表示。設(shè)集合Xx,x,,x到

12m

Yy,y,,y上的一個(gè)二元關(guān)系為R，首先我們在平面上做出m個(gè)結(jié)點(diǎn)分別記作

12n

x,x,,x，另外做n個(gè)結(jié)點(diǎn)分別記作y,y,,y。如果xRy，則從結(jié)點(diǎn)x至結(jié)點(diǎn)

12m12niji

y做一有向弧，其箭頭指向y，如果xRy，則x,y之間沒有線段連接。用這種方法連

jjijij

接起來的圖稱為R的關(guān)系圖。

例3.5.8畫出例3.5.6的關(guān)系圖。

解本題的關(guān)系圖如圖3-11所示：

圖3-11例3.5.8的關(guān)系圖

例3.5.9設(shè)A{1,2,3,4,5}，R{1,2,1,5,2,2,3,2,3,1,4,3}，畫出R

的關(guān)系圖。

解因?yàn)镽是A上的關(guān)系，故只需畫出A中的每個(gè)元素即可。如果aRa，就畫一

ij

條由a到a的有向弧。若aa，則畫出的是一條自回路。本題的關(guān)系圖如圖所

ijij3-12

頁腳內(nèi)容

禁煙教案

示。

3

2

14

5

圖3-12例3.5.9的關(guān)系圖

關(guān)系圖主要表達(dá)結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系，故關(guān)系圖與結(jié)點(diǎn)位置和線段的長短無

關(guān)。

從X到Y(jié)的關(guān)系R是XY的子集，即RXY，而

XY(XY)(XY)，所以，R(XY)(XY)。令ZXY，則

RZZ。因此，我們今后通常限于討論同一集合上的關(guān)系。

3.6關(guān)系的性質(zhì)及其判定方法

3.6.1關(guān)系的性質(zhì)

定義3.6.1設(shè)R是定義在集合X上的二元關(guān)系，如果

（1）對于每一個(gè)xX，都有xRx，則稱R是自反的(Reflexive)。即

R在X上自反(x)(xXxRx)

（2）對于每一個(gè)xX，都有xRx，則稱R是反自反的(Antireflexive)。即

R在X上反自反(x)(xXxRx)

（3）對于任意x,yX，若xRy，就有yRx，則稱R是對稱的(Symmetric)。即

R在X上對稱(x)(y)((xX)(yX)(xRy)(yRx))

頁腳內(nèi)容

禁煙教案

（4）對于任意x,yX，若xRy，yRx，必有xy，則稱R在X上是反對稱的

(Antisymmetric)。即

R在X上反對稱(x)(y)((xX)(yX)(xRy)(yRx)(xy))

（5）對于任意x,y,zX，若xRy，yRz，就有xRz，則稱R在X上是傳遞的

(Transitive)。即

R在X上傳遞(x)(y)(z)((xX)(yX)(zX)(xRy)(yRz)(xRz))

例3.6.1設(shè)A{1,2,3}，則集合A上的關(guān)系

R{1,1,2,2,2,1,3,3}是自反而不是反自反的關(guān)系；

1

R{1,2,1,3,2,1,2,3}是反自反而不是自反的關(guān)系；

2

R{1,1,1,3,2,1,2,3}是既不是自反也不是反自反的關(guān)系；

3

R{1,1,1,3,3,1,2,3,3,2}是對稱的而不是反對稱的關(guān)系；

4

R{1,1,1,3,2,1,2,3}是反對稱的而不是對稱的關(guān)系；

5

R{1,1,2,2,3,3}是既對稱也反對稱的關(guān)系；

6

R{1,2,2,3,3,2}是既不對稱也不反對稱關(guān)系。

7

R{1,1,1,2,2,1,2,2}，R{1,2,3,2}是可傳遞的關(guān)系；

89

R{1,2,2,3,1,3,2,1}是不可傳遞的關(guān)系，因?yàn)?,2R，2,1R，

101010

但1,1R。

10

由定義3.6.1及例3.6.1可知：

（1）對任意一個(gè)關(guān)系R，若R自反則它一定不反自反，若R反自反則它也一定不自

反；但R不自反，它未必反自反，若R不反自反，也未必自反。

（2）存在著既對稱也反對稱的關(guān)系。

頁腳內(nèi)容

禁煙教案

圖3-5表明了自反與反自反、對稱與反對稱性之間的關(guān)系。

圖3-5

例3.6.2(1)集合之間的關(guān)系是自反的、反對稱的和可傳遞的。因?yàn)椋?/p>

1）對于任意集合A，均有AA成立，所以是自反的；

2）對于任意集合A,B，若AB且BA，則AB，所以是反對稱的；

3）對于任意集合A,B,C，若AB且BC，則AC，所以是可傳遞

的。

（2）平面上三角形集合中的相似關(guān)系是自反的、對稱的和可傳遞的。因?yàn)椋喝我庖?/p>

個(gè)三角形都與自身相似；若三角形A相似于三角形B，則三角形B必相似于三角形A；

若三角形A相似于三角形B，且三角形B相似于三角形C，則三角形A必相似于三角形

C。

（3）人類的祖先關(guān)系是反自反、反對稱和可傳遞的。

（4）實(shí)數(shù)集上的“>”關(guān)系是反自反、反對稱和可傳遞的。

（5）實(shí)數(shù)集上的“”關(guān)系是自反、反對稱和可傳遞的。

（6）實(shí)數(shù)集上的“=”關(guān)系是自反、對稱、反對稱和可傳遞的。

（7）人群中的父子關(guān)系是反自反和反對稱的。

（8）正整數(shù)集上的整除關(guān)系是自反、反對稱和可傳遞的。

（9）是反自反、對稱、反對稱和可傳遞的。

頁腳內(nèi)容

禁煙教案

（10）任意非空集合上的全關(guān)系是自反的、對稱的和可傳遞的。

例3.6.3設(shè)整數(shù)集Z上的二元關(guān)系R定義如下：

R{x,yx,yZ,(xy)/2是整數(shù)}，

驗(yàn)證R在Z上是自反和對稱的。

證明xZ,(xx)/20，即x,xR，故R是自反的。

又設(shè)x,yZ，如果xRy，即(xy)/2是整數(shù)，則(yx)/2也必是整數(shù)，即

yRx，因此R是對稱的。

3.6.2由關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)

例3.6.4集合A{1,2,3,4}，A上的關(guān)系R的關(guān)系矩陣為：

1010

0100

M，

R1011

0011

R的關(guān)系圖如圖3-6所示。討論R的性質(zhì)。

圖3-6

解從R的關(guān)系矩陣和關(guān)系圖容易看出，R是自反的、對稱的。

一般地，我們有：

（1）若關(guān)系R是自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上的所有元素都是1；其關(guān)

系圖上每個(gè)結(jié)點(diǎn)都有自環(huán)。

（2）若關(guān)系R是對稱的，當(dāng)且僅當(dāng)其關(guān)系矩陣是對稱矩陣；其關(guān)系圖上任意兩個(gè)結(jié)

頁腳內(nèi)容

禁煙教案

點(diǎn)間若有定向弧，必是成對出現(xiàn)的。

（3）若關(guān)系R是反自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上的元素皆為0；關(guān)系圖

上每個(gè)結(jié)點(diǎn)都沒有自環(huán)。

（4）若關(guān)系R是反對稱的，當(dāng)且僅當(dāng)其關(guān)系矩陣中關(guān)于主對角線對稱的元素不能同

時(shí)為1；其關(guān)系圖上任意兩個(gè)不同結(jié)點(diǎn)間至多出現(xiàn)一條定向弧。

（5）若關(guān)系R是可傳遞的，當(dāng)且僅當(dāng)其關(guān)系矩陣滿足：對i,j,k,ij,jk，若

r1

ij

且r1，則r1；其關(guān)系圖滿足：對i,j,k,ij,jk，若有弧由a指向a，且又

jkikij

有弧由a指向a，則必有一條弧由a指向a。

jkik

例3.6.5圖3-7是由關(guān)系圖所表示的A{a,b,c}上的5個(gè)二元關(guān)系。

（1）（2）

（3）（4）

頁腳內(nèi)容

禁煙教案

（5）

圖3-7

請判斷它們的性質(zhì)。

解(1)是反對稱、傳遞但不是對稱的關(guān)系，而且是既不自反也不反自反的關(guān)系；

(2)是自反、傳遞、反對稱的關(guān)系，但不是對稱也不是反自反的關(guān)系；

(3)是反自反但不是對稱、不是反對稱、不是自反也不是傳遞的關(guān)系；

(4)是不自反、不反自反但是傳遞的關(guān)系，而且既是對稱也是反對稱的關(guān)系；

(5)是自反、反對稱但不是傳遞、不是對稱也不是反自反的關(guān)系。

3.7復(fù)合關(guān)系和逆關(guān)系

3.7.1復(fù)合關(guān)系

1.復(fù)合關(guān)系的定義

定義3.7.1設(shè)R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，則RS稱為R和S的復(fù)合

關(guān)系(

CompositiveRelation)，表示為

RS{x,zxXzZ(y)(yYxRyySz)}

從R和S求RS，稱為關(guān)系的復(fù)合運(yùn)算。

復(fù)合運(yùn)算是關(guān)系的二元運(yùn)算，它能夠由兩個(gè)關(guān)系生成一個(gè)新的關(guān)系，以此類推。例

如，R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，P是從Z到W的關(guān)系，則(RS)P

是從X到W的關(guān)系。

例3.7.1設(shè)R是由A{1,2,3,4,}到B{2,3,4}的關(guān)系，S是由B到C{3,5,6}

的關(guān)系，分別定義為：

R{a,b|ab6}{2,4,3,3,4,2}

頁腳內(nèi)容

禁煙教案

S{b,c|b整除c}{2,6,3,3,3,6}

于是復(fù)合關(guān)系

RS{3,3,3,6,4,6}。

例3.7.2設(shè)A是所有人的集合。

R{a,b|a,bA,a是b的兄弟}，

1

R{b,c|b,cA,b是c的父親}，

2

那么

RR{a,c|a,cA,a是c的叔伯}；

12

而

RR{a,c|a,cA,a是c的祖父}。

22

例設(shè)R和R是集合A{0,1,2,3}上的關(guān)系，

3.7.312

R{i,jji1或ji/2}，R{i,jij2}

12

求RR、RR、（RR）R和（RR）R。

1221121111

解R{0,1,1,2,2,3,0,0,2,1}

1

R{2,0,3,1}

2

RR{1,0,2,1}

12

RR{2,1,2,0,3,2}

21

（RR）R{1,1,1,0,2,2}

121

RR{0,2,0,1,1,3,1,1,0,0,2,2}

11

（RR）R{0,3,0,1,0,2,1,2,0,0,2,3,2,1}

111

頁腳內(nèi)容

禁煙教案

2.關(guān)系的復(fù)合運(yùn)算的性質(zhì)

定理設(shè)R是由集合X到Y(jié)的關(guān)系，則IRRIR。

3.7.1XY

定理3.7.2設(shè)R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，則有

（1）dom(RS)domR

（2）ran(RS)ranS

（3）若ranRdomS，則RS。

證（1）和（2）是顯然的，下面我們證明（3）。用反證法。

反設(shè)RS，則必存在xX,zZ，使x,zRS，從而yY，使

x,yR,y,zS，故yranR且ydomS，所以yranRdomS，這就與

ranRdomS矛盾，因此，RS。

定理（）設(shè)R、R和R分別是從X到Y(jié)、Y到Z和Z到W的關(guān)系，則

3.7.31123

(RR)RR(RR)

123123

即關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律。

（）設(shè)R和R都是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，則

212

1）(RR)S(RS)(RS)

1212

2）(RR)S(RS)(RS)

1212

（）設(shè)S是從X到Y(jié)的關(guān)系，R和R都是從Y到Z的關(guān)系，則

312

1）S(RR)(SR)(SR)

1212

2）S(RR)(SR)(SR)

1212

證我們只證明（2），其它證明類似。

1）x,z(RR)S

12

(y)(yYx,yRRy,zS)

12

頁腳內(nèi)容

禁煙教案

(y)(yY(x,yRx,yR)y,zS)

12

(y)(yYx,yRy,zS)(y)(yYx,yR)y,zS)

12

x,zRSx,zRS

12

x,z(RS)(RS)

12

所以(RR)S(RS)(RS)

1212

2）x,z(RR)S

12

(y)(yYx,yRRy,zS)

12

(y)(yYx,yRx,yRy,zS)

12

x,zRSx,zRS

12

x,z(RS)(RS)

12

所以(RR)S(RS)(RS)。

1212

注意：一般來說，

（）(RR)S(RS)(RS)；

11212

（2）關(guān)系的復(fù)合運(yùn)算不滿足交換律。

例3.7.4（1）設(shè)A{a,b,c}，B{x,y,z}，R和R都是從A到B的關(guān)系，S

12

是從B到A的關(guān)系，R{a,x,a,y}，R{a,x,a,z}，

12

S{x,b,y,c,z,c}，則

(RR)S{a,b}，(RS)(RS){a,b,a,c}，

1212

可見，(RR)S(RS)(RS)，但(RR)S(RS)(RS)。

12121212

（）設(shè)A{a,b,c}，R和R都是集合A上的關(guān)系，R{a,b}，

2121

頁腳內(nèi)容

禁煙教案

R{b,a}，則RR{a,a}，而RR{b,b}，所以RRRR。

212211221

由于關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，所以(RR)RR(RR)可以寫成

123123

RRR。一般地，若R是一由A到A的關(guān)系，R是由A到A的關(guān)系，，R是一

1231