離散數(shù)學課件第6章

1、《離散數(shù)學》教案,計算機科學與技術學院課程學時：64主 講：宋 成,河南理工大學電子教案,第六章：格和布爾代數(shù),§6.1 格的概念§6.2 分配格§6.3 有補格§6.4* 布爾代數(shù),第六章：格和布爾代數(shù),教學目的及要求： 深刻理解和掌握格與布爾代數(shù)的基本概念和基本運算教學類容： 格的概念、有補格，分配格、布爾代數(shù)和布爾表達式。教學重點： 格、布爾代數(shù)和布

2、爾表達式。教學難點： 布爾代數(shù)和布爾表達式。,§6.1 格的概念【定義6.1.1】 設?X,??是偏序集，如果?x,y?X，集合?x,y?都有最小上界和最大下界，則稱?X,??是格。【例6.1】設S12＝?1,2,3,4,6,12?是12的因子構成的集合。其上的整除關系R=??x,y?| x?S12∧y?S12∧x整除y?，R是S12上的偏序關系，?S12,R?是偏序集。寫出S12上的蓋住關系COV S12，畫出哈

3、斯圖，驗證偏序集?S12,R?是格。 解：S12上的蓋住關系 COV S12＝??1,2?,?1,3?,?2,4?,?2,6?,?3,6?, ?4,12?,?6,12??，哈斯圖如圖6.1所示。從哈斯圖中可看出，集合S12的任意兩個元素都有最小上界和最大下界，故偏序集?S12,R?是格。,第六章：格和布爾代數(shù),第六章：格和布爾代數(shù),【例6.2

4、】圖8.2中給出了一些偏序集的哈斯圖，判斷它們是否構成格。 解：它們都不是格。在(a)中，?1,2?沒有下界，因而沒有最大下界。在(b)中，?2,4?雖有兩個上界，但沒有最小上界。在(c)中，?1,3?沒有下界，因而沒有最大下界。在(d)中，?2,3?雖有三個上界，但沒有最小上界。,第六章：格和布爾代數(shù),,設?X,??是格，?x,y?X，今后用x∨y表示集合?x,y?的最小上界，二元運算∨稱為并運算；用x∧y表示集合?x

5、,y?的最大下界，二元運算∧稱為交運算。 【定義6.1.2】 設?X,??是格，∨是X上的并運算，∧是X上的交運算。則稱?X,∨,∧?是格?X,??導出的代數(shù)系統(tǒng)。 ?x,y?P (A)，x∨y=x∪y，x∧y=x∩y。這樣，格?P (A),R??導出的代數(shù)系統(tǒng)?P (A),∨,∧?實際就是代數(shù)系統(tǒng)?P (A),∪,∩?，所以，二元運算∨和∧的運算表如表6.1和表6.2所示。 在例6.1中，根據圖6.1，集合?4,

6、6?的最小上界為12，即4∨6=12=4和6的最小公倍數(shù)；它的最大下界為2，即4∧6=2=4和6的最大公約數(shù)。同樣，這個結果也可以推廣到一般情況。即在格?S12,R?導出的代數(shù)系統(tǒng)?S12,∨,∧?中，二元運算∨是求最小公倍數(shù)；二元運算∧是求最大公約數(shù)。,第六章：格和布爾代數(shù),表6. 1,,,,,,表6. 2,第六章：格和布爾代數(shù),,定義6.1.3 設f是含有格中元素以及符號=,?,?,∨和∧的命題。將f中的?替換成?，?替換成?，∨替

7、換成∧，∧替換成∨，得到一個新命題，所得的命題叫做f的對偶命題，記為f *。　　　　 例如，在格中，f為a∧(b∨c)?a，則f的對偶命題f *為a∨(b∧c)?a 命題f和它的對偶命題f *遵循下列的規(guī)則，這規(guī)則叫做格的對偶原理。 設f是含有格中元素以及符號=,?,?,∨和∧的命題。 若f對一切格為真，則f的對偶命題f *也對一切格為真。 格的許多性質都是互為對偶命題的。有

8、了格的對偶原理，在證明格的性質時，只需證明其中的一個就可以了。,第六章：格和布爾代數(shù),【定理6.1.1】 設?X,??是格，?X,∨,∧?是格?X,??導出的代數(shù)系統(tǒng)。則?a,b,c?X有 ⑴ a∨b=b∨a， a∧b=b∧a (交換律) ⑵ (a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c) (結合律) ⑶ a∨a=

