第十五章格與布爾代數(shù)

第十五章格與布爾代數(shù)15.1格15.2布爾代數(shù)在介紹格之前，對于我們在前面學(xué)過的偏序，我們要補(bǔ)充兩個內(nèi)容：1.哈斯圖2.最小上界與最大下界1.哈斯圖為了更清楚地描述偏序集合中元素間的層次關(guān)系,也為了更快、更有效地畫出偏序關(guān)系的簡化圖,下面介紹“蓋住”的概念。定義

在偏序集<A,≤>中,對x,yA,x≤y且xy,且A中無任何其它元素z,滿足x≤z且z≤y,稱y蓋住x,或稱x是y的直接前趨,y是x的直接后繼。蓋住關(guān)系記作cov(A)={(x,y)|x,yA且y蓋住x}。顯然蓋住關(guān)系是唯一確定的,蓋住關(guān)系是“≤”的子集。蓋住關(guān)系的關(guān)系圖稱哈斯(Hasse)圖,它實際上偏序關(guān)系是經(jīng)過如下簡化的關(guān)系圖:1.省略關(guān)系圖中的每個結(jié)點處的自環(huán),這是因為偏序關(guān)系“≤”是自反的。2.若x<y且y蓋住x,將代表y的結(jié)點放在代表x的結(jié)點之上,并在x與y之間連線,省去有向邊的箭頭,使其成為無向邊。 若x<y但y不蓋住x,則省去x與y之間的連線。例A={1,2,3,4,5,6,8,10,12,16,24},偏序關(guān)系是A上的整除關(guān)系“≤”,畫出偏序集<A,≤>的哈斯圖。我們先畫出關(guān)系圖。注意圖中，并沒有畫出所有關(guān)系，否則畫面更顯凌亂。按照哈斯圖的畫法，去掉一部分，結(jié)果如左圖。例以下是偏序集<P(X)，>的哈斯圖。利用哈斯圖，可以很方便的解決我們在學(xué)習(xí)偏序集中的一些問題：例偏序集<S,≤>，其中S={2,4,5,10,12,20,25}，≤是整除關(guān)系，求此偏序集的極大元和極小元。解：作出哈斯圖，從圖中看出，12,20和25是極大元，2和5是極小元。例確定下圖中每個哈斯圖表示的偏序集是否有最大元和最小元。解：a)的最小元是a，無最大元。b)既無最大元也無最小元。c)無最小元，最大元是d。d)的最小元是a，最大元是d。2.最小上界與最大下界定義

設(shè)集合X上有一個偏序關(guān)系“≤”且設(shè)Y是X的一個子集。（1）如果存在一個元素x∈X，對每個y'∈Y都有y'≤x，則稱x是Y的上界(upperbound)；如果均有x≤y'，則稱x是Y的下界(lowerbound)。（2）如果x∈X是Y的上界且對每一個Y的上界x'均有x≤x'，則稱x是Y的最小上界（或上確界LUB，leastupperbound）；如果x∈X是Y的下界且對每一個Y的下界x'均有x'≤x，則稱x是Y的最大下界（或下確界GLB，greatestlowerbound）例設(shè)有偏序集<A，≤>，其中A={2，4，6，8，12}，偏序關(guān)系是整除關(guān)系，試求{2，4}的上界和最小上界，{8，12}的下界和最大下界。解：{2，4}的上界是4，8，12，最小上界是4。{8，12}的下界是2，4，最大下界是4。例：找出下圖所示哈斯圖的偏序集的子集{a,b,c},{j,h}和{a,c,df}的下界和上界。解：{a,b,c}的上界是e,f,j,h，它唯一的下界是a。{j,h}沒有上界，它的下界是a,b,c,d,e,f。{a,c,df}的上界是f,h,j，它的下界是a。例在上圖所示偏序集中，如果{b,d,g}的最大下界和最小上界存在，求出這個最大下界和最小上界。解：{b,d,g}的上界是g,h，故它的最小上界是g。{b,d,g}的下界是a,b，故它的最大下界是b。15.1格(lattice)1．格作為偏序集定義15.1.1設(shè)<L,≤>是一個偏序集，若對任意a,bL，存在最大下界(GLB)和最小上界(LUB)，則稱<L,≤>為格。用ab表示LUB{a,b}，ab表示GLB{a,b}，并稱和分別為L上的并（或和）和交（或積）運(yùn)算。這樣我們由偏序關(guān)系定義了兩種二元運(yùn)算。有時也用∨和∧分別表示和

