格与布尔代数-PPT.pptx

《格与布尔代数-PPT.pptx》由会员分享，可在线阅读，更多相关《格与布尔代数-PPT.pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、格与布尔代数2023/6/14第6章 格与布尔代数集合的表示方法2子格3特殊格4偏序格与代数格1格的性质2布尔代数52023/6/146、1 格得定义 2023/6/14一、定义设就是一个偏序集,如果对任意a,bL,a,b都有最大下界与最小上界存在,则称就是格,简称L就是格。若L为有限集,则称格为有限格。2023/6/14用 a b表示a,b得最小上界,用a b表示a,b得最大下界读作“并”读作“交”2023/6/14例(1)Sn表示n得所有因子得集合,D就是一个整除关系,问此偏序集就是否就是一个格？(2)设A就是一个集合,P(A)就是A得幂集,就是集合上得包含关系,问此偏序集就是否就是一个格

2、？定理(格得基本性质)设就是格,则运算与适合交换律、结合律、幂等律与吸收律,即(1)a,bL 有 ab=ba,ab=ba(2)a,b,cL 有(ab)c=a(bc),(ab)c=a(bc)(3)aL 有 aa=a,aa=a(4)a,bL 有a(ab)=a,a(ab)=a 定理(格得性质:序与运算得关系)设L就是格,则a,bL有a b ab=a ab=b定理(格得保序性)设L就是格,a,b,c,dL,若a b 且 c d,则 ac bd,ac bd定理:设L就是格,a,b,cL有 a(bc)(ab)(ac)、注意:一般说来,格中得与运算不满足分配律、大家有疑问的，可以询问和交流可以互相讨论下，但

3、要小声点2023/6/14二、子格设(L,)就是一个格,S就是L得一个子集,(S,)称为(L,)得一个子格,当且仅当在运算,下,S就是封闭得。e f g bd c ah例:S=a,b,c,d,e,f,g,h构成格S1=a,b,d,f与S2=c,e,g,h与S3=a,b,c,d,e,g,h都构成格但S3不就是S得子格对偶式:格中元素用运算符,连接起来得得一个表达式f,将f中得换成,将换成,如有0,1,将0换成1,将1换成0,所形成得表达式称为f得对偶表达式记作f*。对偶原理:对于中任一真命题,其对偶命题也真。三、格得同态与同构定义:设与就是两个格,它们分别诱导得代数系统为与,若存在一个从A1到A

4、2得映射f,使得对于任意得a,bA1,有f(a1b)f(a)2f(b)f(a1b)f(a)2f(b)则称f就是从到得格同态。亦称就是得格同态象。当f就是双射得,则称f就是从到得格同构,亦称格与就是同构得。定理:设f就是格到格同态,则对任意得a,bA1,若a1b,必有f(a)2 f(b)。定理:设与就是两个格,f就是从A1到A2双射,则f就是从到得格同构,当且仅当,对任意得a,bA1,a1bf(a)2 f(b)。2023/6/146、2、分配格设就是格,若a,b,c L,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称L为分配格、2023/6/14例a(c)bcdea(b)b c

5、 de(a)2023/6/14例设A为任意一个集合,格就是否就是分配格？2023/6/14定理1所有链都就是分配格。定理2:如果在一个格中交运算对并运算可分配,则并运算对交运算也就是可分配得。反之亦然。2023/6/14定理3一个格就是分配格得充分必要条件就是该格中没有任何子格与两个五元素格中得任何一个同构。定理4定理:设格就是分配格,对任意a,b,cL,如果acbc,acbc则有ab。证明:若就是分配格,且acbc,acbc,则aa(ac)a(bc)(ab)(ac)(ab)(bc)b(ac)b(bc)b2023/6/14性质(1)四个元素以下得格都就是分配格;(2)五个元素得格仅有两个格就是

6、非分配格,其余三个格(右图(a),(b)与(c)都就是分配格。(a)(a)abcde(b)ab cde(c)abc de6、3 有补格2023/6/14一、有界格1、设就是一个格,若存在元素aL,使得对任意xL,都有:a x,则称a为格得全下界,记为02、设就是一个格,若存在元素aL,使得对任意xL,都有:x a,则称a为格得全上界,记为13、具有全上界与全下界得格称为有界格。记为 例:定理:设就是有界格,则aL有:a0=0,a0=a,a1=a,a1=1注意:(1)有限格L=a1,a2,an就是有界格,a1a2an就是L得全下界,a1a2an就是L得全上界、(2)0就是关于运算得零元,运算得幺

7、元;1就是关于运算得零元,运算得幺元、(3)对于涉及到有界格得命题,如果其中含有全下界0或全上界1,在求该命题得对偶命题时,必须将0替换成1,而将1替换成0、2023/6/14定理在格中,全下界与全上界分别就是集合L得最小元与最大元,由于最大元与最小元得惟一性,有下面得定理:设就是一个格,若格得全上界与全下界存在,则必惟一。2023/6/14二、补元设为有界格,1与0分别为它得全上界与全下界,aL。如果存在bL,使得ab=0,ab=1,则称b为a得补元,记为。2023/6/14例如下图有界格,求其所有元素得补元(如果有得话)。c0(b)db1 a0(a)d eb1a c定理 设就是有界分配格、

8、若L中元素 a 存在补元,则存在惟一得补元、证:假设 c 就是 a 得补元,则有 ac=1,ac=0,又知 b 就是 a 得补元,故 ab=1,ab=0 从而得到 ac=ab,ac=ab,由于L就是分配格,b=c、三、有补格若有界格中得所有元素都存在补元,则称为有补格。2023/6/14四、有补分配格2023/6/14有补分配格:布尔格。由一个布尔格所诱导得一个代数系统可记为:。称为布尔代数。6、4 布尔代数定义:一个有补分配格就是一个布尔代数,可记为。设就是一个布尔代数,a,b,c就是集合B中任意元素,于就是,它有如下性质:(1)因为就是一个格,所以有 aaa aaa abba abba(ab)ca(bc)(ab)ca(bc)a(ab)a a(ab)a(2)因为就是分配格,所以有 a(bc)(ab)(ac)a(bc)(ab)(ac)(3)因为就是有界格,所以有 a00 a11 a1a a0a(4)因为就是有补分配格,所以有 a 0 a 1 01 10