格与布尔代数精选文档.ppt

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

1、格与布尔代数本讲稿第一页，共六十五页n n中的应用开创了先河中的应用开创了先河,自此以后布尔代数在自动推自此以后布尔代数在自动推理和逻辑电路设计的分析和优化等问题的讨论中都理和逻辑电路设计的分析和优化等问题的讨论中都有着最直接的应用有着最直接的应用,作为计算机设计基础的数字作为计算机设计基础的数字逻辑就是布尔代数逻辑就是布尔代数.n n本章先介绍格本章先介绍格,在此基础上引入分配格和有补格在此基础上引入分配格和有补格,而把而把布尔代数作为一种特殊的格加以讨论布尔代数作为一种特殊的格加以讨论.本讲稿第二页，共六十五页6.1 用偏序集定义的格用偏序集定义的格n n1.格的第一种定义n n偏序集(L

2、,)?n nRemark 偏序集(L,)中不是任意两个元素均存在上确界及下确界的.n nc,b,a,d?本讲稿第三页，共六十五页n nDef 设(L,)是偏序集,若L中任意两个元素都存在上确界以及下确界,则称(L,)是格格(lattice).为了方便,这样的格可称为偏序偏序格格.n n(Figure 6-3)钻石格钻石格与五角格五角格?n n课堂练习 习题6.1 1.本讲稿第四页，共六十五页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

3、B.本讲稿第五页，共六十五页n n例6-2(P170)证明:(Dn,|)是格,其中Dn是自然数n的正因数组成的集合,|是其上的整除关系.n nProof(cf.Chapter 2)本讲稿第六页，共六十五页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.本讲稿第七页，共六十五页n n2.格的性质n nDef 设(L,)是格,x+y=supx,y,x y=infx,y.n n格中的“+”是求上确界运算,可以看作是格的加

4、法运算,读作“加”；同样,格中的“”是求下确界运算,可以看作是格的乘法运算,读作“乘”.(与环中的与环中的“加加”和和“乘乘”,”,以及数的以及数的“加加”和和“乘乘”不同不同)(与布尔代数的运算一致与布尔代数的运算一致)本讲稿第八页，共六十五页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.本讲稿第九页，共六十五页n n(L,)与(L,)?n nDef 对于任意关于格(L,)的命题,将命题前提和结论中的(1)改为;(2)+改为;(3)改为+；(

5、4)0改为1；(5)1改为0所得到的命题称为原命题的对偶命题对偶命题.n nTheorem 6-2 对于任意关于格(L,)的真命题,其对偶命题亦为真.n n如(1)x x+y,y x+y;(2)x y x,x y y.n n在格的性质中,有很多都是成对(dual)出现的.本讲稿第十页，共六十五页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.本讲稿第十

6、一页，共六十五页n n格的特征性质特征性质.n nTheorem 6-5 格(L,)满足:n n(1)交换性.n n(2)结合性.n n(3)吸收性.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?(仿上;对偶)本讲稿第十二页，共六十五页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

7、)=x y x y=x.n n(3)(1):x=x y y.本讲稿第十三页，共六十五页n n3.格的保序映射n nDef 设(L1,1)和(L2,2)是格偏序集即可,若存在:L1 L2,n n则称为(L1,1)到(L2,2)的保序映射.n n例6-4(P173)?n n作业 习题6.1 3,6,7.本讲稿第十四页，共六十五页6.2 用代数结构定义的格用代数结构定义的格n n1.1.格的第二种定义格的第二种定义n nDef Def 设设(L L,+,+,)是代数结构是代数结构,+,+和和 是是L L上的两个上的两个2 2元运算元运算,同同时满足时满足:n n(1)(1)交换性交换性.n n(2)

8、(2)结合性结合性.n n(3)(3)吸收性吸收性.n n则称则称(L L,+,+,)为为格格格格,称这样定义的格为称这样定义的格为代数格代数格代数格代数格.n n由定义知由定义知,格是具有两个格是具有两个2 2元运算的代数结构元运算的代数结构.本讲稿第十五页，共六十五页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.本讲稿第十六页，共六十五页n n2.格的

9、两种定义的等价性n n格的这两种定义是否是一回事?n nTheorem 6-7 偏序格(L,)与代数格(L,+,)是等价的.n nProof()n n()n n(1)是偏序.自反自反(命题命题1).1).反反对称对称.传递传递.本讲稿第十七页，共六十五页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).本讲稿第十八页，共六十五页n n3.子格n n设(L,)是格,M L,在M上的限制仍记为.有例子表明,(M,)不一定是格.n n例6-5 X=a,b,M=,a,b P(X).

