1第十一章格与布尔代数主要内容格的定义及性质子格分配格、有补格布尔代数211.1格的定义与性质定义11.1设S,≼是偏序集,如果x,yS,{x,y}都有最小上界和最大下界,则称S关于偏序≼作成一个格.(偏序关系P126)求{x,y}最小上界和最大下界看成x与y的二元运算∨和∧,例1设n是正整数,Sn是n的正因子的集合.D为整除关系,则偏序集Sn,D构成格.x,y∈Sn,x∨y是lcm(x,y),即x与y的最小公倍数.x∧y是gcd(x,y),即x与y的最大公约数.3图2例2判断下列偏序集是否构成格,并说明理由.(1)P(B),,其中P(B)是集合B的幂集.(2)Z,≤,其中Z是整数集,≤为小于或等于关系.(3)偏序集的哈斯图分别在下图给出.实例(1)幂集格.x,y∈P(B),x∨y就是x∪y,x∧y就是x∩y.(2)是格.x,y∈Z,x∨y=max(x,y),x∧y=min(x,y),(3)都不是格.可以找到两个结点缺少最大下界或最小上界4格的性质:算律定理11.1设L,≼是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1)a,b∈L有a∨b=b∨a,a∧b=b∧a(2)a,b,c∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L有a∨a=a,a∧a=a(4)a,b∈L有a∨(a∧b)=a,a∧(a∨b)=a5格的性质:序与运算的关系定理11.3设L是格,则a,b∈L有a≼ba∧b=aa∨b=b可以用集合的例子来验证幂集格P(B),,其中P(B)是集合B的幂集.幂集格.x,y∈P(B),x∨y就是x∪y,x∧y就是x∩y.6格的性质:保序定理11.4设L是格,a,b,c,d∈L,若a≼b且c≼d,则a∧c≼b∧d,a∨c≼b∨d例4设L是格,证明a,b,c∈L有a∨(b∧c)≼(a∨b)∧(a∨c).证a∧c≼a≼b,a∧c≼c≼d因此a∧c≼b∧d.同理可证a∨c≼b∨d证由a≼a,b∧c≼b得a∨(b∧c)≼a∨b由a≼a,b∧c≼c得a∨(b∧c)≼a∨ca∨(b∧c)≼(a∨b)∧(a∨c)(注意最大下界)注意:一般说来,格中的∨和∧运算不满足分配律.7格作为代数系统的定义定理11.4设S,∗,◦是具有两个二元运算的代数系统,若对于∗和◦运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序≼,使得S,≼构成格,且a,b∈S有a∧b=a∗b,a∨b=a◦b.证明省略.根据定理11.4,可以给出格的另一个等价定义.定义11.3设S,∗,◦是代数系统,∗和◦是二元运算,如果∗和◦满足交换律、结合律和吸收律,则S,∗,◦构成格.811.2分配格、有补格与布尔代数定义11.5设L,∧,∨是格,若a,b,c∈L,有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.注意:可以证明以上两个条件互为充分必要条件L1和L2是分配格,L3和L4不是分配格.称L3为钻石格,L4为五角格.实例9有界格的定义定义11.6设L是格,(1)若存在a∈L使得x∈L有a≼x,则称a为L的全下界(2)若存在b∈L使得x∈L有x≼b,则称b为L的全上界说明:格L若存在全下界或全上界,一定是惟一的.一般将格L的全下界记为0,全上界记为1.定义11.7设L是格,若L存在全下界和全上界,则称L为有界格,一般将有界格L记为L,∧,∨,0,1.10定理11.6设L,∧,∨,0,1是有界格,则a∈L有a∧0=0,a∨0=a,a∧1=a,a∨1=1注意:有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是L的全上界.0是关于∧运算的零元,∨运算的单位元;1是关于∨运算的零元,∧运算的单位元.有界格的性质11有界格中的补元及实例定义11.8设L,∧,∨,0,1是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,则称b是a的补元.注意:若b是a的补元,那么a也是b的补元.a和b互为补元.例7考虑下图中的格.针对不同的元素,求出所有的补元.12解答(1)L1中a与c互为补元,其中a为全下界,c为全上界,b没有补元.(2)L2中a与d互为补元,其中a为全下界,d为全上界,b与c也互为补元.(3)L3中a与e互为补元,其中a为全下界,e为全上界,b的补元是c和d;c的补元是b和d;d的补元是b和c;b,c,d每个元素都有两个补元.(4)L4中a与e互为补元,其中a为全下界,e为全上界,b的补元是c和d;c的补元是b;d的补元是b.13有界分配格的补元惟一性定理11.7设L,∧,∨,0,1是有界分配格.若L中元素a存在补元,则存在惟一的补元.证假设c是a的补元,a∨c=1,a∧c=0,又知b是a的补元,故a∨b=1,a∧b=0从而得到a∨c=a∨b,a∧c=a∧b,由于L是分配格.b=b∧(b∨a)=b∧(c∨a)=(b∧c)∨(b∧a)=(a∨c)∧c=c注意:在任何有界格中,全下界0与全上界1互补.对于一般元素,可能存在补元,也可能不存在补元.如果存在补元,可能是惟一的,也可能是多个补元.对于有界分配格,如果元素存在补元,一定是惟一的.14图9有补格的定义定义11.9设L,∧,∨,0,1是有界格,若L中所有元素都有补元存在,则称L为有补格.例如,图中的L2,L3和L4是有补格,L1不是有补格.15布尔代数的定义与实例定义11.10如果一个格是有补分配格,则称它为布尔格或布尔代数.布尔代数标记为B,∧,∨,,0,1,为求补运算.例8设S110={1,2,5,10,11,22,55,110}是110的正因子集合,gcd表示求最大公约数的运算,lcm表示求最小公倍数的运算,问S110,gcd,lcm是否构成布尔代数?为什么?解画出哈斯图?(1)不难验证S110关于gcd和lcm运算构成格.(略)(2)验证分配律x,y,z∈S110有gcd(x,lcm(y,z))=lcm(gcd(x,y),gcd(x,z))(3)验证它是有补格,1作为S110中的全下界,110为全上界,1和110互为补元,2和55互为补元,5和22互为补元,10和11互为补元,从而证明了S110,gcd,lcm为布尔代数.16布尔代数的性质定理11.8设B,∧,∨,,0,1是布尔代数,则(1)a∈B,(a)=a.(2)a,b∈B,(a∧b)=a∨b,(a∨b)=a∧b(德摩根律)证(1)(a)是a的补元,a也是a的补元.由补元惟一性得(a)=a.(2)对任意a,b∈B有(a∧b)∨(a∨b)=(a∨a∨b)∧(b∨a∨b)=(1∨b)∧(a∨1)=1∧1=1,(a∧b)∧(a∨b)=(a∧b∧a)∨(a∧b∧b)=(0∧b)∨(a∧0)=0∨0=0a∨b是a∧b的补元,根据补元惟一性有(a∧b)=a∨b,同理可证(a∨b)=a∧b.注意:德摩根律对有限个元素也是正确的.17图11实例下图给出了1元,2元,4元和8元的布尔代数.18第十一章习题课主要内容格的两个等价定义格的性质子格特殊格:分配格、有界格、有补格、布尔代数基本要求能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够证明格中的等式和不等式能判别格L的子集S是否构成子格能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式19解1.求图中格的所有子格.1元子格:{a},{b},{c},{d},{e};2元子格:{a,b},{a,c},{a,d},{a,e},{b,c},{b,d},{b,e},{c,e},{d,e};3元子格:{a,b,c},{a,b,d},{a,b,e},{a,c,e},{a,d,e},{b,c,e},{b,d,e};4元子格:{a,b,c,e},{a,b,d,e},{b,c,d,e};5元子格:{a,b,c,d,e}练习1eabcd20L1L2L3图122.针对下图,求出每个格的补元并说明它们是否为有补格L1中,a与h互为补元,其他元素没补元.L2中,a与g互为补元.b的补元为c,d,f;c的补元为b,d,e,f;d的补元为b,c,e;e的补元为c,d,f;f的补元为b,c,e.L3中,a与h互为补元,b的补元为d;c的补元为d;d的补元为b,c,g;g的补元为d.L2与L3是有补格.练习2