格與布爾代數(shù)

1、第7章 格與布爾代數(shù)第7章 格與布爾代數(shù) n7.1 格格 n7.2 格是代數(shù)系統(tǒng)格是代數(shù)系統(tǒng)n7.3 特殊的格特殊的格n7.4 布爾代數(shù)布爾代數(shù)第7章 格與布爾代數(shù)7.1 格 n 在第三章曾討論過偏序集合,定義了有關(guān)的術(shù)語。并曾證明過:(1)一個(gè)偏序集合的子集,如果存在最小上界(lub),則它是唯一的,如果存在最大下界(glb),則它也是唯一的;(2)如果偏序集合擁有最小元素,則它是唯一的,如果偏序集合擁有最大元素,則它也是唯一的。我們就以這些知識(shí)為基礎(chǔ)介紹格的概念和有關(guān)性質(zhì)。第7章 格與布爾代數(shù)n 7.11 格的定義n 定義7.11設(shè)L,是一個(gè)偏序集合,如果L中每一對(duì)元素a,b,都有最大下界

2、和最小上界,則稱此L,為格。 n 通常用ab表示a,b的最大下界,用ab表示a,b的最小上界。即n a * b=glba,b n ab=luba,b第7章 格與布爾代數(shù)n 例1n (a)設(shè)D是正整數(shù)集合I+中的整除關(guān)系,則I+,D是格,因?yàn)閷?duì)任意a,bI+,n a*b=glba,b=GCDa,b (a,b的最大公因數(shù)) n a b=luba,b=LCMa,b (a,b的最小公倍數(shù))n (b)設(shè)n是一正整數(shù),Sn是n的所有因子的集合。例如S6=1,2,3,6,S8=1,2,4,8,D是整除關(guān)系,則Sn,D是格,例如S8,D,S6,D,S30,D的哈斯圖如圖7.11(a),(b),(c)所示。第7

3、章 格與布爾代數(shù)n (c) 設(shè)S是任意集合,是它的冪集,偏序集合(S),是格,因?yàn)閷?duì)S的任意子集A,B,AB就是A,B的最小上界,AB就是A,B的最大下界。n 當(dāng)集合S僅含有二個(gè)或三個(gè)元素時(shí),相應(yīng)的格的哈斯圖亦如圖7.11(b)和(c)所示。n (d)設(shè)S是非空集合,(S)是S的所有劃分,(S)中的偏序關(guān)系可定義為細(xì)分,ij當(dāng)且僅當(dāng)i中的每一塊都在j的某一塊中。于是劃分積與劃分和+分別是保交和保聯(lián)。所以(S),是格。 第7章 格與布爾代數(shù)n例如S=a,b,c,則n(S)=1,2,3,4,5 n1=a,b,c,2=a,b,c, n3=a,c,b, 4=a,b,cn5=a,b,cn(S),的哈斯圖

4、如圖7.11(d)所示。n(e)圖7.11(e)所示的哈斯圖也是一個(gè)格。第7章 格與布爾代數(shù)圖 7.11 第7章 格與布爾代數(shù)圖 7.12 第7章 格與布爾代數(shù)n 7.1.2 格的對(duì)偶性原理和基本性質(zhì)n 給定一個(gè)偏序集合S,的逆關(guān)系也是S中的偏序關(guān)系,S,也是偏序集合,我們稱偏序集合S,和S,互為對(duì)偶。從圖形上看,后者的哈斯圖就是前者哈斯圖的上下顛倒。如果A S,則關(guān)系的lub(A)和glb (A)就分別等同于關(guān)系的glb(A)和lub(A)。因此,如果L,是一個(gè)格,則L,也是一個(gè)格,我們說這兩個(gè)格互為對(duì)偶?；閷?duì)偶的兩個(gè)格L,和L,有著密切關(guān)系:格L,中的保交正是格L,中的保聯(lián), 第7章 格

5、與布爾代數(shù)n 而格L,中的保聯(lián)正是格L,中的保交。因此,給出關(guān)于格一般性質(zhì)的任何有效命題,把關(guān)系換成,(或把換成),把保交換成保聯(lián),保聯(lián)換成保交,我們能夠得到另一個(gè)有效命題,這就是關(guān)于格的對(duì)偶性原理。 n 格的基本性質(zhì)如表7.11所示。如果一個(gè)公式的對(duì)偶公式是其自身,則對(duì)偶式不重復(fù)列出。第7章 格與布爾代數(shù)表7.11 格的基本性質(zhì)第7章 格與布爾代數(shù)表7.11 格的基本性質(zhì)第7章 格與布爾代數(shù)n 現(xiàn)證明表中各公式。n 證n 公式(1)(3)是偏序集合定義所要求的,對(duì)一切偏序集合均成立,格是偏序集合,所以對(duì)一切格也成立。公式(4)(5)是根據(jù)保交和保聯(lián)的定義所得的,所以對(duì)一切格成立。 n (6)

6、 交換律的證明。n 由 保 聯(lián) 的 定 義 得 a b=luba,b=lubb,a=ba。n 由對(duì)偶原理得a*b=b*a。(下邊都僅證兩對(duì)偶恒等式中的一個(gè)。)第7章 格與布爾代數(shù)n (7) 結(jié)合律的證明。n 設(shè)R=a (b c)和R=(a b) c,由公式(4)(加撇表示右側(cè)的公式,下同)得Ra,Rb c,根據(jù)公式(4)和(3)得Rb和Rc。這樣,根據(jù)公式(5)得Ra b;由Ra b和Rc得R(a b) c=R。類似地可證Ra (b c)=R。因此,根據(jù)公式(2)n 得(a b) c=a (b c)。n 結(jié)合律說明,無括號(hào)表達(dá)式a1 a2 ann 和a1*a2*an都是單義的。因此,可以論述任

