离散数学：8.4 几种特殊的格

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+,

2、 但但E+没有最小上界。没有最小上界。 定义定义. 格（格（L，）称为）称为有界格有界格，如果它有一，如果它有一个最大元素（记为个最大元素（记为1）和一个最小元素（记为）和一个最小元素（记为0），亦即，对任意），亦即，对任意aL，都有，都有 0a1, 0，1称为格（称为格（L，）的界。）的界。 note:v有限格必是有界格。有限格必是有界格。 令令L=a1，an , 0 = a1a2an, 1 = a1 a2 an v有界格不一定是有限格。有界格不一定是有限格。 引理引理2. 若（若（L,0,1）是有界格，则对任）是有界格，则对任意意aL，恒有，恒有 a 0 = a， a1 = a， a 1

3、= 1， a0 = 0。定义定义. 在有界格（在有界格（L， ，0，1）中，一）中，一个元素个元素bL，称为元素，称为元素aL的的余元素余元素，如果，如果 ab = 0， a b = 1。Note: 在有界格中，一元素可能没有余元素；在有界格中，一元素可能没有余元素； 如果有余元素，则未必唯一。如果有余元素，则未必唯一。 引理引理3 在有界格（在有界格（L， ，0，1）中，）中， 1是是0的唯一一个余元素，反之亦然。的唯一一个余元素，反之亦然。证明：证明：由引理由引理2，01 = 0， 0 1 = 1， 所以，所以，0，1互为余元素。互为余元素。 若若cL，且，且c1，c是是0的余元素，则的余

4、元素，则0 c=1。 而由引理而由引理2知，知，0 c = c，故，故，c = 1，矛盾。，矛盾。 因此，因此，0的余元素只能是的余元素只能是1。 同理，同理，1的余元素只能是的余元素只能是0。例例. 证明：若一个有界格（证明：若一个有界格（L， ，0，1）含）含有不只一个元素，则该有界格中任何一个元素有不只一个元素，则该有界格中任何一个元素的余元素必不是它自身。的余元素必不是它自身。证明：证明：我们已经知道在有界格中我们已经知道在有界格中0，1互为余元素。互为余元素。若存在若存在x0，x1，但，但x以自身为余元素，则以自身为余元素，则xx=0， x x=1，而又由于而又由于xx=x， x x

5、=x，所以，所以，x=0，x=1，即，即0=1。由题设有界格（由题设有界格（L， ，0，1）含有不）含有不只只一一个元素知，个元素知，0 1，与，与0=1矛盾。矛盾。v定义定义. 称有界格（称有界格（L，0，1）是一个）是一个有余格，如果有余格，如果L中每一个元素都至少有一个余元中每一个元素都至少有一个余元素。素。v例例. n维格（维格（Ln，n）是一个有余格，其中）是一个有余格，其中1n=(1，1，1), 0n=(0，0，0)是界。是界。对任意对任意Ln中元素（中元素（a1，an），），元素（元素（b1，bn）是它的余元素，其中）是它的余元素，其中niababiiii, 10110例例. 设

6、设S是有是有n个元素的集合，于是，个元素的集合，于是， （S），）， ）是有余格。）是有余格。其中，其中， 和和S是此格的界是此格的界. 对对（S）中任意元素）中任意元素A，（S）中的元素）中的元素S-A是它的余元素。是它的余元素。例例. .证明：证明：设（设（L， ，0，1）为）为含有不只两含有不只两个元素的个元素的有限格，且相应的半序关系为全序关有限格，且相应的半序关系为全序关系系，则这个格必定不是有余格。则这个格必定不是有余格。证明：证明：任取任取L中非中非0、1的元素的元素x。l由于由于x0=0，但，但x 0=x1， x 1=1，但，但x1=x0，所以所以0和和1均不是均不是x的余元素

7、。的余元素。l对任意非对任意非0、非、非1的元素的元素y，则或者有，则或者有xy，或，或者者有有yx。不妨设前者成立，则。不妨设前者成立，则xy=x0，因此，因此，x无余元素。无余元素。即，若一个有限的全序格含有不只两个元素，则即，若一个有限的全序格含有不只两个元素，则其中非其中非0、非、非1元均无余元素，故不是有余格。元均无余元素，故不是有余格。定义定义8.4.4 格（格（L， ）称为分配格，如果对）称为分配格，如果对任意任意a，b，cL，恒有，恒有a（b c）=（ab） （ac）a （bc）=（a b）（a c）Note:l 分配格定义中的两个等式是等价的分配格定义中的两个等式是等价的由由

8、a (b c)=(a b) (a c) ，得，得(a b) (a c)=(a b) a) (a b) c)=a (a c) (b c)=(a (a c) (b c)=a (b c)l不是所有的格都是分配格不是所有的格都是分配格l分配格的任意子格仍是分配格分配格的任意子格仍是分配格例例. n维格（维格（Ln，n），格（），格（S），）， ），）， 格（格（I+，D），格（），格（Sn，D）都是分配格。）都是分配格。引理引理4 任意一个链都是一个分配格。任意一个链都是一个分配格。证明：证明：设设(L,)是一个链，显然是一个链，显然,（L,)是格。是格。任取任取a,b,c L, 1）若）若ab且且a

9、c，于是，于是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定律定律定理定理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而而

