格与布尔代数精选PPT.ppt

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

1、格与布尔代数第1页，此课件共65页哦n n中的应用开创了先河,自此以后布尔代数在自动推理和逻辑电路设计的分析和优化等问题的讨论中都有着最直接的应用,作为计算机设计基础的数字逻辑就是布尔代数.n n本章先介绍格本章先介绍格,在此基础上引入分配格和有补格在此基础上引入分配格和有补格,而把布而把布尔代数作为一种特殊的格加以讨论尔代数作为一种特殊的格加以讨论.第2页，此课件共65页哦6.1 用偏序集定义的格用偏序集定义的格n n1.格的第一种定义n n偏序集(L,)?n nRemark 偏序集(L,)中不是任意两个元素均存在上确界及下确界的.n nc,b,a,d?第3页，此课件共65页哦n nDef

2、设(L,)是偏序集,若L中任意两个元素都存在上确界以及下确界,则称(L,)是格格(lattice).为了方便,这样的格可称为偏序格偏序格.n n(Figure 6-3)钻石格钻石格与五角格五角格?n n课堂练习 习题6.1 1.第4页，此课件共65页哦n n例6-1(P170)证明:(P(X),)是格,其中P(X)是集合X的幂集.n nProof(cf.Chapter 1)A,B P(X),n n(1)supA,B=A B,n n(2)infA,B=A B.第5页，此课件共65页哦n n例6-2(P170)证明:(Dn,|)是格,其中Dn是自然数n的正因数组成的集合,|是其上的整除关系.n n

3、Proof(cf.Chapter 2)第6页，此课件共65页哦n n例6-3(P170)令F是所有合式公式(WFF)组成的集合,是公式间的逻辑蕴涵关系,则(F,)是格.n nProof(cf.Chapter 3)A,B F,n n(1)supA,B=A B,n n(2)infA,B=A B.第7页，此课件共65页哦n n2.格的性质n nDef 设(L,)是格,x+y=supx,y,x y=infx,y.n n格中的“+”是求上确界运算,可以看作是格的加法运算,读作“加”；同样,格中的“”是求下确界运算,可以看作是格的乘法运算,读作“乘”.(与环中的与环中的“加加”和和“乘乘”,”,以及数的以

4、及数的“加加”和和“乘乘”不同不同)(与布尔代数的运算一致与布尔代数的运算一致)第8页，此课件共65页哦n n由于“上确界上界”以及“下界下确界”,根据定义易知n nTheorem 6-1 设(L,)是格,则对于任意x,y L,有n n(1)x x+y,y x+y.n n(2)x y x,x y y.第9页，此课件共65页哦n n(L,)与(L,)?n nDef 对于任意关于格(L,)的命题,将命题前提和结论中的(1)改为;(2)+改为;(3)改为+；(4)0改为1；(5)1改为0所得到的命题称为原命题的对偶命题对偶命题.n nTheorem 6-2 对于任意关于格(L,)的真命题,其对偶命题

5、亦为真.n n如(1)x x+y,y x+y;(2)x y x,x y y.n n在格的性质中,有很多都是成对(dual)出现的.第10页，此课件共65页哦n nTheorem 6-3(保序性保序性)设(L,)是格,对于任意xi,yi L,i=1,2:n nProofn n(1)x1+x2 是x1,x2的上确界;n n(2)y1+y2 是x1,x2的上界:n nTheorem 6-4(幂等性幂等性)设(L,)是格,x L,x+x=x,x x=x.第11页，此课件共65页哦n n格的特征性质特征性质.n nTheorem 6-5 格(L,)满足:n n(1)交换性.n n(2)结合性.n n(3

6、)吸收性.n nProof(3)x x,x y x x+(x y)x;显然,x x+(x y),所以x+(x y)=x.n nx (x+y)=x?(仿上;对偶)第12页，此课件共65页哦n nTheorem 6-6 设(L,)是格,则对于任意x,y L,下列三个命题等价:n n(1)x y.n n(2)x+y=y.n n(2)x y=x.n nProof(1)(2):x y,y y x+y y.显然,y x+y x+y=y.n n(2)(3):x (x+y)=x y x y=x.n n(3)(1):x=x y y.第13页，此课件共65页哦n n3.格的保序映射n nDef 设(L1,1)和(

7、L2,2)是格偏序集即可,若存在:L1 L2,n n则称为(L1,1)到(L2,2)的保序映射.n n例6-4(P173)?n n作业 习题6.1 3,6,7.第14页，此课件共65页哦6.2 用代数结构定义的格用代数结构定义的格n n1.1.格的第二种定义n nDef Def 设(L,+,)是代数结构是代数结构,+,+和和 是是L L上的两个2 2元运算,同时满足同时满足:n n(1)交换性交换性.n n(2)(2)结合性结合性.n n(3)(3)吸收性吸收性.n n则称则称(L L,+,+,)为为格格格格,称这样定义的格为称这样定义的格为代数格代数格.n n由定义知由定义知,格是具有两个格

