第6章格與布爾代數(shù)

1、格論是近代數(shù)學(xué)的一個(gè)重要分支，由它所引出的布爾格論是近代數(shù)學(xué)的一個(gè)重要分支，由它所引出的布爾代數(shù)在計(jì)算機(jī)科學(xué)中有很多直接應(yīng)用。代數(shù)在計(jì)算機(jī)科學(xué)中有很多直接應(yīng)用。第六章第六章 格與布爾代數(shù)格與布爾代數(shù)n 格的概念格的概念n分配格分配格n有補(bǔ)格有補(bǔ)格n布爾代數(shù)布爾代數(shù)n布爾表達(dá)式布爾表達(dá)式 , , , , Aa b c d e fa ca da ea fb cb db eb fc dc ec fd ed fa ab bc cd de eff( ), COV Aa cb cc dd ed f1、回憶偏序集回憶偏序集A，偏序關(guān)系：滿足自反性，反對稱性偏序關(guān)系：滿足自反性，反對稱性，傳遞性。傳遞性。有限

2、集合上的偏序集可用哈斯圖來表示：有限集合上的偏序集可用哈斯圖來表示： 6-1 6-1 格的概念格的概念 Hasse圖為圖為: a,b最小上界是最小上界是c,無最大下界無最大下界 e,f最大下界是最大下界是d,無最小上界無最小上界 因而任兩元素未必有最小上界，最大下界。因而任兩元素未必有最小上界，最大下界。而我們要介紹的而我們要介紹的格是一種特殊的偏序集格是一種特殊的偏序集任兩元素均有最小上任兩元素均有最小上界和最大下界界和最大下界 6-1 6-1 格的概念格的概念 例例1： I+,| a|b：a整除整除b 偏序關(guān)系。偏序關(guān)系。a,b最小上界：最小上界：a,b的最小公倍數(shù)的最小公倍數(shù) LCMa,

3、b最大下界：最大下界：a,b的最大公約數(shù)的最大公約數(shù) GCD I+,|是格是格 例例2：S集合集合 P(s), 偏序集。偏序集。 A,B P(s) A，B最小上界：最小上界： A B A，B最大下界：最大下界： A B 這一偏序集是格這一偏序集是格 2、格、格 A，是偏序集，若對是偏序集，若對 a,bA，a, b有最大下界和最有最大下界和最小上界，小上界，則則稱稱A，為格。為格。 一般可用一般可用Hasse圖表示格。圖表示格。6-1 6-1 格的概念格的概念 例：用圖形判斷含例：用圖形判斷含15個(gè)元素的格：個(gè)元素的格：13個(gè)元素個(gè)元素Hasse圖情況唯一圖情況唯一6-1 6-1 格的概念格的概

4、念 3、格、格A，誘導(dǎo)的代數(shù)系統(tǒng)：誘導(dǎo)的代數(shù)系統(tǒng)：在在A上定義兩個(gè)運(yùn)算上定義兩個(gè)運(yùn)算和和： a,bA，ab： a和和b的的最大下界最大下界 ：交運(yùn)算：交運(yùn)算 ab： a和和b的的最小上界最小上界 ：并運(yùn)算：并運(yùn)算則則A，稱為由格稱為由格A，誘導(dǎo)的代數(shù)系統(tǒng)誘導(dǎo)的代數(shù)系統(tǒng) 例：例：A=1，2，3，6。 A，|A， 也易求得也易求得 A，是是格格A，| 誘導(dǎo)的誘導(dǎo)的代數(shù)系統(tǒng)代數(shù)系統(tǒng)6-1 6-1 格的概念格的概念 4、格的對偶原理：、格的對偶原理： A， 有逆關(guān)系有逆關(guān)系c：； 而而A，也是一偏序關(guān)系也是一偏序關(guān)系 A，與與A，是互為對偶的是互為對偶的 A，是格，則是格，則A，也是格也是格 ab=a

5、cb 哈斯圖互為顛倒哈斯圖互為顛倒有有對偶原理對偶原理： 若若P是是A，格中真命題，若將格中真命題，若將P中中換成換成，換成換成，換成換成，則得到另一命題，則得到另一命題P，P是是P的對偶命題，且的對偶命題，且P也是真命題也是真命題 所以，在證明格有關(guān)的命題時(shí)，證明一個(gè)，則另一個(gè)對偶式所以，在證明格有關(guān)的命題時(shí)，證明一個(gè)，則另一個(gè)對偶式也成立也成立 。6-1 6-1 格的概念格的概念 (3)傳遞性傳遞性 ab， bc a c；ab, bc ac(4) aab；aba； bab；abb(5) ac, bc abc； ac, bc abc(6) ab, cd acbd (acbd )； ab, c

