離散數(shù)學(xué)課件-第4章-7.ppt

1、1,離散數(shù)學(xué) Discrete Mathematics,汪榮貴 教授 合肥工業(yè)大學(xué)軟件學(xué)院專用課件 2010.03,學(xué)習(xí)內(nèi)容,4.1集合的基本知識(shí) 4.2 序偶與笛卡爾積 4.3 關(guān)系及其性質(zhì) 4.4 n元關(guān)系及其應(yīng)用 4.5 關(guān)系的閉包 4.6 等價(jià)關(guān)系 4.7 偏序,偏序,一、偏序 定義1：集合S上的關(guān)系R，如果它是自反的、反對(duì)稱的 和傳遞的，就稱為偏序。 集合S與偏序R一起叫做偏序集，記作（S,R）. 例如數(shù)值的、關(guān)系和集合的都是偏序關(guān)系。,【example 1】證明“大于或等于”關(guān)系（ ）是整數(shù)集合上 的偏序。 solution： 因?yàn)閷?duì)所有整數(shù)a，有a a， 是自反的。 如果a b且

2、b a，那么a=b，因此是反對(duì)稱的。 最后，因?yàn)閍 b和b c，所以是傳遞的。 從而是整數(shù)集合上的偏序且（Z, ）是偏序集。,【example 2】整除關(guān)系“ | ”是正整數(shù)集合上的偏序，因?yàn)橛汕?幾節(jié)所述，它是自反的、反對(duì)稱的和傳遞的。我們看到 （Z+, | ）是偏序集（Z+表示正整數(shù)集合）。,【example 3】證明包含關(guān)系是集合S的冪集上的偏序。 Solution： 因?yàn)橹灰狝是S的子集，就有A A, 是自反的。 因?yàn)锳 B和B A推出A=B，因此它是反對(duì)稱的。 最后，因?yàn)锳 B和B C推出A B, 是傳遞的。 因此， 是P(S)上的偏序，且（ P(S) ， ）是偏序集。,在任意一個(gè)偏

3、序集中記號(hào)a b表示(a，b)R.使用這個(gè)記號(hào) 是由于“小于或等于”關(guān)系是偏序關(guān)系的范例。 注意：符號(hào) 表示任意偏序關(guān)系，并不僅僅是“小于或等于”關(guān)系。 記號(hào)ab表示a b但ab.如果ab,我們說(shuō)“a小于b”或 “b大于a”。 當(dāng)a與b是偏序集（S, ）的元素時(shí)，不一定有a b 或b c。 例如，在（P(Z), ）中,1,2與1,3沒(méi)有關(guān)系，反之亦然，因?yàn)?沒(méi)有一個(gè)集合被另一個(gè)集合包含。類似地在(Z,|)中，2與3沒(méi)關(guān)系，3 與2也沒(méi)關(guān)系。由此得到定義2.,定義2：偏序集(S, ) 的元素a和b叫做可比的，如果a b 或 b a。當(dāng)a和b是S的元素并且既沒(méi)有a b，也沒(méi) 有b a，則稱a與b是

4、不可比的。 【example 4】在偏序集(Z+, ) 中，整數(shù)3和9是可比的嗎？5 和7是可比的嗎？ 整數(shù)3和9是可比的，因?yàn)?|9.整數(shù)5和7是不可比的，因?yàn)? 不能整除7，并且7也不能整除5.,用形容詞“部分的（偏的）”描述偏序是由于一些對(duì)元素可能是不可比的。當(dāng)集合中的每對(duì)元素都可比時(shí)，這個(gè)關(guān)系叫做全序。 定義3：如果(S, ) 是偏序集，且S的每對(duì)元素都是可比的，則S叫做全序集或線序集，且 叫做全序或線序。一個(gè)全序集也叫做鏈。,【example 5】偏序集(Z, )是全序集，因?yàn)橹灰猘和b是整數(shù) ，就有a b或b a。 【example 6】偏序集(Z+, | )不是全序集，因?yàn)樗?/p>

