第七章 格和布爾代數精簡

1、格與布爾代數主講：魚亮主講：魚亮西安電子科技大學多媒體研究所西安電子科技大學多媒體研究所西安電子科技大學多媒體研究所 12022-7-3第七章第七章 格與布爾代數格與布爾代數7.1 格格 7.2 子格和格同態(tài)子格和格同態(tài)7.3 特殊的格特殊的格7.4 布爾代數布爾代數與布爾表達式與布爾表達式西安電子科技大學多媒體研究所 22022-7-37.17.1格格u格的定義：格的定義：設設是一個偏序集，如果集是一個偏序集，如果集合合L中的任意兩個元素都有最小上界和最大中的任意兩個元素都有最小上界和最大下界，則稱下界，則稱為格。為格。西安電子科技大學多媒體研究所 32022-7-37.17.1格格u【例題

2、例題1】判斷下圖中所示各哈斯圖代表的判斷下圖中所示各哈斯圖代表的偏序集合是否是格？為什么？偏序集合是否是格？為什么？abcdefabcdeabcdefabcdabcdabcdefghabcdeabcde西安電子科技大學多媒體研究所 42022-7-37.17.1格格u【例題例題2】設設I+是正整數集合，定義是正整數集合，定義I+上的上的二元關系二元關系“|”,任取任取a,bI+,a|b當且僅當當且僅當a能能整除整除b。證明。證明:是一個格。是一個格。證明：證明：I+上的二元關系上的二元關系|是自反、反對稱和傳遞的，是自反、反對稱和傳遞的，因此因此是一個偏序集合。是一個偏序集合。任取任取a, b

3、I+, a與與b在偏序集合在偏序集合中的最小上界中的最小上界是其最小公倍數是其最小公倍數:luba,bI+。任取任取a,bI+, a與與b在偏序集合在偏序集合中的最大下界中的最大下界是其最大公約數：是其最大公約數：glba,bI+。結論得證。結論得證。西安電子科技大學多媒體研究所 52022-7-37.17.1格格u【例題例題3】設設S是任意集合，是任意集合，(S)是是S的冪集，的冪集，偏序集合偏序集合是否是格？是否是格？解答解答:任取任取A,B(S), A與與B在偏序集合在偏序集合中的最小上界是中的最小上界是AB (S), A與與B在偏序集合在偏序集合 中的最大下界是中的最大下界是AB (S

4、)。西安電子科技大學多媒體研究所 62022-7-37.17.1格格u保交運算保交運算 ab = glba, b,求求a,b的最大下界的最大下界u保聯運算保聯運算 ab = luba, b,求求a,b的最小上界的最小上界u定理定理(格的對偶定理格的對偶定理)如果如果是一個是一個格，則格，則也是一個格。設也是一個格。設P是一個命題，是一個命題，P的對偶命題的對偶命題P*是將關系符是將關系符換成換成，將保交，將保交與保聯與保聯運算符互換所得的命題。若運算符互換所得的命題。若P中中對一切格都為真，則對一切格都為真，則P*對一切格也都為真。對一切格也都為真。西安電子科技大學多媒體研究所 72022-7

5、-37.17.1格格u【例題例題】設設是一個格是一個格,其哈斯圖如下其哈斯圖如下圖所示，畫出圖所示，畫出的哈斯圖。的哈斯圖。 解答：解答：是是的對偶格，因此其哈的對偶格，因此其哈斯圖可由斯圖可由旋轉旋轉180得到，如得到，如(b)圖所圖所示。示。(a)(b)西安電子科技大學多媒體研究所 82022-7-37.17.1代數格代數格u代數格：代數格：設設是一個格，是一個格，a,bL。在。在L上可以定義兩個運算上可以定義兩個運算*和和 ： a*b = glba,b 也可寫成也可寫成 ab = glba,b a b = luba,b 也可寫成也可寫成 ab = luba,b 則稱則稱(或或)為格為格所

