離散數(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，)是一個格。若S是L的任意一個有限非空子集，則S有一個最大下界和一個最小上界。 記集合S的最大下界為inf S； 集合S的最小上界為sup S。 Note: 對于格的一個無窮子集，引理1的結(jié)論不 成立。 例.在格（I+，）中，所有正偶數(shù)組成的集合 記為E+，顯然，E+ I+，但E+沒有最小上界。,定義. 格（L，）稱為有界格，如果它有一個最大元素（記為1）和一個最小元素（記為0），亦即，對任意aL，都有 0a1 0，1稱為格（L，）的界。 結(jié)

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，且

3、c1，c是0的余元素， 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）是其 余元素，其中,例. 設(shè)S是有n個元素的集合，(S)是S的冪 集合，于是，（S），）是有余格。 其中， 和S是此格的界. 對（S）中任意元素A，（S）中的元 素S-A是其余元素。,7.4.3 分 配 格,定義7.4.4

4、格（L，）稱為分配格，如果對任意a，b，cL，恒有 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 b b 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。

5、 L3稱為鉆石格， L4稱為五角格。,引理4 任意一個鏈都是一個分配格。 證明：設(shè)格（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 設(shè)（L,）是一個分配格,對任意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，）是分配格，對 任意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，）是一個有余分配格， 則對任意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，）是一個格，對任意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)=

8、1(1c) = 1 b(ac)=1(1c)= 11 = 1。 (2)當a=0時,若ab,則b可能為0,b1,b2,b3,1。故 a(bc)= 0(bc)=bc b(ac)=b(0c)= bc。,(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) 。,例子與結(jié)論,前面描述的格L1、L2和L3都是模格，但L4不是。因為cd,但c (bd)=c,(cb)

9、d=d 一個格L是模格當且僅當L不含與五角格同構(gòu)的子格。 一個模格是分配格當且僅當L不含與鉆石格同構(gòu)的子格,模格的例,群G中的所有正規(guī)子群做成一個模格。 證明：設(shè)群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 其

10、中a1A,b1B。故u=gab（AB）g，故 g（AB）（AB）g 同理可證：（AB）g g（AB）。故 g（AB）=（AB）g 即，AB是正規(guī)子群. 所以，乘運算對S也是封閉的。,往證， 適合交換律、結(jié)合律、吸收律 結(jié)合律 ， 滿足結(jié)合律是顯然的。 交換律 滿足交換律是顯然的 對于乘運算 ：任取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都是子

11、群，故單位元素1在A中，也在B中，故1AB，故 u = u1A（AB），即A A（AB）。 故 A（AB）=A. 同理可證：A（AB）=A。 亦即：運算和滿足吸收律。 因此，（S，）是一個格。 由于此格中的運算就是集合的交運算，故與 （S，）等價的半序格的部份序就是集合之 間的包含關(guān)系。,（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-1u

12、B，即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)c =(