第六章格和代數(shù)1.的概念

一、格的概念

對(duì)于計(jì)算機(jī)科學(xué)來說，格與布爾代數(shù)是兩個(gè)重要的代數(shù)系統(tǒng).在開關(guān)理論、計(jì)算機(jī)的邏輯設(shè)計(jì)及其它一些科學(xué)領(lǐng)域中，有很多直接應(yīng)用.此兩個(gè)系統(tǒng)有一個(gè)重要特點(diǎn)：強(qiáng)調(diào)次序關(guān)系.(一)格的定義一、格的概念偏序：若集合A上的二元關(guān)系具有(1)自反性，(2)反對(duì)稱性，(3)傳遞性，則稱之為偏序，<A,>稱為偏序集.例6.1.1設(shè)集合X={1,2,3,4,6,12},Y={2,3,6,12,24,36},X和Y上的整除關(guān)系“|”就構(gòu)成兩個(gè)偏序集：<X,|>,<Y,|>.它們的哈斯圖如下：1243612612243623雖然都是哈斯圖，但是它們有一個(gè)重要的差別：<X,|>中“每?jī)蓚€(gè)元素構(gòu)成的集合”都有最大下界和最小上界.<Y,|>無此特點(diǎn).一、格的概念格的定義格：若偏序集<A,>中任意兩個(gè)元素a,b都有最小上界(LUB{a,b})和最大下界(GLB{a,b}),則稱<A,>是格(lattice).通常記：ab=LUB{a,b},ab=GLB{a,b}.由于最小上界、最大下界若存在則唯一，所以、是二元運(yùn)算，分別稱為并運(yùn)算和交運(yùn)算.稱<A,,>為由格<A,>所誘導(dǎo)的代數(shù)系統(tǒng).一、格的概念例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的最小公倍數(shù).m,n的最大公約數(shù).一、格的概念例6.1.2判斷以下代數(shù)系統(tǒng)是否是格.efdcab(3)因?yàn)閑

f不存在.答：不是格.一、格的概念例6.1.2判斷以下代數(shù)系統(tǒng)是否是格.(4)因?yàn)?2不存在.答：不是格.51234一、格的概念例6.1.2判斷以下代數(shù)系統(tǒng)是否是格.(5)因?yàn)槿魏蝺蓚€(gè)元素都有最小上界和最大下界.答：是格.ebcda一、格的概念例6.1.2判斷以下代數(shù)系統(tǒng)是否是格.(6)因?yàn)閐e不存在.答：不是格.fdbcead,e有三個(gè)下界a,b,c,但沒有最大的.一、格的概念例6.1.3設(shè)集合L={1,2,3,4,5,6,7,8,9,10,11,12},問偏序集<L,|>是否為格？因?yàn)椤?”和“10”沒有最小上界，解：173112546910812偏序集<L,|>的哈斯圖如下：所以<L,|>不是格.一、格的概念可以證明：子格必是格.(二)子格子格：設(shè)<A,>是格，<A,,>是由<A,>所誘導(dǎo)的代數(shù)系統(tǒng).設(shè)BA且B,若運(yùn)算和在B中封閉，則稱<B,>是<A,>的子格.一、格的概念例6.1.4

設(shè)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}{a,c}{c}{a}

解：所以<A,>是<P(S),>的子格；所以<B,>不是<P(S),>的子格.因?yàn)閧a,b},{b,c}B,但B,因?yàn)?/p>

S1,S2A,有A,A,S1S2=

S1∪S2S1S2=

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

設(shè)E+是全體正偶數(shù)的集合，問<E+,|>是<Z+,|>的子格嗎？解：2m,2nE+,2m2n=

LCM(2m,2n)2m2n=

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

設(shè)<S,>是一個(gè)格，aS,構(gòu)造S的子集T={x|xS,xa}則<T,>是<S,>的一個(gè)子格.解：x,yT,所以(a是x,y的上界)故xyT,xyT.必有xa和ya,xya,又xyxy,所以xya,因此<T,>是<S,>的一個(gè)子格.一、格的概念(三)格的對(duì)偶原理

設(shè)<A,>是偏序集，用表示偏序關(guān)系的逆關(guān)系，則<A,>也是偏序集.<A,>與<A,>的哈斯圖是互為顛倒的.a,bA,

