第五章二元關(guān)系

第五章關(guān)系

關(guān)系（主要是二元關(guān)系）是一個(gè)更為復(fù)雜的集合。它的元素是有序二元組的形式，這些有序二元組中的兩個(gè)元素來自于兩個(gè)不同或者相同的集合。因此，關(guān)系是建立在其它集合基礎(chǔ)之上的集合。關(guān)系中的有序二元組反映了不同集合中元素與元素之間的關(guān)系，或者同一集合中元素之間的關(guān)系。主要內(nèi)容如下：5.1笛卡爾積5.5關(guān)系的閉包5.2關(guān)系的概念和表示5.6有序關(guān)系5.3關(guān)系的性質(zhì)5.7等價(jià)關(guān)系和相容關(guān)系5.4逆關(guān)系和復(fù)合關(guān)系有序n元組與n個(gè)元素的集合，是不相同的！例如

但

5.1笛卡爾積

一、有序n元組定義5.1.1

由n個(gè)具有給定次序的個(gè)體a1,a2,….,an組成的

序列稱為有序n元組，記作（a1,a2,….,an）或<a1,a2,….,an>例如{4,4,3,2}={4,3,2}

但(4,4,3,2)≠(4,3,2)定義5.1.2

設(shè)（a1,a2,….,an）和（b1,b2,….,bn）是兩個(gè)有序n元組，若a1=b1,a2=b2,….,an=

bn,則稱這兩個(gè)有序n元組相等，并記作當(dāng)n=2時(shí)，有序二元組(a,b)又稱為序偶。（a1,a2,….,an）=（b1,b2,….,bn）

二、笛卡爾積(1)笛卡爾積的定義定義5.1.3設(shè)A,B為任意集合，A和B的笛卡爾積用表示，定義為

例1

設(shè)則但由此可見當(dāng)或者時(shí)，，即笛卡爾積我們常記作

例2

設(shè)則

（3）與笛卡爾積有關(guān)的一些恒等式設(shè)A、B、C是任意的集合，則有1）2）3）4）

（2）笛卡爾積的基數(shù)當(dāng)A和B均是有限集時(shí)，A×B必為有限集，而且

當(dāng)其中有一個(gè)是無限集時(shí)，必為無限集。5.2關(guān)系的概念與表示一、關(guān)系的基本概念1.關(guān)系的定義定義5.2.1

設(shè)n?N,A1,A2.......,An是n個(gè)集合,若RíA1×A2.......×An,則稱R是定義在A1×A2.......×An上的n元關(guān)系.特殊地，若R=?,則稱R為A1×A2.......×An上的n元空關(guān)系；若R=A1×A2.......×An，則稱呼R為A1×A2.......×An上的全關(guān)系

定義5.2.2笛卡爾積的任意一個(gè)子集稱為是由A到B的一個(gè)二元關(guān)系，當(dāng)時(shí)，稱是A上的二元關(guān)系。例3

設(shè)A={a,b}，B={2,5,8}

則令因?yàn)?，，。所以?和均是由A到B的關(guān)系。又令因?yàn)?。所以和均是由B到A的關(guān)系。對(duì)于,令

因?yàn)椋?所以和均是集合B上的關(guān)系。若，則稱a與b有關(guān)系，又記作。

若，則稱a與b沒有關(guān)系，又記作。例如在例3中，，但

全域關(guān)系

因?yàn)?。所以是一個(gè)由到

的關(guān)系。是

上的一個(gè)關(guān)系。常將記作2.幾種特殊的關(guān)系

空關(guān)系對(duì)任意集合.所以是由

到

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

恒等關(guān)系定義集合上的恒等關(guān)系例4設(shè)則

是上的恒等關(guān)系。是上的全域關(guān)系。

3.關(guān)系的定義域和值域

定義5.2.3設(shè)是由到的一個(gè)關(guān)系，的定義域記作，的值域記作，分別定義為：顯然有例5設(shè)。由到的關(guān)系定義為：當(dāng)且僅當(dāng)a整除b時(shí)，

有。于是的定義域，值域AB2.設(shè)，，由到的關(guān)系則用列舉法表示{}{}{}練習(xí):完成下列題目1.設(shè)，由到的關(guān)系則用列舉法表示{}{}{}{}3.設(shè),。

則{}

{}

4.,

則___

到不同的關(guān)系的個(gè)數(shù)是____

5.設(shè)則_______

A上不同關(guān)系的個(gè)數(shù)是________

6.設(shè)則_______A上不同關(guān)系的個(gè)數(shù)是_______

二、關(guān)系的表示

1、集合表示法用表示集合的列舉法或描述法來表示關(guān)系。例6

設(shè), ,用描述法定義由A到B的關(guān)系，試用列舉法將表示出來。

解

例7

有王、張、李、何是某校的老師，該校有三門課程：語(yǔ)文、數(shù)學(xué)和英語(yǔ)，已知王可以教語(yǔ)文和數(shù)學(xué)，張可以教語(yǔ)文和英語(yǔ)，李可以教數(shù)學(xué)，何可以教英語(yǔ)，若記A={王，張，李，何}，B={語(yǔ)文，數(shù)學(xué)，英語(yǔ)}。那么這些老師與課程之間的對(duì)應(yīng)關(guān)系就可以用由A到B的一個(gè)關(guān)系中的序偶來表示。

={(王,語(yǔ)文),(王,數(shù)學(xué)),(張,語(yǔ)文),(張,英語(yǔ)),(李,數(shù)學(xué)),(何,英語(yǔ))}2、矩陣表示法