6、d acbd (acbd)(7)保序性保序性 bc abac, abac (8)交換性交換性 ab=ba; ab=ba; 5、格的基本性質(zhì)：、格的基本性質(zhì)：設(shè)設(shè)A，是格。是格。 (1)自反性自反性 aa | 對偶對偶 aa (2)反對稱性反對稱性 ab,ba a=b. | 對偶對偶 ab,ba a=b 6-1 6-1 格的概念格的概念 (9) 結(jié)合性結(jié)合性：a(bc）= (ab)c; a(bc)=(ab)c(10)等冪性等冪性：aa=a; aa=a(11)吸收性吸收性：a(ab)=a; a(ab)=a(12)分配不等式分配不等式： a(bc) (ab)(ac) (ab)(ac)a(bc)(13

7、) ab ab=a；ab ab=b (14)模不等式模不等式：ac a(bc)(ab)c 6-1 6-1 格的概念格的概念 6-1 6-1 格的概念格的概念 證：只證（證：只證（6）（）（11） 其他書上有其他書上有 (6) bbd ab abd acbd. dbd cd cbd 另一類似可證另一類似可證 (11) 要證要證 aa(ab) a(ab)a 第一式顯然成立第一式顯然成立aa aba a(ab) a a=a(ab) 6、格的等價(jià)原理、格的等價(jià)原理：格：格A， (1)引理引理6-1.1：A，代數(shù)系統(tǒng)，若代數(shù)系統(tǒng)，若, 滿足吸收性，滿足吸收性，則則, 滿足冪等性滿足冪等性證：證： a,b

8、A. a(ab)=a a(ab)=a. b用用ab代替代替(兩式中兩式中b是相互獨(dú)立的是相互獨(dú)立的) a(a(ab)=a 即即 aa=a. (2)格的等價(jià)定理：格的等價(jià)定理：A，代數(shù)系統(tǒng)，代數(shù)系統(tǒng)，.滿足交換性，滿足交換性，結(jié)合性，吸收性，則結(jié)合性，吸收性，則A上存在偏序關(guān)系上存在偏序關(guān)系，使，使A，是一個(gè)格是一個(gè)格 從格可引出代數(shù)系統(tǒng)從格可引出代數(shù)系統(tǒng)A，； 而從滿足三個(gè)條件的而從滿足三個(gè)條件的A，也可導(dǎo)出格也可導(dǎo)出格A，證明見書：（格中三個(gè)性質(zhì)很重要，決定了格）證明見書：（格中三個(gè)性質(zhì)很重要，決定了格）6-1 6-1 格的概念格的概念 6-1 6-1 格的概念格的概念 證：定義一個(gè)證：定義

9、一個(gè) ， a,b A,a bab=a.可證可證是一偏序關(guān)系。是一偏序關(guān)系。1）自反性）自反性 aa=a,a a (吸收性導(dǎo)出吸收性導(dǎo)出 冪等性冪等性)。 2）反對稱性）反對稱性 a b,b a ab=a,ba=b. 交換性交換性 ab=a=ba=ba=b a b 3)傳遞性傳遞性 a b ,b c ab=a,bc=b,ac=(ab)c=a(bc)=ab=a a c.故故是一偏序關(guān)系。是一偏序關(guān)系。 6-1 6-1 格的概念格的概念 4）下面證明）下面證明ab就是就是a,b的最大下界，即要證明的最大下界，即要證明 ab a,ab b 且最大且最大(ab)a=a(ba)=a(ab)=(aa)b=a

10、b(ab)b=a(bb)=abab a ,ab b 即即ab是是a和和b的下界。的下界。 設(shè)設(shè)c是是ab 的任一下界，即的任一下界，即c a,c b則則 ca=c, cb=cc(ab)=(ca)b=cb=c c ab故故 ab是是a和和b的最大下界的最大下界6-1 6-1 格的概念格的概念 若若ab=a 則則 ab=(ab)b=b反之，若反之，若ab=b 則則 ab=a(ab)=aab=aab=b故故A上偏序關(guān)系上偏序關(guān)系 a bab=aab=b 可類似證明得可類似證明得 ab是是a,b的最小上界。的最小上界。因此因此A, 是一個(gè)格是一個(gè)格5）下面證明）下面證明 ab=aab=b7、子格：、子

11、格： 由格由格A,誘導(dǎo)的代數(shù)系統(tǒng)為誘導(dǎo)的代數(shù)系統(tǒng)為A,。設(shè)。設(shè)B A,且且B，如果，如果A中的這兩個(gè)運(yùn)算中的這兩個(gè)運(yùn)算和和關(guān)于關(guān)于B是封閉的是封閉的（B中任兩元在中任兩元在A 中的中的最小上界和最大下界也在最小上界和最大下界也在B中），中），則則稱稱B,是是A, 的子格的子格例：例：I+，格格 I+ ，ab=LCM(a,b) ab=GCD(a,b)又又 兩個(gè)偶數(shù)的兩個(gè)偶數(shù)的GCD，LCM均是偶數(shù)。均是偶數(shù)。E+正偶數(shù)全體，正偶數(shù)全體，、封閉封閉 ， E+ ，是是 I+ ，的子格。的子格。注意：注意： A， 格，格，B A, B , B, 未必是格未必是格， 且若且若即使是格，也未必是子格。即使

12、是格，也未必是子格。6-1 6-1 格的概念格的概念 6-1 6-1 格的概念格的概念 8、格同態(tài)和格同構(gòu)、格同態(tài)和格同構(gòu) ： 設(shè)設(shè)A1, 1和和A2, 2都是格，它們誘導(dǎo)的代數(shù)系統(tǒng)分別都是格，它們誘導(dǎo)的代數(shù)系統(tǒng)分別是：是：A1,1,1和和A2,2,2。若存在映射。若存在映射f:A1A2使得使得對對 a,b A1,有有f(a1b)=f(a)2f(b), f(a1b)=f(a)2f(b)則則稱稱f是從是從A1,1,1到到A2,2,2的格同態(tài)的格同態(tài)，稱，稱f(A1),2為為格格A1,1的格同態(tài)象的格同態(tài)象。若若f是雙射是雙射，則稱，則稱f是從是從A1,1,1到到A2,1,1的格同構(gòu)的格同構(gòu)，稱，

13、稱A1,1和和A2,2格同構(gòu)的格同構(gòu)的。6-1 6-1 格的概念格的概念 兩個(gè)格同構(gòu)時(shí)，其哈斯圖是相同的，僅是標(biāo)記不同。兩個(gè)格同構(gòu)時(shí)，其哈斯圖是相同的，僅是標(biāo)記不同。6-1 6-1 格的概念格的概念 9、同態(tài)的性質(zhì)：、同態(tài)的性質(zhì)：（1）保序性保序性：設(shè)：設(shè)f是格是格A1, 1到到A2, 2的格同態(tài)，則的格同態(tài)，則 對對 x,y A1，若若x 1y,則必有則必有f(x) 2f(y)格同態(tài)必保序，但反之未必，保序的映射未必同態(tài)。格同態(tài)必保序，但反之未必，保序的映射未必同態(tài)。 （2）雙向保序性雙向保序性：設(shè)：設(shè)A1, 1和和A2, 2是格，是格，f是是A1到到A2的雙的雙射，則射，則 f是是A1,

14、1到到A2, 2的格同構(gòu)的格同構(gòu) 對對 a, b A1, a 1b當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)f(a) 2f(b) 6-1 6-1 格的概念格的概念 證：證：x1y，x 1y=x （格性質(zhì)）（格性質(zhì)）f(x1y)=f(x),f(x)2f(y)=f(x) f(x) 2f(y)6-1 6-1 格的概念格的概念 證 f:A1, 1A2, 2的格同構(gòu)由定理知 a,bA,a 1bf(a) 2f(b)反之設(shè)f(a) 2f(b) f(a)2f(b)=f(a)=f(a1b)f是雙射，a1b=a,故a1b已知a,bA,a 1bf(a) 2f(b)要證格同構(gòu)保運(yùn)算設(shè)a1b=c.要證f(a1b)=f(a)2f(b) f(a1b

15、)=f(a)2f(b)c 1a,c1bf(c) 2f(a) f(c)2f(b) f(a1b)= f(c) f(c)2f(a)2f(b)6-1 6-1 格的概念格的概念 設(shè)f(a)2f(b)=f(d) f滿射，則f(c) 2 f(d)而f(d) 2f(a),f(d) 2f(b)由條件d 1a,d 1b d 1a1b=c從而f(d)2f(c)故f(d)=f(c)即f(a)2f(b)=f(a1b)同理可得 f(a1b)=f(a)2f(b) f是格同構(gòu)。 格性質(zhì)中第格性質(zhì)中第12條有對任意格具有分配不等式：條有對任意格具有分配不等式：a(bc) (ab)(ac), (ab)(ac) a(bc)若上述兩

