第5篇ch15格與布爾代數(shù)

1、 第第1515章章 格格 與與 布布 爾爾 代代 數(shù)數(shù)15-1 15-1 格的概念格的概念 定義定義15-1.1 設(shè)設(shè)是一個(gè)偏序集，如果是一個(gè)偏序集，如果A中任意中任意兩個(gè)元素都有最小上界和最大下界，則稱兩個(gè)元素都有最小上界和最大下界，則稱為為格格（lattice）。）。 圖圖6-1.2所示的偏序集都是格。所示的偏序集都是格。 例例1 是格。是格。 例例2 是格。是格。 定義定義15-1.2 設(shè)設(shè)是一個(gè)格是一個(gè)格,如果在上定義兩個(gè)二如果在上定義兩個(gè)二元運(yùn)算元運(yùn)算和和 ,使得對(duì)于任意的使得對(duì)于任意的a,b A ， ab等于等于 a和和b的最小上界的最小上界, ab等于等于a和和b的最大下界的最大

2、下界,那么那么,就稱就稱為由格為由格所誘導(dǎo)的代數(shù)系統(tǒng)。二元運(yùn)所誘導(dǎo)的代數(shù)系統(tǒng)。二元運(yùn)算算和和分別稱為分別稱為并運(yùn)算并運(yùn)算和和交運(yùn)算交運(yùn)算。 通常用通常用ab 表示表示a,b的上確界的上確界,用用ab 表示表示a，b的下確界的下確界,和和分別稱為分別稱為保聯(lián)保聯(lián)(join)和和保交保交(meet)運(yùn)算。由于對(duì)任何運(yùn)算。由于對(duì)任何a，b，ab及及ab都是都是A 中確定中確定的成員，因此的成員，因此 ,均為均為A上的運(yùn)算。上的運(yùn)算。 定義定義15-1.3 設(shè)設(shè)是一個(gè)格是一個(gè)格, 由格由格所誘導(dǎo)所誘導(dǎo)的代數(shù)系統(tǒng)為的代數(shù)系統(tǒng)為 。設(shè)。設(shè)B A 且且B ，如果如果A中的兩個(gè)運(yùn)算中的兩個(gè)運(yùn)算和和 關(guān)于關(guān)于B

3、是封閉的，則稱是封閉的，則稱 是是的子格。的子格。 例例3 設(shè)設(shè)S=a,b ， (S) =, a,b,a,b由格由格誘導(dǎo)的代數(shù)系統(tǒng)為誘導(dǎo)的代數(shù)系統(tǒng)為 。其中其中為為集合的并運(yùn)算和集合的并運(yùn)算和為為集合的交運(yùn)算。集合的交運(yùn)算。 格對(duì)偶原理：格對(duì)偶原理：設(shè)設(shè)是一個(gè)偏序集是一個(gè)偏序集,在在A上定義一上定義一 個(gè)二元關(guān)系個(gè)二元關(guān)系 R,使得對(duì)于使得對(duì)于A中任意兩個(gè)元素中任意兩個(gè)元素a,b都有關(guān)系都有關(guān)系a Rb當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)b a,于是于是也是一個(gè)偏序集。把也是一個(gè)偏序集。把和和稱為相互對(duì)偶的稱為相互對(duì)偶的(哈斯圖相互顛倒哈斯圖相互顛倒)。 可以證明，若可以證明，若是格，則是格，則也是格。也是格。

4、稱稱 R是是 的逆關(guān)系。記為的逆關(guān)系。記為 。 格對(duì)偶原理可以敘述為：設(shè)格對(duì)偶原理可以敘述為：設(shè)P是對(duì)任意格都真的命題，是對(duì)任意格都真的命題，如果在命題如果在命題P中把中把 換成換成 ，換成換成，換成換成，就，就得到另一個(gè)命題得到另一個(gè)命題P，我們把，我們把P稱為稱為P的對(duì)偶命題，則的對(duì)偶命題，則P對(duì)任意格也是真的命題。對(duì)任意格也是真的命題。 定理定理15-1.1 在一個(gè)格在一個(gè)格中，對(duì)任意兩個(gè)元素中，對(duì)任意兩個(gè)元素a,b A都有都有 a ab b ab ab a ab b 證明思路：證明思路： 因?yàn)橐驗(yàn)閍和和b的并是的并是a的一個(gè)上界，所以的一個(gè)上界，所以 a ab 同理同理 b ab 有對(duì)

5、偶原理，即得有對(duì)偶原理，即得 ab a ab b 定理定理15-1.2 在一個(gè)格在一個(gè)格中，對(duì)于任意元素中，對(duì)于任意元素a,b,c,d A,如果如果 a b 和和 c d則則 ac bd ac bd 推論推論 在一個(gè)格在一個(gè)格中，對(duì)于任意元素中，對(duì)于任意元素a,b,c A,如如果果b c,則則 ab ac, ab ac(保序性保序性)。 證明思路：證明思路：因?yàn)橐驗(yàn)閎 bd和和d bd，所以由傳遞性，所以由傳遞性 a bd和和 c bd即即 bd是是a和和c的一個(gè)上界，而的一個(gè)上界，而ac是是a和和c的最小上界，的最小上界，所以，必有所以，必有 ac bd類似地證明類似地證明 ac bd 定理

6、定理15-1.3 在一個(gè)格在一個(gè)格中中,由格由格所誘導(dǎo)的代所誘導(dǎo)的代數(shù)系統(tǒng)為數(shù)系統(tǒng)為,則對(duì)于任意元素則對(duì)于任意元素a,b,c,d A,有有 (1) ab= ba ab= ba (2) a(bc)=(ab)c a(bc)=(ab)c (3) aa=a aa=a (4) a(ab)=a a(ab)=a（交換律）（交換律）（結(jié)合律）（結(jié)合律）（冪等律）（冪等律）（吸收律）（吸收律） 證明思路：證明思路：因（因（1）根據(jù)格的定義，）根據(jù)格的定義， a，b 。 （2）第一式：先證）第一式：先證(ab)c a(bc)根據(jù)定理根據(jù)定理1（x xy,y xy） b bc a(bc ) , a a(bc ) 根