定義5.2.4設(shè)A、B都是有限集，,

，由A到B的關(guān)系可以用一個(gè)的矩陣來表示，的第i行第j列的元素取值如下：矩陣稱為的關(guān)系矩陣。例1中由A到B的關(guān)系可以用一個(gè)的矩陣來表示。

157例8

設(shè)，A上的關(guān)系

解

則可以用一個(gè)的矩陣來表示。

12343、關(guān)系圖表示法關(guān)系圖由結(jié)點(diǎn)和邊組成例如

例1中的

，

,則ρ的關(guān)系圖如下AB例如

例3中的，

的關(guān)系圖如下：練習(xí)：完成下列題目設(shè)

，，A到B的關(guān)系

試構(gòu)造出的關(guān)系矩陣

024

2.設(shè)，A上的關(guān)系

試畫出和的關(guān)系圖。5.3關(guān)系的性質(zhì)一、集合A上關(guān)系的性質(zhì)

定義5.3.1

設(shè)是集合A上的關(guān)系

（1）若對(duì)于所有的，均有，則稱在A上是自反的。

（2）若對(duì)于所有的，均有，則稱在A上是反自反的。

ρ在A上是自反的?"x(x?A?xρx)ρ在A上是自反的?"x(x?A?)例1

設(shè)，

（1）自反與反自反

自反自反非自反反自反

定義5.3.1

設(shè)是集合A上的關(guān)系

（3）對(duì)于所有的，若每當(dāng)有就必有，則稱在A上是對(duì)稱的。

（4）對(duì)于所有的，若每當(dāng)有和就必有，則稱在A上是反對(duì)稱的。

ρ在A上是對(duì)稱的?"a

"

b(a?A∧

b?A∧

aρb?bρa(bǔ))ρ在A上是反對(duì)稱的?"a

"

b(a?A∧

b?A∧

aρb

∧

bρa(bǔ)?a=b)（2）對(duì)稱與反對(duì)稱對(duì)稱，非反對(duì)稱非對(duì)稱，反對(duì)稱非對(duì)稱，非反對(duì)稱對(duì)稱，反對(duì)稱

（5）對(duì)于所有的，若每當(dāng)有和就必有，則稱在A上是可傳遞的。

定義5.3.1

設(shè)是集合A上的關(guān)系

ρ在A上是傳遞的?"a

"

b

"

c(a?A∧

b?A∧c?A∧

aρb∧

bρc?aρc)

定義5.3.1

設(shè)是集合A上的關(guān)系

（6）對(duì)于所有的，只要有和就必有，則稱在A上是反傳遞的。

ρ在A上是反傳遞的?"a

"

b

"

c(a?A∧

b?A∧c?A∧

aρb∧

bρc?)（3）可傳遞與不可傳遞可傳遞不可傳遞可傳遞二、關(guān)系性質(zhì)的特征1.關(guān)系矩陣

1234若是對(duì)稱的，則關(guān)系矩陣關(guān)于主對(duì)角線對(duì)稱。若是反對(duì)稱的，則關(guān)系矩陣中，關(guān)于主對(duì)角線對(duì)稱的元素不同時(shí)為1。若是自反的，則關(guān)系矩陣的主對(duì)角線上的所有元素均為1。若是反自反的，則關(guān)系矩陣的主對(duì)角線上所有元素均為0。若ρ是可傳遞的，則在關(guān)系圖中，若每當(dāng)有邊由ai指向ak，且又有邊由ak指向aj，則必有一條邊由ai指向aj。2.關(guān)系圖若ρ是自反的，則關(guān)系圖中每一結(jié)點(diǎn)引出一個(gè)指向自身的單邊環(huán)。若ρ是反自反的，則關(guān)系圖中每一結(jié)點(diǎn)均沒有單邊環(huán)。若ρ是對(duì)稱的，則在關(guān)系圖中，若兩結(jié)點(diǎn)之間存在有邊，則必存在兩條方向相反的邊。若ρ是反對(duì)稱的，則在關(guān)系圖中，任意兩個(gè)不同的結(jié)點(diǎn)間至多只有一條邊。例3

設(shè)，下面分別給出集合A上三個(gè)關(guān)系的關(guān)系圖，試判斷它們的性質(zhì)。

解（1）是自反的，非對(duì)稱，不是反對(duì)稱，不可傳遞。

（2）非自反，也不是反自反，非對(duì)稱，反對(duì)稱，可傳遞。

（3）是自反的，對(duì)稱的，可傳遞的，不是反自反，也不是反對(duì)稱。

練習(xí)：1.從下列各題給出的備選答案中選出正確的答案，并將其代號(hào)填入題后面的括號(hào)內(nèi)。(1)設(shè)A={0,1,2,3}，A上的關(guān)系ρ={(0,0),(0,2),(1,1),(1,3),(2,2),(2,0),(3,1)}，則ρ是

A、自反的B.對(duì)稱的C.反對(duì)稱的D.可傳遞的

()B

A、B（2)設(shè)ρ是整數(shù)集I上的關(guān)系，定義為當(dāng)且僅當(dāng)時(shí)，

，則ρ是

A、自反的

B.對(duì)稱的

C.反對(duì)稱的

D.可傳遞的

()2.

