離散數(shù)學(xué)-第六章

1第六章關(guān)系§6.1關(guān)系及其性質(zhì)§6.2關(guān)系的運(yùn)算§6.3次序關(guān)系§6.4等價(jià)關(guān)系與劃分2§6.1關(guān)系及其性質(zhì)重點(diǎn)：1.關(guān)系的表示2.關(guān)系的性質(zhì)3一、關(guān)系的定義定義6.1(關(guān)系):X到Y(jié)的關(guān)系:

若R是XY的子集(即RX

Y

),則稱R為X到Y(jié)的二元關(guān)系，簡(jiǎn)稱為關(guān)系。當(dāng)X=Y時(shí),稱R為X上的二元關(guān)系。若<x,y>R,則可表示成xRy,讀做“x與y有關(guān)系R”若<x,y>R,則記作xRy,讀作“x與y不存在關(guān)系R”ˉ4例1:A={1,2,3},B={a,b}R={<1,a>,<1,b>,<2,b>}是A到B的關(guān)系。例2：實(shí)數(shù)集合上的大于關(guān)系“>”表示如下：

>={<x,y>|x,y是實(shí)數(shù)且x>y}

空關(guān)系：設(shè)X是集合，XX的子集，稱為X上的空關(guān)系。X上的全域關(guān)系:UX={<xi,xj>|xi，xjX}=XXX上的恒等關(guān)系：IX={<x,x>|xX}5例3：設(shè)X={0,1,2}UX={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>}IX={<0,0>,<1,1>,<2,2>}定義6.2

設(shè)RXY,dom(R)={xX|yY:<x,y>R},為R的定義域

ran(R)={yY|xX:<x,y>R},為R的值域

顯然，dom(R)X，ran(R)Y6二、關(guān)系的表示關(guān)系矩陣：設(shè)X={x1,……,xm},Y={y1,……,yn},R是X到Y(jié)的二元關(guān)系。

R的關(guān)系矩陣，記作MR=(rij)mn,其中

0若xiRyjrij=1若xiRyjˉ（僅討論從有限集到有限集的二元關(guān)系）7R的關(guān)系矩陣是:100111例6.3設(shè)X={x1,x2},Y={y1,y2,y3},R是X到Y(jié)的關(guān)系。

R={<x1,y1>,<x2,y1>,<x2,y2>,<x2,y3>}82.關(guān)系圖:設(shè)X是有窮集合,則X上的二元關(guān)系R的關(guān)系圖可構(gòu)造如下:

X集合中的元素稱為頂點(diǎn)

,并用點(diǎn)或小圈表示,對(duì)于元素xi

和xj,分別標(biāo)以頂點(diǎn)xi

和xj。如果xiRxj

，即<xi,xj>R,就用一條帶箭頭的弧線把xi

和xj連接起來(lái)，箭頭的方向由xi

指向xj；如果

xiRxj且xjRxi,則在xi

和xj之間畫上兩條方向相反的弧線;

如果

xiRxi，則畫一條從xi

出發(fā)又返回頂點(diǎn)xi的弧線，稱這一條弧線為自環(huán)

.當(dāng)R中所有有序偶處理完畢后,便得到關(guān)系R的圖

.91234圖6.4集合X上的關(guān)系圖例6.4:設(shè)X={1,2,3,4},R是集合X上的關(guān)系,R={<1,2>,<2,2>,<2,4>,<3,2>,<3,4>,<4,1>,<4,3>}則R的關(guān)系圖如下：10三、關(guān)系的性質(zhì)(自反、反自反、對(duì)稱、反對(duì)稱、傳遞)定義6.3設(shè)R是非空集合X上的二元關(guān)系R是自反的

x(xX<x,x>R)在R的關(guān)系圖中，每個(gè)頂點(diǎn)均有自環(huán)；在R的關(guān)系矩陣中，主對(duì)角線的元素均為1。R是反自反的

x(xX<x,x>R)在R的關(guān)系圖中，每個(gè)頂點(diǎn)均無(wú)自環(huán)；在R的關(guān)系矩陣中，主對(duì)角線的元素均為0。11R是對(duì)稱的

xy(xXyX<x,y>R<y,x>R)在R的關(guān)系圖中，任意兩個(gè)不同頂點(diǎn)之間：或者無(wú)弧或者有兩條方向相反的?。籖的關(guān)系矩陣是對(duì)稱矩陣.R是反對(duì)稱的

xy(xXyX<x,y>R<y,x>Rx=y)xy(xXyX<x,y>Rxy<y,x>R)在R的關(guān)系圖中，任意不同頂點(diǎn)之間至多有一條??；在R的矩陣中,若ij且