16、式變?yōu)榈仁剑礉M足分配律，則此格稱為分配格若上述兩式變?yōu)榈仁?，即滿足分配律，則此格稱為分配格1、分配格定義：、分配格定義： 設(shè)設(shè)A,是由格是由格A誘導(dǎo)的代數(shù)系統(tǒng)，若對誘導(dǎo)的代數(shù)系統(tǒng)，若對 a,b,c A有有a(bc)=(ab)(ac)和和a(bc)=(ab)(ac)則稱則稱A, 是分配格是分配格6-2 6-2 分配格分配格 例：例：S=a,b,c, P(s), 格，格， P(S),，對對 P，Q，R P( P(S), P(QR)=（PQ）(PR)P(QR)=（PQ）(PR)所以所以 P(P(S), 是分配格是分配格 格未必一定是分配格！格未必一定是分配格！6-2 6-2 分配格分配格 a ab

17、 bc cd de ea ab bc cd de e(a)(a)(b)(b)6-2 6-2 分配格分配格 2、分配格相關(guān)定理、分配格相關(guān)定理：在一個(gè)格中，若交運(yùn)算對于并運(yùn)算可分配，則并運(yùn)算對在一個(gè)格中，若交運(yùn)算對于并運(yùn)算可分配，則并運(yùn)算對交運(yùn)算也一定可分配，反之也成立（在分配格中定義中交運(yùn)算也一定可分配，反之也成立（在分配格中定義中兩兩個(gè)等式只要有一個(gè)成立即可將一個(gè)格判定為分配格個(gè)等式只要有一個(gè)成立即可將一個(gè)格判定為分配格）6-2 6-2 分配格分配格 證：對證：對 a,b,c若若a(bc)=(ab)(ac)則則(ab)(ac)=(ab)a)(ab)c)=a(ab)c)=a(ac)(bc)=(

18、a(ac)(bc)=a(bc)反之易得證反之易得證 2、分配格相關(guān)定理、分配格相關(guān)定理： 每個(gè)鏈?zhǔn)欠峙涓衩總€(gè)鏈?zhǔn)欠峙涓?6-2 6-2 分配格分配格 證：證：A, 偏序集偏序集 a,b A,有有a b或或b a，則，則A,是鏈。它的哈斯圖排成直線。顯然是鏈。它的哈斯圖排成直線。顯然A,是格。只是格。只要證要證 a,b,c A有有 a(bc)=(ab)(ac)即可。即可。 2、分配格相關(guān)定理、分配格相關(guān)定理： 每個(gè)鏈?zhǔn)欠峙涓衩總€(gè)鏈?zhǔn)欠峙涓?6-2 6-2 分配格分配格 分兩種情況：分兩種情況：（1）ab或或ac(a不是最大元（三者中）不是最大元（三者中）) （2）ba且且ca（三者中（三者中a最