7、何數(shù)目的格的元素的保交和保聯(lián)。 第7章 格與布爾代數(shù)n (8)等冪律的證明。n 由公式(1)有aa,根據(jù)公式(5)得aa a。又由公式(4)a aa,因此,根據(jù)公式(2)得a a=a。n (9) 吸收律的證明。n 由公式(1)有aa,由公式(4)有aa*b,因此,根據(jù)公式(5)得aa (a*b),但由公式(4)有a (a*b)a,這樣,根據(jù)公式(2)得a (a*b)=a。第7章 格與布爾代數(shù)n (10)aba*b=a a b=b的證明。n 先證aba*b=a,由公式1知aa,由假設(shè)ab,所以,由公式5得aa*b,但a*ba。因此,a*b=a。即ab n a*b=a?，F(xiàn)設(shè)a*b=a,由公式(4)

8、知a*bb,所以ab,既a*b=a ab。n 再證a*b=a a b=b由a*b=a得b (a *b)=a b,n 即a b=b。反之,若a b=b,則a*(a b)=a*b,即a*b=a。n 公式(10)建立了格中偏序關(guān)系和保交,保聯(lián)間的一種聯(lián)系。第7章 格與布爾代數(shù)n (11)adbc a*bd*c和adbc a n bd c的證明。n 因?yàn)閐d c,cd c,由傳遞性得ad c,bd n c , 由 公 式 5 得 a b d c , 因 為a*ba,a*bb,由傳遞性得a*bd,a*bc,由公式(5)得a*bd*c。n (12) 保序性的證明。n 公式(11)中d取為a即得。n (13

9、)分配不等式的證明。n 由aa b和aa c得a(a b)*(a c),n 由ba b和ca c得b*c(a b)*(a c)。第7章 格與布爾代數(shù)n 所以,a (b*c)(a b)*(a c)n (14)模不等式的證明。n 若ac,則a c=c,代入公式(13)得n a (b*c)(a b)*cn 若a(b*c)(a b)*c,由于aa (b*c),(a b)*cc,根據(jù)傳遞性得ac。第7章 格與布爾代數(shù)7.2 格是代數(shù)系統(tǒng) n 7.2.1 格n 定義7.21設(shè)L, *, 是代數(shù)系統(tǒng),*和 是載體L上的二元運(yùn)算。如果二元運(yùn) *算 和都是可交換和可結(jié)合的,并且滿足吸收律和等冪律,則代數(shù)系統(tǒng)n

10、L, *, 是格。第7章 格與布爾代數(shù)n 定 義 中 等 冪 律 可 以 刪 除 , 因 為a*a=a*(a (a a)=a,由吸收律可推出等冪律。類似地可證a a=a。n 這一定義和上節(jié)的定義實(shí)際上是等價(jià)的,下述定理說明這一點(diǎn)。 第7章 格與布爾代數(shù)n 定理7.21 如果L, *, 是一個(gè)格,那么,L中存在一偏序關(guān)系,在此偏序關(guān)系作用下,對(duì)所有a,bL有n a b=luba,b (1) n a*b=glba,b (2)n 證首先我們?cè)贚上定義一個(gè)關(guān)系。對(duì)任意a,bLn ab a*b=an 現(xiàn)在我們證明是偏序關(guān)系。因?yàn)?第7章 格與布爾代數(shù)n (1)對(duì)任一元素aL,由等冪律a*a=a,有aa,

11、即是自反的。n (2)對(duì)某一a,bL,如果ab和ba,那么a*b=a和b*a=b。但a*b=b*a,所以a=b。即是反對(duì)稱的。n (3)對(duì)某一a,b,cL。如果ab和bc,那么a*b=a和b*c=b,于是n a*c=(a*b)*c=a*(b*c)=a*b=an 所以,ac,即是傳遞的。 第7章 格與布爾代數(shù)n 7.2.2 子格,格同態(tài)和格的積代數(shù)n 定義7.22 L, *, 是一個(gè)格,S L,如果S對(duì)運(yùn)算和封閉,那么稱S, *, 是L, *, 的子格。n 子格本身是一個(gè)格,因?yàn)榻粨Q律,結(jié)合律,吸收律都是繼承的。顯然,不是L的任意子集都可構(gòu)成子格。例如圖7.21所示的格中,a,b,d,是子格,b

