第六格与布尔代数

第六格与布尔代数演示文稿第1页，共42页。（优选）第六格与布尔代数第2页，共42页。2025/7/29第6章格与布尔代数集合的表示方法2子格3特殊格4偏序格与代数格1格的性质2布尔代数5第3页，共42页。2025/7/296.1格的定义第4页，共42页。2025/7/29一、定义设<L,≼>是一个偏序集，如果对任意a,b∈L，{a,b}都有最大下界和最小上界存在，则称<L,≼>是格，简称L是格。若L为有限集，则称格<L,≼>为有限格。第5页，共42页。2025/7/29用a∨b表示{a,b}的最小上界，用a∧

b表示{a,b}的最大下界∨读作“并”∧读作“交”第6页，共42页。第7页，共42页。2025/7/29例（1）Sn表示n的所有因子的集合，D是一个整除关系，问此偏序集<Sn

，D>是否是一个格？（2）设A是一个集合，P(A)是A的幂集，

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

>是否是一个格？第8页，共42页。定理(格的基本性质)设<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

第9页，共42页。定理（格的性质：序与运算的关系）设L是格,则

a,b∈L有

a≼b

a∧b=a

a∨b=b第10页，共42页。定理（格的保序性）设L是格,

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

a∧c≼b∧d,a∨c≼b∨d第11页，共42页。定理：设L是格,

a,b,c∈L有

a∨(b∧c)≼(a∨b)∧(a∨c).注意：一般说来,格中的∨和∧运算不满足分配律.

第12页，共42页。2025/7/29二、子格设(L,∧,∨)是一个格，S是L的一个子集，(S,∧,∨)称为(L,∧,∨)的一个子格，当且仅当在运算∧,∨下，S是封闭的。第13页，共42页。

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的子格第14页，共42页。对偶式：格中元素用运算符∧,∨连接起来的的一个表达式f，将f中的∧换成∨，将∨换成∧，如有0，1，将0换成1，将1换成0，所形成的表达式称为f的对偶表达式记作f*

。对偶原理:对于<L,R>中任一真命题,其对偶命题也真。第15页，共42页。三、格的同态与同构定义：设<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>是同构的。第16页，共42页。定理：设f是格<A1,≼1>到<A2,≼2>格同态，则对任意的a，b∈A1，若a≼1b，必有f(a)≼2f(b)。第17页，共42页。定理：设<A1,≼1>和<A2,≼2>是两个格，f是从A1到A2双射，则f是从<A1,≼1>到<A2,≼2>的格同构，当且仅当，对任意的a，b∈A1，a≼1b⇔f(a)≼2f(b)。第18页，共42页。2025/7/296.2.分配格设<L,∧,∨>是格,若

a,b,c∈L,有

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

a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.第19页，共42页。2025/7/29例a(c)bcdea(b)bcde(a)第20页，共42页。2025/7/29例设A为任意一个集合，格<P(A),

>是否是分配格？第21页，共42页。2025/7/29定理1所有链都是分配格。

第22页，共42页。定理2：

如果在一个格中交运算对并运算可分配，则并运算对交运算也是可分配的。反之亦然。第23页，共42页。2025/7/29定理3一个格是分配格的充分必要条件是该格中没有任何子格与两个五元素格中的任何一个同构。第24页，共42页。定理4定理:

设格<L,∧,∨>是分配格，对任意a,b,c∈L，如果a∧c＝b∧c，a∨c＝b∨c则有a＝b。第25页，共42页。证明：若<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)＝b第26页，共42页。2025/7/29性质（1）四个元素以下的格都是分配格；（2）五个元素的格仅有两个格是非分配格，其余三个格(右图(a),(b)和(c))都是分配格。(a)(a)abcde(b)abcde(c)abcde第27页，共42页。6.3有补格第28页，共42页。2025/7/29一、有界格1.设<L,≼>是一个格，若存在元素a∈L，使得对任意x∈L，都有：a≼x，则称a为格<L,≼>的全下界，记为02.设<L,≼>是一个格，若存在元素a∈L，使得对任意x∈L，都有：x≼a，则称a为格<L,≼>的全上界，记为13.具有全上界和全下界的格称为有界格。记为<L,∧,∨,0,1>第29页，共42页。例：第30页，共42页。定理：设<L,∧,∨,0,1>是有界格,则

a∈L有

：a∧0=0,a∨0=a,a∧1=a,a∨1=1第31页，共42页。注意：（1）有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是L的全上界.（2）0是关于∧运算的零元,∨运算的幺元；

1是关于∨运算的零元,∧运算的幺元.（3）对于涉及到有界格的命题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,必须将0替换成1,而将1替换成0.第32页，共42页。2025/7/29定理在格<L,≼>中，全下界和全上界分别是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：设<L,≼>是一个格，若格<L,≼>的全上界和全下界存在，则必惟一。第33页，共42页。2025/7/29二、补元设<L,

,

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

b=0，a

b=1，则称b为a的补元，记为。第34页，共42页。2025/7/29例如下图有界格，求其所有元素的补元(如果有的话)。c0(b)db1

a0(a)deb1ac第35页，共42页。定理设<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.第36页，共42页。三、有补格若有界格<L,

,

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

,

>为有补格。第37页，共42页。2025/7/29四、有补分配格第38页，共42页。2025/7/29有补分配格：布尔格。由一个布尔格所诱导的一个代数系统可记为：<L,∧,∨,ˉ,0,1>。称为布尔代数。第39页，共42页。6.4布尔代数定义：一个有补分配格是一个布尔代数，可记为<B,∧,∨,ˉ,0,1>。第40页，共42页。设<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,∧,