第七格与布尔代数

第七格与布尔代数演示文稿1现在是1页\一共有36页\编辑于星期一（优选）第七格与布尔代数现在是2页\一共有36页\编辑于星期一3定义设<A,>为偏序集,BA,yA.(1)若x(xB→xy)成立,则称y为B的上界;(2)若x(xB→yx)成立,则称y为B的下界;(3)令C={y|y为B的上界},若C有最小元，则称该最小元为B的最小上界或上确界,记为LUB(上确界)(4)令D={y|y为B的下界},若D有最大元，则称该最大元为为B的最大下界或下确界,记为GLB(下确界)

复习偏序关系中的上界，下界，上确界与下确界现在是3页\一共有36页\编辑于星期一4例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”为整除关系。其hasze图如下：｛2,7｝的最小上界、最大下界各为什么？｛2,3｝呢？｛5,14｝呢？｛2,7｝的最小上界为14。最大下界无。｛2,3｝的最小上界无，最大下界无。｛5,14｝的最小上界无，最大下界无。§1格的概念

现在是4页\一共有36页\编辑于星期一5然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze图如下：现在是5页\一共有36页\编辑于星期一6一、格1．定义：设<A,≤>是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称 <A,≤>为格。其中上确界lub{a,b}，记为a∨b,称为a和b的并。下确界glb{a,b}，记为a∧b,称为a和b的交。将∨、∧，看作集合上的两个二元运算，故格<A,≤>所诱导的代数系统记作<A，∨，∧>。现在是6页\一共有36页\编辑于星期一7一、格下述偏序集能构成格的是（？）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac现在是7页\一共有36页\编辑于星期一8一、格2、对偶格：若<A,≤>是一个偏序集，则<A,≥>也是一个偏序集，其中“≥”是“≤”的逆关系。若<A,≤>是一个格，则<A,≥>也是一个格，称这两个格互为对偶。若将关于格<A,≤>的命题中符号≤，≥，∨、∧，分别用≥，≤，∧、∨，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。

现在是8页\一共有36页\编辑于星期一9二、格的性质定理1：若<A，≤>是一个格，则对任意a、b

、cA，有（1）a≤a∨b，b≤a∨b

（2）a∧b≤a，a∧b≤b（3）若a≤c且b≤c，则a∨b≤c（4）若c≤a且c≤b，则c≤a∧b现在是9页\一共有36页\编辑于星期一10二、格的性质（1）a≤a∨b，b≤a∨b

证明：因a∨b=lub{a，b}，它显然是a的一个上界，∴a≤a∨b

，同理：b≤a∨b。（2）a∧b≤a，a∧b≤b证明：因a∧b=glb{a，b}，它显然是a的一个下界，∴a∧b≤a

，同理：a∧b≤b。现在是10页\一共有36页\编辑于星期一11二、格的性质（3）若a≤c且b≤c，则a∨b≤c

证明：∵a≤c且b≤c，由上界的定义知，c是{a，b}的一个上界，而a∨b是{a，b}的最小上界，∴a∨b≤c。（4）若c≤a且c≤b，则c≤a∧b证明：∵c≤a且c≤b，由下界的定义知，c是{a，b}的一个下界，而a∧b是{a，b}的最大下界，∴c≤a∧b。

现在是11页\一共有36页\编辑于星期一12二、格的性质推论：在<A，≤>中，对于任意a，b

，cA，如果b≤c，则a∨b≤a∨c，a∧b≤a∧c。定理2：若<A，≤>是一个格，则对于任意a，bA，以下三个公式等价；（1）a≤b

（2）a∨b=b

（3）a∧b=a现在是12页\一共有36页\编辑于星期一13二、格的性质（1）a≤b

（2）a∨b=b

（3）a∧b=a证明：（1）（2）∵a≤b且偏序关系是自反的。∴b≤b，∴

a∨b≤b

又

b≤a∨b成立∴a∨b=b（偏序关系是反对称的）设a∨b=b

∵a≤a∨b成立，将a∨b=b代入a≤a∨b得：a≤b

类似可证（1）（3）现在是13页\一共有36页\编辑于星期一14二、格的性质定理3：<A，≤>是一个格，则对于任意a，b，cA，满足以下四个定律：（1）交换律：a∨b=b∨a

a∧b=b∧a（2）吸收律：a∨（a∧b）=aa∧（a∨b

）=a（3）结合律：a∨（b∨c）=（a∨b）∨c，

a∧（b∧c）=（a∧b

）∧c（4）等幂律：a∨a=a

a∧a=a现在是14页\一共有36页\编辑于星期一15二、格的性质定理4：设有格<A，≤>，对于任意a，b，c，dA，如果a≤b和c≤d，则（1）a∨c≤b∨d，（2）a∧c≤b∧d证：∵b≤b∨d，d≤b∨d

，而a≤b，c≤d，∴由传递性可得：a≤b∨d

，c≤b∨d，这就表明b∨d是a和c的一个上界，而a∨c是a和c的最小上界，∴必有a∨c≤b∨d。类似地可以证明：a∧c≤b∧d

现在是15页\一共有36页\编辑于星期一16二、格的性质定理5：在一个格<A，≤>中，对于任意a，b，cA，有下列分配不等式成立：（1）a∨（b∧c）≤（a∨b）∧（a∨c）（2）a∧（b∨c）≥（a∧b）∨（a∧c）证：由定理1，（1）（2）知：a≤a∨b和a≤a∨c，可得：