8、是具有两个2元运算的代数结构元运算的代数结构.第15页，此课件共65页哦n n为了下面的应用,首先证明两个命题.n n命题命题1 设(L,+,)是代数结构,+和是L上的两个2元运算,若+和相互可吸收,则+和具有幂等性.n nHint n n命题命题2 设(L,+,)是代数结构,+和是L上的两个2元运算,若+和相互可吸收,则x,y L,x y=x x+y=y.第16页，此课件共65页哦n n2.格的两种定义的等价性n n格的这两种定义是否是一回事?n nTheorem 6-7 偏序格(L,)与代数格(L,+,)是等价的.n nProof()n n()n n(1)是偏序.自反(命题1).反反对称对

9、称.传递.第17页，此课件共65页哦n n(2)对于任意x,y L,x y是x,y的下确界.n n(3)对于任意x,y L,x+y是x,y的上确界.n nx,y L,x y x y=x x+y=y(命题2).第18页，此课件共65页哦n n3.子格n n设(L,)是格,M L,在M上的限制仍记为.有例子表明,(M,)不一定是格.n n例6-5 X=a,b,M=,a,b P(X).n n(P(X),).n n(M,)不是格.n n例6-6 X=a,b,c,M=P(X)c.n n(P(X),).n n(M,)是格.第19页，此课件共65页哦n n借助于子代数给子格下的定义:n nDef 设(L,+

10、,)是格,M L,若(M,+,)是格,则称(M,+,)为(L,+,)的子格(sublattice).n n显然,(M,+,)为(L,+,)的子格 M关于+和封闭.n nRemark 设(L,+,)是格,M L,(M,)是格与(M,)是子格存在差异.正因为这样,才借助于子代数对子格定义.第20页，此课件共65页哦n n4.格的同态与同构n n可以类似地定义格的同态与同构.n nDef 设(L1,+,)和(L2,)是格,若存在:L1 L2,分别保持格的求上确界运算和求下确界运算,则称为(L1,+,)到(L2,)的格同态映射.n n格同构的直观意义?n nTheorem 6-8 格同态映射是保序映射

11、.第21页，此课件共65页哦n nRemark 格的保序映射不一定是格同态映射(习题).n n可以考虑格同构映射与格保序映射之间的关系.n n作业 习题6.2 1,4,6,8.第22页，此课件共65页哦6.3 分配格分配格n n1.分配格分配格(distributive lattice)的定义的定义n n有例子表明,格不满足分配性.n n例 6-9 举例说明在格(L,)中,格的乘法运算“”和格加法运算“+”相互不一定可分配.n nSolution第23页，此课件共65页哦n n钻石格?n n五角格?n nTheorem 6-9(分配不等式分配不等式)设(L,)是格,对于任意x,y,z L,有n

12、 n(1)x+(y z)(x+y)(x+z).n n(2)(dual?)n nProof(1)x+(y z)x+y;x+(y z)x+z.第24页，此课件共65页哦n nTheorem 6-10 设(L,+,)是格,则格的乘法运算“”对格的加法运算“+”可分配 格的加法运算“+”对格的乘法运算“”可分配.n nProof()x,y,z L:n n()第25页，此课件共65页哦n nDef 设(L,+,)是格,若格的乘法运算“”对格的加法运算“+”可分配(或格的加法运算“+”对格的乘法运算“”可分配),则称(L,+,)是分配格.n n例6-10 证明:(P(X),)是分配格.n n其他例子?第2