5、著不可比的元素，例如5和7.,定義4：對(duì)于偏序集(S, ) ，如果是全序，并且S的每 個(gè)非空子集都有一個(gè)最小元素，就稱它為良序集。 For example， N是自然數(shù)集合，I是整數(shù)集合，是小于等于關(guān)系，就是良序集。而不是良序集。,定理 所有良序集，一定是全序集。 Proof： 設(shè)為良序集,任取x, y A, 則x, y A, 它有最小 元素。該最小元素或是x,或是y。 于是有x y或 y x，所以是全序集。,定理 有限的全序集，一定是良序集。 Proof： 設(shè)A=a1, a2, ，an, 是全序集。 假設(shè)它不是良序，必存在非空子集BA，B中無(wú)最小元素， 因B是有限集，必存在x, y B,使得

6、x與y之間不滿足關(guān)系,與 是全序矛盾。 是良序集。,【example 7】正整數(shù)的有序?qū)Φ募蟌+Z+與構(gòu)成 良序集，對(duì)于(a1, a2)和(b1, b2),如果a1b1,或如果a1=b1 且a2 b2（字典順序），則(a1, a2) (b1, b2).,在前幾章的學(xué)習(xí)中我們現(xiàn)實(shí)了怎樣使用良序歸納原則證明關(guān)于一個(gè)良序集的結(jié)果?，F(xiàn)在我們敘述并證明這個(gè)證明技術(shù)是有效的。 定理1 良序歸納原理 設(shè)S是一個(gè)良序集，如果下述條件成立： 基礎(chǔ)步：P(x0)對(duì)S的最小元素為真，且 歸納步: 對(duì)一切y S, 如果P(x)對(duì)所有的xy為真，則P(y)為 真。那么P(x)對(duì)所有的x S為真。,proof： 假若P

7、(x)不對(duì)所有的x S為真。那么存在一個(gè)元素y S使 得P(y)為假。于是集合A=x S| P(x)為假是非空的。 因?yàn)镾是良序的，集合A有最小元素a. 易知a不等于x0,因?yàn)閺?基礎(chǔ)步知道P(x0)為真。 根據(jù)a是選自A的最小元素，我們知道對(duì)所有的x S (xa)都 有P(x)為真。由歸納步這就可以退出P(a)為真。 這個(gè)矛盾就證明了P(x)必須對(duì)所有x S 為真。,二、字典順序 字典順序是以字母表中的字母順序?yàn)榛A(chǔ)的。這是從一個(gè)集合上的偏序構(gòu)造一個(gè)集合上的串的序的特殊情況。我們將說(shuō)明這種構(gòu)造在任一個(gè)偏序集上是怎么做的。,首先，我們將說(shuō)明怎樣在兩個(gè)偏序集(A1, 1)和(A2, 2)的笛 卡

8、爾積上構(gòu)造一個(gè)偏序。 在A1A2上的字典順序定義如下：如果第一個(gè)對(duì)的第一個(gè) 元素（在A1中）小于第二個(gè)對(duì)的第一個(gè)元素，或者第一個(gè)元 素相等，但是第一個(gè)對(duì)的第二個(gè)元素（在A2中）小于第二個(gè) 對(duì)的第二個(gè)元素，那么第一個(gè)對(duì)小于第二個(gè)對(duì)。換句話說(shuō)， (a1, a2)小于(b1,b2),即 (a1, a2) (b1,b2) 或者a11b1,或者a1=b1且a22b2. 把相等加到A1A2上的序就得到偏序。,【example 8】確定在偏序集（ZZ， ）中是否有 (3, 5) (4,8), (3,8)(4,5) 和(4,9) (4,11) ? 這里的 是從Z上通常的關(guān)系構(gòu)造的字典順序。 Solution：

9、 因?yàn)?4,故而(3, 5) (4,8), 且(3,8)(4,5) 。因?yàn)?4,9)與(4,11) 的第一元素相同，但911,我們有(4,9) (4,11) 。 下圖明顯地顯示了Z+Z+ 中比(3,4)小的有序?qū)Φ募稀?可以在n個(gè)偏序集(A1, 1 ), (A2, 2 ), , (An, n ) 的笛卡爾 積上定義字典順序。 如下定義A1A2An上的偏序 ：如果a10 是的a1=b1,ai=bi,且ai+1i+1 bi+1,那么 (a1,a2,an)(b1,b2,bn) 換句話說(shuō)，如果在兩個(gè)n元組不同元素出現(xiàn)的第一位置上等 一個(gè)n元組的元素小于第二個(gè)n元組的元素，那么第一個(gè)n元組小 于第二個(gè)

