第六格与布尔代数

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

b表示{a,b}的最大下界∨读作“并”∧读作“交”现在是6页\一共有42页\编辑于星期二现在是7页\一共有42页\编辑于星期二2023/4/24例（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页\编辑于星期二2023/4/24二、子格设(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页\编辑于星期二2023/4/246.2.分配格设<L,∧,∨>是格,若a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.现在是19页\一共有42页\编辑于星期二2023/4/24例a(c)bcdea(b)bcde(a)现在是20页\一共有42页\编辑于星期二2023/4/24例设A为任意一个集合，格<P(A),>是否是分配格？现在是21页\一共有42页\编辑于星期二2023/4/24定理1所有链都是分配格。

现在是22页\一共有42页\编辑于星期二定理2：

如果在一个格中交运算对并运算可分配，则并运算对交运算也是可分配的。反之亦然。现在是23页\一共有42页\编辑于星期二2023/4/24定理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页\编辑于星期二2023/4/24性质（1）四个元素以下的格都是分配格；（2）五个元素的格仅有两个格是非分配格，其余三个格(右图(a),(b)和(c))都是分配格。(a)(a)abcde(b)abcde(c)abcde现在是27页\一共有42页\编辑于星期二6.3有补格现在是28页\一共有42页\编辑于星期二2023/4/24一、有界格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页\编辑于星期二2023/4/24定理在格<L,≼>中，全下界和全上界分别是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：设<L,≼>是一个格，若格<L,≼>的全上界和全下界存在，则必惟一。现在是33页\一共有42页\编辑于星期二2023/4/24二、补元设<L,,>为有界格，1和0分别为它的全上界和全下界，a∈L。如果存在b∈L，使得ab=0，ab=1，则称b为a的补元，记为。现在是34页\一共有42页\编辑于星期二2023/4/24例如下图有界格，求其所有元素的补元(如果有的话)。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页\编辑于星期二2023/4/24四、有补分配格现在是38页\一共有42页\编辑于星期二2023/4/24有补分配格：布尔格。由一个布尔格所诱导的一个代数系统可记为：<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,∧,∨>是分配格，所以有

a∧(b∨c)＝(a∧b)∨(a∧c)a∨(b∧c)＝(a∨b)∧(a∨c)（3）因为<B,∧,∨,0,1>是有界格，所以有

a∧0＝0a∨1＝