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

1、1,離散數(shù)學(xué) Discrete Mathematics,汪榮貴 教授 合肥工業(yè)大學(xué)軟件學(xué)院專用課件 2010.03,學(xué)習(xí)內(nèi)容,4.1集合的基本知識 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，如果它是自反的、反對稱的 和傳遞的，就稱為偏序。 集合S與偏序R一起叫做偏序集，記作（S,R）. 例如數(shù)值的、關(guān)系和集合的都是偏序關(guān)系。,【example 1】證明“大于或等于”關(guān)系（ ）是整數(shù)集合上 的偏序。 solution： 因?yàn)閷λ姓麛?shù)a，有a a， 是自反的。 如果a b且

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

3、序集中記號a b表示(a，b)R.使用這個(gè)記號 是由于“小于或等于”關(guān)系是偏序關(guān)系的范例。 注意：符號 表示任意偏序關(guān)系，并不僅僅是“小于或等于”關(guān)系。 記號ab表示a b但ab.如果ab,我們說“a小于b”或 “b大于a”。 當(dāng)a與b是偏序集（S, ）的元素時(shí)，不一定有a b 或b c。 例如，在（P(Z), ）中,1,2與1,3沒有關(guān)系，反之亦然，因?yàn)?沒有一個(gè)集合被另一個(gè)集合包含。類似地在(Z,|)中，2與3沒關(guān)系，3 與2也沒關(guān)系。由此得到定義2.,定義2：偏序集(S, ) 的元素a和b叫做可比的，如果a b 或 b a。當(dāng)a和b是S的元素并且既沒有a b，也沒 有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.,用形容詞“部分的（偏的）”描述偏序是由于一些對元素可能是不可比的。當(dāng)集合中的每對元素都可比時(shí)，這個(gè)關(guān)系叫做全序。 定義3：如果(S, ) 是偏序集，且S的每對元素都是可比的，則S叫做全序集或線序集，且 叫做全序或線序。一個(gè)全序集也叫做鏈。,【example 5】偏序集(Z, )是全序集，因?yàn)橹灰猘和b是整數(shù) ，就有a b或b a。 【example 6】偏序集(Z+, | )不是全序集，因?yàn)樗?/p>

5、著不可比的元素，例如5和7.,定義4：對于偏序集(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中無最小元素， 因B是有限集，必存在x, y B,使得

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

7、(x)不對所有的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的最小元素，我們知道對所有的x S (xa)都 有P(x)為真。由歸納步這就可以退出P(a)為真。 這個(gè)矛盾就證明了P(x)必須對所有x S 為真。,二、字典順序 字典順序是以字母表中的字母順序?yàn)榛A(chǔ)的。這是從一個(gè)集合上的偏序構(gòu)造一個(gè)集合上的串的序的特殊情況。我們將說明這種構(gòu)造在任一個(gè)偏序集上是怎么做的。,首先，我們將說明怎樣在兩個(gè)偏序集(A1, 1)和(A2, 2)的笛 卡

8、爾積上構(gòu)造一個(gè)偏序。 在A1A2上的字典順序定義如下：如果第一個(gè)對的第一個(gè) 元素（在A1中）小于第二個(gè)對的第一個(gè)元素，或者第一個(gè)元 素相等，但是第一個(gè)對的第二個(gè)元素（在A2中）小于第二個(gè) 對的第二個(gè)元素，那么第一個(gè)對小于第二個(gè)對。換句話說， (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) 換句話說，如果在兩個(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中的字典順序。換句話說，為確定兩 個(gè)不同串的序，較長的串

11、被切到較短的串的長度t，即t=min(m,n) 然 后使用St上的字典順序比較每個(gè)船的前t為組成的t元組，如果對應(yīng)于 第一個(gè)串的t元組小于第二個(gè)串的t元組，或者這兩個(gè)t元組相等，但是 第二個(gè)串更長，那么第一個(gè)串小于第二個(gè)串。,【example 10】 考慮小寫英語字母串構(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è)串更長。此外 discrete discretion,在有窮偏序集的有向圖中有許多可以不必顯示出來，因?yàn)樗麄兪潜仨毚嬖诘摹?例如，考慮在集合1，2，3，4上的偏序(a, b)| a b的有向圖，參見圖a。因?yàn)檫@個(gè)關(guān)系是偏序，它是自反的并且有向圖在所有的頂點(diǎn)都有環(huán)，因此，我們不必顯示這些環(huán)，因?yàn)樗鼈兪潜仨毘霈F(xiàn)的。在圖b中沒有顯示這些環(huán)。由于一個(gè)偏序是傳遞的，我們不必顯示那些由于傳遞性而必須出現(xiàn)的邊。例如，在圖c中沒有顯示邊(1,3),(1,4)和(2,4)，因?yàn)樗鼈兪潜仨毘霈F(xiàn)的。如果假設(shè)所有的

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