下圖給出了{(lán)1,2,3}上三個(gè)關(guān)系的關(guān)系圖，試對(duì)每一個(gè)圖所表示的關(guān)系的性質(zhì)作出判別，并將選中的性質(zhì)的代號(hào)填入相應(yīng)的括號(hào)內(nèi)。

若A.自反的B.對(duì)稱的C.反對(duì)稱的

D.可傳遞E.反自反則

是（

）則

是（

）則

是（

）

A﹑BA

E5.4逆關(guān)系和復(fù)合關(guān)系一、關(guān)系的并、交、補(bǔ)運(yùn)算例1

設(shè)，

則若和都是由集合A到B的關(guān)系，則，。于是，，因此，和也都是由A到B的關(guān)系。若將看作是全集U，則也都是由A到B的關(guān)系。例2

設(shè)，這里.設(shè)由A到B的關(guān)系,則；；均是由A到B的關(guān)系。二、逆關(guān)系定義5.4.1

設(shè)A、B是任意集合，ρ是由A到B的關(guān)系，定義由B到A的關(guān)系

ρ-1={(b,a)|(a,b)?ρ}稱ρ-1為關(guān)系ρ的逆關(guān)系。

解

由的定義知于是例3

設(shè)，，定義由A到B的關(guān)系：當(dāng)且僅當(dāng)a整除b時(shí)，有，試求的逆關(guān)系。

定理5.4.1：設(shè)R和S均是A到B的關(guān)系，則（1）（R-1）-1=R，（2）（R∪S）-1=R-1∪S-1，（3）（R∩S）-1=R-1∩S-1，（4）（R-S）-1=R-1-S-1，（5）（A×B）-1=B×A（6）Ф-1=Ф，IA-1=IA

（7）R=S<=>R-1=S-1。三、復(fù)合關(guān)系1、復(fù)合關(guān)系的定義

定義5.4.2

設(shè)是由A到B的關(guān)系，是由B到C的關(guān)系，則和的復(fù)合關(guān)系是一個(gè)由A到C的關(guān)系，用表示，定義為：當(dāng)且僅當(dāng)存在元素，使得，時(shí)，有。ρ1ρ2={(a,c)|a?A∧c?C∧$b(b?B∧(a,b)?ρ1∧(b,c)?ρ2)例4

設(shè)是由到的關(guān)系。是由B到的關(guān)系。分別定義為：于是復(fù)合關(guān)系2、關(guān)系復(fù)合運(yùn)算的性質(zhì)定理5.4.2

設(shè)是由集合A到B的關(guān)系，則

例5

以例4中的關(guān)系為例，

,從關(guān)系圖，可得

,定理5.4.3

設(shè)是由A到B的關(guān)系，是由B到C的關(guān)系，是由C到D的關(guān)系，則有

例6

設(shè)，，,.A到B的關(guān)系B到C的關(guān)系C到D的關(guān)系則A到C的關(guān)系因此因此所以定理5.4.5

設(shè)R1和R2是由A到B的關(guān)系，S1和S2是由B到C的關(guān)系，若R1íR2,S1íS2,則R1

S1íR2S2定理5.4.4

設(shè)R1是由A到B的關(guān)系，R2和R3是由B到C的關(guān)系，R4是由C到D的關(guān)系，則1)如果R2íR3,則R1

R2íR1

R3,R2

R4íR3R4

2)R1(R2èR3)=(R1

R2)è(R1

R3)

3)

(R2èR3)

R4=(R2

R4)è(R3

R4)

4)R1(R2∩R3)=(R1

R2)∩(R1

R3)

5)

(R2∩

R3)

R4=(R2

R4)∩(R3

R4)

6)(R1R2)-1=R2-1

R1-1

特別地,當(dāng)，時(shí)，復(fù)合關(guān)系簡(jiǎn)記作，它也是集A上的一個(gè)關(guān)系。其定義如下：1）ρ0=IA2)"n?N,

ρn=ρn-1ρ定理5.4.6

：設(shè)R是A上的關(guān)系，則1）"n?Z，（R

n)-1=(R-1)n2)"n,m?Z,Rn

R

m=Rn+m3)"n,m?Z,(Rn)m=Rnm3.求復(fù)合關(guān)系的方法（1）根據(jù)復(fù)合關(guān)系的定義求復(fù)合關(guān)系

例6中求復(fù)合關(guān)系采用的就是這種方法。

又例如

下面的關(guān)系圖給出了從集合A到B的關(guān)系和從B到C的關(guān)系定理5.4.7

：設(shè)R是A上的關(guān)系，且$s,t?Z,s<t使得Rs=Rt,則

1）"i?Z，Rs+i=Rt+i2)"k,i?Z,Rs+kp+i=Rs+i(p=t-s)3)"q?Z,Rq?{R0,R1,....,Rt-1}（2）運(yùn)用關(guān)系矩陣的運(yùn)算求復(fù)合關(guān)系布爾運(yùn)算其加法和乘法運(yùn)算定義如下

,

,例如

?關(guān)系矩陣的乘積

對(duì)兩個(gè)關(guān)系矩陣求其乘積時(shí)，其運(yùn)算法則與一般矩陣的乘法是相同的，但其中的加法運(yùn)算和乘法運(yùn)算應(yīng)改為布爾加和布爾乘。

則例7

設(shè)和是兩個(gè)關(guān)系矩陣復(fù)合關(guān)系的關(guān)系矩陣

定理5.4.6

設(shè)A、B、C均是有限集，是一由A到B的關(guān)系,是一由B到C的關(guān)系，它們的關(guān)系矩陣分別為和，則復(fù)合關(guān)系的關(guān)系矩陣?yán)?

