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

《离散数学 第六章 格与布尔代数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章格与布尔代数6.1格的概念6.2分配格6.3有补格6.4布尔代数1§6.1格的概念本章将介绍其他的代数系统——格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。2定义设为偏序集,BA,yA.(1)若x(xB→xy)成立,则称y为B的上界;(2)若x(xB→yx)成立,则称y为B的下界;(3)令C={y

2、y为B的上界},若C有最小元素，则称该最小元素为B的最小上界或上确界,记为LUB(上确界)(4)令D

3、={y

4、y为B的下界},若D有最大元素，则称该最大元素为为B的最大下界或下确界,记为GLB(下确界)复习偏序关系中的上界，下界，上确界与下确界3§6.1格的概念例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”为整除关系。其hasze图如下：｛2,7｝的最小上界、最大下界各为什么？｛2,3｝呢？｛5,14｝呢？｛2,7｝的最小上界为14。最大下界无。｛2,3｝的最小上界无，最大下界无。｛5,14｝的最小上界无，最大下界无。4然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze图如下：§

5、6.1格的概念5一、格1．定义：设是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称为格。其中上确界lub{a,b}，记为a∨b,称为a和b的并。下确界glb{a,b}，记为a∧b,称为a和b的交。将∨、∧，看作集合上的两个二元运算，故格所诱导的代数系统记作。6一、格下述偏序集能构成格的是（？）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac7一、格2、对偶格：若是一个偏序集，则也是一个偏序集，其中“≥”是“≤”的逆关系。若是一个格，则也是一个格

6、，称这两个格互为对偶。若将关于格的命题中符号≤，≥，∨、∧，分别用≥，≤，∧、∨，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。8二、格的性质定理1：若是一个格，则对任意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∧b9二、格的性质（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}，

7、它显然是a的一个下界，∴a∧b≤a，同理：a∧b≤b。10二、格的性质（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二、格的性质推论：在中，对于任意a，b，cA，如果b≤c，则a∨b≤a∨c，a∧b≤a∧c。定理2：若是一个格，则对于任意a，bA，以下三个公式等价；（1）a≤b（2）a∨b=b（3）a∧b

8、=a12二、格的性质（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二、格的性质定理3：是一个格，则对于任意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=a14二、格的性质定

9、理4：设有格，对于任意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，∴由传递性可得：a≤b∨d，c≤b∨d，这就表明b∨d是a和c的一个上界，而a∨c是a和c的最小上界，∴必有a∨c≤b∨d。类似地可以证明：a∧c≤b∧d15二、格的性质定理5：在一个格中，对于任意a，b，cA，有下列分配不等式成立：（1）a∨（b∧c）≤（a∨b）∧（a∨c）（2）a∧（b∨c）≥（a∧b）∨（a∧c