7、據(jù)定理根據(jù)定理2（x1 x2且且y1 y2 x1y1 x2y2） ab a(bc ) 又因?yàn)橛忠驗(yàn)?c (bc ) a(bc ) 再根據(jù)定理再根據(jù)定理2 (ab)c a(bc ) 再證再證a(bc) (ab)c b ab, c c bc (ab)c a (ab) a(bc ) a(bc) a(bc ) 例例4 設(shè)設(shè)是一個(gè)偏序集，定義是一個(gè)偏序集，定義 ab =maxa,b （取大運(yùn)算）取大運(yùn)算） ab =min a,b （取小運(yùn)算）取小運(yùn)算）則則是一個(gè)格。由此格誘導(dǎo)的代數(shù)系統(tǒng)為是一個(gè)格。由此格誘導(dǎo)的代數(shù)系統(tǒng)為可以證明，該代數(shù)系統(tǒng)的兩個(gè)運(yùn)算滿足可以證明，該代數(shù)系統(tǒng)的兩個(gè)運(yùn)算滿足定理定理15-1.

8、3的的4個(gè)個(gè)運(yùn)算律運(yùn)算律。 引理引理15-1.1 設(shè)設(shè)是一個(gè)代數(shù)系統(tǒng)是一個(gè)代數(shù)系統(tǒng),其中其中,都是二元運(yùn)算且滿足吸收律，則都是二元運(yùn)算且滿足吸收律，則和和都滿足冪都滿足冪等律。等律。 證明思路：證明思路： 由吸收律：由吸收律： a(ab)=a (1) a(ab) =a (2) 將將(1)中的中的b取為取為(ab) ，得得 a(a(ab)=a再由得再由得 aa=a 同理可證同理可證 aa=a 定理定理15-1.4 設(shè)設(shè)是一個(gè)代數(shù)系統(tǒng)是一個(gè)代數(shù)系統(tǒng),其中其中,都是二元運(yùn)算且滿足交換律、結(jié)合律和吸收律，則都是二元運(yùn)算且滿足交換律、結(jié)合律和吸收律，則A上存在偏序關(guān)系上存在偏序關(guān)系 ，使，使是一個(gè)格。是

9、一個(gè)格。 證明思路：證明思路：分四部分內(nèi)容來(lái)證明：分四部分內(nèi)容來(lái)證明： (1) 定義二元關(guān)系定義二元關(guān)系 ： a b當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (ab)=a (2) 證明是偏序關(guān)系（證：自反、反對(duì)稱和傳遞）證明是偏序關(guān)系（證：自反、反對(duì)稱和傳遞） ； (3)證明證明ab是是a和和b的最大下界（下確界）；的最大下界（下確界）； (4)證明證明、滿足滿足交換律和吸收律。交換律和吸收律。 第第1式證明思路：式證明思路：由定理由定理15-1.1 a ab, a ac,再由定理再由定理15-1.2和冪等律得和冪等律得 a=aa (ab)(ac) (1)另外另外,由于由于 bc b ab 和和 bc c ac所以所

10、以 bc=bcbc (ab)(ac) (2)再對(duì)再對(duì)(1)式和式和(2)式應(yīng)用定理式應(yīng)用定理15-1.2得得 a(bc) (ab)(ac) 第第2式證明由對(duì)偶原理從上式直接可得。式證明由對(duì)偶原理從上式直接可得。 定理定理15-1.5 在一個(gè)格在一個(gè)格中中,對(duì)于任意的對(duì)于任意的a,b,c A, 都有：都有： a(bc) (ab)(ac) (ab)(ac) a(bc) 定理定理15-1.6 設(shè)設(shè)是一個(gè)格是一個(gè)格,那么，對(duì)于任意的那么，對(duì)于任意的a,b A, 都有：都有： a b(ab)=a(ab)=b a b(ab)證明思路：證明思路： (1)先證先證 a b (ab)=a 由由a b和和a a

11、，根據(jù)定理，根據(jù)定理15-1.2得得 a ab 又根據(jù)又根據(jù)ab的定義，的定義， 有有 ab a 由二元關(guān)系由二元關(guān)系 的反對(duì)稱性得的反對(duì)稱性得 ： ab = a (2) 再證再證 (ab)=a a b 設(shè)設(shè)ab=a，則，則a =ab b ，這就證明了，這就證明了 (ab)=a a b 綜合綜合(1)和和(2)得：得： a b(ab) 定理定理15-1.7 設(shè)設(shè)是一個(gè)格是一個(gè)格,那么，對(duì)于任意的那么，對(duì)于任意的a,b,c A, 都有：都有： a ca(bc) (ab)c 證明思路：證明思路： (1)先證先證 a c a(bc) (ab)c 根據(jù)定理根據(jù)定理15-1.6有有 a c (ac)=c

12、 根據(jù)定理根據(jù)定理15-1.5有有a(bc) (ab)(ac) a(bc) (ab)c (2) 再證再證 a(bc) (ab)c a c 若若 a(bc) (ab)c 則則 a a(bc) (ab)c c 即即 a c 綜合綜合(1)和和(2)得：得：a ca(bc) (ab)c 推論推論 設(shè)設(shè)是一個(gè)格是一個(gè)格,那么，對(duì)于任意的那么，對(duì)于任意的a,b,c A, 都有：都有： (ab)(ac) a(b (ac) a(b (ac) ) (ab) (ac) 證明思路：第證明思路：第1式是式是 a(bc) (ab) (ac) 式的對(duì)偶。式的對(duì)偶。 第第2式是第式是第1式的對(duì)偶。式的對(duì)偶。 定義定義15

13、-1.4 設(shè)設(shè)和和是兩個(gè)格是兩個(gè)格,那那么么,由他們分別誘導(dǎo)的代數(shù)系統(tǒng)為由他們分別誘導(dǎo)的代數(shù)系統(tǒng)為和和 ，如果存在著一個(gè)從，如果存在著一個(gè)從A1到到A2的映射的映射f，使得對(duì)于任意的使得對(duì)于任意的a,b A1 ，有，有 f(a1 b)= f(a)2 f(b) f(a 1 b)= f(a)2 f(b)則稱則稱 f為從為從 到到 的格同態(tài)，的格同態(tài)，亦可稱亦可稱 是是 的的 格同態(tài)象。此外，格同態(tài)象。此外，當(dāng)當(dāng) f是雙射時(shí)，則稱是雙射時(shí)，則稱 f為從為從 到到 的格同構(gòu)，亦可稱的格同構(gòu)，亦可稱 和和 兩個(gè)格是同構(gòu)的兩個(gè)格是同構(gòu)的 。 證明思路：證明思路：因?yàn)橐驗(yàn)閤 1y ，所以所以x1y=x f(

14、x1y) = f(x) f(x)2f(y) = f(x) 故故 f(x) 2f(y) 定理定理15-1.8 設(shè)設(shè)f是格是格和和是的格同態(tài)是的格同態(tài),則對(duì)于任意的則對(duì)于任意的x,y A1, 若若x 1y,必有必有:f(x) 2f(y) 。 例例7： f:S (S), x y=f(x)=y| y S, y x 定理定理15-1.9 設(shè)設(shè)和和是是兩兩個(gè)格個(gè)格, f是從是從A1到到A2的雙射，則的雙射，則f是從是從到到的格同構(gòu)，當(dāng)且的格同構(gòu)，當(dāng)且僅當(dāng)對(duì)任意的僅當(dāng)對(duì)任意的a,b A1, 都有：都有：a 1b f(a) 2f(b) 證明證明: (1) 先證先證f是是到到的格同構(gòu)的格同構(gòu) a 1bf(a)

15、2f(b) 由定理由定理15-1.8， 若若 a 1b, 必有必有: f(a) 2f(b) () 反之，設(shè)反之，設(shè) f(a) 2f(b) ， () 則則(格同構(gòu)大條件格同構(gòu)大條件) f(a)2f(b)= f(a1b)= f(a) 由于由于f是雙射，所以是雙射，所以 a1b=a 故故 ： a 1b (2) 再證再證 a 1bf(a) 2f(b) f是是到到的格同構(gòu)的格同構(gòu) 設(shè)對(duì)任意的設(shè)對(duì)任意的a,b A1, a 1bf(a) 2f(b) 設(shè)設(shè) a1b=c，則，則 c 1a, c 1b ， 于是于是 f(a1b)=f (c) ,f(c) 2f(a) , f(c) 2f(b) 故有故有 f(c) 2

16、f(a)2f(b) 令令 f(a)2f(b)=f(d) 則則 f(c) 2f(d) , f(d) 2f(a) , f(d) 2f(b) 故有故有 d 1a ，d 1b，于是，于是 d 1a1b ，即，即 d 1c， 所以所以 f(d) 2f(c) 因此因此 f(d)=f(c) 即即 f(a1b)=f(a)2f(b) 類似地可證：類似地可證： f(a1b)=f(a)2 f(b) 格同構(gòu)證畢。格同構(gòu)證畢。 定義定義15-2.1 設(shè)設(shè) 是由格是由格是所誘是所誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)任意的導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)任意的a,b,c A，滿足：，滿足： a(bc)= (ab)(ac) a(bc)= (ab)(a

17、c) 則稱則稱 是分配格是分配格 。15-2 分配格分配格 例例1： 集合：集合：S=a,b,c 格：格： 代數(shù)系統(tǒng)：代數(shù)系統(tǒng)： 結(jié)論：結(jié)論： 是一個(gè)分配格。是一個(gè)分配格。 例例2：不是分配格的例子。：不是分配格的例子。 例例3：利用兩個(gè)：利用兩個(gè)“特殊五元素非分配格特殊五元素非分配格”的結(jié)論。的結(jié)論。 定理定理15-2.1 如果在一個(gè)分配格中交運(yùn)算對(duì)于并運(yùn)算可如果在一個(gè)分配格中交運(yùn)算對(duì)于并運(yùn)算可分配，則并運(yùn)算對(duì)于交運(yùn)算也一定是可分配的。反之亦然。分配，則并運(yùn)算對(duì)于交運(yùn)算也一定是可分配的。反之亦然。 證明證明定理的前半部分：定理的前半部分： 分配格中交對(duì)并可分配分配格中交對(duì)并可分配 并對(duì)交也一