13、6页，此课件共65页哦n n钻石格和五角格是两个非常重要的非分配格的例子.我们只给出n nTheorem 6-11设(L,+,)是格,则L是分配格的充要条件是L中不含有同构于钻石格和五角格的子格.n n根据上述定理有以下两个推论.n nCorollary 1 小于5个元素的格为分配格.n nCorollary 2 任意链是分配格.n n(可直接证.)第27页，此课件共65页哦n n2.分配格的性质n nTheorem 6-12 设(L,+,)是格,则L是分配格的充要条件是对于任意x,y,z L,由x+y=x+z和x y=x z可以推出y=z.n nRemark 由x+y=x+z可以推出y=z?

14、x y=x z?n nProof()y=y+(x z)=(y+x)(y+z)=(z+x)(y+z)=(x y)+z=(x z)+z=z.n n()?n n判断一个格是否分配格?n n作业 习题6.3 2,5,7,9.第28页，此课件共65页哦6.4 有补格有补格n n1.有界格n n一般来说,格L不一定存在最大元与最小元.例如,实数集R关于数的小于等于关系 所作成的格(R,).n nDef 设(L,)是格,若L存在最大元素1以及最小元素0,则称(L,)为有界格有界格(bounded lattice).第29页，此课件共65页哦n n例6-12 证明:对任意集合X,(P(X),)是有界格.n n

15、Hint 最大元素最大元素:X X;最小元素最小元素:.n n显然,任意有限格是有界格(?).第30页，此课件共65页哦n n2.补元有补格n nDef 设(L,+,)是有界格,a L,若存在b L,使得a+b=1且a b=0,则称b为a的补元补元(complement).n n显然,在任意有界格中,若b为a的补元,则a为b的补元；0与1互为补元.但对于有界格,不是每个元素均有补元,同时一个元素的补元未必唯一.n n因此,不能定义1元运算 .第31页，此课件共65页哦第32页，此课件共65页哦n nDef 设(L,+,)是有界格,若L中每个元素都有补元,则称(L,+,)为有补格有补格(latt

16、ice complemented).n n例6-14 证明:对任意集合X,(P(X),)是有补格.n nHint A P(X),X-A P(X):n nA (X-A)=X,n nA (X-A)=.n n右图是有补格,不是分配格.第33页，此课件共65页哦n n几个重要结论.n nTheorem 6-13 在分配格中,若一个元素存在补元,则补元是唯一的.n nClearly.n n根据定理6-13知,在有补分配格中,每个元素都有唯一的补元.正因为如此,在有补分配格中可以定义一个元素的补运算“”，它是其上的1元代数运算.第34页，此课件共65页哦n n下述定理是有补分配格的重要性质.n nTheo

17、rem 6-14 设(L,+,)是有补分配格,则De Morgan律成立,即对于任意x,y L,有n n(1)n n(2)n nProof(1)n n(2)?第35页，此课件共65页哦n nTheorem 6-15 设(L,+,)是有补分配格,则对于任意x,y L,有n nProof 显然,n n(1)x y:n n(2)n n作业 习题6.4,4,5,6,7.第36页，此课件共65页哦6.5 布尔代数布尔代数n n1.1.布尔代数的格定义布尔代数的格定义n nDef Def 元素个数元素个数 2 2 的有补分配格(B B,)称为布尔代数布尔代数布尔代数布尔代数(Boolean algebra

18、)(Boolean algebra)或布尔格或布尔格.n n偏序集与各种格之间的相互关系偏序集与各种格之间的相互关系?n n仅仅1 1个元素的有补分配格是布尔代数的退化情形，一般不作为布尔代数考虑，可参见布尔代数的公理化定义.n n显然，在任何布尔代数或布尔格中有两个特殊元素，一个是其最小元0 0，一个是其最大元，一个是其最大元1.1.当然当然0 0 1 1.第37页，此课件共65页哦n n在任意布尔代数(B,)中可以定义3种代数运算:对于任意x,y B,n n(a)布尔加“+”:x+y=supx,y.n n(b)布尔乘“”:x y=infx,y.n n(c)布尔补“”:x的补元.n n例6-

