资源描述：
《格与布尔代数课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3-2章格与布尔代数3-2-1格的概念一、格——一种特殊的偏序集定义1设是偏序集,如果∀x,y∈X,{x,y}都有最小上界和最大下界,则称偏序集为一个格。由于最小上界和最大下界的惟一性,可以把求{x,y}的最小上界和最大下界看成x与y的两种二元运算，记做∨和∧,x∨y∈Xx∧y∈X格，和的哈斯图.格的实例例设n是正整数,Sn是n的正因子的集合。D为整除关系,则偏序集构成格。例设n是正整数,Sn是n的正因子的集合。D为整除关系,则偏序集构成格。x,y∈Sn,x
2、∨y=lcm(x,y),即x与y的最小公倍数。x∧y=gcd(x,y),即x与y的最大公约数。(1),其中P(B)是集合B的幂集。解:是格。x,y∈P(B),x∨y=x∪y,x∧y=x∩y.x∪y,x∩y∈P(B).称,为B的幂集格。(2),其中Z是整数集,≤为小于或等于关系。解:是格。x,y∈Z,x∨y=max(x,y),x∧y=min(x,y)例判断下列偏序集是否构成格,并说明理由。(3)偏序集的哈斯图如下，判断是否格。{a,b}没有最大下界不是格{b,d}有两个上界c和e,但没有最小上界不是格
3、{b,c}有三个上界d,e,f,但没有最小上界。不是格不是格{a,g}没有最大下界。例13.3设G是群,L(G)是G的所有子群的集合。即L(G)={H
4、H≤G}，在L(G)上定义包含关系 ,则L(G)关于包含关系构成一个格,称为G的子群格。对任意的H1,H2∈L(G),H1∩H2也是G的子群,而是由H1∪H2生成的子群（即包含着H1∪H2的最小的子群）.易见在L(G)中,H1∧H2就是H1∩H2,H1∨H2就是.定义2设是一个格,如果在X上定义两个二元运算∨和∧，使得x∨y等于x与y的最小上界，x
5、∧y等于最大下界，则称为由格所诱导的代数系统。由于最小上界和最大下界的惟一性,可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧,x∨y∈X，x∧y∈X(1),其中P(B)是集合B的幂集。x,y∈P(B),x∨y=x∪y,x∧y=x∩y.x∪y,x∩y∈P(B).(2),其中Z是整数集,≤为小于或等于关系。格∀x,y∈Z,x∨y=max(x,y),x∧y=min(x,y)称为格所诱导的代数系统,。幂集格max(x,y)∈Z，min(x,y)∈
6、Z称为格所诱导的代数系统,。二、对偶命题和对偶原理定义是一个格，设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三、格的性质定理1在
7、一个格中，对L中任意元素a,b,c,d都有(1)a≼a∨bb≼a∨ba∧b≼aa∧b≼ba∧c≼b∧d,(2)若a≼b且c≼d,则a∨c≼b∨d证明：a∧c≼a≼ba∧c≼c≼d因此a∧c≼b∧d同理可证a∨c≼b∨d推论在一个格中，对于a,b,c∈L，若a≼b，则a∨c≼b∨ca∧c≼b∧c,证明：由已知a≼b,由定理1有a∨c≼b∨ca∧c≼b∧c,又c≼c,(自反性)定理2设是格,由所诱导的代数系统为，则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1)∀a,b∈L有a∨b=b
8、∨a, a∧b=b∧a∀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∀a,b∈L有a∨(a∧b)=a,a∧(a∨b)=a幂集格设是格，证明：∀a,b,c∈L有(1)a∨(b∧c)≼(a∨b)∧(a∨c)定理3(2)(a∧b)∨(a∧c)≼a∧(b∨c)对偶命题证明：∀a,b,c∈L因为a≼a∨b,a≼a∨c所以a≼(a∨b)∧(a∨c)因为b≼a∨b,c≼a∨c由定理1，有b∧c≼(a∨b)∧(a∨c)所以a∨(b∧c
9、)≼(a∨b)∧(a∨c)(2)证：由最小上界定义有 (a∨b)∨c≽a∨b≽a ①(a∨b)∨c≽a∨b≽b ②(a∨b)∨c≽c③由②和③有 (a∨b)∨c≽b∨c
