第十五格與布爾代數

第十五格與布爾代數演示文稿當前1頁，總共50頁。（優(yōu)選）第十五格與布爾代數當前2頁，總共50頁。1.哈斯圖為了更清楚地描述偏序集合中元素間的層次關系,也為了更快、更有效地畫出偏序關系的簡化圖,下面介紹“蓋住”的概念。定義

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

設集合X上有一個偏序關系“≤”且設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）當前9頁，總共50頁。例設有偏序集<A，≤>，其中A={2，4，6，8，12}，偏序關系是整除關系，試求{2，4}的上界和最小上界，{8，12}的下界和最大下界。解：{2，4}的上界是4，8，12，最小上界是4。{8，12}的下界是2，4，最大下界是4。當前10頁，總共50頁。例：找出下圖所示哈斯圖的偏序集的子集{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。當前11頁，總共50頁。例在上圖所示偏序集中，如果{b,d,g}的最大下界和最小上界存在，求出這個最大下界和最小上界。解：{b,d,g}的上界是g,h，故它的最小上界是g。{b,d,g}的下界是a,b，故它的最大下界是b。當前12頁，總共50頁。15.1格(lattice)1．格作為偏序集定義15.1.1

設<L,≤>是一個偏序集，若對任意a,bL，存在最大下界(GLB)和最小上界(LUB)，則稱<L,≤>為格。用ab表示LUB{a,b}，ab表示GLB{a,b}，并稱和分別為L上的并（或和）和交（或積）運算。這樣我們由偏序關系定義了兩種二元運算。有時也用∨和∧分別表示和

。因此，格有時也表示成<L,,>或<L,∨,∧>。當前13頁，總共50頁。顯然，對于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的最小上界。當前14頁，總共50頁。例

設n為正整數，Sn為n的正因子的集合，≤為整除關系，則<Sn，≤>構成格。因為x，y∈Sn，xy就是x，y的最小公倍數，xy是x，y的最大公約數。當前15頁，總共50頁。例

冪集P(A)上的包含關系定義了一個偏序關系，P(A)中任意兩個元素x，y，有xy=x∪yxy=x∩y因此，<P(A),>是一個格。當前16頁，總共50頁。注意：并非每個偏序集都是格。如，設A＝{2,3,6,8},“整除”關系R={?2,2?,?2,6?,?2,8?,?3,3?,?3,6?,?6,6?,?8,8?}是A上的一個偏序關系，則<A，R>是一個偏序集，但不是格。因為23不存在，68也不存在。當前17頁，總共50頁。例確定下圖中每個哈斯圖表示的偏序集是不是格。解：在a)和c)中的哈斯圖表示的偏序集是格。因為每個偏序集中每對元素都有最小上界和最大下界。

b)所示的哈斯圖的偏序集不是格，例如元素b和c沒有最小上界。只要注意到d,e,f中每一個都是上界，但這3個元素的任何一個關于這個偏序集中的序都不小于其它兩個。當前18頁，總共50頁。練習：確定下圖中每個哈斯圖表示的偏序集是不是格。除c外，其余都是格。因為c中最下兩個元素既沒有上確界也沒有下確界。當前19頁，總共50頁。格的對偶性原理是成立的：令<L,≤>是偏序集，且<L,≥>是其對偶的偏序集。若<L,≤>是格，則<L,≥>也是格，反之亦然。這是因為，對于L中任意a和b，<L,≤>中LUB{a,b}等同于<L,≥>中GLB{a,b}，<L,≤>中GLB{a,b}等同于<L,≥>中的LUB{a,b}。若L是有限集，這些性質易從偏序集及其對偶的哈斯圖得到驗證。當前20頁，總共50頁。從上討論中，可知兩格互為對偶?；閷ε嫉膬蓚€<L,≤>和<L,≥>有著密切關系，即格<L,≤>中交運算正是格<L,≥>中的并運算，而格<L,≤>中的并運算正是格<L,≥>中的交運算。因此，給出關于格一般性質的任何有效命題，把關系≤換成≥（或者≥換成≤），交換成并，并換成交，可得到另一個有效命題，這就是關于格的對偶性原理。當前21頁，總共50頁。定義設<L,∨,∧>是一個格，S是L的非空子集，如果S關于運算∨和∧是封閉的，則稱<S,∨,∧>是<L,∨,∧>的子格。顯然，子格本身是一個格。