9、 a， a∧a= a (冪等律) ⑷ a∨(a∧b)=a a∧(a∨b)=a (吸收律) 證明：⑴?a,b?X，?a,b?=?b,a?，所以它們的最小上界相等。即a∨b=b∨a，同理可證a∧b=b∧a ⑵ a和b的最大下界一定是a、b的下界，即a∧b?a，同理，(a∧b)∧

10、c?a∧b，所以，(a∧b)∧c?a∧b?a 同理有 (a∧b)∧c?a∧b?b 和 (a∧b)∧c?c,第六章：格和布爾代數(shù),由以上3式得 (a∧b)∧c?b∧c和(a∧b)∧c?a∧(b∧c)類似地可證 a∧(b∧c)?(a∧b)∧c根據偏序關系的反對稱性有(a∧b)∧c= a∧(b∧c) 由對偶原理得 (a∨b)∨c= a∨(b∨c) ⑶ 顯然a?a

11、∨a，又由?的自反性得a?a，從而推出a∨a?a，根據偏序關系的反對稱性有a∨a=a 由對偶原理得a∧a=a ⑷顯然 a?a∨(a∧b)， 又由a?a，a∧b?a得a∨(a∧b)?a，從而得 a∨(a∧b)=a。 由對偶原理得a∧(a∨b)=a,第六章：格和布爾代數(shù),【定理6.1.2】 設?X,∨,∧?是代數(shù)系

12、統(tǒng)，其中∨,∧都是二元運算。如果∨和∧滿足吸收律，則∨和∧滿足冪等律。 證明：a∨a=a∨(a∧(a∨b))=a，同理可證a∧a=a【定理6.1.3】 設?X,∨,∧?是代數(shù)系統(tǒng)，其中∨,∧都是二元運算，滿足交換律、結合律和吸收律，則可適當定義X的偏序關系?，使?X,??構成一個格。 證明：定義X上的一個二元關系 ?=??a,b?|a,b?X且a∧

13、b=a? ⑴ 證明?是X上的偏序關系。 由定理6.1.2知∧滿足冪等律，即a∧a=a，所以a?a。故?是自反的。 設a?b且b?a，則a∧b=a且b∧a=b，于是a=a∧b=b∧a=b。所以?是反對稱的。 設a?b且b?c，則a∧b=a且b∧c=b，于是a∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a，即a?c，故?是傳遞的。 這就證明了?是X上的偏序關系。,第六

14、章：格和布爾代數(shù),⑵證明?a,b?X，a∧b是集合?a,b?的最大下界。因為 (a∧b)∧a=a∧b和(a∧b)∧b=a∧b所以a∧b?a且a∧b?b，即a∧b是?a,b?的下界。 下證a∧b是?a,b?的最大下界。 設c是?a,b?的任一下界，即c?a，c?b，那么有 c∧a=c，c∧b=c而 c∧(a∧b)=(c∧a

15、)∧b=c∧b=c所以 c?a∧b，即a∧b是?a,b?的最大下界。 ⑶ 證明a∧b=a的充分必要條件是a∨b= b 設a∧b=a，由吸收率可得 a∨b=(a∧b)∨b=b∨(b∧a)=b，即a∨b= b 設a∨b=b，由吸收率可得 a∧b=a∧(a∨b)=a，即a∧b=a,第六章：格和布爾代數(shù),⑷ 證明?a,b?X，a∨b是集合?a,b?的最小上界。

16、 根據⑶，偏序關系?可以等價的定義為： ?=??a,b?|a,b?X且a∨b=b?，用這個定義和類似于⑵的方法可以證明a∨b是集合?a,b?的最小上界。 因此，?X,??構成一個格。 根據定理6.1.3，可以給出格的另一個等價定義。 【定義6.1.4】 設?X,*,°?是代數(shù)系統(tǒng)，其中*和°都是二元運算，如果*和°在X上封閉且滿足交換律、結合律和吸收律，則稱?X,*,°?為