12、,c,不是子格,因?yàn)閎,c對(duì)運(yùn)算不封閉。 第7章 格與布爾代數(shù)圖 7.21 第7章 格與布爾代數(shù)n 定義7.23 L, *, 和S,是兩個(gè)格。n 定義一個(gè)映射f:LS,如果對(duì)于任何a,bL,有n f (a*b)=f (a)f (b)n 和n f (a*b)=f (a)f (b)n 則稱f是從L, *, 到S,的格同態(tài)。第7章 格與布爾代數(shù)圖 7.22第7章 格與布爾代數(shù)n 定理7.22 L, *, 和S,是兩個(gè)格,n 在集合L和S中,對(duì)應(yīng)于保交和保聯(lián)運(yùn)算的偏序關(guān)系 分別是和,如果f:LSn 是格同態(tài),則對(duì)任何a,bL,且ab,必有f (a)f (b)。n 證根據(jù)ab a*b=a有n f (a*

13、b)=f (a)f (b)=f (a)n 所以,f (a)f (b)。證畢第7章 格與布爾代數(shù)n 在定義7.23中,若f是雙射函數(shù),則稱f是格同構(gòu)。或說L, *, 和S,兩個(gè)格同構(gòu)。由于同構(gòu)是相互的,又是保序的,所以對(duì)任何a,bL有,n abf (a)f (b)n 和n f (a)f (b) abn 這說明同構(gòu)的兩個(gè)格的哈斯圖是一樣的,只是各結(jié)點(diǎn)的標(biāo)記不同而已。第7章 格與布爾代數(shù) 圖 7.23 第7章 格與布爾代數(shù)n 例1n (a) 設(shè)L1=a,b,c,L2=(a,b,c),如圖7.23n 所示。f:a,b,c(a,b,c),f (x)=y|yx。n 因?yàn)閒 (x1*x2)=f (minx1

14、,x2)=y|yminx1,x2n =y|yx1y|yx2 n =f(x1)f(x2)n f (x1 x2)=f (maxx1,x2)n =y|ymaxx1,x2n =y|yx1y|yx2=f (x1)f (x2)n 所以,f是L1到L2的格同態(tài)。第7章 格與布爾代數(shù)n (b)具有一,二,三個(gè)元素的格,分別同構(gòu)于一、二,三個(gè)元素的鏈。四個(gè)元素的格必同構(gòu)于圖7.24(a)和(b)之一,五個(gè)元素的格必同構(gòu)于圖7.25(a),(b),(c),(d),(e)之一。 圖 7.24 第7章 格與布爾代數(shù)圖 7.25第7章 格與布爾代數(shù)n 定義7.24設(shè)L,*, 和S,是兩個(gè)格。定義一個(gè)代數(shù)系統(tǒng)LS,+如下

15、:對(duì)任意a1,b1,n a2,b2LS,有n a1,b1。a2,b2=a1*a2 , b1b2 n a1,b1+a2,b2=a1 a2,b1b2n 我們稱LS,*,+是格L,*, 和S,的直接乘積或積代數(shù)。n 第7章 格與布爾代數(shù)n 例2n (a) 圖7.26給出了格1,2,4,D和1,3,D的積代數(shù)。這個(gè)積代數(shù)和格S12,D的圖完全一樣,只不過前者結(jié)點(diǎn)用a,b標(biāo)記,后者結(jié)點(diǎn)用ab標(biāo)記而已。n (b) 記L=0,1,考慮格L,自身的積代數(shù)。這里是通常意義的“小于或等于”。這些積代數(shù)是n L2,2,L3,3Ln,n。一般地說,在格n Ln,n中,任意元素a,b有以下形式:第7章 格與布爾代數(shù)n

16、a=a1,a2,ann b=b1,b2,bnn 這里的ai,bi是0或1。n anb a1b1a2b2anbnn 也不難定義出Ln上的運(yùn)算 *和 。我們稱格nLn,n為0,1n重組的格。n 圖7.27給出了格L,L2,2和n L3,3的哈斯圖,一般地說,格Ln,n的圖是一個(gè)n維立方體。第7章 格與布爾代數(shù)圖 7.26第7章 格與布爾代數(shù)圖 7.27 第7章 格與布爾代數(shù)7.3 特殊的格 n 7.3.1 分配格n 任何格的元素都能滿足分配不等式,但某些特殊格,其所有元素都能滿足分配律。n 定義7.31設(shè)L,*, 是一個(gè)格,如果對(duì)于任何a,b,cL,有n a*(b c)=(a*b) (a*c) (

17、1)n a (b*c)=(a b)*(a c) (2)n 則稱L,*, 是一個(gè)分配格。第7章 格與布爾代數(shù)n 定理7.31 分配格是模格。n 證 由于a (b*c)=(a b)*(a c),若ac,則a c=c,n 代入上式得n a (b*c)=(a b)*c 證畢。n 格可分為模格和非模格,本定理和以下例子說明,模格又可分為分配格和非分配格。第7章 格與布爾代數(shù)n 例1n (a) 如圖7.31所示的格不是分配格,因?yàn)閚 a*(b c)=a*1=an a*b a*c=0 0=0 n 所以,a*(b c)(a*b) (a*c)但可以驗(yàn)證它是模格。n 注意,格中某些元素滿足分配律,但這不能保證是分

18、配格。n (b) 圖7.32所示的格不是分配格,因?yàn)樗皇悄８瘛D中n ba但b (c*a)(b c)*a第7章 格與布爾代數(shù)圖7.31 圖7.32 第7章 格與布爾代數(shù)n 定理7.32每個(gè)鏈都是分配格。n 證設(shè)L,是一個(gè)鏈,且a,b,cL,考察下述可能情況:(1)ab或ac;(2)ab和ac。n 對(duì)于情況(1)有n a * ( b c ) = a 和 ( a * b ) (a*c)=a n 對(duì)于情況(2)有n a*(bc)=b c和(a* b) (a*c)=b cn 這就證明了元素a,b,c滿足分配律(1)。第7章 格與布爾代數(shù)n 定理7.33分配格的子格是分配格;兩個(gè)分配格的積代數(shù)是分配格

