格與布爾代數(shù)

1、1離散數(shù)學(xué)離散數(shù)學(xué)（6.7 格與布爾代數(shù)）格與布爾代數(shù)）Discrete Mathematics（Algbra Structures）計算機(jī)科學(xué)及信息類專業(yè)基礎(chǔ)教材計算機(jī)科學(xué)及信息類專業(yè)基礎(chǔ)教材 2 定義定義(偏序關(guān)系與偏序集偏序關(guān)系與偏序集) 設(shè)設(shè)R是集合是集合A上的一個二元關(guān)上的一個二元關(guān)系系, 如果如果R具有具有自反性自反性, 反對稱性和傳遞性反對稱性和傳遞性, 那么稱那么稱R為為一個偏序關(guān)系一個偏序關(guān)系(或部分序或部分序, 或半序關(guān)系或半序關(guān)系); 記為記為，并稱，并稱 為為偏序集。偏序集。6.7.1 偏序集偏序集例如例如: 1.實數(shù)集合實數(shù)集合R關(guān)于它上面的小于等于關(guān)系做成一個偏序關(guān)

2、于它上面的小于等于關(guān)系做成一個偏序集集.2.正整數(shù)集正整數(shù)集I+關(guān)于整除關(guān)系關(guān)于整除關(guān)系D作成一個偏序集作成一個偏序集。33.集合的包含關(guān)系使得所考慮的集合全體集合的包含關(guān)系使得所考慮的集合全體S作成一個偏作成一個偏序集序集.4.集合集合A=a,b,c,d,e在在R下做成一個偏序集下做成一個偏序集, 這里這里R=, , , 。6.7.1 偏序集偏序集4Hasse圖圖 (1) 用小圓圈表示元素，且若用小圓圈表示元素，且若xy且且xy，則，則y畫在畫在x之上之上。(2) 規(guī)定若規(guī)定若xy(xy)且沒有其它元素且沒有其它元素z(zx,y),使得使得 xz且且zy,則在則在x與與y之間用線段相連。之間

3、用線段相連。6.7.1 偏序集偏序集5例：例：集合集合A=a,b,c,d,e在在R下做成一個偏序集下做成一個偏序集, 這這里里R=, , , 。6.7.1 偏序集偏序集abcedHasse圖圖6例例. 設(shè)設(shè)n為正整數(shù)為正整數(shù),Sn是是n的全部正因數(shù)的集合的全部正因數(shù)的集合,則則 是格是格.和和 的的Hasse圖如下圖如下:6.7.1 偏序集偏序集S24=1，2，3，4，6，8，12，24S30=1，2，3，5，6，10，15，307定義定義(最大元和最小元最大元和最小元) 設(shè)設(shè)為偏序集為偏序集,如果如果A中有一中有一個元素個元素a, 對于所有的對于所有的A中元素中元素x, 都有都有xa(ax)

4、, 則稱則稱a為該偏序集的最大元為該偏序集的最大元(最小元最小元).abced6.7.1 偏序集偏序集8定義定義(極大元和極小元極大元和極小元) 設(shè)設(shè)為偏序集為偏序集, A中元素中元素a稱稱為一個極大為一個極大(小小)元元, 如果除如果除a之外之外, A中沒有元素中沒有元素x, 使使得得ax(xa); 或者等價地或者等價地, x A, ax(xa), 則則a=x.abced6.7.1 偏序集偏序集9 設(shè)設(shè)是是a,b,c的冪集關(guān)于包含于關(guān)系構(gòu)的冪集關(guān)于包含于關(guān)系構(gòu)成的偏序集成的偏序集,該偏序集的該偏序集的Hasse 圖如下圖如下6.7.1 偏序集偏序集10結(jié)論結(jié)論：（1）最大）最大(小小)元一定

5、唯一；而極大元一定唯一；而極大(小小)元不一定。元不一定。 (2) 最大元一定是極大元；最小元一定是極小元。最大元一定是極大元；最小元一定是極小元。反之反之 不真不真.6.7.1 偏序集偏序集11MA=a,b,c,d,e,f ,M=a,b定義定義(上界和下界上界和下界) 設(shè)設(shè)為偏序集為偏序集, M A, 若若A中中存在元素存在元素a，對對M中任意元素中任意元素m, 都有都有ma(am).則則稱稱a為為M的一個上界的一個上界(下界下界).結(jié)論：結(jié)論：由定義可以看出由定義可以看出, M的上的上(下下)界未必在界未必在M中中, 而且而且M未必未必一定有上一定有上(下下)界界.6.7.1 偏序集偏序集

