離散數(shù)學(xué)II課件：7_4幾種特殊的格

1、7.4 幾種特殊的格,7.4.1 有 界 格 7.4.2 有 余 格 7.4.3 分 配 格 7.4.4 模 格,7.4.1 有 界 格,引理1 設(shè)(L，)是一個(gè)格。若S是L的任意一個(gè)有限非空子集，則S有一個(gè)最大下界和一個(gè)最小上界。 記集合S的最大下界為inf S； 集合S的最小上界為sup S。 Note: 對(duì)于格的一個(gè)無窮子集，引理1的結(jié)論不 成立。 例.在格（I+，）中，所有正偶數(shù)組成的集合 記為E+，顯然，E+ I+，但E+沒有最小上界。,定義. 格（L，）稱為有界格，如果它有一個(gè)最大元素（記為1）和一個(gè)最小元素（記為0），亦即，對(duì)任意aL，都有 0a1 0，1稱為格（L，）的界。 結(jié)

2、論：有限格必是有界格 令L=a1，an , 0 = a1a2an, 1 = a1a2an 引理2. 若（L,0,1）是有界格，則對(duì)任意aL，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0。,定義. 在有界格（L，0，1）中，一個(gè)元素bL，稱為元素aL的余元素，如果 ab = 0， ab = 1。 1 1 1 a b a b a b c 0 0 0 (a,b都無余）（a有唯一余）（a有b,c兩個(gè)余） 1 a b c 0,引理3 在有界格（L，0，1）中，1是0的唯一一個(gè)余元素，反之亦然。 證明：由引理2，01 = 0， 01 = 1， 所以，0，1互為余元素。 若cL，且

3、c1，c是0的余元素， 0c = 0， 0c = 1。 但是，由引理2知，0c = c 故，c = 1，矛盾。,7.4.2 有 余 格,定義. 稱有界格（L，0，1）是一個(gè) 有余格，如果對(duì)L中每一個(gè)元素，都至少有一 個(gè)余元素。 例. n維格（Ln，n）是一個(gè)有余格，其中 1n=(1，1，1), 0n=(0，0，0)是界。 對(duì)任意Ln中元素（a1，an）， 元素（b1，bn）是其 余元素，其中,例. 設(shè)S是有n個(gè)元素的集合，(S)是S的冪 集合，于是，（S），）是有余格。 其中， 和S是此格的界. 對(duì)（S）中任意元素A，（S）中的元 素S-A是其余元素。,7.4.3 分 配 格,定義7.4.4

4、格（L，）稱為分配格，如果對(duì)任意a，b，cL，恒有 a（bc）=（ab）（ac） a（bc）=（ab）（ac） Note: (1)分配格定義中的兩個(gè)等式是等價(jià)的 (2) n維格（Ln，n），格（S），）， 格（I+，D），格（Sn，D）都是分配格。 但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。,例子,d d e e c b c b c d d b b a a c a a L1 L2 L3 L4 圖中L1和L2是分配格，但L3,L4不是。因?yàn)樵贚3中 b(cd)=b e=b和(b c) (b d)=a a=a； 在L4中d(bc)=d e=d和(d b) (d c)=a c=c。

5、 L3稱為鉆石格， L4稱為五角格。,引理4 任意一個(gè)鏈都是一個(gè)分配格。 證明：設(shè)格（L，）是一個(gè)鏈，任取a,b,c L, 1）若ab且ac，于是abc，故 a（bc）= bc 而ab = b，ac = c，所以 （ab）（ac）= bc 故a（bc）=（ab）（ac）。 2）若ab或者ac，于是a（bc）， 故a（b c）= a。而 （ab）（ac）= a 所以a（bc）=（ab）（ac）。,De Morgan定律,定理7.4.1 設(shè)（L,）是一個(gè)分配格,對(duì)任意a,bL,若a，b有余元素a,b，則 （ab）= ab （ab）= ab 證明： (ab)(ab)=(aba)(abb) =(1b)

6、(a1)= 11 = 1 而(ab)(ab)=(aab)(bab) =(0b)(0a)= 00 = 0 故由余元素定義知， （ab）= ab 同理可證另一等式。,定理7.4.2 設(shè)格（L，）是分配格，對(duì) 任意a，b，cL，如果 ac = bc， ac = bc， 則有a = b。 證明：若（L，）是分配格，且ac=bc，ac=bc， 則 a = a（ac）= a（bc） =（ab）（ac） =（ab）（bc）= b（ac） = b（bc）= b,推論 設(shè)格（L，）是一個(gè)有余分配格， 則對(duì)任意aL，a的余元素a是唯一的。 證明： 因（L，）是有余格，設(shè)a和a都是a的余元素，即 aa= 0， aa

