集合論-第三章2

1、2.3 2.3 例題例題例例1 1 設(shè)設(shè)R R為為X X上的二元關(guān)系，顯然若上的二元關(guān)系，顯然若R R ，則，則R R是反自是反自反的、對(duì)稱和傳遞的；但若反的、對(duì)稱和傳遞的；但若RR 且且R R是反自反的和對(duì)是反自反的和對(duì)稱的，則稱的，則R R不是傳遞的。不是傳遞的。此題可變形為：此題可變形為： 若若RR 且且R R是反自反的和傳遞的是反自反的和傳遞的, ,則則R R是反對(duì)稱的。是反對(duì)稱的。例例2 2 設(shè)設(shè)R R是是X X上的二元關(guān)系，證明：上的二元關(guān)系，證明：R R對(duì)稱對(duì)稱R RR R-1-1。說(shuō)明說(shuō)明: :例中的結(jié)果還可以減弱為例中的結(jié)果還可以減弱為X X上的二元關(guān)系上的二元關(guān)系R R是對(duì)

2、是對(duì)稱當(dāng)且僅當(dāng)稱當(dāng)且僅當(dāng)R R R R-1-1。第二章第二章 習(xí)題課（習(xí)題課（1 1）例例1 1 設(shè)設(shè)X X a,b,ca,b,c ，給出，給出X X上的一個(gè)二元關(guān)系，使其同上的一個(gè)二元關(guān)系，使其同時(shí)時(shí)不滿足不滿足自反性、反自反性、對(duì)稱性、反對(duì)稱和傳遞自反性、反自反性、對(duì)稱性、反對(duì)稱和傳遞性的二元關(guān)系，并畫(huà)出性的二元關(guān)系，并畫(huà)出R R的關(guān)系圖。的關(guān)系圖。例例2 2 設(shè)設(shè)A A是集合，是集合，R,SR,SX XX X且且R,SR,S都是傳遞的，則都是傳遞的，則 (1) RS(1) RS是否傳遞的？是否傳遞的？ (2) RS(2) RS是否是不傳遞的？是否是不傳遞的？ 不一定是傳遞的不一定是傳遞的

3、; ; 不一定不傳遞的（有可能傳遞）不一定不傳遞的（有可能傳遞） 例例3 3 設(shè)有集合設(shè)有集合X X，|X|=3,|X|=3,求求X X上具有上具有反自反且反對(duì)稱性反自反且反對(duì)稱性的的二元關(guān)系的數(shù)目，并寫(xiě)出計(jì)算過(guò)程。二元關(guān)系的數(shù)目，并寫(xiě)出計(jì)算過(guò)程。 若若|X|=n|X|=n，結(jié)果又如何？，結(jié)果又如何？ |X|=3,27; |X|=n, 3 |X|=3,27; |X|=n, 3(n(n2 2-n)/2-n)/2 例例4 4 設(shè)設(shè)X X是一個(gè)集合，是一個(gè)集合，|X|X|n n，求：，求： (1) X(1) X上的二元關(guān)系有多少？上的二元關(guān)系有多少？ (2) (2) X X上的自反的二元關(guān)系有多少？

4、上的自反的二元關(guān)系有多少？ (3) X(3) X上的反自反的二元關(guān)系有多少？上的反自反的二元關(guān)系有多少？ (1)2(1)2n2 n2 (2)(2)、(3)(3)自反與反自反一樣多自反與反自反一樣多2 2n2-nn2-n (4) (4) X X上的對(duì)稱的二元關(guān)系有多少？上的對(duì)稱的二元關(guān)系有多少？ (5) X(5) X上的反對(duì)稱的二元關(guān)系有多少？上的反對(duì)稱的二元關(guān)系有多少？ (4)(4) 2 2(n2+n)/2 (n2+n)/2 (5)(5) 3 3(n2-n)/2(n2-n)/22 2n n (6) X (6) X上上既是既是自反的自反的又是又是反自反的關(guān)系有多少？反自反的關(guān)系有多少？ (7)

5、X(7) X上既不是自反的也不是反自反的關(guān)系有多少？上既不是自反的也不是反自反的關(guān)系有多少？ (6)0 ,(7)(6)0 ,(7) |B|BC CCCC C|=|S|-|A|=|S|-|AB|=2|=2n2-nn2-n(2(2n n-2)-2) (8) X (8) X上自反的且對(duì)稱的關(guān)系有多少？上自反的且對(duì)稱的關(guān)系有多少？ 與與“反自反且對(duì)稱關(guān)系有多少？反自反且對(duì)稱關(guān)系有多少？”一樣多一樣多2 2(n2-n)/2(n2-n)/2 (9) X(9) X上自反的或?qū)ΨQ的關(guān)系有多少？上自反的或?qū)ΨQ的關(guān)系有多少？ |BC|=2|BC|=2n2-nn2-n+2+2(n2+n)/2(n2+n)/2-2-2

6、(n2-n)/2(n2-n)/2 (10)X (10)X上反自反的上反自反的且且反對(duì)稱的關(guān)系有多少？反對(duì)稱的關(guān)系有多少？ (11)X(11)X上上既是既是對(duì)稱的對(duì)稱的也是也是反對(duì)稱的關(guān)系有多少？反對(duì)稱的關(guān)系有多少？ (10) 3(10) 3(n2-n)/2(n2-n)/2 (11) R(11) RI IX X，2 2n n (12)X(12)X上既不是對(duì)稱的也不是反對(duì)稱的關(guān)系有多少？上既不是對(duì)稱的也不是反對(duì)稱的關(guān)系有多少？ |B|BC CCCC C|=|S|-|B|=|S|-|BC|=2|=2n2n2-2-2(n2+n)/2(n2+n)/2-3-3(n2-n)/2(n2-n)/22 2n n+

7、2+2n n例例5 5 設(shè)設(shè) A=1,2,3A=1,2,3，R R是是A A的冪集的冪集2 2A A上的二元關(guān)系且上的二元關(guān)系且 R=(R=(a,b)|aa,b)|ab b ，則，則R R不滿足下列哪些性質(zhì)？不滿足下列哪些性質(zhì)？為什么？為什么？ aRbaRb a ab b (1) (1) 自反性自反性 (2) (2) 反自反性反自反性 (3) (3) 對(duì)稱性對(duì)稱性 (4) (4) 反對(duì)稱性反對(duì)稱性 (5) (5) 傳遞性傳遞性 不滿足自反性、反自反性、反對(duì)稱性、傳遞性不滿足自反性、反自反性、反對(duì)稱性、傳遞性 例例6 6 設(shè)設(shè)R R是復(fù)數(shù)集合是復(fù)數(shù)集合C C上的一個(gè)二元關(guān)系且滿足上的一個(gè)二元關(guān)系

8、且滿足xRyxRyx-yx-y= =a+bia+bi，a,ba,b為非負(fù)整數(shù)，試確定為非負(fù)整數(shù)，試確定R R的性質(zhì)。的性質(zhì)。若若a=b=0a=b=0時(shí)，時(shí)，R=I(R=I(恒等關(guān)系恒等關(guān)系) )，滿足滿足自反性、對(duì)稱、反自反性、對(duì)稱、反對(duì)稱性、傳遞性對(duì)稱性、傳遞性若若a a、b b不全為零不全為零0 0時(shí)，時(shí)，滿足反滿足反自反性、反對(duì)稱性自反性、反對(duì)稱性5 5 關(guān)系矩陣和關(guān)系圖關(guān)系矩陣和關(guān)系圖 前面介紹過(guò)的關(guān)系都是用集合表達(dá)式來(lái)定義的，前面介紹過(guò)的關(guān)系都是用集合表達(dá)式來(lái)定義的，對(duì)于有限集合上的關(guān)系還可以用關(guān)系矩陣和關(guān)系圖的對(duì)于有限集合上的關(guān)系還可以用關(guān)系矩陣和關(guān)系圖的方法給出，這兩種方法形象、