6、上界為上界為a,c;d下界為下界為b,e,fM=a,c,d無上界無上界M=b,c,f無下界無下界12定義定義(上確界和下確界上確界和下確界)設(shè)設(shè)為偏序集為偏序集, M A, A中元素中元素a稱為稱為M的的最小上界即上確界最小上界即上確界(最大下界即下確界最大下界即下確界), 如果如果a是是M的一個上界的一個上界(下界下界), 并且對并且對M的任意一個上界的任意一個上界(下界下界)x, 都有都有ax (xa).6.7.1 偏序集偏序集無上確界，下確界為無上確界，下確界為eM=c,d上確界為上確界為a，下確界為，下確界為b136.7.1 偏序集偏序集M=a,b上確界上確界a,b，下確界為，下確界為

7、 上確界上確界a,b，下確界為，下確界為a 上確界上確界a,b,c，下確界為，下確界為b M=a,b,c或或M=a,b,c或或M=a,a,b上確界上確界a,b,c，下確界為，下確界為 M=a,b,b,c14定義定義(全序集或全序集或鏈鏈) 設(shè)設(shè)為為一個偏序集，稱為一條一個偏序集，稱為一條鏈鏈, 如果如果A中任意兩個元素中任意兩個元素a,b都是可比的都是可比的, 即在即在A上偏上偏序關(guān)系下序關(guān)系下, 對于對于A中任意兩個元素中任意兩個元素a,b，必有，必有ab或或ba. 則稱該則稱該偏序集偏序集為全序集，為全序集，全序集亦稱鏈全序集亦稱鏈. 6.7.1 偏序集偏序集例例: (見圖見圖1)，(見圖

8、見圖2)作成一條鏈。作成一條鏈。圖圖2156.7.1 偏序集偏序集定義（良序集定義（良序集）任何一個非空子集都有最小元任何一個非空子集都有最小元素的偏序集素的偏序集稱為良序集。稱為良序集。例：例：(見圖見圖1)是良序集；是良序集； (見圖見圖2)不是良序集（因不是良序集（因I+在大于等于關(guān)系在大于等于關(guān)系 下無最小元；下無最小元；圖圖216 結(jié)論：結(jié)論： 良序集是鏈，但鏈未必就是良序集，如良序集是鏈，但鏈未必就是良序集，如是是全序，但并非任意子集均有最小元，全序，但并非任意子集均有最小元，I+在大于等于關(guān)在大于等于關(guān)系下就無最小元；然而任何一條系下就無最小元；然而任何一條有限有限的鏈，必是一個

9、的鏈，必是一個良序集。良序集。6.7.1 偏序集偏序集176.7.2 格的定義格的定義定義定義1 (格的偏序定義格的偏序定義)給出一個偏序集給出一個偏序集,如果對于任意如果對于任意a,b L，L的子集的子集a,b在在L中都有上確界中都有上確界: supa,b 和和 下確界下確界: infa,b，則稱，則稱是一個是一個偏序格偏序格。186.7.2 格的定義格的定義( a )鏈?zhǔn)歉矜準(zhǔn)歉?( b )偏序偏序,格格;( c )偏序偏序,格格;( d )偏序偏序,格格;( e )偏序偏序,非格非格;( f )偏序偏序,非格非格;( g )偏序偏序,格格;( h )偏序偏序,非格非格;( i )偏序偏序

10、,非格非格;196.7.2 格的定義格的定義例例. 設(shè)設(shè)S是任意集合是任意集合, 則則為偏序格為偏序格。|S|=1|S|=2|S|=3兩個集合兩個集合A，B的上確界是的上確界是AB，下確界是，下確界是AB206.7.2 格的定義格的定義例例. 設(shè)設(shè)n為正整數(shù)為正整數(shù),Sn是是n的全部正因數(shù)的集合的全部正因數(shù)的集合,則則 是格是格和和 的的Hasse圖如下圖如下:兩個正整數(shù)的上確界是它們的最小公倍數(shù)，兩個正整數(shù)的上確界是它們的最小公倍數(shù)，下確界是它們的最大公約數(shù)。下確界是它們的最大公約數(shù)。216.7.2 格的定義格的定義定義定義2(代數(shù)格代數(shù)格) 設(shè)設(shè)是代數(shù)是代數(shù), a,b,c L,若若滿足滿足

