離散數(shù)學(xué)-第10講-分配格、有界格與有補(bǔ)格

1、1,離散數(shù)學(xué)（二）,特殊格:分配格,有界格與有補(bǔ)格,主要內(nèi)容:,重點(diǎn)和難點(diǎn):,一、分配格,分配格的定義： 設(shè)是一個(gè)格, 若對(duì)于任何a,b,cL,有 a*(bc) = (a*b)(a*c) 保交對(duì)保聯(lián)可分配 (1) a(b*c) = (ab)*(ac) 保聯(lián)對(duì)保交可分配 (2) 則稱是一個(gè)分配格。 Note: 上述定義中(1)和(2)是等價(jià)的,只要一個(gè)成立,應(yīng)用吸收律可推出另外一個(gè)。因此,判斷一個(gè)格是否是分配格只需判斷(1)或(2)其中之一. 例1:S=a,b,c, 為分配格, 因?yàn)槿稳,B,C(S), (a) A(BC)=(AB)(AC) (b) A(BC)=(AB)(AC),一、分配格,例

2、2: 圖中鉆石格與五角格是分配格嗎？,(a) b*(cd)b*ab (b*c)(b*d)eee 所以b*(cd) (b*c)(b*d) (b) c*(bd)c*ac (c*b)(c*d)ed=d 所以c*(bd) (c*b)(c*d),一、分配格,定理1 設(shè)是偏序格，則是分配格當(dāng)且僅當(dāng) (i) 在此格中不存在與鉆石格同構(gòu)的子格; (ii) 且不存在與五角格同構(gòu)的子格。 推論:設(shè)是格，|L|是分配格。 定理2 每個(gè)鏈都是分配格。 證明: 設(shè)是鏈，則必是格.任取a,b,cL,討論以下兩種情況: (1) ab或ac; (2) ab和ac。 對(duì)于情況(1)有: a*(bc)=a; (a*b)(a*c)

3、=aa=a. 對(duì)于情況(2)有: a*(bc)=bc; (a*b)(a*c)=bc. 因此有a*(bc)=(a*b)(a*c). 所以,每個(gè)鏈都是分配格.,一、分配格,定理3 設(shè)是一個(gè)格，若*運(yùn)算對(duì)運(yùn)算可分配，則對(duì)*也可分配，反之亦然。 證明: 設(shè)*運(yùn)算對(duì)運(yùn)算可分配，即任取a,b,cL,滿足 a*(bc) = (a*b)(a*c), 現(xiàn)要證 a(b*c) = (ab)*(ac). (ab)*(ac) = (ab) * a)(ab) *c) = a (a*c)(b*c) = a(a*c)(b*c) = a(b*c) 同理可由a(b*c) = (ab)*(ac)推出a*(bc) = (a*b)(a

4、*c).,一、分配格,定理4 設(shè)是一個(gè)分配格，那么對(duì)于任意a,b,cL,若有a*b= a*c和ab=ac，則必有b=c。 證明: c = (a*c)c = (a*b)c = (ac) *(bc) = (ab)*(bc) = (ab)*b)(ab) * c) = b(a*c) (b*c) = b(a*b) (b*c) = b(a*c) = b(a*b) = b,二、有界格和有補(bǔ)格,全上/下界定義: 設(shè)是一個(gè)格, 若aL, 對(duì)所有xL均有xa,稱a為格的全上界； 若bL, 對(duì)所有xL均有bx,稱b為格的全下界。 通常將全上界記為“1”，而將全下界記為“0”。 定理5 對(duì)于一個(gè)格,若全上界存在,那么

