第六章格和代数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,|>.它们的哈斯图如下：1243612612243623虽然都是哈斯图，但是它们有一个重要的差别：<X,|>中“每两个元素构成的集合”都有最大下界和最小上界.<Y,|>无此特点.一、格的概念格的定义格：若偏序集<A,>中任意两个元素a,b都有最小上界(LUB{a,b})和最大下界(GLB{a,b}),则称<A,>是格(lattice).通常记：ab=LUB{a,b},ab=GLB{a,b}.由于最小上界、最大下界若存在则唯一，所以、是二元运算，分别称为并运算和交运算.称<A,,>为由格<A,>所诱导的代数系统.一、格的概念例6.1.2判断以下偏序集是否是格.(1)<Z+,|>(2)<P(S),>

m,nZ+,答：是格.答：是格.mn=

LCM(m,n).mn=

GCD(m,n).

S1,S2P(S),S1S2=

S1∪S2.S1S2=

S1∩S2.m,n的最小公倍数.m,n的最大公约数.一、格的概念例6.1.2判断以下代数系统是否是格.efdcab(3)因为e

f不存在.答：不是格.一、格的概念例6.1.2判断以下代数系统是否是格.(4)因为32不存在.答：不是格.51234一、格的概念例6.1.2判断以下代数系统是否是格.(5)因为任何两个元素都有最小上界和最大下界.答：是格.ebcda一、格的概念例6.1.2判断以下代数系统是否是格.(6)因为de不存在.答：不是格.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,>所诱导的代数系统.设BA且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,S2A,有A,A,S1S2=

S1∪S2S1S2=

S1∩S2可画出<P(S),>的哈斯图.{a,b}∩{b,c}=设<A,>是格，BA且B,则<B,>是偏序集，但但<B,>不一定是格；<B,>即使是格，也不一定是<A,>的子格.例6.1.5

设E+是全体正偶数的集合，问<E+,|>是<Z+,|>的子格吗？解：2m,2nE+,2m2n=

LCM(2m,2n)2m2n=

GCD(2m,2n)E+,E+,所以<E+,|>是<Z+,|>的子格.一、格的概念例6.1.6

设<S,>是一个格，aS,构造S的子集T={x|xS,xa}则<T,>是<S,>的一个子格.解：x,yT,所以(a是x,y的上界)故xyT,xyT.必有xa和ya,xya,又xyxy,所以xya,因此<T,>是<S,>的一个子格.一、格的概念(三)格的对偶原理

设<A,>是偏序集，用表示偏序关系的逆关系，则<A,>也是偏序集.<A,>与<A,>的哈斯图是互为颠倒的.a,bA,

称<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,dA(ab)(ba)a=b.性质二(反对称性)：aa,aa.(ab)(ba)a=b,性质三(传递性)：(ab)(bc)ac.(ab)(bc)ac,一、格的概念性质四(确界描述之一)：aba,abb.aab,bab,性质五(确界描述之二)：(ca)(cb)cab.(ac)(bc)abc,格的基本性质一、格的概念性质六：abab=aab=b.证：其它结论类似可证.下面证明abab=a.必要性：设ab,故充分性：因为abb,设ab=a,所以ab.又aa,aab.又ab

a.所以ab=a.格的基本性质一、格的概念性质七(交换律)：ab=ba,ab=ba.性质八(结合律)：(ab)c=a(bc)(1),(ab)c=a(bc)(2).证：令R1=(ab)c,R2=a(bc),下面证明(2)式，(1)式由对偶原理可得.由性质四可得R1

ab,R1

cR1

a,R1

b,R1

cR1

a,R1

bcR1

a(bc)=R2同理可证R2

R1,所以R2=R1.（性质四,传递性）（性质五）（性质五）格的基本性质一、格的概念因为aba,性质九(幂等律)：性质十(吸收律)：aa=a,aa=a.a(ab)=a(1),a(ab)=a(2).证：下面证明(1)式，(2)式由对偶原理可得.由性质六可得a(ab)=a.由自反性，aa,证：由性质六可得aa=aa

=a.格的基本性质一、格的概念性质十一：若ab,cd,则acbd(1),acbd(2).证：下面证明(1)式，(2)式类似可证.已知ab,cd,又由性质四可得bbd,dbd,由传递性可得abd,cbd.由性质五可得acbd.格的基本性质一、格的概念性质十二(保序性)：若bc,则abac,abac.证：已知bc,又由自反性，aa,由性质十一可得abac,abac.格的基本性质一、格的概念性质十三(分配不等式)：(ab)(ac)a(bc)(2).a(bc)

(ab)(ac)(1),证：下面证明(1)式，(2)式由对偶原理可得.由性质四，aab,aac,由性质十一，aa(ab)(ac).a=bab,cac,bc(ab)(ac).由性质五，a(bc)

(ab)(ac).格的基本性质一、格的概念性质十四(模不等式)：ac

a(bc)

(ab)c.证：（必要性）已知ac,由性质六，ac=c.代入分配不等式，a(bc)

(ab)(ac)=(ab)c.（充分性）已知

a(bc)

(ab)c,由性质四a

a(bc),(ab)c

c,由传递性ac格的基本性质一、格的概念推论：a(b(ac))

