離散7.4幾種特殊的格

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

2、限格必是有界格 令L=a1，an , 0 = a1a2an, 1 = a1a2an 引理2. 若（L,0,1）是有界格，則對任意aL，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0。 定義. 在有界格（L，0，1）中，一個元素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兩個余） 1 a b c 0引理3 在有界格（L，0，1）中，1是0的唯一一個余元素，反之亦然。證明：由引理2，01 = 0， 01 = 1，所以，0，1互為余元素。若cL，且c1，c是0的

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

4、，恒有a（bc）=（ab）（ac）a（bc）=（ab）（ac）Note: (1)分配格定義中的兩個等式是等價的 (2) n維格（Ln，n），格（S），）， 格（I+，D），格（Sn，D）都是分配格。 但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。 例子 d d e e c b c b c d d bb a a c a a L1 L2 L3 L4圖中L1和L2是分配格，但L3,L4不是。因為在L3中 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。L3稱為鉆石格， L4稱為五角格。引理4 任意一個鏈都是

5、一個分配格。證明：設格（L，）是一個鏈，任取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 設（L,）是一個分配格,對任意a,bL,若a，b有余元素a,b，則（ab）= ab（ab）= ab證明： (ab)(ab)=(aba)(abb) =(1b)(a1)= 11 = 1而(ab)(ab)=(aab)(bab) =(0b)(0a)

6、= 00 = 0故由余元素定義知， （ab）= ab同理可證另一等式。定理7.4.2 設格（L，）是分配格，對任意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 推論 設格（L，）是一個有余分配格，則對任意aL，a的余元素a是唯一的。證明： 因（L，）是有余格，設a和a都是a的余元素，即 aa= 0， aa= 1 aa= 0， aa= 1故aa= aa，aa= aa。由定理8.4.2知，a= a。 7.4.4

7、模 格 定義7.4.5 設（L，）是一個格，對任意a，b，cL，如果ab，都有a（bc）= b（ac）則稱（L，）為模格。Note:(1)任意一個分配格都是模格， 由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)當a=1時,若ab,則b也一定是1。故 a(bc)=1(1c) = 1 b(ac)=1(1c)= 11 = 1。(2)當a=0時,若ab,則b可能為0,b1,b2,b3,1。故 a

8、(bc)= 0(bc)=bc b(ac)=b(0c)= bc。1b3b20b1(3)當a= b1,b2,b3之一時， 若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。綜上，對任意a，b，cL，如果ab，都有a(bc）= b(ac) 。 1b3b20b1例子與結論前面描述的格L1、L2和L3都是模格，但L4不是。因為cd,但c (bd)=c,(cb) d=d 一個格L是模格當且僅當L不含與五角格同構的子格。一個模格是分配格當且僅當L不含與鉆石格同構的子格

9、模格的例群G中的所有正規(guī)子群做成一個模格。證明：設群G的所有正規(guī)子群做成的集合為S，規(guī)定S中兩種運算： ， ，對任意AS，BS，A與B的交集記為AB。A與B的乘積（記為AB）為如下集合：AB = y(A)(yB)（1）往證（S,， )是格 往證， 是S上的二元代數(shù)運算。因為正規(guī)子群的交仍為正規(guī)子群，故運算 對S封閉。 對任意AS，BS，對任意gG，任取ug（AB），于是，u = gab其中aA,bB。因為A，B是正規(guī)子群，所以gab = a1gb = a1b1g其中a1A,b1B。故u=gab（AB）g，故g（AB）（AB）g同理可證：（AB）g g（AB）。故 g（AB）=（AB）g即，AB

10、是正規(guī)子群.所以，乘運算對S也是封閉的。往證， 適合交換律、結合律、吸收律結合律 ， 滿足結合律是顯然的。交換律 滿足交換律是顯然的 對于乘運算 ：任取uAB,即 u=ab(aA,bB)。由于B是正規(guī)子群，所以， u = ab = b1a（b1B）故uBA，即AB BA。同理可證：BA AB，故AB=BA。即乘運算滿足交換律。吸收律 任取uA(AB),于是,u=ac,其中cAB,故u = acA，即A（AB）A。任取uA，因為A，B都是子群，故單位元素1在A中，也在B中，故1AB，故u = u1A（AB），即A A（AB）。故 A（AB）=A. 同理可證：A（AB）=A。 亦即：運算和滿足吸收

11、律。因此，（S，）是一個格。由于此格中的運算就是集合的交運算，故與（S，）等價的半序格的部份序就是集合之間的包含關系。 （2）往證（S,， )是 模格對任意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。因為a-1AB，uB，故a-1uB，即dB。故dCB。因此， u = adA（CB），即（AC）BA（CB），所以有 A（CB）=（AC）B由定義知，（S，）是模格。 定理7.4.3 格(L，)是模格的充要條件是：對任意a，b，cL，如果ab，ac=bc，ac=bc則必有a=b。證明：必要性。若格（L，）是模格，則對任意a，b，cL，如果ab，ac=bc，a c=b c，則a = a （ac）= a （bc） = b（ac）= b（bc）= b充分性。任取a，b，cL，且ab。因為(a(bc) c = a (bc)c)=ac 又因為ab，所以ab（ac），故a c（b（ac）c （a c） c = ac所以，（b（a c） c = a c。因此(a(bc