當前22頁，總共50頁。例如：設<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}問，其中哪些構成格？哪些是<S,≤>的子格？<S1,≤>,<S2,≤>是<S,≤>的子格，而<S3,≤>雖然是格，但不是<S,≤>的子格，因為b∧d=fS3。hfcbedga當前23頁，總共50頁。2．格的基本性質定理1

設<L,≤>是格，對任意a,bL，有 ①ab=ba≤b ②ab=aa≤b ③ab=aab=b亦即a≤bab=bab=a當前24頁，總共50頁。定理2

設<L,≤>是格，對任意a,bL，有①aa=a,bb=b （等冪律）②ab=ba,ab=ba （交換律）③a(bc)=(ab)c, a(bc)=(ab)c（結合律）④a(ab)=a, a(ab)=a （吸收律）當前25頁，總共50頁。定理3

設<L,≤>是格，對任意a,b,cL，有①若a≤b和c≤d，則ac≤bd，ac≤bd。②若a≤b，則ac≤bc，ac≤bc。（保序性）當前26頁，總共50頁。定理4

設<L,≤>是格，對任意的a,b,cL，有①a(bc)≤(ab)(ac)②(ab)(ac)≤a(bc)通常稱上二式為格中分配不等式。當前27頁，總共50頁。3．特殊的格定義設<L,≤>是格，若L中有最大元和最小元，則稱<L,≤>為有界格。由于最大（?。┰嬖诒匚ㄒ?，故一般把格中最大元記為1，最小元記為0。由定義可知，對任意aL，有①0≤a≤1②a0=0,a0=a③a1=a,a1=1由此可知，0是<L,≤>關于的零元，關于的幺元；1是<L,≤>關于的幺元，關于的零元當前28頁，總共50頁。例：試判斷下面哪些是有界格？

×√√當前29頁，總共50頁。定義：若L是有限集合，稱<L,≤>為有限格。定理5