6、所誘導的代數系統(tǒng)，簡稱代數格。誘導的代數系統(tǒng)，簡稱代數格。西安電子科技大學多媒體研究所 92022-7-37.17.1代數格的性質代數格的性質u定理定理1在一個格在一個格中，對任意的中，對任意的a,bA,都有都有 aab, bab aba, abb證明：因為證明：因為a和和b的并是的并是a的一個上界，所以的一個上界，所以 aab 同理同理 bab 由對偶原理即得由對偶原理即得 aba, abb西安電子科技大學多媒體研究所 102022-7-37.17.1代數格的性質代數格的性質u定理定理2在一個格在一個格中，對于中，對于a,b,c,dA,如果如果 ab 和和 cd 則則 ac bd ac bd

7、證明：因為證明：因為 bbd, dbd,由傳遞性可得由傳遞性可得 a b d, c b d 這就表明這就表明bd是是a和和c的一個上界，而的一個上界，而ac 是是a和和c的最小上界，所以，必有的最小上界，所以，必有西安電子科技大學多媒體研究所 112022-7-37.17.1代數格的性質代數格的性質 ac bd 類似地可以證明類似地可以證明 ac bd西安電子科技大學多媒體研究所 122022-7-37.17.1代數格的基本性質代數格的基本性質u由格誘導的代數系統(tǒng)滿足以下性質：由格誘導的代數系統(tǒng)滿足以下性質：(1)自反性自反性 a a(2)反對稱性反對稱性 (a b) 且且 (b a) a =

8、 b(3)傳遞性傳遞性 (a b) 且且 (b c) a c(4) aba, abb aab, bab(5) (ca) 且且(cb) c(ab), (bc)且且(ac) c (ab)(6)交換律交換律 ab=ba ab= ba西安電子科技大學多媒體研究所 132022-7-37.17.1代數格的基本性質代數格的基本性質(7)結合律結合律 (ab)c=a(bc), (ab)c=a(b c)(8)等冪律等冪律 aa=a, a a=a (9)吸收律吸收律 a(ab)= a, a(ab)=a(10) ab ab=a a b=b(11) ab 且且d c ad bc ab 且且d c a d bc西安電

9、子科技大學多媒體研究所 142022-7-37.17.1代數格的基本性質代數格的基本性質(12)保序性保序性 bc abac, bc a bac(13)分配不等式分配不等式 a (bc) (ab)(ac) a(bc) (ab)(ac) (14)模不等式模不等式 a c a(bc)(ab)c證明：證明：(7) 由定理由定理1可知可知 bbca(bc) 和和 aa(bc) 西安電子科技大學多媒體研究所 152022-7-37.17.1代數格的基本性質代數格的基本性質由定理由定理2可知可知 ab a(bc) 又因又因cbc a(bc) 說明說明a(bc) 是是ab 和和c的上界的上界,而而(ab)c

10、是是 ab 和和c的最小上界，因此的最小上界，因此 (ab)c a(bc) 類似得可以證明類似得可以證明 a(bc) (ab)c 因此因此 a(bc) = (ab)c 由對偶原理可得由對偶原理可得 a(bc) = (ab)c 西安電子科技大學多媒體研究所 162022-7-37.17.1代數格的基本性質代數格的基本性質(8)由定理由定理1可知可知 aaa由自反性可知由自反性可知 a a由此可得由此可得 aa a因此因此 aa = a利用對偶原理可得利用對偶原理可得 aa = a(9)根據定理根據定理1可得可得 aa(ab)因為因為 a a, ab a 因此因此 a(ab ) a所以所以 a(a

11、b ) = a利用對偶原理，即得利用對偶原理，即得 a(ab) = a西安電子科技大學多媒體研究所 172022-7-37.17.1代數格的基本性質代數格的基本性質(10)首先證明首先證明ab ab=a因為因為ab和和aa,就有就有aab,但由定理但由定理1可知可知ab a,由反對稱性，得由反對稱性，得ab=a。這就證明了。這就證明了ab ab=a。反之，假定反之，假定ab=a，則，則a= abb,這就證明了這就證明了 ab=a ab因此因此ab ab=a用同樣得方法可以用同樣得方法可以ab ab=b西安電子科技大學多媒體研究所 182022-7-37.17.1代數格的基本性質代數格的基本性質