18、定可分配并對(duì)交也一定可分配設(shè)對(duì)任意的設(shè)對(duì)任意的a,b,c A，若若 a(bc)= (ab)(ac) (交對(duì)并可分配交對(duì)并可分配a)則則 (ab)(ac) =(ab)a)(ab)c) (交對(duì)并可分配交對(duì)并可分配(ab) =a(ab)c) (吸收律吸收律) =a(ac)(bc) (交對(duì)并可分配交對(duì)并可分配c) =(a (ac) )(bc) (結(jié)合律結(jié)合律) =a(bc) (吸收律吸收律) （并對(duì)交可分配）（并對(duì)交可分配） 定理定理15-2.2 每個(gè)鏈?zhǔn)欠峙涓?。每個(gè)鏈?zhǔn)欠峙涓瘛?證明證明 是鏈?zhǔn)擎?是分配格是分配格 設(shè)設(shè)是一個(gè)鏈，所以，是一個(gè)鏈，所以， 一定是格。一定是格。對(duì)任意的對(duì)任意的a,b,c

19、 A，只要討論以下兩種情況：，只要討論以下兩種情況： （1） a b 或或 a c （2） b a 且且 c a 對(duì)于情況（對(duì)于情況（1），無(wú)論是），無(wú)論是b c還是還是c b ，都有，都有 a(bc)= a 和和 (ab)(ac)=a （a?。┬。?對(duì)于情況（對(duì)于情況（2），總有），總有 bc a 所以所以 a(bc) = bc （a大）大）而由而由b a和和c a ，應(yīng)有，應(yīng)有(ab)(ac)=bc 故故a(bc)=(ab)(ac)成立。成立。 定理定理15-2.3 設(shè)設(shè)是分配，那么，對(duì)任意的是分配，那么，對(duì)任意的a,b,c A,如果滿足如果滿足:ab=ac和和ab=ac成立成立, 則必有