19、16 设|X|1,证明:(P(X),)是布尔代数,称为集合代数集合代数:n n ,X).第38页，此课件共65页哦n n例6-17 证明:(F,)是布尔代数,其中F是所有合式公式组成的集合,是公式间的逻辑蕴涵关系,称为逻辑代数逻辑代数,F中的元素是逻辑表达式:n n特别地,令G是所有命题公式组成的集合,则称(G,)为命题代数.令H是仅含命题变元p1,p2,pn的所有命题公式组成的集合,则(H,)是布尔代数,这时n n由于集合代数和逻辑代数都是布尔代数,因此它们有完全相似的性质.第39页，此课件共65页哦n n2.布尔代数的性质n nTheorem 6-16 设(B,)是布尔代数,n nI.(B

20、,)是格;n nII.(B,)是分配格;n nIII.(B,)是有补格;n nIV.(B,)是有补分配格.第40页，此课件共65页哦n n以下是布尔代数的特征性质,参见下面的布尔代数的公理化定义.n n交换律.n n分配律.n n幺元律：n n有补律：第41页，此课件共65页哦n n3.布尔代数的公理化定义n nDef(E.V.Hungtington)设B是集合,|B|2,“+”和“”是B上的两个2元代数运算,“”是B上的1元代数运算,且满足n n(1)交换律.n n(2)分配律.n n(3)幺元律:n n(4)有补律:n n则称 是布尔代数布尔代数.n nRemark 按这种定义需强调两个0

21、元运算.第42页，此课件共65页哦n nTheorem 6-17 布尔代数的两种定义是等价的.n nProof 只需证明:满足定义6-13条件的代数结构是格且0和1分别是其最小元素和最大元素即可,因为根据(2)分配律和(4)有补律知是B有补分配格.n n首先注意,由于定义中的条件是对偶出现的,所以在该代数结构中,对偶原理成立.n n其次,x B,x+1=1.第43页，此课件共65页哦n n再其次,n n(B,+,)是格:n n(1)交换性.n n(2)吸收性.n n(3)结合性.n nB上定义:第44页，此课件共65页哦n n4.子布尔代数n n由于布尔代数中有两个0元运算:0和1,有必要对子

22、布尔代数给出定义.n nDef 设 是布尔代数,C B,若n n 是布尔代数,则称 是n n 的子布尔代数子布尔代数.n n显然,对于布尔代数 ,C B,则C是B的子布尔代数 0,1 C且C关于运算+,封闭.第45页，此课件共65页哦n n5.布尔代数的同态与同构n n定义两个布尔代数的同态与同构时,同样要注意布尔代数中的两个0元运算:0和1.n nDef 设 和 是布尔代数,若存在映射:B1 B2且保持所有布尔代数中的运算n n(1)n n(2)n n(3)n n(4)n n(5)第46页，此课件共65页哦n n布尔代数之间的同态(构)又称为布尔同态(构),它要求(1)(5)都要成立,但实际

23、上,其中的一些条件可以从别的条件推导出来,见本节习题8,9,10.n n由布尔代数的同构定义容易知道,2个元素的布尔代数是最简单的布尔代数,任意布尔代数都有同构于2个元素的布尔代数的子布尔代数.n n作业 习题6.5 16,8,9,10.第47页，此课件共65页哦6.6 有限布尔代数的结构有限布尔代数的结构n n有限布尔代数与无限布尔代数?n n对于集合代数(P(X),),当|X|=n1有限时P(X)有限,(P(X),)是有限布尔代数.n nTheorem(M.H.Stone)设 是有限布尔代数,则存在有限集合X使得 与集合代数 ,X)同构.第48页，此课件共65页哦n n实际上,集合X是由有

24、限布尔代数的所有原子组成的集合,先定义一般格上的原子的概念.n nDef 设(L,)是格,其最小元素为0,对于a L,若a盖住0,则a称为格的原子原子(atom).n n例子(图6-16)?第49页，此课件共65页哦n nProperty 1(P187)n nProperty 2(P188)n nProperty 3(P188)第50页，此课件共65页哦n nProperty 4(P188)n nProperty 5(P188)n nProperty 6(P188)第51页，此课件共65页哦n nProof of the Stone theorem:令集合X是由有限布尔代数 的所有原子组成的集

