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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,7.2,分配格,对格,中的任意元素,a,b,cA,，必有,a,(b,c)(a,b),(a,c),(a,b),(a,c)a,(b,c,）,当上述两式中等号成立的时候，就得到一类特殊的格。,定义,设,是由格,所诱导的代数系统。如果对任意的,a,b,cA,，满足：,a,(b,c)=(a,b),(a,c),a,(b,c)=(a,b),(a,c),则称,是分配格。,例：判断图示的格是否是分配格,a,3,（,a,4,a,5,）,=a,3,a,1,=a,3,（,a,3,a,4,）（,a,3,a,5,）,=a,4,a,6,=a,4,所示的格不是分配格。,定理,如果格中交对并是分配的，那么并对交也是分配的，反之亦然。,证明：已知对格中任意元素,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,，,cA,(1),若,a,b,或,a,c,，则,a,(b,c),a,，,(a,b),(a,c),a,即：,a,(b,c),(a,b),(a,c),(2),若,a,b,且,a,c,，则,a,(b,c),b,c,，,(a,b),(a,c),b,c,即：,a,(b,c),(a,b),(a,c),。,定理成立。,定理：设,是一个分配格，则对于任意,a,，,b,，,c,A,，如果有,ab=ac,和,ab=ac,成立，则必有,b=c,。,证明：,对于任意,a,，,b,，,c,A,，,（,ab,）,c =,（,ac,）,c=c,（,ab,）,c =,（,ac,）（,bc,）,=,（,ab,）（,bc,）,=b,（,ac,）,=b (ab),=b,b=c,定义,设,是由格,所诱导的代数系统。,对,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,有补格,定义,设,是一个格，如果存在元素,aA,，对于任意的,x A,，都有：,a x,，则称,a,为格,的全下界，记格的全下界为,0,。,定义,设,是一个格，如果存在元素,bA,，对于任意的,x A,，都有：,x b,，则称,b,为格,的全上界，记格的全上界为,1,。,定理,如果格,有全上界（全下界），那么它是唯一的。,证明：（反证法）设格有两个不相等的全上界,a,和,b,，则由定义,a,b,，且,b,a,，由“,”的反对称性，得,a,b,。所以假设不成立。,定义,设,是一个格，如果格中存在全上界和全下界，则称该格为有界格。,定理,如果,是有界格，全上界和全下界分别是,1,和,0,，则对任意元素,aA,，有：,a,1=1a=1,a1=1a=a,a,0=0a=a,a0=0a=0,证明：,对任意元素,aA,，有：,1,a,1,，,而,(,a,1),A,且,1,是全上界，,a,1,1,，,根据偏序关系的反对称性可得,a,1,=,1,。,由交换律可得：,1,a,a,1,=,1,。,定理,如果,是有界格，全上界和全下界分别是,1,和,0,，则对任意元素,aA,，有：,a,1=1a=1,a1=1a=a,a,0=0a=a,a0=0a=0,证明：,a,a,，,a,1,，,a,a,1,，,而,a1,a,，,根据偏序关系的反对称性可得,：,a1=a,，,由交换律可得：,a,1,1,a=a,。,类似可证另两式。,定义,设,是一个有界格，对于,A,中的一个元素,a,，如果存在,bA,，使得,a,b=1,和,ab=0,，则称元素,b,是元素,a,的补元,元素,a,是元素,b,的补元。,讨论定义：,(1)0,1=1,01=0,，即在有界格中，,1,和,0,互为补元；,(2),由定义可知,A,中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。,定义,在一个有界格中，如果每个元素都至少有一个补元，则称此格为有补格。,讨论定义：,（,1,）在有补格中，每 个元素一定存在补元（不一定是一个补元）；,（,2,）有补格一定是有界格，而有界格不一定是有补格。,如下图所示的格，是有补格吗？,a2,，,a3,a7,等元素不存在补元,该格是有界格，不是有补格。,定理,在有界分配格中，若有一个元素有补元，则必是唯一的。,证明,:(,反证法,),假,设,a,有两个不同的补元,b,和,c,则有：,a,b=1,ab=0,a,c=1,ac=0,所以,a,b=,a,c,，,ab=ac,由分配格中定理知：,b=c,故本定理成立。,