第3章集合與關(guān)系hhs

1、1/38集合論溯源集合論溯源十六世紀(jì)末十六世紀(jì)末 起源起源十九世紀(jì)十九世紀(jì) 德國(guó)數(shù)學(xué)家德國(guó)數(shù)學(xué)家康托康托創(chuàng)立創(chuàng)立古典集合論古典集合論19001900年前后年前后 出現(xiàn)各種出現(xiàn)各種悖論悖論19081908年年 策莫羅建立集合論的公理系統(tǒng)策莫羅建立集合論的公理系統(tǒng)目前目前 集合論公理系統(tǒng)有兩種形式集合論公理系統(tǒng)有兩種形式: :策莫羅策莫羅- -弗蘭克爾弗蘭克爾- -柯很形式柯很形式（zfczfc）貝爾內(nèi)斯貝爾內(nèi)斯- -諾伊曼諾伊曼- -葛德爾形式（葛德爾形式（bngbng）在在計(jì)算機(jī)領(lǐng)域計(jì)算機(jī)領(lǐng)域得到廣泛應(yīng)用得到廣泛應(yīng)用2/38古典集合論古典集合論 康托稱集合是康托稱集合是“一些確定的、不同的東西

2、的總體，這些東西，一些確定的、不同的東西的總體，這些東西，人們能夠意識(shí)到，并且能夠判斷一個(gè)給定的東西是否屬于這個(gè)總?cè)藗兡軌蛞庾R(shí)到，并且能夠判斷一個(gè)給定的東西是否屬于這個(gè)總體體”。悖論悖論 -理發(fā)師悖論：理發(fā)師悖論：在一個(gè)小島上有唯一的一位理發(fā)師。他宣稱：我為在一個(gè)小島上有唯一的一位理發(fā)師。他宣稱：我為島上所有不為自己理發(fā)的人理發(fā)，而不給那些為自己理發(fā)的人理島上所有不為自己理發(fā)的人理發(fā)，而不給那些為自己理發(fā)的人理發(fā)。發(fā)。”。 請(qǐng)問：理發(fā)師的頭發(fā)由誰來理呢？請(qǐng)問：理發(fā)師的頭發(fā)由誰來理呢？ -羅素悖論：羅素悖論：令集合令集合s為包含所有不以自身為元素的那些集合，即為包含所有不以自身為元素的那些集合，

3、即s=x| x x 請(qǐng)問：請(qǐng)問：s s嗎嗎 ？ 3/38包括九個(gè)公理包括九個(gè)公理外延公理外延公理空集公理空集公理無序?qū)頍o序?qū)碚齽t公理正則公理替換公理替換公理方冪集公理方冪集公理集公理集公理無限公理無限公理選擇公理選擇公理外延公理：外延公理：假定假定a和和b都是集合，如果任都是集合，如果任何一個(gè)事物屬于何一個(gè)事物屬于 a也一定屬于也一定屬于b，屬于，屬于b 也一定屬于也一定屬于a ，那么，那么a和和b是同一個(gè)是同一個(gè)集合，或稱兩個(gè)集合集合，或稱兩個(gè)集合a和和b相等。相等?？占恚嚎占恚捍嬖谝粋€(gè)不包括任何元素的集存在一個(gè)不包括任何元素的集合。合。正則公理：正則公理：任何一個(gè)非空集合任

4、何一個(gè)非空集合a一定包一定包含一個(gè)元素含一個(gè)元素a，a的任何一個(gè)元素都不的任何一個(gè)元素都不是是 a 的元素的元素 集合論是學(xué)習(xí)計(jì)算機(jī)科學(xué)必備的基礎(chǔ)知識(shí)集合論是學(xué)習(xí)計(jì)算機(jī)科學(xué)必備的基礎(chǔ)知識(shí) , 計(jì)算機(jī)領(lǐng)域的大多計(jì)算機(jī)領(lǐng)域的大多數(shù)基本概念和理論都可以采用集合論的有關(guān)術(shù)語來描述和論證數(shù)基本概念和理論都可以采用集合論的有關(guān)術(shù)語來描述和論證, 集合集合論被廣泛地應(yīng)用于形式語言、編譯理論、信息檢索、數(shù)據(jù)結(jié)構(gòu)、算論被廣泛地應(yīng)用于形式語言、編譯理論、信息檢索、數(shù)據(jù)結(jié)構(gòu)、算法分析、程序設(shè)計(jì)、人工智能等領(lǐng)域法分析、程序設(shè)計(jì)、人工智能等領(lǐng)域 。 4/383.1 集合的基本概念3.2 集合的基本運(yùn)算3.3 集合中元素

5、的計(jì)數(shù)3.4 笛卡爾乘積3.5 關(guān)系的概念3.6 關(guān)系的表示與性質(zhì)3.7 關(guān)系的運(yùn)算3.8 關(guān)系的閉包運(yùn)算3.9 相容關(guān)系與覆蓋3.10 等價(jià)關(guān)系與劃分3.11 偏序關(guān)系5/381. 集合定義集合定義 集合沒有精確的數(shù)學(xué)定義集合沒有精確的數(shù)學(xué)定義 理解：由離散個(gè)體構(gòu)成的整體稱為理解：由離散個(gè)體構(gòu)成的整體稱為集合集合，稱這些個(gè)體為集，稱這些個(gè)體為集 合的合的元素元素 常見的數(shù)集：常見的數(shù)集：n, z, q, r, c 等分別表示自然數(shù)、整數(shù)、有等分別表示自然數(shù)、整數(shù)、有 理數(shù)、實(shí)數(shù)、復(fù)數(shù)集合理數(shù)、實(shí)數(shù)、復(fù)數(shù)集合2. 集合表示法集合表示法 枚舉法枚舉法-通過列出全體元素來表示集合通過列出全體元素來

6、表示集合 謂詞表示法謂詞表示法-通過謂詞概括集合元素的性質(zhì)通過謂詞概括集合元素的性質(zhì) 實(shí)例：實(shí)例： 枚舉法：枚舉法： 謂詞法：謂詞法：,cbaa., 3, 2, 1b冬秋，夏，春，c|是學(xué)生xxd |是整數(shù)xxe 01|2xrxxf6/383. 集合的元素具有的性質(zhì)集合的元素具有的性質(zhì) 無序性無序性：元素列出的順序無關(guān)：元素列出的順序無關(guān) 相異性相異性：集合的每個(gè)元素只計(jì)：集合的每個(gè)元素只計(jì) 數(shù)一次數(shù)一次 確定性確定性：對(duì)任何元素和集合都：對(duì)任何元素和集合都 能確定這個(gè)元素是否能確定這個(gè)元素是否 為該集合的元素為該集合的元素 任意性任意性：集合的元素也可以是：集合的元素也可以是 集合集合4元素