rij=1,則rji=0。12R是傳遞的xyz(xXyXzX<x,y>R<y,z>R<x,z>R)在R的關(guān)系圖中，若頂點(diǎn)x到頂點(diǎn)y有一條路徑，則必有從x到y(tǒng)的一條弧（處處有捷徑）。從關(guān)系矩陣中不易看出傳遞關(guān)系的特征。例(1)X上的恒等關(guān)系是自反、對(duì)稱、反對(duì)稱、傳遞的

(2)X上的“<”是反自反、反對(duì)稱、傳遞的思考題(1)非空集X上的空關(guān)系？？？(2)空集上的空關(guān)系？？？13指出下列二元關(guān)系所具有的性質(zhì):例:設(shè)X={1,2,3},集合X上的二元關(guān)系R1={<1,2>,<2,3>,<3,1>}R2={<1,2>,<1,3>}R3={<1,2>,<1,3>,<2,3>,<3,2>}R4={<1,2>,<2,1>,<1,3>,<3,1>,<1,1>,<2,2>,<3,3>}14關(guān)系圖和關(guān)系矩陣中五種性質(zhì)的表述R自反反自反對(duì)稱反對(duì)稱傳遞MR對(duì)角線元素全1對(duì)角線元素全0對(duì)稱矩陣aij.aji=0(ij)若有k使aik.akj=1,則aij=1GR所有結(jié)點(diǎn)都有自圈所有結(jié)點(diǎn)都無(wú)自圈

結(jié)點(diǎn)間有向邊都成對(duì)出現(xiàn)結(jié)點(diǎn)間無(wú)成對(duì)出現(xiàn)的有向邊處處有捷徑15圖6.5給出了一些關(guān)系圖，指出由這些圖給定的關(guān)系所具有的性質(zhì)，并寫出對(duì)應(yīng)的關(guān)系矩陣。x5x1x2x3x1x2x3x4(a)(b)x1x2x3x4(c)圖6.5關(guān)系圖(d)x2x1x3x416解圖6.5(a)的關(guān)系是反對(duì)稱的,反自反的.

圖6.5(b)的關(guān)系是自反的、對(duì)稱的、反對(duì)稱的、和可傳遞的。圖6.5(c)的關(guān)系是自反的，對(duì)稱的。圖6.5(d)的關(guān)系是反自反的、反對(duì)稱的、傳遞的。關(guān)系圖：直觀、形象關(guān)系矩陣：便于計(jì)算機(jī)處理17思考題：設(shè)A為恰有n個(gè)元素的有限集，1）A上共有多少個(gè)不同的自反關(guān)系？2）A上共有多少個(gè)不同的反自反關(guān)系？3）A上共有多少個(gè)不同的對(duì)稱關(guān)系？4）A上共有多少個(gè)不同的反對(duì)稱關(guān)系？5）A上共有多少個(gè)不同的既是對(duì)稱又反對(duì)稱的關(guān)系？18§6.2關(guān)系的運(yùn)算重點(diǎn)掌握關(guān)系的復(fù)合、逆、自反閉包、對(duì)稱閉包、傳遞閉包等定義及運(yùn)算定義6.4設(shè)R和S是從集合A到B的關(guān)系,取全集為A×B,則R∩S,R∪S,R－S,～R仍是A到B的關(guān)系，并且對(duì)于任意x∈A,y∈B:x(R∩S)yxRy∧xSyx(R∪S)yxRy∨xSyx(R－S)yxRy∧xSyx(～R)yxRyˉˉ19例4.12設(shè)R和S是集合A＝｛1,2,3,4｝上的關(guān)系，

R＝｛〈x,y〉｜x－y是2的非零整倍數(shù)｝

S＝｛〈x,y〉｜x－y是3的非零整倍數(shù)｝求：R∩S，R∪S，R－S和～R。解R＝｛〈1,3〉,〈3,1〉,〈2,4〉,〈4,2〉｝

S＝｛〈1,4〉,〈4,1〉｝則R∩S＝R∪S＝{〈1,3〉,〈3,1〉,〈2,4〉,〈4,2〉,〈1,4〉,〈4,1〉}R－S＝{〈1,3〉,〈3,1〉,〈2,4〉,〈4,2〉}

～R＝{〈1,1〉,〈1,2〉,〈1,4〉,〈2,1〉,〈2,2〉,〈2,3〉,〈3,2〉,〈3,3〉,〈3,4〉,〈4,1〉,〈4,3〉,〈4,4〉}20定義6.5設(shè)R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則R·S＝｛〈x,z〉｜y