19、。從子格和積代數(shù)的定義易知定理成立。n 定理7.34設(shè)L,*, 是一個(gè)分配格。對(duì)于任何元素a,b,cL有n (a*b=a*c)(a b=a c) b=cn 證 (a*b) c=(a*c) c=cn (a*b) c=(a c)*(b c)=(a b)*(b c) n =b (a*c)=b (a*b)=b n 證畢。第7章 格與布爾代數(shù)n 7.3.2 有界格和有補(bǔ)格n 設(shè)L,*, 是一個(gè)格,格中每一對(duì)元素都有最小上界和最大下界。用歸納法不難證明,格中每一個(gè)有窮子集,也都有一個(gè)最小上界和一個(gè)最大下界。n 設(shè)S=a1,a2,an是有窮子集,一般地說,S的最大下界和最小上界可表示為:121121glb(

20、 )*lub( )ninininiSaaaaSaaaa 第7章 格與布爾代數(shù)n 定義7.32如果在格L,中存在一個(gè)元素a,對(duì)于任何元素b,都有ab(ba),則稱a為格L,的全下界(全上界)。n 定理7.35一個(gè)格L,的全下界(全上界)是唯一的。n 證用反證法。如果有兩個(gè)全下界a和b,a,bL且ab。因?yàn)閍是全下界,所以ab。又因?yàn)閎是全下界,所以ba。因此,a=b,得出矛盾。類似地,可證全上界的唯一性。第7章 格與布爾代數(shù)n 例2 n (a)在格(S), 中,S是全上界,是全下界。n (b)在圖7.33所示的格中,a是全上界,h是全下界。n 定義7.33如果一個(gè)格中存在全下界和全上界,n 則把

21、它們稱為格的界,并分別用0和1來表示。有0和1的格稱為有界格。第7章 格與布爾代數(shù)圖 7.33第7章 格與布爾代數(shù)n 定理7.36設(shè)L,是一個(gè)有界格,對(duì)任意元素aL,必有:n a 0=a a*1=a (3) n a 1=1 a*0=0 (4)n 證由于0a1,所以上述各式顯然成立。證畢。n 式(3)說明,對(duì) ,0是么元;對(duì),1是么元。式(4)說明,對(duì),1是零元;對(duì) ,0是零元。這兩式還說明在有界格中,0和1互為對(duì)偶。第7章 格與布爾代數(shù)n 定義7.34設(shè)L,*, ,0,1是一有界格。對(duì)于L中的一個(gè)元素a,如果存在元素bL,使n a*b=0 a b=1n 則稱元素b是元素a的補(bǔ)元或補(bǔ),記為a。n

22、 上述定義中,a和b是對(duì)稱的,如果b是a的補(bǔ)元,則a也是b的補(bǔ)元。一般地說,一個(gè)元素aL,可以不存在補(bǔ)元;如果存在補(bǔ)元?jiǎng)t補(bǔ)元也未必是唯一的。 第7章 格與布爾代數(shù)n例4觀察圖7.34中各格的元素的補(bǔ)元。n在(a)中a,b,c三個(gè)結(jié)點(diǎn)都無補(bǔ)元。n在(b)中a,b,c都互為補(bǔ)元,補(bǔ)元不唯一。n在(c)中,c的補(bǔ)元是a和b;a的補(bǔ)元是c;b的補(bǔ)元是c。第7章 格與布爾代數(shù)圖 7.34第7章 格與布爾代數(shù)n 定理7.37在有界格L,*, ,0,1中,0和1互為補(bǔ)元,且是唯一的。n 證 因?yàn)?*1=0,0 1=1,所以0和1互為補(bǔ)元。若0的補(bǔ)元不唯一,另有補(bǔ)元c,則n 0*c=0, 0 c=1n 但0

23、c=c,c=1,得出矛盾。類似地可證1的補(bǔ)元也是唯一的。證畢。n 定理7.38在分配格中,如果元素aL有一個(gè)補(bǔ)元,則此補(bǔ)元是唯一的。n 證 假定b和c都是a的補(bǔ)元,則n a*b=0=a*c a b=1=a cn 由定理7.34得b=c。證畢。第7章 格與布爾代數(shù)n 定義7.35如果在一個(gè)有界格中,每個(gè)元素都至少有一個(gè)補(bǔ)元素,則稱此格為有補(bǔ)格。圖7.34的(b)和(c)都是有補(bǔ)格。n 定義7.36如果一個(gè)格,既是有補(bǔ)格,又是分配格,則稱此格為有補(bǔ)分配格,又稱布爾格。 第7章 格與布爾代數(shù)n 7.3.3 有補(bǔ)分配格的性質(zhì)n 定理7.39有補(bǔ)分配格L,*, 中,任何元素aL的補(bǔ)元a是唯一的。n 定

24、理 7 . 3 1 0 有 補(bǔ) 分 配 格L,*, 中,對(duì)于每一個(gè)aL,都有n (a)=an 證由于a*a=0,a a=1和(a)*an =0,(a) a=1,而補(bǔ)元是唯一的,所以,(a)=a。證畢。第7章 格與布爾代數(shù)n 定理7.311有補(bǔ)分配格L,*, 中,對(duì)于所有a,bL,有n (1) (a b)=a*bn (2) (a*b)=a bn 此即德摩根定律。n 證 (a b)(ab)=aab b*a*b=0n (a b) a*b=(a b a)(a b b)=1n 所以,(a b)=a*b。n 根據(jù)對(duì)偶性原理得(a*b)=a b。證畢。 第7章 格與布爾代數(shù)n 定理7.312有補(bǔ)分配格L,*

25、, 中,對(duì)所有a,bL,有n ab a*b=0a b=1n 證 由于 ab a*b=aa b=bn 根據(jù)德摩根定律得 n ab ab=ba b=an 因而 ab a * b=0n a b=1 第7章 格與布爾代數(shù)n反之,a*b=0 b (a*b)=b n b a=b n abn a b=1 a*(a b)=a n (a*a) (a*b)=a n a*b=an abn 證畢。第7章 格與布爾代數(shù)7.4 布爾代數(shù) n 7.4.1 布爾代數(shù)n 上節(jié)已指出,布爾代數(shù)就是有補(bǔ)分配格,常記以B,*, ,0,1,現(xiàn)將其性質(zhì)綜合如下:n 1.B,*, 是一個(gè)格,滿足n (L-1) a*a=a n (L-1)