20、則必有 b=c 。 證明證明：因?yàn)椋阂驗(yàn)?(ab)c= (ac)c=c (吸收律吸收律) 而而 (ab)c=(ac)(bc)=(ab)(bc) = b(ac) (并對(duì)交可分配并對(duì)交可分配b) = b(ab) (ab=ac條件條件) =b (吸收律吸收律) b = c成立。成立。 定義定義15-2.2 設(shè)設(shè) 是由格是由格是所誘是所誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)任意的導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)任意的a,b,c A，當(dāng)，當(dāng)b a時(shí)，時(shí)，有：有： a(bc)= b(ac) 則稱則稱 是模格是模格 。 定理定理15-2.4 設(shè)設(shè)是模格，當(dāng)且僅當(dāng)在中不含是模格，當(dāng)且僅當(dāng)在中不含有適合下述條件的元素有適合下述條件的元素

21、， ， 滿足：滿足： 且且 = 和和 = 證明證明：(1)先證：先證： 是模格是模格 有有 , , , ,使使 且且 = 和和 = (反設(shè)反設(shè)) 若存在上述若存在上述 , , , , 因?yàn)橐驗(yàn)?, , 且且 ( ) )= ( ) )= (吸收律吸收律) ( ) ) =( ) ) = (吸收律吸收律) 比較上兩式，得比較上兩式，得 ( ) ) ( ) ) (根據(jù)根據(jù) ) 所以所以 不是模格。不是模格。 (出現(xiàn)矛盾出現(xiàn)矛盾) (2) 再證：有再證：有 , , , ,使使 且且 = 和和 = 是模格是模格 (反設(shè)反設(shè)) 若若不不是模格，則有是模格，則有a,b,c滿足：滿足： b b a 且且 b(c

22、a) (bc)a 令令 = =b(ca) = (bc)a = =c有有 = =(bc)ac= a(bc)c) = =ac= acc 因此因此 (ac b(ca)= ) 另外另外, ,由于由于(條件條件) , ,故有故有 ,所以所以: = 同理可證同理可證 = 。 (3)綜合綜合(1)和和 (2)得到結(jié)論。得到結(jié)論。 定理定理15-2.5 對(duì)于模格對(duì)于模格，若有三個(gè)元素，若有三個(gè)元素a,b,c，使得以下三式中的任意一式中把使得以下三式中的任意一式中把“ ”換為換為“=”成立，則成立，則另外兩個(gè)式子中把另外兩個(gè)式子中把“ ”換為換為“=”也成立。也成立。 a(bc) (ab )(ac) (1) (

23、ab)(ac) a(bc) (2) (ab)(bc)(ca) (ab)(bc)(ca) (3) 證明證明：設(shè)：設(shè)(1)成立，根據(jù)對(duì)偶律成立，根據(jù)對(duì)偶律(2)也成立。也成立。 只需先證明：只需先證明： (1)成立且成立且(2)成立成立 (3)也成立也成立 (3)式右端式右端= (ab)(bc)(ca)=(ac)b) (ca) =(ca) b)(ac) ( (分配分配(ca) ) = (ab)(bc)(ca) = (3)式左端式左端 ( (分配分配b) ) 再證明：再證明： (3)也成立也成立 (1)成立且成立且(2)成立成立 (1)左端左端= a(bc)=利用利用(3)式推導(dǎo)式推導(dǎo)= (1)右端

24、右端。 定理定理15-2.6 對(duì)于分配格必定是模格。對(duì)于分配格必定是模格。 證明證明：設(shè)：設(shè)是一個(gè)分配格，對(duì)于是一個(gè)分配格，對(duì)于A的任意元素的任意元素a,b,c，如果，如果 b a 則則 ab= b 。 因此因此 a(bc)= (ab)(bc) = b(ac) 6-3 有補(bǔ)格有補(bǔ)格 定義定義15-3.1 設(shè)設(shè)是一個(gè)格，如果存在元素是一個(gè)格，如果存在元素a A ,對(duì)對(duì)于任意的于任意的x A,都有都有a x,則為格的全下界則為格的全下界,記為記為“0”。 定理定理15-3.1 格格若有全下界若有全下界,則全下界是唯一的。則全下界是唯一的。 證明證明：用反證法：用反證法 如果有兩個(gè)不相等的全下界如果

25、有兩個(gè)不相等的全下界a和和b，a,b A 且且ba 因?yàn)橐驗(yàn)?a 是全下界，是全下界， b A ，所以，所以 a b 又因?yàn)橛忠驗(yàn)?b 是全下界，是全下界， a A ，所以，所以 b a 由此得由此得 a=b 與有兩個(gè)不相等的全下界與有兩個(gè)不相等的全下界a和和b 矛盾。矛盾。 定義定義15-3.2 設(shè)設(shè)是一個(gè)格，如果存在元素是一個(gè)格，如果存在元素b A,對(duì)對(duì)于任意的于任意的x A,都有都有x b,則為格的全上界則為格的全上界,記為記為“1”。 證明證明：用反證法：用反證法 如果有兩個(gè)不相等的全上界如果有兩個(gè)不相等的全上界a和和b ，a,b A 且且ba 因?yàn)橐驗(yàn)?a 是全上界，是全上界， b