Y使得:xRy∧ySz)｝為X到Z的關(guān)系,稱為R和S的復(fù)合關(guān)系。R·SRS21例4.13設(shè)R＝｛〈1,2〉,〈2,2〉,〈3,4〉｝,S＝｛〈1,3〉,〈2,5〉,〈3,1〉,〈4,2〉｝求:R·S,S·R,(R·S)·R，R·(S·R)，R·R。解:R·S={<1,5>,<2,5>,<3,2>}S·R={<1,4>,<3,2>,<4,2>}R·R={<1,2>,<2,2>}顯然，dom(R·S)dom(R)，ran(R·S)ran(S)。

R·S≠S·R，故關(guān)系的復(fù)合運(yùn)算不滿足交換律。

(R·S)·R={<3,2>}R·(S·R)={<3,2>}可證：關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律。22定理6.1設(shè)R，S，P分別是X到Y(jié)、Y到Z、Z到W的關(guān)系，則(R·S)·P＝R·(S·P)。證明:對(duì)任意〈x,w〉:

〈x,w〉∈(R·S)·P

z∈Z(〈x,z〉∈R·S∧〈z,w〉∈P)

z∈Z(y∈Y(〈x,y〉∈R∧〈y,z〉∈S)∧〈z,w〉∈P)

y∈Y(〈x,y〉∈R∧z∈Z(〈y,z〉∈S∧〈z,w〉∈P))

y∈Y(〈x,y〉∈R∧〈y,w〉∈S·P)〈x,w〉∈R·(S·P)故(R·S)·P＝R·(S·P)。23例6.8設(shè)R和S是整數(shù)集合Z上的兩個(gè)關(guān)系，R＝｛〈x,2x〉｜x∈Z｝，S＝｛〈x,7x〉｜x∈Z｝求：R·S，R·R，R·R·R和R·S·R。解 R·S＝｛〈x,14x〉｜x∈Z｝

R·R＝｛〈x,4x〉｜x∈Z｝

R·R·R＝｛〈x,8x〉｜x∈Z｝

R·S·R＝｛〈x,28x〉｜x∈Z｝定義4.16設(shè)R是集合A上的關(guān)系，n是自然數(shù)，R的n次冪Rn定義如下：(1)R0

是集合A上的恒等關(guān)系IA，即R0＝IA；(2)Rn＋1＝Rn·

R。顯然，R1＝R0·

R＝IA·

R＝R

24對(duì)n歸納易證，對(duì)于任意m,n∈N，(1)Rm·

Rn＝Rm＋n(2)(Rm)n＝Rmn兩個(gè)關(guān)系的復(fù)合，也可用矩陣運(yùn)算來(lái)表示。用矩陣運(yùn)算求兩個(gè)關(guān)系的復(fù)合多用于一個(gè)集合上的關(guān)系的復(fù)合。為了不失一般性，下面介紹A到B的關(guān)系和B到C的關(guān)系的復(fù)合。關(guān)系復(fù)合的矩陣表示：25設(shè)A＝｛a1,a2,…,am｝,B＝｛b1,b2,…,bp｝,C＝｛c1,c2,…,cn｝,R是A到B的關(guān)系，S是B到C的關(guān)系，關(guān)系矩陣MR＝(rij)m×p

，MS＝(sij)p×n,則

R·S的關(guān)系矩陣MR·S

＝(tij)m×n

，其中

tij＝(ri1∧s1j)

∨(ri2∧s2j)

∨…∨(rip∧spj)

＝(rik∧skj)

因?yàn)橛蓮?fù)合關(guān)系的定義，〈ai,cj〉∈R·S當(dāng)且僅當(dāng)，存在bk使得〈ai,bk〉∈R且〈bk,cj〉∈S。即rik＝skj＝1。故rik∧skj＝1。也就是說(shuō)，ri1∧s1j，ri2∧s2j，…，rip∧spj中至少有一個(gè)是1，即(ri1∧s1j)

∨(ri2∧s2j)

∨…∨(rip∧spj)＝1?！舙K=126例：設(shè)A＝｛a,b,c,d｝上的關(guān)系R＝｛〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉｝,求R2的關(guān)系矩陣。解：

MR＝MR2＝*＝27顯然，dom(R－1)＝ran(R)，ran(R－1)＝dom(R)，

R－1

的逆關(guān)系是R，即(R－1)－1

＝R。若R和S都是關(guān)系，則(R∪S)－1

＝R－1∪S－1

。R－1

的關(guān)系矩陣是:R的關(guān)系矩陣MR的轉(zhuǎn)置矩陣。將R的關(guān)系圖中的每條有向邊的方向反向，就得到R－1

的關(guān)系圖。定義6.7將關(guān)系R中每個(gè)有序偶的第一元和第二元對(duì)換所得到的關(guān)系,稱為R的逆關(guān)系，記作R－1，