12、最后證明最后證明ab=a ab=b根據定理根據定理1可知可知abb,而而abb,因為因為ab=a,故故a b,而而bb,因此因此 abb,這樣就得到了這樣就得到了ab=b，即，即ab=a ab=b。反之，假定反之，假定ab=b, 由定理由定理1可知可知aba, 因為因為ab=b，故，故b=aba,而而aa,因此因此aba,這樣就這樣就得到了得到了ab=a,即即ab=b ab=a 。 因此得到因此得到ab=a ab=b西安電子科技大學多媒體研究所 192022-7-37.17.1代數格的基本性質代數格的基本性質(13)由定理由定理1可知可知 aab和和aac,由定理由定理2可知可知 a (ab)

13、 (ac) (1)另外由于另外由于 bcbab, bcc ac, 故故 b c (a b) (a c) (2) 因此由因此由(1)、(2)可得：可得：a(bc)(ab) (ac) 利用對偶原理，即得利用對偶原理，即得 a (b c) (a b)(a c) 西安電子科技大學多媒體研究所 202022-7-37.17.1代數格的基本性質代數格的基本性質(14)由性質由性質(10)有有 ac (ac) = c 再由性質再由性質(13)有有 a(bc) (ab) (ac) 用用c替代上式中的替代上式中的(ac)，即得，即得 a(bc) (ab) c所以所以 ac a(bc) (ab) c另外，若另外，