26、A ，所以，所以 b a 又因?yàn)橛忠驗(yàn)?b 是全上界，是全上界， a A ，所以，所以 a b 由此得由此得 a=b 與有兩個(gè)不相等的全上界與有兩個(gè)不相等的全上界a和和b 矛盾。矛盾。 定理定理15-3.2 格格若有全上界若有全上界,則全下界是唯一的。則全下界是唯一的。 定義定義15-3.3 設(shè)設(shè)是一個(gè)格，如果存在全下界和全是一個(gè)格，如果存在全下界和全上界，則稱該格為有界格。上界，則稱該格為有界格。 定理定理15-3.3 設(shè)設(shè)是一個(gè)有界格，則對(duì)于任意的是一個(gè)有界格，則對(duì)于任意的a A,都有都有 a1=1 a1=a (1是是運(yùn)算的零元運(yùn)算的零元,運(yùn)算的幺元運(yùn)算的幺元) a0=a a0=0 (0是

27、是運(yùn)算的幺元運(yùn)算的幺元,運(yùn)算的零元運(yùn)算的零元) 證明證明：(1) 證證 a1=1 因?yàn)橐驗(yàn)?a1 A且且1是全上界，所以是全上界，所以 a1 1 又因?yàn)橛忠驗(yàn)?1 a1，所以，所以 a1=1 (2) 證證 a1=a 因?yàn)橐驗(yàn)?a a， a 1, 所以所以 a a1 又因?yàn)橛忠驗(yàn)?a1 a， 所以所以 a1=a (3) 證證a0=a (略略) (4) 證證a0=0 (略略) 定義定義15-3.4 設(shè)設(shè)是一個(gè)有界格，對(duì)于是一個(gè)有界格，對(duì)于A中任意的中任意的a,如果存在如果存在b A ，使得，使得ab=1和和ab=0 ，則稱元素，則稱元素b是是元素元素a的的補(bǔ)元補(bǔ)元。此時(shí)稱。此時(shí)稱a和和b是是互補(bǔ)的

28、互補(bǔ)的。 定義定義15-3.5 在一個(gè)有界格中，如果每個(gè)元素都至少有在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元素，則稱此格為一個(gè)補(bǔ)元素，則稱此格為有補(bǔ)格有補(bǔ)格。 定理定理15-3.4 在一個(gè)有界分配格中，如果有一個(gè)元素在一個(gè)有界分配格中，如果有一個(gè)元素有補(bǔ)元素，則必是唯一的。有補(bǔ)元素，則必是唯一的。 證明證明：設(shè)：設(shè) a有兩個(gè)補(bǔ)元素有兩個(gè)補(bǔ)元素b和和c，即有，即有 ab=1 和和 ab=0 ac=1 和和 ac=0 由定理由定理15-2.3即得即得 b=c 定義定義15-3.6 一個(gè)格如果如果它即是有補(bǔ)格，又是分配一個(gè)格如果如果它即是有補(bǔ)格，又是分配格，則稱此格為格，則稱此格為有補(bǔ)分配格有補(bǔ)

29、分配格。一般把任一元素。一般把任一元素a的唯的唯一補(bǔ)元記為一補(bǔ)元記為 a (或或a- )。 15-4 15-4 布爾代數(shù)布爾代數(shù) 定義定義15-4.1 代一個(gè)有補(bǔ)分配格稱為代一個(gè)有補(bǔ)分配格稱為布爾格布爾格。 求一個(gè)元素的補(bǔ)元素可以看作一元運(yùn)算，稱為補(bǔ)運(yùn)算。求一個(gè)元素的補(bǔ)元素可以看作一元運(yùn)算，稱為補(bǔ)運(yùn)算。 定義定義15-4.2 設(shè)設(shè) 是由布爾格是由布爾格是所誘導(dǎo)的代數(shù)系統(tǒng)。稱這個(gè)代數(shù)系統(tǒng)為是所誘導(dǎo)的代數(shù)系統(tǒng)。稱這個(gè)代數(shù)系統(tǒng)為布爾代數(shù)布爾代數(shù)。 例例1 設(shè)設(shè)是由布爾格是由布爾格是所誘導(dǎo)的代數(shù)系統(tǒng)。這個(gè)代數(shù)系統(tǒng)為是所誘導(dǎo)的代數(shù)系統(tǒng)。這個(gè)代數(shù)系統(tǒng)為布爾代數(shù)布爾代數(shù)。 定理定理15-4.1 在一個(gè)有界分

