第8節(jié) 偏序關(guān)系_第1頁(yè)
第8節(jié) 偏序關(guān)系_第2頁(yè)
第8節(jié) 偏序關(guān)系_第3頁(yè)
第8節(jié) 偏序關(guān)系_第4頁(yè)
第8節(jié) 偏序關(guān)系_第5頁(yè)
已閱讀5頁(yè),還剩15頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第8節(jié)偏序關(guān)系主要內(nèi)容:偏序關(guān)系的定義哈斯圖特殊元素1

定義1集合X上的二元關(guān)系R稱為偏序關(guān)系,如果R同時(shí)滿足以下三個(gè)性質(zhì):當(dāng)抽象地討論X上的偏序關(guān)系時(shí),常用符號(hào)“”表示偏序關(guān)系。如果xy,則讀作“x小于或等于y”。1.R是自反的;2.R是反對(duì)稱的;3.R是傳遞的。約定xy且xy時(shí),就記為x<y。在偏序關(guān)系中,并不是X中所有元素都可比較;如果存在x,yX使得xy與yx中有一個(gè)成立,則稱x與y可比較;如果x,yX,xy并且yx,則稱x與y不可比較。偏序關(guān)系的定義2

定義2設(shè)是X上的一個(gè)偏序關(guān)系,則稱二元組(X,)為偏序集。一個(gè)集合上可能存在多個(gè)偏序集。例1:設(shè)S是一個(gè)集合,S的子集間的包含關(guān)系是不是偏序關(guān)系?在這個(gè)偏序集中,存在著不可比較元素。例如:S={a,b,c},則{a}與{b,c}不可比較。偏序集例如實(shí)數(shù)集上存在(R,)和(R,≥)兩個(gè)偏序集。S的子集間的包含關(guān)系是2S上的偏序關(guān)系,(2S,)是一個(gè)偏序集。3例2:自然數(shù)集合N上的整除關(guān)系“”是不是偏序關(guān)系?自然數(shù)集合N上的整除關(guān)系“”是偏序關(guān)系。

(N,)是一個(gè)偏序集。設(shè)≤是X上的偏序關(guān)系,則≤的逆≤-1也是X上的偏序關(guān)系,以后用“≥”表示≤的逆關(guān)系,并讀成“大于或等于”。若x≥y且xy,則簡(jiǎn)記為x>y。實(shí)例4

定義3集合X上的偏序關(guān)系叫做全序關(guān)系,如果x,yX,xy與yx至少有一個(gè)成立。全序關(guān)系也稱為線性序關(guān)系。X與全序關(guān)系≤構(gòu)成的二元組(X,≤)稱為全序集。偏序集與全序集的主要區(qū)別在于全序集中任兩個(gè)元素均可比較“大小”,而在偏序集中任意兩個(gè)元素不一定都能比較大小。實(shí)數(shù)間的常用的“小于或等于”關(guān)系是不是全序關(guān)系?全序關(guān)系與全序集集合的包含關(guān)系與自然數(shù)間的整除關(guān)系是不是全序關(guān)系?是全序關(guān)系,相應(yīng)的偏序集也是全序集。二者都不是全序關(guān)系。5

定義4設(shè)(X,≤)是一個(gè)偏序集,稱y蓋住x,如果x<y且對(duì)每個(gè)zX,若x≤z≤y,則x=z或y=z。如果y蓋住x,則y被稱為x的后繼,而x稱為y的前驅(qū)。蓋住的定義例3:偏序集(N,≤)中,稱3蓋住2,3是2的后繼,2是3的先驅(qū)。

{1,2,4,6}集合上的整除關(guān)系,2覆蓋1,4和6覆蓋2;但4不覆蓋1.6哈斯(Hasse)圖首先偏序關(guān)系≤是自反的,所以偏序關(guān)系的關(guān)系圖中每個(gè)頂點(diǎn)都有一個(gè)環(huán),因此可以省略每個(gè)頂點(diǎn)的環(huán)。其次由于偏序關(guān)系是傳遞的,那么只要在前驅(qū)與后繼間聯(lián)線即可。最后由于反對(duì)稱性,若x<y,xy,則點(diǎn)y畫(huà)在x的上方,這樣就不必用矢線了,按上述方法畫(huà)出的圖稱為(X,≤)的哈斯圖。

7特點(diǎn):(1)每個(gè)結(jié)點(diǎn)沒(méi)有環(huán);(2)兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過(guò)結(jié)點(diǎn)位置的高低表示,位置低的元素的順序在前;(3)具有蓋住關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊。

哈斯圖就是利用偏序的自反、反對(duì)稱、傳遞性簡(jiǎn)化了的關(guān)系圖。哈斯(Hasse)圖的特點(diǎn)8例4:({1,2,3,4,5,6,7,8,9},R整除)(P({a,b,c}),R)哈斯圖實(shí)例9

例5:已知偏序集(A,R)的哈斯圖如下圖所示,試求出集合A和關(guān)系R的表達(dá)式。A={a,b,c,d,e,f,g,h}

R={(b,d),(b,e),(b,f),(c,d),(c,e),(c,f),(d,f),(e,f),(g,h)}∪IA