5、它是唯一的(若全下界存在,則唯一). Note: 1 有限格必有全上界(全下界) 2 無(wú)限格不一定有全上界(全下界) 如無(wú)全上界. 有界格的定義: 具有全上界和全下界的格稱為有界格,記作.,二、有界格和有補(bǔ)格,例2 (1) S=a,b,c, 偏序格是 ， 全上界 S A(S),有AS 全下界 A(S), 有A (2) X=A|A是由變?cè)猵1,p2,pn, , 構(gòu)成的合式公 式集。誘導(dǎo)的偏序格是 . 全上界 T PX,有PT 全下界 F PX, 有FP.,二、有界格和有補(bǔ)格,定理6 設(shè)是一個(gè)有界格，則對(duì)于aA,都有 a1=1 a1=a (1是運(yùn)算的零元,運(yùn)算的幺元) a0=a a0=0 (0是運(yùn)

6、算的幺元,運(yùn)算的零元) 證明: (1) 證 a1=1 因?yàn)閍1 L且1是全上界，所以 a11;又因?yàn)?1 a1，所以 a1=1. (2) 證 a1=a 因?yàn)閍 a，a 1, 所以a a1;又因?yàn)?a1 a，所以a1=a. (3)(4)類似可證.,二、有界格和有補(bǔ)格,補(bǔ)元的定義: 設(shè)是有界格aL,若存在bL使得ab=1和ab=0,則稱b為a的補(bǔ)元。,(1)中a,b,c都不存在補(bǔ)元,0與1互為補(bǔ)元. (2)中a,b,c中任意兩個(gè)都互為補(bǔ)元, 0與1互為補(bǔ)元. (3)中a的補(bǔ)元都是b和c,而c的補(bǔ)元是a,0與1互為補(bǔ)元.,Note: 在格中有的元素?zé)o補(bǔ)元,有的元素有補(bǔ)元,有的元素有多個(gè)補(bǔ)元.,二、有

7、界格和有補(bǔ)格,有補(bǔ)格定義: 如果在一個(gè)有界格中，每個(gè)元素都至少有一個(gè)補(bǔ)元,則稱這個(gè)格為有補(bǔ)格.上圖中(2)和(3)是有補(bǔ)格,而(1)不是有補(bǔ)格.,證明: 01=0，01=1，0、1互為補(bǔ)元。設(shè)c也是0的補(bǔ)元， 0c =1， 必有c=1，故0的補(bǔ)元唯一。 同理可證1的補(bǔ)元也唯一。,定理7 在有界格中, 0 和 1互為補(bǔ)元, 且是唯一的.,證明: 設(shè) b,c都是a的補(bǔ)元, 則ab=0=ac, ab=1=ac,分配格 滿足消去律,可知b=c. 消去律: (即對(duì)于任意a,b,cL有(ab=ac) (ab=ac)b=c),定理8 在分配格中，如果元素aL有一個(gè)補(bǔ)元a ，則此補(bǔ)元a是唯一的.,三、布爾格(

8、布爾代數(shù)),布爾格的定義 如果格,既是有補(bǔ)格,又是分配格,則稱此格為布爾格(或有補(bǔ)分配格),也叫做布爾代數(shù).,例3 設(shè)S是非空有限集合, 為代數(shù)格 A,B(S)，ABAB=AAB 由誘導(dǎo)的偏序格是. 說(shuō)明是布爾格.,證明 (1)是格; (2)是有界格, 因?yàn)?全上界 S A(S),有AS 全下界 A(S),有A; (3)是有補(bǔ)格, 因任取 A(S), A的補(bǔ)元是S-A; (4)是分配格, 因和運(yùn)算滿足相互分配律. 綜上可知, 是一個(gè)布爾格。,三、布爾格(布爾代數(shù)),例4 X=A|A是由變?cè)猵1,p2,pn,構(gòu)成的合式公式集。誘導(dǎo)的偏序格是 .說(shuō)明是布爾格.,證明 (1) 是格， (2) 是有界格, 因?yàn)?全上界 T PX,有PT 全下界 F PX, 有FP. (3) 是有補(bǔ)格，因任取 PX, P的補(bǔ)元是P (4) 是分配格,因和運(yùn)算滿足相互分配律， 綜上可知, 是一個(gè)布爾格。,三、布爾格(布爾代數(shù)),由于布爾代數(shù)L中的每個(gè)元都有唯一的補(bǔ)元.求一個(gè)元素的補(bǔ)元素可以看作一元運(yùn)算,稱為補(bǔ)運(yùn)算.因此,布爾代數(shù)L可記為,其中表示求補(bǔ)運(yùn)算.,證明 (1) 由于aa=1, aa=0;根據(jù)交換律有, aa=1, aa=0;所以(a)=a; (2) (ab)(ab)=(aab)(bab)=0 (ab)(