稱<A,>與<A,>為彼此對(duì)偶的偏序集.若<A,>是格，則<A,>也是格，反之亦成立.稱這兩個(gè)格互為對(duì)偶.由格<A,>所誘導(dǎo)的代數(shù)系統(tǒng)的并（交）運(yùn)算，正好是由格<A,>所誘導(dǎo)的代數(shù)系統(tǒng)的交（并）運(yùn)算.<A,>的LUB{a,b}對(duì)應(yīng)于<A,>的GLB{a,b},<A,>的GLB{a,b}對(duì)應(yīng)于<A,>的LUB{a,b}.一、格的概念格的對(duì)偶原理對(duì)偶原理：設(shè)P是對(duì)任意格都為真的命題，將P中的,,,分別換成,,,得命題P’,則P’對(duì)任意格也是真的命題.一、格的概念(四)格的基本性質(zhì)性質(zhì)一(自反性)：設(shè)<A,>是一個(gè)格，a,b,c,dA(ab)(ba)a=b.性質(zhì)二(反對(duì)稱性)：aa,aa.(ab)(ba)a=b,性質(zhì)三(傳遞性)：(ab)(bc)ac.(ab)(bc)ac,一、格的概念性質(zhì)四(確界描述之一)：aba,abb.aab,bab,性質(zhì)五(確界描述之二)：(ca)(cb)cab.(ac)(bc)abc,格的基本性質(zhì)一、格的概念性質(zhì)六：abab=aab=b.證：其它結(jié)論類似可證.下面證明abab=a.必要性：設(shè)ab,故充分性：因?yàn)閍bb,設(shè)ab=a,所以ab.又aa,aab.又ab

a.所以ab=a.格的基本性質(zhì)一、格的概念性質(zhì)七(交換律)：ab=ba,ab=ba.性質(zhì)八(結(jié)合律)：(ab)c=a(bc)(1),(ab)c=a(bc)(2).證：令R1=(ab)c,R2=a(bc),下面證明(2)式，(1)式由對(duì)偶原理可得.由性質(zhì)四可得R1

ab,R1

cR1

a,R1

b,R1

cR1

a,R1

bcR1

a(bc)=R2同理可證R2

R1,所以R2=R1.（性質(zhì)四,傳遞性）（性質(zhì)五）（性質(zhì)五）格的基本性質(zhì)一、格的概念因?yàn)閍ba,性質(zhì)九(冪等律)：性質(zhì)十(吸收律)：aa=a,aa=a.a(ab)=a(1),a(ab)=a(2).證：下面證明(1)式，(2)式由對(duì)偶原理可得.由性質(zhì)六可得a(ab)=a.由自反性，aa,證：由性質(zhì)六可得aa=aa

=a.格的基本性質(zhì)一、格的概念性質(zhì)十一：若ab,cd,則acbd(1),acbd(2).證：下面證明(1)式，(2)式類似可證.已知ab,cd,又由性質(zhì)四可得bbd,dbd,由傳遞性可得abd,cbd.由性質(zhì)五可得acbd.格的基本性質(zhì)一、格的概念性質(zhì)十二(保序性)：若bc,則abac,abac.證：已知bc,又由自反性，aa,由性質(zhì)十一可得abac,abac.格的基本性質(zhì)一、格的概念性質(zhì)十三(分配不等式)：(ab)(ac)a(bc)(2).a(bc)

(ab)(ac)(1),證：下面證明(1)式，(2)式由對(duì)偶原理可得.由性質(zhì)四，aab,aac,由性質(zhì)十一，aa(ab)(ac).a=bab,cac,bc(ab)(ac).由性質(zhì)五，a(bc)

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

a(bc)

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

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

a(bc)

(ab)c,由性質(zhì)四a

a(bc),(ab)c

c,由傳遞性ac格的基本性質(zhì)一、格的概念推論：a(b(ac))

(ab)(ac)(2).(ab)(ac)a(b(ac))(1),證：由性質(zhì)四，aac,應(yīng)用模不等式

a(bc)

(ab)c,將c換成ac,得a(b(ac))

(ab)(ac).下面證明(2)式，(1)式由對(duì)偶原理可得.格的基本性質(zhì)一、格的概念引理：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足吸收律，則,必滿足冪等律.證：

a,bA,因?yàn)?滿足吸收律，所以a(ab)=a(1),a(ab)=a(2).由b的任意性，在(1)式中用ab取代b等式仍然成立，可得a(a(ab))=a.再由(2)式可得aa=a.同理可證aa=a.a格的基本性質(zhì)一、格的概念定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.分析：證明思路(1)在A上構(gòu)造偏序關(guān)系;(2)證明偏序集<A,>中任意兩個(gè)元素有最小上界和最大下界.任一滿足交換律，結(jié)合律和吸收律的代數(shù)系統(tǒng)誘導(dǎo)一個(gè)格.格的基本性質(zhì)一、格的概念證：在A上定義二元關(guān)系:

a,bA,