10、n元組。,【example 9】注意（1，2，3，5）（1，2，4，3），因?yàn)檫@ 些4元組的前兩位相同，但是第一個(gè)4元組的第三位3小于第二個(gè) 4元組的第三位4（這里的4元組上的字典順序是整數(shù)集合上的通 常的“小于或等于”關(guān)系導(dǎo)出的字典順序）。,我們現(xiàn)在可以定義串上的字典順序?？紤]偏序集S上的串a(chǎn)1a2an 和b1b2bn,假定這些串不相等。設(shè)t是m，n中較小的數(shù)。 定義字典順序如下： a1a2an小于b1b2bn,當(dāng)且僅當(dāng) （a1a2at） （b1b2bt） 或者 （a1a2at） = （b1b2bt）并且mn 其中這個(gè)不等式中的表示St中的字典順序。換句話說(shuō)，為確定兩 個(gè)不同串的序，較長(zhǎng)的串

11、被切到較短的串的長(zhǎng)度t，即t=min(m,n) 然 后使用St上的字典順序比較每個(gè)船的前t為組成的t元組，如果對(duì)應(yīng)于 第一個(gè)串的t元組小于第二個(gè)串的t元組，或者這兩個(gè)t元組相等，但是 第二個(gè)串更長(zhǎng)，那么第一個(gè)串小于第二個(gè)串。,【example 10】 考慮小寫(xiě)英語(yǔ)字母串構(gòu)成的集合。使用在字母表中的字母序，可以構(gòu)成在串的集合上的字典順序。 如果兩個(gè)串第一次出現(xiàn)不同字母時(shí)，第一個(gè)串的字母先于第二個(gè)字母，或者如果第一個(gè)串和第二個(gè)串在所有的位都相同，但是第二個(gè)串有更多的字母，那么，第一個(gè)串小于第二個(gè)串。這種排序和字典使用的排序相同。例如 discreet discrete 因?yàn)檫@兩個(gè)串在第7位首次出現(xiàn)

12、字母，并且 e t. discreet discreetness 因?yàn)檫@兩個(gè)串前8個(gè)字母相同，但是第二個(gè)串更長(zhǎng)。此外 discrete discretion,在有窮偏序集的有向圖中有許多可以不必顯示出來(lái)，因?yàn)樗麄兪潜仨毚嬖诘摹?例如，考慮在集合1，2，3，4上的偏序(a, b)| a b的有向圖，參見(jiàn)圖a。因?yàn)檫@個(gè)關(guān)系是偏序，它是自反的并且有向圖在所有的頂點(diǎn)都有環(huán)，因此，我們不必顯示這些環(huán)，因?yàn)樗鼈兪潜仨毘霈F(xiàn)的。在圖b中沒(méi)有顯示這些環(huán)。由于一個(gè)偏序是傳遞的，我們不必顯示那些由于傳遞性而必須出現(xiàn)的邊。例如，在圖c中沒(méi)有顯示邊(1,3),(1,4)和(2,4)，因?yàn)樗鼈兪潜仨毘霈F(xiàn)的。如果假設(shè)所有的

13、邊的方向是向上的，我們不必顯示邊的方向；圖c沒(méi)有顯示方向。,三、哈塞圖（ Hasse 圖）,我們可以使用下面的過(guò)程表示一個(gè)有窮集上的偏序。 從這個(gè)關(guān)系的有向圖開(kāi)始： (1)自反性：每個(gè)頂點(diǎn)都有自回路，省去。 (2)反對(duì)稱性：兩個(gè)頂點(diǎn)間只可能有一個(gè)箭頭從左 右，或從下上的方向從小到大安置頂點(diǎn)，可省略箭頭。 (3)傳遞性：由于有(a,b)，(b,c)R 則(a,c) R 故只畫(huà)(a,b)，(b,c)對(duì)應(yīng)的邊,省略邊(a,c)。,完成以上步驟就得到一個(gè)包含著足夠表示偏序信息的圖，這個(gè) 圖叫作哈塞圖,哈塞圖（ Hasse 圖） 定義：設(shè)是上的一個(gè)偏序關(guān)系，如果a b ，則將畫(huà)在 下面，且不，使ac，c