設(shè)有集合，，A到B的關(guān)系B到C的關(guān)系則234123123與例7比較得例9

設(shè)，A上的關(guān)系試求和。解

作出的關(guān)系矩陣abcd因此根據(jù)定理又，所以因此（3）利用關(guān)系圖求復(fù)合關(guān)系

設(shè)是有限集A上的關(guān)系，則復(fù)合關(guān)系也是A上的關(guān)系，由復(fù)合關(guān)系的定義，對(duì)于任意的，當(dāng)且僅當(dāng)存在，使得，時(shí)，有。

反映在關(guān)系圖上，這意味著，當(dāng)且僅當(dāng)在的關(guān)系圖中有某一結(jié)點(diǎn)存在，使得有邊由指向，且有邊由指向時(shí)，在的關(guān)系圖中有邊從指向。

類似地，對(duì)于任意正整數(shù)n，當(dāng)且僅當(dāng)在的關(guān)系圖中存在n-1個(gè)結(jié)點(diǎn),使得有邊由指向,由指向，…由指向時(shí)，在的關(guān)系圖中，有邊由結(jié)點(diǎn)指向。根據(jù)的關(guān)系圖構(gòu)造出的關(guān)系圖：

對(duì)于的關(guān)系圖中的每一結(jié)點(diǎn)，找出從經(jīng)過長(zhǎng)為n的路能夠到達(dá)的結(jié)點(diǎn)，這些結(jié)點(diǎn)在的關(guān)系圖中，邊必須由指向它們。例10

試?yán)脴?gòu)造和的關(guān)系圖的方法求例9中的和。

例中（4）根據(jù)和的關(guān)系圖直接寫出和中的序偶.解（1）先作出的關(guān)系圖

（2）構(gòu)造的關(guān)系圖。在的關(guān)系圖中尋找長(zhǎng)為2的路。

（3）構(gòu)造的關(guān)系圖。在的關(guān)系圖中尋找長(zhǎng)為3的路.練習(xí)

；完成下列題目設(shè)，A上的關(guān)系則用列舉法表示

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

2.設(shè)，A上的關(guān)系3.下圖給出了集合上的關(guān)系的關(guān)系圖，試畫出關(guān)系和的關(guān)系圖。

3.逆關(guān)系1）IAíρ

?

ρ是自反的反自反的對(duì)稱的反對(duì)稱的傳遞的2）ρ∩IA=?

?ρ是3）ρ=ρ-1?

ρ是4）ρ∩ρ-1

íIA

?ρ是5）ρρíρ?ρ是5）ρρ∩ρ=??ρ是反傳遞的

5.5關(guān)系的閉包一、閉包的定義

