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

上传人(卖家):三亚风情 文档编号:3407065 上传时间:2022-08-28 格式:PPT 页数:16 大小:265.50KB
下载 相关 举报
离散数学第七章(第2讲)课件.ppt_第1页
第1页 / 共16页
离散数学第七章(第2讲)课件.ppt_第2页
第2页 / 共16页
离散数学第七章(第2讲)课件.ppt_第3页
第3页 / 共16页
离散数学第七章(第2讲)课件.ppt_第4页
第4页 / 共16页
离散数学第七章(第2讲)课件.ppt_第5页
第5页 / 共16页
点击查看更多>>
资源描述

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 故本定理成立。故本定理成立。

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(离散数学第七章(第2讲)课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|