羅平翻譯的高等離散結(jié)構(gòu)課件

第六章序關(guān)系與序結(jié)構(gòu)6.1偏序集偏序集：在某個集合A上的關(guān)系R如果是自反的、反對稱的和傳遞的，那么稱R是一個偏序。集合A與偏序R一起稱作偏序集，用(A，R)表示。如果不會產(chǎn)生混淆的話，那么可以把偏序集簡單地記成A而非(A，R)。例1設(shè)A是集合S的子集的集合，集合的包含關(guān)系

是A上的一個偏序，所以(A，)是一個偏序集。例2

設(shè)Z+是正整數(shù)集合，通常的關(guān)系≤(小于或等于)是Z+上的一個偏序。同樣≥(大于或等于)也是Z+上的一個偏序。例3

整除關(guān)系(aRb當且僅當a?|?b)是Z+上的一個偏序。2例4

設(shè)是集合A上所有等價關(guān)系的集合，因為是由A

A的子集所組成的，所以在集合的包含偏序下是一個偏序集。如果R和S是A上的等價關(guān)系，那么某些性質(zhì)可以用關(guān)系符號表示如下：RS當且僅當xRy推出對A中所有x,y有xSy，于是(，)是一個偏序集。例5

Z+上的關(guān)系<不是一個偏序，因為它不是自反的。例6

設(shè)R是集合A上一個偏序，R–1是R的逆關(guān)系，那么R–1也是一個偏序。為了看清這一點，回顧4.4節(jié)給出的自反性、反對稱性和傳遞性的特征。如果R有這三種性質(zhì)，那么?R，R∩R–1?，R2R，通過取逆有?=?–1R–1，R–1∩(R–1)–1=R–1∩R?，(R–1)2R–1，所以，由4.4節(jié)可知，R–1是自反的、反對稱的和傳遞的。因此，R–1也是一個偏序。偏序集(A，R–1)稱為偏序集(A，R)的對偶，偏序R–1稱為偏序R的對偶。3最熟悉的偏序是Z和R上的關(guān)系≤和≥。由于這個原因，當一般談到集合A上的偏序R時，常常對R使用符號≤或≥，這使得R的性質(zhì)更熟悉和更容易記憶。因此，讀者可以把符號≤用來當作不同集合上許多不同的偏序。但不要誤認為這些關(guān)系都是相同的或者它們是熟知的Z或R上的關(guān)系≤。如果需要同另一個偏序區(qū)別開來，也可以使用如≤1，≤，≥1，≥等符號來表示偏序。本書將遵守下面的約定，當(A，≤)是一個偏序集時，總是使用符號≥代替偏序≤–1，因此，(A，≥)將是對偶偏序集。類似地，偏序集(A，≤1)的對偶將用(A，≥1)表示，偏序集(B，≤)的對偶用(B，≥)表示。這種約定再一次使人想起熟悉的對偶偏序集(Z，≤)和(Z，≥)以及偏序集(R，≤)和(R，≥)。4如果(A，≤)是一個偏序集，對A的元素a和b，如果a≤b或b≤a，那么說a和b是可比的。注意，在偏序集中每一對元素不必都是可比的。例如，考慮例3中的偏序集，元素2和7不是可比的，因為27且72。因此，在偏序集中的“偏”字意味著某些元素可能不是可比的。如果在一個偏序集A中每一對元素都是可比的，則稱A是一個全序集，偏序稱為全序，也稱A是一個鏈。例7

例2中的偏序集是全序集。5定理1

如果(A，≤)和(B，≤)是偏序集，那么(A

B，≤)是一個偏序集，它的偏序≤由下述定義：如果在A中a≤a和在B中b≤b，那么(a,b)≤(a,b)。注意，上面使用的符號≤表示三種不同的偏序。證明

如果(a,b)∈A

B，因為在A中有a≤a和在B中有b≤b，所以(a,b)≤(a,b)，從而≤在A

B中滿足自反性質(zhì)?，F(xiàn)在假設(shè)(a,b)≤(a，b)和(a,b)≤(a,b)，其中a,a∈A，b,b∈B。于是在A中有

a≤a，a≤a且在B中有

b≤b,b≤b,因為A和B是偏序集，所以在A和B中，由偏序的反對稱性推出a=a

和b=b，因此，≤在AB中滿足反對稱性。最后，假設(shè)(a,b)≤(a，b)和(a，b)≤(a,b)，其中a,a,a∈A且b,b,b∈B，那么a≤a且a≤a，所以，由A中偏序的傳遞性推出a≤a。類似地，b≤b且b≤b，所以由B中偏序的傳遞性推出b≤b。因此，(a,b)≤(a，b)，由此推出在AB中偏序的傳遞性成立，從而得到AB是一個偏序集。

6在如上笛卡兒積A×B上定義的偏序≤稱作積偏序。設(shè)(A，≤)是一個偏序集，如果a≤b，但a≠b，則稱a<b?，F(xiàn)在假設(shè)(A，≤)和(B，≤)是偏序集，在定理1中已經(jīng)在A×B上定義了積偏序?，F(xiàn)在在A×B上定義另一個有用的偏序，用?表示，它的定義如下：如果a<a,或者a=a且b≤b,那么(a,b)?(a,b)，這種排序稱為字典序。除第一個坐標“相等”的情況外，第一個坐標元素的排序起決定性作用而可以忽略第二個坐標的排序。如果(A，≤)和(B，≤)是全序集，那么在A×B上的字典序?也是一個全序。7例8

設(shè)A=?R，用通常的排序≤，那么平面R2=R×R給出了字典序，如圖6.1所示?？梢钥吹狡矫媸怯勺值湫蛩a(chǎn)生的全序，每條垂直線有通常的序，并且在該直線上的點比它右邊的垂直線上的點小。因此，在圖6.1中,p2?p3,p1?p2,p1?p3。8圖6.1字典序很容易擴展到笛卡兒積A1×A2×…×An：

當且僅當

或

和

或

，

和

或…

，

和

因此，第一個坐標完全決定了排序（除非它相等），在第一個坐標相等的情況下，考慮第二個坐標。如果再次相等，考慮第三個坐標，等等。9例9設(shè)S={a，b，…，z}是通常的字母表，采用通常的全序方法(a≤b，b≤c，…，y≤z)。于是S?n=S×S×…×S(n個因子)能與長度為n的所有字集合等同。在S?n上的字典序具有性質(zhì)：如果w1?w2(w1，w2∈S?n)，那么w1在字典列表中將先于w2。這一事實說明了字典序名稱的由來。因此，park?part，help?hind，jump?mump。因為j<m，所以第三個為真。因為h=h,e<i,所以第二個為真。因為p=p，a=a，r=r，k<t，所以第一個為真。