14、 b，則，間用直線連 接。并符合簡化的關(guān)系圖的繪制，稱這樣得到關(guān)系圖為 哈塞圖（Hasse圖）。,29,2020/8/28,【example 11】畫出表示1，2，3，4，6，8，12上的偏序 (a,b)|a 整除b的哈塞圖。 Solution： 由這個(gè)偏序的有向圖開始，如下圖a所示。移走所有的環(huán)， 如下圖b所示，然后刪去所有由傳遞性導(dǎo)出的邊。這些邊是 (1,4),(1,6),(1,8),(1,12),(2,8),(3,12).排列所有的邊使得方向向上 ，并且刪除所有的箭頭得到哈塞圖。結(jié)果如圖c所示。,【example 12】畫出冪集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è)（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。,通過這個(gè)例子可以看出，一個(gè)偏序集可以有多于一個(gè)的極大元素和 多于一個(gè)的極小元素。,在偏序集中存在一個(gè)元素大于每個(gè)其他的元素，這樣的元素叫做最大元素，即a是偏序集（S， ）

18、的最大元素，當(dāng)對所有的bS有b a。當(dāng)最大元素存在時(shí)它是唯一的。 類似地，一個(gè)元素叫做最小元素，當(dāng)它小于偏序集的所有其他元素。即a是偏序集（S， ）的最小元素，如果對所有的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)橛蟹磳ΨQ性，所以有a=b。 同理可證最大元素的唯一性。,小結(jié)： 是偏序集，B是A的非空子集，則 B的極小(大)元素總是存在的，就是子集中處在最下(上)層的元素是極小(大)元素。 B的最小元(最大元)素有時(shí)可能不存在，只要有唯一的極小(大)元素，則這個(gè)極小(大)元素就是最小(大)元素。否則就沒有最小(大)元素。,【example 14】確定下圖的每個(gè)哈塞圖表示的偏序集是否有最 大元素和最小元素。,Solution： 哈塞圖(a)的偏序集的最小元素時(shí)a。這個(gè)偏序集沒有最大元 素。 哈塞圖(b)的偏序集既沒有

20、最大元素也沒有最小元素。 哈塞圖(c)的偏序集沒有最小元素，它的最大元素時(shí)d。 哈塞圖(d)的偏序集有最小元素a和最大元素d。,【example15】設(shè)S是集合。確定偏序集（P(S), ）中是否存在最大元素與最小元素。 Solution： 最小元素時(shí)空集。因?yàn)閷τ赟的任何子集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)闆] 有被所有正整數(shù)整除的整數(shù)，所以不存在最大元素。,47,2020

21、/8/28,有時(shí)可以找到一個(gè)元素大于偏序集（S， ）的子集A中所有的元素。如果u是S的元素使得對所有的元素a A,有a u，那么u叫做A的一個(gè)上界。 也可能存在一個(gè)元素小于A中的所有的其他元素。如果l是S的一個(gè)元素使得對所有的元素a A,有l(wèi) a，那么l叫做A的一個(gè)下界。,定義上界與下界： 設(shè)（P, ）是半序集，AP，若aP，對 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）上例中，無最大

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沒有上界，它的下界是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è)偏序集中 每對元素都有最小上界和最大下界。 另一方面，圖b所示的哈塞圖的偏序集不是格，因?yàn)樵豣和 c沒有最小上界。為此只要注意到d，e和f中每一個(gè)都是上界，但 這3個(gè)元素的任何一個(gè)關(guān)于這個(gè)偏序集中的序都不大于其他2個(gè).,【example】下列各集合對于整除關(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)長中的元素對2,3沒有最小上界； 是，因?yàn)長=1,2

