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

本章将介绍其他的代数系统——格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。7.1 格的概念7.2 分配格7.3有补格7.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中的任两个元素a、b，都有最小上界和最大下界，则称A,≤为格。其中上确界lub{a,b}，记为a∨b,称为a和b的并。下确界glb{a,b}，记为a∧b,称为a和b的交。将∨、∧，看作集合上的两个二元运算，故格A,≤所诱导的代数系统记作A，∨，∧。例：下述偏序集能构成格的是（）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac2、对偶格对偶格：若A,≤是一个偏序集，则A,≥也是一个偏序集，其中“≥”是“≤”的逆关系。若A,≤是一个格，则A,≥也是一个格，称这两个格互为对偶格。若将关于格A,≤的命题中符号≤，≥，∨、∧，分别用≥，≤，∧、∨，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。3、格的性质定理1：若A，≤是一个格，则对任意a、b、c?A，有（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（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。（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。推论：在A，≤中，对于任意a，b，c?A，如果b≤c，则a∨b≤a∨c，a∧b≤a∧c。定理2：若A，≤是一个格，则对于任意a，b?A，以下三个公式等价；（1）a≤b（2）a∨b=b（3）a∧b=a（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）定理3：A，≤是一个格，则对于任意a，b，c?A，满足以下四个定律：（1）交换律：a∨b=b∨aa∧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=aa∧a=a定理4：设有格A，≤，对于任意a，b，c，d?A，如果a≤b和c≤d，则（1）a∨c≤b∨d，（2）a∧c≤b∧d证：∵b≤b∨d，d≤b∨d，而a≤b，c≤d，∴由传