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

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

2、下界,那么那么,就稱就稱為由格為由格所誘導(dǎo)的代數(shù)系統(tǒng)。二元運所誘導(dǎo)的代數(shù)系統(tǒng)。二元運算算和和分別稱為分別稱為并運算并運算和和交運算交運算。 通常用通常用ab 表示表示a,b的上確界的上確界,用用ab 表示表示a，b的下確界的下確界,和和分別稱為分別稱為保聯(lián)保聯(lián)(join)和和保交保交(meet)運算。由于對任何運算。由于對任何a，b，ab及及ab都是都是A 中確定中確定的成員，因此的成員，因此 ,均為均為A上的運算。上的運算。 定義定義15-1.3 設(shè)設(shè)是一個格是一個格, 由格由格所誘導(dǎo)所誘導(dǎo)的代數(shù)系統(tǒng)為的代數(shù)系統(tǒng)為 。設(shè)。設(shè)B A 且且B ，如果如果A中的兩個運算中的兩個運算和和 關(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)為 。其中其中為為集合的并運算和集合的并運算和為為集合的交運算。集合的交運算。 格對偶原理：格對偶原理：設(shè)設(shè)是一個偏序集是一個偏序集,在在A上定義一上定義一 個二元關(guān)系個二元關(guān)系 R,使得對于使得對于A中任意兩個元素中任意兩個元素a,b都有關(guān)系都有關(guān)系a Rb當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)b a,于是于是也是一個偏序集。把也是一個偏序集。把和和稱為相互對偶的稱為相互對偶的(哈斯圖相互顛倒哈斯圖相互顛倒)。 可以證明，若可以證明，若是格，則是格，則也是格。也是格。

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

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

6、定理15-1.3 在一個格在一個格中中,由格由格所誘導(dǎo)的代所誘導(dǎo)的代數(shù)系統(tǒng)為數(shù)系統(tǒng)為,則對于任意元素則對于任意元素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 ) 又因為又因為 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è)是一個偏序集，定義是一個偏序集，定義 ab =maxa,b （取大運算）取大運算） ab =min a,b （取小運算）取小運算）則則是一個格。由此格誘導(dǎo)的代數(shù)系統(tǒng)為是一個格。由此格誘導(dǎo)的代數(shù)系統(tǒng)為可以證明，該代數(shù)系統(tǒng)的兩個運算滿足可以證明，該代數(shù)系統(tǒng)的兩個運算滿足定理定理15-1.

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

9、一個格。 證明思路：證明思路：分四部分內(nèi)容來證明：分四部分內(nèi)容來證明： (1) 定義二元關(guān)系定義二元關(guān)系 ： a b當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (ab)=a (2) 證明是偏序關(guān)系（證：自反、反對稱和傳遞）證明是偏序關(guān)系（證：自反、反對稱和傳遞） ； (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)再對再對(1)式和式和(2)式應(yīng)用定理式應(yīng)用定理15-1.2得得 a(bc) (ab)(ac) 第第2式證明由對偶原理從上式直接可得。式證明由對偶原理從上式直接可得。 定理定理15-1.5 在一個格在一個格中中,對于任意的對于任意的a,b,c A, 都有：都有： a(bc) (ab)(ac) (ab)(ac) a(bc) 定理定理15-1.6 設(shè)設(shè)是一個格是一個格,那么，對于任意的那么，對于任意的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)系 的反對稱性得的反對稱性得 ： 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è)是一個格是一個格,那么，對于任意的那么，對于任意的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è)是一個格是一個格,那么，對于任意的那么，對于任意的a,b,c A, 都有：都有： (ab)(ac) a(b (ac) a(b (ac) ) (ab) (ac) 證明思路：第證明思路：第1式是式是 a(bc) (ab) (ac) 式的對偶。式的對偶。 第第2式是第式是第1式的對偶。式的對偶。 定義定義15

13、-1.4 設(shè)設(shè)和和是兩個格是兩個格,那那么么,由他們分別誘導(dǎo)的代數(shù)系統(tǒng)為由他們分別誘導(dǎo)的代數(shù)系統(tǒng)為和和 ，如果存在著一個從，如果存在著一個從A1到到A2的映射的映射f，使得對于任意的使得對于任意的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是雙射時，則稱是雙射時，則稱 f為從為從 到到 的格同構(gòu)，亦可稱的格同構(gòu)，亦可稱 和和 兩個格是同構(gòu)的兩個格是同構(gòu)的 。 證明思路：證明思路：因為因為x 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),則對于任意的則對于任意的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è)和和是是兩兩個格個格, f是從是從A1到到A2的雙射，則的雙射，則f是從是從到到的格同構(gòu)，當(dāng)且的格同構(gòu)，當(dāng)且僅當(dāng)對任意的僅當(dāng)對任意的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è)對任意的設(shè)對任意的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)。如果對任意的導(dǎo)的代數(shù)系統(tǒng)。如果對任意的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é)論： 是一個分配格。是一個分配格。 例例2：不是分配格的例子。：不是分配格的例子。 例例3：利用兩個：利用兩個“特殊五元素非分配格特殊五元素非分配格”的結(jié)論。的結(jié)論。 定理定理15-2.1 如果在一個分配格中交運算對于并運算可如果在一個分配格中交運算對于并運算可分配，則并運算對于交運算也一定是可分配的。反之亦然。分配，則并運算對于交運算也一定是可分配的。反之亦然。 證明證明定理的前半部分：定理的前半部分： 分配格中交對并可分配分配格中交對并可分配 并對交也一

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

