第六章格和布爾代數(shù)

1、第六章 格和布爾代數(shù)2014-2015 學(xué)年第二學(xué)期陳磊6.1 格的概念 對(duì)于偏序集來(lái)說(shuō),它的任一子集不是必定存在最小上界或最大下界的.【例】由右圖所示的偏序集中, 2,3的最小上界是6, 但沒(méi)有最大下界 24,36的最大下界是12,但沒(méi)有最小上界 約定 把a(bǔ),b的最小上界(最大下界)稱為 元素a,b的最小上界(最大下界). 有沒(méi)有一種偏序集使得任何兩個(gè)元素都有最小上界和最大下界? 定義6-1.1 設(shè)A, 是一個(gè)偏序集，如果A中任意兩個(gè)元素都有最小上界和最大下界，則稱A, 是格?！纠?.設(shè)I+表示所有的正整數(shù),定義I+上的二元關(guān)系為整除關(guān)系|,則是一個(gè)偏序關(guān)系.進(jìn)一步,任意兩個(gè)元素的最大下界

2、就是兩個(gè)數(shù)的最大公約數(shù),而最小上界為兩個(gè)數(shù)的最小公倍數(shù),因此是格 2.也是格,任意兩個(gè)元素S1,S2,最大下界為S1S2,最小上界為S1S2【例】下圖中給出了一些偏序集的哈斯圖，判斷它們是否構(gòu)成格。 定義6-1.2 設(shè)A, 是一個(gè)格, 如果在A上定義兩個(gè)二元運(yùn)算和,使得對(duì)于任意的a,b A, ab等于a和b的最小上界, ab等于a和b的最大下界,那么就稱 為由格所誘導(dǎo)的代數(shù)系統(tǒng), 二元運(yùn)算和稱為并運(yùn)算和交運(yùn)算.【例】S=a,b, P(S)=?,a,b,a,b, 那么是一個(gè)格由這個(gè)格所誘導(dǎo)的代數(shù)系統(tǒng)為, 其中是集合的并, 是集合的交, 這兩個(gè)運(yùn)算的運(yùn)算表見(jiàn)下表 aabba,baaaa,ba,ba

3、,bbba,ba,ba,ba,ba,bba,ba,baba,baaabbba,baba,b 定義6-1.3 設(shè)A, 是一個(gè)格，由A, 誘導(dǎo)的代數(shù)系統(tǒng)A,設(shè) BA且B?, 如果A中兩個(gè)運(yùn)算和關(guān)于B是封閉的，則稱B, 是A, 的子格。 子格一定是格【例】 是一個(gè)格,E+是正偶數(shù)的全體,則是的一個(gè)子格 注 對(duì)于格,B是A的非空子集, 也是一個(gè)偏序集 不一定是格 即使是格,也不一定是的子格【例】設(shè)是一個(gè)格,其中S=a,b,c,d,e,f,g,h,哈斯圖如下所示S1=a,b,d,fS2=c,e,g,hS3=a,b,c,d,e,g,h, ,都是格,其中和是的子格,而,不是的子格. 設(shè)A, 是一個(gè)偏序集,

4、在A上定義一個(gè)新的二元關(guān)系R, 使得對(duì)于A中兩個(gè)元素a,b, 有關(guān)系a Rb當(dāng)且僅當(dāng)b a 也是一個(gè)偏序集 A, 和稱為是彼此對(duì)偶的 若A, 是一個(gè)格,則也是一個(gè)格 R一般用 表示 設(shè)P是對(duì)任意格都為真的命題, 如果在命題P中把 換成 , 換成，換成, 就得到另一個(gè)命題P1, 稱P1為P的對(duì)偶命題. 同時(shí)P1對(duì)任意格也是真命題 定理6-1.1在一個(gè)格A, 中,對(duì)任意的a,b A, 都有 a ab, b ab ab a, ab b 定理6-1.2在一個(gè)格A, 中,對(duì)于a,b,c,d A, 如果a b和c d,則 ac bd, ac bd 推論 在一個(gè)格A, 中, 對(duì)于a,b,c A, 如果b c