9、直觀，不僅對(duì)分析關(guān)系方法給出，這兩種方法形象、直觀，不僅對(duì)分析關(guān)系性質(zhì)有很大的方便，而且也有利于用計(jì)算來(lái)處理有關(guān)性質(zhì)有很大的方便，而且也有利于用計(jì)算來(lái)處理有關(guān)問(wèn)題。問(wèn)題。5.15.1關(guān)系矩陣關(guān)系矩陣定義定義1 1 設(shè)設(shè)A A、B B為有限集合為有限集合,A=a,A=a1 1,a,a2 2, ,a,an n, B=b B=b1 1,b,b2 2, , ,b bm m , ,則則 (1) (1) 若若R R是從是從A A到到B B的二元關(guān)系，則的二元關(guān)系，則n nm m矩陣矩陣M MR R=(=(r rijij) )n nm m稱為稱為A A到到B B的二元關(guān)系的二元關(guān)系R R的關(guān)系矩陣，簡(jiǎn)稱的關(guān)

10、系矩陣，簡(jiǎn)稱關(guān)系矩陣。其中關(guān)系矩陣。其中1 ( ,) 1,2, ;1,2,3,0 ( ,)ijijija bRrin jma bR當(dāng)當(dāng)(2) (2) 若若R R是是A A上的關(guān)系，則上的關(guān)系，則n nn n矩陣稱為矩陣稱為A A上的二元關(guān)系上的二元關(guān)系R R的關(guān)系矩陣，簡(jiǎn)稱關(guān)系矩陣，其中：的關(guān)系矩陣，簡(jiǎn)稱關(guān)系矩陣，其中：二、例題二、例題例例1 設(shè)設(shè)A=a1,a2,a3,a4，B=b1,b2,b3。A到到B的二元關(guān)系的二元關(guān)系R=(a1,b1),(a1,b3),(a2,b3),(a4,b2)，則，則R的關(guān)系矩陣為：的關(guān)系矩陣為：例例2 設(shè)設(shè)A=1,2,3,4,，集合，集合A上的大于關(guān)系上的大于關(guān)

11、系“”定義為：定義為： =(2,1),(3,1),(4,1),(3,2),(4,2),(4,3)，則關(guān)系則關(guān)系“”的關(guān)系矩陣為的關(guān)系矩陣為：101001000010RM0000100011001110M1 (,) ( ,1, 2,)0 (,)ijijijaaRri jnaaR當(dāng)當(dāng)三、關(guān)系矩陣包含關(guān)系的信息三、關(guān)系矩陣包含關(guān)系的信息 設(shè)設(shè)M MR R是關(guān)系是關(guān)系R R的關(guān)系矩陣，則的關(guān)系矩陣，則 (1) R(1) R是自反的是自反的M MR R的對(duì)稱線上的元素全為的對(duì)稱線上的元素全為1 1。 (2) R(2) R是反自反的是反自反的M MR R對(duì)稱線上的元素全為對(duì)稱線上的元素全為0 0。 (3)

12、 R(3) R是對(duì)稱的是對(duì)稱的MRMR是對(duì)稱的。是對(duì)稱的。 (4) R(4) R是反對(duì)稱的是反對(duì)稱的若若ijij, ,則則r rijij與與r rjiji不能同時(shí)為不能同時(shí)為1 1。 或或r rijij+r+rjiji1 (5) R (5) R是傳遞的是傳遞的若若r rijij1 1且且r rjkjk1 1，則，則r rikik1 1。 或或M MR RM MR RMMR R，即，即R RR RR R (6) R (6) R-1-1的關(guān)系矩陣為的關(guān)系矩陣為M MR RT T。5.25.2關(guān)系圖關(guān)系圖定義定義1 1 設(shè)設(shè)A A，B B為有限集合，為有限集合，A=aA=a1 1,a,a2 2, ,

13、a,an n, , B=bB=b1 1,b,b2 2, , ,b bm m,R,R是是A A到到B B的一個(gè)二元關(guān)系。的一個(gè)二元關(guān)系。 首先在平面上用首先在平面上用n n個(gè)小圓點(diǎn)代表個(gè)小圓點(diǎn)代表A A中的中的n n個(gè)元素，個(gè)元素，并在這些點(diǎn)的旁邊標(biāo)上并在這些點(diǎn)的旁邊標(biāo)上a a1 1,a,a2 2, ,a,an n ；然后用另外；然后用另外m m個(gè)個(gè)小圓點(diǎn)代表小圓點(diǎn)代表B B中的中的m m個(gè)元素，并在這些點(diǎn)旁邊標(biāo)上個(gè)元素，并在這些點(diǎn)旁邊標(biāo)上b b1 1,b,b2 2, , ,b bm m 。于是有：。于是有： 若若( (a ai i,b,bj j) )R R，則在頂點(diǎn)，則在頂點(diǎn)a ai i到作一

14、條帶箭頭的線到作一條帶箭頭的線指向頂點(diǎn)指向頂點(diǎn)b bj j ； 若若( (a ai i,b,bj j) ) R R ，則，則a ai i與與b bj j之間沒(méi)有線聯(lián)結(jié)。之間沒(méi)有線聯(lián)結(jié)。 用這種方法構(gòu)造的圖形稱為用這種方法構(gòu)造的圖形稱為A A到到B B的關(guān)系的關(guān)系R R的關(guān)系的關(guān)系圖，簡(jiǎn)稱關(guān)系圖。圖，簡(jiǎn)稱關(guān)系圖。 當(dāng)當(dāng)A AB B時(shí)時(shí)，A A上的關(guān)系上的關(guān)系R R的關(guān)系圖畫(huà)法類似。把的關(guān)系圖畫(huà)法類似。把A A中的中的每一個(gè)元素在平面上用點(diǎn)表示，并在這些點(diǎn)旁邊標(biāo)上每一個(gè)元素在平面上用點(diǎn)表示，并在這些點(diǎn)旁邊標(biāo)上元素的名字。元素的名字。 若若( (a ai i,b,bj j) )R R，則從代表，則從

15、代表a ai i的點(diǎn)的點(diǎn)畫(huà)畫(huà)一條帶箭頭的一條帶箭頭的線指向代表線指向代表a aj j的點(diǎn)。的點(diǎn)。 若若( (a ai i,a,ai i) )R R, ,則從頂點(diǎn)則從頂點(diǎn)a ai i也畫(huà)一條指向自己的矢也畫(huà)一條指向自己的矢線，稱為環(huán)。線，稱為環(huán)。 這樣得到的圖形稱為這樣得到的圖形稱為A A上的關(guān)系上的關(guān)系R R的關(guān)系圖，簡(jiǎn)稱的關(guān)系圖，簡(jiǎn)稱關(guān)系圖。關(guān)系圖。說(shuō)明：說(shuō)明：為了使圖形直觀，易于理解，通常把為了使圖形直觀，易于理解，通常把A A中元素中元素a a1 1,a,a2 2, ,a,an n畫(huà)在左邊，而把畫(huà)在左邊，而把B B中元素中元素b b1 1,b,b2 2, , ,b bm m畫(huà)在畫(huà)在右邊。