ab=a.a

bStep1證是偏序：1)由運(yùn)算滿足吸收律，根據(jù)引理，aA,aa=a.所以aa.從而是自反的.則ab=a,ba=b,2)設(shè)ab,ba,而由運(yùn)算滿足交換律可得ab=ba,故a=b.從而是反對(duì)稱的.定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.一、格的概念續(xù)證：則ab=a,bc=b,3)設(shè)ab,bc,那么ac=(ab)

c=a(bc)=ab=a(結(jié)合律)(ab=a)(bc=b)(ab=a)所以ac.從而是傳遞的.定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.一、格的概念續(xù)證：Step2證ab是a,b的最大下界：因?yàn)?ab)a==aba(ab)=(aa)b(ab)b=a(bb)=ab再由的定義，可得ab

a,ab

b.說明ab是a,b的下界.(交換律)(結(jié)合律)(吸收律(冪等律))定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.一、格的概念續(xù)證：設(shè)c是a,b的任一下界，按的定義有則ca,cb.ca=c,cb=c.進(jìn)而有c(ab)=(ca)b=cb=c.按的定義有cab.故ab是a,b的最大下界.定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.一、格的概念續(xù)證：Step3證ab是a,b的最小上界：先證ab=a與ab=b等價(jià)：若ab=a,則ab=(ab)b=b.=b(ab)=b(ba)(ab=a)(交換律)(交換律)(吸收律)反之，若ab=b,則ab=a(ab)=a.(ab=b)(吸收律)定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.一、格的概念續(xù)證：

ab=b.由此可見，證明開始定義的偏序關(guān)系等價(jià)于：

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

任意一個(gè)格<A,>可誘導(dǎo)一個(gè)具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)<A,,>,其中運(yùn)算滿足交換律、結(jié)合律、吸收律.反之，任意一個(gè)運(yùn)算滿足交換律、結(jié)合律、吸收律的代數(shù)系統(tǒng)也可誘導(dǎo)一個(gè)格.定理一：設(shè)<A,,>是一個(gè)代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律，結(jié)合律和吸收律，則A上存在偏序關(guān)系,使<A,>是一個(gè)格.一、格的概念(五)格同態(tài)與格同構(gòu)

任意一個(gè)格<A,>可視為一個(gè)具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)<A,,>,其中運(yùn)算滿足交換律、結(jié)合律、吸收律.

因此，對(duì)格可以引入代數(shù)系統(tǒng)中同態(tài)的概念.一、格的概念格同態(tài)與格同構(gòu)

設(shè)<A1,>,<A2,>是格，它們所誘導(dǎo)的代數(shù)系統(tǒng)分別是<A1,1,1>,<A2,2,2>,若存在映射f:A1A2,對(duì)a,bA1,有

f(a1b)=f(a)2

f(b),稱<f(A1),>是<A1,>的格同態(tài)象.f(a1b)=f(a)2

f(b),若f是雙射，則稱f是從<A1,1,1>到<A2,2,2>的格同構(gòu)，也稱格<A,>與<A,>同構(gòu).則稱f是從<A1,1,1>到<A2,2,2>的格同態(tài).一、格的概念定理二：設(shè)f是格<A1,>到<A2,>的格同態(tài)，a,b

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

因?yàn)閍b,證：所以a

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

1b)=f(a)2f(b)故f(a)f(b).(f是格同態(tài))

此定理說明，格同態(tài)是保序的.但其逆不真.格同態(tài)的性質(zhì)一、格的概念例6.1.7設(shè)集合X={1,2,3,4,6,12},<X,|>,<X,>都是格，它們的哈斯圖如下：1243612作映射f:XX,f(x)=x.6124321顯然若x|y,則f(x)

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

f(6).

=2=4一、格的概念格同構(gòu)的性質(zhì)定理三：設(shè)兩個(gè)格<A1,>和<A2,>,f是A1到A2的雙射，則f是格<A1,>到格<A2,>的格同構(gòu)，當(dāng)且僅當(dāng)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是格同構(gòu))反之，若f(a)f(b),則而f是雙射，則設(shè)f是格<A1,>到格<A2,>的格同構(gòu).由定理二，a,b

A1,若ab,一、格的概念續(xù)證：設(shè)a,b

A1,ab

f(a)f(b).

定理三：設(shè)兩個(gè)格<A1,>和<A2,>,f是A1到A2的雙射，則f是格<A1,>到格<A2,>的格同構(gòu)，當(dāng)且僅當(dāng)a,b

A1,ab

f(a)f(b).

要證f是格<A1,>到格<A2,>的格同構(gòu)，即要證f(a1b