27、,3,4,6,9,12,18,36任何一對元素a,b，都有最小上界和最大下界； 是，與同理； 不是，因?yàn)長中的元素對6,7沒有最小上界不存在最小上界.,【example】下圖中給出了一些偏序集的哈斯圖，判斷它們是否 構(gòu)成格。,Solution： 它們都不是格。 在(a)中，1,2沒有下界，因而沒有最大下界。 在(b)中，2,4雖有兩個(gè)上界，但沒有最小上界。 在(c)中，1,3沒有下界，因而沒有最大下界。 在(d)中，2,3雖有三個(gè)上界，但沒有最小上界。,【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， | ）中沒有上界，它們 當(dāng)然沒有最小上界。因此第一個(gè)偏序集不是格。 第二個(gè)偏序集的每兩個(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ī)程序的信息流要受到限制，這可 以通過安全權(quán)限來實(shí)現(xiàn)。我們可以使用格的模型來表示不同的信 息流策略。 例如，一個(gè)通用的信息流策略適用于政府或軍事系統(tǒng)中的多 級安全策略。為，誒組信息分配一個(gè)安全級別，并且每個(gè)安全級 別用一個(gè)對（A, C）表示，其中A是權(quán)限級別，C是種類。然后 允許人和計(jì)算機(jī)程序從一個(gè)被特別限制的安全類的集合中訪問信 息。,在美國政府中，使用的典型的權(quán)限級別是不保密（0）、秘密 （1）、機(jī)密（2）和絕密（3）。在安全級別中使用的種類是一 個(gè)集合的

30、子集，這個(gè)集合含有與一個(gè)特定行業(yè)領(lǐng)域相關(guān)的所有的 分部，每個(gè)分部表示一個(gè)指定的對象域。 例如，如果分部的集合是間諜，鼴鼠。雙重間諜，那么存 在8個(gè)不同的種類，分部集合有8個(gè)子集，對于每個(gè)子集有一類 ，例如間諜，鼴鼠。,我們可以對安全類排序，規(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ù)的順序？ 為了對這個(gè)問題構(gòu)造模型，我們建立一個(gè)任務(wù)集合上的偏序， 使得ab,當(dāng)且僅當(dāng)a和b是任務(wù)且直到a結(jié)束后b才能開始。為安 排好這個(gè)項(xiàng)目，需要得出與這個(gè)偏序相容的所有20個(gè)任務(wù)的順 序。我們將說明怎樣做到這一點(diǎn)。,從定義開始，如果只要aRb就有a b,則稱一個(gè)全序與偏序R 是相容的。從一個(gè)偏序構(gòu)造一個(gè)相容的全序叫做拓?fù)渑判颉Ｐ枰褂靡?. 引理1：每個(gè)有窮非空偏序集（S, ）都有極小元素。,Proof： 選擇S的一個(gè)元素a0. 如果a0不是績效元素，那么存在元素a1, 滿足a1 a0.如果a1不是極小元素，那么存在元素a2,滿足a2 a1. 繼續(xù)這一過程，使得如果an不是極小元素，那么存在元素an+1滿 足an+1an.因?yàn)樵谶@個(gè)偏序集只有有窮個(gè)元素，這個(gè)過程一定結(jié) 束并且具有極小元素an.,我們將要描述的拓?fù)渑判蛩惴▽θ魏斡懈F非空偏序集都有效 為在偏序集（A, ）上定義一個(gè)全序，首先選擇一個(gè)極小元 素a1；由引理1這樣的元素存在。接著，A-a1， 也是一個(gè) 偏序集。如果它是非空的，選擇這個(gè)偏序集的一個(gè)極小元素a2. 然后再取走a2，如果還有其