1.格的概念

一、格的概念对于计算机科学来说，格与布尔代数是两个重要的代数系统.在开关理论、计算机的逻辑设计及其它一些科学领域中，有很多直接应用.此两个系统有一个重要特点：强调次序关系.(一)格的定义一、格的概念偏序：若集合A上的二元关系具有(1)自反性，(2)反对称性，(3)传递性，则称之为偏序，A,称为偏序集.例6.1.1设集合X={1,2,3,4,6,12},Y={2,3,6,12,24,36},X和Y上的整除关系“|”就构成两个偏序集：X,|,Y,|.它们的哈斯图如下：24612243623虽然都是哈斯图，但是它们有一个重要的差别：X,|中“每两个元素构成的集合”都有最大下界和最小上界.Y,|无此特点.一、格的概念格的定义格：若偏序集A,中任意两个元素a,b都有最小上界(LUB{a,b})和最大下界(GLB{a,b}),则称A,是格(lattice).通常记：ab=LUB{a,b},ab=GLB{a,b}.由于最小上界、最大下界若存在则唯一，所以、是二元运算，分别称为并运算和交运算.称A,,为由格A,所诱导的代数系统.一、格的概念例6.1.2判断以下偏序集是否是格.(1)Z+,|(2)P(S),m,nZ+,答：是格.答：是格.mn=LCM(m,n).mn=GCD(m,n).S1,S2P(S),S1S2=S1∪S2.S1S2=S1∩S2.m,n的最小公倍数.m,n的最大公约数.一、格的概念例6.1.2判断以下代数系统是否是格.efdcab(3)因为ef不存在.答：不是格.一、格的概念例6.1.2判断以下代数系统是否是格.(4)因为32不存在.答：不是格.51234一、格的概念例6.1.2判断以下代数系统是否是格.(5)因为任何两个元素都有最小上界和最大下界.答：是格.ebcda一、格的概念例6.1.2判断以下代数系统是否是格.(6)因为de不存在.答：不是格.fdbcead,e有三个下界a,b,c,但没有最大的.一、格的概念例6.1.3设集合L={1,2,3,4,5,6,7,8,9,10,11,12},问偏序集L,|是否为格？因为“9”和“10”没有最小上界，解：173112546910812偏序集L,|的哈斯图如下：所以L,|不是格.一、格的概念可以证明：子格必是格.(二)子格子格：设A,是格，A,,是由A,所诱导的代数系统.设BA且B,若运算和在B中封闭，则称B,是A,的子格.一、格的概念例6.1.4设S={a,b,c},则P(S),是格.取A={,{a},{c},{a,c}},B={,{a},{c},{a,b},{b,c},{a,c},{a,b,c}},问A,,B,是P(S),的子格吗？{a,b,c}{a,b}{b,c}{b}{a,c}{c}{a}解：所以A,是P(S),的子格；所以B,不是P(S),的子格.因为{a,b},{b,c}B,但{b}B,因为S1,S2A,有A,A,S1S2=S1∪S2S1S2=S1∩S2可画出P(S),的哈斯图.{a,b}∩{b,c}=设A,是格，BA且B,则B,是偏序集，但但B,不一定是格；B,即使是格，也不一定是A,的子格.例6.1.5设E+是全体正偶数的集合，问E+,|是Z+,|的子格吗？解：2m,2nE+,2m2n=LCM(2m,2n)2m2n=GCD(2m,2n)E+,E+,所以E+,|是Z+,|的子格.一、格的概念例6.1.6设S,是一个格，aS,构造S的子集T={x|xS,xa}则T,是S,的一个子格.解：x,yT,所以(a是x,y的上界)故xyT,xyT.必有xa和ya,xya,又xyxy,所以xya,因此T,是S,的一个子格.一、格的概念(三)格的对偶原理设A,是偏序集，用表示偏序关系的逆关系，则A,也是偏序集.A,与A,的哈斯图是互为颠倒的.a,bA,称A,与A,为彼此对偶的偏序集.若A,是格，则A,也是格，反之亦成立.称这两个格互为对偶.由格A,所诱导的代数系统的并（交）运算，正好是由格A,所诱导的代数系统的交（并）运算.A,的LUB{a,b}对应于A,的GLB{a,b},A,的GLB{a,b}对应于A,的LUB{a,b}.一、格的概念格的对偶原理对偶原理：设P是对任意格都为真的命题，将P中的,,,分别换成,,,得命题P’,则P’对任意格也是真的命题.一、格的概念(四)格的基本性质性质一(自反性)：设A,是一个格，a,b,c,dA(ab)(ba)a=b.性质二(反对称性)：aa,aa.(ab)(ba)a=b,性质三(传递性)：(ab)(bc)ac.(ab)(bc)ac,一、格的概念性质四(确界描述之一)：aba,abb.aab,bab,性质五(确界描述之二)：(ca)(cb)cab.(ac)(bc)abc,格的基本性质一、格的概念性质六：abab=aab=b.证：其它结论类似可证.下面证明abab=a.必要性：设ab,故充分性：因为abb,设ab=a,所以ab.又aa,aab.又aba.所以ab=a.格的基本性质一、格的概念性质七(交换律)：ab=ba,ab=ba.性质八(结合律)：(ab)c=a(bc)(1),(ab)c=a(bc)(2).证：令R1=(ab)c,R2=a(bc),下面证明(2)式，(1)式由对偶原理可得.由性质四可得R1ab,R1cR1a,R1b,R1cR1a,R1bcR1a(bc)=R2同理可证R2R1,所以R2=R1.（性质四,传递性）（性质五）（性质五）格的基本性质一、格的概念因为aba,性质九(幂等律)：性质十(吸收律)：aa=a,aa=a.a(ab)=a(1),a(ab)=a(2).证：下面证明(1)式，(2)式由对偶原理可得.由性质六可得a(ab)=a.由自反性，aa,证：由性质六可得aa=aa=a.格的基本性质一、格的概念性质十一：若ab,cd,则acbd(1),acbd(2).证：下面证明(1)式，(2)式类似可证.已知ab,cd,又由性质四可得bbd,dbd,由传递性可得abd,cbd.由性质五可得acbd.格的基本性质一、格的概念性质十二(保序性)：若bc,则abac,abac.证：已知bc,又由自反性，aa,由性质十一可得abac,abac.格的基本性质一、格的概念性质十三(分配不等式)：(ab)(ac)a(bc)(2).a(bc)(ab)(ac)(1),证：下面证明(1)式，(2)式由对偶原理可得.由性质四，aab,aac,由性质十一，aa(ab)(ac).a=bab,cac,bc(ab)(ac).由性质五，a(bc)(ab)(ac).格的基本性质一、格的概念性质十四(模不等式)：aca(bc)(ab)c.证：（必要性）已知ac,由性质六，ac=c.代入分配不等式，a(bc)(ab)(ac)=(ab)c.（充分性）已知a(bc)(ab)c,由性质四aa(bc),(ab)cc,由传递性ac格的基本性质一、格的概念推论：a(b(ac))(ab)(ac)(2).(ab)(ac)a(b(ac))(1),证：由性质四，aac,应用模不等式a(bc)(ab)c,将c换成ac,得a(b(ac))(ab)(ac).下面证明(2)式，(1)式由对偶原理可得.格的基本性质一、格的概念引理：设A,,是一个代数系统，其中,都是二元运算且满足吸收律，则,必满足幂等律.证：a,bA,因为,满足吸收律，所以a(ab)=a(1),a(ab)=a(2).由b的任意性，在(1)式中用ab取代b等式仍然成立，可得a(a(ab))=a.再由(2)式可得aa=a.同理可证aa=a.a格的基本性质一、格的概念定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.分析：证明思路(1)在A上构造偏序关系;(2)证明偏序集A,中任意两个元素有最小上界和最大下界.任一满足交换律，结合律和吸收律的代数系统诱导一个格.格的基本性质一、格的概念证：在A上定义二元关系:a,bA,ab=a.abStep1证是偏序：1)由运算满足吸收律，根据引理，aA,aa=a.所以aa.从而是自反的.则ab=a,ba=b,2)设ab,ba,而由运算满足交换律可得ab=ba,故a=b.从而是反对称的.定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.一、格的概念续证：则ab=a,bc=b,3)设ab,bc,那么ac=(ab)c=a(bc)=ab=a(结合律)(ab=a)(bc=b)(ab=a)所以ac.从而是传递的.定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.一、格的概念续证：Step2证ab是a,b的最大下界：因为(ab)a==aba(ab)=(aa)b(ab)b=a(bb)=ab再由的定义，可得aba,abb.说明ab是a,b的下界.(交换律)(结合律)(吸收律(幂等律))定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.一、格的概念续证：设c是a,b的任一下界，按的定义有则ca,cb.ca=c,cb=c.进而有c(ab)=(ca)b=cb=c.按的定义有cab.故ab是a,b的最大下界.定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.一、格的概念续证：Step3证ab是a,b的最小上界：先证ab=a与ab=b等价：若ab=a,则ab=(ab)b=b.=b(ab)=b(ba)(ab=a)(交换律)(交换律)(吸收律)反之，若ab=b,则ab=a(ab)=a.(ab=b)(吸收律)定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.一、格的概念续证：ab=b.由此可见，证明开始定义的偏序关系等价于：a,bA,ab可以用证明“ab是a,b的最大下界”类似的方法证明“ab是a,b的最小上界”.综上所述，A,是格.任意一个格A,可诱导一个具有两个二元运算的代数系统A,,,其中运算满足交换律、结合律、吸收律.反之，任意一个运算满足交换律、结合律、吸收律的代数系统也可诱导一个格.定理一：设A,,是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使A,是一个格.一、格的概念(五)格同态与格同构任意一个格A,可视为一个具有两个二元运算的代数系统A,,,其中运算满足交换律、结合律、吸收律.因此，对格可以引入代数系统中同态的概念.一、格的概念格同态与格同构设A1,,A2,是格，它们所诱导的代数系统分别是A1,1,1,A2,2,2,若