R－1＝｛〈x,y〉｜〈y,x〉∈R｝。例如R＝｛〈a,1〉,〈a,3〉,〈b,1〉,〈b,2〉,〈c,1〉｝

R－1＝｛〈1,a〉,〈3,a〉,〈1,b〉,〈2,b〉,〈1,c〉｝28關(guān)系復(fù)合的性質(zhì)

設(shè)二元關(guān)系R1

AB，R2,R3

BC，R4

CD：若R2

R3，則R1oR2

R1oR3

且R2oR4

R3oR4；

R1o(R2∪R3)=(R1oR2)∪(R1oR3)；

(R2∪R3)oR4=(R2oR4)∪(R3oR4)；

R1o(R2∩R3)(R1oR2)∩(R1oR3)；

(R2∩R3)oR4

(R2oR4)∩(R3oR4)；

(R1oR2)–1=R2–1

oR1–1；

(R1oR2)oR4=R1o(R2oR4)。29思考題

設(shè)R1

和R2

都是集合A上的二元關(guān)系，證明或用反例推翻以下的論斷：a)若R1和R2都是自反的，則R1

oR2(R12)也是自反的；b)若R1和R2都是反自反的，則R1

oR2(R12)也是反自反的；c)若R1和R2都是對(duì)稱的，則R1

oR2(R12)也是對(duì)稱的；d)若R1和R2都是傳遞的，則R1

oR2(R12)也是傳遞的。30定理6.2設(shè)R和S是關(guān)系，則(R·S)－1＝S－1

·R－1。證明對(duì)于任意〈z,x〉，

〈z,x〉∈(R·S)－1

〈x,z〉∈R·S

y(〈x,y〉∈R∧〈y,z〉∈S)

y(〈y,x〉∈R－1∧〈z,y〉∈S－1)

〈z,x〉∈S－1·R－1因此，(R·S)－1＝S－1·R－1

。31二元關(guān)系性質(zhì)的判斷條件

引理6.1設(shè)R為A上的二元關(guān)系，則有條件成立：

R為自反的

iffIA

R；

R為反自反的

iff

IAR=；

R為對(duì)稱的

iffR=R–1

；

R為反對(duì)稱的

iffR

R–1

IA；

R為傳遞的

iff

RoRR

。32定義6.8設(shè)R是集合A上的關(guān)系。關(guān)系R′

稱為R的自反（對(duì)稱、傳遞）閉包，當(dāng)且僅當(dāng)R′滿足以下三個(gè)條件：(1)R′是自反的（對(duì)稱的、傳遞的）；(2)R

R′

；(3)對(duì)于A上的任何自反（對(duì)稱、傳遞）關(guān)系R，如果RR

，則R′

R。將R的自反(對(duì)稱、傳遞)閉包分別記作r(R),s(R),t(R)

可以證明：

R的自反、對(duì)稱、傳遞閉包r(R),s(R),t(R)的存在性與唯一性。33由定義6.8可知：1）R是自反的當(dāng)且僅當(dāng)r(R)＝R；2）R是對(duì)稱的當(dāng)且僅當(dāng)s(R)＝R；3）R是傳遞的當(dāng)且僅當(dāng)t(R)＝R。定理6.3設(shè)R是集合A上的關(guān)系，則r(R)＝R∪IA

。證明：顯然R∪IA是自反的，且R

R∪IA

,由自反閉包r(R)的定義可知，r(R)

R∪IA。另外,r(R)

是A上的自反關(guān)系且Rr(R)

,因此

IA

r(R),故R∪IAr(R)。所以，r(R)＝R∪IA

。34定理6.4設(shè)R是集合A上的關(guān)系，則s(R)＝R∪R–1

。證明:因(R∪R–1)–1＝R–1∪(R–1)–1＝R–1∪R＝R∪R–1,由引理6.1可知，R∪R–1

是對(duì)稱的。顯然R’R∪R–1。設(shè)R′是A上任意對(duì)稱關(guān)系且RR′