17、格。 根據定義6.1.4和定理6.1.1，格?X,??導出的代數(shù)系統(tǒng)?X,∨,∧?是格，以后不再區(qū)分偏序集定義的格和代數(shù)系統(tǒng)定義的格，統(tǒng)稱為格。,第六章：格和布爾代數(shù),【定理6.1.4】 設?X,??是格，∨是X上的并運算，∧是X上的交運算。則?a,b?X有 ⑴ a?b當且僅當a∧b=a ⑵ a?b當且僅當a∨b=b 證明：⑴ 設a?b，下證a∧b=a 由a

18、?a且a?b知a是集合?a,b?的下界，故有a?a∧b；另一方面，由于a∧b是?a,b?的最大下界，所以是?a,b?的下界，即a∧b?a。根據偏序關系的反對稱性得a∧b=a 設a∧b=a，下證a?b a=a∧b?b，即a?b ⑵ 可類似⑴進行證明。,第六章：格和布爾代數(shù),【 定理6.1.5】 設?X,??是格，∨是X上的并運算，∧是X上的交運算。?a,b,c,d?X，若a?b且c?d，則

19、a∨c?b∨d，a∧c?b∧d 證明： a?b?b∨d ，c?d?b∨d，因此a∨c?b∨d 類似的可以證明a∧c?b∧d【定理6.1.6】 設?X,??是格，∨是X上的并運算，∧是X上的交運算。則?a,b,c?X有 ⑴ a∨(b∧c) ? (a∨b)∧(a∨c) ⑵ (a∧b)∨(a∧c) ? a∧(b∨c) 證明：⑴ 根據定理8.1.5，由a?a和b∧c

20、?b得 a∨(b∧c)?a∨b 又由a?a且b∧c?c得 a∨(b∧c)?a∨c 從而得到 a∨(b∧c)?(a∨b)∧(a∨c) 利用對偶原理，即得

21、⑵。 一般地說，格中的∨和∧并不滿足分配律。,第六章：格和布爾代數(shù),【定義6.1.5】 設?X,∨,∧?是格，B是X的非空子集，如果B關于運算∨和∧也構成格，則稱?B,∨,∧?是?X,∨,∧?的子格。 在例6.1中，令B1＝?1,2,3,6?，B2＝?2,4,6,12?，則 ?B1,∨,∧?和?B2,∨,∧?是格?S12,∨,∧?的子格。 令B3＝?1,2,3,12?

22、，由于2∨3=6，而6?B3，所以 ?B3,∨,∧?不是格?S12,∨,∧?的子格。 以下定義格的同態(tài)?！径x6.1.6】 設?X1,∨1,∧1?和?X2,∨2,∧2?是格，其中∨1,∧1,∨2和∧2都是二元運算。f是從X1到X2的一個映射，對任意的a,b?X1有f(a∨1b)=f(a)∨2 f(b)， f(a∧1b)=f(a)∧2f(b)

23、則稱f是格?X1,∨1,∧1?到格?X2,∨2,∧2?的格同態(tài)。如果f是單射、滿射和雙射，分別稱f是格單同態(tài)、格滿同態(tài)和格同構。稱?f(X1),∨2,∧2?是?X1,∨1,∧1?的格同態(tài)像。,第六章：格和布爾代數(shù),【定理6.1.7】 設?X1,?1?和?X2,?2?是格，?X1,∨1,∧1? 和?X2,∨2,∧2?是它們導出的代數(shù)系統(tǒng)。f是格?X1,∨1,∧1?到格?X2,∨2,∧2?的格同態(tài)，則?a,b?X1，如果a?1b，必

24、有f(a)?2f(b) 證明：設a?1b，根據定理6.1.4，a∧1b=a，由于 f 是格?X1,∨1,∧1?到格?X2,∨2,∧2?的格同態(tài)，所以 f(a)=f(a∧1b)=f (a)∧2f (b)，再由定理6.1.4，f (a)?2f (b)。 定理6.1.7說明格同態(tài)是保序的。一般地說，定理6.1.7的逆并不成立?！纠?.3】設A=?a,b,c,d,e?，?A,??是格，其哈斯圖如圖8.3所

25、示，P(A)是A的冪集合，R?=??x,y?|x?P(A)∧y?P (A)∧x?y?是P(A)上的偏序關系。?P(A), R??也是格。作映射f：A→P (A)，定義為：?x?A，f(x)= ?y|y?A且y?x?，即：f(a)=?a,b,c,d,e?=A，f(b)=?b,e?，f(c)=?c,e?，f(d)=?d,e?，f(e)=?e?。證明f是保序的，但不是格同態(tài)。,第六章：格和布爾代數(shù),證明：?a,b?A，設a?b，?c?f