定義5.5.1設(shè)R是非空集合A上的關(guān)系,若A另外有一個(gè)關(guān)系R’滿足滿足如下三條，(1）R’是自反的(，

）(2）RR’(3）對(duì)A上任何一個(gè)滿足以上兩條的關(guān)系R”，均有R’R”，則稱關(guān)系R’為R的自反(

,

)閉包,記作r(R),()。對(duì)稱的對(duì)稱s(R),傳遞的傳遞t(R)二、閉包的性質(zhì)

定理5.5.1設(shè)R是非空集A的關(guān)系,則(1)R是自反的充要條件是R=r(R)(2)R是對(duì)稱的充要條件是R=s(R)(3)R是傳遞的充要條件是R=t(R)定理5.5.2

設(shè)R是非空集A的關(guān)系,則r(R)=RA設(shè)R是非空集A的關(guān)系,則s(R)=RR-1設(shè)R是非空集合A上的關(guān)系,t(R)=Ri=RR2…

推論：設(shè)A是非空有限集，|A|=n，則t(R）=RR2…Rn例1

設(shè)，A上的關(guān)系,則

顯然，是自反的。

例2

例4中的

。

它不是對(duì)稱的,

則顯然，是對(duì)稱的。

例3

設(shè)，A上的關(guān)系則注意到,則，二、閉包的性質(zhì)

定理5.5.3設(shè)R是非空集A的關(guān)系,則(1)若R是自反的，則s(R),t(R)也是自反的(2)若R是對(duì)稱的，則r(R),t(R)也是對(duì)稱的(3)若R是傳遞的，則r(R)也是傳遞的定理5.5.４設(shè)R是非空集A的關(guān)系,則(1)rs(R)=sr(R)(2)rt(R)=tr(R)(3)st(R)íts(R)三、利用關(guān)系矩陣和關(guān)系圖求關(guān)系的閉包例7

設(shè)，A上的關(guān)系

求。

1.利用關(guān)系矩陣求的閉包(1)因?yàn)?/p>

所以于是

(2)若，則；，則，即為若中,則中若中，則中。這說明是的轉(zhuǎn)置矩陣。根據(jù)的關(guān)系矩陣。于是（3）因?yàn)?，所以?duì)任意，只要屬于、、、中任何一個(gè)關(guān)系，則，于是于是2.利用關(guān)系圖求的閉包例8

對(duì)例7中的關(guān)系，利用關(guān)系圖求其閉包。ρ的關(guān)系圖r(ρ)的關(guān)系圖t(ρ)的關(guān)系圖S(ρ)的關(guān)系圖

3.設(shè)，A上的關(guān)系

對(duì)下列求出的閉包判斷正確與否，分別將“Y”或“N”填入后面的括號(hào)。

（）（）（）

NYN

5.6次序關(guān)系一、偏序關(guān)系

定義5.5.1設(shè)R是非空集A上的關(guān)系,如果R具有自反性,反對(duì)稱性和傳遞性,則稱R是A上的偏序關(guān)系,或稱半序關(guān)系。稱序偶<A；R>為偏序集（或偏序結(jié)構(gòu)）。

注意：定義中的“≤”不是指普通中的實(shí)數(shù)中的大小關(guān)系的≤,而是一般的偏序關(guān)系。

通常，把偏序關(guān)系R記作≤,如果<a,b>∈≤,則記作a≤b,讀作“a小于等于b”例1:設(shè)集合A＝{a,b,c},A上的關(guān)系R＝{<a,a>,<a,b>,<a,c>,<b,b>,<b,c>,<c,c>},判斷R是否是偏序關(guān)系。例3:設(shè)A是是一個(gè)集合，則集合的“包含”關(guān)系是否是其冪集上的偏序關(guān)系。（是）（是）（是）例2:設(shè)A是非零自然數(shù)集,DA是A上的整除關(guān)系,判斷DA是否是偏序關(guān)系二、擬序關(guān)系

定義5.5.2設(shè)R是非空集A上的關(guān)系,如果R具有反自反性和傳遞性,則稱R是A上的擬序關(guān)系,或稱半序關(guān)系。稱序偶<A；R>為擬序集（或擬序結(jié)構(gòu)）。通常，把擬序關(guān)系R記作＜,如果<a,b>∈＜,則記作a＜b,讀作“a小于b”。例4:設(shè)A是是一個(gè)集合，則集合的“真包含”關(guān)系是否是其冪集上的擬序關(guān)系。例3設(shè)A＝{1,2,3,4},A上的大于關(guān)系和小于關(guān)系是否是擬序關(guān)系。定理5.5.1擬序關(guān)系必是反對(duì)稱的。因此(1)由反自反性和傳遞性可以推出反對(duì)稱。(2)擬序關(guān)系具有反自反性,反對(duì)稱性和傳遞性。(3)擬序和偏序的區(qū)別在于反自反性和自反性上定理5.5.2

若R是偏序關(guān)系,則R-A是擬序關(guān)系。若R是擬序關(guān)系,則R∪A是偏序關(guān)系三、全序關(guān)系

定義5.5.3設(shè)R是A上的偏序關(guān)系,若a,b∈A,則a≤b和b≤a,兩者必居其一,則稱R為A上的全序關(guān)系,或稱線序關(guān)系。稱<A；R>為全序集（或線序集）。例如：實(shí)數(shù)中的≤,≥關(guān)系是全序關(guān)系四、哈斯圖

描述偏序集的關(guān)系圖,可以簡(jiǎn)化為哈斯圖,其簡(jiǎn)化規(guī)則為：1）用小圓圈代表元素2）如果x≤y,并且x≠y,則將代表y的小圓圈畫在代表x的小圓圈的上方3）若x≤y，且在A中不存在任何其它元素z，使得x≤z,z≤y，則有一條由x到y(tǒng)的連線。例5

設(shè)A={a,b,c}，則“í”關(guān)系是P(A)上的偏序關(guān)系，則(P(A),R)是偏序集,其哈斯圖如下例6

A＝{1,2,3,4,5,6},≤是實(shí)數(shù)上的小于等于關(guān)系,因(A,≤)不僅是偏序集,而且還是全序,全序關(guān)系的哈斯圖是一條線故又稱線序,即任何兩個(gè)元素均存在大小關(guān)系。123456四、最大元,最小元,極大元,極小元定義5.5.4設(shè)(A,≤)是偏序集,集合BA1)若存在元素b∈B,使得B中沒有元素x滿足x≠b且x≤b,則稱b為B的一個(gè)極小元

2)若存在元素b∈B,使得B中沒有元素x滿足x≠b且b≤x,則稱b為B的一個(gè)極大元

3)如存在元素b∈B,使得x∈B,均有b≤x,則稱b為B的最小元

4)如存在元素b∈B,使得x∈B,均有x≤b,則稱b為B的最大元例如設(shè)<A;≤>的哈斯圖如下所示：討論當(dāng)B去相應(yīng)集合時(shí)，其最大元,最小元,極大元,極小元a,ba,b無無a,bc無cB極小元極大元最小元最大元{a,b}{a,b,c}abcdefghiabcdefghiB極小元極大元最小元最大元{a,b,c,d}{b,c,d,f}{a,c,f,i}a,bc,d無無bfbfaiai說明：1)如果A的子集B存在最大元b,則最大元是唯一的。

2)最大元可能不存在3)極大元未必是最大元4)極大元未必是唯一的5)如果B存在最大元x,則x就是B的極大元,此時(shí)極大元也只有一個(gè)6)孤立點(diǎn)則又是極大元,也是極小元五、上界、下界；上確界，下確界定義5.5.5設(shè)(A,≤)是偏序集,集合B是A的非空子集1)如存在a∈A,使得x∈B,均有x≤a,則稱B有上界，并稱a為B的一個(gè)上界

2)如存在a∈A,使得x∈B,均有a≤x,則稱B有下界，并稱a為B的一個(gè)下界

3）若a是B的上界，并且對(duì)B的每一個(gè)上界a’皆有a≤a’，則稱a是B的上確界

