第6章 格与布尔代数.ppt

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

1、Chapter 6 格与布尔代数格与布尔代数n n格论格论(1935)(1935)是一种重要的代数结构是一种重要的代数结构,它是计算机它是计算机语言的指称语义的理论基础，在计算机语言的指称语义的理论基础，在计算机应用逻辑应用逻辑研究中有着重要作用研究中有着重要作用.n n布尔代数是英国数学家布尔代数是英国数学家George BooleGeorge Boole在在18471847年左右年左右在对逻辑思维法则进行研究时提出的，后来很多在对逻辑思维法则进行研究时提出的，后来很多数学家特别是数学家特别是E.V.E.V.HungtingtonHungtington和和E.H.StoneE.H.Stone

2、对布对布尔代数的进行了一般化研究，在尔代数的进行了一般化研究，在19381938年年C.E.C.E.ShannonShannon发表的发表的A Symbolic Analysis of Relay and A Symbolic Analysis of Relay and Switching Circuits Switching Circuits 论文，为布尔代数在工艺技术论文，为布尔代数在工艺技术n n中的应用开创了先河中的应用开创了先河,自此以后布尔代数在自动自此以后布尔代数在自动推理和逻辑电路设计的分析和优化等问题的讨论推理和逻辑电路设计的分析和优化等问题的讨论中都有着最直接的应用中都有着

3、最直接的应用,作为计算机设计基础的作为计算机设计基础的数字逻辑数字逻辑就是布尔代数就是布尔代数.n n本章先介绍格本章先介绍格,在此基础上引入分配格和有补格在此基础上引入分配格和有补格,而把布尔代数作为一种特殊的格加以讨论而把布尔代数作为一种特殊的格加以讨论.6.1 用偏序集定义的格用偏序集定义的格n n1.格的第一种定义n n偏序集(L,)?n nRemark 偏序集(L,)中不是任意两个元素均存在上确界及下确界的.n nc,b,a,d?n nDef 设(L,)是偏序集,若L中任意两个元素都存在上确界以及下确界,则称(L,)是格格(lattice).为了方便,这样的格可称为偏偏序格序格.n

4、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 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

5、,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格中的“+”是求上确界运算,可以看作是格的加法运算,读作“加”；同样,格中的“”是求下确界运算,可以看作是格的乘法运算,读作“乘”.(与环中的与环中的“加加”和和“乘乘”,以及数的以及数的“加加”和和“乘乘”不同不同)(与布尔代数的运算一致与布尔代数的运算一致)n n由于“上确界上界”以及“下界下确界”,根据定义易知n nTheorem 6-1 设(L,)是格,则对于任意x,y L,有n n(1)x x+y,y x+y.

6、n n(2)x y x,x y y.n n(L,)与(L,)?n nDef 对于任意关于格(L,)的命题,将命题前提和结论中的(1)改为;(2)+改为;(3)改为+；(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

7、 n(2)y1+y2 是x1,x2的上界:n nTheorem 6-4(幂等性幂等性)设(L,)是格,x L,x+x=x,x x=x.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)

8、: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.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

9、n(1)(1)交换性交换性.n n(2)(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.格的两种定义的等

10、价性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).n n(P(X),).n n(M,)不是格.n n例6-6 X=

11、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 nDef 设(L1,+,)和(L2,)是格,若存在:L1 L2,分别保持格的求上确界运算和求下确界运算,则称为(L1,+,

12、)到(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,)中,格的乘法运算“”和格加法运算“+”相互不一定可分配.n nSolutionn n钻石格?n n五角格?n nTheorem 6-9(分配不等式分配不等式)设(L,)是格,对于

13、任意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()n nDef 设(L,+,)是格,若格的乘法运算“”对格的加法运算“+”可分配(或格的加法运算“+”对格的乘法运算“”可分配),则称(L,+,)是分配格.n n例6-10 证明:(P(X),)是分配格.n n其他例子?n n钻石格和五角格是两个非常重