如果S是一個偏序集，那么可以用下面的方法把字典序擴展到S*(見1.3節(jié))。如果x=a1a2…an和y=b1b2…bk屬于S*并且n≤k，那么如果在Sn的字典序下有(a1，…，an)?(b1，…，bk)，則稱Sn中x?y。10在上一自然段，使用了n個數(shù)組(a1,a2,…，an)∈S?n，它實際上與字符串a(chǎn)1a2…an∈S*是長度為n的同一序列，只不過用不同的符號表示罷了。這種符號的不同是出于歷史原因，在使用它們時依賴于上下文環(huán)境而轉(zhuǎn)換。例10設(shè)S是{a，b，…，z}，按通常的次序，那么S*是任意長度的所有可能的“詞”的集合，無論這些“詞”是否有意義。因此，在S*中有help?helping，因為在S4中，help?help。類似地，因為在S6中helper?helping，所以helper?helping。正如例子help?helping所示，排序包括了詞頭排序，即：任意一個詞比它的所有詞頭(開始部分)大，這也是字典中詞的出現(xiàn)方法。11因為一個偏序是一種關(guān)系，所以可考慮在有限集合上任意偏序的有向圖。將看到偏序的有向圖表示方法比那些一般的關(guān)系有向圖表示方法更簡單。下面的定理提供了該方向的第一個結(jié)果。定理2偏序的有向圖中沒有長度比1大的環(huán)。證明

假設(shè)在集合A上偏序≤的有向圖包含一個長度為n≥2的環(huán)，那么存在互不相同的元素a1，a2，…，an∈A，使得a1≤a2,a2≤a3,…,an–1≤an,an≤a1由偏序的傳遞性，使用n–1次得到a1≤an。由反對稱性有an≤a1和a1≤an，從而推出an=a1，這與假設(shè)a1，a2，…，an互不相同是矛盾的。12哈塞圖設(shè)A是一個有限集合，定理2表明A上偏序的有向圖只有長度為1的環(huán)。事實上，因為偏序是自反的，所以在偏序的有向圖中每個頂點被包含在長度為1的環(huán)中。為了簡化這件事情，將去掉有向圖中所有這種環(huán)。因此，在圖6.2(a)中表示的有向圖將畫成如圖6.2(b)所示的圖。13圖6.2我們也去掉由傳遞性推出的所有邊。因此，如果a≤b且b≤c，那么得到a≤c。在這種情況下，省略從a到c的邊，但要畫從a到b和從b到c的邊。例如，圖6.3(a)所示的有向圖將畫成圖6.3(b)所示的圖。還約定用所有朝上的邊來畫偏序的有向圖，以致箭頭可以從邊上省略。最后，用點取代圓圈來表示頂點。因此，圖6.4所示的圖給出了圖6.2(a)所示有向圖的最終形式。這樣的偏序圖比它的有向圖簡單得多，稱作偏序集上偏序的哈塞圖。因為哈塞圖完全描述了有關(guān)的偏序，所以它是一種非常有用的工具。14圖6.3圖6.4例11設(shè)A={1，2，3，4，12}，考慮A上的整除性偏序，即：如果a,bA，a≤b當且僅當a?|?b。畫出偏序集(A，≤)的哈塞圖。解

在圖6.5中給出了圖6.5的偏序集的有向圖。哈塞圖如圖6.6所示，由此可以看出哈塞圖的簡單性。

15圖6.5

圖6.6例12

設(shè)S={a，b，c}和A=P(S)，畫出具有偏序(集合包含)關(guān)系的偏序集A的哈塞圖。解

首先確定A，得到A={,{a},,{c},{a，b},{a，c},{b，c},{a，b，c}}于是哈塞圖如圖6.7所示。

注意,一個有限全序集的哈塞圖總是具有圖6.8所示的形式。16圖6.7圖6.8容易看到如果(A，≤)是一個偏序集，(A，≥)是對偶偏序集,那么(A,≥)的哈塞圖恰好是把(A，≤)的哈塞圖顛倒過來。例13

圖6.9(a)給出了偏序集(A，≤)的哈塞圖，其中A={a，b，c，d，e，f?}。圖6.9(b)給出了對偶偏序集(A，≥)的哈塞圖。注意，像剛才提到的那樣，這些圖能夠通過把另一個圖顛倒過來而得到。17圖6.9拓撲排序如果A是具有偏序≤的一個偏序集，有時需要對集合A找一個全序

，使得該全序只不過是已知偏序在如下意義的一個擴展：如果a≤b，那么a?b。構(gòu)造如?的一個全序的過程稱作拓撲排序。該問題產(chǎn)生于當人們必須把有限偏序集A輸入計算機時。A中的元素必須以某種次序被輸入，并且也許要求它們輸入后保持偏序，即：如果a≤b，那么a是在b之前被輸入。拓撲排序?將給出遇到這種情況時元素輸入的次序。18例14

對于哈塞圖如圖6.10所示的偏序集，給出一個拓撲排序。解

顯然如圖6.11(a)所示的哈塞圖的偏序?是一個全序。容易看到每一對元素用≤排序也就是用?排序，所以?是偏序≤的拓撲排序。圖6.11(b)和(c)給出了此問題的另外兩種解答。

19圖6.10圖6.11同構(gòu)設(shè)(A，≤)和(A，≤)是偏序集，f?：A→A是A與A之間的一一對應(yīng)。如果對于A中任意的a和b，a≤b當且僅當

f(a)≤f?(b)，那么稱函數(shù)

f是從(A，≤)到(A，≤)的一個同構(gòu)。如果

f：A→A是一個同構(gòu)，那么稱(A，≤)和(A，≤)是同構(gòu)的偏序集。例15

設(shè)A是正整數(shù)集合Z+，≤是A上通常的偏序(見例2)。A是正偶數(shù)集合，≤是A上通常的偏序。函數(shù)f：A→A由f(a)=2a給出，它是從(A，≤)到(A，≤)的一個同構(gòu)。首先，因為如果f(a)=f(b)，那么2a=2b，即a=b，所以f是單射。其次，Dom(f?)=A，所以f是處處有定義的。最后，如果c∈A，那么有某個a∈Z+使得c=2a，所以c=f(a)。這就證明了f是滿射。因此，f是一一對應(yīng)。最后，如果a和b是A中的元素，則顯然a≤b當且僅當2a≤2b。因此f是一個同構(gòu)。

