格与布尔代数

格与布尔代数第1页，共65页，2023年，2月20日，星期一中的应用开创了先河,自此以后布尔代数在自动推理和逻辑电路设计的分析和优化等问题的讨论中都有着最直接的应用,作为计算机设计基础的《数字逻辑》就是布尔代数.本章先介绍格,在此基础上引入分配格和有补格,而把布尔代数作为一种特殊的格加以讨论.第2页，共65页，2023年，2月20日，星期一6.1用偏序集定义的格1.格的第一种定义偏序集(L,)?Remark偏序集(L,)中不是任意两个元素均存在上确界及下确界的.{c,b},{a,d}?第3页，共65页，2023年，2月20日，星期一Def设(L,)是偏序集,若L中任意两个元素都存在上确界以及下确界,则称(L,)是格(lattice).为了方便,这样的格可称为偏序格.(Figure6-3)钻石格与五角格?课堂练习习题6.11.第4页，共65页，2023年，2月20日，星期一例6-1(P170)

证明:(P(X),)是格,其中P(X)是集合X的幂集.Proof(cf.Chapter1)A,BP(X),(1)sup{A,B}=AB,(2)inf{A,B}=AB.第5页，共65页，2023年，2月20日，星期一例6-2(P170)

证明:(Dn,|)是格,其中Dn是自然数n的正因数组成的集合,|是其上的整除关系.Proof(cf.Chapter2)第6页，共65页，2023年，2月20日，星期一例6-3(P170)

令F是所有合式公式(WFF)组成的集合,是公式间的逻辑蕴涵关系,则(F,)是格.Proof(cf.Chapter3)A,BF,(1)sup{A,B}=AB,(2)inf{A,B}=AB.第7页，共65页，2023年，2月20日，星期一2.格的性质Def设(L,)是格,x+y=sup{x,y},x

∙

y=inf{x,y}.格中的“+”是求上确界运算,可以看作是格的加法运算,读作“加”；同样,格中的“”是求下确界运算,可以看作是格的乘法运算,读作“乘”.(与环中的“加”和“乘”,以及数的“加”和“乘”不同)(与布尔代数的运算一致)第8页，共65页，2023年，2月20日，星期一由于“上确界上界”以及“下界下确界”,根据定义易知Theorem6-1设(L,)是格,则对于任意x,y

L,有(1)x

x+y,y

x+y.(2)x

∙y

x,x

∙y

y.第9页，共65页，2023年，2月20日，星期一(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)出现的.第10页，共65页，2023年，2月20日，星期一Theorem6-3(保序性)设(L,)是格,对于任意xi,yi

L,i=1,2:Proof(1)x1+x2是{x1,x2}的上确界;(2)y1+y2是{x1,x2}的上界:Theorem6-4(幂等性)设(L,)是格,xL,x+x=x,x

∙x=x.

第11页，共65页，2023年，2月20日，星期一格的特征性质.Theorem6-5格(L,)满足:(1)交换性.(2)结合性.(3)吸收性.Proof(3)x

x,x

∙y

xx+(x

∙y)x;显然,x

x+(x

∙y),所以x+(x

∙y)=x.x∙(x

+y)=x?(仿上;对偶)第12页，共65页，2023年，2月20日，星期一Theorem6-6设(L,)是格,则对于任意x,y

L,下列三个命题等价:(1)x

y.(2)x+y=y.(2)x

∙y

=x.Proof(1)(2):x

y,y

yx+y

y.显然,y

x+yx+y=y.(2)(3):x

∙(x+y)=x

∙y

x

∙y

=x.(3)(1):x=x

∙y

y.第13页，共65页，2023年，2月20日，星期一3.格的保序映射Def设(L1,1)和(L2,2)是格{偏序集即可},若存在:L1

L2,则称为(L1,1)到(L2,2)的保序映射.例6-4(P173)?作业习题6.13,6,7.第14页，共65页，2023年，2月20日，星期一6.2用代数结构定义的格1.格的第二种定义Def设(L,+,∙)是代数结构,+和是L上的两个2元运算,同时满足:(1)交换性.(2)结合性.(3)吸收性.则称(L,+,∙)为格,称这样定义的格为代数格.由定义知,格是具有两个2元运算的代数结构.第15页，共65页，2023年，2月20日，星期一为了下面的应用,首先证明两个命题.命题1设(L,+,∙)是代数结构,+和是L上的两个2元运算,若+和相互可吸收,则+和具有幂等性.Hint命题2设(L,+,∙)是代数结构,+和是L上的两个2元运算,若+和相互可吸收,则x,yL,x