19、大）最大） 無論無論bc或或cb, a(bc)=a. (ab)(ac)=aa(bc)=(ab)(ac) bca, a(bc)=bc,(ab)(ac)=bc a(bc)=(ab)(ac) 2、分配格相關(guān)定理、分配格相關(guān)定理：cbcabacabaAcbaA有若是分配格，則對,6-2 6-2 分配格分配格 cbbbabcabcbbacbcacbacccacb)()()()()()()()a（證：（定理：定理：一個(gè)一個(gè)格是分配格（元素格是分配格（元素5）的充要條件）的充要條件是該格中沒有任是該格中沒有任何一個(gè)子格與書何一個(gè)子格與書P244中圖中圖6-2.2（a）或（）或（b）中的任一個(gè)同構(gòu)。）中的任一

20、個(gè)同構(gòu)。6-2 6-2 分配格分配格 a ab bc cd de ea ab bc cd de e(a)(a)(b)(b)n=1,2,3,4時(shí)情形易證時(shí)情形易證aced f子格子格bbdecf與其同構(gòu)，所以與其同構(gòu)，所以不是分配格不是分配格6-2 6-2 分配格分配格 , , ,a()()(14,AAa b cAcabcabcA 是由格誘導(dǎo)的代數(shù)系統(tǒng)，若對當(dāng)時(shí)有 第性質(zhì)有關(guān)）則稱是模格。定理：分配格是模格。定理：分配格是模格。6-2 6-2 分配格分配格 3、模格定義：、模格定義：, ,.,()()()(),Aa b cAacacc acaabcacbcabcA證：是分配格，對若則是模格。ab

21、cde不是模格，不是模格，也不是分配格也不是分配格dc,但c (db)=ca=c d (cb)=de=dabecd是模格，是模格，不是分配格不是分配格6-2 6-2 分配格分配格 abecd是模格，是模格，不是分配格不是分配格6-2 6-2 分配格分配格 用定義證明用定義證明 任意任意xy, x (yz)=(xz) y.若若x=y時(shí)時(shí) 此時(shí)顯然成立（吸收性）此時(shí)顯然成立（吸收性）討論討論xy,xy的情形的情形 只有取只有取x=e或或y=a時(shí)才可能有時(shí)才可能有xy. （1）x=e時(shí)時(shí) y=b,c,d 類似（對稱）類似（對稱）6-2 6-2 分配格分配格 不妨取不妨取x=e,y=b.則則e (bz

22、)=bz (ez) b=zbe最小最小等式成立。等式成立。（2） y=a,x=b時(shí)時(shí) b (az)=bz , (bz) a=bz (a最大最大)等式成立等式成立因而，模格未必是分配格因而，模格未必是分配格1、有界格：、有界格： A,是格，若是格，若 aA時(shí)，時(shí)， xA, 都有都有ax,則稱則稱a為為格格A,的全下界，記為的全下界，記為0定理：一個(gè)格定理：一個(gè)格A,若有若有全下界，則是唯一的全下界，則是唯一的（即（即A的最小元的最小元） A,是格，若是格，若 bA, xA,都有都有xb,則稱則稱b為格為格A,的全上界，記為的全上界，記為1定理：一個(gè)格定理：一個(gè)格A,若有若有全上界，則是唯一的全上

23、界，則是唯一的（即（即A的最大元的最大元）6-3 6-3 有補(bǔ)格有補(bǔ)格 反證法：假設(shè)有兩個(gè)全下界反證法：假設(shè)有兩個(gè)全下界a,bA,a b因?yàn)橐驗(yàn)閍是全下界，是全下界，bA,所以所以ab又又b是全下界，是全下界，aA,所以所以ba,從而從而a=b矛盾，所以矛盾，所以a唯一。唯一。例：例：, S有限集，全下界為有限集，全下界為 ，全上界為，全上界為S，則為有界格，則為有界格定理定理：A,是有界格，則對是有界格，則對 aA,必有必有a0=a, a1=aa0=0, a1=1即即0，1分別是分別是 ，的幺元，又分別是的幺元，又分別是 ， 的零元的零元若一個(gè)格存在全上界和全下界，則稱該格為若一個(gè)格存在全上