20假設(shè)f：A→A是從偏序集(A，≤)到偏序集(A，≤)的一個同構(gòu)。還假設(shè)B是A的一個子集，B=f?(B)是對應(yīng)的A的子集。那么從同構(gòu)的定義可以看到下面的原理必定成立。定理3(對應(yīng)原理)如果B的元素相互間或者與A的其他元素間有某種性質(zhì)，并且這種性質(zhì)可完全根據(jù)關(guān)系≤定義，那么B的元素一定具有由≤定義的完全相同的性質(zhì)。21例16

設(shè)(A，≤)是偏序集，它的哈塞圖如圖6.12所示。假設(shè)f是從(A，≤)到某個其他偏序集(A，≤)的一個同構(gòu)。首先注意對A中任意x有d≤x(稍后將d這樣的元稱為A的“最小元”)，那么在A中對應(yīng)元f?(d)一定滿足性質(zhì)：對A中的所有y有f?(d)≤y。作為另一個例子，注意ab和b

a，這種元素對稱為在A中是不可比的。于是從對應(yīng)原理得到f(a)和f(b)在A中一定也是不可比的。

22圖6.12確切地說，設(shè)(A，≤)和(A，≤)是有限偏序集，f：A→A是一一對應(yīng)，H是(A，≤)的任意哈塞圖。那么1．如果f是一個同構(gòu)，H的每個符號a用f?(a)取代，那么H將變?yōu)?A，≤)的一個哈塞圖。反之2．如果H是(A，≤)的一個哈塞圖，當每個符號a由f?(a)代替時，那么f是一個同構(gòu)。這就說明了名字“同構(gòu)”的合理性，因為同構(gòu)偏序集用哈塞圖描述有相同的“形狀”。23例17

設(shè)A={1，2，3，6}，≤是關(guān)系|(整除)，圖6.13(a)表示(A，≤)的哈塞圖。設(shè)A=P({a，b})={，{a}，，{a，b}}，≤是集合包含

，如果f：A→A定義如下f(1)=，f(2)={a}，f(3)=，f(6)={a，b}那么容易看到f是一一對應(yīng)。如果哈塞圖的每個符號a∈A用f?(a)代替，結(jié)果如圖6.13(b)所示。因為很顯然這是(A，≤)的一個哈塞圖，所以函數(shù)

f是一個同構(gòu)。24圖6.136.2偏序集的極值元在一個偏序集中，某些元素對于偏序集的許多性質(zhì)和應(yīng)用具有特殊的重要性。在這一節(jié)討論這些元素，在稍后幾節(jié)可以看到它們所起的重要作用。本節(jié)考慮一個偏序集(A，≤)。一個元素a∈A，如果在A中不存在任何元素c使得a<c，則稱a是A的一個極大元。一個元素b∈A，如果在A中不存在任何元素c使得c<b，則稱b是A的一個極小元。由此立即得到：如果(A，≤)是一個偏序集，那么(A，≥)是它的對偶偏序集。元素a∈A是(A，≥)的一個極大元當且僅當a是(A，≤)的一個極小元。同樣，a是(A，≥)的一個極小元當且僅當它是(A，≤)的一個極大元。25例1

考慮偏序集A，它的哈塞圖如圖6.22所示。元素a1,a2和a3是A的極大元，元素b1,b2和b3是極小元。注意，因為在b2與b3之間不存在任何直線，所以可以斷定既沒有b3≤b2也沒有b2≤b3。

圖6.2226例2

設(shè)A是有通常偏序≤的非負實數(shù)偏序集，那么0是A的極小元，A不存在極大元。例3

偏序集Z具有通常的偏序≤，它沒有極大元也沒有極小元。

定理1

設(shè)A是有偏序≤的有限非空偏序集，那么A至少有一個極大元和一個極小元。證明

設(shè)a是A的任意一個元素，如果a不是極大元，那么能夠找到一個元a1∈A，使得a<a1；如果a1不是極大元，那么能夠找到一個元a2∈A，使得a1<a2。因為A是有限集，所以這種推理不能無限次繼續(xù)下去。因此，最終獲得有限鏈：a<a1<a2<…<ak–1<ak，它不能再擴充了。因此，對任意b∈A，不能有ak<b，所以ak是(A，≤)的一個極大元。同理可得對偶偏序集(A，≥)有一個極大元，所以(A，≤)有一個極小元。27用極小元的概念，能夠為已知有限偏序集(A,≤)給出一種求拓撲排序的算法。首先注意如果a∈A且B=A–{a}，那么B也是≤在B×B限制下的一個偏序集(見4.2節(jié))。于是得到如下的算法，該算法產(chǎn)生一個名為SORT的線性數(shù)組。假設(shè)SORT是按遞增下標排序，即：SORT[1]SORT[2]…，那么用這種方式定義A上的關(guān)系

是(A，≤)的一種拓撲排序。算法找有限偏序集(A，≤)的拓撲排序。步驟1：選擇A的一個極小元a。步驟2：使a成為SORT的下一項并且用A–{a}代替A。步驟3：重復(fù)步驟1和步驟2直到A={}。28例4

設(shè)A={a,b,c,d,e}，A上偏序≤的哈塞圖如圖6.23(a)所示，該偏序集的一個極小元是標號為d的頂點(也可選e)。把d放入SORT[1]中，并且在圖6.23(b)中給出A–3u85fge的哈塞圖。新A的一個極小元是e，所以e成為SORT[2]，A–{e}如圖6.23(c)所示。這個過程繼續(xù)下去，直至用完A中元素為止，并且填充SORT。圖6.23(f)給出了全部數(shù)組SORT和對應(yīng)于SORT的偏序集的哈塞圖。這就是(A，≤)的一個拓撲排序。29圖6.23一個元素a∈A，如果對所有x∈A有x≤a，則稱a是A的最大元。一個元素a∈A，如果對所有x∈A有a≤x，則稱a是A的最小元。同前面一樣，(A，≤)的一個元a是最大元(最小元)當且僅當它是(A，≥)的最小元(最大元)。例5

考慮例2中定義的偏序集，那么0是一個最小元，不存在最大元。

例6

設(shè)S={a,b,c}，考慮6.1節(jié)的例12定義的偏序集A=P(S)，空集是A的一個最小元，集合S是A的一個最大元。