設<L,≤>是有限格，其中L={a1,a2,···,an}，則<L,≤>是有界格。當前30頁，總共50頁。定義設<L,≤>是格，對任意的a,b,cL，有①a(bc)=(ab)(ac)②(ab)(ac)=a(bc)則稱<L,≤>為分配格，稱①和②為格中分配律。當前31頁，總共50頁。分配格的性質性質1：如果①交對并可分配，則②并對交也一定是可分配的，反之亦然。只證前半部分，即由①推②：(ab)(ac)＝((ab)a)((ab)c)（由①）＝(aa)(ab)(ca)(cb)（由①,交換律）＝a(ab)(ac)(bc)＝a(bc)（吸收律）注：此性質說明，分配格的定義可以簡化成只需滿足①或②其中之一即可。當前32頁，總共50頁。性質2：每個鏈<L,≤>都是分配格。（|L|≥3）鏈鏈當前33頁，總共50頁。例：試判斷下面兩個哈斯圖是否表示的是分配格？顯然(1)是格，但因為b(cd)=ba=b，而(bc)(bd)=ee=e，故它不是分配格；顯然(2)也是格，但因為c(bd)=ca=c，而(cb)(cd)=ed=d，故它也不是分配格，注：上面兩個具有五個元素的格是很重要的，因為有這樣的定理：一個格是分配格的充要條件是，在該格中沒有任何子格與這兩個五元素格中的任何一個同構。bcdae(1)bcdea(2)當前34頁，總共50頁。我們知道，驗證一個格是不是分配格是很復雜的，可以利用上面這個定理判斷一個格不是分配格。如(3)中，容易驗證<{a,b,c,e,g},≤>是<{a,b,c,d,e,f,g},≤>的子格，且與(1)同構，或者容易驗證<{a,b,c,f,g},≤>是<{a,b,c,d,e,f,g},≤>的子格，且與(2)同構，故不是分配格。從而判斷它不是分配格。bcdae(1)bcdea(2)abcfgde(3)當前35頁，總共50頁。例：證明<Sn,≤>是一個分配格。證：設∧和∨分別為Sn上的交（或積）和并（或和）運算，對于任意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)（事實上，上面是利用“最大公約數對最小公倍數是分配的，最小公倍數對最大公約數也是分配的”這個性質）故<Sn，|>是一個分配格。當前36頁，總共50頁。在介紹有補格之前，先介紹補元的定義。定義設<L,≤>是有界格，對于aL，存在bL，使得ab=0，ab=1稱b為a的補元，記為a'。由定義可知，若b是a的補元，則a也是b的補元，即a與b互為補元。顯然，0'=1和1'=0。一般說來，一個元素可以有其補元，未必唯一，也可能無補元。當前37頁，總共50頁。例：試判斷下圖中每個元素有無補元，若有，寫出補元。1,0顯然互為補元；a的補元是e，c的補元是d；b沒有補元；d的補元是c和e，e的補元是a和d。1acedb0當前38頁，總共50頁。關于補元，有下面的性質：定理6

設<L,≤>是有界分配格，若aL，且補元存在，則其補元是唯一的。下面介紹有補格的定義。當前39頁，總共50頁。定義設<L,≤>是格，若L中每個元素至少有一補元，則稱<L,≤>為有補格。由于補元的定義是在有界格中給出的，可知，有補格一定是有界格。當前40頁，總共50頁。例：試判斷下圖中哪些是有補格？√√√×

當前41頁，總共50頁。定義若一格既是有補又是分配的，則稱該格為有補分配格，或布爾格，或布爾代數。關于有補分配格，有下面幾個性質：當前42頁，總共50頁。定理7

設<L,≤>是有補分配格，若任意元素aL，則a的補元a'是唯一的。該定理6的直接推論，因為有補分配格當然是有界分配格。由于有補分配格中，每個元素a都有唯一的補元a'，因此可在L上定義一個一元運算—補運算“'”。這樣，有補分配格可看作具有兩個二元運算和一個一元運算的代數結構，習慣上稱它為布爾代數，記為<B,,,',0,1>，其中B=L。當前43頁，總共50頁。定理8

設<L,≤>是有補分配格，對任意a,bL，則①(a')'=a②(ab)'=a'b'③(ab)'=a'b'后兩式稱為格中德·摩根律。當前44頁，總共50頁。定理9

設<L,≤>是有補分配格，對任意a,bL，有

a≤bab'=0 a'b=1格同態(tài)，格直積等概念可以接下來定義和研究，但這里不打算這樣做，因為如此進行會相對較繁，而是將格作為一個代數結構而引入它們。當前45頁，總共50頁。4．代數結構所誘導的偏序集確立的格前面我們已知，有補分配格是一個代數結構，叫做布爾代數；反之，由代數結構也可以導出格。定義設<L,,>是一代數結構，其中和是L上滿足交換律、結合律和吸收律的二元運算，且對任意a,bL，定義偏序關系≤如下：a≤bab=a則<L,≤>是格，稱<L,≤>為代數結構<L,,>所誘導的偏序集確立的格。當前46頁，總共50頁。15.2布爾代數前已指出，布爾代數是有補分配格，常記為<B,,,‘,0,1>，因此，它具有格、有界格、分配格、有補格的所有性質。我們把這些性質羅列如下：對任意a,b,cB，有當前47頁，總共50頁。①<B,,>是