26、a a=a n (L-2) a*b=b*a 第7章 格與布爾代數(shù)n(L-2) a b=b a n(L-3) (a*b)*c=a*(b*c) n(L-3) (a b) c=a (b c) n(L-4) a*(a b)=a n(L-4) a (a*b)=a第7章 格與布爾代數(shù)n 2.B, *, 是一個(gè)分配格,滿足n(D-1) a*(b c)=(a*b) (a*c) n (D-1) a (b*c)=(a b)*(a c) n (D-2) (a*b) (b*c) (c*a)=(a b)*(b c)*(c a) n (D-3) (a*b=a*c)(a b=a c) b=c 第7章 格與布爾代數(shù)n3.B,

27、*, ,0,1是一個(gè)有界格,滿足n(B-1) 0a1 n(B-2) a*0=0 n(B-2) a 1=1 n(B-3) a*1=a n(B-3) a 0=a第7章 格與布爾代數(shù)n4.B , *, ,0,1是一個(gè)有補(bǔ)格,滿足n (C-1) a*a=0 n (C-1) a a=1 n (C-2) 0=1 n (C-2) 1=0n5.B, *, ,0,1是一個(gè)有補(bǔ)分配格,滿足n (C-3) (a*b)=a b n (C-3) (a b)=a*b第7章 格與布爾代數(shù)n 6.在集合B上存在偏序,滿足n (P-1) a*b=glba,b n (P-1) a b=luba,b n (P-2) ab a*b=

28、a a b=b n (P-3) ab a*b=0 a b=1 ban 以上公式,不都是獨(dú)立的,可以從其中選定一些作為基本公式,推出其它公式。也就是說,可以用這些基本公式定義布爾代數(shù)。 第7章 格與布爾代數(shù)n 例1 n (a)設(shè)B=0,1,B上的運(yùn)算*, ,由下面的表定義:*0 1010 00 1 0 1010 11 1xx0110 代數(shù)B,*, ,0,1能滿足定義7.41的要求。所以它是布爾代數(shù),它是二元素布爾代數(shù)。二元素布爾代數(shù)是圖為鏈的唯一布爾代數(shù)。第7章 格與布爾代數(shù)n (b)設(shè)S是非空集合。(S)是它的冪集,n (S), -,S能滿足定義7.41的要求,所以是布爾代數(shù)。如果S有n個(gè)元素

29、,則(S)有2n個(gè)元素,該布爾代數(shù)的圖形是n維立方體。圖7.41給出了S=a,S=a,b,S=a,b,c時(shí)布爾代數(shù)的圖形。若S是空集,則(S)僅有一個(gè)元素 ,于是 =0=1,我們稱它為退化了的布爾代數(shù),我們不研究它。第7章 格與布爾代數(shù) 圖 7.41 第7章 格與布爾代數(shù)n (c)用S表示含有n個(gè)命題變?cè)拿} 公 式 集 合 。 代 數(shù) 系 統(tǒng) S , , , ,F,T是一布爾代數(shù),其中,和 分別是合取,析取和否定運(yùn)算,F和T是永假式和永真式,并把互為等價(jià)的兩個(gè)命題公式看成是相等的。對(duì)應(yīng)于運(yùn)算和,偏序關(guān)系是永真蘊(yùn)含。第7章 格與布爾代數(shù)n(d) 設(shè)Bn是0和1組成的n重組集合,記n a =

30、a1, a2, , an b =b1,b2,bn n 0n= 0 , 0 , , 0 1n=1,1,1na,b為Bn中的任意元素,定義n a*b=a1b1,a2b2,anbn n a b=a1b1,a2b2,anbn n a= a1, a2, an第7章 格與布爾代數(shù)n 7.4.2 子布爾代數(shù)n 定義7.42設(shè)B,*, ,0,1是一個(gè)布爾代數(shù),SB。如果S含有元素0和1,并且在運(yùn)算*, 和的作用下封閉,則稱S,*, ,0,1是B,*, ,0,1的子布爾代數(shù)。n 實(shí)際檢測(cè)一個(gè)子集S是否是子布爾代數(shù),不需要按定義進(jìn)行,只須該子集對(duì)運(yùn)算集合*,或 ,封閉就可以了。因?yàn)閚 a b=(a*b),1=(a

31、*a)和0=a*a第7章 格與布爾代數(shù)n 定理 7.41子布爾代數(shù)是一個(gè)布爾代數(shù)。n 證設(shè)S,*, ,0,1是B,*, ,0,1的子布爾代數(shù)。則0和1屬于S;由于S對(duì)*, 和是封閉的,所以,如果aS,則aS,于是定義7.41中的第3和4條顯然在S中成立;又交換律和分配律是繼承的,所以S,*, ,0,1是一個(gè)布爾代數(shù)。證畢。第7章 格與布爾代數(shù)n 例2考察圖7.42所示的布爾代數(shù)n B,* , ,0,1。n (a) S1=a,a,0,1,由于S1含有0和1,且對(duì)運(yùn)算*、 ,封閉。所以,S1,*, ,0,1是B,*, ,0,1的子布爾代數(shù)。這個(gè)子布爾代數(shù)也可以說由元素a生成的。一般地說,B的任意非