26、(a)，c?a，由偏序關系的傳遞性得c?b，所以c?f(b)，即f(a)?f(b)，于是f(a)R?f(b)。故f是保序的。 對于b,d?A，b∨d=a f(b∨d)=f(a)=A f(b)∪f (d)=?b,e?∪?d,e? =?b,d,e? f(b∨d)≠f(b)∪f (d) f不是

27、格同態(tài)。 但是，當f是格同構時，定理6.1.7的逆成立。,第六章：格和布爾代數(shù),【定理6.1.8】 設?X1,?1?和?X2,?2?是格，?X1,∨1,∧1?和?X2,∨2,∧2?是它們導出的代數(shù)系統(tǒng)。f 是X1到X2的雙射，則 f 是?X1,∨1,∧1? 到 ?X2,∨2,∧2? 的格同構的充分必要條件是?a,b?X1，a?1b?f(a)?2f(b) 證明：設f是?X1,∨1,∧1?到?X2,∨2

28、,∧2?的格同構，下證?a,b?X1，a?1b?f(a)?2f(b) 由定理6.1.7可知，?a,b?X1，如果a?1b，必有f(a)?2f(b) 設f(a)?2f(b)，由定理6.1.4有f(a)=f(a)∧2f(b)=f(a∧1b)，由于f是雙射，故a∧1b=a，所以a?1b 這就證明a?1b?f(a)?2f(b) 設?a,b?X1，a?1b?f(a)?2f(b)，下證 f

29、 是?X1,∨1,∧1?到?X2,∨2,∧2?的格同構。 設a∧1b=c，則c?1a，c?1b，f(c)=f(a∧1b)，f(c)?2f(a)，f(c)?2f(b)，故 f(c)?2f(a)∧2f(b)。 設f(a)∧2f(b)=f(d)，則有f(c)?2f(a)∧2f(b)=f(d)，即f(c)?2f(d)；還有f(d)?2f(a)和f(d)?2f(b)。所以有d?1a和d?1b，,第六章：格和布爾代數(shù),

30、于是d?1a∧1b，即d?1c，故f(d)?2f(c)，再由偏序關系的反對稱性有f(c)=f(d)。即f(a∧1b)=f(c)=f(d)=f (a)∧2f(b) 類似地可以證明 f(a∨1b)=f (a)∨2f(b) 這就證明了f是?X1,∨1,∧1?到?X2,∨2,∧2?的格同構?！径x6.1.7】 設?X1,?1?和?X2,?2?是格， ?X1,∨1,∧1? 和?X2,∨2,∧2?是它們

31、導出的代數(shù)系統(tǒng)。其中∨1,∧1,∨2和∧2都是二元運算。??a1,b1??X1×X2和??a2,b2??X1×X2，定義X1×X2上的二元運算∨3和∧3為： ?a1,b1?∨3?a2,b2?=?a1∨1a2, b1∨2b2? ?a1,b1?∧3?a2,b2?=?a1∧1a2, b1∧2b2?代數(shù)系統(tǒng)? X1×X2,∨3,∧3?稱為格?X1,∨1,∧1?

32、到格?X2,∨2,∧2?的直積。 如果?X1,∨1,∧1?和?X2,∨2,∧2?是格，可以證明代數(shù)系統(tǒng)?X1×X2,∨3,∧3?也是格,第六章：格和布爾代數(shù),§6.2 分配格【定義6.2.1】 設?X,??是格，?X,∨,∧?是?X,??導出的代數(shù)系統(tǒng)，如果?a,b,c?X有 a∨(b∧c)=(a∨b)∧(a∨c) (并運算對交運算可分配) a∧(b∨c)=(a∧

33、b)∨(a∧c) (交運算對并運算可分配)則稱?X,∨,∧?為分配格。 因為a∨(b∧c)=(a∨b)∧(a∨c)和 a∧(b∨c)=(a∧b)∨(a∧c) 互為對偶命題，根據對偶原理，定義6.2.1還可以改寫為：一個格如果交運算對并運算可分配或并運算對交運算可分配，則稱該格為分配格。,第六章：格和布爾代數(shù),【例6.4】 設A=?a,b,c?，P (A)=?Æ,?a?,?b?,?c