16、右邊。2.2.例例(1)(1)設(shè)設(shè)A=1,2,3,4,B=A=1,2,3,4,B=a,b,ca,b,c ，A A到到B B的二元關(guān)系的二元關(guān)系 R=(1,a),(2,a),(4,a),(3,b),(3,c)R=(1,a),(2,a),(4,a),(3,b),(3,c)，則，則R R的關(guān)系圖的關(guān)系圖如圖如圖1 1所示。所示。 (2) (2) 設(shè)設(shè)A=1,2,3,4A=1,2,3,4，則在，則在A A上的整除關(guān)系上的整除關(guān)系R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(

17、3,3),(4,4)，則則R R的關(guān)系圖如圖的關(guān)系圖如圖2 2所示。所示。 圖圖1 圖圖21234cba1234二、關(guān)系圖包含關(guān)系的所有信息二、關(guān)系圖包含關(guān)系的所有信息(1) R(1) R是自反的是自反的 R R的關(guān)系圖的每個(gè)頂點(diǎn)都有一個(gè)環(huán)。的關(guān)系圖的每個(gè)頂點(diǎn)都有一個(gè)環(huán)。(2) R(2) R是反自反的是反自反的 R R的關(guān)系圖的每個(gè)頂點(diǎn)都沒(méi)有環(huán)。的關(guān)系圖的每個(gè)頂點(diǎn)都沒(méi)有環(huán)。(3) R(3) R是對(duì)稱的是對(duì)稱的在在R R的關(guān)系圖中，若兩個(gè)不同的頂點(diǎn)的關(guān)系圖中，若兩個(gè)不同的頂點(diǎn)間有弧，則必有方向相反的兩條?。▽?duì)稱弧）。間有弧，則必有方向相反的兩條?。▽?duì)稱弧）。(4) R(4) R是反對(duì)稱是反對(duì)稱在

18、在R R的關(guān)系圖中，若兩個(gè)不同的頂點(diǎn)的關(guān)系圖中，若兩個(gè)不同的頂點(diǎn)之間有弧，則弧只有一條。之間有弧，則弧只有一條。(5) R(5) R是傳遞的是傳遞的在在R R的關(guān)系圖中，任意從某點(diǎn)沿箭頭的關(guān)系圖中，任意從某點(diǎn)沿箭頭所指的方向經(jīng)過(guò)二步走到另一點(diǎn)，則從該點(diǎn)必能一步所指的方向經(jīng)過(guò)二步走到另一點(diǎn)，則從該點(diǎn)必能一步走到另一點(diǎn)。走到另一點(diǎn)。5.3 5.3 閉包的運(yùn)算閉包的運(yùn)算 用矩陣方法計(jì)算閉包用矩陣方法計(jì)算閉包 一、布爾矩陣的運(yùn)算一、布爾矩陣的運(yùn)算 在關(guān)系矩陣在關(guān)系矩陣M MR R中，中，r rijij的值不是的值不是0 0就是就是1 1，這種矩陣，這種矩陣稱為布爾矩陣。把關(guān)系用對(duì)應(yīng)的稱為布爾矩陣。把關(guān)

19、系用對(duì)應(yīng)的布爾矩陣布爾矩陣表示，而布表示，而布爾矩陣是代數(shù)所研究的對(duì)象，因此便于進(jìn)行爾矩陣是代數(shù)所研究的對(duì)象，因此便于進(jìn)行代數(shù)處理代數(shù)處理。特別是矩陣間可以進(jìn)行特別是矩陣間可以進(jìn)行代數(shù)運(yùn)算代數(shù)運(yùn)算，這有利于計(jì)算機(jī)的，這有利于計(jì)算機(jī)的存儲(chǔ)處理，下面介紹布爾矩陣間的若干運(yùn)算。存儲(chǔ)處理，下面介紹布爾矩陣間的若干運(yùn)算。定義定義1 1 設(shè)設(shè)M MR R,M,MS S是兩個(gè)是兩個(gè)階的布爾矩陣，則階的布爾矩陣，則（1 1）把）把M MR R和和M MS S的對(duì)應(yīng)元素的的對(duì)應(yīng)元素的“邏輯和邏輯和”所形成的矩所形成的矩陣稱為陣稱為M MR R與與M MS S的的邏輯和邏輯和，記為，記為M MR RM MS S。

20、即。即 M MR RM MS S=(=(r rijijssijij) )。其中，其中，0 00=0,00=0,01=11=10=10=11 1。 運(yùn)算是取最大運(yùn)算是取最大 （1 1）把）把M MR R和和M MS S的對(duì)應(yīng)元素的的對(duì)應(yīng)元素的“邏輯乘邏輯乘”所形成的矩所形成的矩陣稱為陣稱為M MR R與與MSMS的的邏輯乘邏輯乘 ，記為，記為M MR RM MS S。即。即 M MR RM MS S=(=(r rijijs sijij) )。其中其中,0,00=00=01=11=10=0,10=0,11=11=1運(yùn)算是取最小運(yùn)算是取最小 （3 3）設(shè)）設(shè)M MR R是是n np p，M MS S

21、是是p pm m階的布爾矩陣，定義階的布爾矩陣，定義M MR R與與M MS S的的“布爾乘法布爾乘法”運(yùn)算運(yùn)算“”,”,令令M MR RM MS S=M=MT T=(=(t tijij) )nmnm，則則“”“”運(yùn)算是先取最小，再取最大運(yùn)算是先取最小，再取最大 11221()()()(),1,2,;1,2,ijijijippjpikkjktrsrsrsrsin jm 二、求二、求RSRS，RSRS，RSRS關(guān)系矩陣關(guān)系矩陣(1)M(1)MRSRS= M= MR RM MS S；(2)M(2)MRSRS= M= MR RM MS S；(3)M(3)MRSRS= M= MR RMMS S。三、閉

22、包的運(yùn)算三、閉包的運(yùn)算(1)M(1)Mr(R)r(R)=M=MR RM MI I； r(Rr(R)=RI)=RI(2)M(2)Ms(R)s(R)=M=MR RM MR RT T； s(Rs(R)=RR)=RR-1-1(3)M(3)MR+R+= =M Mt(Rt(R) )=M=MR RM MR R2 2M MR Rn n。 R R+ += =t(Rt(R)=RR)=RR2 2R Rn n 6 6 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分 內(nèi)容：等價(jià)關(guān)系、等價(jià)類、劃分、等價(jià)關(guān)系與劃分的關(guān)系內(nèi)容：等價(jià)關(guān)系、等價(jià)類、劃分、等價(jià)關(guān)系與劃分的關(guān)系6.1 6.1 等價(jià)關(guān)系等價(jià)關(guān)系一、定義一、定義定義定義1 1 設(shè)設(shè)R