14、若a(bc) (ab) c,則明顯地有則明顯地有 a a(bc) (ab) c c所以所以a(bc) (ab) c ac 因此因此ac a(bc) (ab) c西安電子科技大學多媒體研究所 212022-7-37.17.1格格u定理定理設設是一個代數系統(tǒng)，其是一個代數系統(tǒng)，其中運算中運算和和都滿足吸收律，則運算都滿足吸收律，則運算和和 都滿足等冪律。都滿足等冪律。證明：由于證明：由于和和都滿足吸收律，則任取都滿足吸收律，則任取a,bA,有有 a (a b) = a (1) a (a b) = a (2)將將(1)式中的式中的b用用(ab)替換得替換得 a (a (ab) = a a=a 西安電

15、子科技大學多媒體研究所 222022-7-37.17.1格格將將(2)式中的式中的b用用(ab)替換得到替換得到 a (a (ab) = aa = a 故故 和和都滿足等冪律。都滿足等冪律。西安電子科技大學多媒體研究所 232022-7-37.17.1格格u定理定理設設是一個代數系統(tǒng)，其是一個代數系統(tǒng)，其中中和和都是二元運算且滿足交換律、結合都是二元運算且滿足交換律、結合律、吸收律，則律、吸收律，則A上存在偏序關系上存在偏序關系，使得，使得是一個格。是一個格。證明：在證明：在A上定義二元關系上定義二元關系為：任取為：任取a,bA,a b 當且僅當當且僅當 a b = a。(i)證明證明是一個偏

16、序關系是一個偏序關系。西安電子科技大學多媒體研究所 242022-7-37.17.1格格任取任取a,bA, aa = a,根據根據的定義可知的定義可知 aa,因此因此a是是自反自反的。的。設設ab, ba,則則a b = a = b,因此因此是是反對稱反對稱的。的。設設ab, bc,則有則有 a b = a 和和 bc = bac = ( a b) c = a ( b c ) =a b = a則有則有 a c。因此。因此是是傳遞傳遞的。的。因此可知因此可知是一個偏序集合。是一個偏序集合。 西安電子科技大學多媒體研究所 252022-7-37.17.1格格(ii)證明任取證明任取a,bA, a和

17、和b存在存在最小上界最小上界和和最大下界最大下界。因為因為(ab)a = aba = ab (ab)b = abb = ab因此因此ab a , abbab是是a和和b的下界。的下界。西安電子科技大學多媒體研究所 262022-7-37.17.1格格設設c是是a和和b的任意下界，即有的任意下界，即有ca且且cb,則有則有 ca = c且且cb = c而而 c(ab) = (ca) b = cb = c所以有所以有c ab。由此可知，。由此可知， ab是是a和和b的最大下的最大下界。界。同理可證，同理可證， ab是是a和和b的最小上界。的最小上界。由由(i)、(ii)可知，可知，是一個格。是一個

18、格。西安電子科技大學多媒體研究所 272022-7-37.27.2子格子格u子格：子格：設設是一個格，是一個格，是由是由所誘導的代數系統(tǒng)。所誘導的代數系統(tǒng)。S L且且S , 如果如果L中的兩個運算中的兩個運算和和在在S上是封閉的，上是封閉的，則稱則稱是是的子格。的子格。 格載體L的一個子集S如果對原對原保交和保聯運算都封閉保交和保聯運算都封閉，稱是的子格。子格是子代數的概念在格上的擴展。西安電子科技大學多媒體研究所 282022-7-37.27.2子格子格u【例題例題】圖圖(a)、(b)中所示的格中所示的格分別分別是格是格的子格嗎？的子格嗎？(a)abdcedeab(b)一個格中的部分元素在原

19、偏序關系上構成一個格，不能說明它就是原格的子格。主要看該子集上的任意兩個元素在原運主要看該子集上的任意兩個元素在原運算保交和保聯下的結果是否也在該子集算保交和保聯下的結果是否也在該子集中。中。abecdffacde西安電子科技大學多媒體研究所 292022-7-37.27.2格同態(tài)格同態(tài)u格同態(tài)：格同態(tài)：設設和和是兩個格，由它們所是兩個格，由它們所分別誘導的代數系統(tǒng)為分別誘導的代數系統(tǒng)為和和,其其中中和和是保交運算是保交運算, 和和是保聯運算。如是保聯運算。如果存在一個從果存在一個從L1到到L2的映射的映射f,使得任取使得任取a,bL1滿足滿足 f(ab)=f(a) f(b) f(ab)=f(

20、a) f(b)則稱則稱f為從為從到到的格同態(tài)，稱的格同態(tài)，稱為為的同態(tài)象。的同態(tài)象。西安電子科技大學多媒體研究所 302022-7-37.27.2格同態(tài)格同態(tài)u【例題例題】設集合設集合A=a,b,c,是一個格，其哈是一個格，其哈斯圖如圖斯圖如圖(a)所示。集合所示。集合B= (A),也是一個格，也是一個格，其哈斯圖如圖其哈斯圖如圖(b)所示。函數所示。函數f:AB,其中其中f(x)=y| yx。證明。證明:f是從是從到到的格同態(tài)。的格同態(tài)。(a)(b)abccb西安電子科技大學多媒體研究所 312022-7-37.27.2格同態(tài)格同態(tài)證明：證明：是一個格，設其誘導的代數格為是一個格，設其誘導的

21、代數格為，任取，任取a,bA,因為因為是一個鏈，是一個鏈，所以所以 a b=mina,b ab=maxa,b誘導的代數格為誘導的代數格為。(i)A中元素在函數中元素在函數f下的象分別為下的象分別為 f(a)=a, f(b)=a,b, f(c)=a,b,c故故f是從是從A到到B的單射函數。的單射函數。西安電子科技大學多媒體研究所 322022-7-37.27.2格同態(tài)格同態(tài)(ii)f(x1 x2)=f(minx1,x2)=y| yminx1,x2 =y| y x1 y| y x2 =f(x1) f(x2) f(x1 x2)=f(maxx1,x2)=y| ymaxx1,x2 =y| y x1 y|

22、 y x2 =f(x1) f(x2)故故f是從是從到到的格同態(tài)的格同態(tài)。西安電子科技大學多媒體研究所 332022-7-37.27.2格同態(tài)性質格同態(tài)性質u定理定理(格同態(tài)的保序性格同態(tài)的保序性) 設設f是從格是從格 到格到格的格同態(tài)，則對任意的格同態(tài)，則對任意x,yL1,如果如果xy,必有必有f(x) f(y)。 證明：因為證明：因為xy，所以有，所以有xy=x,又又 f(xy)=f(x) f(y) = f(x) 故故f(x) f(y)。西安電子科技大學多媒體研究所 342022-7-37.27.2格同構格同構u格同構：格同構：設設f是從格是從格到格到格的格的格同態(tài)，若同態(tài)，若f是雙射函數，

23、則稱是雙射函數，則稱f為從為從 到到的格同構。的格同構。u具有一具有一,二二,三個元素的格三個元素的格,分別是一、二分別是一、二,三三個元素的鏈個元素的鏈,四個和五個元素對應表中同構四個和五個元素對應表中同構格之一，如下表所示：格之一，如下表所示：西安電子科技大學多媒體研究所 352022-7-3哈斯圖哈斯圖1個元素的格個元素的格2個元素的格個元素的格3個元素的格個元素的格4個元素的互個元素的互不同構的格不同構的格5個元素的互個元素的互不同構的格不同構的格西安電子科技大學多媒體研究所 362022-7-37.37.3特殊的格：分配格特殊的格：分配格u分配格：分配格：設設是由格是由格所誘導所誘導

24、的代數系統(tǒng)，如果對任意的的代數系統(tǒng)，如果對任意的a,b,cL,滿足：滿足： a(bc) = (ab)(ac) 保交對保聯可分配保交對保聯可分配 a(bc) = (ab)(ac) 保聯對保交可分配保聯對保交可分配 則稱則稱是分配格。是分配格。 西安電子科技大學多媒體研究所 372022-7-37.37.3分配格分配格u【例題例題】圖圖(a)、(b)所示的格是分配格嗎？所示的格是分配格嗎？為什么？為什么？分析：均不是分配格?？紤]分析：均不是分配格。考慮b(cd)與與(b c)(b d)；考慮；考慮c (bd)與與(cb)(cd)cabde(a)鉆石格abcde(b)五角格西安電子科技大學多媒體研究

25、所 382022-7-37.37.3分配格分配格u定理定理設設是一個格，若是一個格，若運算對運算對運算可分配，則運算可分配，則對對也可分配，反之亦也可分配，反之亦然。然。證明：設證明：設運算對運算對運算可分配，即任取運算可分配，即任取a,b,cL,滿足滿足 a(bc) = (ab)(ac)現要證現要證 a(bc) = (ab)(ac)(ab)(ac) = (ab) a) (ab) c) = a (ab) c) 西安電子科技大學多媒體研究所 392022-7-37.37.3分配格分配格 = a(ac)(bc) = a(ac)(bc) = a(bc)由此可知，由此可知，運算對運算對運算也可分配。運