14、 b，則，間用直線連 接。并符合簡(jiǎn)化的關(guān)系圖的繪制，稱這樣得到關(guān)系圖為 哈塞圖（Hasse圖）。,29,2020/8/28,【example 11】畫(huà)出表示1，2，3，4，6，8，12上的偏序 (a,b)|a 整除b的哈塞圖。 Solution： 由這個(gè)偏序的有向圖開(kāi)始，如下圖a所示。移走所有的環(huán)， 如下圖b所示，然后刪去所有由傳遞性導(dǎo)出的邊。這些邊是 (1,4),(1,6),(1,8),(1,12),(2,8),(3,12).排列所有的邊使得方向向上 ，并且刪除所有的箭頭得到哈塞圖。結(jié)果如圖c所示。,【example 12】畫(huà)出冪集P(S)上的偏序(A, B) | A B的哈塞 圖，其中S=

15、a, b, c. Solution : 關(guān)于這個(gè)偏序的哈塞圖是由相關(guān)的有向圖得到的，先刪除所 有的環(huán)和所有的由傳遞性產(chǎn)生的邊，即 (, a, b), (, a, c), (, b, c), (, a, b, c), ( a , a, b, c), ( b ,a, b, c)和(c, a, b, c). 最后，使所有的邊方向向上并刪除箭頭。得到哈塞圖如下所 示。,【example】： ， ， 1（，） ， 2（，） |， 3(s1,s2)s1s2，s1，s2p(B) 求R1, R2, R3 所表示關(guān)系的哈塞圖。,具有極值性質(zhì)的偏序集元素有許多重要應(yīng)用。 偏序集的一個(gè)元素叫做極大的，當(dāng)它不小于這個(gè)

16、偏序集的任何其他元素。即a在偏序集（S， ）中是極大的，當(dāng)不存在bS使得ab. 類似地，偏序集的一個(gè)元素叫做極小的，如果它不大于這個(gè)偏序集的任何其他元素。即a在偏序集（S， ）中是極小的，如果不存在bS使得ba。 使用哈塞圖很容易是識(shí)別極大元素和極小元素。它們是圖中的“頂”元素與“底”元素。,四、極大元素與極小元素,定義極大元與極小元： 設(shè)（S， ）是偏序集，若S，且在S中找不到一個(gè) 元素b（ba），使ab（ba），則稱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),【examp

17、le】（N，|）是偏序集， A=2，3，4，5，6，7，8，9則 中極大元素：， 極小元素：， 注： 極大元，極小元并不要求唯一，且同一元素，可以既是極大元，又是極小元，如，。 極大元，極小元必須是子集中的元素。,【example 13】偏序集（2，4，5，10，12，20，25，| ）的 哪些元素時(shí)極大的，哪些是極小的？ Solution： 右圖關(guān)于這個(gè)偏序集的哈塞圖 顯示了極大元素是12，20和25， 極小元素時(shí)2和5。,通過(guò)這個(gè)例子可以看出，一個(gè)偏序集可以有多于一個(gè)的極大元素和 多于一個(gè)的極小元素。,在偏序集中存在一個(gè)元素大于每個(gè)其他的元素，這樣的元素叫做最大元素，即a是偏序集（S， ）

18、的最大元素，當(dāng)對(duì)所有的bS有b a。當(dāng)最大元素存在時(shí)它是唯一的。 類似地，一個(gè)元素叫做最小元素，當(dāng)它小于偏序集的所有其他元素。即a是偏序集（S， ）的最小元素，如果對(duì)所有的bS有a b。當(dāng)最小元素存在時(shí)它也是唯一的。,40,2020/8/28,定義 最大元素與最小元素： 設(shè)（S， ）是偏序集，若， (），則稱為的最大元素（最小元素）。 【example】上例中其Hasse圖如下圖所示,結(jié)論：子集中是不存在最大元（最小元）的。,定理 是偏序集，B是A的非空子集，如果B有最小元素(最大元素)，則最小元素(最大元素)是唯一的。 proof： 假設(shè)B有兩個(gè)最小元素a、b,則 因?yàn)閍是最小元素，bB，

