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

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

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

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

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

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

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

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

8、了格的對(duì)偶原理，在證明格的性質(zhì)時(shí)，只需證明其中的一個(gè)就可以了。,第六章：格和布爾代數(shù),【定理6.1.1】 設(shè)?X,??是格，?X,∨,∧?是格?X,??導(dǎo)出的代數(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) (結(jié)合律) ⑶ 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根據(jù)偏序關(guān)系的反對(duì)稱性有(a∧b)∧c= a∧(b∧c) 由對(duì)偶原理得 (a∨b)∨c= a∨(b∨c) ⑶ 顯然a?a

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

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

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

14、章：格和布爾代數(shù),⑵證明?a,b?X，a∧b是集合?a,b?的最大下界。因?yàn)?(a∧b)∧a=a∧b和(a∧b)∧b=a∧b所以a∧b?a且a∧b?b，即a∧b是?a,b?的下界。 下證a∧b是?a,b?的最大下界。 設(shè)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 設(shè)a∧b=a，由吸收率可得 a∨b=(a∧b)∨b=b∨(b∧a)=b，即a∨b= b 設(shè)a∨b=b，由吸收率可得 a∧b=a∧(a∨b)=a，即a∧b=a,第六章：格和布爾代數(shù),⑷ 證明?a,b?X，a∨b是集合?a,b?的最小上界。

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

17、格。 根據(jù)定義6.1.4和定理6.1.1，格?X,??導(dǎo)出的代數(shù)系統(tǒng)?X,∨,∧?是格，以后不再區(qū)分偏序集定義的格和代數(shù)系統(tǒng)定義的格，統(tǒng)稱為格。,第六章：格和布爾代數(shù),【定理6.1.4】 設(shè)?X,??是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。則?a,b?X有 ⑴ a?b當(dāng)且僅當(dāng)a∧b=a ⑵ a?b當(dāng)且僅當(dāng)a∨b=b 證明：⑴ 設(shè)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。根據(jù)偏序關(guān)系的反對(duì)稱性得a∧b=a 設(shè)a∧b=a，下證a?b a=a∧b?b，即a?b ⑵ 可類似⑴進(jìn)行證明。,第六章：格和布爾代數(shù),【 定理6.1.5】 設(shè)?X,??是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。?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】 設(shè)?X,??是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。則?a,b,c?X有 ⑴ a∨(b∧c) ? (a∨b)∧(a∨c) ⑵ (a∧b)∨(a∧c) ? a∧(b∨c) 證明：⑴ 根據(jù)定理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) 利用對(duì)偶原理，即得

21、⑵。 一般地說(shuō)，格中的∨和∧并不滿足分配律。,第六章：格和布爾代數(shù),【定義6.1.5】 設(shè)?X,∨,∧?是格，B是X的非空子集，如果B關(guān)于運(yùn)算∨和∧也構(gòu)成格，則稱?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】 設(shè)?X1,∨1,∧1?和?X2,∨2,∧2?是格，其中∨1,∧1,∨2和∧2都是二元運(yùn)算。f是從X1到X2的一個(gè)映射，對(duì)任意的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)和格同構(gòu)。稱?f(X1),∨2,∧2?是?X1,∨1,∧1?的格同態(tài)像。,第六章：格和布爾代數(shù),【定理6.1.7】 設(shè)?X1,?1?和?X2,?2?是格，?X1,∨1,∧1? 和?X2,∨2,∧2?是它們導(dǎo)出的代數(shù)系統(tǒng)。f是格?X1,∨1,∧1?到格?X2,∨2,∧2?的格同態(tài)，則?a,b?X1，如果a?1b，必

24、有f(a)?2f(b) 證明：設(shè)a?1b，根據(jù)定理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說(shuō)明格同態(tài)是保序的。一般地說(shuō)，定理6.1.7的逆并不成立。【例6.3】設(shè)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)上的偏序關(guān)系。?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，設(shè)a?b，?c?f

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

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

28、,∧2?的格同構(gòu)，下證?a,b?X1，a?1b?f(a)?2f(b) 由定理6.1.7可知，?a,b?X1，如果a?1b，必有f(a)?2f(b) 設(shè)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) 設(shè)?a,b?X1，a?1b?f(a)?2f(b)，下證 f

