離散數(shù)學(xué)ii74幾種特殊的格-1ppt課件

1、8.4.1 有有 界界 格格 8.4.2 有有 余余 格格 8.4.3 分分 配配 格格 8.4.4 模模 格格 引理引理1 設(shè)設(shè)(L，)是一個(gè)格。若是一個(gè)格。若S是是L的任意一個(gè)的任意一個(gè)有限非空子集，則有限非空子集，則S有一個(gè)最大下界和一個(gè)最有一個(gè)最大下界和一個(gè)最小上界。小上界。記集合記集合S的最大下界為的最大下界為inf S； 集合集合S的最小上界為的最小上界為sup S。 Note: 對(duì)于格的一個(gè)無窮子集，引理對(duì)于格的一個(gè)無窮子集，引理1的結(jié)論的結(jié)論不不成立。成立。 例例.在格在格I+，）中，所有正偶數(shù)組成的集合）中，所有正偶數(shù)組成的集合記為記為E+，顯然，顯然，E+ I+，但，但E+

2、沒有最小上界。沒有最小上界。定義定義. 格格L，）稱為有界格，如果它有一）稱為有界格，如果它有一個(gè)最大元素記為個(gè)最大元素記為1和一個(gè)最小元素記為和一個(gè)最小元素記為0），亦即，對(duì)任意），亦即，對(duì)任意aL，都有，都有 0a1 0，1稱為格稱為格L，）的界。）的界。 結(jié)論：有限格必是有界格結(jié)論：有限格必是有界格 令令L=a1，an , 0 = a1a2an, 1 = a1 a2 an 引理引理2. 假設(shè)假設(shè)L, ,0,1是有界格，則對(duì)任是有界格，則對(duì)任意意aL，恒有，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0。 定義定義. 在有界格在有界格L， ，0，1中，一個(gè)元中，一個(gè)

3、元素素bL，稱為元素，稱為元素aL的余元素，假設(shè)的余元素，假設(shè) ab = 0， a b = 1。 1 1 1 a b a b a b c 0 0 0 (a,b都無余）（都無余）（a有唯一余）（有唯一余）（a有有b,c兩個(gè)余）兩個(gè)余） 1 a b c 0引理引理3在有界格在有界格L， ，0，1)中，中，1是是0的唯一一個(gè)余元素，反之亦然。的唯一一個(gè)余元素，反之亦然。證明：由引理證明：由引理2，01 = 0， 0 1 = 1，所以，所以，0，1互為余元素?；橛嘣?。若若cL，且，且c1，c是是0的余元素，的余元素，0c = 0， 0 c = 1。但是，由引理但是，由引理2知，知，0 c = c故

4、，故，c = 1，矛盾。，矛盾。 v定義定義. 稱有界格稱有界格L， ，0，1是一個(gè)是一個(gè)v有余格，如果對(duì)有余格，如果對(duì)L中每一個(gè)元素，都至少有一中每一個(gè)元素，都至少有一v個(gè)余元素。個(gè)余元素。v例例. n維格維格Ln，n是一個(gè)有余格，其中是一個(gè)有余格，其中v1n=(1，1，1), 0n=(0，0，0)是界。是界。v對(duì)任意對(duì)任意Ln中元素中元素a1，an），），v元素元素b1，bn是其是其 余元素，其中余元素，其中niababiiii, 10110例例. 設(shè)設(shè)S是有是有n個(gè)元素的集合，個(gè)元素的集合，(S)是是S的冪的冪集合，于是，（集合，于是，（S），），）是有余格。）是有余格。其中，其中， 和

5、和S是此格的界是此格的界.對(duì)對(duì)S中任意元素中任意元素A，S中的元中的元素素S-A是其余元素。是其余元素。定義定義8.4.4 格格L， ）稱為分配格，如果對(duì)）稱為分配格，如果對(duì)任意任意a，b，cL，恒有，恒有a（b c）=（ab） （ac）a （bc）=（a b）（a c）Note: (1)分配格定義中的兩個(gè)等式是等價(jià)的分配格定義中的兩個(gè)等式是等價(jià)的 (2) n維格維格Ln，n），格），格S），），），）， 格格I+，D），格），格Sn，D都是分配格。都是分配格。 但不是所有的格都是分配格但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。分配格的任意子格仍是分配格。 l d d e e

6、l c b c b c d d blb a a c al al L1 L2 L3 L4l圖中L1和L2是分配格，但L3,L4不是。因?yàn)樵贚3中 lb(cd)=b e=b和(b c) (b d)=a a=a；l在L4中d(bc)=d e=d和(d b) (d c)=a c=c。lL3稱為鉆石格， L4稱為五角格。引理引理4 任意一個(gè)鏈都是一個(gè)分配格。任意一個(gè)鏈都是一個(gè)分配格。證明：設(shè)格證明：設(shè)格L，）是一個(gè)鏈，任?。┦且粋€(gè)鏈，任取a,b,c L, 1若若ab且且ac，于是，于是ab c，故，故 a（b c）= b c而而ab = b，ac = c，所以，所以（ab） （ac）= b c故故a（b