23、R是非空集合是非空集合A A上的二元關(guān)系，若上的二元關(guān)系，若R R同時(shí)具有同時(shí)具有以下三個(gè)性質(zhì)：以下三個(gè)性質(zhì)： (1)R(1)R是自反的；是自反的；(2)R(2)R是對(duì)稱的；是對(duì)稱的；(3)R(3)R是傳遞的。是傳遞的。則稱則稱R R是是A A上的等價(jià)關(guān)系，記為上的等價(jià)關(guān)系，記為“”。 R R是等價(jià)關(guān)系是等價(jià)關(guān)系二、例：二、例：12,AIR RRRR二、例：二、例：1.1.平面上三角形集合中，三角形的相似關(guān)系，全等關(guān)平面上三角形集合中，三角形的相似關(guān)系，全等關(guān)系都是等價(jià)關(guān)系。系都是等價(jià)關(guān)系。2.2.實(shí)數(shù)集上實(shí)數(shù)集上n n階方陣集合中，矩陣的相似、正交關(guān)系階方陣集合中，矩陣的相似、正交關(guān)系也是等

24、價(jià)關(guān)系。也是等價(jià)關(guān)系。3.3.恒等關(guān)系和全關(guān)系是等價(jià)關(guān)系。恒等關(guān)系和全關(guān)系是等價(jià)關(guān)系。4. 4. 定義在人的集合上的定義在人的集合上的 “年齡相等年齡相等”是等價(jià)關(guān)系，是等價(jià)關(guān)系，但但“相互認(rèn)識(shí)相互認(rèn)識(shí)”、“同學(xué)同學(xué)”、 “朋友朋友”關(guān)系都不是關(guān)系都不是等價(jià)關(guān)系。等價(jià)關(guān)系。5.5.整數(shù)整數(shù)Z Z上的上的“相等相等”、“模模n n同余同余”關(guān)系都是等價(jià)關(guān)關(guān)系都是等價(jià)關(guān)系。系。 設(shè)設(shè)X=1,2,X=1,2,7,8,7,8，R=(R=(x,y)|x,yXx,y)|x,yX且且x=y(mod3)x=y(mod3)，其中其中x=y(mod3) x=y(mod3) 表示表示x-yx-y可以被可以被3 3整

25、除，稱整除，稱R R為為X X上的模上的模3 3同余關(guān)系，則同余關(guān)系，則R R是是X X上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。6.2 6.2 等價(jià)類等價(jià)類一、定義一、定義定義定義2 2 設(shè)設(shè)R R是非空集合是非空集合A A上的一個(gè)等價(jià)關(guān)系，上的一個(gè)等價(jià)關(guān)系，XX，令令 xxR R=y|yXy|yX且且( (x,y)Rx,y)R 則稱集合則稱集合 xxR R為為x x關(guān)于關(guān)于R R的等價(jià)類，簡(jiǎn)稱的等價(jià)類，簡(jiǎn)稱x x的等價(jià)類，簡(jiǎn)的等價(jià)類，簡(jiǎn)記為記為xx。例：例：在上例中的等價(jià)關(guān)系在上例中的等價(jià)關(guān)系R R的三個(gè)不同等價(jià)類為：的三個(gè)不同等價(jià)類為：二、說(shuō)明：二、說(shuō)明：1.1.集合集合X X中的八個(gè)元素各有一個(gè)等價(jià)