7、與集合的關(guān)系元素與集合的關(guān)系 隸屬關(guān)系：隸屬關(guān)系： 或者或者 5集合的樹型層次結(jié)構(gòu)集合的樹型層次結(jié)構(gòu)d a , a a7/386.集合與集合之間的關(guān)系：集合與集合之間的關(guān)系： , =, , , , 定義定義6.1 a b x ( x a x b )，a是是b的子集的子集 定義定義6.2 a = b a b b a 定義定義6.3 a b a b a b ，a是是b的真子集的真子集 a b x ( x a x b ) 思考：思考： 和和 的定義的定義 注意注意 和和 是不同層次的問題是不同層次的問題8/387空集空集 ：不含有任何元素的集合不含有任何元素的集合 實(shí)例：實(shí)例： x | x r x2

8、+1=0 定理定理6.1 空集是任何集合的子集?？占侨魏渭系淖蛹?證證: 對(duì)于任意集合對(duì)于任意集合a， a x (xx a) t (恒真命題恒真命題) 推論推論 是惟一的是惟一的 一般地，稱集合a的子集和a為a的平凡子集。8. 冪集：冪集： (a)= x | x a 實(shí)例：實(shí)例： ()=, ()=, 計(jì)數(shù)：計(jì)數(shù)：如果如果 |a|=n，則，則 | (a)|=2n.9. 全集全集 e：包含了所有集合的集合包含了所有集合的集合 全集具有相對(duì)性：與問題有關(guān)，不存在絕對(duì)的全集全集具有相對(duì)性：與問題有關(guān)，不存在絕對(duì)的全集9/38例 a= a, b, c，求a的冪冪集(a) 。 解： 將a的子集從小到

9、大分類： 0元子集，即空集, ； 1元子集，即單元集，a，b，c； 2元子集，a, b，b, c，a, c； 3元子集，a, b, c； 集合a有(a) = , a, b, c, a, b, a, c, b, c, a, b, c。習(xí)題：p86（6）d10/381 集合的運(yùn)算2 集合運(yùn)算算律集合的基本運(yùn)算有集合的基本運(yùn)算有: 并并 a b = x | x a x b 交交 a b = x | x a x b 相對(duì)補(bǔ)相對(duì)補(bǔ) a b = x | x a x b 對(duì)稱差對(duì)稱差 a b = (a b) (b a) 絕對(duì)補(bǔ)絕對(duì)補(bǔ) a = e a a ba baba ba文氏圖11/381 集合的運(yùn)算2

10、集合運(yùn)算算律說明說明(1)并和交運(yùn)算可以推廣到有窮個(gè)集合上，即并和交運(yùn)算可以推廣到有窮個(gè)集合上，即 a1 a2 an = x | x a1 x a2 x an a1 a2 an = x | x a1 x a2 x an (2) a b a b = a b = a b = a例 a=0, 1, 2，b=2, 3，計(jì)算解：ba3, 1, 031, 0uba3, 1, 023, 2, 1, 0ba12/381 集合的運(yùn)算2 集合運(yùn)算算律 任何代數(shù)運(yùn)算都遵從一定的算律，集合運(yùn)算也不例外。下面給出集合運(yùn)算的主要算律，其中a，b，c表示任意的集合。 冪等律 結(jié)合律 交換律 分配律 同一律 零 律 排中律

11、矛盾律 吸收律 雙重否定律 德摩根律 aaauaaaicbacbauuuucbacbaiiiiabbauuabbaii cabacbauiuiu cabacbaiuiuiaauauaiuuauaiuaauaai, abaaiuabaauiaa cabacbaiu cabacbauicbcbiucbcbuiu u 13/381 集合的運(yùn)算2 集合運(yùn)算算律 除了以上算律，還有一些關(guān)于集合運(yùn)算性質(zhì)的重要結(jié)論，在此一并給出。 建立了相對(duì)補(bǔ)運(yùn)算和交運(yùn)算之間的聯(lián)系，可以利用它將相對(duì)補(bǔ)轉(zhuǎn)變成交。 給出了 的三種等價(jià)的定義，為證明兩個(gè)集合之間包含關(guān)系提供了新方法，同時(shí)也可以用于集合公式的化簡(jiǎn)。bbaabaii

12、babbaauuabababaibaabababbaiuabbacbacbaaoaoaacbcabababaibaabababbaiuba 習(xí)題：p95（11）a14/38 集合a含有n個(gè)元素，可以說集合a的基數(shù)是n，記作card a=n。所謂基數(shù)就是表示集合中所含元素多少的量。如果集合a的基數(shù)是n，也可以記為|a|=n。顯然空集的基數(shù)是0，即|=0 。 定義定義3.3.1 設(shè)為集合，若存在自然數(shù)n（0也是自然數(shù)），使得|a|=card a=n ，則稱a為有窮集，否則就稱a為無窮集。 例3.3.1 有100名程序員，其中47名熟悉c語言，35名熟悉c+語言，23名熟悉這兩種語言。問有多少人對(duì)這

13、兩種語言都不熟悉？ 解：設(shè)a，b分別表示熟悉c和c+語言的程序員的集合，則該問題可以用圖3.3.1的文氏圖表示。將熟悉兩種語言的對(duì)應(yīng)人數(shù)23填入ab的區(qū)域內(nèi)，不難得到a-b和b-a的人數(shù)分別為 | a-b| = |a|-| ab|=47-23=24 | b-a| = |b|-| ab|=35-23=12 從而得到| ab|=24+23+12=59, 故，| (ab)|=100-59=41， 即兩種語言都不熟悉的有41人。15/38 設(shè)s是有窮集，p1和p2分別表示兩種性質(zhì)，對(duì)于s中的任何一個(gè)元素x，只能處于以下四種情況之一： （1）只具有性質(zhì)p1 ； （2）只具有性質(zhì)p2 ； （3）具有p1和

14、p2兩種性質(zhì)； （4）兩種性質(zhì)都沒有。 令a1和a2分別表示s中具有性質(zhì)p1和p2的元素的集合。為了使表達(dá)式簡(jiǎn)潔，對(duì)任何集合b，用 代替b。由文氏圖不難得到以下公式 這就是容斥原理的一種簡(jiǎn)單形式。 如果涉及到三條性質(zhì)，容斥原理的公式則變成 321323121321321aaaaaaaaaaaasaaaiiiiiii16/38定理定理 3.3.1 s中不具有性質(zhì)p1, p2, , pm的元素?cái)?shù)是 定理3.3.1證明略。 推論推論 在s中至少具有一條性質(zhì)的元素?cái)?shù)是mmmkjikjimjijimiimaaaaaaaaasaaaiiiiiiiii.1.2111121mmmkjikjimjijimiim