7、= 1 aa= 0， aa= 1 故aa= aa，aa= aa。 由定理8.4.2知，a= a。,7.4.4 模 格,定義7.4.5 設(shè)（L，）是一個(gè)格，對(duì)任意a， b，cL，如果ab，都有 a（bc）= b（ac） 則稱（L，）為模格。 Note: (1)任意一個(gè)分配格都是模格， 由ab， ab=b,故 a（bc）= （ab）（ a c） = b（ac） （2）模格不一定是分配格。,例.如圖所示,L=0,1,b1,b2,b3。則， 格(L,)不是分配格： b1（b2b3）= b1 （b1b2）（b1b3）= 0。 格(L,)是模格： (1)當(dāng)a=1時(shí),若ab,則b也一定是1。故 a(bc)=

8、1(1c) = 1 b(ac)=1(1c)= 11 = 1。 (2)當(dāng)a=0時(shí),若ab,則b可能為0,b1,b2,b3,1。故 a(bc)= 0(bc)=bc b(ac)=b(0c)= bc。,(3)當(dāng)a= b1,b2,b3之一時(shí)， 若ab，則b是1或a。 若b = 1，則 a(bc)= a（1c）=ac b(ac)=1(ac)=ac 。 若b = a，則 a(bc）= a（ac） = a b(ac)= a（ac）= a。 綜上，對(duì)任意a，b，cL，如果ab，都有a(bc）= b(ac) 。,例子與結(jié)論,前面描述的格L1、L2和L3都是模格，但L4不是。因?yàn)閏d,但c (bd)=c,(cb)

9、d=d 一個(gè)格L是模格當(dāng)且僅當(dāng)L不含與五角格同構(gòu)的子格。 一個(gè)模格是分配格當(dāng)且僅當(dāng)L不含與鉆石格同構(gòu)的子格,模格的例,群G中的所有正規(guī)子群做成一個(gè)模格。 證明：設(shè)群G的所有正規(guī)子群做成的集合為S， 規(guī)定S中兩種運(yùn)算： ， ，對(duì)任意AS，BS， A與B的交集記為AB。 A與B的乘積（記為AB）為如下集合： AB = y(A)(yB) （1）往證（S,， )是格 往證， 是S上的二元代數(shù)運(yùn)算。 因?yàn)檎?guī)子群的交仍為正規(guī)子群，故運(yùn)算 對(duì)S封閉。,對(duì)任意AS，BS，對(duì)任意gG，任取ug（AB），于是， u = gab 其中aA,bB。因?yàn)锳，B是正規(guī)子群，所以 gab = a1gb = a1b1g 其

10、中a1A,b1B。故u=gab（AB）g，故 g（AB）（AB）g 同理可證：（AB）g g（AB）。故 g（AB）=（AB）g 即，AB是正規(guī)子群. 所以，乘運(yùn)算對(duì)S也是封閉的。,往證， 適合交換律、結(jié)合律、吸收律 結(jié)合律 ， 滿足結(jié)合律是顯然的。 交換律 滿足交換律是顯然的 對(duì)于乘運(yùn)算 ：任取uAB,即 u=ab(aA,bB)。 由于B是正規(guī)子群，所以， u = ab = b1a（b1B） 故uBA，即AB BA。 同理可證：BA AB，故AB=BA。 即乘運(yùn)算滿足交換律。,吸收律 任取uA(AB),于是,u=ac,其中cAB,故u = acA，即A（AB）A。 任取uA，因?yàn)锳，B都是子

11、群，故單位元素1在A中，也在B中，故1AB，故 u = u1A（AB），即A A（AB）。 故 A（AB）=A. 同理可證：A（AB）=A。 亦即：運(yùn)算和滿足吸收律。 因此，（S，）是一個(gè)格。 由于此格中的運(yùn)算就是集合的交運(yùn)算，故與 （S，）等價(jià)的半序格的部份序就是集合之 間的包含關(guān)系。,（2）往證（S,， )是 模格 對(duì)任意AS，BS，CS，如果AB， 任取uA(CB),于是,u=ad,其中dCB,aA,而AAC,故u=ad（AC）B，即 A（CB）（AC）B。 任取u(AC)B,于是,uB,uAC。令 u = ad(其中aA，dC)，于是，d = a-1u。因?yàn)閍-1AB，uB，故a-1u

12、B，即dB。故dCB。因此， u = adA（CB），即 （AC）BA（CB）， 所以有 A（CB）=（AC）B 由定義知，（S，）是模格。,定理7.4.3 格(L，)是模格的充要條件是： 對(duì)任意a，b，cL，如果 ab，ac=bc，ac=bc 則必有a=b。 證明：必要性。若格（L，）是模格，則對(duì) 任意a，b，cL，如果 ab，ac=bc，a c=b c， 則 a = a （ac）= a （bc） = b（ac）= b（bc）= b,充分性。任取a，b，cL，且ab。 因?yàn)?a(bc) c = a (bc)c)=ac 又因?yàn)閍b，所以ab（ac），故 a c（b（ac）c （a c） c = ac 所以，（b（a c） c = a c。 因此(a(bc)c =(