第6章 格与布尔代数ppt课件.ppt

《第6章 格与布尔代数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter6格与布尔代数格论(1935)是一种重要的代数结构,它是计算机语言的指称语义的理论基础，在计算机应用逻辑研究中有着重要作用.布尔代数是英国数学家GeorgeBoole在1847年左右在对逻辑思维法则进行研究时提出的，后来很多数学家特别是E.V.Hungtington和E.H.Stone对布尔代数的进行了一般化研究，在1938年C.E.Shannon发表的ASymbolicAnalysisofRelayandSwitchingCircuits论文，为布尔代数在工艺技术中的应用开创了先河,自此以后

2、布尔代数在自动推理和逻辑电路设计的分析和优化等问题的讨论中都有着最直接的应用,作为计算机设计基础的《数字逻辑》就是布尔代数.本章先介绍格,在此基础上引入分配格和有补格,而把布尔代数作为一种特殊的格加以讨论.6.1用偏序集定义的格1.格的第一种定义偏序集(L,)?Remark偏序集(L,)中不是任意两个元素均存在上确界及下确界的.{c,b},{a,d}?Def设(L,)是偏序集,若L中任意两个元素都存在上确界以及下确界,则称(L,)是格(lattice).为了方便,这样的格可称为偏序格.(Figure

3、6-3)钻石格与五角格?课堂练习习题6.11.例6-1(P170)证明:(P(X),)是格,其中P(X)是集合X的幂集.Proof(cf.Chapter1)A,BP(X),(1)sup{A,B}=AB,(2)inf{A,B}=AB.例6-2(P170)证明:(Dn,

4、)是格,其中Dn是自然数n的正因数组成的集合,

5、是其上的整除关系.Proof(cf.Chapter2)例6-3(P170)令F是所有合式公式(WFF)组成的集合,是公式间的逻辑蕴涵关系,则(F,)是格.Proof(cf.Chapt

6、er3)A,BF,(1)sup{A,B}=AB,(2)inf{A,B}=AB.2.格的性质Def设(L,)是格,x+y=sup{x,y},x∙y=inf{x,y}.格中的“+”是求上确界运算,可以看作是格的加法运算,读作“加”；同样,格中的“”是求下确界运算,可以看作是格的乘法运算,读作“乘”.(与环中的“加”和“乘”,以及数的“加”和“乘”不同)(与布尔代数的运算一致)由于“上确界上界”以及“下界下确界”,根据定义易知Theorem6-1设(L,)是格,则对于任意x,yL,有(1)x

7、x+y,yx+y.(2)x∙yx,x∙yy.(L,)与(L,)?Def对于任意关于格(L,)的命题,将命题前提和结论中的(1)改为;(2)+改为;(3)改为+；(4)0改为1；(5)1改为0所得到的命题称为原命题的对偶命题.Theorem6-2对于任意关于格(L,)的真命题,其对偶命题亦为真.如(1)xx+y,yx+y;(2)x∙yx,x∙yy.在格的性质中,有很多都是成对(dual)出现的.Theorem6-3(保序性)设(L,)是格,对于任意xi,yiL,i=1,2:P

8、roof(1)x1+x2是{x1,x2}的上确界;(2)y1+y2是{x1,x2}的上界:Theorem6-4(幂等性)设(L,)是格,xL,x+x=x,x∙x=x.格的特征性质.Theorem6-5格(L,)满足:(1)交换性.(2)结合性.(3)吸收性.Proof(3)xx,x∙yxx+(x∙y)x;显然,xx+(x∙y),所以x+(x∙y)=x.x∙(x+y)=x?(仿上;对偶)Theorem6-6设(L,)是格,则对于任意x,yL,下列三个命题等价:(1)xy.(2)x+y=

9、y.(2)x∙y=x.Proof(1)(2):xy,yyx+yy.显然,yx+yx+y=y.(2)(3):x∙(x+y)=x∙yx∙y=x.(3)(1):x=x∙yy.3.格的保序映射Def设(L1,1)和(L2,2)是格{偏序集即可},若存在:L1L2,则称为(L1,1)到(L2,2)的保序映射.例6-4(P173)?作业习题6.13,6,7.6.2用代数结构定义的格1.格的第二种定义Def设(L,+,∙)是代数结构,+和是L上的两个2元运算,同时满足:(1)交换性.

10、(2)结合性.(3)吸收性.则称(L,+,∙)为格,称这样定义的格为代数格.由定义知,格是具有两个2元运算的代数结构.为了下面的应用,首先证明两个命题.命题1设(L,+,∙)是代数结构,+和是L上的两个2元运算,若+和相互可吸收,则+和具有幂等性.Hint命题2设(L,+,∙)是代数结构,+和是L上的两个2元运算,若+和相互可吸收,则x,yL,x∙y=xx+y=y.2.格的两种定义的等价性格的这两