15、aaaaaaaaaaaaiiiiiiuuu.1.2111112117/38例：某班學(xué)生150人。數(shù)學(xué)考試成績(jī)90分以上的有80人，語文考試成績(jī)90分以上的有75人，兩門課程均在90分以上的有50人，問 （1）只有一門課程成績(jī)90分以上的學(xué)生有多少人？ （2）兩門課程成績(jī)均不在90分以上的學(xué)生有多少人？解：全集為該班學(xué)生組成的集合。設(shè) 由題意可知 （1）即需求 。因?yàn)?所以， ，即（2）即需求分以上的數(shù)學(xué)成績(jī)?cè)?0| xxa 分以上的語文成績(jī)?cè)?0| xxb 80a75b50ba i150ubabaiuibabbbabbabaababababauuiuuiiuuiiuiuibababababab

16、abauiiiuiiiui5550507580bababababababaiiiuiui18/38定義定義7.1 由兩個(gè)元素由兩個(gè)元素 x 和和 y，按照一定的順序組成的二元組，按照一定的順序組成的二元組稱為稱為有序?qū)τ行驅(qū)Γ涀?，記?有序?qū)π再|(zhì)有序?qū)π再|(zhì): (1) 有序性有序性 （當(dāng)（當(dāng)x y時(shí)）時(shí)） (2) 與與相等的充分必要條件是相等的充分必要條件是 = x=u y=v定義定義7.2 設(shè)設(shè)a,b為集合，為集合，a與與b的的笛卡兒積笛卡兒積記作記作a b，且，且 a b = | x a y b.19/38例例1 a=1,2,3, b=a,b,c a b =, b a =,a=, b=p(

17、a) a = , p(a) b = 20/38笛卡兒積的性質(zhì)笛卡兒積的性質(zhì):(1) 不適合交換律不適合交換律 a b b a (a b, a, b)(2) 不適合結(jié)合律不適合結(jié)合律 (a b) c a (b c) (a, b, c)(3) 對(duì)于并或交運(yùn)算滿足分配律對(duì)于并或交運(yùn)算滿足分配律 a (b c) = (a b) (a c) (b c) a = (b a) (c a) a (b c) = (a b) (a c) (b c) a = (b a) (c a) (4) 若若 a 或或 b 中有一個(gè)為空集，則中有一個(gè)為空集，則 a b 就是空集就是空集. a = b = (5) 若若 |a| =

18、 m, |b| = n, 則則 |a b| = mn證明證明 a (b c) = (a b) (a c)證證 任取任取 : a(bc) xaybc xa(ybyc) (xayb)(xayc) abac (ab)(ac)所以有所以有a(bc) = (ab)(ac).21/38例例2 (1) 證明證明a=b,c=d a c=b d (2) a c = b d是否推出是否推出 a=b,c=d? 為什么？為什么？解解 (1) 任取任取 a c x a y c x b y d b d(2) 不一定不一定.反例如下：反例如下： a=1，b=2, c = d = , 則則a c = b d但是但是a b.2

19、2/38定義定義3.5.1 設(shè)設(shè)a，b是任意兩個(gè)集合，是任意兩個(gè)集合，ab的子集的子集r稱為從稱為從a到到b的二元關(guān)系，當(dāng)?shù)亩P(guān)系，當(dāng)a=b 時(shí)，稱時(shí)，稱r為為a上的二元關(guān)系。上的二元關(guān)系。 從上述定義可以看出從上述定義可以看出a到到b的二元關(guān)系，也是序偶的集合。的二元關(guān)系，也是序偶的集合。 若若 r，則稱，則稱a與與b有關(guān)系有關(guān)系r，記作，記作a r b。 若若 ，則稱，則稱a與與b沒有關(guān)系沒有關(guān)系r，記作，記作 。 例如：設(shè)例如：設(shè)a=a, b, c, d, b=0, 1，則，則r=a, 0, b, 0, c, 1 就是一個(gè)從就是一個(gè)從a到到b的二元關(guān)系。的二元關(guān)系。定義定義3.5.2

20、設(shè)設(shè)a，b是任意兩個(gè)集合，是任意兩個(gè)集合，r是是a到到b上的二元關(guān)系，上的二元關(guān)系，若若r=，則稱為空關(guān)系。若，則稱為空關(guān)系。若r= ab，則稱，則稱r為全關(guān)系。為全關(guān)系。 稱為稱為a上的恒等關(guān)系。上的恒等關(guān)系。 全關(guān)系全關(guān)系 例如：設(shè)例如：設(shè)a=0, 1, 2，則，則 。rba ,bra |,axaaiaaaabaabaea|,2, 2,1, 1,0, 0ai23/38定義定義3.5.3 設(shè)a，b是兩個(gè)集合，r是從a到b上的二元關(guān)系，則 (1)若存在bb，使得r，則所有這樣的aa組成的集合，稱為二元關(guān)系r的定義域。記作dom(r)或d(r)，即 (2)若存在aa，使得 r，則所有這樣的bb組