10、(a b)(ab)=(aab) (bab) =(0b) (0a)= 0 0 = 0故由余元素定义知，故由余元素定义知， （ab）= a b同理可证另一等式。同理可证另一等式。例例. 设（设（L，*，+，0，1）是有界分配格，证明：）是有界分配格，证明：L中拥有余元素的的各元素构成一个代数子格。中拥有余元素的的各元素构成一个代数子格。证明：设证明：设L中拥有余元素的元素的集合为中拥有余元素的元素的集合为L。任取任取L中元素中元素a,b，设，设a,b的的余元素分别为余元素分别为a和和b。则则 (a+b) * (a * b)=(a*a*b)+(b*a*b)=0+0=0 (a+b)+(a * b)=(

11、a+b+a)*(a+b+b)=1*1=1所以所以a+b有余元素有余元素a*b，即，即，a +bL。同理，同理，a*b有余元素有余元素a+b ，即，即， a*bL。所以所以L对运算对运算*，+封闭，封闭，故（故（L ，*，+，0，1）是（）是（L，*，+，0，1）的）的代数子格。代数子格。定理定理8.4.2 设格（设格（L，）是分配格，对）是分配格，对任意任意a，b，cL，如果，如果 ac = bc， ac = bc，则有则有a = b。证明：证明：a = a（ac）= a（bc） =（ab）（ac） =（ab）（bc）= b（ac） = b（bc）= b 推论推论 设格（设格（L，）是一个有余

12、分配格，）是一个有余分配格，则对任意则对任意aL，a的余元素的余元素a是唯一的。是唯一的。证明：证明： 因（因（L，）是有余格，设）是有余格，设a和和a都都是是a的余元素，即的余元素，即 aa= 0， aa= 1 aa= 0， aa= 1故故aa= aa，aa= aa。由定理由定理8.4.2知，知，a= a。 定义定义8.4.5 设（设（L，）是一个格，对任意）是一个格，对任意a，b，cL，如果，如果ab，都有，都有a（bc）= b（ac）则称（则称（L，）为模格。）为模格。Note:Note:v 不是任意格都是模格。不是任意格都是模格。v 任意一个分配格都是模格。任意一个分配格都是模格。 由

13、由ab， ab=b,故故 a（bc）= （ab）（ a c） = b（ac）v 模格不一定是分配格。模格不一定是分配格。例例.如图所示如图所示,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(bc)= 0(bc)=bc b(ac)=b(0c)= bc。1b3

14、b20b1(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群群(G, )中的所有正规子群做成一个模格。中的所有正规子群做成一个模格。证明：证明：设群设群G的所有正规子群做成的集合为的所有正规子群做成的集合为S，规定规定S中两种运算：中两种运算： ， ，对任意，对任意AS，BS

15、，vA与与B的交集记为的交集记为AB。vA与与B的乘积（记为的乘积（记为AB）为如下集合：）为如下集合：AB = x y (xA)(yB)（1）往证（）往证（S,， )是格是格. 往证往证， 是是S上的二元代数运算。上的二元代数运算。v因为正规子群的交仍为正规子群，故运算因为正规子群的交仍为正规子群，故运算 对对S封闭。封闭。v 对任意对任意AS，BS，对任意，对任意gG，任取，任取ug（AB），于是，），于是，u = g a b其中其中aA,bB。因为。因为A，B是正规子群，所以是正规子群，所以g a b = a1 g b = a1 b1 g其中其中a1A,b1B。故。故u=g a b=a1

16、 b1 g（AB）g，故故 g（AB） （AB）g同理可证：（同理可证：（AB）g g（AB）。故）。故 g（AB）=（AB）g即，即，AB是正规子群是正规子群.所以，乘运算所以，乘运算对对S也是封闭的。也是封闭的。 往证往证， 适合交换律、结合律、吸收律适合交换律、结合律、吸收律结合律结合律 ， 满足结合律是显然的。满足结合律是显然的。交换律交换律 满足交换律是显然的满足交换律是显然的 对于乘运算对于乘运算 ：任取：任取uAB,即即u=a b (aA,bB)。由于由于B是正规子群，所以，是正规子群，所以，u = a b = b1 a（b1B）故故uBA，即，即AB BA。同理可证：同理可证：

17、BA AB，故，故AB=BA。即乘运算满足交换律。即乘运算满足交换律。吸收律吸收律 任取任取uA(AB),于是于是,u=a c, 其中其中aA, cAB故故u = a cA，即，即A（AB） A。任取任取uA，因为，因为A，B都是子群，故单位元素都是子群，故单位元素1在在A中，也在中，也在B中，故中，故1AB，因此，因此，u = u 1A（AB），即），即A A（AB）。）。故故 A（AB）=A. 同理可证：同理可证：A（AB）=A。因此，（因此，（S，）是一个格。）是一个格。由于此格中的运算由于此格中的运算就是集合的交运算，故与就是集合的交运算，故与（S，）等价的半序格的部份序就是集合之）等

18、价的半序格的部份序就是集合之间的包含关系。间的包含关系。 （2）往证模等式成立）往证模等式成立.对任意对任意AS，BS，CS，如果如果A B，往证，往证A（ B C ）= B （AC）l任取任取u A（ B C ）,于是于是,u=a d, 其中其中aA, dB C, 由由aA, A B，知，知aB，再由，再由dB，知，知u= a dB。由由aA, dC,知知 u=a dAC。因此，因此， u=a d B （AC），），即即 A（CB） B （AC）。l任取任取u B （AC）,于是于是, u B, u AC。令令 u=a d (其中其中a A，d C)， 则则d = a-1 u， 往证往证d B。因为因为a A， A是是G的子群，所以的子群，所以a-1 A，而，而A B，因此，因此 a-1 B而而u B，故，故 a-1 u B，即，即d B。再由再由d C，知，知d B C ，而，而a A，因此，因此， u = a d A（ B C ），），即即B （AC） A（ B C ）。因此，因此，A（ B C ）= B （AC）。综上，（综上，（S，）是模格。）是模格。 定理定理8.