格的定义.

格的定义•格是任二元都(在其中)有glb和lub的偏序集,具体说:偏序集S,称为格,如果ab(a,bSglb{a,b}S∧lub{a,b}S).•我们知道:glb或lub若存在必唯一,故glb:SSS,lub:SSS是映射,从而定义格S中的两个二元运算,我们分别把它们记为a*b=glb{a,b}和ab=lub{a,b}并分别称为的a与b保交与保联.•对有限偏序集常用它的Hasse图验证它是否组成一个格,例如教本p215的图7.1-1(a)—(e)是格,7.2c)不是格(后者左右肩两点的glb不存在).abcababcbcacabcd格的举例①每个线性序集,例如R,及其子集,都是格,glb{a,b}=min{a,b};lub{a,b}=max{a,b}.②集S的幂集(S)和包含关系组成偏序集,对任意A,B(S),glb{A,B}=A∩B(S);lub{A,B}=A∪B(S).因此,(S),是格.例如({a,b,c}),的Hasse图在图7.1-1(c)中画出.③正整数集I+与整除关系组成偏序集,对任意a,bI+,glb{a,b}=GCD(a,b)I+;lub{a,b}=LCM(a,b)I+.因此,I+,|是格.特别,对任意正整数nI+,令Sn记n的所有正因子的集,则Sn,|是格.7.1#2S={1,2,3,4,5},S,是格吗?•S,是格,a*b=min(a,b);ab=max(a,b).•一般地,任何线性序集都是格.154327.1#3画出格S72,|的Hasse图72=2332;x=2i3j,i=0,1,2,3;j=0,1,2.S72={72,36,24,18,12,9,8,6,4,3,2,1}91836722481243612格的对偶原理•因偏序的逆关系也是偏序;故B=S,是格B=S,是格;对任意AB,lub(A)=glb(A),glb(A)=lub(A);(记格B中的对应运算)特别对任意a,bS,a*b=ab,ab=a*b.•对偶原理:对于格S,中任何有效公式,把*与;与互换后仍为有效公式.格的基本公式及其证明⑥交换律:a*b=b*a;ab=ba.(其中a,bS为任意元素,下同)证:由对偶原理只须证其中一个即可.例如第一个a*b=glb{a,b}=glb{b,a}=b*a.⑦结合律:(a*b)*c=a*(b*c);(ab)c=(ab)c.证:w(a*b)*ca*b和cwa,b和cwa和b*cwa*(b*c),即(a*b)*c=wa*(b*c).同理可得a*(b*c)(a*b)*c.⑧等幂律:a*a=a;aa=a.证:aaaa*a,又按*定义有a*aa.所以a*a=a.格的基本公式及其证明续⑨吸收律:a*(ab)=a;a(a*b)=a.证:aa∧aabaa*(ab);此外又有a*(ab)a,故结论成立.⑩重要公式:a*b=aabab=b.证:因aba*b=a(1)的对偶为:abab=a,故只须证(1)即可.事实上abaa*b.又a*ba,得证a*b=a.显然a*b=aab,故(1)成立.格的基本公式及其证明续⑾ad∧bca*bd*c.(可证其对偶为ad∧bcabdc)证:因a*bad,a*bbc,故a*bd*c.⑿保序性:bca*ba*c∧abac.证:因恒有aa,故当bc时令d=a结论由⑾推出.⒀分配不等式:a(b*c)(ab)*(ac)(还有对偶式)证:因b*cb;b*cc,故由保序性推出:a(b*c)ab和a(b*c)ac,故结论成立.⒁模不等式:aca(b*c)(ab)*c.证:a(b*c)(ab)*caa(b*c)(ab)*cc.反之acac=c,故结论由⒀推出.7.1#8元素不多于3个的格全是链设S,是格.若|S|=1,它显然是链(全序集);若|S|=2,不妨设|S|={a,b}且ab,则为二元链;若|S|=3,不妨设|S|={a,b,c}.今用反证法证S中任二元a,b都可比较.设a,b不可比较,则glb{a,b},lub{a,b}{a,b},由此得glb{a,b}=c=lub{a,b}.进一步又有ca∧cac=a,矛盾.格的另一个等价定义•有两个二元运算的代数L,*,称为一个格,如果*,都满足交换律,结合律和等幂律并且满足吸收律:对L中任意元素a,b,c有(交换)a*b=b*a;ab=ba;(结合)(a*b)*c=a*(b*c);(ab)c=a(bc);(等幂)a*a=a;aa=a;(吸收)a*(ab)=a=a(a*b);•注:等幂律可由吸收律推出(aa=a(a*(ab))=a),故可从上述定义中删去.格的两个定义等价由格的前一个定义可定义两个二元运算:*,,并已证明*,都满足交换,结合和等幂律并且满足吸收律(见表7.1-1),故它满足格的后一定义.反之,由格的后一定义可证明L是其任二元的lub,glb都在L中的偏序集,从而满足格的前一定义.在L中定义关系:aba*b=a,则等幂律:a*a=a保证自反律aa;ab∧baa*b=a∧b*a=b(交换律)a=b;ab∧bca*b=a∧b*c=b(传递律)a*c=(a*b)*c=a*(b*c)=a*b=a,即ac,得证L,是偏序集.对任意a,bL,设c是a,b的下界,则c*a=c∧c*b=cc*a*b=c,即ca*b;又a*b*b=a*ba*bb,类似有a*ba.glu{a,b}=a*bL.同理lub{a,b}=abL.(注a*b=aab=(a*b)b=b吸收律)子格与格的直接积•作为代数的格L,*,的子代数称为子格,换句话说,若HL,且H对*,封闭,则H,*,是L的子格.•子格H本身也是格,因交换律,结合律,吸收律在L中成立必在H中成立.•设L,L是格,则积代数:LL,*,,其中a,b*c,d=a*c,b*d;a,bc,d=ac,bd,也是格,称为格L与L的直接积.(LL对*,封闭由L,L对*,封闭推出;交换律,结合律,吸收律在L,L中成立推出在L中也成立.)求下图表示的格S,的所有真子格•S,的2元子格(只写载体):{e,d},{e,c},{e,b},{e,a},{b,a},{c,a},{d,a};•S的3元子格:{e,d,a},{e,c,a},{e,b,a};•S的4元子格:{e,d,c,a},{e,d,b,a},{e,c,b,a}.abcde7.2#3格L,的封闭区间[a,b]是子格封闭区间[a,b]定义为由a,b界定的线性序子集:[a,b]={x|xL∧axb},其中a,bL.证:[a,b]显然是L的子集;x,y[a,b]axb∧ayb即a(b)为{x,y}的下(上)界ax*yxyb即x*y,xy[a,b][a,b]对*,封闭,从而是L的一个子格.格的同态•作为代数的格L,*,的代数同态称为格同态,具体讲,f:L,*,L,*,称为格同态,如果对任何a,bL,有f(a*b)=f(a)*f(b),和f(ab)=f(a)f(b).•格的同态象是陪域格L的子格(见定理6.3-2)(习题7.2#6).•(定理7.2-2)格同态f:L,*,;L,*,,是保序的:对任何a,bL有abf(a)f(b).证:aba*b=af(a)=f(a*b)=f(a)*f(b)f(a)f(b).格的同构•双射的格同态称为格同构.•任意格同构的定义域格与陪域格的Hasse图除标记外完全相同.•(p220例1)不计同构差别只有2个4元格,如图7.2-4所示;不计同构差别只有5个5元格,如图7.2-5所示.分配格的定义•其两个运算满足分配律的格称为分配格,具体讲,格L,*,称为分配格,如果对任何a,bL有a*(bc)=(a*b)(a*c),(1)和a(b*c)=(ab)*(ac).(2)•由格的对偶原理,(1)成立当且仅当(2)成立,故L,*,为分配格当且仅当(1)和(2)之一成立即可.•(7.3#1)用吸收律证(1)(2).(ab)*(ac)=((ab)*a)((ab)*c)用(1)=a((a*c)(b*c))用吸收律和(1)=a(b*c)用结合律和吸收律分配格举例①链(线性序集)是分配格.例如,I,min,max,(7.3#5)是分配格.证:设a,b,c为链S,的任意3元.若a=glb{a,b,c},则a*(bc)=a=aa=(a*b)(a*c);若a=lub{a,b,c},则a*(bc)=bc=(a*b)(a*c);若bac,则a*(bc)=a*c=a=ba=(a*b)(a*c).②集S的幂集格(S),∪,∩,是分配格.证:由集合论知(定理2.2-2):A∩(B∪C)=(A∩B)∪(A∩C).对任意正整数nSn,GCD,LCM是分配格证:对任意x,ySn,由I,min,max,是分配格知min(ai,max(bi,ci))=max(min(ai,bi),min(ai,ci)).由此立即推出GCD(x,LCM(y,z))=LCM(GCD(x,y),GCD(x,z)).所以,格Sn,GCD,LCM是分配格.kkmkmnknppyppx1111,},{max},{max111),(kkmnkmnppyxLCM},{min},{min111),(kkmnkmnppyxGCD非分配格的举例a*(bc)=a*1=a,b*(ac)=b*1=b(a*b)(a*c)=00=0,(b*a)(b*c)=0c=c注①此两例都不满足双消去律:a*b=a*c∧ab=acb=c.②可以证明:格L是分配格当且仅当L没有同构于例1或例2的子格.1bc01ab0ca例1例2分配格的充要条件•定理:格L,*,是分配格当且仅当在L中成立双消去律:a*b=a*c∧ab=acb=c.证:由已知条件,分配律及吸收律立即推出必要性:c=c*(ac)=c*(ab)=(c*a)(c*b)=(b*a)(c*b)=(ac)*b=(ab)*b=b.充分性(7.3#2)(由逆反律)等价于:若L不是分配格,则在L中双消去律不成立.但这一结论可由上面关于非分配格的注①和②推出(在L中有同构于例1或例2的子格,它们都不满足双消去律).格的全下界与全上界的概念•格L,(视为偏序集)的元素a称为L的全下(上)界,如果b(bLab)(b(bLba))•格的全下(上)界至多有一个,并记为0(1).证:若有两个:u,v,则uv∧vu,进而推出u=v.•由定义得:对任意bL有b*0=0,b0=b;b*1=b,b1=1.•例①对任何有限格L={a1,…,an}有0=a1**an,1=a1an(a1**an=ai*bai).•②I,全下界,全上界皆无;N,有全下界0而无全上界;[0,1],全下界,全上界皆有.有界格与有补格定义:同时有全下界0和全上界1的格称为有界格;有界格L,*,,0,1的元素a的补元是满足a*b=0∧ab=1的元素bL;每元都有补元的有界格称为有补格.例:幂集格(S),∪,∩,,,S及图7.3-4中的格.注①0和1互为补元,且是唯一的(定理7.3-7).②a{0,1}的补元一般不唯一