邱婉玲耿素云离散数学ch.ppt

《邱婉玲耿素云离散数学ch.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章格与布尔代数主要内容格的定义及性质子格分配格、有补格布尔代数111.1格的定义与性质定义11.1设是偏序集，如果x,yS，{x,y}都有最小上界和最大下界，则称S关于偏序≼作成一个格.求{x,y}最小上界和最大下界看成x与y的二元运算∨和∧，例1设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集构成格.x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数.x∧y是gcd(x,y)，即x与y的最大公约数.2图2例2判断下列偏序集是否构成格，并说明理由.(1)，其中P(B)是集合B的幂集.(2)，其中Z是整

2、数集，≤为小于或等于关系.(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)都不是格.可以找到两个结点缺少最大下界或最小上界3实例：子群格例3设G是群，L(G)是G的所有子群的集合.即L(G)={H

3、H≤G}，对任意的H1,H2∈L(G)，H1∩H2是G的子群，是由H1∪H2生成的子群（即包含着H1∪H2的最小子群）.在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格.在L(G)中，H1∧H

4、2就是H1∩H2H1∨H2就是4格的性质：对偶原理定义11.2设f是含有格中元素以及符号=,≼,≽,∨和∧的命题.令f*是将f中的≼替换成≽,≽替换成≼,∨替换成∧,∧替换成∨所得到的命题.称f*为f的对偶命题.例如,在格中令f是(a∨b)∧c≼c,f*是(a∧b)∨c≽c.格的对偶原理设f是含有格中元素以及符号=,≼,≽,∨和∧等的命题.若f对一切格为真,则f的对偶命题f*也对一切格为真.例如,如果对一切格L都有a,b∈L,a∧b≼a，那么对一切格L都有a,b∈L,a∨b≽a注意：对偶是相互的，即(f*)*=f5格的性质：算律定理11.1设是格,则运算∨和

5、∧适合交换律、结合律、幂等律和吸收律,即(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)=a6证明(1)a∨b是{a,b}的最小上界,b∨a是{b,a}的最小上界.由于{a,b}={b,a},所以a∨b=b∨a.由对偶原理,a∧b=b∧a.(2)由最小上界的定义有(a∨b)∨c≽a∨b≽a(1)(a∨b)∨c≽a∨b≽b(2)

6、(a∨b)∨c≽c(3)由式(2)和(3)有(a∨b)∨c≽b∨c(4)由式(1)和(4)有(a∨b)∨c≽a∨(b∨c)同理可证(a∨b)∨c≼a∨(b∨c)根据反对称性(a∨b)∨c=a∨(b∨c)由对偶原理,(a∧b)∧c=a∧(b∧c)7证明(3)显然a≼a∨a,又由a≼a可得a∨a≼a.根据反对称性有a∨a=a.由对偶原理,a∧a=a得证.(4)显然a∨(a∧b)≽a(5)由a≼a,a∧b≼a可得a∨(a∧b)≼a(6)由式(5)和(6)可得a∨(a∧b)=a,根据对偶原理,a∧(a∨b)=a8格的性质：序与运算的关系定理11.2设L是格,则

7、a,b∈L有a≼ba∧b=aa∨b=b证(1)先证a≼ba∧b=a由a≼a和a≼b可知a是{a,b}的下界,故a≼a∧b.显然有a∧b≼a.由反对称性得a∧b=a.(2)再证a∧b=aa∨b=b根据吸收律有b=b∨(b∧a)由a∧b=a和上面的等式得b=b∨a,即a∨b=b.(3)最后证a∨b=ba≼b由a≼a∨b得a≼a∨b=b9格的性质：保序定理11.3设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

8、.同理可证a∨c≼b∨d证由a≼a,b∧c≼b得a∨(b∧c)≼a∨b由a≼a,b∧c≼c得a∨(b∧c)≼a∨c从而得到a∨(b∧c)≼(a∨b)∧(a∨c)注意：一般说来,格中的∨和∧运算不满足分配律.10格作为代数系统的定义定理11.4设是具有两个二元运算的代数系统,若对于∗和◦运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序≼,使得构成格,且a,b∈S有a∧b=a∗b,a∨b=a◦b.证明省略.根据定