24、界和全下界，則稱該格為有界格有界格6-3 6-3 有補(bǔ)格有補(bǔ)格 6-3 6-3 有補(bǔ)格有補(bǔ)格 證明：證明：因?yàn)橐驗(yàn)閍a,0是全下界，所以是全下界，所以 0 a,所以所以 a0a又又a0a 故故a0=a.因?yàn)橐驗(yàn)?是全下界是全下界 a0A, 所以所以 0a0而而a00 所以所以a0=0,其他兩個(gè)同理類似可證其他兩個(gè)同理類似可證 2、有補(bǔ)格：、有補(bǔ)格：（1）補(bǔ)元定義）補(bǔ)元定義：A,是有界格，對于是有界格，對于aA,若存在若存在bA，使得使得ab=1,和和ab=0，則稱則稱b是是a的補(bǔ)元的補(bǔ)元。b是是a的補(bǔ)元，則稱的補(bǔ)元，則稱a也是也是b的補(bǔ)元（的補(bǔ)元（互為補(bǔ)元互為補(bǔ)元） 在有界格中，一個(gè)元素，可以

25、沒有補(bǔ)元，也可以有多個(gè)補(bǔ)元在有界格中，一個(gè)元素，可以沒有補(bǔ)元，也可以有多個(gè)補(bǔ)元b沒有補(bǔ)元沒有補(bǔ)元 0-1互為補(bǔ)元互為補(bǔ)元a,d是是e的補(bǔ)元的補(bǔ)元 a:補(bǔ)元補(bǔ)元ec,e是是d的的 補(bǔ)元補(bǔ)元 b無補(bǔ)元無補(bǔ)元c:補(bǔ)元為補(bǔ)元為d1 10 0C Ca ab bd de e6-3 6-3 有補(bǔ)格有補(bǔ)格 （2）有補(bǔ)格定義有補(bǔ)格定義：在一個(gè)：在一個(gè)有界格中，每個(gè)元素都至少有有界格中，每個(gè)元素都至少有一個(gè)補(bǔ)元一個(gè)補(bǔ)元，則稱此格，則稱此格為有補(bǔ)格為有補(bǔ)格例：例： 下圖中都是有補(bǔ)格下圖中都是有補(bǔ)格111000ababcdabcd6-3 6-3 有補(bǔ)格有補(bǔ)格 （3）定理：在）定理：在有界分配格中有界分配格中，若元素，

26、若元素a有補(bǔ)元素，則必是有補(bǔ)元素，則必是唯一的唯一的 證明：設(shè)證明：設(shè)a有兩個(gè)補(bǔ)元有兩個(gè)補(bǔ)元b,c，則，則ab=1=ac ab=0=ac有分配格性質(zhì)可得：有分配格性質(zhì)可得：b=c（4）布爾格：一個(gè)格若）布爾格：一個(gè)格若既是有補(bǔ)格，又是分配格，則稱既是有補(bǔ)格，又是分配格，則稱為有補(bǔ)分配格，也稱布爾格為有補(bǔ)分配格，也稱布爾格。其中的任一元素。其中的任一元素a的唯一補(bǔ)的唯一補(bǔ)元用元用 來記，即是來記，即是a的補(bǔ)元。的補(bǔ)元。 a6-3 6-3 有補(bǔ)格有補(bǔ)格 首先，格是由偏序集首先，格是由偏序集A,引出的引出的 若其中每任兩元有最小上界，最大下界，則為若其中每任兩元有最小上界，最大下界，則為格格 若格滿

27、足分配等式，誘導(dǎo)運(yùn)算若格滿足分配等式，誘導(dǎo)運(yùn)算，可分配，則為可分配，則為分配格分配格若格有若格有0，1，則為，則為有界格有界格若有界格中任一元有補(bǔ)元，則為若有界格中任一元有補(bǔ)元，則為有補(bǔ)格有補(bǔ)格分配格分配格+有補(bǔ)格有補(bǔ)格=布爾格布爾格小小 結(jié)結(jié)模格模格未必是分配格，分配格必是模格未必是分配格，分配格必是模格 a,b A, 是格是格 1. a b a b （a，b 可以無關(guān)系可以無關(guān)系 ） 2.有界格未必是有界格未必是有限格有限格，而有限格必是有界格，而有限格必是有界格 偏序集偏序集A, 格格分配格分配格有界格有界格有補(bǔ)格有補(bǔ)格布爾格布爾格偏序集偏序集格格分配格分配格有界格有界格有補(bǔ)格有補(bǔ)格布爾

28、格布爾格小小 結(jié)結(jié)1、布爾代數(shù)：、布爾代數(shù)： 由由布爾格布爾格誘導(dǎo)的誘導(dǎo)的代數(shù)系統(tǒng)代數(shù)系統(tǒng)稱為布稱為布爾代數(shù)爾代數(shù)6-4 6-4 布爾代數(shù)布爾代數(shù),.: ,AAaAaaAA 布爾格可誘導(dǎo)布爾代數(shù)另外定義運(yùn)算對補(bǔ)運(yùn)算是 的補(bǔ)元。是由布爾格所誘導(dǎo)的代數(shù)系統(tǒng)。_( ),S( ),S( ).( ), , ,sAs AAss 例：有界格： ， ；分配格；它是布爾格誘導(dǎo)的布爾格代數(shù)為：6-4 6-4 布爾代數(shù)布爾代數(shù) a,b,cb,ca,cbc aa,b若：若：S=a,b,c, , ,1a23AaababDeMorganabab 是布爾代數(shù)：（ （）（ ）律（ ）6-4 6-4 布爾代數(shù)布爾代數(shù) 2、性質(zhì)