例7

有通常偏序的偏序集Z既無最小元也無最大元。30定理2

一個偏序集至多有一個最大元也至多有一個最小元。證明

假設(shè)a和b是偏序集A的最大元，那么，由于b是一個最大元，所以有a≤b。類似地，由于a是一個最大元，所以有b≤a。因此，由反對稱性質(zhì)得到a=b，故如果偏序集有一個最大元，那么它只有一個這樣的元。因為對所有偏序集這一事實都為真，所以對偶偏序集(A，≥)至多有一個最大元，故(A，≤)也至多有一個最小元。

一個偏序集的最大元，如果存在的話，用I表示，它常稱作單位元。類似地，一個偏序集的最小元，如果存在的話，用0表示，它常稱作零元?？紤]某個偏序集A和A的子集B，一個元素a∈A，如果對所有b∈B有b≤a，則稱a是B的一個上界。如果對所有b∈B有a≤b，則稱a是B的一個下界。31例8

考慮偏序集A={a，b，c，d，e，f，g，h}，它的哈塞圖如圖6.24所示。求A的下列子集的所有上界和下界。(a)B1={a，b}(b)B2={c，d，e}

解(a)B1沒有下界，它的上界是c，d，e，f，g，h。(b)B2的上界是f，g和h，它的下界是c，a和b。32例8表明一個偏序集的子集B可以有也可以沒有上界或下界(在A中)，而且B的上界或下界可以屬于也可以不屬于B本身。圖6.24設(shè)A是一個偏序集，B是A的一個子集。如果一個元a∈A是B的上界并且當a是B的一個上界時，有a≤a，則稱a是B的最小上界(LUB(B))。因此，如果對所有b∈B，有b≤a并且如果當a∈A也是B的一個上界時，那么a≤a，則a=LUB(B)。類似地，如果一個元a∈A是B的一個下界，并且當a是B的一個下界時，a≤a，則稱a是B的最大下界(GLB(B))。因此，如果對所有b∈B有a≤b，并且當a∈A也是B的一個下界時，有a≤a，那么a=GLB(B)。同通常情況一樣，(A，≤)中的上界對應(yīng)(A，≥)中的下界(對于同一集合元素)，(A，≤)中的下界對應(yīng)(A，≥)中的上界。對于最大下界和最小上界，類似的命題成立。33例9

設(shè)A是例8中考慮的偏序集，有例中所定義的子集B1和B2，對于(a)B1；(b)B2；求所有最小上界和最大下界。解(a)因為B1沒有下界，所以它沒有最大下界。然而，LUB(B1)=c。(b)因為B2的下界是c，a和b，所以易得GLB(B2)=c,B2的上界是f，g和h。因為f和g不是可比的，所以推出B2沒有最小上界。

定理3

設(shè)(A，≤)是一個偏序集，那么A的一個子集B至多有一個LUB和一個GLB。

證明類似于定理2的證明。34用A的哈塞圖的觀點對有限偏序集A上的LUB和GLB做一些解釋。設(shè)B={b1，b2，…,br}，如果a=LUB(B)，那么a是通過向上道路從b1，b2，…,br可能到達的第一個頂點。類似地，如果a=GLB(B)，那么a是通過向下道路從b1，b2，…，br可能到達的第一個頂點。例10

設(shè)A={1，2，3，4，5，…，11}是偏序集，它的哈塞圖如圖6.25所示，如果LUB和GLB存在的話，求B={6，7，10}的LUB和GLB。35解

從頂點6，7和10搜索所有向上的道路，可以發(fā)現(xiàn)LUB(B)=10。類似地，從6，7和10通過檢查所有向下的道路，可以發(fā)現(xiàn)GLB(B)=4。圖6.25定理4

假設(shè)(A，≤)和(A，≤)是在同構(gòu)f：A→A下的同構(gòu)偏序集。(a)如果a是(A,≤)的一個極大(極小)元，那么f?(a)是(A，≤)的一個極大(極小)元。(b)如果a是(A，≤)的最大(最小)元，那么f?(a)是(A，≤)的最大(最小)元。(c)如果a是A的子集B的一個上界(下界，最小上界，最大下界)，那么f?(a)是A的子集

f?(B)的一個上界(下界，最小上界，最大下界)。(d)如果(A，≤)的每個子集有一個LUB(GLB)，那么(A，≤)的每個子集有一個LUB(GLB)。36例11

驗證偏序集(A，≤)與(A，≤)不同構(gòu)，它們的哈塞圖分別如圖6.26(a)和(b)所示。解

因為(A，≤)有一個最大元a，而(A,≤)沒有最大元，所以兩個偏序集不是同構(gòu)的。因為(A，≤)沒有一個最小元，而(A,≤)有一個最小元，所以也能推出它們不是同構(gòu)的。37圖6.266.3格格是任意兩個元素所組成的子集{a，b}都有最小上界和最大下界的一個偏序集(L,≤)。用

ab表示LUB({a，b})并且稱它為a和b的并。類似地，用ab表示GLB({a，b})并且稱它為a和b的交。格結(jié)構(gòu)經(jīng)常出現(xiàn)在計算和數(shù)學(xué)應(yīng)用中。注意，格是如1.6節(jié)所描述的具有二元運算“并”與“交”的一種數(shù)學(xué)結(jié)構(gòu)。例1

設(shè)S是一個集合，L=P(S)，已看到包含

是L上的一個偏序。設(shè)A和B屬于偏序集(L，)，那么AB是集合A∪B。為了看清這一點，注意AA∪B,BA∪B，如果AC和BC，那么得到A∪BC。類似地，可證明在(L，)中元素AB是集合A∩B。所以，L是一個格。38例2

考慮偏序集(Z+，≤)，對于Z+中的a和b，a≤b當且僅當a?|?b，于是L是一個格。在這個格中，a與b的并和交分別是它們的最小公倍數(shù)和最大公約數(shù)(見1.4節(jié))，即ab=LCM(a，b)，ab=GCD(a，b) 例3

設(shè)n是一個正整數(shù)，Dn是n的所有正因子的集合。那么Dn在例2所考慮的整除關(guān)系下是一個格。因此，如果n=20，則有D20={1，2，4，5，10，20}，D20的哈塞圖如圖6.39(a)所示。如果n=30，則有D30={1,2,3,5,6,10,15,30}。D30的哈塞圖如圖6.39(b)所示。39例4

圖6.40中的哪些哈塞圖表示格？解

