格与布尔代数

格与布尔代数2026/5/4第6章格与布尔代数集合的表示方法2子格3特殊格4偏序格与代数格1格的性质2布尔代数52026/5/46、1格得定义2026/5/4一、定义设<L,≼>就是一个偏序集,如果对任意a,b∈L,{a,b}都有最大下界与最小上界存在,则称<L,≼>就是格,简称L就是格。若L为有限集,则称格<L,≼>为有限格。2026/5/4用a∨b表示{a,b}得最小上界,用a∧

b表示{a,b}得最大下界∨读作“并”∧读作“交”2026/5/4例(1)Sn表示n得所有因子得集合,D就是一个整除关系,问此偏序集<Sn

,D>就是否就是一个格？(2)设A就是一个集合,P(A)就是A得幂集,

就是集合上得包含关系,问此偏序集<P(A),

>就是否就是一个格？定理(格得基本性质)设<L,≼>就是格,则运算∨与∧适合交换律、结合律、幂等律与吸收律,即(1)

a,b∈L

有

a∨b=b∨a,a∧b=b∧a(2)

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(4)

a,b∈L

有

a∨(a∧b)=a,a∧(a∨b)=a

定理(格得性质:序与运算得关系)设L就是格,则

a,b∈L有

a≼b

a∧b=a

a∨b=b定理(格得保序性)设L就是格,

a,b,c,d∈L,若a≼b且c≼d,则

a∧c≼b∧d,a∨c≼b∨d定理:设L就是格,

a,b,c∈L有

a∨(b∧c)≼(a∨b)∧(a∨c)、注意:一般说来,格中得∨与∧运算不满足分配律、大家有疑问的，可以询问和交流可以互相讨论下，但要小声点2026/5/4二、子格设(L,∧,∨)就是一个格,S就是L得一个子集,(S,∧,∨)称为(L,∧,∨)得一个子格,当且仅当在运算∧,∨下,S就是封闭得。

e

fg

bd

c

ah

例:S={a,b,c,d,e,f,g,h}构成格S1={a,b,d,f}与S2={c,e,g,h}与S3={a,b,c,d,e,g,h}都构成格但S3不就是S得子格对偶式:格中元素用运算符∧,∨连接起来得得一个表达式f,将f中得∧换成∨,将∨换成∧,如有0,1,将0换成1,将1换成0,所形成得表达式称为f得对偶表达式记作f*

。对偶原理:对于<L,R>中任一真命题,其对偶命题也真。三、格得同态与同构定义:设<A1,≼1>与<A2,≼2>就是两个格,它们分别诱导得代数系统为<A1,∧1,∨1>与<A2,∧2,∨2>,若存在一个从A1到A2得映射f,使得对于任意得a,b∈A1,有f(a∧1b)＝f(a)∧2f(b)f(a∨1b)＝f(a)∨2f(b)则称f就是从<A1,∧1,∨1>到<A2,∧2,∨2>得格同态。亦称<f(A1),≼2>就是<A1,≼1>得格同态象。当f就是双射得,则称f就是从<A1,∧1,∨1>到<A2,∧2,∨2>得格同构,亦称格<A1,≼1>与<A2,≼2>就是同构得。定理:设f就是格<A1,≼1>到<A2,≼2>格同态,则对任意得a,b∈A1,若a≼1b,必有f(a)≼2f(b)。定理:设<A1,≼1>与<A2,≼2>就是两个格,f就是从A1到A2双射,则f就是从<A1,≼1>到<A2,≼2>得格同构,当且仅当,对任意得a,b∈A1,a≼1b⇔f(a)≼2f(b)。2026/5/46、2、分配格设<L,∧,∨>就是格,若

a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)

a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格、2026/5/4例a(c)bcdea(b)bcde(a)2026/5/4例设A为任意一个集合,格<P(A),

>就是否就是分配格？2026/5/4定理1所有链都就是分配格。