29、：、性質(zhì)：6-4 6-4 布爾代數(shù)布爾代數(shù) _(1)(a)(2)()1,)()0)()1)1 11)()000aaaaba baba baba babaabbaa baaba baa bba baba 證： 與 互補(bǔ)， 要證（ （_b另以類似可證。3、布爾代數(shù)的同構(gòu)、布爾代數(shù)的同構(gòu)121211221212_1211221),B,:,()( )( )()( )( )( )( ),AfABa bAf abf af bf abf af bf af afABAA 定義：和是兩個(gè)布爾代數(shù)若存在雙射使得對則稱 是從的布爾同構(gòu)映射2）著重研究）著重研究有限布爾代數(shù)之間的同構(gòu)有限布爾代數(shù)之間的同構(gòu)6-4 6-

30、4 布爾代數(shù)布爾代數(shù) 4、有限布爾代數(shù)：、有限布爾代數(shù)： 是布爾代數(shù)，若是布爾代數(shù)，若A是有限集，則稱是有限集，則稱為為有限布爾代數(shù)有限布爾代數(shù) 對于有限布爾代數(shù)，對于有限布爾代數(shù)，、若若|A|=|B|，則，則A B，而且對，而且對任一有限布爾代數(shù)系統(tǒng)，元素個(gè)任一有限布爾代數(shù)系統(tǒng)，元素個(gè)數(shù)必有數(shù)必有2 2n n （1）原子：）原子：是格，且存在全下界是格，且存在全下界0，若，若aA，a蓋住蓋住0，則稱，則稱a為原子為原子（第一個(gè)比（第一個(gè)比0大的元素）大的元素）6-4 6-4 布爾代數(shù)布爾代數(shù) d, e是原子是原子de，de=0一般來說，任兩個(gè)原子交必為一般來說，任兩個(gè)原子交必為0 aced0

31、1b定理定理：A，是有下界是有下界0的有限格，則對于的有限格，則對于 b0，bA，都存在原子都存在原子aA,使得使得ab。（即一定有某條路徑，往下走。（即一定有某條路徑，往下走經(jīng)過原子到達(dá)經(jīng)過原子到達(dá)0）6-4 6-4 布爾代數(shù)布爾代數(shù) 定理定理：A，是有下界是有下界0的有限格，則對于的有限格，則對于 b0，bA，都存在原子都存在原子aA,使得使得ab。（即一定有某條路徑，往下走。（即一定有某條路徑，往下走經(jīng)過原子到達(dá)經(jīng)過原子到達(dá)0）6-4 6-4 布爾代數(shù)布爾代數(shù) 證：（證：（1）若）若b是原子，則是原子，則bb成立。成立。 （2）若）若b不是原子，一定存在不是原子，一定存在b1,使得使得0

32、b1bb1b若若b1b1是原子，則成立。是原子，則成立。若若b1b1不是原子，存在不是原子，存在b2A,b2A,使得使得0b2b1b0b2b1bA A，是有限格是有限格經(jīng)過有限步，找到經(jīng)過有限步，找到0bi0bib2b1b,b2b1b, 而而bibi是原子是原子 bibbi有限布爾代數(shù)中，有限布爾代數(shù)中，0bA，a1,a2ak是所有滿足是所有滿足aib的原子，則的原子，則 b=a1a2ak并且這種表示是唯一的并且這種表示是唯一的（也就是說，任一非零元，我們可用原子來唯一表示它。）（也就是說，任一非零元，我們可用原子來唯一表示它。）6-4 6-4 布爾代數(shù)布爾代數(shù) 分兩部分證明：分兩部分證明：

33、1）引理：）引理：A， 有限布爾代數(shù)，有限布爾代數(shù)，0bA， a1,a2,ak是所有滿足是所有滿足aib的原子，的原子， 則則b=a1a2ak（2 2）StoneStone表示定理：表示定理：6-4 6-4 布爾代數(shù)布爾代數(shù) 證：記證：記a1a2ak=c,要證要證b=caib b是是a1,a2,ak的上界的上界而而c是是a1,a2,ak的最小上界的最小上界 cb下證下證bc用上述引理只要證用上述引理只要證b =0反證：設(shè)反證：設(shè)b 0，則存在原子，則存在原子a，使得，使得0ab而而b b ab,a而而a1,a2,ak是是 aib的所有原子的所有原子 aac而而a 故故a c=0 a=0與與a是

34、原子矛盾是原子矛盾 故故b =0 bc 從而從而b=ccccccccc1, 2,a aak（2 2）StoneStone表示定理：表示定理：6-4 6-4 布爾代數(shù)布爾代數(shù) 2) 表示法是唯一的表示法是唯一的 b=a1a2ak，假設(shè)，假設(shè)b=b1b2bt， bi（i=1t）是原子）是原子1, 2,b bbt,1, 2,a aak1, 2,a aak( 12)aaak1, 2,b bbt,( 12)bbbtbib bi tk要證 t=k 反證法假設(shè)tk 至少存在ai ai =ai分配展開 (aib1)（aib2）（aibt）=（aia1）（aia2）（aiai）（aiak）a,b 是原子，是原子

