离散数学第七章(第2讲)课件.ppt

1、7.2 7.2 分配格分配格对格对格中的任意元素中的任意元素a,b,c A，必有，必有a (b c)(a b)(a c)(a b)(a c)a (b c）当上述两式中等号成立的时候，就得到一类特殊的格。当上述两式中等号成立的时候，就得到一类特殊的格。定义定义设设是由格是由格所诱导的代数系统。所诱导的代数系统。如果对任意的如果对任意的a,b,c A，满足：，满足：a (b c)=(a b)(a c)a (b c)=(a b)(a c)则称则称是分配格。是分配格。例：判断图示的格是否是分配格例：判断图示的格是否是分配格 a3（a4a5）=a3a1=a3 （a3a4）（a3a5）=a4a6=a4 所

2、示的格不是分配格。所示的格不是分配格。定理定理如果格中交对并是分配的，那么并对交也是分配如果格中交对并是分配的，那么并对交也是分配的，反之亦然。的，反之亦然。证明：已知对格中任意元素证明：已知对格中任意元素a,b,c，有：，有：a (b c)(a b)(a c)，而，而(a b)(a c)=(a b)a)(a b)c)=a (a b)c)=a (a c)(b c)=(a (a c)(b c)=a (b c)即：并对交也是分配的。即：并对交也是分配的。定理定理每个链均是分配格。每个链均是分配格。证明：设证明：设是链。对任意是链。对任意a，b，c A (1)若若ab或或ac，则，则 a (b c)

3、a，(a b)(a c)a 即：即：a (b c)(a b)(a c)(2)若若ab且且ac，则，则 a (b c)b c，(a b)(a c)b c 即：即：a (b c)(a b)(a c)。定理成立。定理成立。定理：设定理：设A 是一个分配格，则对于任意是一个分配格，则对于任意a a，b b，c c A A，如果有如果有ab=acab=ac和和ab=acab=ac成立，则必有成立，则必有b=cb=c。证明：证明：对于任意对于任意a a，b b，c c A A，（ab）c =（ac）c=c （ab）c =（ac）（bc）=（ab）（bc）=b（ac）=b (ab)=b b=c 定义定义设设

4、是由格是由格所诱导的代数系统。所诱导的代数系统。对对A中任意中任意a，b，c，如果，如果b a，就，就有有a (b c)b (a c)则称则称为模格。为模格。定理定理分配格是模格。分配格是模格。证明：对于分配格中任意元素证明：对于分配格中任意元素a,b,c,有：有：a (b c)(a b)(a c)若若b a，则，则a b=b，代入上式得，代入上式得 a (b c)b (a c)分配格是模格。分配格是模格。7.3 7.3 有补格有补格定义定义设设是一个格，如果存在元素是一个格，如果存在元素a A，对于，对于任意的任意的x A，都有：，都有：a x，则称，则称a为格为格的全下的全下界，记格的全下

5、界为界，记格的全下界为0。定义定义设设是一个格，如果存在元素是一个格，如果存在元素b A，对于，对于任意的任意的x A，都有：，都有：x b，则称，则称b为格为格的全上的全上界，记格的全上界为界，记格的全上界为1。定理定理如果格如果格有全上界（全下界），那么它是唯有全上界（全下界），那么它是唯一的。一的。证明：（反证法）设格有两个不相等的全上界证明：（反证法）设格有两个不相等的全上界a和和b，则，则由定义由定义a b，且，且b a，由，由“”的反对称性，的反对称性，得得ab。所以假设不成立。所以假设不成立。定义定义设设是一个格，如果格中存在全上界和全下是一个格，如果格中存在全上界和全下界，则称

6、该格为有界格。界，则称该格为有界格。定理定理如果如果是有界格，全上界和全下界分别是是有界格，全上界和全下界分别是1和和0，则，则对任意元素对任意元素a A，有：，有：a 1=1 a=1 a 1=1 a=a a 0=0 a=a a 0=0 a=0 证明：证明：对任意元素对任意元素a A，有：，有：1 a 1，而而(a 1)A且且1是全上界，是全上界，a 1 1，根据偏序关系的反对称性可得根据偏序关系的反对称性可得 a 1=1。由交换律可得：由交换律可得：1 aa 1=1。定理定理如果如果是有界格，全上界和全下界分别是是有界格，全上界和全下界分别是1和和0，则对，则对任意元素任意元素a A，有：，

7、有：a 1=1 a=1 a 1=1 a=a a 0=0 a=a a 0=0 a=0 证明：证明：a aa，a1，a a 1，而而 a 1 a，根据偏序关系的反对称性可得，根据偏序关系的反对称性可得 ：a 1=a，由交换律可得：由交换律可得：a 11 a=a。类似可证另两式。类似可证另两式。定义定义设设是一个有界格，对于是一个有界格，对于A中的一个元素中的一个元素a，如，如果存在果存在b A，使得，使得a b=1和和a b=0，则称元素，则称元素b是元素是元素a的补元的补元,元素元素a是元素是元素b的补元。的补元。讨论定义：讨论定义：(1)0 1=1,0 1=0，即在有界格中，即在有界格中，1和

8、和0互为补元；互为补元；(2)由定义可知由定义可知A中一个元素的补元不一定是唯一的；可能中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。存在多个补元，也可能不存在补元。定义定义在一个有界格中，如果每个元素都至少有一个在一个有界格中，如果每个元素都至少有一个补元补元，则称此格为有补格。，则称此格为有补格。讨论定义：讨论定义：（1）在有补格中，每）在有补格中，每 个元素一定存在补元（不一定是个元素一定存在补元（不一定是一个补元）；一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。）有补格一定是有界格，而有界格不一定是有补格。如下图所示的格，是有补格吗？如下图所示的格，是有补格吗？a2，a3,a7等元素不存在补元等元素不存在补元 该格是有界格，该格是有界格，不是有补格。不是有补格。定理定理在有界分配格中，若有一个元素有补元，则必在有界分配格中，若有一个元素有补元，则必是唯一的。是唯一的。证明证明:(反证法反证法)假假设设a有两个不同的补元有两个不同的补元 b和和c,则有：则有：a b=1,a b=0 a c=1,a c=0 所以所以 a b=a c，a b=a c 由分配格中定理知：由分配格中定理知：b=c 故本定理成立。故本定理成立。