32、空子集都可以生成B,*, ,0,1的子布爾代數(shù)。 第7章 格與布爾代數(shù)圖 7.42 第7章 格與布爾代數(shù)n (b) S2=c,b,a,1,S2不包含特異元素0,所以不是B,*, ,0,1的子布爾代數(shù)。但若補(bǔ)運(yùn)算是對(duì)1(作為全上界)和 c ( 作 為 全 下 界 ) 定 義 的 , 則S2,*, ,c,1是布爾代數(shù)。n (c) S3=0,b,a,1對(duì)運(yùn)算不封閉,所以S3不能構(gòu)成布爾代數(shù),當(dāng)然也不能成為子布爾代數(shù)。n ( d ) 對(duì) 任 意 布 爾 代 數(shù)B,*, ,0,1子集0,1和B總能構(gòu)成子布爾代數(shù),這兩種子布爾代數(shù)稱為平凡的。第7章 格與布爾代數(shù)n 7.4.3 布爾同態(tài)n 定義7.43設(shè)A

33、,*, ,0,1和B, - ,是兩個(gè)布爾代數(shù)。定義一個(gè)映射f:AB,如果在f的作用下能夠保持布爾代數(shù)的所有運(yùn)算,且常數(shù)相對(duì)應(yīng),亦即對(duì)于任何a,bA有:n f (a*b)=f (a)f(b) n f (a b)=f (a)f(b) n f (a)=f (a) n f (0)= n f (1)=n 則稱映射f:AB是一個(gè)布爾同態(tài)。 第7章 格與布爾代數(shù)n 7.4.4 有限布爾代數(shù)的原子表示n 本小節(jié)研究有限布爾代數(shù)的一個(gè)重 要 性 質(zhì) , 就 是 任 何 有 限 布 爾 代 數(shù)B,*, ,0,1都同構(gòu)于某一集合S的冪集代數(shù)(S), -,S。n 我們探討這一問題的思路是這樣的:n 第一步:介紹B中的

34、特殊元素原子及其性質(zhì)。n 第二步:證明B中除0外的每一元素x,都可唯一地表示成原子的保聯(lián),即x=a1 a2 ak(ai是原子)n 第三步:證明上述斷言。 第7章 格與布爾代數(shù)n 定義7.44設(shè)a,b是一個(gè)格中的兩個(gè)元素,如果ba且ba,即ba,并且在此格中再?zèng)]有別的元素c,使得bc和ca,則稱元素a覆蓋元素b。n 定義7.45設(shè)B,*, ,0,1是一布爾代數(shù),aB,如果a復(fù)蓋0,則稱元素a是該布爾代數(shù)的一個(gè)原子。n 定理7.42元素a是布爾代數(shù)B,*, ,0,n 1的原子,當(dāng)且僅當(dāng)a0時(shí),對(duì)任意元素xB,有n x*a=a 或 x*a=0n 證必要性。因?yàn)閤*aa,而a是原子,所以,x*a=a或

35、x*a=0。第7章 格與布爾代數(shù)n 充分性。若a0不是原子,則存在一元素xB,合ax0,于是有x*a=x,這與假設(shè)“a0時(shí)對(duì)任意xB有x*a=a或x*a=0”相矛盾。所以,a是原子。證畢n 推 論 7 . 4 2 a 是 布 爾 代 數(shù)B,*, ,0,1的原子,x是B的任意元素,則或者ax,或者ax,但不能同時(shí)成立。 n 證由于n x*a=a ax, x*a=0 axn 所以,根據(jù)定理7.42,如果a是原子,x是B的任意元素,有 n a x 或 axn 若兩者同時(shí)成立,則ax*x=0,這與a0矛盾。 第7章 格與布爾代數(shù)n 定理7.42及其推論說明:原子是這樣的元素,它把B中的元素分為兩類,第

36、一類是與自己可比較的(包括自身),它小于等于這一類中的任一元素。第二類是與自己不可比較的或是0,它小于等于這一類中任一元素的補(bǔ)元。n 為了加深對(duì)原子和定理7.42的認(rèn)識(shí),試考察圖7.43,(a)中,a1是原子;(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子。在(a),(b)崐和(c)三圖中,虛線都是表示原子a1將B的元素劃分成兩類。第7章 格與布爾代數(shù)圖 7.43 第7章 格與布爾代數(shù)n 定理7.43 設(shè)B,*, ,0,1是一個(gè)有限布爾代數(shù),則對(duì)于每一個(gè)非零元 素 x B , 至 少 存 在 一 個(gè) 原 子 a , 使x*a=a(即ax)。n 證若x是原子,則x*x=x,此x就是

37、所求的原子a。若x不是原子,因?yàn)閤0,所以,從x下降到0有一條路徑,又由于B是有限的,此路徑所經(jīng)過的結(jié)點(diǎn)是有限的,不妨設(shè)為n xa1a2ak0n 則ak覆蓋0,而x*ak=ak,此ak就是所求的原子a。證畢。第7章 格與布爾代數(shù)n 定理7.44 如果元素a1和a2是布爾代數(shù)B,*, ,0,1中的兩個(gè)原子,且a1*a20,則a1=a2。n 證由定理7.42有a1*a2=a2和a2*a1=a1,所以a1=a2。本定理的逆反是:若a1a2,則a1*a2=0,它是關(guān)于原子的重要性質(zhì)。下面進(jìn)行第二步。第7章 格與布爾代數(shù)n 定理7.45設(shè)B,*, ,0,1是有限布爾代數(shù),x是B中任意非0元素,a1,a2

38、,ak是滿足aix的所有原子(i=1,2,k),則n x=a1 a2 akn 證記 a1 a2 ak=y,n 因?yàn)?aix(i=1,2,k)n 所以,yx。如果能進(jìn)一步證明xy,那么問題就解決了。由定理7.312知,只需證明x*y=0就可以了。為此,我們用反證法。 第7章 格與布爾代數(shù)n 設(shè)x*y0,于是必有一原子a,使ax*y,又因x*yx和x*yy,所以,由傳遞性得n ax 和 ayn 因?yàn)閍是一原子,且滿足ax,所以a必是a1,a2,ak中的一個(gè),因此ay。但這與ay矛盾。故x*y=0,即xy。證畢。第7章 格與布爾代數(shù)n 定理7.46 定理7.45中的表示式n x=a1 a2 akn