10、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,)是格.本讲稿第十九页，共六十五页n n借助于子代数给子格下的定义:n nDef 设(L,+,)是格,M L,若(M,+,)是格,则称(M,+,)为(L,+,)的子格(sublattice).n n显然,(M,+,)为(L,+,)的子格 M关于+和封闭.n nRemark 设(L,+,)是格,M L,(M,)是格与(M,)是子格存在差异.正因为这样,才借助于子代数对子格定义.本讲稿第二十页，共六十五页n n4.格的同态与同构n n可以类似地定义格的同态与同构.n nDe

11、f 设(L1,+,)和(L2,)是格,若存在:L1 L2,分别保持格的求上确界运算和求下确界运算,则称为(L1,+,)到(L2,)的格同态映射.n n格同构的直观意义?n nTheorem 6-8 格同态映射是保序映射.本讲稿第二十一页，共六十五页n nRemark 格的保序映射不一定是格同态映射(习题).n n可以考虑格同构映射与格保序映射之间的关系.n n作业 习题6.2 1,4,6,8.本讲稿第二十二页，共六十五页6.3 分配格分配格n n1.分配格分配格(distributive lattice)的定义的定义n n有例子表明,格不满足分配性.n n例 6-9 举例说明在格(L,)中,格

12、的乘法运算“”和格加法运算“+”相互不一定可分配.n nSolution本讲稿第二十三页，共六十五页n n钻石格?n n五角格?n nTheorem 6-9(分配不等式分配不等式)设(L,)是格,对于任意x,y,z L,有n 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.本讲稿第二十四页，共六十五页n nTheorem 6-10 设(L,+,)是格,则格的乘法运算“”对格的加法运算“+”可分配 格的加法运算“+”对格的乘法运算“”可分配.n nProof()x,y,z L:n n()本讲稿第二十五页，共六

13、十五页n nDef 设(L,+,)是格,若格的乘法运算“”对格的加法运算“+”可分配(或格的加法运算“+”对格的乘法运算“”可分配),则称(L,+,)是分配格.n n例6-10 证明:(P(X),)是分配格.n n其他例子?本讲稿第二十六页，共六十五页n n钻石格和五角格是两个非常重要的非分配格的例子.我们只给出n nTheorem 6-11设(L,+,)是格,则L是分配格的充要条件是L中不含有同构于钻石格和五角格的子格.n n根据上述定理有以下两个推论.n nCorollary 1 小于5个元素的格为分配格.n nCorollary 2 任意链是分配格.n n(可直接证.)本讲稿第二十七页，

14、共六十五页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?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.本讲稿第二十八页，共六十五页6.4 有补格有补格n n1.有界格n n一般来说,格L不一定存在最大元与最小元.例如,实数集R关于数的小于等于关系 所作成

15、的格(R,).n nDef 设(L,)是格,若L存在最大元素1以及最小元素0,则称(L,)为有界格有界格(bounded lattice).本讲稿第二十九页，共六十五页n n例6-12 证明:对任意集合X,(P(X),)是有界格.n nHint 最大元素最大元素:X X;最小元素最小元素:.n n显然,任意有限格是有界格(?).本讲稿第三十页，共六十五页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互为补元.但对于有界格,

16、不是每个元素均有补元,同时一个元素的补元未必唯一.n n因此,不能定义1元运算 .本讲稿第三十一页，共六十五页本讲稿第三十二页，共六十五页n nDef 设(L,+,)是有界格,若L中每个元素都有补元,则称(L,+,)为有补格有补格(lattice 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右图是有补格,不是分配格.本讲稿第三十三页，共六十五页n n几个重要结论.n nTheorem 6-13 在分配格中,若一个元素存在补元,则补元是唯一的.n

17、nClearly.n n根据定理6-13知,在有补分配格中,每个元素都有唯一的补元.正因为如此,在有补分配格中可以定义一个元素的补运算“”，它是其上的1元代数运算.本讲稿第三十四页，共六十五页n n下述定理是有补分配格的重要性质.n nTheorem 6-14 设(L,+,)是有补分配格,则De Morgan律成立,即对于任意x,y L,有n n(1)n n(2)n nProof(1)n n(2)?本讲稿第三十五页，共六十五页n nTheorem 6-15 设(L,+,)是有补分配格,则对于任意x,y L,有n nProof 显然,n n(1)x y:n n(2)n n作业 习题6.4,4,5

18、,6,7.本讲稿第三十六页，共六十五页6.5 布尔代数布尔代数n n1.1.布尔代数的格定义布尔代数的格定义n nDef Def 元素个数元素个数 2 2 的有补分配格的有补分配格(B B,)称为称为布尔代数布尔代数布尔代数布尔代数(Boolean algebra)(Boolean algebra)或布尔格或布尔格.n n偏序集与各种格之间的相互关系偏序集与各种格之间的相互关系?n n仅仅1 1个元素的有补分配格是布尔代数的退化情形，一个元素的有补分配格是布尔代数的退化情形，一般不作为布尔代数考虑，可参见布尔代数的公理化定般不作为布尔代数考虑，可参见布尔代数的公理化定义义.n n显然，在任何布

19、尔代数或布尔格中有两个特殊元素，一个显然，在任何布尔代数或布尔格中有两个特殊元素，一个是其最小元是其最小元0 0，一个是其最大元，一个是其最大元1.1.当然当然0 0 1 1.本讲稿第三十七页，共六十五页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-16 设|X|1,证明:(P(X),)是布尔代数,称为集合代数集合代数:n n ,X).本讲稿第三十八页，共六十五页n n例6-17 证明:(F,)是布尔代数,其中F是所有合式公式组成