29、 是?X1,∨1,∧1?到?X2,∨2,∧2?的格同構(gòu)。 設(shè)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)。 設(shè)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)，再由偏序關(guān)系的反對(duì)稱性有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?的格同構(gòu)?！径x6.1.7】 設(shè)?X1,?1?和?X2,?2?是格， ?X1,∨1,∧1? 和?X2,∨2,∧2?是它們

31、導(dǎo)出的代數(shù)系統(tǒng)。其中∨1,∧1,∨2和∧2都是二元運(yùn)算。??a1,b1??X1×X2和??a2,b2??X1×X2，定義X1×X2上的二元運(yùn)算∨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】 設(shè)?X,??是格，?X,∨,∧?是?X,??導(dǎo)出的代數(shù)系統(tǒng)，如果?a,b,c?X有 a∨(b∧c)=(a∨b)∧(a∨c) (并運(yùn)算對(duì)交運(yùn)算可分配) a∧(b∨c)=(a∧

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

34、?,?a,b?,?a,c?,?b,c?,?a,b,c??是A的冪集合，P (A)上的包含關(guān)系R?=??x,y?| x?P (A)∧y?P (A)∧x?y?是P (A)上的偏序關(guān)系。?P (A), R??是偏序集，P (A)上的蓋住關(guān)系 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??導(dǎo)出的代數(shù)系統(tǒng)，證明?P (A)

36、,∨,∧?是分配格。 證明：前面已經(jīng)證明了格?P (A), R??導(dǎo)出的代數(shù)系統(tǒng)?P (A),∨,∧?實(shí)際就是代數(shù)系統(tǒng)?P (A),∪,∩?，其中∪是集合的并運(yùn)算，∩是集合的交運(yùn)算。而集合的并、交運(yùn)算滿足分配律：,第六章：格和布爾代數(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】設(shè)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,??不是分配格。 本例中的格叫做五角格，五角格也不是分配格。鉆石格和五角格是兩個(gè)很重要的格。,第六章：格和布爾

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

40、同構(gòu)的子格，所以不是分配格；在圖8.6 (b)中含有與鉆石格同構(gòu)的子格，所以不是分配格。,第六章：格和布爾代數(shù),第六章：格和布爾代數(shù),【定理6.2.2】 設(shè)?X,??是格，?X,∨,∧?是格?X,??導(dǎo)出的代數(shù)系統(tǒng)。?X,??是分配格的充分必要條件是?a,b,c?X，當(dāng)a∧b=a∧c且a∨b=a∨c時(shí)，必有b= c 證明：設(shè)?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 (交換律和吸收律) 設(shè)?a,b,c?X，當(dāng)a∧b=a∧c且a∨b=a∨c時(shí)，有b=c，但?X,∨,∧?不是分配格。由定理6.2.1知?X,∨,∧?中必含有與鉆石格或五角格同構(gòu)的子格。假設(shè)?X

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

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

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

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

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

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

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

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

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

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

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

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

55、補(bǔ)元，a也是a′的補(bǔ)元，由布爾代數(shù)中補(bǔ)元的惟一性有(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】 設(shè)?X,*,°,′?是代數(shù)系統(tǒng)，其中*和°都是二元運(yùn)算，′是一元運(yùn)算。?X,*,°,′?是布爾代數(shù)的充分必要條件是：⑴*和°在X上封閉且滿足交換律。 ⑵*和°滿足分配律(滿足*對(duì)°的分配律和°對(duì)*的分配律)。 ⑶X中存在運(yùn)算*的幺元和運(yùn)算°的幺元。設(shè)運(yùn)算*的幺元為0，運(yùn)算°的幺元為1。即?a?X，有a*0

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

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

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

61、則?B,∨,∧,′, 0,1 ?是?X,∨,∧,′, 0,1 ?子布爾代數(shù) 證明：⑴ ?a,b?B，因?yàn)?B?X，所以 a,b?X。又因?yàn)?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 根據(jù)定理 6.4.2，?B,∨,∧,′, 0,1 ? 是布爾代數(shù)，它是?X,∨,∧,′,0,1 ?的子布爾代數(shù)。 為了方便，以下將x?y且x≠y記為x?y。,第六章：格和布爾代數(shù),【例4.10】設(shè)?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，即運(yùn)算∨和∧在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) (結(jié)合律),第六章：格和布爾代數(shù),= x∨

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

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

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

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