21、成的集合，稱為二元關(guān)系r的值域。記作ran(r)或r(r)，即 r的定義域和值域一起稱作r的域，記作fldr，即 fldr = dom(r)ran(r) 從x到y(tǒng)的二元關(guān)系r，也可以用圖解的方式表示，如圖3.5.1所示，x和y是兩個(gè)集合。xi是集合x中的元素，yj是集合y中的元素，當(dāng)且僅當(dāng)xiryj時(shí)，才有一條從xi指向yj的有向邊。),)( |)(rbabardom),)( |)(rbaabrran24/38圖 3.5.1 圖解表示法25/38定理定理3.5.1 若若r和和s是從集合是從集合a到到b上的兩個(gè)二元關(guān)系，則上的兩個(gè)二元關(guān)系，則r和和s的并、交、補(bǔ)、差也是的并、交、補(bǔ)、差也是a到到

22、b上的二元關(guān)系。上的二元關(guān)系。 證明：因?yàn)樽C明：因?yàn)閞和和s是從集合是從集合a到到b上的二元關(guān)系上的二元關(guān)系 所以有所以有r ab，s ab。從而有。從而有 即即rs和和rs都是都是a到到b上的二元關(guān)系。上的二元關(guān)系。 又因?yàn)橛忠驗(yàn)?所以所以r和和s也是也是a到到b上的二元關(guān)系。上的二元關(guān)系。 由于由于 故故r-s也是也是a到到b上的二元關(guān)系上的二元關(guān)系basrubasribarbar)(basbas)(basrsri26/381 關(guān)系的矩陣表示2 關(guān)系的圖形表示3 關(guān)系的性質(zhì) 設(shè) x=a, b, c, y=0, 1, 2, 3，r=, , ?？傻藐P(guān)系r的矩陣表示如下： 由上例看出，給定從有限

23、集x到y(tǒng)的二元關(guān)系r，就可以構(gòu)造出它的關(guān)系矩陣。 給定兩個(gè)有限集合 和 ，并且r是從x到y(tǒng)的二元關(guān)系 。如果有 則稱矩陣 是r的關(guān)系矩陣，并記作 。0000100011003210cba,.,21mxxxx ,.,21nyyyy jijiijyrxryxr若若01ijrrm27/381 關(guān)系的矩陣表示2 關(guān)系的圖形表示3 關(guān)系的性質(zhì)設(shè)畫出r的關(guān)系圖。 解： r的關(guān)系圖如圖3.6.1所示。 圖3.6.1 r的關(guān)系圖 ,4321xxxxx ,21yyy 。,231211yxyxyxr28/381 關(guān)系的矩陣表示2 關(guān)系的圖形表示3 關(guān)系的性質(zhì)定義定義3.6.1 設(shè)設(shè) r 為為a上的關(guān)系上的關(guān)系,

24、(1) 若若 x(xa r), 則稱則稱 r 在在 a 上是上是自反自反的的.(2) 若若 x(xa r), 則稱則稱 r 在在 a 上是上是反自反反自反的的. 實(shí)例：實(shí)例：自反：全域關(guān)系自反：全域關(guān)系ea, 恒等關(guān)系恒等關(guān)系ia, 小于等于關(guān)系小于等于關(guān)系la, 整除關(guān)系整除關(guān)系da反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系. a=1,2,3, r1, r2, r3是是a上的關(guān)系上的關(guān)系, 其中其中 r1, r2, r3r2 自反自反 ，r3 反自反，反自反，r1既不是自反的也不是反自反的既不是自反的也不是反自反的.29/381 關(guān)系的矩陣表

25、示2 關(guān)系的圖形表示3 關(guān)系的性質(zhì)定義定義3.6.2 設(shè)設(shè) r 為為 a上的關(guān)系上的關(guān)系, (1) 若若 x y( x,yarr), 則稱則稱 r 為為 a上上對(duì)稱對(duì)稱的關(guān)系的關(guān)系.(2) 若若 x y( x,yarrx=y), 則稱則稱 r 為為a上的上的反對(duì)稱反對(duì)稱關(guān)系關(guān)系.實(shí)例：實(shí)例：對(duì)稱關(guān)系：對(duì)稱關(guān)系：a上的全域關(guān)系上的全域關(guān)系ea, 恒等關(guān)系恒等關(guān)系ia和空關(guān)系和空關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系ia和空關(guān)系也是和空關(guān)系也是a上的反對(duì)稱關(guān)系上的反對(duì)稱關(guān)系. 設(shè)設(shè)a1,2,3, r1, r2, r3和和r4都是都是a上的關(guān)系上的關(guān)系, 其中其中 r1,，r2, r3,，r4

26、, r1：對(duì)稱和反對(duì)稱；：對(duì)稱和反對(duì)稱； r2：只有對(duì)稱；：只有對(duì)稱；r3：只有反對(duì)稱；：只有反對(duì)稱； r4：不對(duì)稱、不反對(duì)稱：不對(duì)稱、不反對(duì)稱30/381 關(guān)系的矩陣表示2 關(guān)系的圖形表示3 關(guān)系的性質(zhì)定義定義3.6.3 設(shè)設(shè)r為為a上的關(guān)系上的關(guān)系, 若若 x y z(x,y,zarrr), 則稱則稱 r 是是a上的上的傳遞傳遞關(guān)系關(guān)系.實(shí)例：實(shí)例： a上的全域關(guān)系上的全域關(guān)系 ea,恒等關(guān)系恒等關(guān)系 ia和空關(guān)系和空關(guān)系 ，小于等小于等于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系設(shè)設(shè) a1,2,3, r1, r2, r3是是a上的關(guān)系上的關(guān)系, 其中其

27、中 r1, r2, r3r1和和r3是是a上的傳遞關(guān)系上的傳遞關(guān)系, r2不是不是a上的傳遞關(guān)系上的傳遞關(guān)系. 31/381 關(guān)系的矩陣表示2 關(guān)系的圖形表示3 關(guān)系的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij1, 且ij, 則rji0m2中1位置, m中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)兩點(diǎn)之間有邊, 是一對(duì)方向相反的邊兩點(diǎn)之間有邊,是一條有向邊點(diǎn)xi到xj有邊, xj 到xk有邊, 則xi到xk也有邊 32/381 關(guān)系的逆運(yùn)算2 關(guān)系的合成運(yùn)算定義定義3.7.1 設(shè)設(shè)r是從集合是從集合x到集合到集合y的二元關(guān)系

28、，如果將的二元關(guān)系，如果將r中中每一對(duì)序偶的元素順序互換，所得到的新的集合則稱為每一對(duì)序偶的元素順序互換，所得到的新的集合則稱為r的逆關(guān)系，記作的逆關(guān)系，記作 ，即，即 由逆關(guān)系的定義可知，由逆關(guān)系的定義可知， 的關(guān)系圖可以通過將的關(guān)系圖可以通過將r的關(guān)系的關(guān)系圖的所有有向弧逆轉(zhuǎn)得到，它的關(guān)系矩陣可以通過將圖的所有有向弧逆轉(zhuǎn)得到，它的關(guān)系矩陣可以通過將r的的關(guān)系矩陣轉(zhuǎn)置得到。關(guān)系矩陣轉(zhuǎn)置得到。 例例3.7.1 設(shè)設(shè) ，求求 。 解：解： 。1r,|,1ryxxyr, 4, 2, 1,4, 3, 2, 1cbarcbayx1r4 ,2 ,1 ,1cbar33/381 關(guān)系的逆運(yùn)算2 關(guān)系的合成運(yùn)

