《《离散数学》课件：8-4-几种特殊的格》由会员分享，可在线阅读，更多相关《《离散数学》课件：8-4-几种特殊的格（23页珍藏版）》请在金锄头文库上搜索。
1、8.4 几种特殊的格几种特殊的格 8.4.1 有有 界界 格格 8.4.2 有有 余余 格格 8.4.3 分分 配配 格格 8.4.4 模模 格格 1 18.4.1 有界格有界格 引引理理1 设设(L,)是是一一个个格格。若若S是是L的的任任意意一一个个有有限限非非空空子子集集，则则S有有一一个个最最大大下下界界和和一个最小上界。一个最小上界。记集合记集合S的最大下界为的最大下界为infS； 集合集合S的最小上界为的最小上界为supS。注注：对对于于格格的的一一个个无无穷穷子子集集，引引理理1的的结结论论不成立。不成立。例例：在在格格(I+,)中中，所所有有正正偶偶数数组组成成的的集集合合记记
2、为为E+，显显然然，E+ I+，但但E+没没有有最最小小上上界。界。2 2定定义义8.4.1 格格(L,)称称为为有有界界格格，如如果果它它有有一一个个最最大大元元素素(记记为为1)和和一一个个最最小小元元素素(记记为为0)，亦亦即即，对对任任意意aL，都都有有0a1，0, 1称为格称为格(L,)的的界界。结论：结论：有限格必是有界格。有限格必是有界格。令令L=a1,an，0=a1a2an，1=a1a2an 引引理理2 若若(L, 0, 1)是是有有界界格格，则则对对任任意意aL，恒有：恒有： a0=a，a1=a， a1=1，a0=0。 3 3定定义义8.4.2 在在有有界界格格(L, , 0
3、, 1)中中，一一个个元元素素bL，称称为为元元素素aL的的余余元元素素，如如果果ab=0，a b=1引引理理3 在在有有界界格格(L, , 0, 1)中中，1是是0的唯一一个余元素，反之亦然。的唯一一个余元素，反之亦然。证证明明：由由引引理理2，01=0，0 1=1，所所以以，0,1互为余元素。互为余元素。若若cL，且且c1，c是是0的的余余元元素素，0c=0，0 c=1。但是，由引理但是，由引理2知，知，0 c=c。故，故，c=1，矛盾。矛盾。4 48.4.2 有余格有余格 定定义义8.4.3 称称有有界界格格(L, , 0, 1)是是一一个个有有余余格格，如如果果对对L中中每每一一个个元
4、元素素，都都至至少少有有一个余元素。一个余元素。例例：n维维格格(Ln,n)是是一一个个有有余余格格，其其中中1n=(1, 1, 1)，0n=(0, 0, 0)是是界界。对对任任意意Ln中中元元素素(a1, , an)，元元素素(b1, , bn)是其余元素，其中：是其余元素，其中：5 5设设S是有是有n个元素的集合，个元素的集合，(S)是是S的幂集的幂集合，于是，合，于是，(S), )是有余格。是有余格。其中，其中， 和和S是此格的界。是此格的界。对对(S)中任意元素中任意元素A，(S)中的元素中的元素S-A是是其余元素。其余元素。例：例： 6 68.4.3 分配格分配格 定定义义8.4.4
5、 格格(L, )称称为为分分配配格格，如如果果对任意对任意a,b,cL，恒有恒有a(b c)=(ab) (ac)a (bc)=(a b)(a c)注：注：1)分配格定义中的两个等式是等价的。分配格定义中的两个等式是等价的。2)n维格维格(Ln,n)，格，格(S), )，格，格(I+, D)，格，格(Sn, D)都是分配格。但不是所有的都是分配格。但不是所有的格都是分配格。格都是分配格。3)分配格的任意子格仍是分配格。分配格的任意子格仍是分配格。 7 7任意一个链都是一个分配格。任意一个链都是一个分配格。证证 明明 ： 设设 格格 (L,)是是 一一 个个 链链 ， 任任 取取a,b,cL，1)
6、若若ab且且ac，于是于是abc，故故 a(bc)=bc而而ab=b，ac=c，所以：，所以：(ab)(ac)=bc故故a(bc)=(ab)(ac)。2)若若ab或者或者ac，于是于是a(bc)，故故a(bc)=a。而。而(ab)(ac)=a所以所以a(bc)=(ab)(ac)。引理引理4 8 8De Morgan定律定律定定理理8.4.1 设设(L, )是是一一个个分分配配格格，对对任意任意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)(a
7、b)=(aab) (bab)=(0b) (0a)=0 0=0故由余元素定义知，故由余元素定义知， (ab)=a b同理可证另一等式。同理可证另一等式。9 9设设格格(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 定理定理8.4.21010设设格格(L, )是是一一个个有有余余分分配配格格，则则对对任任意意aL，a的余元素的余元素a是唯一的。是唯一的。证证明明：因因
8、(L, )是是有有余余格格，设设a和和a都都是是a的余元素，即的余元素，即 aa=0，a a=1 aa=0，a a=1故故aa=aa，a a=a a。由定理由定理8.4.2知，知，a=a。 推论推论11118.4.4 模格模格 定义定义8.4.5 设设(L,)是一个格，对任意是一个格，对任意a,b,cL，如果如果ab，都有：都有：a (bc)=b(a c)则称则称(L,)为模格。为模格。注意：注意：1)任任意意一一个个分分配配格格都都是是模模格格，由由ab， a b=b，故：，故：a (bc)=(a b)( a c) =b(a c)2)模格不一定是分配格。模格不一定是分配格。 1212如图所示
9、，如图所示，L=0,1,b1,b2,b3。则，则，格格(L, )不是分配格：不是分配格： b1(b2 b3)=b1(b1b2) (b1b3)=0。格格(L, )是模格：是模格：1)当当a=1时时，若，若ab，则，则b也一定是也一定是1。故。故 a (bc)=1 (1c)=1 b(a c)=1(1 c)=11=1。2)当当a=0时时，若，若ab，则，则b可能为可能为0,b1,b2,b3,1。故故a (bc)=0 (bc)=bcb(a c)=b(0 c)=bc。1b3b20b1例：例： 13133)当当a=b1,b2,b3之一时之一时，若若ab，则，则b是是1或或a。若若b=1，则：，则： a(b
10、c)=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)。 1b3b20b11414模格的例：模格的例：群群G中的所有正规子群做成一个模格。中的所有正规子群做成一个模格。证明：证明：设群设群G的所有正规子群做成的集合的所有正规子群做成的集合为为S，规定，规定S中两种运算：中两种运算：, ，对任意对任意AS，BS，A与与B的交集记为的交集记为AB。A与与B的乘积的乘积(记为记为AB)为如下集合：为如下集合：AB=xy (xA)(yB)1)往证
11、往证(S, )是格。是格。往证往证, 是是S上的二元代数运算。上的二元代数运算。因因为为正正规规子子群群的的交交仍仍为为正正规规子子群群，故故运运算算对对S封闭。封闭。1515对对 任任 意意 AS， BS， 对对 任任 意意 gG， 任任 取取ug(AB)， 于于 是是 ， u=gab。 其其 中中 aA，bB。因因为为A,B是是正正规规子子群群，所所以以gab=a1gb=a1b1g其中其中a1A，b1B。故：。故：u=gab(AB)g，故故g(AB) (AB)g同理可证：同理可证：(AB)g g(AB)。故。故 g(AB)=(AB)g即，即，AB是正规子群是正规子群.所以，乘运算所以，乘运
12、算对对S也是封闭的。也是封闭的。证明：证明：1616往证往证, 适合交换律、结合律、吸收律。适合交换律、结合律、吸收律。结合律：结合律：, 满足结合律是显然的。满足结合律是显然的。交换律：交换律： 满足交换律是显然的。满足交换律是显然的。对于对于乘运算乘运算 ：任取：任取uAB，即：，即：u=ab(aA，bB)由于由于B是正规子群，所以，是正规子群，所以，u=ab=b1a(b1B)故故uBA，即，即AB BA。同理可证：同理可证：BA AB，故，故AB=BA。即乘运算满足交换律。即乘运算满足交换律。1717吸吸收收律律：任任取取uA(AB)，于于是是，u=ac， 其其 中中 cAB， 故故 u
13、=acA， 即即A(AB) A。任任取取uA，因因为为A,B都都是是子子群群，故故单单位位元元素素1在在A中，也在中，也在B中，故中，故1AB，故：，故：u=u1A(AB)，即即A A(AB)。故故A(AB)=A。同理可证。同理可证:A(AB)=A。亦即：运算亦即：运算和和满足吸收律。满足吸收律。因此，因此，(S, )是一个格。是一个格。由由于于此此格格中中的的运运算算就就是是集集合合的的交交运运算算，故故与与(S, )等等价价的的半半序序格格的的部部份份序序就就是是集合之间的包含关系。集合之间的包含关系。 18182)往证往证(S, )是模格。是模格。对任意对任意AS，BS，CS，如果如果A
14、 B，任取任取uA(CB)，于是，于是，u=ad，其中，其中dCB，aA，而，而A AC，故，故u=ad(AC)B，即，即A(CB) (AC)B。任取任取u(AC)B,于是于是,uB,uAC。令令u=ad(其其中中aA,dC)，于于是是，d=a-1u。因因为为a-1A B，uB，故故a-1uB，即即dB。故。故dCB。因此，因此， u=adA(CB)，即，即(AC)B A(CB)，所以有所以有A(CB)=(AC)B由定义知，由定义知，(S, )是模格。是模格。 1919格格(L,)是模格的充要条件是：是模格的充要条件是：对任意对任意a,b,cL，如果：，如果：ab，ac=bc，a c=b c，
15、则必有，则必有a=b。证证明明：必必要要性性。若若格格(L，)是是模模格格，则则对对任意任意a,b,cL，如果：，如果：ab，ac=bc，a c=b c，则，则a=a (ac)=a (bc) =b(a c)=b(b c)=b定理定理8.4.32020充分性。充分性。任取任取a,b,cL，且，且ab。因因为为(a (bc) c=a (bc) c)=a c 又因为又因为ab，所以所以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,)中中 ， 若若 a
16、b， 则则 有有(1)式。式。证明：证明：2121根根据据对对偶偶原原理理2，对对任任意意a,b,cL，若若ab，则有：，则有： (a(b c)c=(b (ac)c因此，当因此，当ab，即，即ba时，有时，有(b(a c)c=(a (bc)c (2)由格的分配不等式知，当由格的分配不等式知，当ab时，有时，有a (bc)b(a c) (3)由由(1)，(2)，(3)式及此定理的条件，得式及此定理的条件，得a (bc)=b(a c)故故(L,)是模格。是模格。证明：证明：2222作业作业11给出所有的给出所有的5元格元格(画出画出Hasse图即可图即可)，并说明哪些是模格，哪些是分配格，哪并说明哪些是模格，哪些是分配格，哪些是有余格。些是有余格。2323