20、的集合,是公式间的逻辑蕴涵关系,称为逻辑代数逻辑代数,F中的元素是逻辑表达式:n n特别地,令G是所有命题公式组成的集合,则称(G,)为命题代数.令H是仅含命题变元p1,p2,pn的所有命题公式组成的集合,则(H,)是布尔代数,这时n n由于集合代数和逻辑代数都是布尔代数,因此它们有完全相似的性质.本讲稿第三十九页，共六十五页n n2.布尔代数的性质n nTheorem 6-16 设(B,)是布尔代数,n nI.(B,)是格;n nII.(B,)是分配格;n nIII.(B,)是有补格;n nIV.(B,)是有补分配格.本讲稿第四十页，共六十五页n n以下是布尔代数的特征性质,参见下面的布尔代

21、数的公理化定义.n n交换律.n n分配律.n n幺元律：n n有补律：本讲稿第四十一页，共六十五页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元运算.本讲稿第四十二页，共六十五页n nTheorem 6-17 布尔代数的两种定义是等价的.n nProof 只需证明:满足定义6-13条件的代数结构是格且0和1分别是其最小

22、元素和最大元素即可,因为根据(2)分配律和(4)有补律知是B有补分配格.n n首先注意,由于定义中的条件是对偶出现的,所以在该代数结构中,对偶原理成立.n n其次,x B,x+1=1.本讲稿第四十三页，共六十五页n n再其次,n n(B,+,)是格:n n(1)交换性.n n(2)吸收性.n n(3)结合性.n nB上定义:本讲稿第四十四页，共六十五页n n4.子布尔代数n n由于布尔代数中有两个0元运算:0和1,有必要对子布尔代数给出定义.n nDef 设 是布尔代数,C B,若n n 是布尔代数,则称 是n n 的子布尔代数子布尔代数.n n显然,对于布尔代数 ,C B,则C是B的子布尔代

23、数 0,1 C且C关于运算+,封闭.本讲稿第四十五页，共六十五页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)本讲稿第四十六页，共六十五页n n布尔代数之间的同态(构)又称为布尔同态(构),它要求(1)(5)都要成立,但实际上,其中的一些条件可以从别的条件推导出来,见本节习题8,9,10.n n由布尔代数的同构定义容易知道,2个元素的布尔代数是最简单的布尔代数,任意布尔代数都有同构于2个元

24、素的布尔代数的子布尔代数.n n作业 习题6.5 16,8,9,10.本讲稿第四十七页，共六十五页6.6 有限布尔代数的结构有限布尔代数的结构n n有限布尔代数与无限布尔代数?n n对于集合代数(P(X),),当|X|=n1有限时P(X)有限,(P(X),)是有限布尔代数.n nTheorem(M.H.Stone)设 是有限布尔代数,则存在有限集合X使得 与集合代数 ,X)同构.本讲稿第四十八页，共六十五页n n实际上,集合X是由有限布尔代数的所有原子组成的集合,先定义一般格上的原子的概念.n nDef 设(L,)是格,其最小元素为0,对于a L,若a盖住0,则a称为格的原子原子(atom).

25、n n例子(图6-16)?本讲稿第四十九页，共六十五页n nProperty 1(P187)n nProperty 2(P188)n nProperty 3(P188)本讲稿第五十页，共六十五页n nProperty 4(P188)n nProperty 5(P188)n nProperty 6(P188)本讲稿第五十一页，共六十五页n nProof of the Stone theorem:令集合X是由有限布尔代数 的所有原子组成的集合.n n(0)=,n n单射?n n满射?n n保持运算?本讲稿第五十二页，共六十五页n n由Stone定理有n nCorollary 1 任意有限布尔代数的