26、算也可分配。同理可證，若同理可證，若運算對運算對運算可分配，則運算可分配，則 運算運算對對運算也可分配。運算也可分配。西安電子科技大學多媒體研究所 402022-7-37.37.3分配格分配格u定理定理每個鏈都是分配格。每個鏈都是分配格。證明：設證明：設是一個鏈，則是一個鏈，則必是一個格。必是一個格。任取任取a,b,cL,討論以下兩種情況：討論以下兩種情況：(i)ab或或ac無論是無論是ab或或ac都有都有 a(bc)=a (ab)(ac) = a 即即 a(bc)= (ab)(ac) 西安電子科技大學多媒體研究所 412022-7-37.37.3分配格分配格(ii)ba且且ca:由由ba,

27、ca知知 bc a，可得，可得 a(bc )= bc 又因為又因為(ab) (ac) = bc ,所以有所以有 a(bc )= (ab) (ac) 由由(i)、(ii)可知可知運算對運算對運算可分配，于是運算可分配，于是運運算對算對運算也可分配。運算也可分配。故每個鏈都是分配格。故每個鏈都是分配格。西安電子科技大學多媒體研究所 422022-7-37.37.3分配格分配格u定理定理設設是一個分配格，那么對于是一個分配格，那么對于任意任意a,b,cL,如果有如果有ab=ac和和ab=ac成立，則必有成立，則必有b=c。證明：證明：b=b(ab)=b(ac) = (ba)(bc) =(ac) (b

28、c)=(ab)c = (ac) c = c西安電子科技大學多媒體研究所 432022-7-37.37.3分配格分配格u定理定理一個格是分配格，當且僅當它不一個格是分配格，當且僅當它不存在與鉆石格和五角格同構的子格。存在與鉆石格和五角格同構的子格。u定理定理分配格的子格是分配格。分配格的子格是分配格。西安電子科技大學多媒體研究所 442022-7-37.37.3有界格有界格u全上界全上界(全下界全下界)：如果格如果格中存在一個中存在一個元素元素a,對于任何元素對于任何元素bL,均有均有b a(a b),則則稱稱a為格為格的全上界的全上界(全下界全下界)。通常將。通常將全上界記為全上界記為“1”，