7、 c）=（ab） （ac）。）。2若若ab或者或者ac，于是，于是a（b c），），故故a（b c）= a。而。而（ab） （ac）= a所以所以a（b c）=（ab） （ac）。）。 De MorganDe Morgan定律定律定理定理8.4.1 設(shè)設(shè)L, ）是一個(gè)分配格）是一個(gè)分配格,對(duì)任意對(duì)任意a,bL,若若a，b有余元素有余元素a,b，那么，那么（ab）= a b（a b）= ab證明：證明： (a b) (ab)=(a b a)(a b b) =(1 b)(a 1)= 11 = 1而而(a b)(ab)=(aab) (bab) =(0b) (0a)= 0 0 = 0故由余元素定義知，

8、故由余元素定義知， （ab）= a b同理可證另一等式。同理可證另一等式。定理定理8.4.2 設(shè)格設(shè)格L， ）是分配格，對(duì)）是分配格，對(duì)任意任意a，b，cL，假設(shè)，假設(shè) ac = bc， a c = b c，則有則有a = b。證 明 ： 假 設(shè) 證 明 ： 假 設(shè) L ， ， ） 是 分 配 格 ， 且） 是 分 配 格 ， 且ac=bc，a c=b c，那么那么a = a（a c）= a（b c） =（ab） （ac） =（ab） （bc）= b（a c） = b（b c）= b 推論推論 設(shè)格設(shè)格L， ）是一個(gè)有余分配格，）是一個(gè)有余分配格，則對(duì)任意則對(duì)任意aL，a的余元素的余元素a是唯

9、一的。是唯一的。證明：證明： 因因L， ）是有余格，設(shè)）是有余格，設(shè)a和和a都都是是a的余元素，即的余元素，即 aa= 0， a a= 1 aa= 0， a a= 1故故aa= aa，a a= a a。由定理由定理8.4.2知，知，a= a。 定義定義8.4.5 設(shè)設(shè)L，）是一個(gè)格，對(duì)任意）是一個(gè)格，對(duì)任意a，b，cL，如果，如果ab，都有，都有a （bc）= b（a c）則稱則稱L，）為模格。）為模格。Note:(1)任意一個(gè)分配格都是模格，任意一個(gè)分配格都是模格， 由由ab， a b=b,故故 a （bc）= （a b）（ a c） = b（a c）（2模格不一定是分配格。模格不一定是分配

10、格。 例例.如下圖如下圖,L=0,1,b1,b2,b3。那么，。那么，格格(L, )不是分配格：不是分配格： b1（b2 b3）= b1（b1b2） （b1b3）= 0。格格(L, )是模格：是模格： (1)當(dāng)當(dāng)a=1時(shí)時(shí),若若ab,則則b也一定是也一定是1。故。故 a (bc)=1 (1c) = 1 b(a c)=1(1 c)= 11 = 1。(2)當(dāng)當(dāng)a=0時(shí)時(shí),若若ab,則則b可能為可能為0,b1,b2,b3,1。故。故 a (bc)= 0 (bc)=bc b(a c)=b(0 c)= bc。1b3b20b1(3)當(dāng)當(dāng)a= b1,b2,b3之一時(shí)，之一時(shí)， 若若ab，則，則b是是1或或a

11、。 若若b = 1，那么，那么 a (bc)= a （1c）=a c b(a c)=1(a c)=a c 。 若若b = a，那么，那么 a (bc）= a （ac） = a b(a c)= a（a c）= a。綜上，對(duì)任意綜上，對(duì)任意a，b，cL，如果，如果ab，都有，都有a (bc）= b(a c) 。 1b3b20b1l前面描述的格L1、L2和L3都是模格，但L4不是。因?yàn)閏d,但c (bd)=c,(c b) d=dl 一個(gè)格L是模格當(dāng)且僅當(dāng)L不含與五角格同構(gòu)的子格。l一個(gè)模格是分配格當(dāng)且僅當(dāng)L不含與鉆石格同構(gòu)的子格群群G中的所有正規(guī)子群做成一個(gè)模格。中的所有正規(guī)子群做成一個(gè)模格。定理定

12、理8.4.3 格格(L，)是模格的充要條件是：是模格的充要條件是：對(duì)任意對(duì)任意a，b，cL，假設(shè)，假設(shè)ab，ac=bc，a c=b c則必有則必有a=b。證明：必要性。若格證明：必要性。若格L，）是模格，則對(duì)）是模格，則對(duì)任意任意a，b，cL，假設(shè)，假設(shè)ab，ac=bc，a c=b c，那么那么a = a （ac）= a （bc） = b（a c）= b（b c）= b充分性。任取充分性。任取a，b，cL，且，且ab。由于由于(a (bc) c = a (bc) c)=a c 又因?yàn)橛忠驗(yàn)閍b，所以，所以ab（a c），故），故a c（b（a c） c （a c） c = a c所以，（所以，（b（a c） c = a c。因此因此(a (bc) c =(b(a c) c (1)亦即，在格亦即，在格L，）中，若）中，若ab，則有，則有1）式。式。 根據(jù)對(duì)偶原理根據(jù)對(duì)偶原理2，對(duì)任意，對(duì)任