25、合.n n(0)=,n n单射?n n满射?n n保持运算?第52页，此课件共65页哦n n由Stone定理有n nCorollary 1 任意有限布尔代数的元素个数为2n,其中n为正整数.n nCorollary 2 在同构意义下,2n个元素的有限布尔代数是唯一的,其中n为正整数.n n作业 习题6.6 14.第53页，此课件共65页哦6.7 布尔表达式布尔表达式n n布尔表达式的化简及其主范式表示在理论研究和实际应布尔表达式的化简及其主范式表示在理论研究和实际应用中都有十分重要的意义用中都有十分重要的意义.n n1 1 布尔表达式的定义布尔表达式的定义布尔表达式的定义布尔表达式的定义n n

26、DefDef 设设 是布尔代数，则是布尔代数，则B B上的布尔表达式布尔表达式布尔表达式布尔表达式(Boolean expression)(Boolean expression)递归定义如下递归定义如下:n n(1)(1)B B中的元素中的元素a a,b b,c c等是布尔表达式等是布尔表达式.n n(2)(2)取值于B B的变元的变元x x1 1,x2 2,等是布尔表达式等是布尔表达式.n n(3)若若e e1和和e e2 2是布尔表达式，则是布尔表达式，则 ,e e1 1+e e2 2,e e1 1 e e2布尔表达布尔表达式式.n n(4)(4)有限次使用有限次使用(1)(2)(3)(1

27、)(2)(3)得到的字符串是仅有的布尔表达式得到的字符串是仅有的布尔表达式.第54页，此课件共65页哦n n例 设B=0,a,b,1,是布尔代数,则 等是B上的布尔表达式.n n含n个变元x1,x2,xn的布尔表达式记为E(x1,x2,xn).因此,上例中的两个布尔表达式分别记为 n n逻辑代数上的布尔表达式常称为逻辑表达式.第55页，此课件共65页哦n n设B=0,1,是布尔代数,它是最简单的逻辑代数.在计算机逻辑电路设计中,B中元素的0和1称为逻辑常量逻辑常量,B上的变元称为逻辑变量逻辑变量,B上的布尔表达式称为逻辑表达式逻辑表达式,它就是命题公式.例如 等是B上的布尔表达式.第56页，此

28、课件共65页哦n n2.布尔表达式的化简n n大家知道,在逻辑电路设计时,会用一个最简单的逻辑表达式去设计组合逻辑电路,因此布尔表达式的化简有着实际应用背景.n n很显然,对于例中的布尔表达式 若取x1=a,x1=a,则可求出该布尔表达式的值为第57页，此课件共65页哦n nDef 6-18n n将x1,x2,当作已经在B中取值,可以利用布尔代数的性质进行有关讨论.例如,第58页，此课件共65页哦n n对于布尔代数上的布尔表达式,与其相等的含最少运算符号“+”、“”及“”的布尔表达式是其最简形式.n n有限布尔代数上的布尔表达式的最简形式在理论上是存在的.在例中,的最简形式为第59页，此课件共

29、65页哦n n下面仅举一个例子介绍布尔表达式的代数化简方法,至于其他方法,如Quine方法和Karnaugh方法可参考其他文献.n n例6-21 设 是布尔代数,化简布尔表达式n nSolution第60页，此课件共65页哦n n3.布尔表达式的主范式n nDef 设 是布尔代数,由B上的n个变元x1,x2,xn产生的最小项最小项为1 2 n,最大项最大项为1+2+n,其中i为xi或n nDef 第61页，此课件共65页哦n n求取布尔表达式E(x1,x2,xn)的主析取范式与主合取范式与求取命题公式的主范式是类似的,其主要步骤如下:n n(1)将B上的变元看作常量使用布尔代数的性质；n n(

30、2)利用De Morgan律将“”深入到变元或常量的前面；n n(3)利用分配律展开；n n(4)补充所缺少的变元；n n(5)(随时)计算并合并常元.第62页，此课件共65页哦n n例6-22 设B=0,a,b,1,是布尔代数,求布尔表达式 的主析取范式与主合取范式.n nSolution 主析取范式:第63页，此课件共65页哦n n主合取范式:第64页，此课件共65页哦n n4.布尔函数n nDef 设 是布尔代数,称:Bn B为B上的n元布尔函数布尔函数(Boolean function).n n显然,布尔表达式(逻辑函数)是布尔函数.n n一般来说布尔函数不是布尔表达式.n n作业 习题6.7 1,2,3,4.第65页，此课件共65页哦