5、, 則ab ac, ab ac. 這個(gè)性質(zhì)稱為格的保序性 定理6-1.3 設(shè)A, 是一個(gè)格，由格A, 所誘導(dǎo)的代數(shù)系統(tǒng)為A, 則對(duì)任意的a,b,c,dA有 ab=ba， ab=ba (交換律) (ab)c=a(bc) (ab)c=a(bc) (結(jié)合律) aa= a， aa= a (冪等律) a(ab)=a a(ab)=a (吸收律) 引理6-1.1 設(shè)A,是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足吸收性，則和滿足冪等性。 定理6-1.4 設(shè)A,是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換性、結(jié)合性和吸收性，則A上存在偏序關(guān)系 ，使A, 是一個(gè)格。 定理6-1.5 在一個(gè)格A, 中，對(duì)任意的a,b

6、,cA, 都有 a(bc) (ab)(ac) (ab)(ac) a(bc) 定理6-1.6 設(shè)A, 是一個(gè)格，那么對(duì)于任意的a,bA, 有 a b ab=a ab=b 定理6-1.7設(shè)A, 是一個(gè)格，那么對(duì)于任意的a,b,cA, 有 a c a(bc) (ab)c 推論 在一個(gè)格A, 中，對(duì)于任意的a,b,cA，必有 (ab) (ac) a (b(ac) a(b (ac) (ab)(ac) 定義6-1.4 設(shè)A1, 1和A2,2是兩個(gè)格，由它們誘導(dǎo)的代數(shù)系統(tǒng)為A1,1,1和A2,2,2，如果存在著一個(gè)從A1到A2的映射，使得對(duì)任意的a,bA1,有 f(a1b)=f(a)2 f(b) f(a1b

7、)=f(a)2 f(b) 則稱f是從A1,1,1到A2,2,2的格同態(tài)，亦可稱是A1, 1的格同態(tài)象。 當(dāng)f是雙射時(shí)，則稱為從A1,1,1到A2,2,2的格同構(gòu)，亦稱A1, 1和A2,2這兩個(gè)格同構(gòu) 定理6-1.8 設(shè)f是格A1,1到A2,2的格同態(tài)，則對(duì)任意的x,yA1，如果x1y，必有f(x)2f(y) 定理6-1.8說(shuō)明格同態(tài)是保序的。一般地，定理6-1.8的逆并不成立【例】設(shè)A=a,b,c,d,e，A, 是格，其哈斯圖如下圖所示，P(A)是A的冪集合，R=x,y|xP(A)yP (A)xy是P(A)上的偏序關(guān)系。P(A), R也是格。作映射f：AP (A)，定義為：xA，f(x)= y

8、|yA且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)。 f(bd)=f(a)=a,b,c,d,e f(b)f(d)=b, ed,e=b, d, e f(bd) f(b)f(d) 定理6-1.9 設(shè)A1,1和A2,2是兩個(gè)格，f 是A1到A2的雙射，則 f 是A1, 1 到 A2,2的格同構(gòu) ， 當(dāng) 且 僅 當(dāng) 對(duì) 于 任 意 的 a , b A1，a1bf(a)2f(b)。 作業(yè) (1) (4) (8) 6.2 分配格 由定理6-1.5 可知在一個(gè)格A, 中，對(duì)任意的a,b,c A, 都有 a(bc

9、) (ab)(ac) (ab)(ac) a(bc) 當(dāng)上述兩個(gè)式子中的等號(hào)都成立時(shí), 即 a(bc) = (ab)(ac) (ab)(ac) = a(bc) 定義一類特殊的格 定義6-2.1 設(shè)A,是由格A,所誘導(dǎo)的代數(shù)系統(tǒng)，如果對(duì)任意的a,b,cA滿足 a(bc)=(ab)(ac) (并運(yùn)算對(duì)交運(yùn)算可分配) a ( b c ) = ( a b ) ( a c ) (交運(yùn)算對(duì)并運(yùn)算可分配) 則稱A, 為分配格?！纠?設(shè)A=a,b,c，P (A)=,a,b,c,a,b,a,c,b,c,a,b,c是A的冪集合，是一個(gè)格. 則它誘導(dǎo)的代數(shù)系統(tǒng)P (A), , , 其中是集合的并運(yùn)算，是集合的交運(yùn)算

10、. 因?yàn)榧系牟ⅰ⒔贿\(yùn)算滿足分配律： 任意的P,Q,RP (A) ,有 P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) 所以，P (A), , 是一個(gè)分配格。【例】A=a,b,c,d,e，A, 是格，其哈斯圖如下左圖所示，證明A, 不是分配格。【例】設(shè)A=a,b,c,d,e，A, 是格，其哈斯圖如上右圖所示，證明A, 不是分配格。 注:一個(gè)格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。鉆石格五角格計(jì)算b(cd)和(bc)(bd)計(jì)算c(bd)和(cb)(cd)【例】下圖給出了兩個(gè)格的哈斯圖。試證明它們都不是分配格。 注: 設(shè)A, 是格，如果|A|5，則A, 一定