a≤（a∨b）∧（a∨c），①又∵b∧c≤b≤a∨b和b∧c≤c≤a∨c∴b∧c≤（a∨b）∧（a∨c）②对于①和②，有：a∨（b∧c）≤（a∨b）∧（a∨c）利用对偶原理，即得：（a∧b）∨（a∧c）≤a∧（b∨c）

现在是16页\一共有36页\编辑于星期一17定义设<A，≤>是一个格，设非空集合S且S

A,若对任意的a,b∈S,有a∧b∈S,a∨b∈S,则称〈S,≤〉是<A，≤>的子格。显然，子格必是格。而格的某个子集构成格，却不一定是子格。三、子格现在是17页\一共有36页\编辑于星期一18【例】设〈A,≤〉是一个格，其中A={a,b,c,d,e},其哈斯图如图所示。S1={a,b,c,d}，S2={a,b,c,e},则〈S1,≤〉是〈A,≤〉是一个子格，〈S2,≤〉不是〈A,≤〉是一个子格，因为b∧c=d∈S2，〈S2,≤〉不是子格。三、子格现在是18页\一共有36页\编辑于星期一19§2分配格

对格<A,≤>中的任意元素a,b,cA，必有a(bc)≤(ab)(ac)(ab)(ac)≤a(bc）当上述两式中等号成立的时候，就得到一类特殊的格。《定义》设<A,,>是由格<A,≤>所诱导的代数系统。如果对任意的a,b,cA，满足：

a(bc)=(ab)(ac)a(bc)=(ab)(ac)

则称<A,≤>是分配格。现在是19页\一共有36页\编辑于星期一20例：判断图示的格是否是分配格

∵a3∧（a4∨a5）=a3∧a1=a3

（a3∧a4）∨（a3∧a5）=a4∨a6=a4

∴所示的格不是分配格。

§2分配格

现在是20页\一共有36页\编辑于星期一21§2分配格《定理》如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a(bc)＝(ab)(ac)

(ab)(ac)=((ab)a)((ab)c) =a((ab)c) =a((ac)(bc)) =(a(ac))(bc) =a(bc)即：并对交也是分配的。现在是21页\一共有36页\编辑于星期一22§2分配格《定理》每个链均是分配格。证明：设<A,≤>是链。对任意a，b，cA(1)若a≤b或a≤c，则a(bc)＝a，

(ab)(ac)＝a即：a(bc)＝(ab)(ac)(2)若a≥b且a≥c，则

a(bc)＝bc，

(ab)(ac)＝bc即：a(bc)＝(ab)(ac)。得证。现在是22页\一共有36页\编辑于星期一23定理：设<A，≤

>是一个分配格，则对于任意a，b，cA，如果有a∧b=a∧c和a∨b=a∨c成立，则必有b=c。§2分配格

证：∵（a∧b）∨c=（a∧c）∨c=c（a∧b）∨c=（a∨c）∧（b∨c）=（a∨b）∧（b∨c）=（b∨a）∧（b∨c）=b∨（a∧c）=b∨(a∧b)=b∴b=c

现在是23页\一共有36页\编辑于星期一24§2分配格《定义》设<A,,>是由格<A,≤>所诱导的代数系统。如对A中任意a，b，c，当b≤a时，有：

a(bc)＝b(ac)则称<A,≤>为模格。现在是24页\一共有36页\编辑于星期一25§2分配格《定理》分配格是模格。证明：由于a(bc)＝(ab)(ac)若b≤a，则ab=b，代入上式得

a(bc)＝b(ac)

∴分配格是模格现在是25页\一共有36页\编辑于星期一26§3有补格《定义》设<A,≤>是一个格，如果存在元素aA，对于任意的xA，都有：a≤x

则称a为格<A,≤>的全下界，记格的全下界为0。《定义》设<A,≤>是一个格，如果存在元素bA，对于任意的xA，都有：x≤b

则称b为格<A,≤>的全上界，记格的全上界为1。现在是26页\一共有36页\编辑于星期一27§3有补格《定理》如果格<A,≤>有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b，则由定义

a≤b，且b≤a，由“≤”的反对称性，a＝b。《定义》设<A,≤>是一个格，如果格中存在全上界和全下界，则称该格为有界格。现在是27页\一共有36页\编辑于星期一28§3有补格《定理》如果<A,≤>是有界格，全上界和全下界分别是1和0，则对任意元素aA，有：

a1=1a=1，a1=1a=a，

a0=0a=a，a0=0a=0。证明：因为1≤a1， 又因(a1)A且1是全上界，∴a1≤1，

∴a1=1。由交换律：1a＝a1=1。 因为a≤a，a≤1，∴aa≤a1，即：a≤a1，又a1≤a，∴a1=a。仿此可得另两式。现在是28页\一共有36页\编辑于星期一29§3有补格《定义》设<A,≤>是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1和ab=0，则称元素b是元素a的补元。讨论定义：（1）∵和是可交换的，∴补元是相互的。

（2）

，即在有界格中，1和0互为补元；

（3）由定义可知A中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。现在是29页\一共有36页\编辑于星期一30§3有补格《定义》在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。现在是30页\一共有36页\编辑于星期一31如图所示的格，是有补格吗？该格是有界格，却不是有补格。§3有补格现在是31页\一共有36页\编辑于星期一32§3有补格《定理》在有界分配格中，若有一个元素有补元，则