离散数学ii74几种特殊的格-1ppt课件

1、8.4.1 有有 界界 格格 8.4.2 有有 余余 格格 8.4.3 分分 配配 格格 8.4.4 模模 格格 引理引理1 设设(L，)是一个格。若是一个格。若S是是L的任意一个的任意一个有限非空子集，则有限非空子集，则S有一个最大下界和一个最有一个最大下界和一个最小上界。小上界。记集合记集合S的最大下界为的最大下界为inf S； 集合集合S的最小上界为的最小上界为sup S。 Note: 对于格的一个无穷子集，引理对于格的一个无穷子集，引理1的结论的结论不不成立。成立。 例例.在格在格I+，）中，所有正偶数组成的集合）中，所有正偶数组成的集合记为记为E+，显然，显然，E+ I+，但，但E+

2、没有最小上界。没有最小上界。定义定义. 格格L，）称为有界格，如果它有一）称为有界格，如果它有一个最大元素记为个最大元素记为1和一个最小元素记为和一个最小元素记为0），亦即，对任意），亦即，对任意aL，都有，都有 0a1 0，1称为格称为格L，）的界。）的界。 结论：有限格必是有界格结论：有限格必是有界格 令令L=a1，an , 0 = a1a2an, 1 = a1 a2 an 引理引理2. 假设假设L, ,0,1是有界格，则对任是有界格，则对任意意aL，恒有，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0。 定义定义. 在有界格在有界格L， ，0，1中，一个元中，一个

3、元素素bL，称为元素，称为元素aL的余元素，假设的余元素，假设 ab = 0， a b = 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， 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是一个是一个v有余格，如果对有余格，如果对L中每一个元素，都至少有一中每一个元素，都至少有一v个余元素。个余元素。v例例. n维格维格Ln，n是一个有余格，其中是一个有余格，其中v1n=(1，1，1), 0n=(0，0，0)是界。是界。v对任意对任意Ln中元素中元素a1，an），），v元素元素b1，bn是其是其 余元素，其中余元素，其中niababiiii, 10110例例. 设设S是有是有n个元素的集合，个元素的集合，(S)是是S的幂的幂集合，于是，（集合，于是，（S），），）是有余格。）是有余格。其中，其中， 和

5、和S是此格的界是此格的界.对对S中任意元素中任意元素A，S中的元中的元素素S-A是其余元素。是其余元素。定义定义8.4.4 格格L， ）称为分配格，如果对）称为分配格，如果对任意任意a，b，cL，恒有，恒有a（b c）=（ab） （ac）a （bc）=（a b）（a c）Note: (1)分配格定义中的两个等式是等价的分配格定义中的两个等式是等价的 (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不是。因为在L3中 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 任意一个链都是一个分配格。任意一个链都是一个分配格。证明：设格证明：设格L，）是一个链，任取）是一个链，任取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 设设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)(ab)=(aab) (bab) =(0b) (0a)= 0 0 = 0故由余元素定义知，

8、故由余元素定义知， （ab）= a b同理可证另一等式。同理可证另一等式。定理定理8.4.2 设格设格L， ）是分配格，对）是分配格，对任意任意a，b，cL，假设，假设 ac = bc， a c = b c，则有则有a = b。证 明 ： 假 设 证 明 ： 假 设 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 推论推论 设格设格L， ）是一个有余分配格，）是一个有余分配格，则对任意则对任意aL，a的余元素的余元素a是唯

9、一的。是唯一的。证明：证明： 因因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。 定义定义8.4.5 设设L，）是一个格，对任意）是一个格，对任意a，b，cL，如果，如果ab，都有，都有a （bc）= b（a c）则称则称L，）为模格。）为模格。Note:(1)任意一个分配格都是模格，任意一个分配格都是模格， 由由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)当当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)=bc b(a c)=b(0 c)= bc。1b3b20b1(3)当当a= b1,b2,b3之一时，之一时， 若若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。综上，对任意综上，对任意a，b，cL，如果，如果ab，都有，都有a (bc）= b(a c) 。 1b3b20b1l前面描述的格L1、L2和L3都是模格，但L4不是。因为cd,但c (bd)=c,(c b) d=dl 一个格L是模格当且仅当L不含与五角格同构的子格。l一个模格是分配格当且仅当L不含与钻石格同构的子格群群G中的所有正规子群做成一个模格。中的所有正规子群做成一个模格。定理定

12、理8.4.3 格格(L，)是模格的充要条件是：是模格的充要条件是：对任意对任意a，b，cL，假设，假设ab，ac=bc，a c=b c则必有则必有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充分性。任取充分性。任取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，）中，若）中，若ab，则有，则有1）式。式。 根据对偶原理根据对偶原理2，对任意，对任