29、算定理定理3.7.1 設(shè)設(shè)r和和s都是從都是從x到到y(tǒng)的二元關(guān)系，則下的二元關(guān)系，則下列各式成立。列各式成立。（1） （2） （3） （4） ，這里，這里r表示表示（5） （6）若）若 ，則，則 rr11)(111)(srsruu111)(srsrii)()(11rrryx )(111)(srsrsr11sr34/381 關(guān)系的逆運(yùn)算2 關(guān)系的合成運(yùn)算 定理定理3.7.2 設(shè)設(shè)r是是a上的二元關(guān)系，則上的二元關(guān)系，則（1） r在在a上是自反的，當(dāng)且僅當(dāng)上是自反的，當(dāng)且僅當(dāng) 。（2） r在在a上是反自反的，當(dāng)且僅當(dāng)上是反自反的，當(dāng)且僅當(dāng) 。 （3） r在在a上是對(duì)稱的，當(dāng)且僅當(dāng)上是對(duì)稱的，當(dāng)且僅

30、當(dāng) 。（4） r在在a上是反對(duì)稱的，當(dāng)且僅當(dāng)上是反對(duì)稱的，當(dāng)且僅當(dāng) 。riairai1 rrairr1i35/381 關(guān)系的逆運(yùn)算2 關(guān)系的合成運(yùn)算定義定義3.7.2 設(shè)r是從集合x到集合y的二元關(guān)系，s是從集合y到z的關(guān)系，則r s稱為r和s的合成關(guān)系，定義為 r s稱為關(guān)系的合成運(yùn)算。 設(shè)r是從集合 到集合 的關(guān)系， s是從集合 到集合 的關(guān)系， 則 是一個(gè) 的矩陣， 是一個(gè) 的矩陣。依照普通矩陣乘法的運(yùn)算，可以定義兩個(gè)關(guān)系矩陣的合成運(yùn)算。),)(|,szyryxyyyzzxxzxsr,.,21mxxxx ,.,21nyyyy ,.,21nyyyy ,.,21lzzzz rmnmsmln3

31、6/38由上述前兩個(gè)矩陣可以構(gòu)造這兩個(gè)矩陣的合成矩陣，記作 。 元素 可由下式得到： 其中 。和的運(yùn)算規(guī)則如下： 兩個(gè)關(guān)系的合成運(yùn)算，就是將布爾關(guān)系矩陣做乘法，所得結(jié)果即為合成關(guān)系矩陣。 mnmmnnraaaaaaaaam.212222111211nlnnllsbbbbbbbbbm.212222111211mlmmllsrcccccccccmm.212222111211srmm ijc)(kjiknkijbacljmi., 2, 1,., 2, 1。111, 001, 010, 000, 111, 101, 110, 0001 關(guān)系的逆運(yùn)算2 關(guān)系的合成運(yùn)算37/381 關(guān)系的逆運(yùn)算2 關(guān)系的

32、合成運(yùn)算定理定理3.4.3 設(shè)設(shè)x, y, z和和w都是集合。都是集合。r是從集合是從集合x到到y(tǒng)的關(guān)系，的關(guān)系，s是從集合是從集合 y到到z的關(guān)系，的關(guān)系，t是從集合是從集合z到到w的關(guān)系。于是有的關(guān)系。于是有 (r s ) t= r ( s t ) 即關(guān)系的合成運(yùn)算滿足結(jié)合律。即關(guān)系的合成運(yùn)算滿足結(jié)合律。證明：證明：對(duì)任意的對(duì)任意的 (r s ) t，根據(jù)合成關(guān)系的定義可知，必，根據(jù)合成關(guān)系的定義可知，必然存在然存在zz，使得，使得 (r s )， t。又因?yàn)?。又因?yàn)?(r s )，故必存在，故必存在yy，使得，使得 r并且并且 s。由。由 s且且 t，根據(jù)合成關(guān)系的定義知，根據(jù)合成關(guān)系的

33、定義知 ( s t )，又因?yàn)?，又因?yàn)?r且且 s t ，得到，得到 r ( s t )。故由。故由的的任意性可知任意性可知(r s) t r ( s t ) 。 同理可證同理可證r ( s t )(r s ) t。 綜上所述，得到綜上所述，得到(r s) t= r ( s t )，即關(guān)系的合成運(yùn)算滿，即關(guān)系的合成運(yùn)算滿足結(jié)合律。足結(jié)合律。 一般來說，關(guān)系的合成運(yùn)算是不滿足交換律的，即一般來說，關(guān)系的合成運(yùn)算是不滿足交換律的，即r s s r。38/38定義定義3.7.3 設(shè)設(shè)r是集合是集合x中的二元關(guān)系，中的二元關(guān)系，nn（n是自然數(shù)是自然數(shù)集），于是集），于是r的的n次冪次冪 定義為：定義

34、為：（1） ，即，即 是是r中的恒等關(guān)系。中的恒等關(guān)系。（2） 。定理定理3.7.4 設(shè)設(shè)r是集合是集合x中的二元關(guān)系。設(shè)中的二元關(guān)系。設(shè)m, nn。則有。則有（1） （2）定理定理3.7.5 設(shè)設(shè)r是是a上的二元關(guān)系，則上的二元關(guān)系，則r在在a上是傳遞的，當(dāng)且上是傳遞的，當(dāng)且僅當(dāng)僅當(dāng)1 關(guān)系的逆運(yùn)算2 關(guān)系的合成運(yùn)算xir00rrrrnn1nmnmrrrnmnmrr)(rrr例題14,習(xí)題:p119(5)、(6)39/381 關(guān)系的閉包定義2 關(guān)系的閉包構(gòu)造方法3 關(guān)系的閉包性質(zhì)定義定義3.7.1 設(shè)設(shè)r是非空集合是非空集合a上的關(guān)系上的關(guān)系, r的的自反自反(對(duì)稱或傳遞對(duì)稱或傳遞)閉包閉包

35、是是a上的關(guān)系上的關(guān)系r , 使得使得r 滿足以下條件：滿足以下條件：(1) r 是自反的是自反的(對(duì)稱的或傳遞的對(duì)稱的或傳遞的) (2) r r (3) 對(duì)對(duì)a上任何包含上任何包含r的的自反自反(對(duì)稱或傳遞對(duì)稱或傳遞)關(guān)系關(guān)系r 有有rr 則稱則稱r是是r的的自反閉包，記作自反閉包，記作r(r), （對(duì)稱閉包記作對(duì)稱閉包記作s(r), 傳傳遞閉包記作遞閉包記作t(r). ）由定義可知：由定義可知：（1）自反自反(對(duì)稱或傳遞對(duì)稱或傳遞)閉包閉包是關(guān)系是關(guān)系（2）自反自反(對(duì)稱或傳遞對(duì)稱或傳遞)閉包閉包是包含是包含r的最小的最小自反自反(對(duì)稱或傳對(duì)稱或傳遞遞)關(guān)系關(guān)系40/381 關(guān)系的閉包定義

36、2 關(guān)系的閉包構(gòu)造方法3 關(guān)系的閉包性質(zhì)集合構(gòu)造方法：集合構(gòu)造方法： 設(shè)設(shè)r為為a上的關(guān)系上的關(guān)系, 則有則有 (1) r(r)=rr0 (2) s(r)=rr 1 (3) t(r)=rr2r3說明：對(duì)有窮集說明：對(duì)有窮集a(|a|=n)上的關(guān)系上的關(guān)系, (3)中的并最多不超過中的并最多不超過rn（參見課（參見課本本p122定理定理3.8.5）矩陣構(gòu)造方法：矩陣構(gòu)造方法： 設(shè)關(guān)系設(shè)關(guān)系r, r(r), s(r), t(r)的關(guān)系矩陣分別為的關(guān)系矩陣分別為m, mr , ms 和和 mt 則則 mr=m+e ms=m+m mt=m+m2+m3+e 是單位矩陣是單位矩陣, m 是是 轉(zhuǎn)置矩陣，相

37、加時(shí)使用轉(zhuǎn)置矩陣，相加時(shí)使用邏輯加邏輯加.說明：對(duì)有窮集說明：對(duì)有窮集a(|a|=n)上的關(guān)系上的關(guān)系, mt=m+m2+mn41/381 關(guān)系的閉包定義2 關(guān)系的閉包構(gòu)造方法3 關(guān)系的閉包性質(zhì)關(guān)系圖構(gòu)造方法：關(guān)系圖構(gòu)造方法： 設(shè)關(guān)系設(shè)關(guān)系r, r(r), s(r), t(r)的關(guān)系圖分別記為的關(guān)系圖分別記為g, gr, gs, gt, 則則gr , gs , gt 的頂點(diǎn)集與的頂點(diǎn)集與g 的頂點(diǎn)集相等的頂點(diǎn)集相等. 除了除了g 的邊以外的邊以外, 以以下述方法添加新的邊：下述方法添加新的邊： (1) 考察考察g 的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn), 若沒環(huán)就加一個(gè)環(huán)，得到若沒環(huán)就加一個(gè)環(huán)，得到gr (2)