。因此，格有時也表示成<L,,>或<L,∨,∧>。顯然，對于ab，有：①ab≤a和ab≤b，則表明ab是a和b的下界。②若c≤a和c≤b，則c≤ab，這表明ab是a和b的最大下界。對于ab，有：①a≤ab和b≤ab，則表明ab是a和b的上界。②若a≤c，且b≤c，則ab≤c，這表明ab是a和b的最小上界。例

設(shè)n為正整數(shù)，Sn為n的正因子的集合，≤為整除關(guān)系，則<Sn，≤>構(gòu)成格。因為x，y∈Sn，xy就是x，y的最小公倍數(shù)，xy是x，y的最大公約數(shù)。例

冪集P(A)上的包含關(guān)系定義了一個偏序關(guān)系，P(A)中任意兩個元素x，y，有xy=x∪yxy=x∩y因此，<P(A),>是一個格。注意：并非每個偏序集都是格。如，設(shè)A＝{2,3,6,8},“整除”關(guān)系R={?2,2?,?2,6?,?2,8?,?3,3?,?3,6?,?6,6?,?8,8?}是A上的一個偏序關(guān)系，則<A，R>是一個偏序集，但不是格。因為23不存在，68也不存在。例確定下圖中每個哈斯圖表示的偏序集是不是格。解：在a)和c)中的哈斯圖表示的偏序集是格。因為每個偏序集中每對元素都有最小上界和最大下界。b)所示的哈斯圖的偏序集不是格，例如元素b和c沒有最小上界。只要注意到d,e,f中每一個都是上界，但這3個元素的任何一個關(guān)于這個偏序集中的序都不小于其它兩個。練習(xí)：確定下圖中每個哈斯圖表示的偏序集是不是格。除c外，其余都是格。因為c中最下兩個元素既沒有上確界也沒有下確界。格的對偶性原理是成立的：令<L,≤>是偏序集，且<L,≥>是其對偶的偏序集。若<L,≤>是格，則<L,≥>也是格，反之亦然。這是因為，對于L中任意a和b，<L,≤>中LUB{a,b}等同于<L,≥>中GLB{a,b}，<L,≤>中GLB{a,b}等同于<L,≥>中的LUB{a,b}。若L是有限集，這些性質(zhì)易從偏序集及其對偶的哈斯圖得到驗證。從上討論中，可知兩格互為對偶?；閷ε嫉膬蓚€<L,≤>和<L,≥>有著密切關(guān)系，即格<L,≤>中交運(yùn)算正是格<L,≥>中的并運(yùn)算，而格<L,≤>中的并運(yùn)算正是格<L,≥>中的交運(yùn)算。因此，給出關(guān)于格一般性質(zhì)的任何有效命題，把關(guān)系≤換成≥（或者≥換成≤），交換成并，并換成交，可得到另一個有效命題，這就是關(guān)于格的對偶性原理。定義設(shè)<L,∨,∧>是一個格，S是L的非空子集，如果S關(guān)于運(yùn)算∨和∧是封閉的，則稱<S,∨,∧>是<L,∨,∧>的子格。顯然，子格本身是一個格。