11、: (1)交換律交換律: a*b=b*a, a b=b a; (2)結(jié)合律結(jié)合律: a* (b*c)=(a*b) *c，a (b c)=(a b) c; (3)吸收律吸收律: a*(a b)=a，a (a*b)=a 則稱此代數(shù)系統(tǒng)則稱此代數(shù)系統(tǒng)是是代數(shù)格代數(shù)格. . 226.7.2 格的定義格的定義定理定理1 代數(shù)格代數(shù)格關(guān)于運(yùn)算具有關(guān)于運(yùn)算具有冪等律冪等律.證明證明: 滿足代數(shù)格定義具有吸收律滿足代數(shù)格定義具有吸收律: 即對即對 a,b L都有都有a*(a b)=a, a (a*b)=a.于是于是, 對對L中任意中任意元元x,由吸收律由吸收律,得得 x * x=x *(x (x * x)=x

12、. x xx (x *(x x)=x, 即即具有冪等律具有冪等律.236.7.2 格的定義格的定義定理定理2(代數(shù)格代數(shù)格=偏序格偏序格) 在在代數(shù)格代數(shù)格中中,如果對如果對L中任意元中任意元a,b,成立成立: ab iff a*b=a(或或 a b=b） 則則“”就是就是L中的一個偏序關(guān)系。即中的一個偏序關(guān)系。即是是偏序格偏序格證明證明: (1)“”自反自反: 由代數(shù)格由代數(shù)格關(guān)于運(yùn)算具有冪等律，對任意的關(guān)于運(yùn)算具有冪等律，對任意的L中元中元a, 有有a*a=a， 于是于是aa246.7.2 格的定義格的定義(2)“”反對稱反對稱: 對對L中任意元素中任意元素a,b, 若若ab且且ba, 即

13、即a*b=a且且b*a=b,則則由由的交換律得的交換律得: a=a*b=b*a=b;(3)“”具有傳遞性具有傳遞性: 對對L中任意元中任意元a,b,c，如果，如果ab且且bc,即即a*b=a且且b*c=b, 則由則由的結(jié)合律的結(jié)合律, ,得得a*c=(a*b)*c=a*(b*c)=a*b=a,于是于是ac. 25在代數(shù)格在代數(shù)格中中: a*b=a iff a b=b事實上事實上,若若a*b=a,則則a b=b a=b (a*b) = b (b*a)=b;反之若反之若a b=b,則則a*b=a*(a b)=a.6.7.2 格的定義格的定義266.7.2 格的定義格的定義證明證明: 在在中中, 對

14、對L的任意元的任意元a,b, 都有都有: a b=supa,b=supb,a=b a 同理同理a*b=infa,b= infb,a=b*a a (b c)=supa,supb,c=supa,b,c =supsupa,b,c=(a b) c 同理同理a*(b*c)=(a*b)*c定理定理3(偏序格偏序格=代數(shù)格代數(shù)格) 設(shè)設(shè)是是偏序格，偏序格， a,b L, 定義定義: a*b=infa,b, a b=supa,b，則，則為為代數(shù)格。代數(shù)格。276.7.2 格的定義格的定義 下面證明吸收律：下面證明吸收律：a*(a b)=a 因為因為a*(a b)是是a與與a b的下確界，所以的下確界，所以a*

15、(a b)a a是是a與與a b的一個下界，而的一個下界，而a*(a b)是最大下界。是最大下界。 所以所以aa*(a b)，由反對稱性，由反對稱性， a*(a b)=a 同理可證同理可證a (a*b)=a286.7.2 格的定義格的定義例：例：冪集代數(shù)格，冪集代數(shù)格， 冪集偏序格。冪集偏序格。 A B iff AB=A或或AB=B296.7.3 格的性質(zhì)格的性質(zhì)定理定理 1 (偏序?qū)\(yùn)算的保序性定理偏序?qū)\(yùn)算的保序性定理) 設(shè)設(shè) 是格，是格， a,b,c L, 若若bc，則則: a*ba*c; a ba c.一般結(jié)論：一般結(jié)論： ab ，cd, 則則: a*cb*d; a cb d.證明證明

16、: 因為因為bc, 所以所以b*c=b. 而而 (a*b)*(a*c)=a*(b*c)=a*b, 得得a*ba*c. 同理同理, 由由bc，得，得a ba c。306.7.3 格的性質(zhì)格的性質(zhì)證明證明: 因為因為 aa b, aa c; 得得 ：a(a b)*(a c). 因為因為 b*cba b, b*cca c得得: b*c(a b)*(a c). 則則 a (b*c)(a b)*(a c). 同理可證，有同理可證，有(a*b) (a*c)a*(b c). 定理定理2(分配不等式分配不等式) 設(shè)設(shè)是格，是格， a,b,c L, 則則: a (b*c)(a b)*(a c); (a*b) (

17、a*c)a*(b c).316.7.3 格的性質(zhì)格的性質(zhì)證明證明: (=) 設(shè)設(shè)ab，由由 a b=b，得，得 a (b*c)(a b)*(a c)=b*(a c). ( (=) ) aa (b*c)b*(a c)b定理定理3(模不等式模不等式) 設(shè)設(shè)是格是格, a,b,c L, 則則 ab iff a (b*c)b*(a c).326.7.4 幾種特殊的格幾種特殊的格定義定義1 (有界格有界格) 若格若格存在最大元和最小元，則稱該格為存在最大元和最小元，則稱該格為有界格。有界格。 記記最大元為最大元為1，最小元為，最小元為0。記。記有界格為有界格為。例：例： 有界格。有界格。 336.7.4

18、 幾種特殊的格幾種特殊的格定義定義2 (補(bǔ)元補(bǔ)元) 有界格有界格中，如果中，如果a*b=0且且a b=1. 則稱元素則稱元素b為為a的補(bǔ)元。的補(bǔ)元。346.7.4 幾種特殊的格幾種特殊的格 (a)中中,a和和b均無補(bǔ)元，因為雖有均無補(bǔ)元，因為雖有 a b=1,但無但無a*b=0; (b)中中,a和和b互補(bǔ)，且補(bǔ)元唯一互補(bǔ)，且補(bǔ)元唯一; ; (c)中中,a有兩個補(bǔ)元，即有兩個補(bǔ)元，即b1和和b2。而且而且(a),(b),(c)中的元中的元0,1互為補(bǔ)元互為補(bǔ)元結(jié)論：結(jié)論：(1) 補(bǔ)元互補(bǔ)。補(bǔ)元互補(bǔ)。 即即b是是a的補(bǔ)元的補(bǔ)元, a也是也是b的補(bǔ)元的補(bǔ)元.(2) 在格在格中元素可能有補(bǔ)元中元素可能

19、有補(bǔ)元,可能沒有補(bǔ)元可能沒有補(bǔ)元.(3) 如果某元素有補(bǔ)元如果某元素有補(bǔ)元,則補(bǔ)元未必是唯一的則補(bǔ)元未必是唯一的.356.7.4 幾種特殊的格幾種特殊的格定義定義3(有補(bǔ)格有補(bǔ)格) 有界格有界格稱為是一個有補(bǔ)格稱為是一個有補(bǔ)格,如果對如果對L中中每個元素每個元素, 都至少有一個補(bǔ)元都至少有一個補(bǔ)元.(a),(b),(e)不是有補(bǔ)格，不是有補(bǔ)格，(c)和和(d)是有補(bǔ)格是有補(bǔ)格.(a) (b) (c) (e)366.7.4 幾種特殊的格幾種特殊的格例例： 是有補(bǔ)格是有補(bǔ)格. 最大元是最大元是S，最小元是，最小元是。 對對P(S)中任一元素中任一元素A,S與與A的差集的差集S-A是其唯一補(bǔ)元是其唯

20、一補(bǔ)元 因為因為: (S-A)A=S和和(S-A)A=.376.7.4 幾種特殊的格幾種特殊的格定義定義4(分配格分配格) 格格稱作一個分配格稱作一個分配格,如果對如果對L中中任意元素任意元素a,b,c都有都有: (1) a*(b c)=(a*b) (a*c); (2) a (b*c)=(a b)*(a c). .例：例：冪集格冪集格都是分配格都是分配格. 格格的兩個二元運(yùn)算分別是的兩個二元運(yùn)算分別是S冪集合上的交和并運(yùn)算冪集合上的交和并運(yùn)算,交交對并和并對交都具有分配律對并和并對交都具有分配律;38(a) (b) (c) (e)a1a2a3b3b1b2因為因為a1*(a2 a3)= a1*1

21、=a1 (a1*a2) (a1*a3)= 0*0=0 所以所以(c)不是分配格。不是分配格。因為因為b2*(b1 b3)=b2*1=b2 (b2*b1) (b2*b3)=0 b3=b3所以所以(d)不是分配格不是分配格6.7.4 幾種特殊的格幾種特殊的格(a),(b),(e)是分配格是分配格396.7.4 幾種特殊的格幾種特殊的格定理定理1 (De Morgan律律) 設(shè)設(shè)是分配格是分配格. 若若L的元素的元素a,b分別分別有補(bǔ)元有補(bǔ)元a,b, 則則a*b, a b 也有補(bǔ)元也有補(bǔ)元,且且: (a*b)=a b,(a b)=a*b.證明：因為證明：因為(a b) (a*b)=(a b) a)*