19、 A，只要討論以下兩種情況：，只要討論以下兩種情況： （1） a b 或或 a c （2） b a 且且 c a 對于情況（對于情況（1），無論是），無論是b c還是還是c b ，都有，都有 a(bc)= a 和和 (ab)(ac)=a （a小）?。?對于情況（對于情況（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è)是分配，那么，對任意的是分配，那么，對任意的a,b,c A,如果滿足如果滿足:ab=ac和和ab=ac成立成立, 則必有

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

21、， ， 滿足：滿足： 且且 = 和和 = 證明證明：(1)先證：先證： 是模格是模格 有有 , , , ,使使 且且 = 和和 = (反設(shè)反設(shè)) 若存在上述若存在上述 , , , , 因為因為 , , 且且 ( ) )= ( ) )= (吸收律吸收律) ( ) ) =( ) ) = (吸收律吸收律) 比較上兩式，得比較上兩式，得 ( ) ) ( ) ) (根據(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 對于模格對于模格，若有三個元素，若有三個元素a,b,c，使得以下三式中的任意一式中把使得以下三式中的任意一式中把“ ”換為換為“=”成立，則成立，則另外兩個式子中把另外兩個式子中把“ ”換為換為“=”也成立。也成立。 a(bc) (ab )(ac) (1) (

23、ab)(ac) a(bc) (2) (ab)(bc)(ca) (ab)(bc)(ca) (3) 證明證明：設(shè)：設(shè)(1)成立，根據(jù)對偶律成立，根據(jù)對偶律(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 對于分配格必定是模格。對于分配格必定是模格。 證明證明：設(shè)：設(shè)是一個分配格，對于是一個分配格，對于A的任意元素的任意元素a,b,c，如果，如果 b a 則則 ab= b 。 因此因此 a(bc)= (ab)(bc) = b(ac) 6-3 有補格有補格 定義定義15-3.1 設(shè)設(shè)是一個格，如果存在元素是一個格，如果存在元素a A ,對對于任意的于任意的x A,都有都有a x,則為格的全下界則為格的全下界,記為記為“0”。 定理定理15-3.1 格格若有全下界若有全下界,則全下界是唯一的。則全下界是唯一的。 證明證明：用反證法：用反證法 如果有兩個不相等的全下界如果

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

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

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

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

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

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

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

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

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

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

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

36、因為b是是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 在一個布爾格在一個布爾格中中,對對A中中 任意一任意一個原子個原子a和另一個非零元素和另一個非零元素b，a b 和和a b兩式中有且兩式中有且僅有一式成立。僅有一式成立。 證明證明：(1)先證先證a b 和和a b兩式兩式不可能同時成立不可能同時成立 反設(shè)反設(shè)a b 和和a b同時成立，就有同時成立，就有a bb=0，這，這與與a是原子相矛盾，即是原子相矛盾，即a b 和和a b同時成立。同時成立。 (2)再證再證a b 和和a b兩式中兩式中必有一式成立必有一式成立 因為因為ab 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)的一個有限布爾代數(shù)，所誘導(dǎo)的一個有限布爾代數(shù)， S是布是布爾格中的所有原子的集合，則爾格中的所有原子的集合，則和和同構(gòu)。同構(gòu)。 證明證明：本定理的證明過程分三部分：本定理的證明過程分三部分 (1)構(gòu)造一個映射，并證明它是雙射（既是入射又是滿構(gòu)造一個映射，并證明它是雙射（既是入射又是滿射）；射）； (2)描述代數(shù)系統(tǒng)描述代數(shù)系統(tǒng)和和同構(gòu)并證明之；同構(gòu)并證明之； (3)總結(jié)概括

39、結(jié)論?？偨Y(jié)概括結(jié)論。 第第(1)部分部分證明：證明：對于任意對于任意a A,必有的唯一表示：必有的唯一表示： a=a1a2 ak （引理（引理15-4.2a的原子表示）的原子表示）其中其中ai a （i=1,2,k）,作映射作映射 f(a)=S1那么，這個映射是那么，這個映射是 一個從一個從A到到 (S)的一個雙射。的一個雙射。 第第1 1部分部分雙射證明：雙射證明： . . 對于全下界對于全下界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、一個從是一個從A到到 (S)的一個入射。的一個入射。 . .對于任一個對于任一個S1 (S)，若，若S1 =a1,a2 , ak，則由，則由于運算于運算的封閉性，所以的封閉性，所以 a1a2ak = a A這就說明這就說明 (S)中任一元素，必是中任一元素，必是A中某個元素的象，所以中某個元素的象，所以是一個從是一個從A到到 (S)的一個滿射。的一個滿射。 第第1 1部分部分雙射證明完畢。雙射證明完畢。 第第(2)部分部分證明：證明：和和同構(gòu)同構(gòu) 第第2 2部分部分同構(gòu)性格證明：同構(gòu)性格證明： . . 設(shè)設(shè) f(ab)=S3,若若x S3,則則x必是滿足必是滿足x ab的原的原子，因為子，因為

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，這是因為：，這是因為：

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, ,這是因為這是因為, ,若若x f(a), ,必有必有x a, ,則則由引理由引理6-4.4可知必有可知必有 x a, ,反之反之, ,若原子若原子x滿足滿足x a, ,則必則必有有x a, ,所以所以x f(a) 。 還可以證明還可以證明, ,對于原子對于原子x, ,x a當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x f(a), ,這是這是因為因為,

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), ,所以所以, ,對于對于原子原子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 有限布爾格的元素個數(shù)必定等于有限布爾格的元素個數(shù)必定等于2n，其

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

46、元布爾變元( (取值于取值于A A的變元的變元) )是布爾表達式，布是布爾表達式，布爾變元常用爾變元常用x x，y y，z z等符號表示。等符號表示。如果如果e e1 1, ,e e2 2為布爾表達式，那么為布爾表達式，那么( (e e1 1),(),(e e1 1ee2 2) ,() ,(e e1 1ee2 2) ) 也是布爾表達式。也是布爾表達式。除有限次使用條款（除有限次使用條款（2 2），（），（3 3）生成的表達式）生成的表達式是布爾表達式外，沒有別的是布爾表達式。是布爾表達式外，沒有別的是布爾表達式。 例例1 1 給出了兩個布爾函數(shù)的例子給出了兩個布爾函數(shù)的例子. . 例例2 2

47、給出了布爾表達式的例子給出了布爾表達式的例子。 定義定義15-5.2 15-5.2 一個含有一個含有n n個相異變元的布爾表達式，個相異變元的布爾表達式，稱為含有稱為含有n n元的布爾表達式，記為元的布爾表達式，記為E(xE(x1 1,x,x2 2,x,xn n) )，其中其中x x1 1,x,x2 2,x,xn n為為變元。變元。 定義定義15-5.3 15-5.3 布爾代數(shù)布爾代數(shù)A, 上的一個含有上的一個含有n n元的布爾表達式元的布爾表達式E(xE(x1 1,x,x2 2,x,xn n) )的值是指：將的值是指：將A A中的中的元素作為變元元素作為變元x xi i(i=1,2,n)(i

48、=1,2,n)的值來代替表達式中的值來代替表達式中相應(yīng)的變元（即對變元賦值）相應(yīng)的變元（即對變元賦值）, ,從而計算出表達式的值。從而計算出表達式的值。 定義定義15-5.4 15-5.4 布爾代數(shù)布爾代數(shù)A, 上兩個上兩個n n元的元的布爾表達式為布爾表達式為E E1 1(x(x1 1,x,x2 2,x,xn n) )和和E E2 2(x(x1 1,x,x2 2,x,xn n) ), ,如果對于個變元的任意賦值如果對于個變元的任意賦值x xi i=x=xi i, ,x xi i A時均有時均有 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) ) 則稱這兩個則稱這兩個布爾表達式布爾表達式是等價的。是等價的。 例例3 布爾代數(shù)布爾代數(shù)0,1, 上兩個上兩個3 3元的布爾表達元的布爾表達式為式為 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) ) 驗證這兩個布爾表達式是等價的。驗證這兩個布爾表達式是等價的。 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