离散数学第六章格与布尔代数精.ppt

离散数学第六章格与布尔代数离散数学第六章格与布尔代数1第1页，本讲稿共47页6.1 格的概念格的概念n本章将介绍其他的代数系统本章将介绍其他的代数系统格和布尔代数，格论是数格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。辑、集合等运算有关的知识。2第2页，本讲稿共47页定义定义 设设为偏序集为偏序集,B A,y A.(1)若若 x(x Bx y)成立成立,则称则称y为为B的上界的上界;(2)若若 x(x By x)成立成立,则称则称y为为B的下界的下界;(3)令令C=y|y为为B的上界的上界,若若 C 有最小元素，有最小元素，则称该最小元素为则称该最小元素为 B 的的最小上界或上确界最小上界或上确界,记为记为LUB(上确界上确界)(4)令令D=y|y为为B的下界的下界,若若 D 有最大元素，有最大元素，则称该最大元素为则称该最大元素为为为B的最大下界或下确界的最大下界或下确界,记为记为GLB(下确界下确界)复习偏序关系中的上界，下界，复习偏序关系中的上界，下界，上确界与下确界上确界与下确界3第3页，本讲稿共47页6.1 格的概念格的概念n例：偏序集例：偏序集(2,3,5,7,14,15,21,/)，“/”为整除关为整除关系。系。其其hasze图如下：图如下：2,7的最小上界、最大下的最小上界、最大下界各为什么？界各为什么？2,3呢？呢？5,14呢？呢？2,7的最小上界为的最小上界为14。最大下界无。最大下界无。2,3的最小上界无，最大下界无。的最小上界无，最大下界无。5,14的最小上界无，最大下界无。的最小上界无，最大下界无。4第4页，本讲稿共47页n然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集下界，如：偏序集(1,2,3,4,6,8,12,24,/)：其：其Hasze图如下：图如下：6.1 格的概念格的概念5第5页，本讲稿共47页一、格一、格1定义：设定义：设是一个偏序集，若对是一个偏序集，若对A中的任两个元素中的任两个元素a、b，都有，都有最小上界和最大下界，则称最小上界和最大下界，则称为格。为格。n其中上确界其中上确界 lub a,b，记为，记为ab,称为称为a和和b的并。的并。下确界下确界 glb a,b，记为，记为ab,称为称为a和和b的交。的交。n将将、，看作集合上的两个二元运算，故格，看作集合上的两个二元运算，故格所诱导的代数系所诱导的代数系统记作统记作。6第6页，本讲稿共47页一、格一、格下述偏序集能构成格的是（下述偏序集能构成格的是（？）？）(a)(b)(c)(d)bbcdefacdfabcdefghabcdefac7第7页，本讲稿共47页一、格一、格2、对偶格：、对偶格：若若是一个偏序集，则是一个偏序集，则也是一个偏也是一个偏序集，其中序集，其中“”是是“”的逆关系。的逆关系。若若是一个格，则是一个格，则也是一个格，称这两个格互为也是一个格，称这两个格互为对偶。对偶。若将关于格若将关于格的命题中符号的命题中符号，、，分别用，分别用，、，代替，则得到一个新的命题，称这个新，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。定理：对于格中的一个真命题，其对偶命题亦真。8第8页，本讲稿共47页二、格的性质二、格的性质定理定理1：若：若是一个格，则对任意是一个格，则对任意a、b、c A，有，有（1）aab，bab （2）aba，abb（3）若若ac且且bc，则，则abc（4）若若ca且且cb，则，则cab9第9页，本讲稿共47页二、格的性质二、格的性质（1）aab，bab 证明：因证明：因ab=luba，b，它显然是，它显然是 a 的一个上界，的一个上界，aab，同理：，同理：bab。（2）aba，abb证明：因证明：因ab=glba，b，它显然是，它显然是 a 的一个下界，的一个下界，aba，同理：，同理：abb。10第10页，本讲稿共47页二、格的性质二、格的性质（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第11页，本讲稿共47页二、格的性质二、格的性质推论：推论：在在中，对于任意中，对于任意a，b，c A，如果如果bc，则，则 abac，abac。n定理定理2：若若是一个格，则对于任意是一个格，则对于任意a，b A，以下三个公式等价；，以下三个公式等价；（1）ab （2）ab=b （3）ab=a12第12页，本讲稿共47页二、格的性质二、格的性质（1）ab （2）ab=b （3）ab=a证明：证明：（1）（2）ab 且偏序关系是自反的。且偏序关系是自反的。bb，abb 又又 bab成立成立 ab=b（偏序关系是反对称的）（偏序关系是反对称的）设设ab=b aab成立，将成立，将ab=b代入代入aab得：得：ab 类似可证（类似可证（1）（3）13第13页，本讲稿共47页二、格的性质二、格的性质定理定理3：是一个格，则对于任意是一个格，则对于任意a，b，c A，满足以下四个定，满足以下四个定律：律：（1）交换律：）交换律：ab=ba ab=ba（2）吸收律：）吸收律：a（ab）=a a（ab）=a（3）结合律：）结合律：a（bc）=（ab）c，a（bc）=（ab）c（4）等幂律：）等幂律：aa=a aa=a14第14页，本讲稿共47页二、格的性质二、格的性质定理定理4：设有格设有格，对于任意，对于任意a，b，c，d A，如果，如果ab和和cd，则，则（1）acbd，（2）acbd证：证：bbd，dbd ，而而ab，cd，由传递性可得：由传递性可得：abd，cbd，这就表明这就表明bd是是a和和c的一个上界，而的一个上界，而ac是是a和和c的最小上界，的最小上界，必有必有acbd。类似地可以证明：类似地可以证明：acbd 15第15页，本讲稿共47页二、格的性质二、格的性质定理定理5：在一个格在一个格中，对于任意中，对于任意a，b，c A，有下列分配不，有下列分配不等式成立：等式成立：（1）a（bc）（ab）（ac）（2）a（bc）（ab）（ac）证：证：由定理由定理1，（，（1）（）（2）知：）知：aab和和aac，可得：，可得：a（ab）（ac），），又又 bc bab和和 bccac bc（ab）（ac）对于对于和和，有：，有：a（bc）（ab）（ac）利用对偶原理，即得：（利用对偶原理，即得：（ab）（ac）a（bc）16第16页，本讲稿共47页n定义定义 设是一个格，设非空集合S且S A,若对任意的a,bS,有abS,abS,则称S,是的子格。n显然，子格必是格。而格的某个子集构成格，却不一定是子格。三、子格三、子格17第17页，本讲稿共47页n【例例】设设A,是一个格，其中是一个格，其中A=a,b,c,d,e,其哈斯图如图所示。其哈斯图如图所示。S1=a,b,c,d，S2=a,b,c,e,则则S1,是是A,是一是一个子格，个子格，nS2,不是不是A,是一个子格，因为是一个子格，因为b c=d S2，S2,不是子格。不是子格。三、子格三、子格18第18页，本讲稿共47页n 定义：设 A1,A2,是两个格,由它们所诱导的代数系统为A1,1,1,A2,2,2，如果存在映射f:A1 A2,任意a,b A1，满足：f(a 1 b)=f(a)2 f(b),f(a 1 b)=f(a)2 f(b)称f为A1,1,1 到A2,2,2 的格同态。若f是双射，则称f为格同构，亦称 A1,A2,这两个格是同构。四、格同态与格同构四、格同态与格同构n类似群的同态，也可以定义格的同态。类似群的同态，也可以定义格的同态。19第19页，本讲稿共47页定理：设定理：设f是格是格 A1,1 到到 A2,2的格同态，的格同态，则对任意的则对任意的x,y A1，如果，如果x 1 y，必有，必有f(x)2 f(y)。这说明格的同态是保序的。这说明格的同态是保序的。定理：设两个格为定理：设两个格为 A1,1，A2,2，f是从是从 A1到到 A2的的双射，则的的双射，则 f是是 A1,1 到到 A2,2是格同构，当且仅当对任意的是格同构，当且仅当对任意的x,y A1，如果，如果x 1 y f(x)2 f(y)。四、格同态与格同构四、格同态与格同构20第20页，本讲稿共47页6.26.2分配格分配格对格中的任意元素a,b,cA，必有a (b c)(a b)(a c)(a b)(a c)a(b c）当上述两式中等号成立的时候，就得到一类特殊的格。定义定义设是由格所诱导的代数系统。如果对任意的a,b,cA，满足：a (b c)=(a b)(a c)a(b c)=(a b)(a c)则称是分配格。21第21页，本讲稿共47页例：例：判断图示的格是否是分配格判断图示的格是否是分配格 a3（a4a5）=a3a1=a3 （a3a4）（a3a5）=a4a6=a4 所示的格不是分配格。所示的格不是分配格。6.2分配格分配格22第22页，本讲稿共47页6.26.2分配格分配格定理定理如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a (b c)(a b)(a c)(a b)(a c)=(a b)a)(a b)c)=a (a b)c)=a(a c)(b c)=(a (a c)(b c)=a (b c)即：并对交也是分配的。23第23页，本讲稿共47页6.26.2分配格分配格定理定理每个链均是分配格。证明：设是链。对任意a，b，cA(1)若ab或ac，则 a (b c)a，(a b)(a c)a即：a (b c)(a b)(a c)(2)若ab且ac，则 a (b c)b c，(a b)(a c)b c即：a (b c)(a b)(a c)。得证。24第24页，本讲稿共47页定理：定理：设设是一个分配格，则对于任意是一个分配格，则对于任意a，b，c A，如，如果有果有ab=ac和和ab=ac成立，则必有成立，则必有b=c。6.2分配格分配格证：证：（ab）c=（ac）c=c（ab）c=（ac）（bc）=（ab）（bc）=（ba）（bc）=b（ac）=b(ab)=b b=c 25第25页，本讲稿共47页6.26.2分配格分配格定义定义设是由格所诱导的代数系统。如对A中任意a，b，c有：baa (b c)b (a c)则称为模格。26第26页，本讲稿共47页6.26.2分配格分配格定理定理分配格是模格。证明：由于a (b c)(a b)(a c)若ba，则a b=b，代入上式得 a (b c)b (a c)分配格是模格27第27页，本讲稿共47页6.36.3有补格有补格定义定义设是一个格，如果存在元素aA，对于任意的x A，都有：ax 则称a为格的全下界，记格的全下界为0。定义定义设是一个格，如果存在元素bA，对于任意的x A，都有：xb 则称b为格的全上界，记格的全上界为1。28第28页，本讲稿共47页6.36.3有补格有补格定理定理如果格有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b，则由定义 ab，且ba，由“”的反对称性，ab。定义定义设是一个格，如果格中存在全上界和全下界，则称该格为有界格。29第29页，本讲稿共47页6.36.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，a aa 1，即：aa 1，又 a1a，a1=a。仿此可得另两式。30第30页，本讲稿共47页6.36.3有补格有补格定义定义设是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1和ab=0，则称元素b是元素a的补元。讨论定义：（1）和是可交换的，补元是相互的。（2），即在有界格中，1和0互为补元；（3）由定义可知A中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。31第31页，本讲稿共47页6.36.3有补格有补格定义定义在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。32第32页，本讲稿共47页如图所示的格，是有补格吗？如图所示的格，是有补格吗？该格是有界格，却不是有补格。该格是有界格，却不是有补格。6.3有补格有补格33第33页，本讲稿共47页6.36.3有补格有补格定理定理在有界分配格中，若有一个元素有补元，则必是唯一的。证明：设a有两个补元素b和c,则有：ab=1,ab=0 ac=1,ac=0所以ab=ac，ab=ac由定理知：b=c34第34页，本讲稿共47页有补分配格有补分配格n定义：一个格如果既是有补格，又是分配格，则称该格为有补分定义：一个格如果既是有补格，又是分配格，则称该格为有补分配格，配格，可以证明：在有补分配格中，任一元素的补元都是可以证明：在有补分配格中，任一元素的补元都是唯一唯一的。的。将有补分配格中任一元素将有补分配格中任一元素a的的唯一唯一补元记为补元记为a6.3有补格有补格35第35页，本讲稿共47页6.4 布尔代数定义定义一个格如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。定义定义一个有补分配格称为布尔格。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义A上的一个一元运算，称为补运算，记为“-”。-36第36页，本讲稿共47页6.4 布尔代数定义定义由布尔格，可以诱导一个 包括交，并和补运算的代数系统，称此代数系统为布尔代数。例：设S是一个非空有限集，是一个格，且是一个布尔格。由所诱导的代数系统为 是一个布尔代数。其中“,-”分别是集合的交、并、补运算。37第37页，本讲稿共47页6.4 布尔代数例：设A是一非空集合,(A)是A的幂集,可以验证,是个布尔代数,称此为集合代数,其中运算为,全下界,全上界A。S是命题公式的全体,则是一个布尔代数,称之为命题代数。其中运算为,全下界是恒假公式0,全上界是恒真公式1。38第38页，本讲稿共47页6.4 布尔代数定理定理对于布尔代数中任意两个元素a,b，必定有39第39页，本讲稿共47页定义：定义：当布尔代数的载体A的基数|A|是有限数时,则称之为有限布尔代数。定义：定义：设是一个布尔代数，aA,如果a盖住0，则称元素a是该布尔代数的一个原子原子。6.4 布尔代数定义：定义：布尔代数中除0外的每个元素，都可以唯一地表示成原子的并。例如：40第40页，本讲稿共47页6.4 布尔代数例：，其中S=a,b,c，在这个布尔代数中的元素分三种情况：（）界：全上界S，全下界；（）a,b,c单个元素集合的元素；（）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：a,b=ab,a,c=ac,b,c=bc,a,b,c=abc。a,ca,b,ca,bb,cacb41第41页，本讲稿共47页6.4 布尔代数定理定理设是由有限布尔格所诱导的一个有限布尔代数，S是布尔格中的所有原子的集合，则和同构。42第42页，本讲稿共47页6.4 布尔代数该定理可得以下两个推论：该定理可得以下两个推论：a)与与同同构，构，|p(S)|=2|s|所以，所以，|B|=2|s|，故任，故任一有限布尔代数载体的基数是一有限布尔代数载体的基数是2的幂。的幂。b)任一有限布尔代数和它的原子集合任一有限布尔代数和它的原子集合S构成的构成的幂集集合代数幂集集合代数同构，同构，但后者又与任一基数相同的幂集集合代数同但后者又与任一基数相同的幂集集合代数同构，故具有相同载体基数的有限布尔代数都构，故具有相同载体基数的有限布尔代数都同构。同构。43第43页，本讲稿共47页第三篇小结第三篇小结通过本篇的学习应该达到以下基本要求：(1)给定集合与运算的解析表达式，写出该运算的运算表。(2)给定集合和运算，判别该集合对运算是否封闭。(3)给定二元运算，说明运算是否满足交换律、结合律、幂等律、分配律和吸收律。(4)给定集合S上的二元运算，求出该运算的幺元、零元、幂等元和所有可逆元素的逆元。(5)给定集合S和二元运算*，能判定是否构成半群、独异点和群。44第44页，本讲稿共47页第三篇小结第三篇小结(6)给定半群S和子集B，判定B是否为S的子半群；给定独异点V和子集B，判定B是否为V的子独异点，给定群G和子集H，判定H是否为G的子群。(7)求循环群的所有生成元。(8)给定代数系统V1=，V2=，其中“”和”*“为二元运算，判定：S1 S2是否为V1到V2的同态映射。如果是，说明是否为单同态、满同态和同构，并求出同态象(V1)。(9)判别格、分配格、有界格、有补格和布尔格。求有界格的全上界、全下界和给定元素的补元。45第45页，本讲稿共47页例题选讲例题选讲例1.设：Sa,b，则S上可以定义多少个二元运算？其中有4个运算如下表所示，则有哪些满足交换律，哪些满足幂等律，哪些有幺元，哪些有零元？1abaaabaa2abaabbba3abababaa4abaabb ab46第46页，本讲稿共47页例题选讲例题选讲例2.对以下定义的集合和运算判别它们能否构成代数系统？如能，请说明是构成哪一种代数系统？(1)，为普通加法；(2)，*为普通乘法；(3)，为小于等于关系；47第47页，本讲稿共47页