，則R–1(R')–1。因?yàn)镽′是對(duì)稱的，由引理6.1，(R′)–1＝R′

,故R－1R′，所以R∪R－1

R′

。由對(duì)稱閉包定義知，s(R)＝R∪R－1

定理6.5設(shè)R是集合A上的關(guān)系，則

t(R)＝R∪R2∪R3∪…=證明：只要證明t(R)與互相包含即可。首先用歸納法證：對(duì)于任意n1，

Rn

t(R)。由傳遞閉包的定義可知，Rt(R)。35設(shè)對(duì)于任意n1,

Rnt(R),

下面證明：Rn+1t(R)。設(shè)<x,y>Rn+1，由于Rn+1=Rn·

R，則存在zA，使得<x,z>Rn，<z,y>R。根據(jù)歸納假設(shè)和歸納基礎(chǔ)，有<x,z>t(R)和

<z,y>t(R)，由此可得<x,y>t(R)，則Rn+1t(R)。由于對(duì)于所有的n1，均有Rnt(R)。因此

t(R)

再證t(R)

顯然R。只要再證是傳遞的即可。設(shè)任意<x,y>，<y,z>，則存在正整數(shù)s和k，使得<x,y>Rs,<y,z>Rk,這樣<x,z>Rs+k，因此有<x,z>，所以是傳遞的。由t(R)的最小性，得t(R)。36定理6.6

設(shè)R是集合A上的關(guān)系，A有n個(gè)元素，則

t(R)＝證明:只需證:對(duì)于任意k0，

Rn+k

例：設(shè)集合A＝｛a,b,c｝上的關(guān)系R＝{〈a,b〉,〈b,c〉,〈c,c〉}，求：r(R),s(R),t(R)。解r(R)＝R∪IA＝{〈a,b〉,〈b,c〉,〈c,c〉,〈a,a〉,〈b,b〉}S(R)＝R∪R－1＝｛〈a,b〉,〈b,c〉,〈c,c〉,〈b,a〉,〈c,b〉｝

R2＝｛〈a,c〉,〈b,c〉,〈c,c〉｝

R3=｛〈a,c〉,〈b,c〉,〈c,c〉｝=R2t(R)＝R∪R2＝｛〈a,b〉,〈b,c〉,〈c,c〉,〈a,c〉｝37例6.10設(shè)集合A＝｛a,b,c,d｝,A上的關(guān)系R＝｛〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉｝，試畫出t(R)關(guān)系圖。R關(guān)系圖abcdt(R)關(guān)系圖bacd38閉包的性質(zhì)性質(zhì)1設(shè)二元關(guān)系R1，R2

A2

且R1

R2，則i)r(R1)r(R2)；

s(R1)s(R2)；

t(R1)t(R2)。性質(zhì)2設(shè)二元關(guān)系RA2，i)若R是自反的，則s(R)和t(R)也是自反的；ii)若R是對(duì)稱的，則r(R)和t(R)也是對(duì)稱的；iii)若R是傳遞的，則r(R)也是傳遞的。性質(zhì)3設(shè)二元關(guān)系RA2，則

rs(R)=sr(R)；

rt(R)=tr(R)；

st(R)ts(R)。39§6.3

次序關(guān)系重點(diǎn):偏序關(guān)系畫哈斯圖求偏序集合中的特殊元素次序關(guān)系包括：偏序關(guān)系，全序關(guān)系，嚴(yán)格偏序關(guān)系，良序關(guān)系。40定義6.9（偏序關(guān)系）集合P上的關(guān)系R稱為P上的偏序關(guān)系，當(dāng)且僅當(dāng)R是自反的、反對(duì)稱的和傳遞的。例：〈N,≤〉,〈N,≥〉,〈P(A),〉,〈I+,|〉都是偏序結(jié)構(gòu)定義6.10（全序關(guān)系）設(shè)〈P,≤〉是一個(gè)偏序結(jié)構(gòu)，如果對(duì)于任意x，y∈P，或者x≤y，或者y≤x，則稱≤為P上的全序或線序，并稱〈P,≤〉為全序結(jié)構(gòu)

或鏈。即

(x)(y)(x∈P∧y∈Px≤y∨y≤x)

用“≤”表示偏序關(guān)系，并用〈P,≤〉表示偏序結(jié)構(gòu)。

如果x,y∈P且x≤y，則稱“x小于或等于y”或“x在y之前”。41對(duì)于偏序集合〈P,≤〉，x,y∈P，如果有x≤y或者y≤x，就說(shuō)P的元素x和y是可比的。例：〈N,≤〉,〈N,≥〉都是全序結(jié)構(gòu)。它們中的任意元素x和y都是可比的而〈P(A),〉,〈I+,|〉都不是全序結(jié)構(gòu)定義6.11（嚴(yán)格偏序關(guān)系，又稱擬序關(guān)系）R是集合P上的嚴(yán)格偏序關(guān)系，當(dāng)且僅當(dāng)R是反自反的和傳遞的。

用“＜”表示嚴(yán)格偏序關(guān)系，并稱“x小于y”，稱〈P,＜〉為嚴(yán)格偏序（擬序）結(jié)構(gòu)。42例〈N,＜〉,〈N,＞〉,〈P(A),〉都是嚴(yán)格偏序結(jié)構(gòu)證明若R是P上嚴(yán)格偏序關(guān)系，則R是反對(duì)稱的。證明：假設(shè)R不是反對(duì)稱的，則存在x,y∈P且x≠y，使得〈x,y〉∈R且〈y,x〉∈R因?yàn)镽是傳遞的，所以〈x,x〉∈R，這與R反自反矛盾。由上述證明可知，P上的嚴(yán)格偏序關(guān)系和偏序關(guān)系有如下關(guān)系：＜＝≤－IP