35、，a b時(shí)，時(shí)，ab =0。左邊左邊=0，右邊，右邊=ai，ai=0矛盾，矛盾，t=k（2 2）StoneStone表示定理：表示定理：引理引理3：布爾格：布爾格中，對于任意原子中，對于任意原子aA，另一個(gè)元素，另一個(gè)元素b0，bA，則則ab,和和a 中有且僅有一個(gè)成立。中有且僅有一個(gè)成立。 b6-4 6-4 布爾代數(shù)布爾代數(shù) b證：（證：（1）假設(shè)）假設(shè)ab ，a ，則，則ab =0，a =0與與a 是原子矛盾是原子矛盾兩式不可能同時(shí)成立。兩式不可能同時(shí)成立。 bb（2）至少有一個(gè)成立。）至少有一個(gè)成立。a ba，a 是原子是原子 。 ab=0或或a b =a。 若若a b=0，則，則a （

36、 ）=0，a .若若a b=a，則，則ab.b（2 2）StoneStone表示定理：表示定理：Stone表示定理表示定理：有限布爾代數(shù)，有限布爾代數(shù)，S是是中所中所有原子的集合，則有原子的集合，則 6-4 6-4 布爾代數(shù)布爾代數(shù) （3 3）StoneStone表示定理的推論：表示定理的推論：有限布爾格元素個(gè)數(shù)必定等于有限布爾格元素個(gè)數(shù)必定等于2 2n n ，n n 是原子個(gè)數(shù)，即是原子個(gè)數(shù)，即|A|=|A|=2 2n n =|P(s)| =|P(s)|任何兩個(gè)具有相同元素個(gè)數(shù)的有限次布爾代數(shù)是同構(gòu)的任何兩個(gè)具有相同元素個(gè)數(shù)的有限次布爾代數(shù)是同構(gòu)的|P(S)|= |P(Q)|P(S)|= |

37、P(Q)|S|=|Q|S|=|Q|6-4 6-4 布爾代數(shù)布爾代數(shù) 1 1、布爾表達(dá)式：、布爾表達(dá)式：（1 1）布爾變元：取值為）布爾變元：取值為A A中元素的變元（中元素的變元（布爾代數(shù)布爾代數(shù)) )（2 2）布爾常元：）布爾常元：A A中元素中元素（3 3）布爾表達(dá)式布爾表達(dá)式按下列規(guī)則定義：按下列規(guī)則定義： 單個(gè)布爾常元是布爾表達(dá)式單個(gè)布爾常元是布爾表達(dá)式如果如果e1,e2e1,e2是布爾表達(dá)式，則是布爾表達(dá)式，則 ,(e1e2),(e1e2)，（，（e1e2e1e2）是布爾表達(dá)式是布爾表達(dá)式 單個(gè)布爾變元是布爾表達(dá)式單個(gè)布爾變元是布爾表達(dá)式e1只有有限次使用（只有有限次使用（1）（）（

38、3）后得到的符號串是布爾表達(dá)式）后得到的符號串是布爾表達(dá)式 6-5 6-5 布爾表達(dá)式布爾表達(dá)式 布爾表達(dá)式的定義類似于以前所介紹的命題邏輯中布爾表達(dá)式的定義類似于以前所介紹的命題邏輯中的命題公式，謂詞邏輯中的謂詞公式。它們之間有一定的命題公式，謂詞邏輯中的謂詞公式。它們之間有一定的聯(lián)系，以后我們就可以看出，命題邏輯是一種特殊的的聯(lián)系，以后我們就可以看出，命題邏輯是一種特殊的布爾代數(shù)（取值布爾代數(shù)（取值T T或或F F）。因而研究布爾代數(shù)很有意義。）。因而研究布爾代數(shù)很有意義。例：例： 布爾代數(shù)布爾代數(shù)ax1 ax1 一元布爾表達(dá)式一元布爾表達(dá)式b b 二元布爾表達(dá)式二元布爾表達(dá)式 x 1x

39、26-5 6-5 布爾表達(dá)式布爾表達(dá)式 2 2、 n n元布爾表達(dá)式：元布爾表達(dá)式： 含有含有n n個(gè)不同的布爾變元的表達(dá)式，記為個(gè)不同的布爾變元的表達(dá)式，記為E(xE(x1 1，x xn n) )。布爾表達(dá)式的值布爾表達(dá)式的值：將：將A A中的元素代入表達(dá)式中變元中的元素代入表達(dá)式中變元, ,所得到的所得到的值，也稱值，也稱對表達(dá)式賦值對表達(dá)式賦值. .例：例： 布爾代數(shù)布爾代數(shù)含四個(gè)元素的布爾格一定是此形狀含四個(gè)元素的布爾格一定是此形狀：0是是全下界，全下界，1是全上界；而是全上界；而a、b必?zé)o關(guān)系，必?zé)o關(guān)系，否則否則a無補(bǔ)元，不是布爾格無補(bǔ)元，不是布爾格ab01E(x1,x2) = (1

40、x1)x2 二元布爾表達(dá)式二元布爾表達(dá)式取取x1=a,x2=b, E(a,b) = (1a)b=ab=1 6-5 6-5 布爾表達(dá)式布爾表達(dá)式 3、 n元布爾表達(dá)式的等價(jià)（相等）：元布爾表達(dá)式的等價(jià)（相等）： E1(x1,x2,xn)和和E2(x1,x2,xn)，若對任意的，若對任意的An，兩布爾表達(dá)式的值相等，則稱，兩布爾表達(dá)式的值相等，則稱E1和和E2等價(jià)等價(jià)，記記 E1(x1,x2,xn)=E2(x1,x2,xn) （即任意賦值相等則等價(jià)）（即任意賦值相等則等價(jià)）例：例：布爾代數(shù)布爾代數(shù)E1(x1,x2,x3) = ( x1 x1x2) E2(x1,x2,x3) = ( 13)xxx1