哈塞圖(a)，(b)，(d)和(e)表示格。圖(c)不表示一個格，因為fg不存在。圖(f)不表示一個格，因為de和bc都不存在。圖(g)不表示一個格，因為cd不存在。40例5

在6.1節(jié)的例4中已經(jīng)看到，在集合A上所有等價關(guān)系所組成的集合

在集合包含偏序下是一個偏序集。現(xiàn)在能夠推出

是一個格。等價關(guān)系R和S的交是它們的交集R∩S，并且它們的并是它們的并集的傳遞閉包(R∪S)

(見4.8節(jié))。設(shè)(L，≤)是一個偏序集，(L，≥)是對偶偏序集。如果(L，≤)是一個格，可以證明(L，≥)也是一個格。事實上，對于L中任意a和b，在(L，≤)中a和b的最小上界等于(L，≥)中a和b的最大下界。類似地，在(L，≤)中a和b的最大下界等于(L，≥)中a和b的最小上界。如果L是一個有限集合，那么通過檢驗偏序集的哈塞圖和它對偶的哈塞圖，就很容易看到這一性質(zhì)。41例6

設(shè)S是一個集合，L=P(S)，那么(L，)是一個格，它的對偶格是(L，)，這里

是“包含于”，

是“包含”。于是本例前面的討論表明在偏序集(L，)中的并A∨B是集合A∩B，交A∧B是集合A∪B。

定理1

如果(L1，≤)和(L2，≤)是格，那么(L，≤)是一個格，其中L=L1×L2，L的偏序≤是積偏序。證明

分別用∨1和∧1表示L1中的并和交，用∨2和∧2表示L2中的并和交。從6.1節(jié)的定理1可知，L是一個偏序集?，F(xiàn)在需要證明如果(a1,b1),(a2,b2)∈L，那么(a1,b1)∨(a2,?b2)和(a1,?b1)∧(a2,b2)在L中存在。事實上，可以驗證：(a1,b1)∨(a2,b2)=(a1∨1a2,b1∨2b2)(a1,b1)∧(a2,b2)=(a1∧1a2,b1∧2b2)于是L是一個格。42例7

設(shè)L1和L2分別是由圖6.41(a)和(b)給出的格，那么L=L1×L2是如圖6.41(c)所示的格。設(shè)(L，≤)是一個格，S是L的一個非空子集，如果當a∈S且b∈S時，有a∨b∈S和a∧b∈S，則稱S是L的子格。

43例8

n的所有正因子格Dn?(見例3)是整除關(guān)系下(見例2)格Z+的一個子格。

例9

考慮如圖6.42(a)所示的格L，則圖6.42(b)所示的偏序子集Sb不是L的一個子格，因為a∧b

Sb。圖6.42(c)中的偏序子集Sc不是L的一個子格，因為a∨b

Sc。然而，當把Sc自身視為一個偏序集時，它是一個格。如圖6.42(d)所示的偏序子集Sd是L的一個子格。44同構(gòu)的格如果f：L1→L2是從偏序集(L1，≤1)到偏序集(L2，≤2)的一個同構(gòu)，那么6.2節(jié)的定理4表明L1是一個格當且僅當L2是一個格。事實上，如果a和b是L1的元素，那么f?(a∧b)=f?(a)∧f?(b)和f?(a∨b)=f?(a)∨f?(b)。如果兩個格作為偏序集是同構(gòu)的，則稱它們是同構(gòu)的格。例10

設(shè)L是格D6，L是在包含關(guān)系下的格P(S)，S={a，b}，這些偏序集在6.1節(jié)的例16中已經(jīng)討論過，并且已證明它們是同構(gòu)的。因此，由于兩者都是格，所以它們是同構(gòu)的格。

45如果f：A→B是從格(A，≤)到集合B的一一對應(yīng)，那么可用函數(shù)f在B上定義偏序≤。如果b1和b2是在B中，那么有A的惟一元a1和惟一元a2使得b1=f?(a1)和b2=f?(a2)。定義b1≤b2(在B中)當且僅當a1≤a2(在A中)。如果A和B是有限的，那么能夠從幾何上描述這個過程如下。對(A，≤)構(gòu)造哈塞圖，于是每個符號a用B中的對應(yīng)元f?(a)取代，結(jié)果得到B上偏序≤的哈塞圖。當給出B上的偏序≤時，f將是從偏序集(A，≤)到偏序集(B，≤)的一個同構(gòu)。為了看清這一點，注意到f已經(jīng)被假設(shè)是一一對應(yīng)。≤的定義說明對于A中任意的a1和a2，a1≤a2當且僅當f?(a1)≤f?(a2)。因此，f是一個同構(gòu)。因為(A，≤)是一個格，所以(B，≤)也是格，且它們是同構(gòu)的格。46例11

如果A是一個集合，設(shè)

是A上所有等價關(guān)系所組成的集合，∏是A上所有劃分的集合。在5.1節(jié)的例13中，已構(gòu)造了從

到∏的一一對應(yīng)f。在6.1節(jié)的例4中，考慮了在

上的偏序

。從這個偏序可用上面解釋的f構(gòu)造∏上的偏序≤。由構(gòu)造可知，如果P?1和P?2是A的劃分，R1和R2分別是對應(yīng)于這些劃分的等價關(guān)系，那么P?1≤P?2將意味著R1R2。因為在例5中已證明(，)是一個格，并且知道f是一個同構(gòu)，所以得到(∏，≤)也是一個格。在第35題中可直接根據(jù)它們本身的劃分描述偏序≤。47格的性質(zhì)在證明格的許多性質(zhì)之前，回顧a∨b和a∧b的意義。1．a(chǎn)≤a∨b且b≤a∨b；a∨b是a和b的上界。2．若a≤c且b≤c，則a∨b≤c；a∨b是a和b的最小上界。1．a(chǎn)∧b≤a且a∧b≤b；a∧b是a和b的下界。2．若c≤a且c≤b，則c≤a∧b；a∧b是a和b的最大下界。48定理2

設(shè)L是一個格，那么對L中每個a和b，有(a)a∨b=b

當且僅當a≤b。(b)a∧b=a

當且僅當a≤b。(c)a∧b=a

當且僅當a∨b=b。證明(a)假設(shè)a∨b=b，因為a≤a∨b=b，所以有a≤b。反之，如果a≤b，那么因b≤b，則b是a和b的一個上界；因此，由最小上界的定義得到a∨b≤b。因為a∨b是一個上界，b≤a∨b，所以a∨b=b。(b)類似于(a)的證明，留給讀者作為練習(xí)。(c)從(a)和(b)的證明即得證。49例12

