版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度綠色出行解決方案民間擔(dān)保借款合同4篇
- 男方協(xié)議離婚書(shū)2025年度電子版制作與版權(quán)保護(hù)合同3篇
- 二零二五年度智能電網(wǎng)設(shè)備研發(fā)與銷售合同范本4篇
- 二零二五版內(nèi)資股協(xié)議轉(zhuǎn)讓知識(shí)產(chǎn)權(quán)保護(hù)合同4篇
- 二零二五年度爬架租賃與施工現(xiàn)場(chǎng)環(huán)境保護(hù)合同2篇
- 2025年度城市公園綠地日常養(yǎng)護(hù)維修服務(wù)合同規(guī)范3篇
- 二零二五年度名筑印象住宅電梯品牌代理銷售合同4篇
- 二零二五年內(nèi)蒙古文化旅游融合發(fā)展合同規(guī)范4篇
- 2025年度瓷磚鋪貼與新型建筑材料研發(fā)合同4篇
- 二零二五年度山莊生態(tài)旅游合作開(kāi)發(fā)合同范本2篇
- 二零二五年度無(wú)人駕駛車輛測(cè)試合同免責(zé)協(xié)議書(shū)
- 2025年湖北華中科技大學(xué)招聘實(shí)驗(yàn)技術(shù)人員52名歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- 高三日語(yǔ)一輪復(fù)習(xí)助詞「と」的用法課件
- 毛渣采購(gòu)合同范例
- 無(wú)子女離婚協(xié)議書(shū)范文百度網(wǎng)盤(pán)
- 2023中華護(hù)理學(xué)會(huì)團(tuán)體標(biāo)準(zhǔn)-注射相關(guān)感染預(yù)防與控制
- 五年級(jí)上冊(cè)小數(shù)遞等式計(jì)算200道及答案
- 2024年廣東高考政治真題考點(diǎn)分布匯 總- 高考政治一輪復(fù)習(xí)
- 燃?xì)夤艿滥甓葯z驗(yàn)報(bào)告
- GB/T 44052-2024液壓傳動(dòng)過(guò)濾器性能特性的標(biāo)識(shí)
- 國(guó)際市場(chǎng)營(yíng)銷環(huán)境案例分析
評(píng)論
0/150
提交評(píng)論