22、 (a b) b) = (1 b)*(a 1)=1*1=1且且(a b)*(a*b)=(a*(a*b) (b*(a*b)=(0*b) (a*0)=0 0=0, 所以由補(bǔ)元定義可知所以由補(bǔ)元定義可知(a*b)= a b. 同理有同理有(a b)=a*b. 40定理定理2(分配格中的消去律分配格中的消去律) 設(shè)設(shè)是分配格是分配格,對對L中任意中任意元元a,b,c,若若a*b=a*c且且a b=a c,則則b=c.證明：證明：b=b*(a b)=b*(a c)=(b*a) (b*c) =(a*c) (b*c)=(a b)*c=(a c)*c=c. 6.7.4 幾種特殊的格幾種特殊的格推論推論1：分配

23、格：分配格中中,若若L中的元素有補(bǔ)元，則補(bǔ)元唯一中的元素有補(bǔ)元，則補(bǔ)元唯一證明：設(shè)證明：設(shè)b,c是是a的補(bǔ)元，的補(bǔ)元， 則則 b a=1=c a, b*a=0=c*a, 由由定理定理2，bc推論推論2：在有補(bǔ)分配格：在有補(bǔ)分配格中中,L的任何元素，都有唯一的補(bǔ)元的任何元素，都有唯一的補(bǔ)元41定義定義5 (模格模格) 設(shè)設(shè)是格是格,a,b,c是是L中任意元素中任意元素,若若 ab，則，則a (b*c)b*(a c). 則稱則稱為模格。為模格。6.7.4 幾種特殊的格幾種特殊的格b1b3b2b3 b2b3 (b2*b1)=b3b2*(b3 b1)=b2非模格非模格模格模格426.7.4 幾種特殊的

24、格幾種特殊的格定理定理3 分配格一定是模格。分配格一定是模格。證明：因為在分配格中，證明：因為在分配格中， a (b*c)=(a b)*(a c). 若若ab，則，則a bb， 所以所以a (b*c)=(a b)*(a c)= b*(a c)436.7.4 幾種特殊的格幾種特殊的格定理定理4 一個格一個格是分配格的當(dāng)且僅當(dāng)不含有非分配的是分配格的當(dāng)且僅當(dāng)不含有非分配的 五階子格五階子格(a)或或(b).定理定理5 一個格一個格是一個模格是一個模格, ,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)不含有非不含有非 模格的五階子格模格的五階子格(b)(b). 非模格非模格非分配格非分配格446.7.6 布爾代數(shù)布爾代數(shù)定義定

25、義1 稱一個有補(bǔ)分配格為一個稱一個有補(bǔ)分配格為一個布爾代數(shù)布爾代數(shù). 由定義知由定義知, 一個布爾代數(shù)首先是一個有界格一個布爾代數(shù)首先是一個有界格,界元記為界元記為0,1. 其次其次是有補(bǔ)格是有補(bǔ)格,格中每一元素都有補(bǔ)元格中每一元素都有補(bǔ)元. . 在分配格中在分配格中,補(bǔ)元唯一補(bǔ)元唯一, 即即布爾代數(shù)中的每一元素布爾代數(shù)中的每一元素a都有唯一的補(bǔ)元都有唯一的補(bǔ)元a. 換句話說換句話說, 布爾代布爾代數(shù)上具有一元補(bǔ)運(yùn)算數(shù)上具有一元補(bǔ)運(yùn)算. .因此因此,一般將一個布爾代數(shù)記為一般將一個布爾代數(shù)記為,其中符號其中符號*, 和和分別稱作二元乘、加和分別稱作二元乘、加和一元一元補(bǔ)運(yùn)算補(bǔ)運(yùn)算. . 當(dāng)當(dāng)B

26、為有限集時為有限集時,稱有限布爾代數(shù)稱有限布爾代數(shù)當(dāng)當(dāng)B為無限集時為無限集時,稱無限布爾代數(shù)稱無限布爾代數(shù)456.7.6 布爾代數(shù)布爾代數(shù)(一一)布爾代數(shù)是格布爾代數(shù)是格, a,b B都有都有: 1. aba*b=aa b=b. 2. a*b=infa,b, a b=supa,b. 3. aba*b=0a b=1ba. 證明證明3(=) 由由ab，得，得a b=b，由于補(bǔ)元唯一，則，由于補(bǔ)元唯一，則 (a b)=b, 得得 a * b =b , 因而因而 a*b= a*(a*b)=(a*a)*b =0 (=) 由由a*b=0,得得 a*b=(a*b) (a*b)=a*(b b)=a 所以所以a

27、b466.7.6 布爾代數(shù)布爾代數(shù)(二二)布爾代數(shù)是代數(shù)格布爾代數(shù)是代數(shù)格, a,b,c B都有都有: 4. a*b=b*a, a b=b a。 7. (a*b)*c=a*(b*c), (a b) c=a (b c). 6. a*(a b)=a, a (a*b)=a. 7. a*a=a, a a=a. (三三)布爾代數(shù)是有界格布爾代數(shù)是有界格, a B都有都有: 8. 0a1。 9. a*0=0, a 1=1。 10. a*1=a, a 0=a。 476.7.6 布爾代數(shù)布爾代數(shù)(四四) 布爾代數(shù)是有補(bǔ)格布爾代數(shù)是有補(bǔ)格, a,b B都有都有: 11. a*a=0, a a=1. 12. 0=

28、1, 1=0. 13. (a*b)=a b, (a b)=a*b.(五五) 布爾代數(shù)是分配格布爾代數(shù)是分配格, a,b,c B都有都有: 14. a*(b c)=(a*b) (a*c), a (b*c)=(a b)*(a c). 15. (a*b) (b*c) (c*a)=(a b)*(b c)*(c a). /練習(xí)練習(xí) 16. a*b=a*c, a b=a c b=c. /消去律消去律486.7.6 布爾代數(shù)布爾代數(shù)證明：證明： b=b (a*b) =b (a*c) =(b a)*(b c) =(a c)*(b c) =(a*b) c =(a*c) c =c定理定理1：在分配格：在分配格中中

29、, 對對 a,b,c B, 若若 a b=a c, a*b=a*c, 則必有則必有b=c.49定理定理2：在有補(bǔ)分配格：在有補(bǔ)分配格中中, 每一元的每一元的補(bǔ)元唯一補(bǔ)元唯一. 6.7.6 布爾代數(shù)布爾代數(shù)證明：設(shè)證明：設(shè)a1和和a2是是a的補(bǔ)元，則的補(bǔ)元，則 a*a1=0=a*a2, a a1=1=a a2 由定理由定理1，得，得a1=a2506.7.6 布爾代數(shù)布爾代數(shù)定理定理3(Huntington定理定理) 設(shè)設(shè)是具有兩個二元運(yùn)算是具有兩個二元運(yùn)算的代數(shù)系統(tǒng)的代數(shù)系統(tǒng)(|B|1)，如果對如果對 a,b,c B都滿足下述性都滿足下述性質(zhì)質(zhì): (H1) a*b=b*a, a b=b a; (

30、H2) a*(b c)=(a*b) (a*c), a (b*c)=(a b)*(a c); (H3) B中存在元素中存在元素(記之為記之為)0和和1,使有使有a*1=a, a 0=a ; (H4) 對對B中中a,存在存在a B,使有使有a*a=0, a a=1. 則稱則稱是一個布爾代數(shù)是一個布爾代數(shù)。516.7.6 布爾代數(shù)布爾代數(shù)引理引理1(零律零律) 即即 a B,都有都有a 1=1, a*0=0.證明證明: : 這由這由: : a 1=(a 1)*1 (H3) =1*(a 1) (H1) =(a a)*(a 1) (H4) =a (a*1) (H2) =a a (H3) =1 (H4)

31、同理可證同理可證a*0=052引理引理2(吸收律吸收律) a,b B, a (a*b)=a, a*(a b)=a證明：證明：a (a*b)=(a*1) (a*b) （H3） =a*(1 b) （H2） =a*1 （引理（引理1） =a （H3）同理可證同理可證 a*(a b)=a 6.7.6 布爾代數(shù)布爾代數(shù)536.7.6 布爾代數(shù)布爾代數(shù)引理引理3 (滿足滿足“補(bǔ)元消去律補(bǔ)元消去律”) 滿足滿足Huntington定理的代數(shù)定理的代數(shù)中中, 對對 a,b,c B,有有a B滿足滿足a b=a c, a b=a c, 則必有則必有b=c.證明證明:因為因為b=b 0 （H3） =b (a*a)

32、 （H4） = (b a)*(b a) （H2） =(a c)*(a c) （代換）（代換） = (c a)*(c a) （H2） =c (a*a) （H2） =c 0 （H4） =c546.7.6 布爾代數(shù)布爾代數(shù)引理引理4（結(jié)合律）（結(jié)合律） a,b,c B， a*(b*c)=(a*b)*c, a (b c)=(a b) c;證明：證明： 分析：利用補(bǔ)元消去律進(jìn)行證明。分析：利用補(bǔ)元消去律進(jìn)行證明。 記記A1 a*(b*c); A2= (a*b)*c 即若即若a A1=a A2且且a A1=a A2，則，則A1=A2 因為因為 a A1=a(吸收律吸收律) a A2= a (a*b)*c)