29、而將全下界記為，而將全下界記為“0”。u定理定理一個格一個格若有全上界若有全上界(全下界全下界)，則是唯一的。則是唯一的。西安電子科技大學多媒體研究所 452022-7-37.37.3有界格有界格u有界格：有界格：如果一個格既有全上界又有全下如果一個格既有全上界又有全下界，則稱該格為有界格。界，則稱該格為有界格。u定理定理設設是一個有界格，則對任意是一個有界格，則對任意aA,必有必有 a1 = 1, a1 = a a0 = a, a0 = 0u定理定理每個有限格都是有界格。每個有限格都是有界格。西安電子科技大學多媒體研究所 462022-7-37.37.3有補格有補格u補元：補元：設設是一個有

30、界格，對于是一個有界格，對于L中一中一個元素個元素a,如果存在元素如果存在元素bL,使得使得ab=0, ab=1,則稱元素則稱元素b是是a的補元，記為的補元，記為a=b。同時，同時，a也是也是b的補元，即的補元，即b=a。西安電子科技大學多媒體研究所 472022-7-37.37.3有補格有補格u【例題例題】寫出下圖所示的各有界格中所有寫出下圖所示的各有界格中所有元素的補元。元素的補元。1abc0c1bd0(b)(c)(d)(a)1a 010abc西安電子科技大學多媒體研究所 482022-7-37.37.3有補格有補格u有補格：有補格：在一個有界格中，若每個元素至在一個有界格中，若每個元素至

31、少有一個補元，則稱此格為有補格。少有一個補元，則稱此格為有補格。u【例題例題】下圖中各哈斯圖所表示的格是否下圖中各哈斯圖所表示的格是否是有補格？為什么？是有補格？為什么？01abcde10abcd10abcd01abcdef(a)(b)(c)(d)西安電子科技大學多媒體研究所 492022-7-37.37.3布爾格布爾格u布爾格：布爾格：若一個格既是有補格又是分配格，若一個格既是有補格又是分配格，則稱此格為布爾格。則稱此格為布爾格。u定理定理布爾格布爾格中，每一個元素都有中，每一個元素都有唯一的補元。唯一的補元。證明：證明： 是布爾格，因此是布爾格，因此L中的每一個元素都中的每一個元素都有補元

