离散数学课件第七章(第1讲).ppt

本章将介绍其他的代数系统本章将介绍其他的代数系统格和布尔代数，格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在布尔代数形成比较早，在19世纪，就已经有了相世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。有关的知识。n7.1 格的概念格的概念n7.2 分配格分配格n7.3 有补格有补格n7.4 布尔代数布尔代数第七章第七章 格与布尔代数格与布尔代数7.1 格的概念格的概念 例：偏序集例：偏序集(2,3,5,7,14,15,21,/)，“/”为整除关系。为整除关系。其其hasze图如下：图如下：2,7的最小上界、最大下界各为什的最小上界、最大下界各为什么？么？2,3呢？呢？5,14呢？呢？2,7的最小上界为的最小上界为14。最大下界无。最大下界无。2,3的最小上界无，最大下界无。的最小上界无，最大下界无。5,14的最小上界无，最大下界无。的最小上界无，最大下界无。然而也存在这样一类偏序集，它的每一对元素都有最小上界然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集和最大下界，如：偏序集(1,2,3,4,6,8,12,24,/)：其：其Hasze图图如下：如下：1、格、格 定义：设定义：设是一个偏序集，若对是一个偏序集，若对A中的任两个元素中的任两个元素a、b，都有最小上界和最大下界，则称，都有最小上界和最大下界，则称为格。为格。其中上确界其中上确界 lub a,b，记为，记为ab,称为称为a和和b的并。的并。下确界下确界 glb a,b，记为，记为ab,称为称为a和和b的交。的交。将将、，看作集合上的两个二元运算，故格，看作集合上的两个二元运算，故格所诱所诱导的代数系统记作导的代数系统记作。例：下述偏序集能构成格的是（例：下述偏序集能构成格的是（）(a)(b)(c)(d)bbcdefacdfabcdefghabcdefac2、对偶格 对偶格：若对偶格：若是一个偏序集，则是一个偏序集，则也是一个也是一个偏序集，其中偏序集，其中“”是是“”的逆关系。若的逆关系。若是是一个格，则一个格，则也是一个格，称这两个格互为对偶也是一个格，称这两个格互为对偶格。格。若将关于格若将关于格的命题中符号的命题中符号，、，分别，分别用用，、，代替，则得到一个新的命题，称这个，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真定理：对于格中的一个真命题，其对偶命题亦真。3、格的性质、格的性质定理定理1：若：若是一个格，则对任意是一个格，则对任意a、b、c A，有，有（1）aab，bab （2）aba，abb（3）若若ac且且bc，则，则abc（4）若若ca且且cb，则，则cab（1）aab，bab 证明：因证明：因ab=luba，b，它显然是，它显然是 a 的一个上界，的一个上界，aab，同理：，同理：bab。（2）aba，abb证明：因证明：因ab=glba，b，它显然是，它显然是 a 的一个下界，的一个下界，aba，同理：，同理：abb。（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。推论：在推论：在中，对于任意中，对于任意a，b，c A，如果，如果bc，则，则 abac，abac。定理定理2：若：若是一个格，则对于任意是一个格，则对于任意a，b A，以，以下三个公式等价；下三个公式等价；（1）ab （2）ab=b （3）ab=a（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）定理定理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=a定理定理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 定理定理5：在一个格：在一个格中，对于任意中，对于任意a，b，c A，有下列，有下列分配不等式成立：分配不等式成立：（1）a（bc）（ab）（ac）（2）a（bc）（ab）（ac）证：由定理证：由定理1，（，（1）（）（2）知：）知：aab和和aac，可得：，可得：a（ab）（ac），），又又 bc b ab和和 bc c ac bc（ab）（ac）对于对于和和，有：，有：a（bc）（ab）（ac）类似可证明：（类似可证明：（ab）（ac）a（bc）n定义：定义：设设是一个格，设非空集合是一个格，设非空集合S且且S A，若对任意的若对任意的a，b S，有有a b S，a b S，则称则称是是的子格。的子格。n显显然然，子子格格必必是是格格。而而格格的的某某个个子子集集构构成成格格，却却不不一一定是子格。定是子格。4、子格、子格例例：设：设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。