例如：x＜yx≤y∧x≠y

43

y遮蓋

xx＜y∧

z(z∈P∧x＜z∧z＜y)例:P＝｛1，2，3，4｝,≤是P上的小于或等于關(guān)系，則4遮蓋3，3遮蓋2，2遮蓋了1。若≤是P上的大于或等于關(guān)系，則上述遮蓋關(guān)系恰好相反哈斯圖：在偏序結(jié)構(gòu)〈P,≤〉中，對(duì)于任何兩個(gè)元素x,y∈P，如果x＜y且不存在任何其它元素z∈P，使得x＜z和z＜y，則稱y遮蓋（覆蓋）x。偏序結(jié)構(gòu)通常用簡(jiǎn)化的關(guān)系圖來(lái)表示，這種關(guān)系圖稱為偏序結(jié)構(gòu)圖或哈斯圖。44哈斯圖畫法如下：集合的每一個(gè)元素用一個(gè)點(diǎn)表示，對(duì)于x,y∈P，如果x＜y，則點(diǎn)x畫在點(diǎn)y之下，如果y遮蓋x，就在x和y之間畫一條直線，在哈斯圖中省略了自環(huán)，并約定弧的指向向上，不畫箭頭。例：畫出滿足下列條件的哈斯圖.⑴Pa＝｛1，2，3，4｝，并設(shè)≤是Pa上的小于或等于關(guān)系。1234｛a,b,c｝｛a,b｝｛a｝⑵Pb＝｛

,｛a｝,｛a,b｝,｛a,b,c}}，并設(shè)是Pb上的包含關(guān)系。解：見右圖解：見右圖45例：設(shè)X={2，3，6，12，24，36}，≤為整除關(guān)系，如果x整除y，便有x≤y.畫出〈X,≤〉的哈斯圖.336261224解：見右圖解：見右圖例設(shè)A={a，b，c},

是冪集(A)上的包含關(guān)系，畫出〈(A),〉的哈斯圖{a,b,c}{a,b}{a,c}{b,c}{a}{c}46⑴b是B的最大元b∈B∧x(x∈Bx≤b)⑷b是B的最大下界b是B的下界,且對(duì)B的任意下界x,都有x≤b。

偏序結(jié)構(gòu)中的特殊元素：定義6.12設(shè)〈A,≤〉是偏序結(jié)構(gòu)，并且BA，則⑵b是B的最小元b∈B∧x(x∈Bb≤x)⑶b是B的極大元b∈B∧x(x∈Bb＜x)⑷b是B的極小元b∈B∧x(x∈Bx＜b)

定義6.13設(shè)〈A,≤〉是偏序結(jié)構(gòu)，并且BA，則⑴b是B的上界b∈A∧x(x∈Bx≤b)⑵b是B的下界b∈A∧x(x∈Bb≤x)⑶b是B的最小上界b是B的上界,且對(duì)B的任意上界x,都有b≤x。47⑶若B是有窮集，則B的極大元、極小元必存在，但B的最大元、最小元不一定存在。例：設(shè)集合A＝｛1,2,3,4,5,6｝,≤關(guān)系是整除關(guān)系，畫出哈斯圖，并指出A的極大元、極小元、最大元、最小元、上界、下界、最小上界、最大下界.由上述定義可知：⑴B的最大元、最小元若存在，則唯一；⑵B的極大元、極小元若存在，不一定唯一；A的極大元：4,5,6極小元：1

最大元：無(wú)最小元：1

上界：無(wú)下界：1

最小上界：無(wú)最大下界：1

12364548定義6.14（良序結(jié)構(gòu)）：一個(gè)偏序結(jié)構(gòu)〈P,≤〉，如果P的每一個(gè)非空子集都有一個(gè)最小元，則稱≤為良序關(guān)系，〈P,≤〉為良序結(jié)構(gòu)。例〈N,≤〉是全序結(jié)構(gòu)，也是良序結(jié)構(gòu)；

〈I,≤〉是全序結(jié)構(gòu)，但不是良序結(jié)構(gòu)。（why？）

〈Q+,≤〉,〈R+

,≤〉是全序結(jié)構(gòu)，但都不是良序結(jié)構(gòu)。