32、。設有補元。設aL, a有兩個補元有兩個補元b, cL,根據補元根據補元的定義有：的定義有：ab=0, ac=0 ab=1, ac=1根據分配格的性質可知：根據分配格的性質可知：b=c。西安電子科技大學多媒體研究所 502022-7-37.37.3布爾格布爾格u【例題例題】設設S是非空有限集合是非空有限集合,證明證明 是一個布爾格。是一個布爾格。證明：證明：是一個格，它誘導的代數格為是一個格，它誘導的代數格為。因為。因為,有全上界有全上界S和全和全下屆下屆 ，因此它是有界格。，因此它是有界格。任取任取T(S), =S T是是T的補元，因此它是有補格。的補元，因此它是有補格。和和是相互可分配的，

33、因此它是分配格。是相互可分配的，因此它是分配格。綜上所述，綜上所述，是一個布爾格。是一個布爾格。T西安電子科技大學多媒體研究所 512022-7-37.47.4布爾代數與布爾表達式布爾代數與布爾表達式u布爾代數：布爾代數：由布爾格由布爾格可以誘導出一個可以誘導出一個代數系統(tǒng)代數系統(tǒng)，該代數系統(tǒng)稱為布，該代數系統(tǒng)稱為布爾代數。爾代數。布爾格上的每個元素都有且僅有一個補元，因此布爾格誘導的代數系統(tǒng)有三個運算：保交、保聯和補運算，其中求補運算是一元運算。西安電子科技大學多媒體研究所 522022-7-37.47.4布爾代數布爾代數u【例題例題】求由布爾格求由布爾格所誘導的布所誘導的布爾代數系統(tǒng)。爾代

34、數系統(tǒng)。解答：解答：是由布爾格是由布爾格所所誘導的一個布爾代數，其中誘導的一個布爾代數，其中、和和 分別是集分別是集合的交、并和補運算。合的交、并和補運算。西安電子科技大學多媒體研究所 532022-7-37.47.4布爾代數布爾代數u有限布爾代數：有限布爾代數：載體含有有限個元素的布載體含有有限個元素的布爾代數稱為有限布爾代數。爾代數稱為有限布爾代數。u布爾代數的性質：設布爾代數的性質：設是一個布是一個布爾代數，任取爾代數，任取a,b,cB都有性質成立：都有性質成立：(1)交換律交換律 ab = ba, ab = b a(2)結合律結合律 a(bc) = (ab)c, a (b c) = (

35、a b) c西安電子科技大學多媒體研究所 542022-7-37.47.4布爾代數的性質布爾代數的性質(3)等冪律等冪律 aa = a, aa = a(4)吸收律吸收律 a(ab) = a, a(ab) = a(5)分配律分配律 a(bc) = (ab)(ac) a(bc) = (ab)(ac)(6)同一律同一律 a0 = a, a 1 = a(7)零一律零一律 a0 = 0, a1 = 1(8)互補律互補律 aa = 1, a a = 0(9)對合律對合律 (a) = a(10)德德.摩根律摩根律 (ab)= ab, (ab)=ab西安電子科技大學多媒體研究所 552022-7-37.47.

36、4布爾代數的性質布爾代數的性質證明證明:(10)(ab)(ab)=(aba) (abb) = (b(aa) (a(bb) = (b1)(a1) = 1 1 = 1 (ab) (ab)=(aab)(bab) = (aa)b) (bb )a) =(0 b) (0 a) = 00 = 0所以有所以有(ab)= ab。同理可證。同理可證(ab)=ab。西安電子科技大學多媒體研究所 562022-7-37.47.4布爾代數布爾代數u定理定理設設是一個代數系統(tǒng)，是一個代數系統(tǒng)， 和和是是B上的二元運算，如果對任意上的二元運算，如果對任意a,b,cB 均滿足以下四條性質，則稱均滿足以下四條性質，則稱 是一個