設(shè)L是一個全序集，如果a,b∈L，那么或者a≤b或者b≤a。從定理2可知L是一個格，因為每對元素有最小上界和最大下界。定理3

設(shè)L是一個格，那么1.冪等性質(zhì)(a)a∨a=a(b)a∧a=a2.交換性質(zhì)(a)a∨b=b∨a(b)a∧b=b∧a3.結(jié)合性質(zhì)(a)a∨(b∨c)=(a∨b)∨c(b)a∧(b∧c)=(a∧b)∧c4.吸收性質(zhì)(a)a∨(a∧b)=a(b)a∧(a∨b)=a證明1.命題從LUB和GLB的定義可得到。2.LUB和GLB的定義對a和b是對稱的，所以結(jié)論成立。503.(a)從LUB的定義得到a≤a∨(b∨c)和b∨c≤a∨(b∨c)。而且b≤b∨c和c≤b∨c，于是由傳遞性得b≤a∨(b∨c)和c≤a∨(b∨c)。因此，a∨(b∨c)是a和b的一個上界，所以由最小上界的定義有

a∨b≤a∨(b∨c)因為a∨(b∨c)是a∨b和c的一個上界，所以得到(a∨b)∨c≤a∨(b∨c)類似地有：a∨(b∨c)≤(a∨b)∨c，由≤的反對稱性可知性質(zhì)3(a)成立。(b)證明類似于第(a)部分，略去不證。

4.(a)因為a∧b≤a和a≤a，于是a是a∧b和a的一個上界，所以a∨(a∧b)≤a。另一方面，由LUB的定義有a≤a∨(a∧b)，所以a∨(a∧b)=a。(b)證明類似于第(a)部分，略去不證。51從性質(zhì)3知道，可把a∨(b∨c)和(a∨b)∨c僅寫作a∨b∨c，類似地有a∧b∧c，而且可把LUB({a1,a2,…,an})寫作a1∨a2∨…∨an，GLB({a1,a2,…，an})寫作a1∧a2∧…∧an，因為可以用歸納法證明這些并和交的各項的分組是獨立的。定理4

設(shè)L是一個格，那么對于L中的每個a，b和c，有1．如果a≤b，那么(a)a∨c≤b∨c (b)a∧c≤b∧c2．a(chǎn)≤c和b≤c當且僅當a∨b≤c。3．c≤a和c≤b當且僅當c≤a∧b。4．如果a≤b和c≤d，那么(a)a∨c≤b∨d (b)a∧c≤b∧d證明

證明留作練習(xí)。52幾種特殊類型的格一個格L稱為是有界的，如果它有最大元I和最小元0(見6.2節(jié))。例13

格Z+在整除偏序下(如例2中的定義)不是一個有界的格，因為它有最小元——數(shù)1，但沒有最大元。

例14

格Z在偏序≤下不是有界的，因為它既無最大元也無最小元。

例15

格P(S)（如例1所定義，它是集合S的所有子集）的集合是有界的。它的最大元是S，最小元是。

如果L是一個有界格，那么對所有a∈A，有0≤a≤I，a∨0=a，a∧0=0a∨I=I，a∧I=a53定理5

設(shè)L={a1,a2,…,an}是一個有限格，那么L是有界的。證明

L的最大元是a1∨a2∨…∨an，L的最小元是a1∧a2∧…∧an。

注意，定理5的證明是一個構(gòu)造性證明。證明L有界是通過構(gòu)造最大元和最小元完成的。稱格L是分配的，如果對L中的任意a,b和c，有下面的分配性質(zhì)：1．a(chǎn)∧(b∨c)=(a∧b)∨(a∧c)2．a(chǎn)∨(b∧c)=(a∨b)∧(a∨c)如果L不是分配的，則稱L是非分配的。當元素a,b或c中任意兩個元素是相等的或者元素中任意一個是0或I時，可證明分配性質(zhì)成立，將它留作一個練習(xí)。該結(jié)論可減少在證明分配性質(zhì)成立時所必須檢驗的情形的數(shù)目。然而，分配性質(zhì)的證明通常是一項冗長乏味的任務(wù)。54例16

對于集合S，P(S)是分配格，因為并集和交集(分別為并和交)都滿足如1.2節(jié)所給出的分配性質(zhì)。

例17

如圖6.43所示的格是分配的。因為可以通過從元素a,b,c和d中選出所有有序?qū)眚炞C分配性質(zhì)。

例18

證明：圖6.44所示的格是非分配的。證明

(a)顯然有

a∧(b∨c)=a∧I=a

而(a∧b)∨(a∧c)=b∨0=b(b)注意到a∧(b∨c)=a∧I=a而(a∧b)∨(a∧c)=0∨0=055定理6

格L是非分配的當且僅當它包含一個同構(gòu)于例18中兩個格之一的子格?？赏ㄟ^檢查L的哈塞圖使定理6得到十分有效的使用。設(shè)L是有最大元I和最小元0的一個有界格，a∈L。一個元素a∈L稱作a的補，如果a∨a=I，a∧a=0注意：0=I,I=0。例19

格L=P(S)中的每個元素有一個補，因為如果A∈L，那么它的補集

有性質(zhì)A∨=S和A∧=，即集合的補也是格L中的補。

例20

圖6.44具有每個格中的每個元素均有補的性質(zhì)。元素c在兩種情況下有兩個補a和b。56例21

考慮例3中討論的格D20和D30，如圖6.39所示。注意，在D30中每個元素有一個補。例如，如果a=5，那么a=6，然而在D20中的元素2和元素10沒有補。

例20和21表明一個格中的元素a不一定有補，并且它可能有幾個補。然而，對于一個有界分配格，情況大為受限，正如下面定理所表明的那樣。57定理7

設(shè)L是一個有界的分配格，如果一個補存在，那么它是惟一的。證明

設(shè)a和a是元素a∈L的補，那么a∨a=I

，a∨a=I,a∧a=0，a∧a=0用分配律得到a=a?∨0=a?∨(a∧a?)=(a?∨a)∧(a?∨a?)=I∧(a?∨a?)=a?∨a?同樣a=a∨0=a∨(a∧a?)=(a?∨a)∧(a?∨a?)?=I∧(a?∨a?)=a?∨a?因此a=a?。58定理7的證明是一個直接證明，但是在如何選擇a

和a