34、?,?a,b?,?a,c?,?b,c?,?a,b,c??是A的冪集合，P (A)上的包含關系R?=??x,y?| x?P (A)∧y?P (A)∧x?y?是P (A)上的偏序關系。?P (A), R??是偏序集，P (A)上的蓋住關系 COVP(A)=??Æ,?a??,?Æ,?b??,?Æ,?c??,??a?,?a,b??,

35、??b?,?a,b??,??a?,?a,c??,??c?,?a,c??, ??b?,?b,c??,??c?,?b,c??,??a,b?,?a,b,c??, ??a,c?,?a,b,c??,??b,c?,?a,b,c???其哈斯圖如圖8.4所示。?P (A),∨,∧?是?P (A), R??導出的代數(shù)系統(tǒng)，證明?P (A)

36、,∨,∧?是分配格。 證明：前面已經證明了格?P (A), R??導出的代數(shù)系統(tǒng)?P (A),∨,∧?實際就是代數(shù)系統(tǒng)?P (A),∪,∩?，其中∪是集合的并運算，∩是集合的交運算。而集合的并、交運算滿足分配律：,第六章：格和布爾代數(shù),?P,Q,R?P (A) P∪(Q∩R)=(P∪Q)∩(P∪R) P∩(Q∪R)=(P∩Q)∪(P∩R) 所以，?P (A),∨,∧?分配格。,第六章：

37、格和布爾代數(shù),【例6.5】 A=?a,b,c,d,e?，?A,??是格，其哈斯圖如圖8.3所示，證明?A,??不是分配格。 證明：b∨(c∧d)=b∨e=b (b∨c)∧(b∨d)=a∧a=a b∨(c∧d)≠(b∨c)∧(b∨d) 所以，?A,??不是分配格。 本例中的格叫做鉆石格，鉆石格不是分配格。,第六章：格和布爾

38、代數(shù),【例6.6】設A=?a,b,c,d,e?，?A,??是格，其哈斯圖如圖8.5所示，證明?A,??不是分配格。 證明： d∨(b∧c)=d∨e=d (d∨b)∧(d∨c)=a∧c=c d∨(b∧c)≠(d∨b)∧(d∨c)所以，?A,??不是分配格。 本例中的格叫做五角格，五角格也不是分配格。鉆石格和五角格是兩個很重要的格。,第六章：格和布爾

39、代數(shù),【定理6.2.1 】一個格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構的子格。 這個定理的證明已經超過了本書的范圍，故略去?！?推論1】 設?A,??是格，如果|A|＜5，則?A,??一定是分配格。【推論2】 設?A,??是格，如果?A,??是全序集，則?A,??一定是分配格?！纠?.7】圖8.6給出了兩個格的哈斯圖。試證明它們都不是分配格。 證明：在圖8.6 (a)中含有與五角格

40、同構的子格，所以不是分配格；在圖8.6 (b)中含有與鉆石格同構的子格，所以不是分配格。,第六章：格和布爾代數(shù),第六章：格和布爾代數(shù),【定理6.2.2】 設?X,??是格，?X,∨,∧?是格?X,??導出的代數(shù)系統(tǒng)。?X,??是分配格的充分必要條件是?a,b,c?X，當a∧b=a∧c且a∨b=a∨c時，必有b= c 證明：設?X,??是分配格，?a,b,c?X， a∧b=a∧c且a∨b=a∨c

41、 b=b∨(b∧a)=b∨(a∧b) (吸收律和交換律) =b∨(a∧c)= (b∨a)∧(b∨c) (已知代入和分配律) =(a∨c)∧(b∨c) (交換律和已知代入) =(a∧b)∨c (分配律)

42、 =(a∧c)∨c (已知條件代入) =c (交換律和吸收律) 設?a,b,c?X，當a∧b=a∧c且a∨b=a∨c時，有b=c，但?X,∨,∧?不是分配格。由定理6.2.1知?X,∨,∧?中必含有與鉆石格或五角格同構的子格。假設?X

43、,∨,∧?含有與鉆石格同構的子格，且此子格為?S,∨,∧?，其中S=?u,v,x,y,z?，u為它的最大元，v為它的最小元。從而x∨y=u=x∨z，x∧y=v=x∧z，但y≠z，與已知矛盾。,第六章：格和布爾代數(shù),對五角格的情況，可類似證明。 例如，在圖8.6 (a)中，b∧c=g=b∧f且b∨c=a=b∨f，但c≠f；在圖8.6 (b)中，b∧c=f= b∧e且b∨c=a= b∨e，但c≠e。根據定理6.2.2它們不是