11、是分配格。 定理6-2.1 如果在一個(gè)格中交運(yùn)算對(duì)于并運(yùn)算可分配, 則并運(yùn)算對(duì)交運(yùn)算一定是可分配的. 反之亦然. 定理6-2.2 每個(gè)鏈?zhǔn)欠峙涓?定理6-2.3 設(shè)A, 是一個(gè)分配格, 那么對(duì)于任意的a,b,cA，如果有 ab=ac和ab=ac 成立, 則必有b= c 定義6-2.2 設(shè)A,是一個(gè)格, 由它誘導(dǎo)的代數(shù)系統(tǒng)為A, 如果對(duì)于任意的a,b,cA, 當(dāng)ba時(shí), 有 a(bc)=b(ac) 則稱A,為模格 定理6-2.4 格A,是模格, 當(dāng)且僅當(dāng)在A中不含有適合下述條件的元素u,v,w v u 且 uw=vw, uw=vw 在一般格中,對(duì)于任意的a,b,c, 有以下三個(gè)式子成立 a(bc

12、) (ab)(ac) (ab)(ac) a(bc) (ab)(bc)(ca) (ab)(bc) (ca) 定理6-2.5 對(duì)于模格,若有三個(gè)元素a,b,c, 使得上述三個(gè)式子中任何一個(gè)式子中把“ ”換成“=”成立, 則另外兩個(gè)式子把“ ”換成“=”也必成立. 定理6-2.6 分配格必定是模格. 作業(yè) (2) (5) 6.3 有補(bǔ)格 定義6-3.1 設(shè)A, 是一個(gè)格，如果存在元素aA，對(duì)于任意的xA, 都有 a x 則稱a為格A, 的全下界，記格的全下界為0。 定理6-3.1 一個(gè)格A, ，若有全下界，則是惟一的。 定義6-3.2 設(shè)A, 是一個(gè)格，如果存在元素bA，對(duì)于任意的xA, 都有 x

13、b 則稱b為格A, 的全上界，記格的全上界為1。 定理6-3.2 一個(gè)格A, ，若有全上界，則是惟一的?！纠?1. 在格中, 空集?是全下界, 而A是全上界 2. 如下圖所示的格中, e是全下界, 而a是全上界 定義6-3.3 如果一個(gè)格中存在全下界和全上界, 則稱該格為有界格 定理6-3.3 設(shè)A, 為一個(gè)有界格，則對(duì)任意的aA,必有a1=1, a1=a a0=a, a0=0 設(shè)A,是由有界格A, 所誘導(dǎo)的代數(shù)系統(tǒng) ，aA有a0=0，因?yàn)楦駶M足交換律，所以0a=0，這說(shuō)明0是交運(yùn)算的零元；同樣的道理，0是并運(yùn)算的幺元，而1是交運(yùn)算的幺元和并運(yùn)算的零元 定義6-3.4 設(shè)A, 是一個(gè)有界格，

14、對(duì)于A中的一個(gè)元素a，如果存在bA，使得ab=1且ab=0，則稱b是a的補(bǔ)元。 如果b是a的補(bǔ)元，從上述定義可以看出，a也是b的補(bǔ)元。因此，可以說(shuō)a和b是互補(bǔ)的，或者說(shuō)a和b互為補(bǔ)元。【例】如下圖所示的格中, b和c互為補(bǔ)元，b和d也互為補(bǔ)元，b有兩個(gè)補(bǔ)元c和d。 注: 格中元素的補(bǔ)元并不惟一, 也可能不存在【例】下圖是一個(gè)有界格的哈斯圖。找出a,b,c,d,e的補(bǔ)元。 a的補(bǔ)元: ec的補(bǔ)元: dd的補(bǔ)元: c,ee的補(bǔ)元: a,db沒(méi)有補(bǔ)元 注: 在有界格中，全上界1的惟一補(bǔ)元是全下界0，而全下界0的惟一補(bǔ)元是全上界1。 定義6-3.5 在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元, 則稱