19、根據(jù)最小元素定義，有ab; 類似地，因?yàn)閎是最小元素，aB，根據(jù)最小元素定義，有 ba。因?yàn)橛蟹磳?duì)稱性，所以有a=b。 同理可證最大元素的唯一性。,小結(jié)： 是偏序集，B是A的非空子集，則 B的極小(大)元素總是存在的，就是子集中處在最下(上)層的元素是極小(大)元素。 B的最小元(最大元)素有時(shí)可能不存在，只要有唯一的極小(大)元素，則這個(gè)極小(大)元素就是最小(大)元素。否則就沒(méi)有最小(大)元素。,【example 14】確定下圖的每個(gè)哈塞圖表示的偏序集是否有最 大元素和最小元素。,Solution： 哈塞圖(a)的偏序集的最小元素時(shí)a。這個(gè)偏序集沒(méi)有最大元 素。 哈塞圖(b)的偏序集既沒(méi)有

20、最大元素也沒(méi)有最小元素。 哈塞圖(c)的偏序集沒(méi)有最小元素，它的最大元素時(shí)d。 哈塞圖(d)的偏序集有最小元素a和最大元素d。,【example15】設(shè)S是集合。確定偏序集（P(S), ）中是否存在最大元素與最小元素。 Solution： 最小元素時(shí)空集。因?yàn)閷?duì)于S的任何子集T,有 T，集合S是 這個(gè)偏序集的最大元素，因?yàn)橹灰猅是S的子集，就有T S。,46,2020/8/28,【example 16】在偏序集（Z+, | ）中是否存在最大元素和 最小元素？ Solution： 1是最小元素，因?yàn)橹灰猲是正整數(shù)，就有1|n。因?yàn)闆](méi) 有被所有正整數(shù)整除的整數(shù)，所以不存在最大元素。,47,2020

21、/8/28,有時(shí)可以找到一個(gè)元素大于偏序集（S， ）的子集A中所有的元素。如果u是S的元素使得對(duì)所有的元素a A,有a u，那么u叫做A的一個(gè)上界。 也可能存在一個(gè)元素小于A中的所有的其他元素。如果l是S的一個(gè)元素使得對(duì)所有的元素a A,有l(wèi) a，那么l叫做A的一個(gè)下界。,定義上界與下界： 設(shè)（P, ）是半序集，AP，若aP，對(duì) bA, b a （a b）稱a為A的上界（下界）。,【example】：B=a,b,c,R3= (s1,s2) | s1 s2，s1P(B) , (P(B), )是偏序集。 設(shè)，a,b,c,a,c,a,b,a,c 其Hasse圖如右圖所示:,注： （1）上例中，無(wú)最大

22、元素，但存在的上界 ，。 （2）為的最小元，也是的下界。 （3）最大（?。┰厥堑囊粋€(gè)上（下）界。 （4）上（下）界可以不唯一，也可以不存在。,【example 17】找出下圖所示哈塞圖的偏序集的子集a, b, c, j, h和a，c，d，f的下界和上界。,Solution： a，b，c的上界是e, f, j 和h，它的唯一的下界是a。 j，h沒(méi)有上界，它的下界是a，b，c，d，e和f. a, c, d ,f 的上界是f，h和j，它的下界是a。,元素x叫做子集A的最小上界（上確界），如果x是一個(gè)上界并且它小于A的其他上界。因?yàn)槿绻@樣的元素存在，只存在一個(gè)，稱這個(gè)元素為最小上界（上確界）是有意

23、義的。即如果只要aA就有a x，并且只要z是A的上界，就有x z, x就是A的最小上界（上確界）。 類似地，如果y是A的下界，并且只要z是A的下界，就有z y，y就是A的最大下界（下確界）。A的最大下界（下確界）如果存在也是唯一的。 一個(gè)子集A的最大下界（下確界），和最小上界（上確界），分別記作 glb ( A )和 lub ( A ).,定義上確界與下確界： 設(shè)（S，）是偏序集，AS，若a是A的一個(gè)上界 （下界），而A的上界（下界）z，都有a b（b a） ，則稱a是A的上確界（下確界）。,【example】給定（A,）的哈塞圖如圖所示：,【example 18】在下圖所示偏序集中如果b，d