∙y=xx+y=y.第16页，共65页，2023年，2月20日，星期一2.格的两种定义的等价性格的这两种定义是否是一回事?Theorem6-7偏序格(L,)与代数格(L,+,∙)是等价的.Proof()()(1)是偏序.自反(命题1).反对称.传递.第17页，共65页，2023年，2月20日，星期一(2)对于任意x,y

L,x

∙y是{x,y}的下确界.(3)对于任意x,y

L,x

+y是{x,y}的上确界.x,yL,xyx

∙y=xx+y=y(命题2).第18页，共65页，2023年，2月20日，星期一3.子格设(L,)是格,ML,在M上的限制仍记为.有例子表明,(M,)不一定是格.例6-5X={a,b},M={,{a},{b}}P(X).(P(X),).(M,)不是格.例6-6X={a,b,c},M=P(X)–{c}.(P(X),).(M,)是格.第19页，共65页，2023年，2月20日，星期一借助于子代数给子格下的定义:Def设(L,+,∙)是格,ML,若(M,+,∙)是格,则称(M,+,∙)为(L,+,∙)的子格(sublattice).显然,(M,+,∙)为(L,+,∙)的子格M关于+和∙封闭.Remark设(L,+,∙)是格,ML,(M,)是格与(M,)是子格存在差异.正因为这样,才借助于子代数对子格定义.第20页，共65页，2023年，2月20日，星期一4.格的同态与同构可以类似地定义格的同态与同构.Def设(L1,+,∙)和(L2,,⊙)是格,若存在:L1

L2,分别保持格的求上确界运算和求下确界运算,则称为(L1,+,∙)到(L2,,⊙)的格同态映射.格同构的直观意义?Theorem6-8格同态映射是保序映射.第21页，共65页，2023年，2月20日，星期一Remark格的保序映射不一定是格同态映射(习题).可以考虑格同构映射与格保序映射之间的关系.作业习题6.21,4,6,8.第22页，共65页，2023年，2月20日，星期一6.3分配格1.分配格(distributivelattice)的定义有例子表明,格不满足分配性.例

6-9

举例说明在格(L,)中,格的乘法运算“”和格加法运算“+”相互不一定可分配.Solution第23页，共65页，2023年，2月20日，星期一钻石格?五角格?Theorem6-9(分配不等式)设(L,)是格,对于任意x,y,zL,有(1)x+(y

∙z)(x+y)∙(x+z).(2)(dual?)

Proof(1)

x+(y

∙z)x+y;x+(y

∙z)x+z.第24页，共65页，2023年，2月20日，星期一Theorem6-10设(L,+,∙)是格,则格的乘法运算“”对格的加法运算“+”可分配格的加法运算“+”对格的乘法运算“”可分配.Proof()x,y,zL:()第25页，共65页，2023年，2月20日，星期一Def设(L,+,∙)是格,若格的乘法运算“”对格的加法运算“+”可分配(或格的加法运算“+”对格的乘法运算“”可分配),则称(L,+,∙)是分配格.例6-10证明:(P(X),)是分配格.其他例子?第26页，共65页，2023年，2月20日，星期一钻石格和五角格是两个非常重要的非分配格的例子.我们只给出Theorem6-11设(L,+,∙)是格,则L是分配格的充要条件是L中不含有同构于钻石格和五角格的子格.根据上述定理有以下两个推论.Corollary1小于5个元素的格为分配格.Corollary2任意链是分配格.(可直接证.)第27页，共65页，2023年，2月20日，星期一2.分配格的性质Theorem6-12设(L,+,∙)是格,则L是分配格的充要条件是对于任意x,y,z

L,由x+y=x+z和x

∙

y=x

∙

z可以推出y=z.Remark由x+y=x+z可以推出y=z?x

∙

y=x

∙

z?Proof()y=y+(x

∙z)=(y+x)∙(y+z)=(z+x)∙(y+z)=(x

∙y)+z=(x

∙z)+z=z.()?判断一个格是否分配格?作业