30、配格中，對(duì)于布爾代數(shù)中在一個(gè)有界分配格中，對(duì)于布爾代數(shù)中的任意兩個(gè)元素的任意兩個(gè)元素a，b，必定有，必定有 ( a )=a ab= ab ab= ab 證明證明：只證第：只證第(2)個(gè)等式個(gè)等式 先證互補(bǔ)的兩個(gè)式子先證互補(bǔ)的兩個(gè)式子相并相并等于全上界等于全上界“1”。 (ab)(ab)= (ab)a)(ab)b) =(b(aa)(a(bb) =(b1)(a1) =1 再證互補(bǔ)的兩個(gè)式子再證互補(bǔ)的兩個(gè)式子相交相交等于全下界等于全下界“0”。 (ab)(ab)= 0 定義定義15-4.3 具有有限個(gè)元素的布爾代數(shù)稱為具有有限個(gè)元素的布爾代數(shù)稱為有限有限布爾代數(shù)布爾代數(shù)。 定義定義15-4.4 設(shè)設(shè)

31、和和是兩是兩個(gè)布爾代數(shù)個(gè)布爾代數(shù),如果存在著如果存在著A到到B的雙射的雙射f,對(duì)于任意的對(duì)于任意的a,b A,都有都有 f(ab)=f(a)f(b) f(ab)=f(a)f(b) f(a)=f(a)則稱則稱和和同構(gòu)同構(gòu)。 可以證明可以證明,對(duì)于每一正整數(shù)對(duì)于每一正整數(shù)n,必存在著必存在著2n個(gè)元素的布個(gè)元素的布爾代數(shù)爾代數(shù);反之反之,任一有限布爾代數(shù)任一有限布爾代數(shù),它的元素個(gè)數(shù)必為它的元素個(gè)數(shù)必為2的冪的冪次。次。 定義定義15-4.5 設(shè)設(shè) 是一個(gè)格，且具有全下界是一個(gè)格，且具有全下界0，如果有元素如果有元素a蓋住蓋住0，則稱元素，則稱元素a為原子。為原子。 原子：與原子：與0相鄰且比相鄰

32、且比0“大大” 定理定理15-4.2 設(shè)設(shè) 是一個(gè)具有全下界是一個(gè)具有全下界0的有限的有限格，則對(duì)于任何一個(gè)非零元素格，則對(duì)于任何一個(gè)非零元素b（即不等于全下界（即不等于全下界0的元的元素）至少存在一個(gè)原子素）至少存在一個(gè)原子a ，使得，使得a b 。 證明證明：若：若b是原子，則有是原子，則有b b ，若，若b不是原子，則必不是原子，則必有有b1存在，使得存在，使得0 b1 b 若若b1是原子，則定理得證，否則，必存在是原子，則定理得證，否則，必存在b2使得使得 0 b2 b1 b 由于是一個(gè)有下界的有限格，所以通過有限不驟總可由于是一個(gè)有下界的有限格，所以通過有限不驟總可以找到一個(gè)原子以找

33、到一個(gè)原子bi ，使得，使得0 bi . b2 b1 b 引理引理15-4.1 設(shè)在一個(gè)布爾格中設(shè)在一個(gè)布爾格中,bc=0當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)b c。 證明證明：(1)先證先證 bc=0 b c 若若 bc=0， 因?yàn)橐驗(yàn)?0c=c ， 則則 (bc)c=c 根據(jù)分配性，就有根據(jù)分配性，就有 (bc) (cc) =c 即即 (bc) 1 =c 所以所以 bc =c 又因?yàn)橛忠驗(yàn)?b bc 所以所以 b c (2)再證再證 b c bc=0 若若b c, ,則則bc cc, ,即即bc 0 0，所以所以bc=0 引理引理15-4.2 設(shè)設(shè)是一個(gè)有限布爾代數(shù)是一個(gè)有限布爾代數(shù),若若b是是A中中 任意非

34、零元素，任意非零元素， a1, a2, , ak是是A中滿足中滿足aj b 的所有原子（的所有原子（j=1,2,k） ,則則 b = a1a2ak 證明證明：(1)先證先證 a1a2ak b 記記a1a2ak =c,因?yàn)橐驗(yàn)閍j b,所以所以c b。 (2)再證再證 b a1a2ak 由引理由引理6-4.1知知,要證要證b c若是原子若是原子,只需證只需證bc=0, 反設(shè)反設(shè)bc0,于是必有一個(gè)原子于是必有一個(gè)原子a,使得使得a bc。 又因又因bc b,和和 bc c, 所以所以 a b 和和 a c , 因?yàn)橐驗(yàn)閍是原子是原子,且且a b,所以所以a必是必是a1, a2, , ak中的一中

35、的一 個(gè)個(gè),因此因此 a c,已有已有a c,得得a cc,即即a 0, 與與a是原子矛是原子矛盾。盾。 bc0假設(shè)不成立假設(shè)不成立 。綜合。綜合(1)和和(2)定理得證。定理得證。 引理引理15-4.3 設(shè)設(shè)是一個(gè)有限布爾代數(shù)是一個(gè)有限布爾代數(shù),若若b是是A中中 任意非零元素，任意非零元素， a1, a2, ,ak是是A中滿足中滿足aj b的的所有原子（所有原子（j=1,2,k） ,則則b = a1a2ak是將是將b表示表示為原子之并的唯一形式。為原子之并的唯一形式。 證明證明:設(shè)有另一種表示形式為設(shè)有另一種表示形式為b=aj1aj1ajt 其中其中aj1,aj1,ajt是原子。因?yàn)槭窃印?/p>

36、因?yàn)閎是是aj1,aj1,ajt的最小上的最小上界界,所以必有所以必有aj1 b, aj2 b,., ajt b。而。而a1, a2, , ak是是A中中所有滿足所有滿足ai b （i=1,2,k）的不同原子。）的不同原子。 所以必有所以必有 tk 反設(shè)反設(shè)t k,那么在那么在a1, a2, , ak中必有中必有aj0且且aj0ajl 于是于是,由由aj0(aj1aj1ajt)= aj0(a1a2ak)即即 (aj0aj1) (aj0aj2) (aj0 ajt) = (aj0a1) (aj0a2) (aj0 ak)導(dǎo)致的導(dǎo)致的0= aj0矛盾。矛盾。t k假設(shè)不成立假設(shè)不成立 。 T= =k定

37、理得證。定理得證。 引理引理15-4.4 在一個(gè)布爾格在一個(gè)布爾格中中,對(duì)對(duì)A中中 任意一任意一個(gè)原子個(gè)原子a和另一個(gè)非零元素和另一個(gè)非零元素b，a b 和和a b兩式中有且兩式中有且僅有一式成立。僅有一式成立。 證明證明：(1)先證先證a b 和和a b兩式兩式不可能同時(shí)成立不可能同時(shí)成立 反設(shè)反設(shè)a b 和和a b同時(shí)成立，就有同時(shí)成立，就有a bb=0，這，這與與a是原子相矛盾，即是原子相矛盾，即a b 和和a b同時(shí)成立。同時(shí)成立。 (2)再證再證a b 和和a b兩式中兩式中必有一式成立必有一式成立 因?yàn)橐驗(yàn)閍b a, a是原子是原子,所以只能是所以只能是 ab=0 或或 ab=a