24、，g的最大下界和最小上界存在，求出這個(gè)最大下界和最大上界。,Solution： b，d，g的上界是g和h。因?yàn)?g h, g是最小上界。 b，d，g 的下界是a和b，因?yàn)橛衋 b, b 是 最大下界。,【example 19】在偏序集（Z+, | ）中，如果集合3，9，12和 1，2，4，5，10的最大下界和最小上界存在，求出這些最大 下界和最小上界。 Solution： 求最大下界： 如果3，9，12被一個(gè)整數(shù)整除，那么這個(gè)整數(shù)就是 3，9，12的下界。這樣的整數(shù)只有1和3.因?yàn)?|3，3是 3，9，12的最大下界。 集合1，2，4，5，10關(guān)系到 | 的下界只有1，因此1是 1，2，4，5

25、，10的最大下界。,求最小上界： 一個(gè)整數(shù)是 3，9，12的上界，當(dāng)且僅當(dāng)它被3，9和12整除 。具有這種性質(zhì)的整數(shù)就是那些被3，9和12的最小公倍數(shù)36整 除的整數(shù)。因此，36是3，9，12的最小上界。 一個(gè)正整數(shù)是集合1，2，4，5，10的上界，當(dāng)且僅當(dāng)它被1 ，2，4，5，10整除，具有這種性質(zhì)的整數(shù)就是被這些整數(shù)的最 小公倍數(shù)20整除的整數(shù)。因此，20是集合1，2，4，5，10的 最小上界。,五、格 在這里我們引入格的概念。 定義：設(shè)X,是偏序集，如果x, y X，集合 x, y 都有 最小上界和最大下界，則稱X,是格。 【example 20】確定如下圖所示的每個(gè)哈塞圖表示的偏序集是

26、否是格,Solution： 圖a和c中的哈塞圖表示的偏序集是格。因?yàn)樵诿總€(gè)偏序集中 每對(duì)元素都有最小上界和最大下界。 另一方面，圖b所示的哈塞圖的偏序集不是格，因?yàn)樵豣和 c沒(méi)有最小上界。為此只要注意到d，e和f中每一個(gè)都是上界，但 這3個(gè)元素的任何一個(gè)關(guān)于這個(gè)偏序集中的序都不大于其他2個(gè).,【example】下列各集合對(duì)于整除關(guān)系都構(gòu)成偏序集,判斷哪些偏序集是格? L=1,2,3,4,5； L=1,2,3,4,6,9,12,18,36； L=1,2,22,2n； L=1,2,3,4,5,6,7,8,9,10,Solution： 不是，因?yàn)長(zhǎng)中的元素對(duì)2,3沒(méi)有最小上界； 是，因?yàn)長(zhǎng)=1,2

27、,3,4,6,9,12,18,36任何一對(duì)元素a,b，都有最小上界和最大下界； 是，與同理； 不是，因?yàn)長(zhǎng)中的元素對(duì)6,7沒(méi)有最小上界不存在最小上界.,【example】下圖中給出了一些偏序集的哈斯圖，判斷它們是否 構(gòu)成格。,Solution： 它們都不是格。 在(a)中，1,2沒(méi)有下界，因而沒(méi)有最大下界。 在(b)中，2,4雖有兩個(gè)上界，但沒(méi)有最小上界。 在(c)中，1,3沒(méi)有下界，因而沒(méi)有最大下界。 在(d)中，2,3雖有三個(gè)上界，但沒(méi)有最小上界。,【example 21】偏序集（Z+, | ）是格嗎？ Solution： 設(shè)a和b是兩個(gè)正整數(shù)，這兩個(gè)整數(shù)的最小上界和最大下界分 別是它們的

28、最小公倍數(shù)和最大公約數(shù)，因此這個(gè)偏序集是格。,【example 22】確定偏序集（1，2，3，4，5， | ）和 （1，2，4，8，16，| ）是否為格？ Solution： 因?yàn)?和3在（1，2，3，4，5， | ）中沒(méi)有上界，它們 當(dāng)然沒(méi)有最小上界。因此第一個(gè)偏序集不是格。 第二個(gè)偏序集的每?jī)蓚€(gè)元素都有最小上界和最大下界。在 這個(gè)偏序集中兩個(gè)元素的最小上界是他們中間較大的元素， 而兩個(gè)元素的最大下界是它們中間較小的元素。因此第二個(gè) 偏序集是格。,【example 23】確定（P(S), ）是否為格，其中S是集合。 Solution： 設(shè)A和B是S的兩個(gè)子集，A和B的最小上界和最大下界分別是