38、 考察考察g 的每條邊的每條邊, 若有一條若有一條 xi 到到 xj 的單向邊的單向邊, ij, 則在則在g 中加一條中加一條 xj 到到 xi 的反向邊的反向邊, 得到得到gs (3) 考察考察g 的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn) xi, 找找 xi 可達(dá)的所有頂點(diǎn)可達(dá)的所有頂點(diǎn) xj (允許允許i=j )， 如果沒有從如果沒有從 xi 到到 xj 的邊的邊, 就加上這條邊就加上這條邊, 得到圖得到圖gt42/381 關(guān)系的閉包定義2 關(guān)系的閉包構(gòu)造方法3 關(guān)系的閉包性質(zhì)例例 設(shè)設(shè)a=a,b,c,d, r=, r和和r(r), s(r), t(r)的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示. rr(r)s(r

39、)t(r)43/381 關(guān)系的閉包定義2 關(guān)系的閉包構(gòu)造方法3 關(guān)系的閉包性質(zhì)定理定理3.7.1 設(shè)設(shè)r是非空集合是非空集合a上的關(guān)系上的關(guān)系, 則則 (1) r是自反的當(dāng)且僅當(dāng)是自反的當(dāng)且僅當(dāng) r(r)=r. (2) r是對(duì)稱的當(dāng)且僅當(dāng)是對(duì)稱的當(dāng)且僅當(dāng) s(r)=r. (3) r是傳遞的當(dāng)且僅當(dāng)是傳遞的當(dāng)且僅當(dāng) t(r)=r.定理定理3.7.2 設(shè)設(shè)r1和和r2是非空集合是非空集合a上的關(guān)系上的關(guān)系, 且且 r1 r2, 則則 (1) r(r1) r(r2) (2) s(r1) s(r2) (3) t(r1) t(r2)定理定理3.7.3 設(shè)設(shè)r是非空集合是非空集合a上的關(guān)系上的關(guān)系, (1

40、) 若若r是自反的是自反的, 則則 s(r) 與與 t(r) 也是自反的也是自反的 (2) 若若r是對(duì)稱的是對(duì)稱的, 則則 r(r) 與與 t(r) 也是對(duì)稱的也是對(duì)稱的 (3) 若若r是傳遞的是傳遞的, 則則 r(r) 是傳遞的是傳遞的. 44/381 關(guān)系的閉包定義2 關(guān)系的閉包構(gòu)造方法3 關(guān)系的閉包性質(zhì) 二元關(guān)系的閉包仍然是二元關(guān)系，還可以求它的二元關(guān)系的閉包仍然是二元關(guān)系，還可以求它的閉包。例如，閉包。例如，r是是a上的二元關(guān)系，上的二元關(guān)系，r(r)是它的自反閉是它的自反閉包，還可以求包，還可以求r(r)的對(duì)稱閉包。的對(duì)稱閉包。r(r)的對(duì)稱閉包記為的對(duì)稱閉包記為s(r(r)，簡(jiǎn)記為

41、，簡(jiǎn)記為sr(r)，讀作，讀作r的自反閉包的對(duì)稱閉包。的自反閉包的對(duì)稱閉包。其余類似。其余類似。定理定理3.7.4 設(shè)r是集合a上的二元關(guān)系，則 （1） （2） （3） )()(rsrrrs)()(rtrrrt)()(rtsrst例題12,習(xí)題:p127(1)、(2)a45/381覆蓋與劃分覆蓋與劃分2 2加細(xì)與真加細(xì)加細(xì)與真加細(xì)3 3交叉劃分交叉劃分定義定義3.9.1 給定非空集合a，設(shè)有集合 ，其中 ，且 ， ，且 ，則稱集合s為集合a的覆蓋。,21mssssasiismi, 2, 1asimi1u若還滿足條件 則稱 s 是 a 的劃分.ssjii)(ji 說明： 劃分是覆蓋的特殊情形.

42、劃分的元素 si 稱為劃分的類.例1：令 z=所有整數(shù)的集合 a1=所有偶數(shù)的集合 a2=所有奇數(shù)的集合則 a1,a2是 z 的一個(gè)劃分。46/381覆蓋與劃分覆蓋與劃分2 2加細(xì)與真加細(xì)加細(xì)與真加細(xì)3 3交叉劃分交叉劃分例2：已知 下面哪些集合是 a 的覆蓋或劃分？ , , aa b c2 , , , , ,saa ba c1 , , , ,sa bb c3 , , ,saa b5 , , ,sabc4 , , ,sa b c6 , , ,sa bc最小劃分：是由作為類的集合本身構(gòu)成.如s4最大劃分：是由包含單個(gè)元素的類組成.如s547/381覆蓋與劃分覆蓋與劃分2 2加細(xì)與真加細(xì)加細(xì)與真加

43、細(xì)3 3交叉劃分交叉劃分定義3.9.2 設(shè) a 和 b 是同一集合 x 的兩種劃分,且有 a=a1,a2,.am,b=b1,b2,.bn若 a 的每一個(gè)類都是 b 的某一類的子集,即 則稱 a 是 b 的加細(xì)。ijab若 a 是 b 的加細(xì),且 ba, 則稱 a 是 b 的真加細(xì)。已知x=a,b,c,d，a=a,b,c,d,下面的 bi 哪些是 a的加細(xì)？ b1=a,b,c,d b2 =a,b,c,d, b3=a,b,c,d b4=a,b,c,d b5=d,a,b,c b6=a,d,b,c48/381覆蓋與劃分覆蓋與劃分2 2加細(xì)與真加細(xì)加細(xì)與真加細(xì)3 3交叉劃分交叉劃分定義3.9.3 若 a

44、=a1,a2,ar 與 b=b1,b2,bs 是同一個(gè)集合 x 的兩種劃分，則其中所有 ai bj 組成的集合，稱為是原來兩種劃分的交叉劃分。例4：x =所有生物的集合 p =所有植物的集合 e =所有史前生物 a =所有動(dòng)物的集合 f =所有史后生物則：p,a、 e,f 是 x 的兩種劃分。其交叉劃分為 pe, pf,ae, af 其中 pe表示史前植物 pf表示史后植物 ae表示史前動(dòng)物 af表示史后動(dòng)物定理定理1 若 a, b 是同一集合 x 的兩種劃分,則其交叉劃分也是原集合的一種劃分。定理定理2 任何兩種劃分的交叉劃分，都是原來劃分的一種加細(xì)。49/381等價(jià)關(guān)系的定義等價(jià)關(guān)系的定義

45、2 2等價(jià)類的定義等價(jià)類的定義3 3商集與劃分商集與劃分定義定義3.10.1 設(shè)設(shè)r為非空集合上的關(guān)系為非空集合上的關(guān)系. 如果如果r是自反的、對(duì)稱的是自反的、對(duì)稱的和傳遞的和傳遞的, 則稱則稱r為為a上的上的等價(jià)關(guān)系等價(jià)關(guān)系. 設(shè)設(shè) r 是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系, 若若r, 稱稱 x等價(jià)于等價(jià)于y, 記做記做xy. 例例1 設(shè)設(shè) a=1,2,8, 如下定義如下定義a上的關(guān)系上的關(guān)系r： r=| x,yax y(mod 3)其中其中x y(mod 3)叫做叫做 x與與 y 模模3相等相等, 即即x除以除以3的余數(shù)與的余數(shù)與y除以除以3的余數(shù)相等的余數(shù)相等. 不難驗(yàn)證不難驗(yàn)證 r 為為a上的

46、等價(jià)關(guān)系上的等價(jià)關(guān)系, 因?yàn)橐驗(yàn)?1) xa, 有有 x x (mod 3)(2) x,ya, 若若x y(mod 3), 則有則有y x(mod 3) (3) x,y,za, 若若x y(mod 3), y z(mod 3), 則有則有x z(mod 3)模模 3 等價(jià)關(guān)系的關(guān)系圖等價(jià)關(guān)系的關(guān)系圖50/381等價(jià)關(guān)系的定義等價(jià)關(guān)系的定義2 2等價(jià)類的定義與性質(zhì)等價(jià)類的定義與性質(zhì)3 3商集與劃分商集與劃分定義定義3.10.2 設(shè)設(shè)r為非空集合為非空集合a上的等價(jià)關(guān)系上的等價(jià)關(guān)系, xa，令，令 xr = y | yaxry稱稱xr 為為x關(guān)于關(guān)于r的等價(jià)類的等價(jià)類, 簡(jiǎn)稱為簡(jiǎn)稱為x的的等價(jià)類等