(ab)(ac)(2).(ab)(ac)a(b(ac))(1),证：由性质四，aac,应用模不等式

a(bc)

(ab)c,将c换成ac,得a(b(ac))

(ab)(ac).下面证明(2)式，(1)式由对偶原理可得.格的基本性质一、格的概念引理：设<A,,>是一个代数系统，其中,都是二元运算且满足吸收律，则,必满足幂等律.证：

a,bA,因为,满足吸收律，所以a(ab)=a(1),a(ab)=a(2).由b的任意性，在(1)式中用ab取代b等式仍然成立，可得a(a(ab))=a.再由(2)式可得aa=a.同理可证aa=a.a格的基本性质一、格的概念定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.分析：证明思路(1)在A上构造偏序关系;(2)证明偏序集<A,>中任意两个元素有最小上界和最大下界.任一满足交换律，结合律和吸收律的代数系统诱导一个格.格的基本性质一、格的概念证：在A上定义二元关系:

a,bA,

ab=a.a

bStep1证是偏序：1)由运算满足吸收律，根据引理，aA,aa=a.所以aa.从而是自反的.则ab=a,ba=b,2)设ab,ba,而由运算满足交换律可得ab=ba,故a=b.从而是反对称的.定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.一、格的概念续证：则ab=a,bc=b,3)设ab,bc,那么ac=(ab)

c=a(bc)=ab=a(结合律)(ab=a)(bc=b)(ab=a)所以ac.从而是传递的.定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.一、格的概念续证：Step2证ab是a,b的最大下界：因为(ab)a==aba(ab)=(aa)b(ab)b=a(bb)=ab再由的定义，可得ab

a,ab

b.说明ab是a,b的下界.(交换律)(结合律)(吸收律(幂等律))定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.一、格的概念续证：设c是a,b的任一下界，按的定义有则ca,cb.ca=c,cb=c.进而有c(ab)=(ca)b=cb=c.按的定义有cab.故ab是a,b的最大下界.定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.一、格的概念续证：Step3证ab是a,b的最小上界：先证ab=a与ab=b等价：若ab=a,则ab=(ab)b=b.=b(ab)=b(ba)(ab=a)(交换律)(交换律)(吸收律)反之，若ab=b,则ab=a(ab)=a.(ab=b)(吸收律)定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.一、格的概念续证：

ab=b.由此可见，证明开始定义的偏序关系等价于：

a,bA,ab可以用证明“ab是a,b的最大下界”类似的方法证明“ab是a,b的最小上界”.综上所述，<A,>是格.

任意一个格<A,>可诱导一个具有两个二元运算的代数系统<A,,>,其中运算满足交换律、结合律、吸收律.反之，任意一个运算满足交换律、结合律、吸收律的代数系统也可诱导一个格.定理一：设<A,,>是一个代数系统，其中,都是二元运算且满足交换律，结合律和吸收律，则A上存在偏序关系,使<A,>是一个格.一、格的概念(五)格同态与格同构

任意一个格<A,>可视为一个具有两个二元运算的代数系统<A,,>,其中运算满足交换律、结合律、吸收律.

因此，对格可以引入代数系统中同态的概念.一、格的概念格同态与格同构

设<A1,>,<A2,>是格，它们所诱导的代数系统分别是<A1,1,1>,<A2,2,2>,若存在映射f:A1A2,对a,bA1,有

f(a1b)=f(a)2

f(b),称<f(A1),>是<A1,>的格同态象.f(a1b)=f(a)2

f(b),若f是双射，则称f是从<A1,1,1>到<A2,2,2>的格同构，也称格<A,>与<A,>同构.则称f是从<A1,1,1>到<A2,2,2>的格同态.一、格的概念定理二：设f是格<A1,>到<A2,>的格同态，a,b

A1,若ab,必有f(a)f(b).

因为ab,证：所以a

1b=a.从而f(a)=f(a

1b)=f(a)2f(b)故f(a)f(b).(f是格同态)

此定理说明，格同态是保序的.但其逆不真.格同态的性质一、格的概念例6.1.7设集合X={1,2,3,4,6,12},<X,|>,<X,>都是格，它们的哈斯图如下：1243612作映射f:XX,f(x)=x.6124321显然若x|y,则f(x)

f(y),因而f是保序的.但f不是格同态.例如：f(416)f(4)2

f(6).

=2=4一、格的概念格同构的性质定理三：设两个格<A1,>和<A2,>,f是A1到A2的双射，则f是格<A1,>到格<A2,>的格同构，当且仅当a,b

A1,ab

f(a)f(b).

故ab.证：a

1b=a,

f(a)f(b);

f(a)=f(a)2f(b)=f(a

1b)(f是格同构)反之，若f(a)f(b),则而f是双射，则设f是格<A1,>到格<A2,>的格同构.由定理二，a,b

A1,若ab,一、格的概念续证：设a,b

A1,ab

f(a)f(b).

定理三：设两个格<A1,>和<A2,>,f是A1到A2的双射，则f是格<A1,>到格<A2,>的格同构，当且仅当a,b

A1,ab

f(a)f(b).

要证f是格<A1,>到格<A2,>的格同构，即要证f(a1b