37、布爾代數。是一個布爾代數。(1)交換律交換律 ab = ba, ab = b a(2)分配律分配律 a(bc) = (ab)(ac) a(bc) = (ab)(ac)西安電子科技大學多媒體研究所 572022-7-37.47.4布爾代數布爾代數(3)同一律同一律 B中存在兩個元素中存在兩個元素1和和0，并且對，并且對B中任中任意元素意元素a,滿足滿足 a 1 = a, a 0 = a(4)互補律互補律 對對B中每個元素中每個元素a都存在唯一元素都存在唯一元素aB，滿足，滿足 a a = 0, a a = 1 西安電子科技大學多媒體研究所 582022-7-37.47.4有限布爾代數的原子表示有

38、限布爾代數的原子表示u本小節(jié)研究有限布爾代數的一個重要性質，本小節(jié)研究有限布爾代數的一個重要性質，就是任何有限布爾代數就是任何有限布爾代數都同構都同構于某有限集合于某有限集合S的冪代數的冪代數,這說這說明有限布爾代數有以下結構特征：明有限布爾代數有以下結構特征：(1)任何有限布爾代數，其載體元素個數是任何有限布爾代數，其載體元素個數是2的冪次。的冪次。(2)對每個正整數對每個正整數n,都存在具有都存在具有2n個元素的布爾格。個元素的布爾格。(3)對于元素個數相同的布爾代數都是同構的。對于元素個數相同的布爾代數都是同構的。西安電子科技大學多媒體研究所 592022-7-37.47.4有限布爾代數

39、的原子表示有限布爾代數的原子表示u覆蓋：覆蓋：設設a,b是一個格中的兩個元素，如果是一個格中的兩個元素，如果ba且且ba,即即ba,并且在此格中再沒有別的并且在此格中再沒有別的元素元素c,使得使得bc和和ca,則稱元素則稱元素a覆蓋元素覆蓋元素b。u原子：原子：設設是一個格，且具有全下界是一個格，且具有全下界0,如果有元素如果有元素aA, a蓋住蓋住0，則稱元素，則稱元素a為原為原子。子。西安電子科技大學多媒體研究所 602022-7-37.47.4有限布爾代數的原子表示有限布爾代數的原子表示u定理定理設設是一個布爾代數，是一個布爾代數，a和和b是該布爾代數的兩個原子，且有是該布爾代數的兩個原

40、子，且有ab,則則a b = 0。證明：證明：(反證法反證法)假設假設ab = c 0,因為因為ab,則有則有0 c a或或0 c b，這與，這與a和和b是原子相矛盾是原子相矛盾,故假設錯誤，有故假設錯誤，有ab = 0。西安電子科技大學多媒體研究所 612022-7-37.4Stone7.4Stone表示定理表示定理u定理定理(Stone表示定理表示定理)設設是是一個有限布爾格一個有限布爾格所誘導的一個有限布所誘導的一個有限布爾格代數，爾格代數，S是布爾格是布爾格的所有原子的的所有原子的集合集合,則則和和同構。同構。西安電子科技大學多媒體研究所 622022-7-37.4Stone7.4St

41、one表示定理的推論表示定理的推論u推論推論1有限布爾格的元素個數必定等于有限布爾格的元素個數必定等于2n,其中其中n是該布爾格中所有原子的個數。是該布爾格中所有原子的個數。u推論推論2任何一個具有任何一個具有2n個元素的有限布個元素的有限布爾代數都是同構的。爾代數都是同構的。西安電子科技大學多媒體研究所 632022-7-37.47.4布爾表達式布爾表達式u布爾常元：布爾常元：設設是一個布爾代數，是一個布爾代數，稱稱B中的元素為該布爾代數的布爾常元。中的元素為該布爾代數的布爾常元。u布爾變元：布爾變元：設設是一個布爾代數，是一個布爾代數，稱取值于稱取值于B中元素的變量為該布爾代數的布中元素的變量為該布爾代數的布爾變元。爾變元。西安電子科技大學多媒體研究所 642022-7-37.47.4布爾表達式布爾表達式u布爾表達式的歸納定義：布爾表達式的歸納定義：n單個布爾常元和單個布爾變元是布爾表達式。單個布爾常元和單