第七格与布尔代数PPT课件

.,1,本章将介绍其他的代数系统格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。,.,2,定义设为偏序集,BA,yA.(1)若x(xBxy)成立,则称y为B的上界;(2)若x(xByx)成立,则称y为B的下界;(3)令C=y|y为B的上界,若C有最小元，则称该最小元为B的最小上界或上确界,记为LUB(上确界)(4)令D=y|y为B的下界,若D有最大元，则称该最大元为为B的最大下界或下确界,记为GLB(下确界),复习偏序关系中的上界，下界，上确界与下确界,.,3,例：偏序集(2,3,5,7,14,15,21,/)，“/”为整除关系。其hasze图如下：2,7的最小上界、最大下界各为什么？2,3呢？5,14呢？,2,7的最小上界为14。最大下界无。2,3的最小上界无，最大下界无。5,14的最小上界无，最大下界无。,1格的概念,.,4,然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(1,2,3,4,6,8,12,24,/)：其Hasze图如下：,.,5,一、格,1定义：设是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称为格。其中上确界luba,b，记为ab,称为a和b的并。下确界glba,b，记为ab,称为a和b的交。将、，看作集合上的两个二元运算，故格所诱导的代数系统记作。,.,6,一、格,下述偏序集能构成格的是（？）,(a),(b),(c),(d),b,b,c,d,e,f,a,c,d,f,a,b,c,d,e,f,g,h,a,b,c,d,e,f,a,c,.,7,一、格,2、对偶格：若是一个偏序集，则也是一个偏序集，其中“”是“”的逆关系。若是一个格，则也是一个格，称这两个格互为对偶。若将关于格的命题中符号，、，分别用，、，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。,.,8,二、格的性质,定理1：若是一个格，则对任意a、b、cA，有（1）aab，bab（2）aba，abb（3）若ac且bc，则abc（4）若ca且cb，则cab,.,9,二、格的性质,（1）aab，bab证明：因ab=luba，b，它显然是a的一个上界，aab，同理：bab。（2）aba，abb证明：因ab=glba，b，它显然是a的一个下界，aba，同理：abb。,.,10,二、格的性质,（3）若ac且bc，则abc证明：ac且bc，由上界的定义知，c是a，b的一个上界，而ab是a，b的最小上界，abc。（4）若ca且cb，则cab证明：ca且cb，由下界的定义知，c是a，b的一个下界，而ab是a，b的最大下界，cab。,.,11,二、格的性质,推论：在中，对于任意a，b，cA，如果bc，则abac，abac。定理2：若是一个格，则对于任意a，bA，以下三个公式等价；（1）ab（2）ab=b（3）ab=a,.,12,二、格的性质,（1）ab（2）ab=b（3）ab=a证明：（1）（2）ab且偏序关系是自反的。bb，abb又bab成立ab=b（偏序关系是反对称的）设ab=baab成立，将ab=b代入aab得：ab类似可证（1）（3）,.,13,二、格的性质,定理3：是一个格，则对于任意a，b，cA，满足以下四个定律：（1）交换律：ab=baab=ba（2）吸收律：a（ab）=aa（ab）=a（3）结合律：a（bc）=（ab）c，a（bc）=（ab）c（4）等幂律：aa=aaa=a,.,14,二、格的性质,定理4：设有格，对于任意a，b，c，dA，如果ab和cd，则（1）acbd，（2）acbd证：bbd，dbd，而ab，cd，由传递性可得：abd，cbd，这就表明bd是a和c的一个上界，而ac是a和c的最小上界，必有acbd。类似地可以证明：acbd,.,15,二、格的性质,定理5：在一个格中，对于任意a，b，cA，有下列分配不等式成立：（1）a（bc）（ab）（ac）（2）a（bc）（ab）（ac）证：由定理1，（1）（2）知：aab和aac，可得：a（ab）（ac），又bcbab和bccacbc（ab）（ac）对于和，有：a（bc）（ab）（ac）利用对偶原理，即得：（ab）（ac）a（bc）,.,16,定义设是一个格，设非空集合S且SA,若对任意的a,bS,有abS,abS,则称S,是的子格。显然，子格必是格。而格的某个子集构成格，却不一定是子格。,三、子格,.,17,【例】设A,是一个格，其中A=a,b,c,d,e,其哈斯图如图所示。S1=a,b,c,d，S2=a,b,c,e,则S1,是A,是一个子格，S2,不是A,是一个子格，因为bc=dS2，S2,不是子格。,三、子格,.,18,2分配格,对格中的任意元素a,b,cA，必有a(bc)(ab)(ac)(ab)(ac)a(bc）当上述两式中等号成立的时候，就得到一类特殊的格。定义设是由格所诱导的代数系统。如果对任意的a,b,cA，满足：a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称是分配格。,.,19,例：判断图示的格是否是分配格a3（a4a5）=a3a1=a3（a3a4）（a3a5）=a4a6=a4所示的格不是分配格。,2分配格,.,20,2分配格,定理如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a(bc)(ab)(ac)(ab)(ac)=(ab)a)(ab)c)=a(ab)c)=a(ac)(bc)=(a(ac)(bc)=a(bc)即：并对交也是分配的。,.,21,2分配格,定理每个链均是分配格。证明：设是链。对任意a，b，cA(1)若ab或ac，则a(bc)a，(ab)(ac)a即：a(bc)(ab)(ac)(2)若ab且ac，则a(bc)bc，(ab)(ac)bc即：a(bc)(ab)(ac)。得证。,.,22,定理：设是一个分配格，则对于任意a，b，cA，如果有ab=ac和ab=ac成立，则必有b=c。,2分配格,证：（ab）c=（ac）c=c（ab）c=（ac）（bc）=（ab）（bc）=（ba）（bc）=b（ac）=b(ab)=bb=c,.,23,2分配格,定义设是由格所诱导的代数系统。如对A中任意a，b，c，当ba时，有：a(bc)b(ac)则称为模格。,.,24,2分配格,定理分配格是模格。证明：由于a(bc)(ab)(ac)若ba，则ab=b，代入上式得a(bc)b(ac)分配格是模格,.,25,3有补格,定义设是一个格，如果存在元素aA，对于任意的xA，都有：ax则称a为格的全下界，记格的全下界为0。定义设是一个格，如果存在元素bA，对于任意的xA，都有：xb则称b为格的全上界，记格的全上界为1。,.,26,3有补格,定理如果格有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b，则由定义ab，且ba，由“”的反对称性，ab。定义设是一个格，如果格中存在全上界和全下界，则称该格为有界格。,.,27,3有补格,定理如果是有界格，全上界和全下界分别是1和0，则对任意元素aA，有：a1=1a=1，a1=1a=a，a0=0a=a，a0=0a=0。证明：因为1a1，又因(a1)A且1是全上界，a11，a1=1。由交换律：1aa1=1。因为aa，a1，aaa1，即：aa1，又a1a，a1=a。仿此可得另两式。,.,28,3有补格,定义设是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1和ab=0，则称元素b是元素a的补元。讨论定义：（1）和是可交换的，补元是相互的。（2），即在有界格中，1和0互为补元；（3）由定义可知A中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。,.,29,3有补格,定义在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。,.,30,如图所示的格，是有补格吗？该格是有界格，却不是有补格。,3有补格,.,31,3有补格,定理在有界分配格中，若有一个元素有补元，则必是唯一的。证明：设a有两个补元素b和c,则有：ab=1,ab=0ac=1,ac=0所以ab=ac，ab=ac由定理知：b=c,.,32,4布尔代数,定义一个格如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。定义一个有补分配格称为布尔格。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义A上的一个一元运算，称为补运算，记为“-”。,-,.,33,4布尔代数,定义由布尔格，可以诱导一个包括交，并和补运算的代数系统，称此代数系统为布尔代数。例：设S是一个非空有限集，是一个格，且是一个布尔格。由所诱导的代数系统为是一个布尔代数。其中“,-”分别是集合的交、并、补运算。,.,34,4布尔代数,例：设A是一非空集合,(A)是A的幂集,可以验证,是个布尔代数,称此为集合代数,其中运算为,全下界,全上界A。,.,35,4布尔代数,定理对于布尔代数中任意两个元素a,b，必定有,.,36,定义：当布尔代数的载体A的基数|A|是有限数时,则称之为有限布尔代数。定义：设是一个布尔代数，aA,如果a盖住0，则称元素a是该布尔代数的