的表達方式方面并不是很清楚。在這種證明中，含有某些嘗試和錯誤，但是人們希望使用L是有界的和L是可分配的假設(shè)。另外一種證明方法見第36題。一個格L稱作有補的，如果它是有界的并且L中的每個元素有一個補。例22

格L=P(S)是有補的。注意在這種情況下，L中的每個元素有惟一的補，這一點能夠直接看到或者通過定理7看到。

例23

在例20中所討論的格是有補的(見圖6.44)。在這種情況下，補不是惟一的。

596.4有限布爾代數(shù)本節(jié)討論在計算機科學(xué)中有著大量應(yīng)用的一類格。在6.3節(jié)的例6中已經(jīng)看到，如果S是一個集合，L=P(S)，

是通常的包含關(guān)系，那么偏序集(L，)是一個格。這些格有許多非一般格所共有的性質(zhì)。正因如此，它們很容易用來處理許多實際問題，并且在各種應(yīng)用中起著非常重要的作用。本節(jié)將僅限于考慮格(P(S)，)，其中S是一個有限集合。從尋找所有本質(zhì)上不同的例子開始。60定理1

如果S1={x1,x2,…,xn}和S2={y1,y2,…，yn}是有n個元素的任意兩個有限集合，那么格(P(S1)，)和(P(S2)，)是同構(gòu)的。特別可以同樣地畫出它們的哈塞圖。證明

像圖6.58所示的那樣，把集合的元素排列起來，使得S1在S2上面，S1中的每個元素直接對應(yīng)于S2中有相同標號的元素。對S1的每個子集A,設(shè)f?(A)是S2的子集，該子集是由與A中元素對應(yīng)的所有元素組成的。圖6.59給出了S1的一個特殊子集A和對應(yīng)的S2的子集f(A)容易看到，剛才描述的函數(shù)f是從S1的子集到S2的子集的一一對應(yīng)。同樣顯然，如果A和B是S1的任意子集,那么AB當且僅當f(A)f(B)。有關(guān)的細節(jié)省略。因此,格(P(S1),)和(P(S2),)是同構(gòu)的。

61該定理的一個基本要點是格(P(S)，)完全由偏序集的數(shù)|S|所決定，在任何情況下它不依賴于S中元素的性質(zhì)。例1圖6.60(a)和(b)分別給出了格(P(S)，)和(P(T)，)的哈塞圖，其中S={a,b,c}，T={2，3，5}。從此圖很容易看到兩個格是同構(gòu)的。事實上，一種可能的同構(gòu)f?:?S→T由下述給出：f?({a})={2},f?()={3},f?({c})={5},f?({a,b})={2,3},f?({b,c})={3,5},f?({a,c})={2,5},f?({a,b,c})={2,3,5},f?()=.

62因此，對每個n=0,1,2,…,只存在形如(P(S)，)的一類格。這種格僅依賴于n而不依賴于S，正如3.1節(jié)的例2所表示的那樣，它有2n個元素?；仡?.3節(jié)，如果一個集合S有n個元素，那么S的所有子集可用長度為n的0和1的序列來表示。所以，可用這種序列給格(P(S)，)的哈塞圖標號。這樣做的目的就是使圖不依賴于特殊集合S，并且強調(diào)它只依賴于n的事實。例2

圖6.60(c)給出了圖6.60(a)和(b)中出現(xiàn)的圖是如何用0和1的序列來標號的。這種標號同樣能很好地用于描述圖6.60(a)或(b)的格，或者從任意有三個元素的集合S產(chǎn)生的格(P(S)，)。

63一個有n個元素的集合，如果對應(yīng)它的格的哈塞圖是用長度為n的0和1的序列標號的(如上所述)，那么得到的格取名為Bn。在Bn中的偏序性質(zhì)能夠直接描述如下。如果x=a1a2…an和y=b1b2…bn是Bn的兩個元素，那么1．x≤y當且僅當對k=1,2,…,n有ak≤bk(按數(shù)0或1)。2．x∧y=c1c2…cn,這里ck=min{ak，bk}。3．x∨y=d1d2…dn，這里dk?=?max{ak,bk}。4．x有一個補x'=z1z2…zn，其中如果xk=0，則zk=1，如果xk=1，則zk=0。64這些命題的真實性可通過觀察(Bn，≤)與(P(S),)是同構(gòu)的這一事實看到，所以在Bn中的每個x和y對應(yīng)于S中的子集A和B。于是x≤y，x∧y,x∨y和x'

分別對應(yīng)于AB，A∩B，AB和(集合補)(請驗證)。對于n=0,1,2,3,圖6.61給出了格Bn的哈塞圖。由上可知，每個格(P(S)，)與Bn

同構(gòu)，其中n=|S|。其他的格也可能與某個Bn

同構(gòu)，因此它也具有Bn所具有的所有特殊性質(zhì)。65例3在6.1節(jié)的例17中，已考慮在整除偏序下6的所有正整數(shù)因子所組成的格D6,它的哈塞圖在該例中也已給出。現(xiàn)在可以看到，D6與B2是同構(gòu)的。事實上，f：D6→B2是一個同構(gòu)，其中

f?(1)=00，f?(2)=10，f?(3)=01，f?(6)=11所以可以給出以下定義。一個有限格稱為一個布爾代數(shù)，如果對某個非負整數(shù)n它與Bn是同構(gòu)的。因此，每個Bn是一個布爾代數(shù)，所以每個格(P(S)，)也是一個布爾代數(shù)，其中S是一個有限集合。例3表明D6也是一個布爾代數(shù)。在本節(jié)只討論有限偏序集。然而，對于這種難以理解的限制，已注意到存在無限偏序集與格(P(S)，)(當然S是無限集合)共享所有相關(guān)的性質(zhì)，但是它不與這些格中任何一個格同構(gòu)。因此，把布爾代數(shù)的定義限制到有限的情況是非常必要的，它對于我們提到的應(yīng)用也是足夠的。66例4考慮格D20和D30，它們分別是在整除偏序下20和30的所有正整數(shù)因子所組成的格。這些偏序集在6.3節(jié)的例3中已介紹過，它們的哈塞圖在圖6.39中已給出。因為D20有6個元素，對任意整數(shù)n≥0，6≠2n，所以推出D20不是布爾代數(shù)。偏序集D30有8個元素，因為8=23，所以它可能是一個布爾代數(shù)。通過圖6.39(b)和圖6.61的比較，可以看到D30與B3是同構(gòu)的。事實上，由f?(1)=000,f?(2)=100,f?(3)=010,f?(5)=001,?f?(6)=110,?f?(10)=101,?f?(15)=011,?f?(30)=111定義的f：D30→B3是一一對應(yīng)，并且是一個同構(gòu)。因此，D30是一個布爾代數(shù)。67對于某個非負整數(shù)n，如果一個有限格L不是包含2n個元素，那么L不可能是一個布爾代數(shù)。如果|L|=2n，則L可以是也可以不是一個布爾代數(shù)。如果L相對來說比較小，那么能夠把它的哈塞圖與Bn的哈塞圖進行比較。用這種方法在例4中已看到D30是一個布爾代數(shù)。然而，如果L很大，那么這種技巧是不現(xiàn)實的。在這種情況下，也許能夠通過直接構(gòu)造一個與某個Bn的同構(gòu)或者等價地與(P(S)，)(S為某個有限集)的同構(gòu)來證明L是一個布爾代數(shù)。例如，假設(shè)想要知道格Dn是否是一個布爾代數(shù)，就需要一種方法進行判斷，無論n是多大。下面的定理給出了該問題的部分回答。68定理2

