離散數(shù)學課件第章2

1離散數(shù)學DiscreteMathematics

汪榮貴教授合肥工業(yè)大學軟件學院專用課件2010.03

學習內容4.1集合的基本知識4.2序偶與笛卡爾積4.3關系及其性質4.4n元關系及其應用4.5關系的閉包4.6等價關系4.7偏序偏序一、偏序

定義1：集合S上的關系R，如果它是自反的、反對稱的和傳遞的，就稱為偏序。集合S與偏序R一起叫做偏序集，記作（S,R）.

例如數(shù)值的≤、≥關系和集合的都是偏序關系。【example1】證明“大于或等于”關系（≥）是整數(shù)集合上的偏序。

solution：因為對所有整數(shù)a，有a≥a，≥是自反的。如果a≥b且b≥a，那么a=b，因此≥是反對稱的。最后，因為a≥b和b≥c，所以≥是傳遞的。從而≥是整數(shù)集合上的偏序且（Z,≥

）是偏序集?！緀xample2】整除關系“|”是正整數(shù)集合上的偏序，因為由前幾節(jié)所述，它是自反的、反對稱的和傳遞的。我們看到（Z+,|）是偏序集（Z+表示正整數(shù)集合）?！緀xample3】證明包含關系是集合S的冪集上的偏序。Solution：因為只要A是S的子集，就有AA,是自反的。因為AB和BA推出A=B，因此它是反對稱的。最后，因為AB和BC推出AB,是傳遞的。因此，是P(S)上的偏序，且（P(S)，）是偏序集。在任意一個偏序集中記號a?b表示(a，b)R.使用這個記號是由于“小于或等于”關系是偏序關系的范例。注意：符號?表示任意偏序關系，并不僅僅是“小于或等于”關系。記號a<b表示a?b但a≠b.如果a<b,我們說“a小于b”或“b大于a”。當a與b是偏序集（S,?

）的元素時，不一定有a?b或b?c。

例如，在（P(Z),）中,{1,2}與{1,3}沒有關系，反之亦然，因為沒有一個集合被另一個集合包含。類似地在(Z,|)中，2與3沒關系，3與2也沒關系。由此得到定義2.定義2：偏序集(S,?)的元素a和b叫做可比的，如果a?b或b?a。當a和b是S的元素并且既沒有a?b，也沒有b?a，則稱a與b是不可比的。【example4】在偏序集(Z+,?)中，整數(shù)3和9是可比的嗎？5和7是可比的嗎？整數(shù)3和9是可比的，因為3|9.整數(shù)5和7是不可比的，因為5不能整除7，并且7也不能整除5.用形容詞“部分的（偏的）”描述偏序是由于一些對元素可能是不可比的。當集合中的每對元素都可比時，這個關系叫做全序。定義3：如果(S,?)是偏序集，且S的每對元素都是可比的，則S叫做全序集或線序集，且?叫做全序或線序。一個全序集也叫做鏈?！緀xample5】偏序集(Z,≤)是全序集，因為只要a和b是整數(shù)，就有a≤b或b≤a。【example6】偏序集(Z+,|)不是全序集，因為它包含著不可比的元素，例如5和7.定義4：對于偏序集(S,?)，如果?是全序，并且S的每個非空子集都有一個最小元素，就稱它為良序集。Forexample，N是自然數(shù)集合，I是整數(shù)集合，≤是小于等于關系，<N,≤>就是良序集。而<I,≤>不是良序集。定理所有良序集，一定是全序集。Proof：

設<A,≤>為良序集,任取x,y∈A,則{x,y}A,它有最小元素。該最小元素或是x,或是y。

于是有x≤y或

y≤x，所以<A,≤>是全序集。定理有限的全序集，一定是良序集。Proof：

設A={a1,a2,…，an},<A,≤>是全序集。假設它不是良序，必存在非空子集BA，B中無最小元素，因B是有限集，必存在x,y∈B,使得x與y之間不滿足≤關系,與≤是全序矛盾?！?lt;A,≤>是良序集。【example7】正整數(shù)的有序對的集合Z+×Z+與?構成良序集，對于(a1,a2)和(b1,b2),如果a1<b1,或如果a1=b1且a2≤b2（字典順序），則(a1,a2)?(b1,b2).在前幾章的學習中我們現(xiàn)實了怎樣使用良序歸納原則證明關于一個良序集的結果。現(xiàn)在我們敘述并證明這個證明技術是有效的。定理1

良序歸納原理設S是一個良序集，如果下述條件成立：

基礎步：P(x0)對S的最小元素為真，且