33、 =(a (a*b)*(a c) =a*(a c) =a 所以所以 a A1=a A2 55又因為又因為a A1=(a (a*(b*c) =(a a)*(a (b*c) /分配律分配律 = a (b*c) a A2=a (a*b)*c) =(a (a*b)*(a c) /分配律分配律 =(a a)*(a b)*(a c) /分配律分配律 =(a b)*(a c) =a (b*c) 所以所以a A1=a A2 由由補(bǔ)元消去律得，補(bǔ)元消去律得，A1=A26.7.6 布爾代數(shù)布爾代數(shù)56引理引理5(證明證明0和和1是最小元和最大元是最小元和最大元) 即即 a B,都都有有0a1.證明證明: 因為因為

34、 a, b B, ab iff a*b=a(或或 a b=b） 由由H3，有，有a*1=a, a 0=a，可知，可知0a1即即是有界格，再由是有界格，再由H2和和H4可知可知是有補(bǔ)分配格，即為布爾代數(shù)。是有補(bǔ)分配格，即為布爾代數(shù)。6.7.6 布爾代數(shù)布爾代數(shù)576.7.6 布爾代數(shù)布爾代數(shù)例例. 以下代數(shù)是布爾代數(shù)以下代數(shù)是布爾代數(shù),它們滿足它們滿足Huntington公理。公理。1.是布爾代數(shù)是布爾代數(shù),這個簡單的布爾代數(shù)這個簡單的布爾代數(shù)稱稱電路代數(shù)電路代數(shù)。2.非空集合非空集合S的冪集代數(shù)的冪集代數(shù)是布爾代數(shù)是布爾代數(shù)稱稱集合代數(shù)集合代數(shù)。3.設(shè)設(shè)P為命題公式的集合為命題公式的集合,則則

35、是布爾代數(shù)是布爾代數(shù),亦稱亦稱命題代數(shù)命題代數(shù)。586.7.6 布爾代數(shù)布爾代數(shù)定義定義2 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù), 0,1 S B. 若若 也也是布爾代數(shù)是布爾代數(shù),則稱之為布爾代則稱之為布爾代 數(shù)數(shù)的的子布爾代數(shù)子布爾代數(shù). .596.7.6 布爾代數(shù)布爾代數(shù)定理定理4 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù). .載體載體B的子集的子集S是子是子布爾代數(shù)當(dāng)且僅當(dāng)布爾代數(shù)當(dāng)且僅當(dāng)S對運(yùn)算對運(yùn)算 *, 或者或者 , 封閉封閉. . 證明：若證明：若S對運(yùn)算對運(yùn)算 *, 封閉封閉,則任取則任取 a S,有有a S,因此有因此有 0=a*a S,進(jìn)而有進(jìn)而有1=0 S. 而且對而且對 a,b S,有有a,b

36、S,于是有于是有a b=(a*b) S。 a,b S, 由于由于 和和*封閉，所封閉，所以以a 0=a S，a a=1 S, a*1=a S,又又a b S B ，a*b S B ，所以，所以a bb a，a*bb*a。同理在。同理在S S中中 與與*互相具有分配律。由互相具有分配律。由Huntington定理，定理，S是是B的子的子布爾代數(shù)。布爾代數(shù)。606.7.6 布爾代數(shù)布爾代數(shù)定義定義4 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù).若若B中元素中元素a0且對且對 x B,滿足滿足x*a=a或者或者x*a=0,則稱則稱a為該布爾代數(shù)的為該布爾代數(shù)的下下原子原子。下原子是下原子是a, b, c616.7.6

37、 布爾代數(shù)布爾代數(shù) 若若a是下原子是下原子,則布爾代數(shù)中不存在元素則布爾代數(shù)中不存在元素0 0ba,能有能有0ba.不然不然,由由b*a=b及及b0,ba, 就會產(chǎn)生與就會產(chǎn)生與a是下原是下原子的矛盾子的矛盾. .換句話說換句話說,在布爾代數(shù)的在布爾代數(shù)的Hasse圖中圖中,下原子下原子是那些蓋住最小元是那些蓋住最小元0的元素的元素,即最小元即最小元0與下原子與下原子 由一條線段直接相連。由一條線段直接相連。 若兩個下原子的乘積不為若兩個下原子的乘積不為0, 則則 a1=a1*a2=a2.逆否逆否命題是說命題是說, 若兩個下原子若兩個下原子a1a2,則則 a1*a2=0. 626.7.6 布爾

38、代數(shù)布爾代數(shù)引理引理1 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù), 則對每一非零元則對每一非零元x B, 必有下原子必有下原子a, 滿足滿足ax。證明證明: 若若x是下原子是下原子,該該引理顯然成立引理顯然成立; 若若x不是下原子不是下原子, 則有則有B中非零元中非零元b0,使得使得x*b00且且x*b0 x.令令x*b0=x1,則則x1x. 若若x1是下原子是下原子,則該引理已證則該引理已證;若若x1不是下原子不是下原子,則有則有B中非零元中非零元b1,使得使得x1*b10且且x1*b1x1. .令令x1*b1=x2, 則則x2x1. .重復(fù)上述過程重復(fù)上述過程,由于我們討論的布由于我們討論的布爾代數(shù)其階數(shù)

39、爾代數(shù)其階數(shù)|B|有限有限,故必存在故必存在xn=a, a是布爾代數(shù)的是布爾代數(shù)的下原子下原子. . 63下原子是下原子是a, b, c6.7.6 布爾代數(shù)布爾代數(shù)646.7.6 布爾代數(shù)布爾代數(shù)引理引理2 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù), x是是B中任意非中任意非0元素元素. .如果如果a1,a2,.,am是所有滿足是所有滿足aix的下原子的下原子, 則則: : x=a1 a2 . am,且表達(dá)式唯一且表達(dá)式唯一. . 例：例：a= a b= bc= ca,b= aba,c= acb,c= bca,b,c= abc下原子是下原子是a, b, c65證明證明: (1) x= a1 a2 . am（