14、要的非分配格的例子.我们只给出n nTheorem 6-11设(L,+,)是格,则L是分配格的充要条件是L中不含有同构于钻石格和五角格的子格.n n根据上述定理有以下两个推论.n nCorollary 1 小于5个元素的格为分配格.n nCorollary 2 任意链是分配格.n n(可直接证.)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)=(

15、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关于数的小于等于关系 所作成的格(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 设(

16、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元运算 .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右图是有

17、补格,不是分配格.n n几个重要结论.n nTheorem 6-13 在分配格中,若一个元素存在补元,则补元是唯一的.n 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 显

18、然,n n(1)x y:n n(2)n n作业 习题6.4,4,5,6,7.6.5 布尔代数布尔代数n n1.1.布尔代数的格定义布尔代数的格定义n nDef Def 元素个数元素个数 2 2 的有补分配格的有补分配格(B B,)称为称为布尔代布尔代布尔代布尔代数数数数(Boolean algebra)(Boolean algebra)或布尔格或布尔格.n n偏序集与各种格之间的相互关系偏序集与各种格之间的相互关系?n n仅仅1 1个元素的有补分配格是布尔代数的退化情形，个元素的有补分配格是布尔代数的退化情形，一般不作为布尔代数考虑，可参见布尔代数的公一般不作为布尔代数考虑，可参见布尔代数的公

19、理化定义理化定义.n n显然，在任何布尔代数或布尔格中有两个特殊元显然，在任何布尔代数或布尔格中有两个特殊元素，一个是其最小元素，一个是其最小元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以下是布尔代数的特征性质,参见下面的布尔代数的公理化定义.n n交换律.n n分配律.n n幺元律：n n有补律：

21、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分别是其最小元素和最大元素即可,因为根据(2)分配律和(4)有补律知是B有补分配格.n n首先注意,由于定义中的条件是对偶出现的,所以在该代

22、数结构中,对偶原理成立.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的子布尔代数 0,1 C且C关于运算+,封闭.n n5.布尔代数的同态与同构n n定义两个布尔代数的同态与同构时,同样要注意布尔代数中的两个0元运算:0和1.n nDef 设 和 是布尔代数,若

23、存在映射: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个元素的布尔代数的子布尔代数.n n作业 习题6.5 16,8,9,10.6.6 有限布尔代数的结构有限布尔代数的结构n n有限布尔代数与无限布尔代数?n n对于集合代数(P(X),),当|X|=n1有限时P(X)有限,(P(X),)是有限布尔

24、代数.n nTheorem(M.H.Stone)设 是有限布尔代数,则存在有限集合X使得 与集合代数 ,X)同构.n n实际上,集合X是由有限布尔代数的所有原子组成的集合,先定义一般格上的原子的概念.n nDef 设(L,)是格,其最小元素为0,对于a L,若a盖住0,则a称为格的原子原子(atom).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

25、 theorem:令集合X是由有限布尔代数 的所有原子组成的集合.n n(0)=,n n单射?n n满射?n n保持运算?n n由Stone定理有n nCorollary 1 任意有限布尔代数的元素个数为2n,其中n为正整数.n nCorollary 2 在同构意义下,2n个元素的有限布尔代数是唯一的,其中n为正整数.n n作业 习题6.6 14.6.7 布尔表达式布尔表达式n n布尔表达式的化简及其主范式表示在理论研究和布尔表达式的化简及其主范式表示在理论研究和实际应用中都有十分重要的意义实际应用中都有十分重要的意义.n n1 1 布尔表达式的定义布尔表达式的定义布尔表达式的定义布尔表达式的

26、定义n nDefDef 设设 是布尔代数，则是布尔代数，则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,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)有限

27、次使用有限次使用(1)(2)(3)(1)(2)(3)得到的字符串是仅有的得到的字符串是仅有的布尔表达式布尔表达式.n n例 设B=0,a,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.布尔表达式的化简

28、n n大家知道,在逻辑电路设计时,会用一个最简单的逻辑表达式去设计组合逻辑电路,因此布尔表达式的化简有着实际应用背景.n n很显然,对于例中的布尔表达式 若取x1=a,x1=a,则可求出该布尔表达式的值为n nDef 6-18n n将x1,x2,当作已经在B中取值,可以利用布尔代数的性质进行有关讨论.例如,n n对于布尔代数上的布尔表达式,与其相等的含最少运算符号“+”、“”及“”的布尔表达式是其最简形式.n n有限布尔代数上的布尔表达式的最简形式在理论上是存在的.在例中,的最简形式为n n下面仅举一个例子介绍布尔表达式的代数化简方法,至于其他方法,如Quine方法和Karnaugh方法可参考

29、其他文献.n n例6-21 设 是布尔代数,化简布尔表达式n nSolutionn 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.