15、此格為有補(bǔ)格【例】如下圖所示三個(gè)格均為有補(bǔ)格 定理6-3.4 在有界分配格中,若有一個(gè)元素有補(bǔ)元,則必是唯一的 定義定義6-3.66-3.6 一個(gè)格如果它既是有補(bǔ)格又是分配格, 則稱為有補(bǔ)分配格.并記格中任一元素a的唯一補(bǔ)元為 作業(yè) (1) (4) (6) 6.4 布爾代數(shù) 定義6-4.1 有補(bǔ)分配格稱為布爾格。 在布爾格中每一個(gè)元素a都有補(bǔ)元, 并且是唯一的, 這唯一的補(bǔ)元記為 對(duì)于一個(gè)有補(bǔ)分配格, 計(jì)算一個(gè)元素的補(bǔ)元可以確定一個(gè)一元運(yùn)算, 記為 “-”, 稱為補(bǔ)運(yùn)算 定義6-4.2 由布爾格A, ，可以誘導(dǎo)一個(gè)代數(shù)系統(tǒng)A, -, 這個(gè)代數(shù)系統(tǒng)稱為布爾代數(shù)?！纠縎是一個(gè)非空有限集合, P

16、(S), 是一個(gè)格, P (S),是由P (S),導(dǎo)出的代數(shù)系統(tǒng). 集合的并(交)對(duì)于交(并)是可分配的, 而且其全上界為S, 全下界為?. 因此P(S),是有界分配格. 對(duì)任意TP (S)，都有一個(gè)補(bǔ)元ST. P (S), 是一個(gè)布爾代數(shù). 定理6-4.1 對(duì)于布爾代數(shù)中任意兩個(gè)元素a,b, 必定有 定義 6-4.3 具有有限個(gè)元素的布爾代數(shù)稱為有限布爾代數(shù)babababaaa)( 定義 6-4.4 設(shè)A, -和B, -是兩個(gè)布爾代數(shù), 如果存在著A到B的雙射f, 對(duì)于任意的a,bA, 都有 f(ab)=f(a)f(b) f(ab)=f(a)f(b) 則稱A, -和B, -同構(gòu))()(afa

17、f 接下來(lái)用同構(gòu)的觀點(diǎn)來(lái)討論有限布爾代數(shù)的結(jié)構(gòu) 定義6-4.5 設(shè)A, 是一個(gè)格，具有全下界0，如果有元素a蓋住0，則稱元素a為原子?！纠咳缦聢D所示是三個(gè)格的哈斯圖, 試找出每個(gè)格的原子 注: 若a,b是原子, 且ab, 則ab=0 定理6-4.2 設(shè)A, 是一個(gè)具有全下界0的有限格，則對(duì)于任何一個(gè)非零元素b(即b0)，至少存在一個(gè)原子a，使得a b。 注: 上述定理中的原子a不一定惟一 引理6-4.1 在一個(gè)布爾格中, 當(dāng)且僅當(dāng)b c。 引理6-4.2 設(shè)A,-是一個(gè)有限布爾代數(shù)，若b是A中任意非零元素, a1,a2,ak是A中滿足aj b的所有原子，則 b=a1a2ak 引理6-4.3

18、設(shè)A, -是一個(gè)有限布爾代數(shù), bA且b0，a1,a2,ak是滿足ai b(i=1,k)的A中的所有原子, 則b=a1a2ak是將b表示為原子的并的惟一形式。0cb 引理 6-4.4 在一個(gè)布爾代數(shù)A, 中, 對(duì)A中任意一個(gè)原子a和另一個(gè)非零元素b, a b和a 兩式中有且僅有一式成立. 定理6-4.3 (Stone表示定理) 設(shè)A, -是由有限布爾格A, 所誘導(dǎo)的一個(gè)有限布爾代數(shù)，S是布爾格A, 中所有原子的集合，則A,- 和P (S), 同構(gòu)。 推論6-4.1 有限布爾格的元素個(gè)數(shù)必定等于2n，其中n是該布爾格中所有原子的個(gè)數(shù)。 推論6-4.2 任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)都是同構(gòu)