47、價(jià)類, 簡(jiǎn)記為簡(jiǎn)記為xr 實(shí)例實(shí)例 a=1, 2, , 8上模上模3等價(jià)關(guān)系的等價(jià)類：等價(jià)關(guān)系的等價(jià)類： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6定理定理3.10.1 設(shè)設(shè)r是非空集合是非空集合a上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 則則(1) x a, x是是a的非空子集的非空子集(2) x,y a, 如果如果 xry, 則則 x = y(3) x,y a, 如果如果 x y, 則則 x與與y不交不交(4) x | x a=a51/381等價(jià)關(guān)系的定義等價(jià)關(guān)系的定義2 2等價(jià)類的定義與性質(zhì)等價(jià)類的定義與性質(zhì)3 3商集與劃分商集與劃分證證

48、(1) 由定義由定義, x a有有x a. 又又x x, 即即x非空非空. (2) 任取任取 z, 則有則有 zx r r r r r r 從而證明了從而證明了zy. 綜上所述必有綜上所述必有 x y. 同理可證同理可證 y x. 這就得到了這就得到了x = y. (3) 假設(shè)假設(shè) xy, 則存在則存在 z xy, 從而有從而有z xz y, 即即 r r成立成立. 根據(jù)根據(jù)r的對(duì)稱性和傳遞性必有的對(duì)稱性和傳遞性必有 r, 與與 x y矛盾矛盾 (4) 先證先證x | x a a. 任取任取y, y x | x a x(x ay x) y xx a y a 從而有從而有x | xa a 再證再

49、證a x | xa. 任取任取y, y a y yy a yx | x a 從而有從而有x | xa a成立成立. 綜上所述得綜上所述得x | x a = a. 52/381等價(jià)關(guān)系的定義等價(jià)關(guān)系的定義2 2等價(jià)類的定義與性質(zhì)等價(jià)類的定義與性質(zhì)3 3商集與劃分商集與劃分定義定義3.10.3 設(shè)設(shè) r 為非空集合為非空集合a上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 以以 r 的所有等價(jià)的所有等價(jià)類 作 為 元 素 的 集 合 稱 為類 作 為 元 素 的 集 合 稱 為 a 關(guān) 于關(guān) 于 r 的的 商商 集集 , 記 做記 做 a / r , a/r = xr | xa實(shí)例實(shí)例 設(shè)設(shè) a=1,2,8，a關(guān)于模