26、元素个数为2n,其中n为正整数.n nCorollary 2 在同构意义下,2n个元素的有限布尔代数是唯一的,其中n为正整数.n n作业 习题6.6 14.本讲稿第五十三页，共六十五页6.7 布尔表达式布尔表达式n n布尔表达式的化简及其主范式表示在理论研究和实际应布尔表达式的化简及其主范式表示在理论研究和实际应用中都有十分重要的意义用中都有十分重要的意义.n n1 1 布尔表达式的定义布尔表达式的定义布尔表达式的定义布尔表达式的定义n nDefDef 设设 是布尔代数，则是布尔代数，则B B上的上的布尔表达式布尔表达式布尔表达式布尔表达式(Boolean expression)(Boolea

27、n expression)递归定义如下递归定义如下:n n(1)(1)B B中的元素中的元素a a,b b,c c等是布尔表达式等是布尔表达式.n n(2)(2)取值于取值于B B的变元的变元x x1 1,x x2 2,等是布尔表达式等是布尔表达式.n n(3)(3)若若e e1 1和和e e2 2是布尔表达式，则是布尔表达式，则 ,e e1 1+e e2 2,e e1 1 e e2 2布尔表达布尔表达式式.n n(4)(4)有限次使用有限次使用(1)(2)(3)(1)(2)(3)得到的字符串是仅有的布尔表达得到的字符串是仅有的布尔表达式式.本讲稿第五十四页，共六十五页n n例 设B=0,a,

28、b,1,是布尔代数,则 等是B上的布尔表达式.n n含n个变元x1,x2,xn的布尔表达式记为E(x1,x2,xn).因此,上例中的两个布尔表达式分别记为 n n逻辑代数上的布尔表达式常称为逻辑表达式.本讲稿第五十五页，共六十五页n n设B=0,1,是布尔代数,它是最简单的逻辑代数.在计算机逻辑电路设计中,B中元素的0和1称为逻辑常量逻辑常量,B上的变元称为逻辑变量逻辑变量,B上的布尔表达式称为逻辑表达逻辑表达式式,它就是命题公式.例如 等是B上的布尔表达式.本讲稿第五十六页，共六十五页n n2.布尔表达式的化简n n大家知道,在逻辑电路设计时,会用一个最简单的逻辑表达式去设计组合逻辑电路,因

29、此布尔表达式的化简有着实际应用背景.n n很显然,对于例中的布尔表达式 若取x1=a,x1=a,则可求出该布尔表达式的值为本讲稿第五十七页，共六十五页n nDef 6-18n n将x1,x2,当作已经在B中取值,可以利用布尔代数的性质进行有关讨论.例如,本讲稿第五十八页，共六十五页n n对于布尔代数上的布尔表达式,与其相等的含最少运算符号“+”、“”及“”的布尔表达式是其最简形式.n n有限布尔代数上的布尔表达式的最简形式在理论上是存在的.在例中,的最简形式为本讲稿第五十九页，共六十五页n n下面仅举一个例子介绍布尔表达式的代数化简方法,至于其他方法,如Quine方法和Karnaugh方法可参

30、考其他文献.n n例6-21 设 是布尔代数,化简布尔表达式n nSolution本讲稿第六十页，共六十五页n n3.布尔表达式的主范式n nDef 设 是布尔代数,由B上的n个变元x1,x2,xn产生的最小项最小项为1 2 n,最大项最大项为1+2+n,其中i为xi或n nDef 本讲稿第六十一页，共六十五页n n求取布尔表达式E(x1,x2,xn)的主析取范式与主合取范式与求取命题公式的主范式是类似的,其主要步骤如下:n n(1)将B上的变元看作常量使用布尔代数的性质；n n(2)利用De Morgan律将“”深入到变元或常量的前面；n n(3)利用分配律展开；n n(4)补充所缺少的变元；n n(5)(随时)计算并合并常元.本讲稿第六十二页，共六十五页n n例6-22 设B=0,a,b,1,是布尔代数,求布尔表达式 的主析取范式与主合取范式.n nSolution 主析取范式:本讲稿第六十三页，共六十五页n n主合取范式:本讲稿第六十四页，共六十五页n n4.布尔函数n nDef 设 是布尔代数,称:Bn B为B上的n元布尔函数布尔函数(Boolean function).n n显然,布尔表达式(逻辑函数)是布尔函数.n n一般来说布尔函数不是布尔表达式.n n作业 习题6.7 1,2,3,4.本讲稿第六十五页，共六十五页