4）若a是B的下界，并且對(duì)B的每一個(gè)下界a’皆有a’≤a，則稱a是B的下確界例如B上界下界上確界下確界{a,b}{a,b,c}c,d,e,f,g,h,i無無無c,e,f,h,i無c無abcdefghiabcdefghiB上界下界上確界下確界{a,b,c,d}{b,c,d,f}{a,c,f,i}f,h,i無f無f,h,ibfbiaia六、良序關(guān)系

定義5.5.4設(shè)≤是A上的偏序關(guān)系,則<A；≤>是良序集，當(dāng)且僅當(dāng)：1）≤是A上的全序關(guān)系2）A的每個(gè)子集都有極小元練習(xí)

1.對(duì)下述論斷判斷正確與否，在相應(yīng)括號(hào)中鍵入“Y”或“N”。（1）設(shè)A={2,3,6,12,24,36}，A上的整除關(guān)系是一偏序關(guān)系，用“≤”表示。

(b)“≤”={(2,2),(2,6),(3,3),(3,6),(6,6),(6,12),(12,12),(12,24),(24,24),(36,36)}（）NY（2）集合A={3,9,27,54}上的整除關(guān)系是A上的全序（）Y（a）該偏序關(guān)系的次序圖是（）解

滿足上述條件的最小基數(shù)的關(guān)系ρ2={（2,3），（2,4），（4,3）｝一般說，給定ρ1和ρ1·ρ2，不能唯一的確定ρ2。例如ρ2=｛（2,3），(2,4)，(4,3)，(0,0)，(3,3)｝也可以.1．給定ρ1=｛(0,1),（1,2）,（3,4）,ρ1·ρ2=｛(1,3)，（1,4），（3,3）｝,求一個(gè)基數(shù)最小的關(guān)系,使?jié)M足ρ2的條件.一般地說,若給定ρ1和ρ1·ρ2，ρ2能被唯一地確定嗎?基數(shù)最小的ρ2能被唯一確定嗎？給定ρ1和ρ1·ρ2，也不能唯一的確定出最小基數(shù)的ρ2。

則ρ2=｛（2,3），(2,4)，(4,3)｝或ρ2=｛（2,3），(2,4)，(3,3)｝都可以。例如ρ1=｛（0,1），(1,2)，(3,3)，(3,4)｝，ρ1·ρ2=｛（1,3），(1,4)，(3,3)｝，432．下列關(guān)系哪一個(gè)是自反的、對(duì)稱的、反對(duì)稱的或可傳遞的？（1）當(dāng)且僅當(dāng)n1·

n2<8(n1,n2∈N）時(shí),有n1ρn2（2）當(dāng)且僅當(dāng)r1≤|

r2|(r1,r2∈R)時(shí),有r1ρr2

解（1）ρ不是自反的，如4∈N，但4·4=16>8。

ρ是對(duì)稱的，因?yàn)閷?duì)于任意的n1,n2∈N，若有n1·

n2<8，則n2n1=n1n2<8。ρ不是可傳遞的，例如，3·2<8，2·3<8，但3·3=9>8。

ρ不是反對(duì)稱的，例，2·3<8，3·2<8，但3≠2.（2）ρ是自反的，因?yàn)閷?duì)任意的r∈R，有r≤|r|。

ρ不是對(duì)稱的，如-1≤|3|，但3>|-1|。ρ不是可傳遞的，100≤|-101|，-101≤|2|，但100>|2|ρ不是反對(duì)稱的，如-3≤|2|，2≤|-3|，但-3≠2。設(shè)ρ1和ρ2是集合A上的任意兩個(gè)關(guān)系,判斷下列命題是否正確,并說明理由.（1）若ρ1和ρ2是自反的，則ρ1·ρ2也是自反的；（2）若ρ1和ρ2是非自反的，則ρ1·ρ2也是非自反的；證明（1）正確。(2)否。所以對(duì)任意的a∈A,有a(ρ1·ρ2)a，因此ρ1·ρ2也是自反的。又對(duì)任意的a∈A,有aρ2a.

因?yàn)閷?duì)任意的a∈A,有aρ1a,例如，設(shè)集合A=｛a,b｝.ρ1={(a,b),(b,a)},ρ2={(a,b),(b,a)}顯然ρ1和ρ2都是非自反的，但ρ1·ρ2自反。