38、若若ab=0，則，則 a(b) =0 ，由引理，由引理6-4.1得得 a b； 若若ab=a,由引理由引理6-1.6得得a b。 定理定理15-4.3(Stone 表示定理表示定理) 設(shè)設(shè) 是由是由有限布爾格有限布爾格所誘導(dǎo)的一個(gè)有限布爾代數(shù)，所誘導(dǎo)的一個(gè)有限布爾代數(shù)， S是布是布爾格中的所有原子的集合，則爾格中的所有原子的集合，則和和同構(gòu)。同構(gòu)。 證明證明：本定理的證明過程分三部分：本定理的證明過程分三部分 (1)構(gòu)造一個(gè)映射，并證明它是雙射（既是入射又是滿構(gòu)造一個(gè)映射，并證明它是雙射（既是入射又是滿射）；射）； (2)描述代數(shù)系統(tǒng)描述代數(shù)系統(tǒng)和和同構(gòu)并證明之；同構(gòu)并證明之； (3)總結(jié)概括

39、結(jié)論?？偨Y(jié)概括結(jié)論。 第第(1)部分部分證明：證明：對(duì)于任意對(duì)于任意a A,必有的唯一表示：必有的唯一表示： a=a1a2 ak （引理（引理15-4.2a的原子表示）的原子表示）其中其中ai a （i=1,2,k）,作映射作映射 f(a)=S1那么，這個(gè)映射是那么，這個(gè)映射是 一個(gè)從一個(gè)從A到到 (S)的一個(gè)雙射。的一個(gè)雙射。 第第1 1部分部分雙射證明：雙射證明： . . 對(duì)于全下界對(duì)于全下界0 A，規(guī)定，規(guī)定 f(0)= 。 . .如果如果 S1 =a1,a2 , ak (S)，而有，而有a,b A,使得使得 f(a)= f(a)=S1 ，則則a=a1a2 ak = b， 所以所以 f是

40、一個(gè)從是一個(gè)從A到到 (S)的一個(gè)入射。的一個(gè)入射。 . .對(duì)于任一個(gè)對(duì)于任一個(gè)S1 (S)，若，若S1 =a1,a2 , ak，則由，則由于運(yùn)算于運(yùn)算的封閉性，所以的封閉性，所以 a1a2ak = a A這就說(shuō)明這就說(shuō)明 (S)中任一元素，必是中任一元素，必是A中某個(gè)元素的象，所以中某個(gè)元素的象，所以是一個(gè)從是一個(gè)從A到到 (S)的一個(gè)滿射。的一個(gè)滿射。 第第1 1部分部分雙射證明完畢。雙射證明完畢。 第第(2)部分部分證明：證明：和和同構(gòu)同構(gòu) 第第2 2部分部分同構(gòu)性格證明：同構(gòu)性格證明： . . 設(shè)設(shè) f(ab)=S3,若若x S3,則則x必是滿足必是滿足x ab的原的原子，因?yàn)樽?，因?yàn)?/p>

41、ab a和和ab b，所以，所以x a且且x b，推得，推得x S1且且x S2，即，即x S1S2 ，這就證得，這就證得S3 S1S2 。 反之反之,若若x S1S2,則則x S1且且x S2,所以所以x必是滿足必是滿足x a和和x b的原子的原子,推得推得x必是滿足必是滿足x ab的原子的原子,所以所以x S3,這這就證明了就證明了 S1S2 S3 。 綜上所述，就有綜上所述，就有S3 = = S1S2 ，即，即 f(ab)= f(a)f(b) . . 設(shè)設(shè) f(ab)=S3,若若x S3,則則x是滿足是滿足x ab的原的原子，所以必有子，所以必有x a或或x b，這是因?yàn)椋海@是因?yàn)椋?

42、若若x a且且x b,則由引理則由引理6-4.4可知必有可知必有 x a且且x b,所所以以x ab= ab 。再由條件。再由條件x ab,便得便得 x (ab)(ab)=0這與這與x是原子相矛盾。是原子相矛盾。因此，若因此，若x a則則x S1或者若或者若x b則則x S2 ，所以，所以 x S1S2 這就證明了這就證明了S3 S1S2 。 反之反之,若若x S1S2, 則則x S1或或x S2,若若x S1，則，則 x a ab所以所以x S3,同理，若同理，若x S2，則，則 x b ab所以所以x S3,這就證明了這就證明了 S1S2 S3 。 綜上所述，就有綜上所述，就有S3 = =

43、 S1S2 ，即，即 f(ab)= f(a)f(b) . .最后證明同構(gòu)性的最后證明同構(gòu)性的f(a)= f(a)式：式： 將將S看作全集看作全集, ,另另f(a)=S1, ,則則f(a)=S-S1=S-f(a), ,可以證可以證明明x f(a)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x a, ,這是因?yàn)檫@是因?yàn)? ,若若x f(a), ,必有必有x a, ,則則由引理由引理6-4.4可知必有可知必有 x a, ,反之反之, ,若原子若原子x滿足滿足x a, ,則必則必有有x a, ,所以所以x f(a) 。 還可以證明還可以證明, ,對(duì)于原子對(duì)于原子x, ,x a當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x f(a), ,這是這是因?yàn)橐驗(yàn)?