例如：設(shè)<S,≤>是一個格，其中S＝{a,b,c,d,e,f,g,h}，如圖所示，取S1={a,b,d,f}S2={c,e,g,h}S3={a,b,c,d,e,g,h}問，其中哪些構(gòu)成格？哪些是<S,≤>的子格？<S1,≤>,<S2,≤>是<S,≤>的子格，而<S3,≤>雖然是格，但不是<S,≤>的子格，因為b∧d=fS3。hfcbedga2．格的基本性質(zhì)定理1設(shè)<L,≤>是格，對任意a,bL，有 ①ab=ba≤b ②ab=aa≤b ③ab=aab=b亦即a≤bab=bab=a定理2設(shè)<L,≤>是格，對任意a,bL，有①aa=a,bb=b （等冪律）②ab=ba,ab=ba （交換律）③a(bc)=(ab)c, a(bc)=(ab)c（結(jié)合律）④a(ab)=a, a(ab)=a （吸收律）定理3設(shè)<L,≤>是格，對任意a,b,cL，有①若a≤b和c≤d，則ac≤bd，ac≤bd。②若a≤b，則ac≤bc，ac≤bc。（保序性）定理4設(shè)<L,≤>是格，對任意的a,b,cL，有①a(bc)≤(ab)(ac)②(ab)(ac)≤a(bc)通常稱上二式為格中分配不等式。3．特殊的格定義設(shè)<L,≤>是格，若L中有最大元和最小元，則稱<L,≤>為有界格。由于最大（?。┰嬖诒匚ㄒ?，故一般把格中最大元記為1，最小元記為0。由定義可知，對任意aL，有①0≤a≤1②a0=0,a0=a③a1=a,a1=1由此可知，0是<L,≤>關(guān)于的零元，關(guān)于的幺元；1是<L,≤>關(guān)于的幺元，關(guān)于的零元例：試判斷下面哪些是有界格？×√√定義：若L是有限集合，稱<L,≤>為有限格。定理5設(shè)<L,≤>是有限格，其中L={a1,a2,···,an}，則<L,≤>是有界格。定義設(shè)<L,≤>是格，對任意的a,b,cL，有①a(bc)=(ab)(ac)②(ab)(ac)=a(bc)則稱<L,≤>為分配格，稱①和②為格中分配律。分配格的性質(zhì)性質(zhì)1：如果①交對并可分配，則②并對交也一定是可分配的，反之亦然。只證前半部分，即由①推②：(ab)(ac)＝((ab)a)((ab)c)（由①）＝(aa)(ab)(ca)(cb)（由①,交換律）＝a(ab)(ac)(bc)＝a(bc)（吸收律）注：此性質(zhì)說明，分配格的定義可以簡化成只需滿足①或②其中之一即可。性質(zhì)2：每個鏈<L,≤>都是分配格。（|L|≥3）鏈鏈例：試判斷下面兩個哈斯圖是否表示的是分配格？顯然(1)是格，但因為b(cd)=ba=b，而(bc)(bd)=ee=e，故它不是分配格；顯然(2)也是格，但因為c(bd)=ca=c，而(cb)(cd)=ed=d，故它也不是分配格，注：上面兩個具有五個元素的格是很重要的，因為有這樣的定理：一個格是分配格的充要條件是，在該格中沒有任何子格與這兩個五元素格中的任何一個同構(gòu)。bcdae(1)bcdea(2)我們知道，驗證一個格是不是分配格是很復(fù)雜的，可以利用上面這個定理判斷一個格不是分配格。如(3)中，容易驗證<{a,b,c,e,g},≤>是<{a,b,c,d,e,f,g},≤>的子格，且與(1)同構(gòu)，或者容易驗證<{a,b,c,f,g},≤>是<{a,b,c,d,e,f,g},≤>的子格，且與(2)同構(gòu)，故不是分配格。從而判斷它不是分配格。bcdae(1)bcdea(2)abcfgde(3)例：證明<Sn,≤>是一個分配格。證：設(shè)∧和∨分別為Sn上的交（或積）和并（或和）運(yùn)算，對于任意a，b，c∈Sn，有a∨(b∧c)=lcm(a,gcd(b,c))=gcd(lcm(a,b),lcm(a,c))=(a∨b∧(a∨c)a∧(b∨c)=gcd(a,lcm(b,c))=lcm(gcd(a,b),gcd(a,c))=(a∧b)∨(a∧c)（事實上，上面是利用“最大公約數(shù)對最小公倍數(shù)是分配的，最小公倍數(shù)對最大公約數(shù)也是分配的”這個性質(zhì)）故<Sn，|>是一個分配格。在介紹有補(bǔ)格之前，先介紹補(bǔ)元的定義。定義設(shè)<L,≤>是有界格，對于aL，存在bL，使得ab=0，ab=1稱b為a的補(bǔ)元，記為a'。由定義可知，若b是a的補(bǔ)元，則a也是b的補(bǔ)元，即a與b互為補(bǔ)元。顯然，0'=1和1'=0。一般說來，一個元素可以有其補(bǔ)元，未必唯一，也可能無補(bǔ)元。例：試判斷下圖中每個元素有無補(bǔ)元，若有，寫出補(bǔ)元。1,0顯然互為補(bǔ)元；a的補(bǔ)元是e，c的補(bǔ)元是d；b沒有補(bǔ)元；d的補(bǔ)元是c和e，e的補(bǔ)元是a和d。1acedb0關(guān)于補(bǔ)元，有下面的性質(zhì)：定理6設(shè)<L,≤>是有界分配格，若aL，且補(bǔ)元存在，則其補(bǔ)元是唯一的。下面介紹有補(bǔ)格的定義。定義設(shè)<L,≤>是格，若L中每個元素至少有一補(bǔ)元，則稱<L,≤>為有補(bǔ)格。由于補(bǔ)元的定義是在有界格中給出的，可知，有補(bǔ)格一定是有界格。例：試判斷下圖中哪些是有補(bǔ)格？√√√×

定義若一格既是有補(bǔ)又是分配的，則稱該格為有補(bǔ)分配格，或布爾格，或布爾代數(shù)。關(guān)于有補(bǔ)分配格，有下面幾個性質(zhì)：定理7設(shè)<L,≤>是有補(bǔ)分配格，若任意元素aL，則a的補(bǔ)元a'是唯一的。該定理6的直接推論，因為有補(bǔ)分配格當(dāng)然是有界分配格。由于有補(bǔ)分配格中，每個元素a都有唯一的補(bǔ)元a'，因此可在L上定義一個一元運(yùn)算—補(bǔ)運(yùn)算“'”。這樣，有補(bǔ)分配格可看作具有兩個二元運(yùn)算和一個一元運(yùn)算的代數(shù)結(jié)構(gòu)，習(xí)慣上稱它為布爾代數(shù)，記為<B,,,',0,1>，其中B=L。定理8設(shè)<L,≤>是有補(bǔ)分配格，對任意a,bL，則①(a')'=a②(ab)'=a'b'③(ab)'=a'b'后兩式稱為格中德·摩根律。定理9設(shè)<L,≤>是有補(bǔ)分配格，對任意a,bL，有 a≤bab'=0 a'b=1格同態(tài)，格直積等概念可以接下來定義和研究，但這里不打算這樣做，因為如此進(jìn)行會相對較繁，而是將格作為一個代數(shù)結(jié)構(gòu)而引入它們。4．代數(shù)結(jié)構(gòu)所誘導(dǎo)的偏序集確立的格前面我們已知，有補(bǔ)分配格是一個代數(shù)結(jié)構(gòu)，叫做布爾代數(shù)；反之，由代數(shù)結(jié)構(gòu)也可以導(dǎo)出格。定義設(shè)<L,,>是一代數(shù)結(jié)構(gòu)，其中和是L上滿足交換律、結(jié)合律和吸收律的二元運(yùn)算，且對任意a,bL，定義偏序關(guān)系≤如下：a≤bab=a則<L,≤>是格，稱<L,≤>為代數(shù)結(jié)構(gòu)<L,,>所誘導(dǎo)的偏序集確立的格。15.2布爾代數(shù)前已指出，布爾代數(shù)是有補(bǔ)分配格，常記為<B,,,‘,0,1>，因此，它具有格、有界格、分配格、有補(bǔ)格的所有性質(zhì)。我們把這些性質(zhì)羅列如下：對任意a,b,cB，有①<B,,>是格，且≤為B上由或所定義的偏序關(guān)系，滿足(L-1)ab=LUB{a,b}，ab=GLB{a,b}(L-2)a≤bab=bab=a(L-3)aa=a，aa=a（等冪律）(L-4)ab=ba，ab=ba（交換律）(L-5)(ab)c=a(bc)，(ab)c=a(bc)（結(jié)合律）(L-6)a(ab)=a，a(ab)=a（吸收律）②<B,,>是分配格，滿足(D-1)a(bc)=(ab)(ac)，a(bc)=(ab)(ac)（分配律）(D-2)(ab=ac)∧(ab=ac)b=c(可約律)(D-3)(ab)(bc)(ca)=(ab)(bc)(ca)③<B,,,',0,1>是有界格，滿足(B-1)0≤a≤1(B-2)a0=a，aa=a（幺律）(B-3)a1=1，a0=0（零律）④<B,,,',0,1>是有補(bǔ)格，滿足(C-1)aa'=1，aa'=0（互補(bǔ)律）(C-2)1'=0，0'=1⑤<B,,,',0,1>是有補(bǔ)分配格，滿足(CD-1)(ab)'=a'a'，(ab)'=a'b'（德·摩根律）(CD-2)a≤ba'b=1ab'=0b'≤a'注意，上述公式并非都是獨立的，可從中選出一些公式作為基本公式，用它們推出其余的公式，而且可以用基本公式定義布爾代數(shù)。定義15.1.1設(shè)<B,,,'>是一代數(shù)結(jié)構(gòu)，其中和是B上的二元運(yùn)算，'是B上的一元運(yùn)算。0,1B。若對任意a,bB，有①ab=ba，ab=ba（交換律）②a(bc)=(ab)(ac)，a(bc)=(ab)(ac)（分配律）③a0=a，a1=a（幺律）④aa'=1，aa