（3）若ρ1和ρ2是對(duì)稱的，則ρ1·ρ2也是對(duì)稱的；（4）若ρ1和ρ2是反對(duì)稱的，則ρ1·ρ2也是反對(duì)稱的；（5）若ρ1和ρ2是可傳遞的，則ρ1·ρ2也是可傳遞的；例如，設(shè)集合A=｛1,2,3｝，ρ1=｛（1,2），（2,1）｝,ρ2=｛（1,3），(3,1)｝，顯然ρ1和ρ2都是對(duì)稱的，例如設(shè)A=｛1,2,3｝,ρ1={(1,2),(3，3）｝,ρ2={(2,3）,(3，1）｝顯然ρ1和ρ2都是反對(duì)稱的，例如設(shè)A=｛1,2,3},ρ1={(1,2),(2,3）,(1,3）},ρ2=｛（2，3），（3，1），（2，1）｝，顯然ρ1和ρ2都可傳遞的.但ρ1·ρ2=｛（2,3）｝不是對(duì)稱的。但ρ1·ρ2={(1,3）,(2,1）,(1,1)}不是可傳遞的。但ρ1·ρ2=｛（1,3），(3,1)｝不是反對(duì)稱的。證明（3）否.

(4)否.（5）否.4.有人說，集合A上的關(guān)系，如果是對(duì)稱的且可傳遞，則它也是自反的。其理由是，從對(duì)稱性傳遞性例

設(shè)A＝｛1,2，3｝ρ＝｛(1,2),(2,1),(1,1),(2,2)}

5．設(shè)ρ1是集合A上的一個(gè)關(guān)系，ρ2=｛（a,b）|存在c，使（a,c）∈ρ1且（c,b）∈ρ1｝，試證明：若ρ1是一個(gè)等價(jià)關(guān)系，則ρ2也是一個(gè)等價(jià)關(guān)系。證明

因?yàn)棣?是自反的，所以對(duì)于任意的a∈A,有（a,a）∈ρ1

，

由（a,a）∈ρ1,(a,a)∈ρ1由ρ1的對(duì)稱性,又有（b,c）∈ρ1,且（c,a）∈ρ1,因而有（b,a）∈ρ2,故ρ2是對(duì)稱的。對(duì)于任意的a,b∈A,若（a,b）∈ρ2,則必有元素c∈A，使得（a,c）∈ρ1,且（c,b）∈ρ1,

因此有（a,a)∈ρ2,ρ2是自反的。

對(duì)于任意的a,b,c∈A,若（a,b）∈ρ2,(b,c)∈ρ2,則必有元素d,e∈A,使得（a,d）∈ρ1(d,b)∈ρ1(b,e)∈ρ1(e,c)∈ρ1

由ρ1的可傳遞性，又有（a,b）∈ρ1,(b,c)∈ρ1,于是有（a,c）∈ρ2,故ρ2是可傳遞的。

由上證得ρ2是一個(gè)等價(jià)關(guān)系。證法二設(shè)（a,b）∈ρ1,由ρ1的自反性，又有（a,a）∈ρ1,

由（a,a）∈ρ1,(a,b)∈ρ1,于是有（a,b）∈ρ2,因此ρ1ρ2。

反之，設(shè)（a,b）∈ρ2，則必存在c∈A,使得（a,c）∈ρ1,(c,b)∈ρ1,

而由ρ1的可傳遞性，又有（a,b）∈ρ1,因此ρ2ρ1.由上可知ρ2=ρ1，因此ρ2是等價(jià)關(guān)系。

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

一、相容關(guān)系

定義5.7.1

設(shè)R是集合A上的關(guān)系，如果它是自反的，對(duì)稱的，則稱R是A上的相容關(guān)系。若aRb,則稱a和b是相容的，否則稱a和b是不相容的。

例1

設(shè)A為學(xué)生的集合，考察集合A上的“同班同學(xué)”關(guān)系是否是相容關(guān)系？是1.相容關(guān)系的定義

例2

有學(xué)生6人組成集合A={張小平，王平，丁小燕，王芳，王春，李承}定義A上的關(guān)系R={(x,y)|x,y∈A，且x與y中出現(xiàn)有相同的字}，考察R是否是A上的相容關(guān)系？

是

例3

設(shè)A={T1,T2,T3,T4,T5,T6}是某臺(tái)微機(jī)上6項(xiàng)任務(wù)的集合，有五個(gè)子程序S1,S2,S3,S4,S5供它們選擇調(diào)用，下表列出了它們調(diào)用子程序的情況。調(diào)用的子程序任務(wù)名稱

定義A上的關(guān)系R={(x,y)|x,y∈A且x與y調(diào)用了相同的子程序},問R是否是相容關(guān)系？是2.相容關(guān)系的簡(jiǎn)化表示

125432.極大相容類

定義5.7.2設(shè)R是非空集合A上的相容關(guān)系，SíA,如果對(duì)于S中的任意元素a和b,皆有aRb,則稱S為一個(gè)關(guān)于R的相容類；

定義5.7.3設(shè)R是非空集合A上的相容關(guān)系，S是一個(gè)關(guān)于R的相容類。若S不真包含在其他的相容類中，則稱S是關(guān)于R的一個(gè)極大相容類。

例4設(shè)集合A={1,2,3,4,5,6,7}的相容關(guān)系R如下圖所示，則R的所有極大相容類包括：1254367{1,2,3,4},{2,5},{3,6},{5,6,7}例5設(shè)集合A={1,2,3,4,5}的相容關(guān)系R如下圖所示，則R的所有極大相容類包括：12543{1,2,3},{3,4},{4,5},如何求出一個(gè)相容關(guān)系R的極大相容類？1、設(shè)S是關(guān)于相容關(guān)系R的一個(gè)極大相容類，問：S的子集是否是關(guān)于R的相容類？是2、從偏序關(guān)系的角度考察極大相容類3、如果一個(gè)相容類由{x}èS形成，則S應(yīng)當(dāng)滿足什么條件？

(1)S是一個(gè)相容類(2)S是x鄰接點(diǎn)集合的子集考慮下面兩個(gè)問題：

設(shè)相容關(guān)系R的所有相容類集合為S,則<S,í>是一個(gè)偏序集，極大相容類是該偏序集的極大元1254367例6初始狀態(tài)：n=7;S={1},{2},{3},{4},{5},{6},{7}A={7}Si∩A={7}S={1},{2},{3},{4},{5},{6},{7}+{6,7}-{6}-{7}={1},{2},{3},{4},{5},{6,7}n=6A={6,7}Si∩A={6,7}S={1},{2},{3},{4},{5},{6,7}+{5,6,7}-{5}-{6,7}={1},{2},{3},{4},{5,6,7}n=5A=?Si∩A=?S={1},{2},{3},{4},{5,6,7}n=4A={4,6}Si∩A={4},{6}S={1},{2},{3},{4},{5,6,7}+{3,4}+{3,6}-{3}-{4}={1},{2},{5,6,7},{3,4},{3,6}n=3A={3,4,5}Si∩A={5},{3,4},{3}S={1},{2},{5,6,7},{3,4},{3,6}+{2,5}+{2,3,4}+{2,3}-{2}-{2,3}-{3,4}={1},{5,6,7},{3,6},{2,5},{2,3,4}n=2A={2,3,4}Si∩A={2,3,4},{3},{2}S={1},{5,6,7},{3,6},{2,5},{2,3,4}n=1+{1,2,3,4}+{1,3}+{1,2}-{1}-{1,2}-{1,3}-{2,3,4}={5,6,7},{3,6},{2,5},{1,2,3,4}二、相容關(guān)系與覆蓋

定理5.7.1

設(shè)ρ是有限集合A上的一個(gè)相容關(guān)系，#A=n，則對(duì)于任意a∈A，必存在一個(gè)最大相容類C，使得a∈C。證明

設(shè)a∈A，若對(duì)于任意b∈A，a≠b均有則{a}就是一個(gè)最大相容類。若存在，使得，則令對(duì)于來說，若存在元素，使得與中各元素都有相容關(guān)系，則又得，…，由于A中元素個(gè)數(shù)有限，所以至多經(jīng)過n-1步，這個(gè)過程就會(huì)終止，而最后得到的，就是最大相容類且

定理5.7.2

設(shè)ρ是有限集合A上的一個(gè)相容關(guān)系，則ρ的所有最大相容類的集合是A的一個(gè)覆蓋。

證明

設(shè)是ρ的所有最大相容類構(gòu)成的集合，顯然由定理2-9，對(duì)任意a∈A，必存在某個(gè)最大相容類，使得，因此,于是,故，S是A的一個(gè)覆蓋。集合A上相容關(guān)系ρ的最大相容類所構(gòu)成的A的覆蓋常記作

定理5.7.3

設(shè)是A的一個(gè)覆蓋，根據(jù)S定義的關(guān)系是A上的相容關(guān)系。證明

因?yàn)?，所以?duì)于任意a∈A，必然存在某個(gè)使得，因此，于是(a,a)∈ρ，故ρ是自反的。對(duì)于任意a,b∈A，若(a,b)∈ρ，則必存在某個(gè)使得因而，于是(b,a)∈A，故ρ是對(duì)稱的。由上證明ρ是A上的相容關(guān)系。例如

設(shè)A={a,b,c,d},集合和

是A的兩個(gè)不同的覆蓋，但根據(jù)它們構(gòu)造出的相容關(guān)系均是ρ={(a,a),(a,b),(b,a),(b,b),(b,c),(c,b),(c,d),(d,c),(b,d),(d,b),(c,c),(d,d)}

可見，相容關(guān)系和覆蓋之間并不存在著一一對(duì)應(yīng)的關(guān)系練習(xí)1.設(shè)集合，ρ是A上的相容關(guān)系，其關(guān)系矩陣的下三角矩陣為

（1）試根據(jù)相容關(guān)系的對(duì)稱性，填入關(guān)系矩陣中的其它元素。

（2）用列舉法表示ρ={}(a1,a1),(a2,a1),(a2,a2),(a3,a3),(a4,a2),(a4,a3),(a4,a4),(a5,a1),(a5,a3),(a5,a5),(a1,a2),(a1,a5),(a2,a4),(a3,a4),(a3,a5)（3）寫出集合A上ρ的最大相容類覆蓋。三、等價(jià)關(guān)系

1、等價(jià)關(guān)系的定義定義5.7.4集合A上的關(guān)系ρ，如果它是自反的，對(duì)稱的，且可傳遞的，則稱ρ是A上的等價(jià)關(guān)系。

例如

一群人的集合中姓氏相同的關(guān)系也是等價(jià)關(guān)系。但朋友關(guān)系不是等價(jià)關(guān)系，因?yàn)樗豢蓚鬟f。例7

設(shè)A是任意集合，則A上的恒等關(guān)系和全域關(guān)系UA均是A上的等價(jià)關(guān)系。例8

設(shè)A={1,2,3,4,5,6,7,8,9},定義A上的關(guān)系R:則R是A上的等價(jià)關(guān)系。2.元素a與b等價(jià)

設(shè)ρ是集合A上的等價(jià)關(guān)系，若元素aρb，則稱a與b等價(jià)，或稱b與a等價(jià)。123456710893.等價(jià)類

定義5.7.5設(shè)ρ是集合A上的等價(jià)關(guān)系，則A中等價(jià)于元素a的所有元素組成的集合稱為a生成的等價(jià)類，用表示，即

例如

對(duì)于例8中的R來說[1]R={1,2,3},[2]R={1,2,3},[3]R={1,2,3},[4]R={4},[5]R={5,6},[6]R={5,6},[7]R={7,8,9,10},[8]R={7,8,9,10},[9]R={7,8,9,10},[10]R={7,8,9,10},4、等價(jià)類的性質(zhì)

1.對(duì)任意,因?yàn)閷?duì)于任意的a∈A,有aρa(bǔ)，所以。

2.對(duì)任意的a,b∈A若aρb，則