44、,若若x a而而x f(a), ,將導(dǎo)致將導(dǎo)致x a的矛盾的矛盾, ,所以所以x f(a), ,反反之之, ,若若x f(a)而而x a, ,也將導(dǎo)致也將導(dǎo)致x f(a)的矛盾的矛盾, ,所以所以x a 。 另外還可以證明另外還可以證明, , x f(a)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x f(a), ,所以所以, ,對(duì)于對(duì)于原子原子x, , x f(a)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x f(a), ,因此因此, , f(a)=f(a) 第第2 2部分部分同構(gòu)性證明完畢。同構(gòu)性證明完畢。 (3)總結(jié)概括結(jié)論總結(jié)概括結(jié)論:和和同構(gòu)。同構(gòu)。 推論推論15-4.1 有限布爾格的元素個(gè)數(shù)必定等于有限布爾格的元素個(gè)數(shù)必定等于2n，其

45、中，其中n是該布爾格中所有原子的個(gè)數(shù)。是該布爾格中所有原子的個(gè)數(shù)。 推論推論15-4.2 任何一個(gè)具有任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)個(gè)元素的有限布爾代數(shù)都是同構(gòu)的。都是同構(gòu)的。15-5 布爾表達(dá)式布爾表達(dá)式 定義定義15-5.115-5.1 設(shè)設(shè)A, 為布爾代數(shù)為布爾代數(shù), ,如下遞歸如下遞歸地定義地定義A A上上布爾表達(dá)式布爾表達(dá)式( (Boolean expressionsBoolean expressions) )：布爾常元布爾常元( (取值于取值于A A的常元的常元) )是布爾表達(dá)式是布爾表達(dá)式, ,布爾布爾常元常用常元常用a a, ,b b，c c等符號(hào)表示。等符號(hào)表示。布爾變

46、元布爾變?cè)? (取值于取值于A A的變?cè)淖冊(cè)? )是布爾表達(dá)式，布是布爾表達(dá)式，布爾變?cè)Ｓ脿栕冊(cè)Ｓ脁 x，y y，z z等符號(hào)表示。等符號(hào)表示。如果如果e e1 1, ,e e2 2為布爾表達(dá)式，那么為布爾表達(dá)式，那么( (e e1 1),(),(e e1 1ee2 2) ,() ,(e e1 1ee2 2) ) 也是布爾表達(dá)式。也是布爾表達(dá)式。除有限次使用條款（除有限次使用條款（2 2），（），（3 3）生成的表達(dá)式）生成的表達(dá)式是布爾表達(dá)式外，沒有別的是布爾表達(dá)式。是布爾表達(dá)式外，沒有別的是布爾表達(dá)式。 例例1 1 給出了兩個(gè)布爾函數(shù)的例子給出了兩個(gè)布爾函數(shù)的例子. . 例例2 2

47、給出了布爾表達(dá)式的例子給出了布爾表達(dá)式的例子。 定義定義15-5.2 15-5.2 一個(gè)含有一個(gè)含有n n個(gè)相異變?cè)牟紶柋磉_(dá)式，個(gè)相異變?cè)牟紶柋磉_(dá)式，稱為含有稱為含有n n元的布爾表達(dá)式，記為元的布爾表達(dá)式，記為E(xE(x1 1,x,x2 2,x,xn n) )，其中其中x x1 1,x,x2 2,x,xn n為為變?cè)?。變?cè)?定義定義15-5.3 15-5.3 布爾代數(shù)布爾代數(shù)A, 上的一個(gè)含有上的一個(gè)含有n n元的布爾表達(dá)式元的布爾表達(dá)式E(xE(x1 1,x,x2 2,x,xn n) )的值是指：將的值是指：將A A中的中的元素作為變?cè)刈鳛樽冊(cè)獂 xi i(i=1,2,n)(i

48、=1,2,n)的值來(lái)代替表達(dá)式中的值來(lái)代替表達(dá)式中相應(yīng)的變?cè)磳?duì)變?cè)x值）相應(yīng)的變?cè)磳?duì)變?cè)x值）, ,從而計(jì)算出表達(dá)式的值。從而計(jì)算出表達(dá)式的值。 定義定義15-5.4 15-5.4 布爾代數(shù)布爾代數(shù)A, 上兩個(gè)上兩個(gè)n n元的元的布爾表達(dá)式為布爾表達(dá)式為E E1 1(x(x1 1,x,x2 2,x,xn n) )和和E E2 2(x(x1 1,x,x2 2,x,xn n) ), ,如果對(duì)于個(gè)變?cè)娜我赓x值如果對(duì)于個(gè)變?cè)娜我赓x值x xi i=x=xi i, ,x xi i A時(shí)均有時(shí)均有 E E1 1(x(x1 1,x,x2 2,x,xn n)=E)=E2 2(x(x1 1,x,x2

49、2,x,xn n) ) 則稱這兩個(gè)則稱這兩個(gè)布爾表達(dá)式布爾表達(dá)式是等價(jià)的。是等價(jià)的。 例例3 布爾代數(shù)布爾代數(shù)0,1, 上兩個(gè)上兩個(gè)3 3元的布爾表達(dá)元的布爾表達(dá)式為式為 E E1 1(x(x1 1,x,x2 2,x,x3 3)=(x)=(x1 1xx2 2)(x)(x1 1xx3 3) ) 和和 E E2 2(x(x1 1,x,x2 2,x,x3 3)=x)=x1 1(x(x2 2xx3 3) ) 驗(yàn)證這兩個(gè)布爾表達(dá)式是等價(jià)的。驗(yàn)證這兩個(gè)布爾表達(dá)式是等價(jià)的。 E E1 1(0,1,1)=(01)(00)=0(0,1,1)=(01)(00)=0 E E2 2(0,1,1)=0(10)=0(0,1,1)=0(10)=0 E E1 1(1,1,1)=(11)(10)=1(1,1,1)=(11)(10)=1 E E2 2(1,1,1)=1(10)=1(1,1,1)=1(10)=1 E E1 1(0,0,0)=(00)(01)=0(0,0,0)=(00)(01)=0 E