（why？）由定義可知，每個(gè)良序結(jié)構(gòu)都是全序結(jié)構(gòu)（why？）但并非每個(gè)全序結(jié)構(gòu)都是良序的，當(dāng)然有窮的全序結(jié)構(gòu)一定是良序的。49良序的充要條件定理A若≤為集合P上的偏序關(guān)系，則≤為P上良序關(guān)系，當(dāng)且僅當(dāng)1）≤為P上的全序關(guān)系；2）P的每個(gè)非空子集都有極小元。定理B設(shè)〈A,≤〉為全序結(jié)構(gòu)，則〈A,≤〉是良序結(jié)構(gòu)的充要條件是：不存在A中元素的無(wú)窮序列a0,a1,a2,…,使得對(duì)每個(gè)iN，皆有ai+1<ai

。簡(jiǎn)而言之，就是：不存在A中元素的無(wú)窮遞降序列。

50§6.4等價(jià)關(guān)系與劃分例6.18設(shè)R是集合A=｛1,2,3,4,5,6,7｝上的關(guān)系，

R={〈x,y〉|x∈A∧y∈A∧3|(x－y)｝(模3同余關(guān)系)證明R是一個(gè)等價(jià)關(guān)系，并畫出其關(guān)系圖。

證明：略其關(guān)系圖如右圖所示，可見R的確是A上自反、對(duì)稱、傳遞的關(guān)系，故R是A上的等價(jià)關(guān)系。定義(等價(jià)關(guān)系)

如果集合A上的關(guān)系R是自反、對(duì)稱、傳遞的，則稱R為A上的等價(jià)關(guān)系。51例：設(shè)集合X是整數(shù)集合I的任意子集，證明：

X上的模m同余關(guān)系是等價(jià)關(guān)系。證明：自反性：對(duì)于任意xX，顯然xx(modm)。對(duì)稱性:對(duì)于任意x,yX,若xy(modm),則存在kI，使得x-y=k*m，故y-x=(-k)*m，因此yx(modm)。傳遞性:對(duì)于任意x,y,zX,若xy(modm),yz(modm),則存在k,nI使得x–y=k*m,y–z=n*m，于是有x–z=(k+n)*m，因此xz(modm)綜上所述，模m同余關(guān)系是等價(jià)關(guān)系?？梢宰C明:對(duì)于任意正整數(shù)m，模m同余關(guān)系是等價(jià)關(guān)系。若x和y有模m同余關(guān)系，一般記作xy(modm)52定義(等價(jià)類)設(shè)R是集合A上的等價(jià)關(guān)系。對(duì)于每個(gè)x∈A，A中與x有關(guān)系R的元素的集合稱為x關(guān)于R的等價(jià)類，簡(jiǎn)稱為x的等價(jià)類，記作[x]R，即:[x]R＝｛y｜y∈A∧x

Ry｝，顯然[x]R

A對(duì)上例給出的集合A=｛1,2,3,4,5,6,7｝上的關(guān)系R，A中各元素的等價(jià)類如下：[1]R=[4]R=[7]R=｛1,4,7｝[2]R=[5]R=｛2,5｝[3]R=[6]R=｛3,6｝53定理設(shè)R是非空集合A上的等價(jià)關(guān)系，則有：(1)對(duì)于每個(gè)x∈A，x[x]R

，即[x]R是A的非空子集。(2)[x]R

＝[y]R當(dāng)且僅當(dāng)xRy。(3)若x,y∈A且xy，則[x]R

[y]R=

。(4)[x]R

＝A,其中[x]R表示所有等價(jià)類的并集。證明：(1)因R自反，任取

x∈A均有xRx，故

x∈[x]R

，因此，[x]R。(2)設(shè)[x]R

＝[y]R，因?yàn)閥∈[y]R,所以y∈[x]R,由[x]R的定義，可得：xRy

。設(shè)xRy,任取

z∈[y]R,則有

yRz,因R傳遞,故xRz，因此z∈[x]R,故[y]R

[x]R

。因R對(duì)稱，所以有yRx，同理可證：[x]R

[y]R

。因此，[x]R=[y]R54（3）假設(shè)[x]R

[y]R

，則z使z∈[x]R

且z∈[y]R，即xRz，yRz，因R是對(duì)稱的，故zRy，因R是傳遞的，所以有xRy，這與xy的題設(shè)相矛盾！因此，[x]R

[y]R

。（4）任取

x∈A，則[x]R

A。所以有[x]R

A。任取

z∈A，有z∈[z]R，[z]R[x]R

，故有z∈[x]R

。因此，A

[x]R

，所以[x]R