44、分配格。 §6.3 有補格 【定義6.3.1】 設?X,??是格，如果?a?X，?x?X都有 a?x (x?a)則稱a為格?X,??的全下(上)界，記為0(1)?！径ɡ?.3.1】 設?X,??是格，若格?X,??有全下界或全上界，則它們一定是惟一的。 證明：用反證法。 如果有兩個全下界a和b，a,b?X。因為a是全下界，所以a?b；又因為b是全

45、下界，所以b?a。再由?的反對稱性有a=b 類似地可證明全上界的惟一性。,第六章：格和布爾代數(shù),【定義6.3.2】設?X,??是格，?X,∨,∧?是格?X,??導出的代數(shù)系統(tǒng)。若格?X,∨,∧?存在全下界0和全上界1，則稱?X,∨,∧?為有界格，記為?X,∨,∧,0,1?。 在例8.4中，?P (A), R??是格。?P (A),∨,∧?是?P (A), R??導出的代數(shù)系統(tǒng)。空集Æ是格的全下界

46、，而集合A是格的全上界。因而?P (A),∨,∧?是有界格，可記為?P (A)∨,∧,Æ,A?。在例6.6中，從哈斯圖(圖8.5)中可以看出，a是全上界，而e是全下界，所以?A,??是有界格?！径ɡ?.3.2】 設?X,∨,∧,0,1?為有界格，則?a?X有 a∧0=0，a∨0=a； a∧1=a，a∨1=1 證明：因為0是全下界且a∧0?X，所以0?a

47、∧0，又因為a∧0?0，由?的反對稱性有a∧0=0 顯然a?a，由于1是全上界，所以有a?1，從而推出 a?a∧1，又因為a∧1?a，再由?的反對稱性有a∧1=a a∨0=a 和a∨1=1可以類似地證明。,第六章：格和布爾代數(shù),設?X,∨,∧,0,1?為有界格，a?X有a∧0=0，因為格滿足交換律，所以0∧a=0，這說明0是交運算的零元；同樣的道理，0是并運算的幺元，而1是交運算的幺元和并運算的零元。

48、【定義6.3.3】 設 ?X,∨,∧,0,1? 為有界格，如果對于 a?X，?b?X，使得a∨b=1且a∧b=0，則稱b是a的補元。 如果b是a的補元，從定義6.3.3可以看出，a也是b的補元。因此，可以說a和b是互補的，或者說a和b互為補元。 例如，在例6.6中，從哈斯圖(圖8.5)中可以看出，b和c互為補元，b和d也互為補元，b有兩個補元c和d。所以格中元素的補元并不惟一。,第六章：格和布爾代數(shù),【

49、例6.8】圖8.7是一個有界格的哈斯圖。找出a,b,c,d,e的補元。 解：從圖8.7中可以看出，a的補元是e；b沒有補元；c的補元是d；d的補元是c和e，e的補元是a和d，0和1互為補元。 顯然，在有界格中，全上界1的惟一補元是全下界0，而全下界0的惟一補元是全上界1。除了1和0，其它元素有的有補元，有的沒有補元。如果某個元素的補元存在，補元可能有一個，也可能有多個。但在有界分配格中，如果元素的補元存

50、在，則一定惟一。,第六章：格和布爾代數(shù),【定理6.3.3】設?X,∨,∧,0,1?為有界分配格，如果對于a?X，a存在補元b，則b是a的惟一補元。 證明：因為b是a的補元，所以有 a∨b=1，a∧b=0 設c?X，c是a的另一個補元，同樣也有a∨c=1，a∧c=0 從而有 a∨b= a∨c，a∧b= a∧c 由于?X,∨,∧,0,1?為分配格，根據定理6.6.6必有b=c

51、，即a的補元惟一。【定義6.3.4】設?X,∨,∧,0,1?為有界格，如果?a?X，在X中都有a的補元存在，則稱?X,∨,∧,0,1?為有補格 例如，圖8.8是三個有界格的哈斯圖，由于每一個元素至少有一個補元，所以它們都是有補格。,第六章：格和布爾代數(shù),第六章：格和布爾代數(shù),,§6.4 布爾代數(shù) 【定義6.4.1】 有補分配格稱為布爾格。 在布爾格中每一個元素都有補元。因為有補格一定是有界