哈斯圖實(shí)例10例6:設(shè)A={a1,a2,...,an}是一個(gè)全序集,則其元素(A,≤)的哈斯圖象一條鏈子一樣。所以,全序關(guān)系也叫做線性序關(guān)系,全序集又稱為線性序集??梢浴皬男〉酱蟆迸帕袨椋?/p>

ai1<ai2<...<ain全序關(guān)系的哈斯圖11

定義5設(shè)(X,≤)是一個(gè)偏序集,BX。如果存在一個(gè)元素aX使得對(duì)B中每個(gè)元素x有x≤a,則稱a為B的一個(gè)上界。上界與下界的定義如果存在一個(gè)元素bX,使得對(duì)B的每一個(gè)元素x有b≤x,則稱b為B的一個(gè)下界。①上界與下界都不一定存在。例7:令A(yù)={2,3,6,12,24,36},A在整除關(guān)系“”下構(gòu)成一個(gè)偏序集(A,)。{24,36}不存在上界,②上界與下界可能有很多元素6,12,24,36都是子集{2,3}的上界。{2,3}不存在下界,12

定義6設(shè)(X,≤)是一個(gè)偏序集,BX。如果存在一個(gè)元素aB使得對(duì)B中每個(gè)元素x有x≤a,則稱a是B中的最大元素。①最大元素一定是上界,最小元素一定是下界;最大與最小元素如果存在一個(gè)元素bB,使得對(duì)B的每一個(gè)元素x有b≤x,則稱b是B中的最小元素。②有上下界不一定有最大與最小元素,③最大元素與最小元素若有一定是唯一的。因?yàn)樯舷陆绮灰欢ㄔ谧蛹?13

定義7設(shè)(X,≤)是一個(gè)偏序集,BX。如果B有上界且B的一切上界之集有最小元素,則這個(gè)最小上界稱為B的上確界,記為supB。上確界與下確界的定義如果B有下界且B的一切下界之集有最大元素,則這個(gè)最大下界稱為B的下確界,記為infB。例8:令A(yù)={2,3,6,12,24,36},A在整除關(guān)系“”下構(gòu)成一個(gè)偏序集(A,)。6,12,24,36都是子集{2,3}的上界。6是子集{2,3}的上確界。2,3,6,12都是子集{24,36}的下界。12是子集{24,36}的下確界。14A中有最大元素和最小元素嗎?實(shí)例例9:令A(yù)={2,3,6,12,24,36},A在整除關(guān)系“”下構(gòu)成一個(gè)偏序集(A,)。A中沒(méi)有最大元素也沒(méi)有最小元素。因?yàn)?4與36不可比,2與3也不可比。但是A中沒(méi)有比24和36更大的元素,也沒(méi)有比2與3更小的元素。稱24和36都是極大元素,2與3都是極小元素。15

定義8設(shè)(X,≤)是一個(gè)偏序集,AX,A中元素s稱為A的極大元素,如果A中沒(méi)有元素m使得ms且s≤m。①若A中有極大元素,則極大元素屬于A,而且未必唯一,甚至可能有無(wú)窮多個(gè)。如果A中有元素d,使得xA,若xd,則x≤d不成立,那么d被稱為A的極小元素。②極大元素不一定是最大元素,但最大元素一定是極大元素。同樣若A中有極小元素,則極小元素屬于A,而且未必唯一,甚至可能有無(wú)窮多個(gè)。同樣極小元素不一定是最小元素,但最小元素一定是極小元素。極大元素與極小元素的定義16解:極小元:a,b,c,g;極大元:a,f,h;沒(méi)有最小元與最大元。B的下界和最大下界都不存在;上界有d和f;最小上界為d。實(shí)例例10:設(shè)偏序集(A,≤)如下圖所示,求A的極小元、最小元、極大元、最大元。設(shè)B={b,c,d},求B的下界、上界、下確界、上確界。17畢業(yè)舞會(huì)上,小伙子與姑娘跳舞,已知每個(gè)小伙子至少與一個(gè)姑娘跳過(guò)舞,但未能與所有姑娘跳過(guò)。同樣地,每個(gè)姑娘也至少與一個(gè)小伙子跳舞,但也未能與所有的小伙子跳過(guò)舞。證明:在所有參加舞會(huì)的小伙與姑娘中,必可找到兩個(gè)小伙子和兩個(gè)姑娘,這兩個(gè)小伙子中的每一個(gè)只與這兩個(gè)姑娘中的一個(gè)跳過(guò)舞,而這兩個(gè)姑娘中的每一個(gè)也只與這兩個(gè)小伙中的一個(gè)跳過(guò)舞。

畢業(yè)舞會(huì)問(wèn)題18畢業(yè)舞會(huì)問(wèn)題不失一般性,不妨設(shè)有m個(gè)小伙,n個(gè)姑娘,分別用集合B、G表示:B={b1,b2,…,bm},G={g1,g2,…,gn}.已知每個(gè)小伙子至少與一個(gè)姑娘跳過(guò)舞,但未能與所有姑娘跳過(guò),所以

令Di={gk|與小伙子bi跳過(guò)舞的姑娘gk,k=1,2,…,n},i=1,2,…,m.

則有Di≠,1≤|Di

|≤

n-1,i=1,2,…,m.

同樣地,每個(gè)姑娘也

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論