26、類中的八個(gè)元素各有一個(gè)等價(jià)類; ; 2. 2. 各個(gè)等價(jià)類之間或者相等或者不相交各個(gè)等價(jià)類之間或者相等或者不相交; ; 3. 3. 所有等價(jià)類的并就等于所有等價(jià)類的并就等于X X。11,4,74722,5,85833,66RRRRRRRR三、性質(zhì)三、性質(zhì)定理定理1 1 設(shè)設(shè)R R是非空集合是非空集合X X上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，XX ，則，則(1)(1) xxR R且且 xxR RX X; ;(2) (2) 若若( (R R, ,則則 xxR R=yyR R; ; (3) (3) 若若( ( R R, , 則則 xxR RyyR R=;=;(4) (4) xxR R=X=X。6.3 6.3

27、 商集商集定義定義3 3 設(shè)設(shè)R R是非空集合是非空集合X X上的一個(gè)等價(jià)關(guān)系，以上的一個(gè)等價(jià)關(guān)系，以R R的不相的不相交的等價(jià)類為元素構(gòu)成的集合稱為交的等價(jià)類為元素構(gòu)成的集合稱為X X在在R R下的商集，下的商集，簡(jiǎn)稱為簡(jiǎn)稱為X X的商集，記為的商集，記為X/RX/R，即，即X/R=X/R=xxR R|xX|xX 。例：例：1.1.在上例中，在上例中，X X在在R R下的商集是：下的商集是： X/R=1,2,3=1,4,7,2,5,8,3,6X/R=1,2,3=1,4,7,2,5,8,3,6。2.2.非空集合非空集合X X上的全關(guān)系上的全關(guān)系E EX X是是X X上的等價(jià)關(guān)系上的等價(jià)關(guān)系,

28、,XX, ,有有 xxE E=X, =X, 商集商集 X/E=XX/E=X。3. X3. X上的恒等關(guān)系上的恒等關(guān)系I IX X是等價(jià)關(guān)系，是等價(jià)關(guān)系，XX, ,有有 xxI IX X=x,=x, 商集商集X/I=X/I=xxI I| | XX = =x|x| XX 。6.4 6.4 劃分劃分一、定義一、定義定義定義4 4 設(shè)設(shè)X X是非空集合，若是非空集合，若X X的一些非空子集形成的集的一些非空子集形成的集族族=A Ai i iIiI滿足下列條件：滿足下列條件： (1) (1) I I，若，若lrlr, , 則則A Al lArAr=;=; (2) A (2) Ai i=X=X。 則稱則稱

29、為為X X的一個(gè)劃分，的一個(gè)劃分，中元素中元素A Ai i為為的劃分塊。的劃分塊。二、說(shuō)明：二、說(shuō)明：(1)(1)集合集合A A的商集就是集合的商集就是集合A A的一個(gè)劃分；的一個(gè)劃分；(2)(2)當(dāng)劃分塊的塊數(shù)有限時(shí)，將劃分當(dāng)劃分塊的塊數(shù)有限時(shí)，將劃分寫(xiě)成：寫(xiě)成： =1 1 , ,2 2, , , n n ，n n為塊數(shù)。為塊數(shù)。 顯然，對(duì)于有限集合來(lái)說(shuō)，它的劃分塊數(shù)一定是顯然，對(duì)于有限集合來(lái)說(shuō)，它的劃分塊數(shù)一定是有限的。有限的。(3)(3)但對(duì)無(wú)限集合劃分塊數(shù)不一定有限。但對(duì)無(wú)限集合劃分塊數(shù)不一定有限。 例：例：1.1.給定整數(shù)集合給定整數(shù)集合Z Z的一個(gè)劃分：的一個(gè)劃分： 1 1=E,O

30、,=E,O,其中其中E E是偶數(shù)集，是偶數(shù)集，O O是奇數(shù)集是奇數(shù)集; ; I I的另外劃分的另外劃分: : 2 2=Z=Z+ +,Z,Z- -,0;,0; 3 3=,-2,-1,0,1,2,-2,-1,0,1,2, 等等。等等。2. 2. 考慮集合考慮集合A=A=a,b,c,da,b,c,d 上的子集族：上的子集族： 1 1=a,b,c,da,b,c,d; 2 2=a,b,c,da,b,c,d; 3 3=a,b,c,da,b,c,d都是都是A A上的劃分。上的劃分。 a,b,c,da,b,c,d 都是都是1 1的劃分塊；的劃分塊； a,ba,b 、 c,dc,d 和和 a,b,c,da,b,

31、c,d 分別是分別是2 2和和3 3的劃的劃分塊。分塊。 4 4=a,b,c,a,da,b,c,a,d 5 5=a,b,da,b,d等都不是等都不是A A的劃分。的劃分。6.5 6.5 等價(jià)關(guān)系與劃分之間的聯(lián)系等價(jià)關(guān)系與劃分之間的聯(lián)系 它們之間的關(guān)系可以用三個(gè)定理來(lái)說(shuō)明。它們之間的關(guān)系可以用三個(gè)定理來(lái)說(shuō)明。定理定理1 1 對(duì)非空集合對(duì)非空集合X X上的任意一個(gè)等價(jià)關(guān)系上的任意一個(gè)等價(jià)關(guān)系R R，X X的商的商集集X/RX/R就是就是X X的劃分。的劃分。 這個(gè)劃分稱為由等價(jià)關(guān)系這個(gè)劃分稱為由等價(jià)關(guān)系R R誘導(dǎo)出來(lái)的誘導(dǎo)出來(lái)的X X的劃分，的劃分，記為記為R R。說(shuō)明：說(shuō)明：X X上的等價(jià)關(guān)系上

32、的等價(jià)關(guān)系R R可以誘導(dǎo)出可以誘導(dǎo)出X X上的一個(gè)劃分，上的一個(gè)劃分，那么給定那么給定X X上的一個(gè)劃分是否可以誘導(dǎo)出上的一個(gè)劃分是否可以誘導(dǎo)出X X上的一個(gè)等上的一個(gè)等價(jià)關(guān)系呢？?jī)r(jià)關(guān)系呢？定理定理2 2 設(shè)設(shè)是非空集合是非空集合X X上的一個(gè)劃分，令上的一個(gè)劃分，令X X上的關(guān)系上的關(guān)系為為R R如下：如下： R R=(=(x,y)|x,yXx,y)|x,yX且且x x和和y y屬于的同一個(gè)屬于的同一個(gè)劃分塊劃分塊, ,則則R R為為X X上的等價(jià)關(guān)系。這個(gè)等價(jià)關(guān)系稱為上的等價(jià)關(guān)系。這個(gè)等價(jià)關(guān)系稱為由劃分由劃分誘導(dǎo)出的誘導(dǎo)出的X X上的等價(jià)關(guān)系。并且上的等價(jià)關(guān)系。并且 R R= =i ii

33、i，i i。定理定理3 3 對(duì)非空集合對(duì)非空集合X X上的一個(gè)劃分上的一個(gè)劃分和和X X上的一個(gè)等價(jià)上的一個(gè)等價(jià)關(guān)系關(guān)系R R，有，有: : 誘導(dǎo)誘導(dǎo)R RR R誘導(dǎo)誘導(dǎo)。說(shuō)明：說(shuō)明：集合集合X X上的劃分上的劃分和和X X上的等價(jià)關(guān)系上的等價(jià)關(guān)系R R之間可以建之間可以建立一一對(duì)應(yīng)關(guān)系。立一一對(duì)應(yīng)關(guān)系。二、例題：二、例題：例例1 1 在集合在集合X=1,2,3X=1,2,3上求出盡可能多的等價(jià)關(guān)系。上求出盡可能多的等價(jià)關(guān)系。 推廣：推廣：X=1,2,3,4,|R|=15X=1,2,3,4,|R|=15個(gè)；個(gè)； X=1,2,3,4,5,|R|=52X=1,2,3,4,5,|R|=52個(gè)個(gè). .

34、例例2 2 給定集合給定集合X=1,2,3,4,5X=1,2,3,4,5，找出，找出X X上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，此關(guān)系此關(guān)系R R能產(chǎn)生劃分能產(chǎn)生劃分1,2,3,4,51,2,3,4,5，并畫(huà)出關(guān)系圖。，并畫(huà)出關(guān)系圖。 對(duì)上述三個(gè)定理的說(shuō)明：對(duì)上述三個(gè)定理的說(shuō)明： 1.1.集合集合X X上的任一等價(jià)關(guān)系可以唯一地誘導(dǎo)出上的任一等價(jià)關(guān)系可以唯一地誘導(dǎo)出X X上的上的一個(gè)劃分；一個(gè)劃分； 2.2.集合集合X X上的任一劃分可以唯一地誘導(dǎo)出上的任一劃分可以唯一地誘導(dǎo)出X X上的一個(gè)上的一個(gè)等價(jià)關(guān)系。等價(jià)關(guān)系。 3.X3.X上給出的一個(gè)劃分與給出的一個(gè)等價(jià)關(guān)系是沒(méi)上給出的一個(gè)劃分與給出的一個(gè)等價(jià)

35、關(guān)系是沒(méi)有什么實(shí)質(zhì)區(qū)別的。有什么實(shí)質(zhì)區(qū)別的。 對(duì)于一個(gè)問(wèn)題中的某個(gè)關(guān)系對(duì)于一個(gè)問(wèn)題中的某個(gè)關(guān)系R R可能不是等價(jià)關(guān)系。可能不是等價(jià)關(guān)系。如果如果R R很重要，希望它是一個(gè)等價(jià)關(guān)系就好了，那么很重要，希望它是一個(gè)等價(jià)關(guān)系就好了，那么可以用可以用R R的等價(jià)閉包（的等價(jià)閉包（R R的自反、對(duì)稱和傳遞閉包），的自反、對(duì)稱和傳遞閉包），記為記為e(Re(R) )。e(Re(R) )是是X X上包含上包含R R的所有等價(jià)關(guān)系的交。的所有等價(jià)關(guān)系的交。習(xí)題課（習(xí)題課（3 3） 例例1 1 在集合在集合A=1,2,3A=1,2,3上求出盡可能多的等價(jià)關(guān)系。上求出盡可能多的等價(jià)關(guān)系。推廣：推廣：A=1,2,3

36、,4, |R|=15A=1,2,3,4, |R|=15個(gè)；個(gè)； A=1,2,3,4,5,|R|=52A=1,2,3,4,5,|R|=52個(gè)。個(gè)。例例2 2 給定集合給定集合 A=1,2,3,4,5A=1,2,3,4,5，找出，找出A A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，此關(guān)系此關(guān)系R R能產(chǎn)生劃分能產(chǎn)生劃分1,21,2，33，4,54,5，并畫(huà)出關(guān)系，并畫(huà)出關(guān)系圖。圖。習(xí)題課（習(xí)題課（4 4） 例例1 1 R R是整數(shù)集是整數(shù)集I I上的關(guān)系，上的關(guān)系，mRnmRn定義為定義為m m2 2n n2 2，則，則 (1) (1) 證明：證明：R R是等價(jià)關(guān)系；是等價(jià)關(guān)系；(2) (2) 確定確定R R的

37、等價(jià)類。的等價(jià)類。例例2 2設(shè)設(shè)R R是是A A上的一個(gè)自反關(guān)系，證明：上的一個(gè)自反關(guān)系，證明： R R是等價(jià)關(guān)系是等價(jià)關(guān)系若若( (R R且且( (a aR R, ,則則( (b bR R 。例例3 3 設(shè)設(shè)A=1,2,3A=1,2,3，A A上的兩個(gè)關(guān)系如圖所示，則它們上的兩個(gè)關(guān)系如圖所示，則它們是否是等價(jià)關(guān)系？是否是等價(jià)關(guān)系？例例4 4 設(shè)設(shè)R R1 1,R,R2 2是是A A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, ,則則R R1 1RR2 2也是也是A A上的等上的等價(jià)關(guān)系嗎？?jī)r(jià)關(guān)系嗎？132231例例5 5 設(shè)設(shè)R R是集合是集合A A上的一個(gè)自反的和傳遞的關(guān)系；上的一個(gè)自反的和傳遞的關(guān)系； S

38、 S是是A A上的一個(gè)關(guān)系，使得上的一個(gè)關(guān)系，使得( (a,b)Sa,b)S(a,b)R(a,b)R且且 ( (b,a)Rb,a)R。證明：。證明：S S是是A A上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。例例6 6 設(shè)設(shè)R R是是A A上的二元關(guān)系，上的二元關(guān)系，S=(S=(a,b)|a,b)| cAcA, ,使得使得( (a,c)Ra,c)R且且( (c,b)Rc,b)R 。證明：若。證明：若R R是等價(jià)關(guān)系，則是等價(jià)關(guān)系，則S S 也是等價(jià)關(guān)系。也是等價(jià)關(guān)系。 說(shuō)明：本題可以證明說(shuō)明：本題可以證明R RS S。例例7 7 設(shè)設(shè)AA1 1,A,A2 2, ,A,An n 是集合是集合A A的劃分，若的劃

39、分，若A Ai iBB，1in1in，證明：，證明：AA1 1B,AB,A2 2B,B, ,A An nBB 是集合是集合ABAB的劃分。的劃分。例例8 8設(shè)設(shè)S=1,2,3,4,S=1,2,3,4,并設(shè)并設(shè)A AS SS,S,在在A A上定義關(guān)系上定義關(guān)系R R為為: : ( (a,b)R(c,d)a,b)R(c,d)a+ba+b= =c+dc+d。 證明證明:(:(1) 1) R R是是A A上的等價(jià)關(guān)系；上的等價(jià)關(guān)系；(2) (2) 計(jì)算計(jì)算A/RA/R。例例9 9 設(shè)設(shè)X=1,2,X=1,2,n, S=X,n, S=XX X。R R是是S S上的如下的關(guān)系：上的如下的關(guān)系： ( (I,

40、j),(k,l)SI,j),(k,l)S，( (I,j)R(k,l)I,j)R(k,l)i+ji+j= =k+lk+l。證明：。證明：（1 1）R R是等價(jià)關(guān)系；（是等價(jià)關(guān)系；（2 2）求等價(jià)類個(gè)數(shù)。）求等價(jià)類個(gè)數(shù)。例例1010設(shè)設(shè)A=1,2,3,4A=1,2,3,41,2,3,41,2,3,4，A A上的二元關(guān)系上的二元關(guān)系R R定定義為：義為：( (x,y)R(u,v)x,y)R(u,v)|x-y|x-y|=|=|u-vu-v| |，證明：，證明： (1)R(1)R是是A A上的等價(jià)關(guān)系；上的等價(jià)關(guān)系；(2)(2)確定由確定由R R對(duì)集合對(duì)集合A A的劃分。的劃分。例例1111設(shè)設(shè)R R1

41、 1是是A A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系，R R2 2是是B B上的等價(jià)關(guān)系。在上的等價(jià)關(guān)系。在 S=AS=AB B上定義關(guān)系上定義關(guān)系R R如下：如下：(x(x1 1,y,y1 1)R(x)R(x2 2,y,y2 2) )(x(x1 1,x,x2 2) ) R R1 1且且(y(y1 1,y,y2 2) ) R R2 2證明：證明：R R是是S S上的等價(jià)關(guān)系上的等價(jià)關(guān)系。例例12 12 設(shè)設(shè) x x1 1,x,x2 2X,X,x x1 1RxRx2 2f(xf(x1 1)=f(x)=f(x2 2) )，求，求R R等價(jià)類。等價(jià)類。 （x=fx=f-1-1(y(yi i)|f(x)=)|f(

42、x)=y yi i,y,yi iY Y ，i=1,2,ni=1,2,n）例例1313 設(shè)設(shè)X=1,2,3,Y=1,2,S=X=1,2,3,Y=1,2,S=f|f:Xf|f:XY Y 。是是S S上上的二元關(guān)系：的二元關(guān)系： f,gSf,gS，則，則fgfgI Im m(f(f)=)=I Im m(g(g) )。證明。證明: : (1) (1)是是S S上的等價(jià)關(guān)系上的等價(jià)關(guān)系; ; (2) (2)求等價(jià)類的集合。求等價(jià)類的集合。例例14 14 P113 (2)P113 (2)例例15 15 P113 (3)P113 (3)例例16 16 設(shè)設(shè)N N是自然數(shù)，定義是自然數(shù)，定義N N上的關(guān)系上的

43、關(guān)系R R如下：如下： R=(R=(x,y)|xNx,y)|xN，yNyN，x+yx+y是偶數(shù)是偶數(shù) ，則，則 (1)(1)證明：證明：R R是一個(gè)等價(jià)關(guān)系；是一個(gè)等價(jià)關(guān)系； (2)(2)求關(guān)系求關(guān)系R R的等價(jià)類。的等價(jià)類。8 8 偏序關(guān)系與偏序集偏序關(guān)系與偏序集 序關(guān)系研究的是集合中的元素的次序，它提供了序關(guān)系研究的是集合中的元素的次序，它提供了一種比較集合中各個(gè)元素一種比較集合中各個(gè)元素“大小大小”的工具。序關(guān)系主的工具。序關(guān)系主要包括：偏序關(guān)系、擬序關(guān)系、全序關(guān)系和良序關(guān)系。要包括：偏序關(guān)系、擬序關(guān)系、全序關(guān)系和良序關(guān)系。其中最重要的是偏序關(guān)系。其中最重要的是偏序關(guān)系。8.18.1偏序

44、關(guān)系偏序關(guān)系一、定義一、定義定義定義1 1 設(shè)設(shè)R R是非空集合是非空集合A A上的一個(gè)二元關(guān)系，若上的一個(gè)二元關(guān)系，若R R同時(shí)同時(shí)具有以下三個(gè)性質(zhì)：具有以下三個(gè)性質(zhì)： (1)R(1)R是自反的；是自反的；(2)R(2)R是反對(duì)稱的；是反對(duì)稱的；(3)R(3)R是傳遞的。是傳遞的。則稱則稱R R是是A A上的上的偏序關(guān)系偏序關(guān)系，簡(jiǎn)稱偏序，記為，簡(jiǎn)稱偏序，記為“”。例：例：1.1.在集合在集合A A的的2 2A A上定義的上定義的“”、“”是偏序關(guān)是偏序關(guān)系。系。2.2.在整數(shù)集合在整數(shù)集合Z Z上的上的 “”、 “” 、“| |”是偏序關(guān)是偏序關(guān)系，系，但但“模模n n同余關(guān)系同余關(guān)系”不

45、是偏序關(guān)系。不是偏序關(guān)系。定義定義2 2 設(shè)設(shè)R R是非空集合是非空集合A A上的一個(gè)二元關(guān)系，若上的一個(gè)二元關(guān)系，若R R同時(shí)具同時(shí)具有下列性質(zhì)：有下列性質(zhì)：(1)R(1)R是反自反的；是反自反的；(2)R(2)R是反對(duì)稱的；是反對(duì)稱的；(3)R(3)R是傳遞的。是傳遞的。則稱則稱R R是是A A上的上的擬序關(guān)系擬序關(guān)系，記為，記為“”。例：例：1.1.在整數(shù)集合在整數(shù)集合Z Z上的上的“”，“”都是擬序關(guān)系。都是擬序關(guān)系。2.2.在集合在集合A A的的2 2A A上定義的上定義的“”, ,“”是擬序關(guān)系。是擬序關(guān)系。說(shuō)明：說(shuō)明：1.1.偏序關(guān)系也稱弱偏序關(guān)系或半序關(guān)系；擬序關(guān)偏序關(guān)系也稱弱

46、偏序關(guān)系或半序關(guān)系；擬序關(guān)系也稱為強(qiáng)偏序關(guān)系。系也稱為強(qiáng)偏序關(guān)系。2.2.有些書(shū)上把定義有些書(shū)上把定義2 2中的條件（中的條件（2 2）省略。）省略。3.3.證明：若證明：若R R是是A A上的擬序關(guān)系，則上的擬序關(guān)系，則R R是反對(duì)稱的。是反對(duì)稱的。二、偏序與擬序的聯(lián)系與區(qū)別二、偏序與擬序的聯(lián)系與區(qū)別定理定理1 1 設(shè)設(shè)R R是是A A上的一個(gè)二元關(guān)系，則上的一個(gè)二元關(guān)系，則(1)(1)若若R R是是A A上的偏序關(guān)系，則上的偏序關(guān)系，則RRRR0 0是是A A上的擬序關(guān)系；上的擬序關(guān)系；(2)(2)若若R R是是A A上的擬序關(guān)系，則上的擬序關(guān)系，則R RR R0 0是是A A上的偏序關(guān)系

47、。上的偏序關(guān)系。區(qū)別：區(qū)別：偏序與擬序的區(qū)別就在于一個(gè)是自反的，一個(gè)偏序與擬序的區(qū)別就在于一個(gè)是自反的，一個(gè)是反自反的。由于它們類似，因此，只要把偏序關(guān)系是反自反的。由于它們類似，因此，只要把偏序關(guān)系搞清楚了，擬序關(guān)系也就很容易搞清楚了。因此，在搞清楚了，擬序關(guān)系也就很容易搞清楚了。因此，在下面只討論偏序關(guān)系。下面只討論偏序關(guān)系。8.28.2偏序集偏序集定義定義3 3 設(shè)設(shè)R R的集合的集合A A上的一個(gè)偏序關(guān)系，集合上的一個(gè)偏序關(guān)系，集合A A對(duì)偏序關(guān)對(duì)偏序關(guān)系系R R形成一個(gè)二元組，記為形成一個(gè)二元組，記為(A,R)(A,R)，稱，稱(A,R)(A,R)為偏序集。為偏序集。例例：1.1.（

48、Z,Z,）是偏序集。）是偏序集。2.(22.(2A A, ,) )是偏序集。是偏序集。3.A3.A2,4,6,82,4,6,8，R R1 1整除關(guān)系，整除關(guān)系，R R2 2整倍數(shù)關(guān)系。整倍數(shù)關(guān)系。R R1 1=(2,2),(2,4),(2,6),(2,8),(4,4),(4,8),(6,6),(8,8),=(2,2),(2,4),(2,6),(2,8),(4,4),(4,8),(6,6),(8,8), R R2 2=(2,2),(4,2),(6,2),(8,2),(4,4),(8,4),(6,6),(8,8)=(2,2),(4,2),(6,2),(8,2),(4,4),(8,4),(6,6),

49、(8,8)。于是于是(A,R(A,R1 1),(A,R),(A,R2 2) )都是偏序集。都是偏序集。說(shuō)明：說(shuō)明：在一個(gè)集合上可以定義多個(gè)偏序關(guān)系，從而可在一個(gè)集合上可以定義多個(gè)偏序關(guān)系，從而可以形成多個(gè)偏序集。因此，在一個(gè)集合上定義多個(gè)偏以形成多個(gè)偏序集。因此，在一個(gè)集合上定義多個(gè)偏序關(guān)系時(shí)，一定要說(shuō)明某個(gè)偏序集是對(duì)哪個(gè)關(guān)系的。序關(guān)系時(shí)，一定要說(shuō)明某個(gè)偏序集是對(duì)哪個(gè)關(guān)系的。四、對(duì)偶四、對(duì)偶 集合集合A A上的偏序關(guān)系上的偏序關(guān)系“”的逆的逆“-1-1”也是也是A A上的上的偏序關(guān)系，以后用偏序關(guān)系，以后用“”表示表示“”的逆關(guān)系的逆關(guān)系“-1-1”。 若若xyxy但但xyxy，則記為，則記為

50、x xy y。稱。稱(A,)(A,)是是(A,)(A,)的對(duì)偶。的對(duì)偶。8.3 8.3 HasseHasse圖圖 利用偏序關(guān)系的良好性質(zhì)，可以把它的關(guān)系圖簡(jiǎn)利用偏序關(guān)系的良好性質(zhì)，可以把它的關(guān)系圖簡(jiǎn)化為比較簡(jiǎn)單的化為比較簡(jiǎn)單的HasseHasse圖。圖。 1.1. 由于偏序關(guān)系是自反的，所以在其關(guān)系圖中，對(duì)由于偏序關(guān)系是自反的，所以在其關(guān)系圖中，對(duì)每個(gè)頂點(diǎn)到自身的矢線（環(huán)）可以省略不畫(huà)。每個(gè)頂點(diǎn)到自身的矢線（環(huán)）可以省略不畫(huà)。 2. 2. 又由于偏序關(guān)系是傳遞的，則若又由于偏序關(guān)系是傳遞的，則若a,b,ca,b,c是三個(gè)不是三個(gè)不同的元素且同的元素且abab，bcbc，則，則acac。這時(shí)在關(guān)

51、系圖中，。這時(shí)在關(guān)系圖中，從從a a到到c c的矢線可以省去不畫(huà)。的矢線可以省去不畫(huà)。3. 3. 最后，若最后，若abab，abab且又不存在元素且又不存在元素c c，caca，b b使得使得acbacb，則稱，則稱b b是是a a的直接上元素的直接上元素(b(b覆蓋覆蓋a)a)。（1 1）若）若b b是是a a的直接上元素，則把代表的直接上元素，則把代表b b的點(diǎn)，畫(huà)在代的點(diǎn)，畫(huà)在代表表a a的點(diǎn)的上方且用一條邊聯(lián)結(jié)。的點(diǎn)的上方且用一條邊聯(lián)結(jié)。（2 2）若）若a a與與b b兩個(gè)元素中，兩個(gè)元素中，a a不是不是b b且且b b也不是也不是a a的直接的直接上元素，則上元素，則a a與與b

52、b之間無(wú)線聯(lián)絡(luò)。一般把它們畫(huà)在一個(gè)之間無(wú)線聯(lián)絡(luò)。一般把它們畫(huà)在一個(gè)水平線上。水平線上。4.4.在在HasseHasse圖中，總認(rèn)為方向向上的，因此不用矢線，圖中，總認(rèn)為方向向上的，因此不用矢線，按著以上方法畫(huà)出的偏序關(guān)系圖稱為按著以上方法畫(huà)出的偏序關(guān)系圖稱為HasseHasse圖。圖。例：例：1.1.設(shè)設(shè)A=aA=a，則，則2 2A A上定義的包含關(guān)系上定義的包含關(guān)系“”是是2 2A A上的偏序關(guān)系，其上的偏序關(guān)系，其HasseHasse圖如圖圖如圖(a)(a)所示。所示。例：例：1.1.設(shè)設(shè)A=aA=a，則，則2 2A A上定義的包含關(guān)系上定義的包含關(guān)系“”是是2 2A A上上的偏序關(guān)系，其

53、的偏序關(guān)系，其HasseHasse圖如圖圖如圖(a)(a)所示。所示。若若A=A=a,ba,b ，則，則2 2A A上定義的包含關(guān)系上定義的包含關(guān)系“”是是2 2A A上的偏上的偏序關(guān)系，其序關(guān)系，其HasseHasse圖如圖圖如圖(b)(b)所示。所示。若若A=A=a,b,ca,b,c ，則，則2 2A A上定義的包含關(guān)系上定義的包含關(guān)系“”是是2 2A A上上的偏序關(guān)系，其的偏序關(guān)系，其HasseHasse圖如圖圖如圖(c)(c)所示。所示。2.2.設(shè)設(shè)A=2,3,6,12,24,36A=2,3,6,12,24,36，容易驗(yàn)證，容易驗(yàn)證A A上的整除關(guān)系是上的整除關(guān)系是A A上的偏序關(guān)系，

54、其上的偏序關(guān)系，其HasseHasse圖如圖圖如圖(d)(d)所示。所示。 (a) (b) (c) (d) a?aa,b?ba,b,caa,bb?cb,ca,c2436326128.4 8.4 最大最大( (小小) )元素、極大元素、極大( (小小) )元元定義定義1 1 設(shè)設(shè)(A,)(A,)是一個(gè)偏序集，是一個(gè)偏序集，B BA A，則，則(1)(1)若若aB,aB,使得使得 xBxB，均有，均有xaxa，則稱，則稱a a為為B B的的最最大元素大元素。(2)(2)若若aB,aB,使得使得 xBxB，均有，均有ax ax ，則稱，則稱a a為為B B的的最最小元素小元素。(3)(3)存在存在a

55、BaB，若，若B B中沒(méi)有任何元素中沒(méi)有任何元素x x，滿足，滿足a ax x且且ax ax ，則稱，則稱a a為為B B的的極大元極大元。(4)(4)存在存在aBaB，若，若B B中沒(méi)有任何元素中沒(méi)有任何元素x x，滿足，滿足a ax x且且xa xa ，則稱，則稱a a為為B B的的極小元極小元。例例: : 集合集合A=1,2,3,4,6,12A=1,2,3,4,6,12上的整除關(guān)系上的整除關(guān)系“| |”是是A A上上偏序關(guān)系，偏序關(guān)系，HasseHasse圖如圖所示。圖如圖所示。令令 B B1 1=2,4,6,12=2,4,6,12；B B2 2=2,3,4,6=2,3,4,6 。例例:

56、 :集合集合A=1,2,3,4,6,12A=1,2,3,4,6,12上的整除關(guān)系上的整除關(guān)系“| |”是是A A上偏上偏序關(guān)系，序關(guān)系，HasseHasse圖如圖所示。圖如圖所示。令令B B1 1=2,4,6,12=2,4,6,12，則，則B B1 1最大元最大元1212，最小元，最小元2 2；B B1 1極大元極大元1212，極小元，極小元2 2。令令B B2 2=2,3,4,6=2,3,4,6 ，則，則B B2 2的最大元：的最大元：無(wú)無(wú)，最小元：，最小元：無(wú)無(wú)；B B2 2的極大元：的極大元：4 4，6 6，最小元：，最小元：2 2，3 3。說(shuō)明：說(shuō)明：如何區(qū)別最大如何區(qū)別最大( (小小

57、) )元與極大元與極大( (小小) )元。元。 1.B1.B的最大的最大( (小小) )元應(yīng)大元應(yīng)大( (小小) )于或等于于或等于B B中其它各元素中其它各元素; ;2.B2.B的極大的極大( (小小) )元應(yīng)不小于元應(yīng)不小于B B中其它各元素。即它大中其它各元素。即它大( (小小) )于或等于于或等于B B中的一些元素，并與中的一些元素，并與B B中另一些元素?zé)o中另一些元素?zé)o關(guān)系關(guān)系; ;3.3.最大最大( (小小) )元不一定存在，若存在必唯一元不一定存在，若存在必唯一; ;4.4.在非空集合中，極大在非空集合中，極大( (小小) )元必存在，但不一定唯一。元必存在，但不一定唯一。 8.

58、5 8.5 上上( (下下) )界、上界、上( (下下) )確界確界定義定義2 2 設(shè)設(shè)(A,)(A,)是一個(gè)偏序集，是一個(gè)偏序集，B BA A，則，則(1)(1)若存在若存在aAaA，使得，使得 xB xB ，均有，均有xaxa，則稱，則稱a a為為B B的上界；的上界；(2)(2)若存在若存在aAaA，使得，使得 xBxB，均有，均有axax，則稱，則稱a a為為B B的的下界；下界； (3)(3)若若B B的一切上界元素形成的集合中有最小元素，則的一切上界元素形成的集合中有最小元素，則稱此稱此最小上界最小上界為為B B的的上確界上確界，記為，記為supBsupB；(4)(4)若若B B的

59、一切下界元素形成的集合中有最大元素，則的一切下界元素形成的集合中有最大元素，則稱此稱此最大下界最大下界為為B B的的下確界下確界，記為，記為infBinfB。例：例：集合集合A=2,3,4,6,9,12,18A=2,3,4,6,9,12,18，A A上整除關(guān)系上整除關(guān)系“| |”是是偏序關(guān)系，其偏序關(guān)系，其HasseHasse圖如圖所示。圖如圖所示。令令 B1=2,4B1=2,4；B2=4,6,9B2=4,6,9；B3=2,3B3=2,3。例：例：集合集合A=2,3,4,6,9,12,18A=2,3,4,6,9,12,18，A A上整除關(guān)系上整除關(guān)系“| |”是是偏序關(guān)系，其偏序關(guān)系，其Has

60、seHasse圖如圖所示。圖如圖所示。令令B B1 1=2,4=2,4，則，則 B B1 1的上界是：的上界是：4,124,12；上確界是：；上確界是：4 4。 B B1 1的下界是：的下界是：2 2； 下確界是：下確界是：2 2。令令B B2 2=4,6,9=4,6,9，則，則B B2 2的上界：無(wú)；上確界：無(wú)。的上界：無(wú)；上確界：無(wú)。B B2 2的下界：無(wú)；下確界：無(wú)。的下界：無(wú)；下確界：無(wú)。令令B B3 3=2,3=2,3，則，則B B3 3的上界是：的上界是：6,12,186,12,18；上確界：；上確界：6 6。B B3 3的下界是：無(wú)；的下界是：無(wú)； 下確界：無(wú)。下確界：無(wú)。121