＝A。55定義設(shè)A是非空集合,πρ(A)(即π包含

A的若干子集)。若π滿足以下三個(gè)條件，則稱π為A上的一個(gè)劃分:(1)對(duì)于每個(gè)S∈π，S≠；(2)對(duì)于任意B,C∈π，若B≠C，則BC＝；（若BC≠，則B＝C）(3)＝A。定義設(shè)R是集合A上的等價(jià)關(guān)系，所有等價(jià)類組成的集合稱為A關(guān)于R的商集，記作A/R，即:

A/R＝｛[x]R｜x∈A｝例：上例中集合A＝｛1,2,3,4,5,6,7｝關(guān)于其等價(jià)關(guān)系R的商集A/R＝｛{1,4,7},{2,5},{3,6}｝56例：設(shè)A＝｛a,b,c｝，給定下列A的子集的集合：B＝｛｛a｝,｛b,c｝｝C＝｛｛a,b,c｝｝D＝｛｛a｝,｛b｝,｛c｝｝E＝｛｛a,b｝,｛b,c｝｝F＝｛｛a｝,｛c｝｝G＝｛,｛a｝,｛b｝,｛c｝｝問(wèn)：這些集合中哪些是A上的劃分？把π中的元素稱為劃分塊，π中劃分塊的個(gè)數(shù)稱為秩,有有窮個(gè)劃分塊的劃分稱為有窮劃分,否則稱為確無(wú)窮劃分.57定理非空集合A上的等價(jià)關(guān)系R,決定了A上的一個(gè)劃分，這個(gè)劃分就是商集A/R。證明：根據(jù)商集定義A/R＝｛[x]R｜∈A｝、等價(jià)類的性質(zhì)定理和劃分的定義,商集A/R確是A上的一個(gè)劃分。定理設(shè)π是非空集合A上的一個(gè)劃分，若令：

Rπ

＝{〈x,y〉|存在S∈π使得x,y∈S｝即:xRπy當(dāng)且僅當(dāng)x和y在π的同一個(gè)劃分塊中，則Rπ必是A上的等價(jià)關(guān)系且

A／Rπ=π。稱Rπ

為由π確定的等價(jià)關(guān)系。證明：首先證明：

Rπ

具有自反性、對(duì)稱性、傳遞性。1）自反性:任取x∈A，由劃分的定義可知:存在S∈π使得x∈S。所以，x,x∈S，故有xRπx

。582）對(duì)稱性：設(shè)xRπy，于是存在S∈π使得x，y∈S，故有yRπx。3）傳遞性：設(shè)xRπy，yRπz，于是存在S∈π,T∈π使得x，y∈S且y，z∈T。由于π是劃分，則由S與T有公共元y

可知：ST≠，故必有S=T，因此z∈S，所以xRπz。因此，Rπ

是A上的等價(jià)關(guān)系。

然后證明：

A／Rπ=π:先證明πA／Rπ:

任取S∈π,存在x∈S，則必有S=[x]R（why?）由[x]R∈A／Rπ,因此

S∈A／Rπ。后證明

A／Rπ

π:

59任取[x]R

∈A／Rπ

，其中x∈A。因π為A上的一個(gè)劃分，則必有S∈π，使得x∈S，故必有S=[x]R

（why?）

因此，[x]R

∈π。由上述定理，可得如下結(jié)論：若A上的一個(gè)劃分為π={C1,C2,…,Cn}，則π確定的等價(jià)關(guān)系就是:Rπ=（C1

C1）（

C2

C2）

…

（Cn

Cn）60上述定理表明，由等價(jià)關(guān)系能夠產(chǎn)生一個(gè)劃分。同樣，由一個(gè)劃分也可以產(chǎn)生一個(gè)等價(jià)關(guān)系。例:UX,IX分別是X上的全域關(guān)系和恒等關(guān)系，則

X/UX={X}，X/IX={{x}xX}例:設(shè)R是N上的“模6同余”關(guān)系，即：R={<x,y>|xNyN

6|(x-y)

},求各元素的等價(jià)類和商集解：等價(jià)類是：[0]R={0，6，12，18，…，}={xx=6nnN}[1]R={1，7，13，19，…，}={xx=6n+1nN}…[5]R={5，11，17，23，…，}={xx=6n+5nN}61下接第七章例:X={a,b,c,d,e},劃分π={{a,b},{c},{d,e}},求劃分π確定的X上的等價(jià)關(guān)系R。解：R={<a,b>,<b,a>,<d,e>,<e,d>}IXN/R={[0]R，[1]R

，[2]R

，[3]R

，[4]R

，[5]R

}62思考題1)有人說(shuō)：“如果集合A上的二元關(guān)系R是對(duì)稱的和傳遞的，則R必是自反的”。并給出了如下的證明：如果<x,y>R，則由R是對(duì)稱的可知<y,x>R，從而由R是傳遞的得到<x,