52、格，所以布爾格一定是有界分配格，根據定理6.3.3，布爾格中的每一個元素的補元存在且惟一。于是可以將求補元的運算看作一元運算且把a的補元記為a′?！径x6.4.2】 設?X,??是布爾格，?X,∨,∧,′?是格?X,??導出的代數(shù)系統(tǒng)。稱代數(shù)系統(tǒng)?X,∨,∧, ′?為布爾代數(shù)。 在6.1節(jié)中證明了 ?P (A), R??是格，其中 A=?a,b?。?P (A),∪,∩?是?P (A), R??導出的代數(shù)系統(tǒng)，其中∪和

53、∩是集合并運算和交運算。以后又進一步說明了?P (A),∪,∩?是分配格和有界格，Æ是全下界、A是全上界。從而?P(A),∪,∩?是有界分配格。令A為全集，?T?P (A)，T的補集~T=A–T?P (A)，滿足T∪~T= A和T∩~T=Æ，所以T的補元T′=~T。根據定義6.4.2，?P (A),∪,∩, ~?是布爾代數(shù)。,第六章：格和布爾代數(shù),可以證明，當A為任意集合時，?P (A),∪,∩, ~?也是布爾代數(shù)

54、。稱為集合代數(shù)。集合代數(shù)是布爾代數(shù)的一個具體模型。 布爾代數(shù)一定是格。根據定理8.1.1，布爾代數(shù)中的兩個二元運算滿足交換律、結合律、冪等律和吸收律。此外，布爾代數(shù)還有下面的性質：【定理6.4.1】 設?X,∨,∧, ′?為布爾代數(shù)，?a,b?X，必有 ⑴ (a′)′=a ⑵ (a∨b)′= a′∧b′ ⑶ (a∧b)′= a′∨b′ 證明：⑴ a′是a的

55、補元，a也是a′的補元，由布爾代數(shù)中補元的惟一性有(a′)′=a,第六章：格和布爾代數(shù),⑵(a∨b)∨(a′∧b′)=((a∨b)∨a′)∧((a∨b)∨b′) =(b∨(a∨a′))∧(a∨(b∨b′)) =(b∨1)∧(a∨1)=1∧1=1 (a∨b)∧(a′∧

56、b′)=(a∧(a′∧b′))∨(b∧(a′∧b′)) =((a∧a′)∧b′)∨((b∧b′)∧a′) =(0∧b′)∨(0∧a′)=0∨0=0所以 (a∨b)′= a′∧b′ ⑶ 同理可證 (a∧b)′= a′∨b′ 定理6.4.1中的⑴稱為雙重否定

57、律，⑵和⑶稱為德摩根律。布爾代數(shù)滿足雙重否定律和德摩根律。,第六章：格和布爾代數(shù),【定理6.4.2】 設?X,*,°,′?是代數(shù)系統(tǒng)，其中*和°都是二元運算，′是一元運算。?X,*,°,′?是布爾代數(shù)的充分必要條件是：⑴*和°在X上封閉且滿足交換律。 ⑵*和°滿足分配律(滿足*對°的分配律和°對*的分配律)。 ⑶X中存在運算*的幺元和運算°的幺元。設運算*的幺元為0，運算°的幺元為1。即?a?X，有a*0

58、=a，a°1=a ⑷ ?a?X，?a′?X，使得a*a′=1，a°a′=0 由于篇幅的限制，證明從略。 定理6.4.2給出的四個條件可以作為布爾代數(shù)的等價定義。 布爾代數(shù)?X,*,°,′?也可以表示成為?X,*,°,′,0,1?，其中0是運算*的幺元，1是運算°的幺元。,第六章：格和布爾代數(shù),【例6.9】設P是所有命題構成的集合，∨,∧和¬分別是命題的析取、合取和

59、否定聯(lián)結詞。證明代數(shù)系統(tǒng)?P,∨,∧, ¬?是布爾代數(shù)。 證明：根據第1章的內容，∨和∧在P上封閉且滿足交換律、分配律。命題常元0(假)和1(真)是集合P的元素，滿足?q?P，q∨0=q，q∧1=q。 ?q?P，¬q?P，滿足q∨¬q=1，q∧¬q=0。 根據定理6.4.2，?P,∨,∧, ¬?是布爾代數(shù)。 例6.9中的布爾代數(shù)?P,∧,