习题6.32,5,7,9.第28页，共65页，2023年，2月20日，星期一6.4有补格1.有界格一般来说,格L不一定存在最大元与最小元.例如,实数集R关于数的小于等于关系所作成的格(R,).Def设(L,)是格,若L存在最大元素1以及最小元素0,则称(L,)为有界格(boundedlattice).第29页，共65页，2023年，2月20日，星期一例6-12

证明:对任意集合X,(P(X),)是有界格.Hint最大元素:X;最小元素:.显然,任意有限格是有界格(?).第30页，共65页，2023年，2月20日，星期一2.补元有补格Def设(L,+,∙)是有界格,a

L,若存在b

L,使得a+b=1且a

∙b=0,则称b为a的补元(complement).显然,在任意有界格中,若b为a的补元,则a为b的补元；0与1互为补元.但对于有界格,不是每个元素均有补元,同时一个元素的补元未必唯一.因此,不能定义1元运算.第31页，共65页，2023年，2月20日，星期一第32页，共65页，2023年，2月20日，星期一Def

设(L,+,∙)是有界格,若L中每个元素都有补元,则称(L,+,∙)为有补格(latticecomplemented).例6-14

证明:对任意集合X,(P(X),)是有补格.HintAP(X),X-AP(X):A(X-A)=X,A(X-A)=.右图是有补格,不是分配格.第33页，共65页，2023年，2月20日，星期一几个重要结论.Theorem6-13在分配格中,若一个元素存在补元,则补元是唯一的.Clearly.根据定理6-13知,在有补分配格中,每个元素都有唯一的补元.正因为如此,在有补分配格中可以定义一个元素的补运算“”，它是其上的1元代数运算.

第34页，共65页，2023年，2月20日，星期一下述定理是有补分配格的重要性质.Theorem6-14设(L,+,∙)是有补分配格,则DeMorgan律成立,即对于任意x,y

L,有(1)(2)Proof(1)(2)?第35页，共65页，2023年，2月20日，星期一Theorem6-15设(L,+,∙)是有补分配格,则对于任意x,y

L,有Proof显然,(1)x

y:(2)作业习题6.4,4,5,6,7.第36页，共65页，2023年，2月20日，星期一6.5布尔代数1.布尔代数的格定义Def元素个数2

的有补分配格(B,)称为布尔代数(Booleanalgebra)或布尔格.偏序集与各种格之间的相互关系?仅1个元素的有补分配格是布尔代数的退化情形，一般不作为布尔代数考虑，可参见布尔代数的公理化定义.显然，在任何布尔代数或布尔格中有两个特殊元素，一个是其最小元0，一个是其最大元1.当然01.第37页，共65页，2023年，2月20日，星期一在任意布尔代数(B,)中可以定义3种代数运算:对于任意x,y

B,(a)布尔加“+”:x+y=sup{x,y}.(b)布尔乘“”:x∙

y=inf{x,y}.(c)布尔补“”:x的补元.例6-16

设|X|1,证明:(P(X),)是布尔代数,称为集合代数:

,X).第38页，共65页，2023年，2月20日，星期一例6-17证明:(F,)是布尔代数,其中F是所有合式公式组成的集合,是公式间的逻辑蕴涵关系,称为逻辑代数,F中的元素是逻辑表达式:特别地,令G是所有命题公式组成的集合,则称(G,)为命题代数.令H是仅含命题变元p1,p2,…,pn的所有命题公式组成的集合,则(H,)是布尔代数,这时由于集合代数和逻辑代数都是布尔代数,因此它们有完全相似的性质.第39页，共65页，2023年，2月20日，星期一2.布尔代数的性质Theorem6-16设(B,)是布尔代数,I.(B,)是格;II.(B,)是分配格;III.(B,)是有补格;IV.(B,)是有补分配格.第40页，共65页，2023年，2月20日，星期一以下是布尔代数的特征性质,参见下面的布尔代数的公理化定义.交换律.分配律.幺元律：有补律：第41页，共65页，2023年，2月20日，星期一3.布尔代数的公理化定义Def(E.V.Hungtington)设B是集合,|B|2,“+”和“”是B上的两个2元代数运算,“”是B上的1元代数运算,且满足(1)交换律.(2)分配律.(3)幺元律:(4)有补律:则称是布尔代数.Remark按这种定义需强调两个0元运算.第42页，共65页，2023年，2月20日，星期一Theorem6-17布尔代数的两种定义是等价的.