40、aix的下原子）的下原子） 由已知由已知a1x, a2x,.,amx, 得得a1 a2 . amx.下面下面證證: x*(a1 a2 . am)=0, 依此及先前的性質(zhì)可依此及先前的性質(zhì)可 得得 x a1 a2 . am.從而得證明從而得證明. 記記b=(a1 a2 . am)6.7.6 布爾代數(shù)布爾代數(shù)666.7.6 布爾代數(shù)布爾代數(shù) 反證：若反證：若x*b0, 由引理由引理1 1,則有下原子則有下原子a,使有使有 ax*b b, 則則ab(1) 但所有滿足但所有滿足aix的下原子只能是的下原子只能是a1,a2,.,am中之一中之一, 所以無妨認(rèn)為所以無妨認(rèn)為a=ai. .于是于是 aa1 a2 . ai am. (2) 由由(1)(1)和和(2)(2)，得，得a(a1 a2 . am)*(a1 a2 . am)=0. 故故a=0, 這與存在下原子這與存在下原子a及假設(shè)矛盾。因此及假設(shè)矛盾。因此 x* (a1 a2 . am)=0. . 故故x=a1 a2 . am676.7.6 布爾代數(shù)布爾代數(shù)(2) x= a1 a2 . am的下原子和表達(dá)式唯一的下原子和表達(dá)式唯一. 若還有若還有x=b1 b2 . bl, 式中式