41、(x2 x3)由由布爾格，可直接利用其性質(zhì)化簡得布爾格，可直接利用其性質(zhì)化簡得E1=E2（分配性）（分配性）6-5 6-5 布爾表達(dá)式布爾表達(dá)式 6-5 6-5 布爾表達(dá)式布爾表達(dá)式 4、 布爾函數(shù)布爾函數(shù)在在 布爾代數(shù)中，布爾代數(shù)中，a,bA， E(x1,x2,xn) abA；abA； AaEAn元布爾表達(dá)式是元布爾表達(dá)式是AnA的函數(shù)的函數(shù)若函數(shù)若函數(shù)An A是是n元布爾表達(dá)式元布爾表達(dá)式 則為則為布爾函數(shù)布爾函數(shù). 對對 ，是否任一，是否任一AnA的函數(shù)都是布爾表達(dá)式？的函數(shù)都是布爾表達(dá)式？不一定！不一定！6-5 6-5 布爾表達(dá)式布爾表達(dá)式 5、布爾表達(dá)式的析取，合取范式：、布爾表達(dá)式

42、的析取，合取范式：在命題邏輯中，我們討論了任一命題公式的主析取，在命題邏輯中，我們討論了任一命題公式的主析取，主合取范式。主析取范式是小項(xiàng)的并，主合取范式是大項(xiàng)主合取范式。主析取范式是小項(xiàng)的并，主合取范式是大項(xiàng)的交，即將命題公式規(guī)范化；類似地，我們引進(jìn)布爾小項(xiàng)，的交，即將命題公式規(guī)范化；類似地，我們引進(jìn)布爾小項(xiàng)，布爾大項(xiàng)。布爾大項(xiàng)。（1）布爾小項(xiàng)布爾小項(xiàng)： 其中其中 是是xi或或 （2）布爾大項(xiàng)布爾大項(xiàng)： 其中其中 是是xi或或ixxi大項(xiàng)，小項(xiàng)各有大項(xiàng)，小項(xiàng)各有2n個(gè)，用個(gè)，用m0，m1， 表示小項(xiàng)表示小項(xiàng) 用用M0，M1， 表示大項(xiàng)表示大項(xiàng)21nm21nM21210 ()1 () 0110

43、10nnmimjijMiMjijmmmMMMx1x2xn x1x2xn ixxi6-5 6-5 布爾表達(dá)式布爾表達(dá)式 （3）析取范式析取范式：是形如下列的布爾表達(dá)式：是形如下列的布爾表達(dá)式 m0 = m1 = = 其中其中 （i=0,1, ）A，mi為布爾小項(xiàng)（類似于命題邏為布爾小項(xiàng)（類似于命題邏輯中的主析取范式）輯中的主析取范式）2121( 0)( 1)()nnm0m1m12xxxn 12xxxnx1x2xn21nmi6-5 6-5 布爾表達(dá)式布爾表達(dá)式 （4）合取范式合取范式：是形如下列的布爾表達(dá)式，其中：是形如下列的布爾表達(dá)式，其中Mi為布爾大項(xiàng)為布爾大項(xiàng)2121( 0M )( 1M )

44、(M)nn01 A 有有|A|種取法種取法因而共有因而共有 個(gè)不同的析取范式和合取范式個(gè)不同的析取范式和合取范式而而f：AB有有 個(gè)不同函數(shù)個(gè)不同函數(shù)f： A 有有 個(gè)不同函數(shù)個(gè)不同函數(shù)ii|A|B| |nAAnAn2|A|6-5 6-5 布爾表達(dá)式布爾表達(dá)式 定理：定理：布爾代數(shù)布爾代數(shù)上的上的任一布爾表達(dá)式任一布爾表達(dá)式E(x1,x2,xn)都都唯一地等價(jià)于某個(gè)析取范式，或者唯一唯一地等價(jià)于某個(gè)析取范式，或者唯一地等價(jià)于某個(gè)合取范式地等價(jià)于某個(gè)合取范式 因而由此定理，我們已知共有因而由此定理，我們已知共有 個(gè)不同的析取范式。個(gè)不同的析取范式。共有個(gè)不同的布爾表達(dá)式共有個(gè)不同的布爾表達(dá)式 / 布爾函數(shù)。布爾函數(shù)。AnA的布爾函數(shù)只有個(gè)。的布爾函數(shù)只有個(gè)。 而函數(shù)有而函數(shù)有 個(gè)不同函數(shù)。個(gè)不同函數(shù)。 n2|A|