Proof只需证明:满足定义6-13条件的代数结构是格且0和1分别是其最小元素和最大元素即可,因为根据(2)分配律和(4)有补律知是B有补分配格.首先注意,由于定义中的条件是对偶出现的,所以在该代数结构中,对偶原理成立.其次,xB,x+1=1.第43页，共65页，2023年，2月20日，星期一再其次,(B,+,∙)是格:(1)交换性.(2)吸收性.(3)结合性.B上定义:第44页，共65页，2023年，2月20日，星期一4.子布尔代数由于布尔代数中有两个0元运算:0和1,有必要对子布尔代数给出定义.Def设是布尔代数,CB,若是布尔代数,则称是的子布尔代数.显然,对于布尔代数,CB,则C是B的子布尔代数0,1C且C关于运算+,,封闭.第45页，共65页，2023年，2月20日，星期一5.布尔代数的同态与同构定义两个布尔代数的同态与同构时,同样要注意布尔代数中的两个0元运算:0和1.Def设和是布尔代数,若存在映射:B1B2且保持所有布尔代数中的运算(1)(2)(3)(4)(5)第46页，共65页，2023年，2月20日，星期一布尔代数之间的同态(构)又称为布尔同态(构),它要求(1)—(5)都要成立,但实际上,其中的一些条件可以从别的条件推导出来,见本节习题8,9,10.由布尔代数的同构定义容易知道,2个元素的布尔代数是最简单的布尔代数,任意布尔代数都有同构于2个元素的布尔代数的子布尔代数.作业习题6.51—6,8,9,10.第47页，共65页，2023年，2月20日，星期一6.6有限布尔代数的结构有限布尔代数与无限布尔代数?对于集合代数(P(X),),当|X|=n1有限时P(X)有限,(P(X),)是有限布尔代数.Theorem(M.H.Stone)设是有限布尔代数,则存在有限集合X使得与集合代数,X)同构.第48页，共65页，2023年，2月20日，星期一实际上,集合X是由有限布尔代数的所有原子组成的集合,先定义一般格上的原子的概念.Def设(L,)是格,其最小元素为0,对于a

L,若a盖住0,则a称为格的原子(atom).例子(图6-16)?第49页，共65页，2023年，2月20日，星期一Property1(P187)Property2(P188)Property3(P188)第50页，共65页，2023年，2月20日，星期一Property4(P188)Property5(P188)Property6(P188)第51页，共65页，2023年，2月20日，星期一ProofoftheStonetheorem:令集合X是由有限布尔代数的所有原子组成的集合.(0)=,单射?满射?保持运算?第52页，共65页，2023年，2月20日，星期一由Stone定理有Corollary1任意有限布尔代数的元素个数为2n,其中n为正整数.Corollary2在同构意义下,2n个元素的有限布尔代数是唯一的,其中n为正整数.作业习题6.61—4.第53页，共65页，2023年，2月20日，星期一6.7布尔表达式布尔表达式的化简及其主范式表示在理论研究和实际应用中都有十分重要的意义.1布尔表达式的定义Def

设是布尔代数，则B上的布尔表达式(Booleanexpression)递归定义如下:(1)B中的元素a,b,c等是布尔表达式.(2)取值于B的变元x1,x2,…等是布尔表达式.(3)若e1和e2是布尔表达式，则,e1+e2,

e1∙e2布尔表达式.(4)有限次使用(1)(2)(3)得到的字符串是仅有的布尔表达式.第54页，共65页，2023年，2月20日，星期一例

设B={0,a,b,1},是布尔代数,则等是B上的布尔表达式.含n个变元x1,x2,…,xn的布尔表达式记为E(x1,x2,…,xn).因此,上例中的两个布尔表达式分别记为逻辑代数上的布尔表达式常称为逻辑表达式.第55页，共65页，2023年，2月20日，星期一设B={0,1},是布尔代数,它是最简单的逻辑代数.在计算机逻辑电路设计中,B中元素的0和1称为逻辑常量,B上的变元称为逻辑变量,B上的布尔表达式称为逻辑表达式,它就是命题公式.例如

等是B上的布尔表达式.第56页，共65页，2023年，2月20日，星期一2.布尔表达式的化简