60、∨, ¬?叫做命題代數(shù)，它是布爾代數(shù)的又一個模型。 【定義6.4.3 】 設 ?X,∨,∧,′, 0,1 ? 是布爾代數(shù)，B 是X的非空子集，若0,1?B且 ?B,∨,∧,′, 0,1 ? 也是布爾代數(shù)。則稱?B,∨,∧,′, 0,1 ?是?X,∨,∧, ′, 0,1 ?子布爾代數(shù)。,第六章：格和布爾代數(shù),【定理6.4.3】 設?X,∨,∧,′,0,1?是布爾代數(shù)，B是X的非空子集，若0,1?B且運算∨,∧,′在B上封閉，

61、則?B,∨,∧,′, 0,1 ?是?X,∨,∧,′, 0,1 ?子布爾代數(shù) 證明：⑴ ?a,b?B，因為 B?X，所以 a,b?X。又因為?X,∨,∧,′,0,1?是布爾代數(shù)，故 a∨b=b∨a，a∧b=b∧a ⑵ 類似⑴可以證明*和°滿足分配律。 ⑶ 已知0,1?B，?a?B?X，a?X，有a∨0=a和a∧1=a ⑷?a?B，由′在B上封閉知有a′?B，使得a∨a′=

62、1，a∧a′=0 根據定理 6.4.2，?B,∨,∧,′, 0,1 ? 是布爾代數(shù)，它是?X,∨,∧,′,0,1 ?的子布爾代數(shù)。 為了方便，以下將x?y且x≠y記為x?y。,第六章：格和布爾代數(shù),【例4.10】設?X,∨,∧,′, 0,1 ?是布爾代數(shù)，a,b?X，a?b，令S=?x| x?X，a?x且x?b?試證明?S,∨,∧,′,0,1 ?是?X,∨,∧,′,0,1 ?的子布爾代數(shù)。

63、 證明：由于a?a且a?b，所以a?S，S是X的非空子集，由S的定義知 a是S的全下界，b是S的全上界。?x, y?S， a?x且x?b，a?y且y?b a?x∨y且x∨y?b，a?x∧y且x∧y?b從而x∨y?S且x∧y?S，即運算∨和∧在S上封閉。 ?x?S，令y=(a∨x′)∧b 由于a?a∨x′，a?b，故a?(a∨x′)∧b；

64、 又由于(a∨x′)∧b?b，所以y=(a∨x′)∧b?S，又 x∨y=x∨((a∨x′)∧b) =x∨((a∧b)∨(x′∧b)) (分配律) =x∨(a∨(x′∧b)) (a?b?a∧b=a) = (x∨a)∨(x′∧b) (結合律),第六章：格和布爾代數(shù),= x∨

65、(x′∧b) (a?x?a∨x=x) =(x∨x′)∧(x∨b) (分配律) =1∧(x∨b) (x′是x的補元) =x∨b (1是∧的幺元) =b (

66、x?b ?x∨b=b) x∧y=x∧((a∨x′)∧b) =(x∧b)∧(a∨x′) (交換律和結合律) =x∧(a∨x′) (由定理8.1.4，x?b?x∧b=x) =(x∧a)∨(x∧x′) (分配律) =(x∧a)∨0 (x′

67、是x的補元) =(x∧a) (0是∨的幺元) =a (由定理8.1.4，a?x?a∧x=a)所以x′=y?S，一元運算′在S上封閉。 根據定理6.4.3，?S,∨,∧, ′, 0,1 ?是?X,∨,∧,′, 0,1 ?的子布爾代數(shù)。,第六章：格和布爾代數(shù),【定義6.4.4

68、】 設?X1,∨1,∧1,′,0,1?和?X2,∨2,∧2,",?,E?是兩個布爾代數(shù)，其中∨1,∧1,∨2和∧2都是二元運算，′和"是一元運算， 0和1 是X1的全下界和全上界，?,E是X2的全下界和全上界。f是從X1到X2的一個映射，對任意的a,b?X1有 f (a∨1b)=f (a)∨2f (b) f (a∧1b)=f