19、的.b 定理6-4.3 (Stone表示定理) 設(shè)A, -是由有限布爾格A, 所誘導(dǎo)的一個(gè)有限布爾代數(shù)，S是布爾格A, 中所有原子的集合，則A,- 和P (S), 同構(gòu)。 推論6-4.1 有限布爾格的元素個(gè)數(shù)必定等于2n，其中n是該布爾格中所有原子的個(gè)數(shù)。 推論6-4.2 任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)都是同構(gòu)的. 作業(yè) (2) (3) (6) 6.5 布爾表達(dá)式 設(shè)A, -是一個(gè)布爾代數(shù), 考慮一個(gè)從An到A的函數(shù)【例】1. A=0,1, 下表給出了一個(gè)從A3到A的一個(gè)函數(shù) 2. B=0,1,2,3,下表給出了一個(gè)從B2到B的一個(gè)函數(shù)001011011200013113100232 定

20、義6-5.1 設(shè)A, -是一個(gè)布爾代數(shù), 并在這個(gè)布爾代數(shù)上定義布爾表達(dá)式如下: (1) A中任何元素是一個(gè)布爾表達(dá)式 (2) 任何變?cè)且粋€(gè)布爾表達(dá)式 (3) 如果e1和e2是布爾表達(dá)式, 那么 ,(e1e2)和 (e1e2)也是布爾表達(dá)式 (4) 只有通過(guò)有限次運(yùn)用規(guī)則(2)和(3)所構(gòu)造的符號(hào)串是布爾表達(dá)式【例】 0,1,2,3, -是一個(gè)布爾代數(shù), 下列三個(gè)符號(hào)串都是布爾表達(dá)式 0 x1, , 1e21)1 (xx )()()32(3121xxxx 定義6-5.2 一個(gè)含有n個(gè)變?cè)牟紶柋磉_(dá)式, 稱為含有n元的布爾表達(dá)式. 記為E(x1,x2,xn), 其中x1,x2,xn為變?cè)?定義

21、6-5.3 布爾代數(shù)A, -上的一個(gè)含有n元的布爾表達(dá)式E(x1,x2,xn)的值是指: 將A中元素作為變?cè)獂i的值來(lái)代替表達(dá)式中相應(yīng)的變?cè)?即對(duì)變?cè)x值), 從而計(jì)算出表達(dá)式的值.【例】 設(shè)布爾代數(shù)0,1, -上的布爾表達(dá)式為: )()()(),(322121321xxxxxxxxxE 定義6-5.4 設(shè)布爾代數(shù)A, -上兩個(gè)n元的布爾代數(shù)為E1(x1,x2,xn)和E2(x1,x2,xn), 如果對(duì)于n個(gè)變?cè)娜我赓x值 , 時(shí), 均有 則稱這兩個(gè)布爾表達(dá)式是等價(jià)的.【例】在布爾代數(shù)上定義: 一個(gè)n元布爾表達(dá)式確定一個(gè)從An到A的函數(shù)?！纠?A=0,1, 右表給出了一個(gè)從A3到A的一個(gè)函數(shù)

22、 iixxAxi),(),(212211nnxxxExxxE)()()(),(3121321321xxxxxxxxxxE00101101)()(31211xxxxE)(3212xxxE 定義 6-5.5 設(shè) 為布爾代數(shù),一個(gè)從An到 A的函數(shù)，如果它能夠用 上的n元布爾表達(dá)式表示，那么，這個(gè)函數(shù)就稱為布爾函數(shù)。 定理 6-5.1 對(duì)于兩個(gè)元素的布爾代數(shù),任何一個(gè)從 0,1n到 0,1的函數(shù),都是布爾函數(shù). 布爾小項(xiàng) 形如 , 其中 是xi或 中的任一個(gè) 析取范式 一個(gè)在 上的布爾表達(dá)式, 如果它能表示成小項(xiàng)的并, 我們稱為這個(gè)布爾表達(dá)式為析取范式. nxxx21ixix 求函數(shù)的析取范式 (1) 取使函數(shù)值為1的有序n元組分別構(gòu)造小項(xiàng) 其中 (2) 將這些小項(xiàng)做并運(yùn)算【例】求由右表定義的函數(shù)的析取范式0 1 個(gè)分量為元組中第若個(gè)分量為元組中第若inxinxxiiinxxx2110100001 布爾大項(xiàng) 形如 , 其中 是xi或 中的任一個(gè) 合取范式 一個(gè)在 上的布爾表達(dá)式, 如果它能表示成大項(xiàng)的交, 我們稱為這個(gè)布爾表達(dá)式為合取范式. 求函數(shù)的合取范式 (1) 取使函數(shù)值為0的有序n元組分別構(gòu)