歸納步:對一切y∈S,如果P(x)對所有的x<y為真，則P(y)為真。那么P(x)對所有的x∈S為真。pr療oo疊f：假若P(省x)不對扶所有織的x∈駛S為真戒。那臨么存齒在一帳個元傻素y撇∈祥S使得P(城y)為假亡。于銹是集贊合A=向{x脈∈災S杏|P(宴x)為假}是非移空的詠。因為S是良鍛序的鋼，集塘合A有最非小元弱素a.易知a不等遵于x0,因為岸從基礎抹步知辟道P(桐x0)為真烤。根據a是選健自A的最珍小元泛素，氧我們篇知道抵對所腰有的x∈孕S持(觸x<a)都有P(柔x)為真?zhèn)颉Ｓ缮w歸納降步這退就可駁以退置出P(斬a)為真逼。這個細矛盾斧就證遞明了P(唱x)必須頑對所范有x∈雜S為真鹿。二、仰字典喉順序字典聞順序是以千字母縫表中狹的字冠母順站序為綿基礎粥的。猾這是蜻從一跡個集怠合上梯的偏查序構唐造一押個集蔬合上向的串各的序振的特注殊情緒況。孝我們迅將說騎明這滑種構招造在軋任一爪個偏濁序集昌上是系怎么宵做的且。首先恨，我引們將雨說明愛怎樣狼在兩捆個偏孩序集(A1,?1)和(A2,?2)的笛卡爾車積上次構造訴一個伴偏序粉。在A1×A2上的殘字典呀順序捎定義抽如下補：如芽果第雷一個湖對的巴第一興個元素血（在A1中）燃小于刷第二額個對毫的第姑一個榨元素份，或突者第序一個日元素相騰等，蕩但是勝第一議個對揚的第往二個介元素咐（在A2中）腔小于蛾第二岔個對的床第二樂個元竊素，蛾那么偶第一狹個對庸小于濁第二晃個對語。換牧句話技說，(a1,裕a2)小于(b1,b2),即(a1,孩a2)<欲(b1,b2)或者a1<1b1,或者a1=b1且a2<2b2.把相溪等加盲到A1×A2上的披序就脊得到御偏序?。【e身xa卷mp筆le赴8扎】確定咬在偏烤序集升（Z×弟Z，?）中沾是否特有(3擔,龍5)<械(4洲,8撕),諒(戶3,威8)妥<(侵4,砌5)和(4啟,9河)戰(zhàn)<(寧4,劉11構)蔽?這里嬌的?是從Z上通淘常的≤關熟系構銹造的形字典湊順序神。So衫lu六ti改on：因為3<畫4,故而(3授,誘5)<均(4扭,8迎),且(3若,8越)<蹈(4屋,5袋)。因迫為(4擊,9汪)與(4旺,1武1)的第抓一元德素相乳同，底但9<都11碧,我們犬有(4敘,9姜)待<(殊4,氣11隆)。下圖港明顯熄地顯批示了Z+×Z+中比(3取,4帳)小的捎有序北對的州集合吊。可以踩在n個偏杯序集(A1,?1),室(孝A2,?2),…,(An,?n)的笛介卡爾積上紗定義丹字典塔順序健。如下錄定義A1×A2×…×An上的拜偏序狼?餅：餅如果a1<b1,或者溉存在犧整數(shù)i>話0是的a1=b1,…臉,ai=bi,且ai+抖1<i+干1bi+故1,那么(a1,a2,…聞,an)<舊(b1,b2,…bn)換句始話說像，如由果在朽兩個n元組哄不同姿元素居出現(xiàn)達的第錘一位揉置上而等一個n元組掩的元刻素小型于第凝二個n元組逼的元捆素，陽那么臉第一貞個n元組互小于第誕二個n元組連?！緀取xa畢mp佳le侵9鳳】注意懶（1，2，3，5）<（1，2，4，3），倉因為蔑這些4元組耀的前倡兩位篇相同堡，但疤是第慢一個4元組耳的第涌三位3小于自第二姥個4元組被的第陵三位4（這掃里的4元組誕上的候字典仰順序剃是整狗數(shù)集旦合上擊的通常的制“小碌于或蹄等于像”關妹系導腸出的趴字典架順序句）。我們挑現(xiàn)在盛可以障定義翻串上綱的字浙典順概序。最考慮宴偏序房誠集S上的爐串a1a2…an和b1b2…bn,假定紹這些崇串不唐相等起。設t是m，n中較的小的蠅數(shù)。定義填字典蜻順序秤如下府：a1a2…an小于b1b2…bn,當且勻僅當（a1a2…at）<（b1b2…bt）蒜或話者（a1a2…at）=（b1b2…bt）并熔且m<軍n其中效這個歡不等治式中雜的<表示St中的幕字典壘順序滋。換盤句話搭說，采為確范定兩個不麥同串蛙的序梨，較斃長的鏟串被植切到竟較短監(jiān)的串播的長鞏度t，即t=mi狀n(盟m,葬n)然后使丈用St上的仁字典診順序梯比較灣每個鈔船的往前t為組晶成的t元組樓，如孟果對櫻應于第一帖個串導的t元組豬小于作第二尊個串舌的t元組侵，或之者這叼兩個t元組坦相等螞，但稈是第二講個串擊更長數(shù)，那踩么第窯一個血串小丑于第攻二個牛串?！緀然xa返mp筍le炕1幻玉0】考慮媽小寫筆英語常字母基串構莖成的每集合屯。使山用在蓬字母泄表中謀的字負母序釣，可漸以構皂成在材串的鞋集合錄上的則字典極順序非。如果墻兩個翁串第順一次不出現(xiàn)罪不同殘字母眼時，逝第一舞個串夏的字遺母先賤于第扁二個醉字母卻，或齊者如帆果第精一個雕串和訊第二側個串軌在所丈有的戲位都旬相同檢，但死是第氧二個紋串有茄更多列的字分母，秋那么才，第室一個滔串小修于第軍二個籮串。焦這種視排序士和字易典使架用的村排序菜相同葉。例以如di顏sc檔re分et蘇<盞d蹦is壯cr坡et憑e因為輪這兩秒個串敬在第7位首色次出否現(xiàn)字屑母，傷并且e<攏t迫.di蕉sc寺re卡et懶<霧d嫩is啊cr家ee他tn駐es梳s因為頌這兩招個串普前8個字調母相群同，匆但是臨第二底個串束更長勇。此遞外di補sc蝴re襯te治<該d冒is押cr它et坐io錢n在有嗽窮偏惜序集弦的有帽向圖姜中有閃許多言可以此不必殲顯示毀出來蘆，因迎為他責們是喘必須雙存在駕的。例如或，考礦慮在伶集合{1，2，3，4}上的尤偏序{(隱a,濕b沈)|禽a≤b}的有串向圖酒，參鉛見圖a。因癢為這樂個關寒系是渣偏序落，它演是自探反的謠并且角有向捏圖在柔所有仿的頂帆點都越有環(huán)渣，因仿此，挺我們散不必片顯示旬這些設環(huán)，銹因為耐它們鴨是必印須出鋪現(xiàn)的需。在內圖b中沒燥有顯肅示這消些環(huán)乒。由政于一鎮(zhèn)個偏泉序是湊傳遞戒的，參我們劈燕不必轉顯示縮慧那些扮由于遭傳遞婆性而悉必須站出現(xiàn)溜的邊茶。例售如，聲在圖c中沒漢有顯搭示邊(1新,3鄰),綿(1鹿,4對)和(2飛,4肺)，因爪為它她們是耕必須摘出現(xiàn)滑的。屬如果序假設論所有墾的邊產的方設向是啊向上反的，味我們思不必賊顯示笛邊的窄方向汪；圖c沒有售顯示睛方向愉。三、稈哈塞雄圖（Ha尺ss燒e圖）我們搬可以糠使用砌下面異的過遲程表患示一軌個有謙窮集貢上的父偏序萍。從這徐個關派系的警有向事圖開尺始：童(1脹)自反情性：紹每個節(jié)頂點蠶都有擾自回州路，超省去做。(2艦)反對退稱性棉：兩末個頂癥點間焦只可滅能有旬一個軟箭頭破從左務→蹦右，令或從雀下→上的庭方向爐從小四到大伙安置默頂點帥，可秒省略望箭頭減。(3食)傳遞般性：膜由于科有(a洪,b聚)，(b祝,c利)∈磚R則(a福,c共)前∈R故只鄰畫(a喪,b軍)，(b奪,c萬)對應諷的邊,省略槍邊(a妻,c溝)。完成縣以上簡步驟憐就得椅到一俗個包頃含著魂足夠食表示治偏序景信息師的圖賄，這掙個圖叫廊作哈塞勒圖哈塞格圖（Ha袖ss蜘e圖）定義擁：設?是Ａ庸上的貞一個督偏序衡關系沸，如恨果a?b，則聽將ａ鄭畫在ｂ下愈面，摸且不ｃ，油使a?c，c?b，則日ａ，搶ｂ間報用直驢線連接。引并符瀉合簡旱化的閣關系寸圖的好繪制菊，稱鉗這樣細得到碎關系笨圖為哈塞研圖（Ha既ss藏e圖）。2920脫23選/5盞/1訓8【e唇xa成mp蠶le動1忘1】畫出艇表示{1，2，3，4，6，8，12判}上的沉偏序{(a,莊b)灣|a整除b}的哈擔塞圖派。Sol湖ut萄io盾n：由這厭個偏討序的膠有向告圖開載始，飾如下續(xù)圖a所示餃。移梅走所藏有的屋環(huán)，如下戲圖b所示澆，然面后刪過去所杜有由判傳遞率性導愚出的淚邊。批這些烤邊是(1電,4手),域(1靈,6傻),銅(1噴,8喉),修(1葬,1獨2)編,(娘2,鎮(zhèn)8)院,(宜3,抱12馬).排列棕所有健的邊姑使得渴方向甚向上，并融且刪抗除所抖有的余箭頭速得到童哈塞絮圖。歌結果痛如圖c所示搏?！緀口xa曉mp念le下1備2】畫出猛冪集P(哪S)上的糠偏序{(冠A,譽B編)彼|增AB}的哈能塞圖，亞其中S=中{a凍,內b,朵c牙}.Sol彎ut超io唱n點:關于花這個箭偏序善的哈介塞圖侮是由鉤相關標的有呢向圖磚得到殖的，角先刪建除所有的竭環(huán)和懷所有鏈的由嗓傳遞孟性產塞生的郊邊，傳即(Φ,漲{僑a,房誠b賽}),齡(Φ,矮{撈a,朗c雁}),購(Φ,課{吩b,攝c咸}),淋(Φ,仙{院a,職b寶,拴c}),({柴a宏},把{紫a,網b飼,圣c}),值(劉{懪?樹{a伶,計b,槽c齡})和({燈c}師,嘩{a嘩,框b,膽c每})憑.最后窩，使垃所有賊的邊頭方向外向上拍并刪曲除箭凝頭。志得到越哈塞貓圖如錦下所示。【e愚xa陶mp怨le青】：Ａ＝愁｛１纖，２增，３飲，４助，５光，６末，７勝，８愧，９管｝Ｂ＝篇｛ａ欲，ｂ裁，ｃ哀｝Ｒ1＝｛獸（ａ成，ｂ杠）｜覆ａ≤ｂ，盤ａ，旱ｂ∈Ａ｝Ｒ2＝｛縣（ａ虛，ｂ狹）｜橫ａ|ｂ，虜ａ，華ｂ∈Ａ｝Ｒ3＝｛(s京1,未s2幣)｜s1s2，s1，s2事∈p仙(B怎)｝求R1,叉R2,猴R3所表數(shù)示關困系的曠哈塞會圖。1

2

3

4

5

6

7

8

9

123456789Φ{a}{c}{a,b}{a,c}{a,c}{a,b,c}具有蓬極值案性質慢的偏晶序集認元素圓有許織多重猴要應攏用。偏序秤集的辣一個幅元素憶叫做抓極大澆的，宣當它蹈不小魂于這串個偏鈴序集割的任站何其稅他元事素。激即a在偏濤序集（S，?）中薦是極大蛙的，當冰不存半在b∈S使得a<緞b.類似杯地，提偏序塞集的釘一個燥元素需叫做喘極小黎的，被如果羅它不閉大于侵這個粥偏序引集的圖任何評其他染元素余。即a在偏拘序集伸（S，?）中拔是極小退的，如憤果不筍存在b∈S使得b<劃a。使用率哈塞拴圖很獻容易晝是識魚別極每大元堆素和送極小深元素草。它次們是困圖中列的“油頂”起元素載與“燦底”疲元素佛。四、添極大貫元素標與極喚小元腹素[定茫義]極大爸元與泉極小摸元：設（S，?）是麥偏序芽集，傲若ａ股∈S，且腦在S中找妙不到砌一個元素b（b≠僵a），站使a?b（b?a），頓則稱a為A中的極大駛元素（極怠小元燙素）峰。y是B的極小廁元素y遮(y辜∈曉B夾∧內繳x富(株x攝∈B響∧顧x燭≠籃y歌∧跟x溜≤利y志))y是B的極大獨元素y麻(y靠∈挑B棄∧津狗x蠻(景x餡∈變B年∧踩x鵝≠陵y繩∧互y糊≤宅x)噸)【e隆xa紹mp角le配】（N，|）是偏島序集勒，A=｛2，3，4，5，6，7，8，9｝則Ａ中吸極大塑元素可：８藍，６阻，９猜，５展，７極小眼元素說：２售，３意，５扶，７注：極大零元，萍極小圖元并驢不要檔求唯港一，厘且同撤一元悠素，囑可以衡既是賄極大拖元，辯又是汗極小馬元，著如５醉，７巖。極大合元，滴極小沉元必僚須是麗子集血Ａ中膏的元峰素。23576489【e雷xa評mp鏟le浮1涉3】偏序別集（{2，4，5，10，12，20，25眉}，|）的哪些究元素維時極炒大的港，哪律些是努極小座的？Sol啦ut畫io刮n：右圖撐關于暗這個騙偏序影集的妹哈塞炮圖顯示泥了極練大元對素是12，20和25，極小妄元素休時2和5。通過禍這個胖例子騎可以諒看出礎，一歷個偏電序集兼可以恨有多由于一襪個的忠極大眠元素冠和多于括一個僑的極旱小元遍素。在偏倉序集痕中存瞇在一迫個元皇素大期于每榴個其廳他的右元素沈，這遲樣的職元素痰叫做起最大訓元素習，即a是偏系序集坦（S，抽?收）的最大封元素，當章對所肥有的b∈S有b?a。當幕最大簽元素逼存在出時它獅是唯駛一的獲。類似走地，賣一個斧元素陷叫做測最小置元素仰，當伐它小謠于偏郊序集椒的所杏有其胳他元翅素。爺即a是偏墓序集雕（S，鼠?油）的最小輝元素，如歌果對保所有撇的b∈S有a?b。當才最小特元素讀存在病時它墾也是籍唯一碧的。4020作23逆/5務/1漆8[定商義]最大葡元素僵與最醫(yī)小元窩素：設（S，?）是貝偏序發(fā)集，堂，若安ａ∈環(huán)Ａ，ｂ∈撒Ａ，序ｂ?ａ(ａ?ｂ）若，則次稱ａ怒為Ａ啦的最大李元素奶（最托小元輕素）?！緀爛xa壟mp禿le串】上例般中其Ha凳ss止e圖如框下圖分所示23576489結論先：子集店Ａ中齒是不個存在球最大賣元（逢最小貸元）肉的。[定理]<A閥,?>是偏借序集戰(zhàn)，B是A的非循空子軟集，蟻如果B有最鑰小元驕素(最大傲元素)，則稠最小桃元素(最大踢元素)是唯盯一的惡。pr券oo霜f：假設B有兩攔個最李小元豈素a、b,則鉗因為a是最小理元素謹，b∈B，根據最小肝元素落定義戴，有a?b;類似露地，鞭因為b是最小泡元素筍，a∈B，根男據最小炊元素燃定義貴，有b?a。因省為?才有反橫對稱營性，調所以另有a=英b。同理冷可證最大皮元素救的唯鑼一性亞。小結蘿：<A準,≤熔>是偏特序集想，B是A的非庸空子波集，濕則⑴B的極小(大)元素耳總是符存在章的，裙就是丹子集盾中處肌在最紗下(上)層的雀元素約是極參小(大)元素禁。⑵B的最小濟元(最大尿元)素有孝時可鍛能不蕩存在閘，只才要有鉗唯一襲的極硬小(大)元素仙，則憐這個貢極小(大)元素庭就是鉤最小(大)元素案。否秘則就棄沒有夜最小(大)元素我。【e閣xa察mp酒le敘1口4】確定壓下圖徑的每準個哈候塞圖鼻表示輕的偏宿序集桶是否哈有最大元林素和群最小誘元素鏡。So令lu潑ti統(tǒng)on：哈塞鈴圖(a師)的偏振序集蘭的最搞小元奪素時a。這棗個偏乒序集專沒有夏最大波元素。哈塞不圖(b您)的偏局序集榆既沒晚有最短大元紀素也駛沒有鋒最小勿元素俗。哈塞腹圖(c悔)的偏衡序集娛沒有裳最小插元素獻，它冬的最晃大元由素時d。哈塞黎圖(d去)的偏樸序集驕有最鞏小元行素a和最駛大元顏素d。【e誓xa伶mp屋le旱15挺】設S是集鑒合。剛確定旱偏序巾集（P(獎S)琴,）中勇是否燭存在進最大起元素飄與最盼小元泊素。Sol饅ut悲io鉤n：最小死元素倒時空漸集。艙因為煙對于S的任愚何子嶼集T,有ΦT，集爬合S是這個版偏序么集的恩最大放元素膽，因擠為只道要T是S的子小集，恒就有T牧到S。4620忽23尋/5哄/1換8【e筑xa道m(xù)p掩le衣1袍6】在偏騾序集圣（Z+,宣|）中撫是否量存在跨最大辮元素浩和最小安元素唉？So延lu吵ti臟on：1是最造小元單素，寨因為賽只要n是正初整數(shù)夏，就餓有1|正n。因激為沒有被亮所有斬正整制數(shù)整隸除的島整數(shù)扎，所烤以不觸存在擁最大星元素銜。4720濁23劈燕/5陪/1銷8有時催可以但找到沖一個臉元素減大于凡偏序殊集（S，稱?沿）的蕉子集A中所叮有的亮元素馬。如弱果u是S的元童素使院得對苦所有蚊的元冰素a∈A氏,有a?u，那案么u叫做A的一個淺上界。也可惜能存偏在一鳥個元佛素小建于A中的室所有哈的其諸他元隔素。邊如果l是S的一啄個元話素使及得對崖所有束的元谷素a∈A勤,有l(wèi)?a，那節(jié)么l叫做A的一個悼下界。[定甘義]上界端與下止界：設（P,?）是味半序切集，AP，若a∈該P，對b∈白A,調b?a（a?b）稱a為A的上界床（下些界）。【e亦xa哪mp釀le編】：B=業(yè){a離,b掠,c腐},融R3={公(港s1,s2)狀|喇s1s2，s1∈P長(B傍)隨},灰(晶P(鍋B)乏,)是偏廢序集腐。設Ａ＝{Ф，{a漠},澆{b末},第{c戶},拖{a遍,c派},兵{a由,b襯},微{a援,c校}}其Ha森ss伐e圖如析右圖剃所示:Φ{a}{c}{a,b}{a,c}{b,c}注：（1）上漫例中瓣，Ａ飄無最鑒大元葛素，脊但存決在Ａ什的上鳳界｛ａ粉，ｂ序，ｃ脊｝。（2）Ф為Ａ婚的最憐小元李，也盤是Ａ婆的下價界。（3）最鑒大（促小）菠元素蹄是Ａ艘的一決個上莊（下艷）界惱。（4）上作（下既）界死可以改不唯結一，橡也可為以不弊存在吊。【e拼xa歌mp緞le蹦1扒7】找出歡下圖目所示假哈塞喇圖的俊偏序談集的狗子集{a鐵,寸b,訴c隨},{j路,潔h}和{a，c，d，f}的下到界和葡上界蠻。Sol命ut草io娃n：{a，b，c}的上我界是e,閣f糊,貝j和h，它機的唯漆一的光下界華是a。{j，h}沒有皂上界齡，它甘的下樂界是a，b，c，d，e和f.{a愧,叨c,鑄d窯,朵f智}的上認界是f，h和j，它礎的下才界是a。元素x叫做痛子集A的最小需上界奶（上筐確界元），如戲果x是一尤個上葡界并陰且它政小于A的其憂他上鎖界。她因為末如果譯這樣急的元炮素存予在，懲只存峽在一收個，首稱這暴個元鉗素為純最小少上界鍛（上活確界輝）是采有意搜義的震。即屠如果跟只要a∈偽A就有a?x，并滾且只侄要z是A的上載界，螺就有x?z,獄x就是A的最縱小上殺界（巡壽上確盆界）罰。類似紫地，執(zhí)如果y是A的下幅界，見并且辮只要z是A的下詠界，蓮就有z?y，y就是A的最大糟下界城（下旨確界誓）。A的最向大下策界（兔下確粉界）獸如果童存在飾也是近唯一記的。一個攤子集A的最沈大下魚界（勿下確弓界）談，和邪最小跨上界漁（上懲確界頑），雕分別狼記作gl再b(我A吼)和lu司b(猴A追).[定哪義]上確園界與伐下確退界：設（S，≤坡）是之偏序樹集，AS，若a是A的一選個上閑界（下檢界）倡，而A的上殘界（期下界料）z，都朝有a征≤憶b（b璃≤見a），則且稱a是A的上確遼界（廁下確渾界）。【e偏xa艘mp舉le筍】給定領（A,圓≤）的菊哈塞圖如繳圖所同示：６°１°３°12°２°36°

<C,≤>

24°子集B上界下界{2,3}{1,2,3}{6,12,24}C

16,12,24,361241,2,3,61無6,12,24,36上確界下確界6624無1161【e赴xa邊mp蜂le何1辨8】在下狂圖所扇示偏長序集茂中如鏈果{b，d，g}的最救大下巷界和竄最小系上界允存在死，求紐奉出這是個最誰大下穩(wěn)界和漁最大沈上界耽。So臣lu費ti瓜on：{b，d，g}的上貧界是g和h。因孟為g含<竹h,渣g是最揮小上該界。{b，d，g}的下苗界是a和b，因蹈為有a莖<柜b,南b是最大籍下界洋?！緀球xa匪mp好le私1舒9】在偏察序集槍（Z+食,誰|）中沫，如敞果集抖合{3，9，12圍}和{1，2，4，5，10鉆}的最蛙大下秤界和胳最小絹上界痛存在碗，求濱出這結些最僻大下界蹈和最愛小上嚇界。Sol唯ut洲io符n：求最貓大下潔界：如果3，9，12被一爆個整種數(shù)整牽除，夫那么健這個話整數(shù)啊就是{3，9，12犧}的下柳界。爺這樣牛的整腰數(shù)只蔽有1和3.因為1|面3，3是{3，9，12導}的最設大下灑界。集合{1，2，4，5，10狐}關系漠到|的下油界只待有1，因躬此1是{1，2，4，5，10梁}的最肅大下愚界。求最搭小上緒界：一個振整數(shù)役是{3，9，12給}的上戶界，起當且波僅當坑它被3，9和12整除。具遭有這診種性予質的刊整數(shù)篩就是驕那些僅被3，9和12的最帝小公連倍數(shù)36整除的夕整數(shù)梢。因晴此，36是{3，9，12核}的最蠶小上數(shù)界。一個寺正整固數(shù)是達集合{1，2，4，5，10例}的上晴界，昆當且屈僅當制它被1，2，4，5，10整除組，具粘有這否種性德質的設整數(shù)鵝就是根被這住些整探數(shù)的忠最小公蹈倍數(shù)20整除換的整散數(shù)。極因此撥，20是集吧合{1，2，4，5，10鑒}的最小借上界汪。五、冬格在這減里我塘們引磨入格炸的概霸念。定義居：設X,?是偏趁序集缺，如跨果x,yX，集剛合{x,y}都有最小爭上界碼和最澤大下待界，翠則稱X,?是格升?！緀獄xa儲mp僻le熟2筋0】確定鵲如下之圖所漆示的動每個遲哈塞供圖表擁示的設偏序獵集是葛否是米格Sol安ut爹io更n：圖a和c中的逮哈塞會圖表赤示的膚偏序仍集是記格。親因為龜在每柏個偏汁序集摟中每對窄元素豆都有駛最小德上界蠟和最榜大下爪界。另一太方面楚，圖b所示誦的哈各塞圖惡的偏而序集扇不是日格，艇因為企元素b和c沒有舌最小勤上界睛。為福此只陪要注熔意到d，e和f中每況一個躁都是童上界綁，但這3個元籌素的扮任何墊一個椅關于朋這個妥偏序惑集中理的序口都不紙大于轟其他2個.【e巖xa導mp偷le中】下列穩(wěn)各集揪合對艇于整患除關累系都徹構成何偏序崗集,判斷息哪些爛偏序集集是坐格?⑴懼L=｛1,涼2,象3,駝4,耳5｝；⑵L=｛1,謝2,鵲3,條4,陜6,犯9,紡12赤,1京8,第36｝；⑶L=｛1,燃2,終22,…忽,2n｝；⑷L=｛1,終2,役3,毫4,準5,煤6,必7,賴8,慰9,雅10｝Sol匙ut含io陶n：⑴不思是，丑因為L中的賭元素翁對{2誓,3張}沒有綱最小晴上界欠；⑵是瞇，因世為L=｛1,錦2,層3,肅4,飯6,綱9,舞12清,1演8,邊36｝任鎖何一舞對元棚素a,b，都宗有最酷小上切界和傭最大鄰下界廈；⑶是鳳，與稱⑵同賓理；⑷不娛是，覽因為L中的貢元素半對{6盛,7堡}沒有捕最小諸上界跪不存球在最姿小上摧界.【e仆xa面mp朝le侵】下圖織中給杏出了怕一些戴偏序夾集的沙哈斯忌圖，梳判斷微它們掏是否構成藥格。So河lu茅ti則on：它們蜘都不棕是格震。在(a壓)中，{1,犁2}沒有辣下界惰，因孟而沒支有最確大下脈界。在(b產)中，{2,犁4}雖有伏兩個焰上界窗，但轉沒有棚最小苦上界后。在(c流)中，{1,技3}沒有肝下界蕉，因雕而沒響有最溉大下為界。在(d伯)中，{2,批3}雖有宴三個綠上界金，但運沒有辨最小賞上界譽。【e亮xa廁mp定le往2店1】偏序抹集（Z+,衰|）是書格嗎企？Sol頭ut檔io急n：設a和b是兩頓個正忽整數(shù)痰，這紅兩個曠整數(shù)投的最逗小上分界和浮最大頸下界職分別是繭它們餃的最皺小公萬倍數(shù)帽和最過大公刻約數(shù)灶，因院此這盼個偏蠟序集斜是格畢?！緀喇xa厭mp障le柏2載2】確定狠偏序呈集（{1，2，3，4，5}，|）和（{1，2，4，8，16必}，|）是忙否為機格？Sol樹ut駛io曠n：因為2和3在（{1，2，3，4，5}，|）中仙沒有附上界顧，它揪們當然譯沒有骨最小借上界規(guī)。因圣此第盼一個臭偏序仰集不聞是格駱。第二偽個偏渠序集宏的每約兩個章元素威都有榮最小橋上界餐和最蹄大下曾界。薄在這個饑偏序咐集中傅兩個藥元素咸的最冬小上遞界是虹他們計中間杰較大擱的元脅素，而兩岔個元狹素的螞最大碑下界故是它旨們中暈間較累小的瘦元素企。因盡此第箭二個偏序毀集是敢格?！緀偽xa孟mp尖le墓2侮3】確定念（P(扣S)厭,）是扛否為租格，旗其中S是集附合。Sol抄ut重io勤n：設A和B是S的兩長個子晉集，A和B的最側小上迷界和殲最大舟下界厚分別榮是A∪浮B和A譜∩務B，因遍此（P(魚S)腹,）是拋格?！緀潮xa道m(xù)p慢le診2新4】信息涉流的看格模豆式在許鎖多設刻置中殿，從捏一個蒸人或計算蔽機程百序到蠻另一至個人迅或計錄算機怎程序萍的信唇息流扭要受療到限關制，貞這可以通桶過安磨全權伸限來圈實現(xiàn)剛。我供們可摔以使隸用格染的模竊型來體表示探不同貢的信息流化策略銀。例如阻，一胸個通吼用的殖信息隸流策優(yōu)略適新用于詞政府艷或軍唯事系紗統(tǒng)中押的多級安沒全策趁略。為疼，誒稠組信要息分礎配一棵個安事全級冤別，里并且掛每個覽安全溉級別用鎮(zhèn)一個生對（A,廈C）表頓示，摟其中A是權恭限級糠別，C是種濱類。饒然后允許雕人和稼計算仿機程昨序從殺一個辟被特筆別限扶制的鞏安全菊類的難集合糞中訪嘴問信息。在美胳國政址府中科，使宣用的撫典型司的權雙限級翼別是儀不保爪密（0）、福秘密（1）、收機密州（2）和陡絕密燥（3）。鳥在安朽全級批別中收使用逮的種鋤類是蛇一個集怖合的習子集衫，這呈個集狼合含器有與同一個陜特定頓行業(yè)矩領域開相關撤的所蛙有的分部交，每或個分頑部表舊示一籃個指養(yǎng)定的手對象躁域。例如辭，如讓果分污部的好集合據是{間諜擔，鼴觸鼠。百雙重男間諜}，那帳么存在8個不棉同的分種類競，分孔部集雕合有8個子認集，昌對于姥每個拌子集詠有一吹類，例融如{間諜瓣，鼴嗚鼠}。我們揀可以搖對安毛全類貍排序胖，規(guī)僚定（A1,C1）?（A2,C2）當罪且僅醉當A1≤A2和C1≤C2.信息貍允許巧從安幫全類麥（A1,C1）流向佳安全悲類（A2,C2）當習且僅掀當（A1,C1）?（A2,C2）佩。例如才，信添息允覆許從繭安全帖類（攪機密或，{間諜疫，鼴感鼠}）流陣向安旋全類（危絕密決，{間諜淋，鼴土鼠，苗雙重蝴間諜}），桐反之州，信無息不茄允許讀從安全類吩（絕咽密，{間諜物，鼴蓮鼠}）流軋向安值全類走（機招密，{間諜孔，鼴把鼠，雙防重間饞諜}）或解（絕稼密，{間諜}）。六、企拓撲節(jié)排序假設捉一個植項目條由20個任臂務構章成。相某些竄任務竹只能勉在其補他任袍務結束之眠后完裂成，感如何法找到躬關于岡這些托任務權的順捆序？為了由對這董個問揉題構嬌造模悠型，始我們住建立槍一個幫任務乎集合聲上的竄偏序著，使得a<奮b,當且飯僅當a和b是任軌務且預直到a結束艇后b才能普開始鏟。為榴安排好乏這個掩項目勺，需鏈要得限出與考這個辰偏序傘相容握的所辭有20個任鹿務的谷順序。選我們度將說蠟明怎哭樣做卡到這菜一點川。從定斃義開鋒始，言如果痛只要aR堂b就有a置?b紀,則稱其一個賞全序?與偏饒序R是相容岸的。從狂一個灰偏序館構造趙一個哄相容象的全跌序叫錯做拓撲鑼排序。需通要使浸用引體理1.引理1：每個曉有窮碑非空耀偏序巴集（S,挎?）都砌有極膜小元自素。Pro您of：選擇S的一骨個元腹素a0.如果a0不是邪績效匪元素房誠，那凱么存房誠在元柴素a1,滿足a1<魚a0.如果a1不是癥極小允元素傲，那乖么存網在元縫素a2,滿足a2<妨a1.繼續(xù)聚這一遺過程痰，使案得如伐果an不是旅極小清元素收，那芝么存我在元菜素an+婆1滿足an+速1<an.因為靈在這漂個偏趨序集魂只有減有窮向個元藍素，技這個傲過程蹄一定制結束并商且具燃有極盤小元遍素an.我們外將要撓描述頌的拓槽撲排異序算具法對沿任何壟有窮講非空阻偏序革集都曉有效為在完偏序認集（A,?）上妻定義暑一個扇全序奪，首孟先選理擇一湊個極稀小元素a1；由危引理1這樣值的元背素存讀在。朋接著話，{A絞-{庭a1}，?}也是縮慧一個偏序公集。胸如果挎它是儉非空衫的，紀選擇清這個微偏序計集的厲一個透極小稀元素a2.然后米再取蘋走a2，如快果還形有其昌他的借元素須留下仇來，哪在{駁