39、是唯一的。n 證 若另有一種表示式為n x=b1 b2 btn 其中b1,b2,bt是B中不同的原子。n 第7章 格與布爾代數(shù)n 因?yàn)閤是b1,b2,bt的最小上界,所以,bix(i=1,2,t)。n 而 a1, a2, , ak是 B 中 滿 足aix(i=1,2,k)的所有原子。所以,b1,b2,bt a1,a2,ak且tk。n 如果tk,那么a1,a2,ak中必有一ai與b1,b2,bt全不相同。于是,由n ai*(b1 b2 bt)=ai*(a1 a2 ak)n 得 0=ain 于是得到矛盾。所以,只有t=k,b1,b2,bt就是a1,a2,ak。證畢。n 現(xiàn)在進(jìn)行第三步。第7章 格與

40、布爾代數(shù)n 定理7.47設(shè)B,*, ,0,1是一個(gè)有限布爾代數(shù),S是此代數(shù)中的所有原子的集合,則B,*, ,0,1同構(gòu)于冪集代數(shù)(S), -,S。第7章 格與布爾代數(shù)n 推論7.47(a)B,*, ,0,1與(S), -, ,S同構(gòu),|(S)|=2|s|,所以,|B|=2|s|,故任一有限布爾代數(shù)載體的基數(shù)是2的冪。n (b) 任一有限布爾代數(shù)和它的原子集合S構(gòu)成的冪集集合代數(shù)(S), - ,S同構(gòu),但后者又與任一基數(shù)相同的冪集集合代數(shù)同構(gòu)。故具有相同載體基數(shù)的有限布爾代數(shù)都同構(gòu)。n 注意,定理7.47對(duì)無限布爾代數(shù)并不成立。第7章 格與布爾代數(shù)n 命題演算(集合論)中的極小項(xiàng)就是由n元命題公

41、式構(gòu)成的布爾代數(shù)的原子。除0外,每一公式都可化成極小項(xiàng)的析取(并)是大家已知的事實(shí)。n 此外,還可用布爾代數(shù)的反原子的保交來表示布爾代數(shù)的元素。反原子是被最大元素1所復(fù)蓋的元素。事實(shí)上,一個(gè)反原子是一個(gè)原子的補(bǔ),所以稱為反原子。根據(jù)對(duì)偶性原理,若把和,0和1,和,原子和反原子互換,重復(fù)上面的全部討論,就可得出相應(yīng)的結(jié)論。第7章 格與布爾代數(shù)圖 7.44第7章 格與布爾代數(shù)n 7.4.5 布爾代數(shù)的積代數(shù)n 定 義 7 . 4 6 設(shè) U =A,*, ,01,11和n V=B, ,02,12是兩個(gè)布爾代數(shù)。定義一個(gè)布爾代數(shù)n W=AB,+, -,03,13如下,其中“”“.”“ -”都是求補(bǔ)運(yùn)算

42、。對(duì)于任何a1,b1,a2,b2AB,第7章 格與布爾代數(shù)n a1, b1 a2, b2 =a1a2,b1b2 n a1, b1 + a2, b2 = a1 a2,b1b2 n a1,b1 =a1, b1n 則 稱 W 是 U 和 V 的 積 代 數(shù) 。 記 為W=UV。第7章 格與布爾代數(shù)n 定理7.48布爾代數(shù)的積代數(shù)是一布爾代數(shù)。n 證因?yàn)榻粨Q律,分配律,公式(B-3)(B-3)(C-1)和(C-1)均成立,符合定義7.41,所以,布爾代數(shù)的積代數(shù)是一布爾代數(shù)。證畢。n 我們用An=Bn,*, ,0,1表示具有n個(gè)元素的布爾代數(shù)。由推n 論7.47知,這里的n必定是2的冪。因此,最小的布

43、爾代數(shù)是n A2=B2, * , ,0,1n 這里B2=0,1,運(yùn)算表如例1(a)所定義。其次是n A4=B4,* , ,0,1n 設(shè)B4=0,a,b,1,其運(yùn)算表如下表所示:第7章 格與布爾代數(shù) 表 7.4-1第7章 格與布爾代數(shù)表 7.42 第7章 格與布爾代數(shù)n 定理7.49布爾代數(shù) 和 同構(gòu),且每一有限布爾代數(shù)都同構(gòu)于某一個(gè) 。n 證 和 基數(shù)相同,所以同構(gòu)。任一布爾代數(shù)的基數(shù)為2n,所以必與 同構(gòu)。證畢。n 本定理說明,只要對(duì) 研究清楚了,一切有限布爾代數(shù)也就清楚了。 2nA2nA2nA2nA2nA2nA2nA第7章 格與布爾代數(shù)n 例4n (a)A4與A22同構(gòu),對(duì)比運(yùn)算表7.41

44、和運(yùn)算表7.42即知。n (b) 設(shè)E=a1,a2,an,則布爾代數(shù)n (E), -, ,E和An2同構(gòu)。同構(gòu) f 可以這樣作出:n f:(E)Bn2 n f (S)=1,2,n10i當(dāng) 時(shí) 當(dāng) 時(shí) iaSiaS這里 例如,n=4時(shí), f (a1,a3,a4)=1,0,1,1第7章 格與布爾代數(shù)n 7.4.6 布爾函數(shù)n B, *, ,0,1是一個(gè)布爾代數(shù),現(xiàn)在考慮一個(gè)從Bn到B的函數(shù)。n 設(shè)B=0,1,表7.43給出了一個(gè)從B3到B的函數(shù)。n 設(shè)B=0,a,b,1,表7.44給出了一個(gè)從B2到B的函數(shù)。 第7章 格與布爾代數(shù) 表 7.43 第7章 格與布爾代數(shù)表 7.44 第7章 格與布爾代