50、關(guān)于模3等價(jià)關(guān)系等價(jià)關(guān)系r的商集為的商集為 a/r = 1,4,7, 2,5,8, 3,6a關(guān)于恒等關(guān)系和全域關(guān)系的商集為：關(guān)于恒等關(guān)系和全域關(guān)系的商集為： a/ia = 1, 2, , 8， a/ea = 1,2,8定義定義3.10.4設(shè)設(shè)a為非空集合為非空集合, 若若a的子集族的子集族( p(a)滿足滿足:(1) (2) x y(x,y xyxy=)(3) = a則稱則稱是是a的一個(gè)的一個(gè)劃分劃分, 稱稱中的元素為中的元素為a的的劃分塊劃分塊.53/381等價(jià)關(guān)系的定義等價(jià)關(guān)系的定義2 2等價(jià)類的定義與性質(zhì)等價(jià)類的定義與性質(zhì)3 3商集與劃分商集與劃分例例3 給出給出 a1,2,3上所有的等

51、價(jià)關(guān)系上所有的等價(jià)關(guān)系解解 先做出先做出a的劃分的劃分, 從左到右分別記作從左到右分別記作 1, 2, 3, 4, 5.1對(duì)應(yīng)對(duì)應(yīng) ea, 5 對(duì)應(yīng)對(duì)應(yīng) ia, 2, 3 和和 4分別對(duì)應(yīng)分別對(duì)應(yīng) r2, r3和和 r4. r 2 = , i a r 3 = , i a r4=,ia1 123 31 1 123 351 123 321 123 341 123 33例題14,習(xí)題:p134(3)、(5)54/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與全序關(guān)系4 4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì)定義定義1:設(shè)設(shè) r 為定義在

52、集合為定義在集合 a 上的一個(gè)關(guān)系上的一個(gè)關(guān)系, 若若 r 是是 a) 自反的自反的 b) 反對(duì)稱的反對(duì)稱的 c) 傳遞的傳遞的 則則 r 稱為稱為偏序關(guān)系偏序關(guān)系，記為，記為 . 序偶序偶 稱作稱作偏序集偏序集.例1 證明在實(shí)數(shù)集r上, 是偏序關(guān)系.證明： 1）對(duì)于任何 a r，有 a a 成立，故 是自反的； 2）對(duì)于任何 a,b r, 如果有 a b 且 b a 成立，則必有 a=b ,故 是反對(duì)稱的； 3）如果有 a b, b c 成立，則必有 ac, 故 是傳遞的。 因此是偏序關(guān)系。55/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與

53、全序關(guān)系4 4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì) 已知 a=2,3,6,8, =|x整除y，驗(yàn)證 是偏序關(guān)系.證明：,8 ,2,6,2,2,28,8,6,6,6,3,3,323681000010001101101m56/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與全序關(guān)系4 4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì)定義定義2：在偏序集合在偏序集合 中，如果中，如果 x , y a, x y, x y, 且且沒有其它元素沒有其它元素 z,滿足滿足x z, z y, 則則稱稱元素元素 y 蓋住元素蓋住元素 x . 并且

54、并且記記 cova=| x, y a; y 蓋住蓋住 x 對(duì)于給定偏序集合 ，它的蓋住關(guān)系是唯一的。所以可用蓋住的性質(zhì)畫出偏序集合圖，稱為哈斯圖對(duì)于給定偏序集合對(duì)于給定偏序集合 ，其哈斯圖做圖規(guī)則如下：，其哈斯圖做圖規(guī)則如下：（1）用小圓圈代表元素；）用小圓圈代表元素；（2）如果）如果 x y 且且 x y，則將代表，則將代表 y 的小圓圈畫在代的小圓圈畫在代表表 x 的小圓圈之上；的小圓圈之上；（3）如果）如果 cova, 則在則在 x 與與 y 之間用直線連接。之間用直線連接。57/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與全序關(guān)系4

55、4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì) a 是 m=12 的因子集合, 為整除關(guān)系, 求 cova，并畫出哈斯圖。解:,12, 6 , 4 , 3 , 2 , 1a = , , , , , , , , , , , iacova=, , , , 6,12 1234612哈斯圖是簡(jiǎn)化的關(guān)系圖哈斯圖是簡(jiǎn)化的關(guān)系圖(1)自反性：每個(gè)頂點(diǎn)都有自回路，自反性：每個(gè)頂點(diǎn)都有自回路，省去自回路省去自回路。(2)反對(duì)稱性：從小到大安置頂點(diǎn)，反對(duì)稱性：從小到大安置頂點(diǎn)，可省略箭頭可省略箭頭。(3)傳遞性：由于有傳遞性：由于有(，)，(，)r 則則 (，)r，故，故只畫（，），（，）對(duì)應(yīng)的邊，只畫（，

56、），（，）對(duì)應(yīng)的邊，省略邊（，）。省略邊（，）。58/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與全序關(guān)系4 4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì) 畫出哈斯圖rcbap,abc,ca,cb,cba,ba59/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與全序關(guān)系4 4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì)a1=1,2,3,4 為小于等于關(guān)系為小于等于關(guān)系1234a2=,a,a,b,a,b,c 為包含關(guān)系為包含關(guān)系a, ba,cba不同的偏序集不同的偏序集, 哈斯圖可

57、以有同樣的結(jié)構(gòu)哈斯圖可以有同樣的結(jié)構(gòu)60/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與全序關(guān)系4 4 偏序集中的特殊元素及性質(zhì)偏序集中的特殊元素及性質(zhì)定義定義4：設(shè)設(shè) 是一偏序集合，在是一偏序集合，在 a 的一個(gè)子集中，如果每?jī)蓚€(gè)元的一個(gè)子集中，如果每?jī)蓚€(gè)元素都是有素都是有(無無)關(guān)系的，則稱這個(gè)子集是鏈關(guān)系的，則稱這個(gè)子集是鏈(反鏈反鏈)。約定：若 a 的子集只有單個(gè)元素,則它既是鏈又是反鏈. 已知已知 a=a,b,c,d,e r=, ,驗(yàn)證驗(yàn)證 是偏序集，畫出哈斯圖，舉例說明鏈和反鏈。是偏序集，畫出哈斯圖，舉例說明鏈和反鏈。解：解： 1000011000101001011011111rm 關(guān)系矩陣對(duì)角線都為關(guān)系矩陣對(duì)角線都為1，且，且rij 和和rji 不同時(shí)為不同時(shí)為1，所以，所以 r 是是自反的自反的和和反對(duì)稱反對(duì)稱的的。定義定義5：在偏序集在偏序集 中，如果中，如果 a 是一個(gè)鏈，則稱是一個(gè)鏈，則稱 為全序集為全序集合合 (線序集合線序集合)，二元關(guān)系，二元關(guān)系 為全序關(guān)系為全序關(guān)系 (線序關(guān)系線序關(guān)系)。61/381 偏序關(guān)系與偏序集偏序關(guān)系與偏序集2 2 蓋住與哈斯圖蓋住與哈斯圖3 3 鏈與全序關(guān)系鏈與