設(shè)n=p1p2…pk，其中pi

是互不相同的素數(shù)，那么Dn

是一個布爾代數(shù)。證明

設(shè)S={p1,p2,…，pk}，如果TS，aT是T中素數(shù)的積，那么aT|n

。對S的某個子集T，n的任何因子一定具有形式aT(設(shè)a=1)。讀者可以證明，如果V和T是S的子集，VT當且僅當av|aT。同樣，從1.4節(jié)定理6的證明得到aV∩T=aV∧aT=GCD(aV,aT)和

aV∪T=aV∨aT=LCM(aV,?aT)。因此，由f?(T)=aT給出的函數(shù)

f∶P(S)→Dn是從P(S)到Dn的一個同構(gòu)。因為P(S)是一個布爾代數(shù)，所以Dn是一個布爾代數(shù)。例5

因為210=2×3×5×7，66=2×3×11，646=2×17×19，所以由定理2得到

D210，D66和D646都是布爾代數(shù)。

69對于其他非常大的格L，可以通過證明L的偏序沒有所需要的性質(zhì)來證明L不是一個布爾代數(shù)。一個布爾代數(shù)與某個Bn是同構(gòu)的，所以它與某個格(P(S),)也是同構(gòu)的。因此，一個布爾代數(shù)L一定是一個有界格和補格(見6.3節(jié))。換言之，它有一個與集合S對應(yīng)的最大元I和與子集

對應(yīng)的最小元0。同樣，L的每個元素x有一個補x'。根據(jù)6.3節(jié)的例16，L也一定是分配格。于是對應(yīng)原理(見6.1節(jié))告訴人們下面的法則成立。定理3(布爾代數(shù)的替換法則)如果用∧替代∩，用∨替代∪，那么集合S上任意子集關(guān)于包含∪或∩成立的任何公式對于布爾代數(shù)L的任意元素將繼續(xù)成立。70例6

如果L是任一布爾代數(shù)，x,y,z∈L，那么下面三條性質(zhì)成立。1．(x')'=x，

對合性質(zhì)2．(x∧y)'=x'∨y'

德·摩根定律3．(x∨y)'=x'∧y'由布爾代數(shù)的替換法則易知上述命題為真，因為它們對應(yīng)的公式1'．=A2'．=∪

3'．=∩

對于集合S的任意子集A和B成立。

71類似地，用替換法則能夠列出任何布爾代數(shù)必定成立的其他性質(zhì)。下面總結(jié)了布爾代數(shù)(L，≤)的所有基本性質(zhì)，每條性質(zhì)的右邊列出集合S的子集所對應(yīng)的性質(zhì)。假設(shè)x,y和z是L中的任意元素，A，B和C是S的任意子集。同樣，I和0分別表示L的最大元和最小元。1．x≤y

當且僅當x∨y=y。1'．AB

當且僅當A∪B=B。2．x≤y

當且僅當x∧y=x。2'．AB

當且僅當A∩B=A。3．(a)x∨x=x。 3'．(a)A∪A=A。(b)x∧x=x。 (b)A∩A=A。4．(a)x∨y=y∨x。 4'．(a)A∪B=B∪A。(b)x∧y=y∧x。 (b)A∩B=B∩A。725.(a)x∨(y∨z)=(x∨y)∨z。5'.(a)A∪(B∪C)=(A∪B)∪C。(b)x∧(y∧z)=(x∧y)∧z。(b)A∩(B∩C)=(A∩B)∩C。6．(a)x∨(x∧y)=x。6'．(a)A∪(A∩B)=A。(b)x∧(x∨y)=x。(b)A∩(A∪B)=A。7．對L中的所有x,0≤x≤I。7'．對所有AP(S),AS。8．(a)x∨0=x。 8'．(a)A∪=A。(b)x∧0=0。 (b)A∩=。9．(a)x∨I=I。 9'．(a)A∪S?=S。(b)x∧I=x。(b)A∩S=A。7310．(a)x∧(y∨z)=(x∧y)∨(x∧z)。(b)x∨(y∧z)=(x∨y)∧(x∨z)。

10'．(a)A∩(B∪C)=(A∩B)∪(A∩C)。

(b)A∪(B∩C)=(A∪B)∩(A∪C)。11．每個元素x有惟一的補x'?滿足：

(a)x∨x'=I。(b)x∧x'=0。

11'．每個元素A有惟一的補

滿足：(a)A∪=S。(b)A∩=。12．(a)0'=I。 12'．(a)=S。(b)I'=0。(b)=。13．(x')'=x。 13'．=A。7414．(a)(x∧y)'=x'∨y'。14'．(a)=∪

。(b)(x∨y)'=x'

∧y'。(b)=∩

。因此，要證明一個格L不是一個布爾代數(shù)，可以通過證明它不具有上面性質(zhì)中的一條或更多條來實現(xiàn)。例7

證明：如圖6.62所示的哈塞圖的格不是一個布爾代數(shù)。證明

元素a和e都是c的補，即：它們兩個關(guān)于元素c都滿足性質(zhì)11(a)和11(b)。但是性質(zhì)11要求這樣的元素在布爾代數(shù)中是惟一的。因此，所給出的格不可能是一個布爾代數(shù)。

75例8

證明：如果n是一個正整數(shù)，p是一個素數(shù)并且p2|n，那么Dn不是布爾代數(shù)。

解

假設(shè)p2|