定理2:

如果在一个格中交运算对并运算可分配,则并运算对交运算也就是可分配得。反之亦然。2026/5/4定理3一个格就是分配格得充分必要条件就是该格中没有任何子格与两个五元素格中得任何一个同构。定理4定理:

设格<L,∧,∨>就是分配格,对任意a,b,c∈L,如果a∧c＝b∧c,a∨c＝b∨c则有a＝b。证明:若<L,∧,∨>就是分配格,且a∧c＝b∧c,a∨c＝b∨c,则a＝a∧(a∨c)＝a∧(b∨c)＝(a∧b)∨(a∧c)＝(a∧b)∨(b∧c)＝b∧(a∨c)＝b∧(b∨c)＝b2026/5/4性质(1)四个元素以下得格都就是分配格;(2)五个元素得格仅有两个格就是非分配格,其余三个格(右图(a),(b)与(c))都就是分配格。(a)(a)abcde(b)abcde(c)abcde6、3有补格2026/5/4一、有界格1、设<L,≼>就是一个格,若存在元素a∈L,使得对任意x∈L,都有:a≼x,则称a为格<L,≼>得全下界,记为02、设<L,≼>就是一个格,若存在元素a∈L,使得对任意x∈L,都有:x≼a,则称a为格<L,≼>得全上界,记为13、具有全上界与全下界得格称为有界格。记为<L,∧,∨,0,1>例:定理:设<L,∧,∨,0,1>就是有界格,则

a∈L有

:a∧0=0,a∨0=a,a∧1=a,a∨1=1注意:(1)有限格L={a1,a2,…,an}就是有界格,a1∧a2∧…∧an就是L得全下界,a1∨a2∨…∨an就是L得全上界、(2)0就是关于∧运算得零元,∨运算得幺元;

1就是关于∨运算得零元,∧运算得幺元、(3)对于涉及到有界格得命题,如果其中含有全下界0或全上界1,在求该命题得对偶命题时,必须将0替换成1,而将1替换成0、2026/5/4定理在格<L,≼>中,全下界与全上界分别就是集合L得最小元与最大元,由于最大元与最小元得惟一性,有下面得定理:设<L,≼>就是一个格,若格<L,≼>得全上界与全下界存在,则必惟一。2026/5/4二、补元设<L,

,

>为有界格,1与0分别为它得全上界与全下界,a∈L。如果存在b∈L,使得a

b=0,a

b=1,则称b为a得补元,记为。2026/5/4例如下图有界格,求其所有元素得补元(如果有得话)。c0(b)db1

a0(a)deb1ac定理设<L,∧,∨,0,1>就是有界分配格、若L中元素a存在补元,则存在惟一得补元、证:假设c就是a得补元,则有

a∨c=1,a∧c=0,又知b就是a得补元,故

a∨b=1,a∧b=0从而得到a∨c=a∨b,a∧c=a∧b,

由于L就是分配格,b=c、三、有补格若有界格<L,

,

>中得所有元素都存在补元,则称<L,

,

>为有补格。2026/5/4四、有补分配格2026/5/4有补分配格:布尔格。由一个布尔格所诱导得一个代数系统可记为:<L,∧,∨,ˉ,0,1>。称为布尔代数。6、4布尔代数定义:一个有补分配格就是一个布尔代数,可记为<B,∧,∨,ˉ,0,1>。设<B,∧,∨,ˉ,0,1>就是一个布尔代数,a,b,c就是集合B中任意元素,于就是,它有如下性质:(1)因为<B,∧,∨>就是一个格,所以有

a∧a＝a

a∨a＝a

a∧b＝b∧a

a∨b＝b∨a(a∧b)∧c＝a∧(b∧c)(a∨b)∨c＝a∨(b∨c)

a∧(a∨b)＝a

a∨(a∧b)＝a(2)因为<B,∧,∨>就是分配格,所以有