45、數(shù)n 定義7.47設(shè)B,*, ,0,1是一個(gè)布爾代數(shù),取值于B中元素的變?cè)Q為布爾變?cè)?B中的元素稱為布爾常元。n 定義7.48設(shè)B,* , ,0,1是一個(gè)布爾代數(shù),這個(gè)布爾代數(shù)上的布爾表達(dá)式定義如下:n (1)單個(gè)布爾常元是一個(gè)布爾表達(dá)式;單個(gè)布爾變?cè)且粋€(gè)布爾表達(dá)式。 第7章 格與布爾代數(shù)n (2)如果e1和e2是布爾表達(dá)式,則(e1),(e1 e2),(e1*e2)也是布爾表達(dá)式。n (3) 除了有限次應(yīng)用條款1和2形成的表達(dá)式外,沒有其它字符串是布爾表達(dá)式。布爾表達(dá)式一般用f,g表示,或更明確地表示成f (x1,x2,xn),n 稱 為 n 元 布 爾 表 達(dá) 式 , 其 中x1,x2

46、,xn是式中可能含有的布爾變?cè)?。布爾表達(dá)式中的某些圓括號(hào)可以省略,約定類似于命題公式。第7章 格與布爾代數(shù)n 例5設(shè)0,a,b,1,*, ,0,1是布爾代數(shù),則n f1=a n f 2=0*x n f 3=(1*x1) x2 n f 4= ( ( a b ) ( x 1 x2)*(x1*x2) n 都是這個(gè)布爾代數(shù)上的布爾表達(dá)式。n 布爾表達(dá)式中的符號(hào),和,就是相應(yīng)布爾代數(shù)中,和三種運(yùn)算,它們滿足布爾代數(shù)的所有公式,可以按照這些公式進(jìn)行計(jì)算。 第7章 格與布爾代數(shù)n 定義7.49布爾代數(shù)B,*, ,0,1上的布爾表達(dá)式 f (x1,x2,xn)的值指的是:將B的元素作為變?cè)獂i(i=1,2,n

47、)的值而代入表達(dá)式以后,計(jì)算出來的表達(dá)式的值。n 例6n (a) 取x1=a,x2=b,則例5中的f3的值是n f3=(1*a) b=a b=1n (b)設(shè)布爾代數(shù)0,1,*, ,0,1上的表達(dá)式n f (x1,x2,x3)=(x1* x2)(x1 x2)(x2 x3),則n f (1,0,1)=(0*1)(0 1)*(0 1)=0*1*1=0第7章 格與布爾代數(shù)n 定 義 7 . 4 1 0 布 爾 代 數(shù)B,*, ,0,1上兩個(gè)n元布爾表達(dá)式f1(x1,x2,xn)和f2(x1,x2,xn),如果對(duì)n個(gè)變?cè)娜我庵概?f1和f2的值均相等,則稱這兩個(gè)布爾表達(dá)式是等價(jià)的或相等的。n 記作 f

48、1(x1,x2,xn)=f2(x1,x2,xn)。n 在實(shí)踐上,如果能有限次應(yīng)用布爾代數(shù)公式,將一個(gè)布爾表達(dá)式化成另一個(gè)表達(dá)式,就可以判定這兩個(gè)布爾表達(dá)式是等價(jià)的。第7章 格與布爾代數(shù)n 定義7.410給出的等價(jià)關(guān)系將n元布爾代數(shù)表達(dá)式集合劃分成等價(jià)類,處于同一個(gè)等價(jià)類中的表達(dá)式都相互等價(jià)。可以證明等價(jià)類數(shù)目是有限的。為此,我們考察以下定義。n 定義7.411給定n個(gè)布爾變?cè)獂1,x2,xn,表達(dá)式n 稱為極小項(xiàng)。這里 表示xi或xi兩者之一。123*nxxxxix第7章 格與布爾代數(shù)n 定義7.412n n 型式的布爾表達(dá)式稱為主析取范式。n 這里mi是極小項(xiàng),i是布爾常元。(i=0,1,2

49、,2n-1)。n 因?yàn)閕有|B|種取法,故不同的主析取范式有 個(gè)。特別,B=0,1時(shí)有 個(gè)。n 任何一個(gè)n元布爾表達(dá)式都唯一地等價(jià)于一個(gè)主析取范式。把一個(gè)n元布爾表達(dá)式化成等價(jià)的主析取范式,主要應(yīng)用德摩根定律等,其方法與“數(shù)理邏輯”和“數(shù)字邏輯”中化成主析取范式的方法完全一致。 00112121nna ma mam2nB22n第7章 格與布爾代數(shù)n 2n個(gè)極小項(xiàng)最多只能造出 個(gè)不同的主析取范式,所以,一個(gè)n元布爾表達(dá)式必等價(jià)于這 個(gè)主析取范式之一。平行地可討論極大項(xiàng)和合取范式。n 定義7.413給定n個(gè)布爾變?cè)獂1,x2,xn。表達(dá)式2nB2nB12nxxx稱為極大項(xiàng)。這里 表示xi或xi兩者之一。ix第7章 格與布爾代數(shù)n 顯然,有2n個(gè)不同的極大項(xiàng)。分別記為M0,M1,M2,