29、 AB和A B，因此（P(S), ）是格。,【example 24】信息流的格模式 在許多設(shè)置中，從一個(gè)人或 計(jì)算機(jī)程序到另一個(gè)人或計(jì)算機(jī)程序的信息流要受到限制，這可 以通過(guò)安全權(quán)限來(lái)實(shí)現(xiàn)。我們可以使用格的模型來(lái)表示不同的信 息流策略。 例如，一個(gè)通用的信息流策略適用于政府或軍事系統(tǒng)中的多 級(jí)安全策略。為，誒組信息分配一個(gè)安全級(jí)別，并且每個(gè)安全級(jí) 別用一個(gè)對(duì)（A, C）表示，其中A是權(quán)限級(jí)別，C是種類。然后 允許人和計(jì)算機(jī)程序從一個(gè)被特別限制的安全類的集合中訪問(wèn)信 息。,在美國(guó)政府中，使用的典型的權(quán)限級(jí)別是不保密（0）、秘密 （1）、機(jī)密（2）和絕密（3）。在安全級(jí)別中使用的種類是一 個(gè)集合的

30、子集，這個(gè)集合含有與一個(gè)特定行業(yè)領(lǐng)域相關(guān)的所有的 分部，每個(gè)分部表示一個(gè)指定的對(duì)象域。 例如，如果分部的集合是間諜，鼴鼠。雙重間諜，那么存 在8個(gè)不同的種類，分部集合有8個(gè)子集，對(duì)于每個(gè)子集有一類 ，例如間諜，鼴鼠。,我們可以對(duì)安全類排序，規(guī)定（A1,C1） （A2,C2）當(dāng)且僅當(dāng) A1 A2和C1 C2.信息允許從安全類（A1,C1）流向安全類 （A2,C2）當(dāng)且僅當(dāng)（A1,C1） （A2,C2） 。 例如，信息允許從安全類（機(jī)密，間諜，鼴鼠）流向安全 類（絕密，間諜，鼴鼠，雙重間諜），反之，信息不允許從安 全類（絕密，間諜，鼴鼠）流向安全類（機(jī)密，間諜，鼴鼠 ，雙重間諜）或（絕密，間諜）。

31、,六、拓?fù)渑判?假設(shè)一個(gè)項(xiàng)目由20個(gè)任務(wù)構(gòu)成。某些任務(wù)只能在其他任務(wù)結(jié) 束之后完成，如何找到關(guān)于這些任務(wù)的順序？ 為了對(duì)這個(gè)問(wèn)題構(gòu)造模型，我們建立一個(gè)任務(wù)集合上的偏序， 使得ab,當(dāng)且僅當(dāng)a和b是任務(wù)且直到a結(jié)束后b才能開(kāi)始。為安 排好這個(gè)項(xiàng)目，需要得出與這個(gè)偏序相容的所有20個(gè)任務(wù)的順 序。我們將說(shuō)明怎樣做到這一點(diǎn)。,從定義開(kāi)始，如果只要aRb就有a b,則稱一個(gè)全序與偏序R 是相容的。從一個(gè)偏序構(gòu)造一個(gè)相容的全序叫做拓?fù)渑判?。需要使用引?. 引理1：每個(gè)有窮非空偏序集（S, ）都有極小元素。,Proof： 選擇S的一個(gè)元素a0. 如果a0不是績(jī)效元素，那么存在元素a1, 滿足a1 a0.如果a1不是極小元素，那么存在元素a2,滿足a2 a1. 繼續(xù)這一過(guò)程，使得如果an不是極小元素，那么存在元素an+1滿 足an+1an.因?yàn)樵谶@個(gè)偏序集只有有窮個(gè)元素，這個(gè)過(guò)程一定結(jié) 束并且具有極小元素an.,我們將要描述的拓?fù)渑判蛩惴▽?duì)任何有窮非空偏序集都有效 為在偏序集（A, ）上定義一個(gè)全序，首先選擇一個(gè)極小元 素a1；由引理1這樣的元素存在。接著，A-a1， 也是一個(gè) 偏序集。如果它是非空的，選擇這個(gè)偏序集的一個(gè)極小元素a2. 然后再取走a2，如果還有其