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

本章将介绍其他的代数系统——格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在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∨a

a∧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=a

a∧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，∴由传递性可得：a≤b∨d

，c≤b∨d，这就表明b∨d是a和c的一个上界，而a∨c是a和c的最小上界，∴必有a∨c≤b∨d。类似可以证明：a∧c≤b∧d

定理5：在一个格<A，≤>中，对于任意a，b，c

A，有下列分配不等式成立：（1）a∨（b∧c）≤（a∨b）∧（a∨c）（2）a∧（b∨c）≥（a∧b）∨（a∧c）证：由定理1，（1）（2）知：a≤a∨b和a≤a∨c，可得：

a≤（a∨b）∧（a∨c），①又∵b∧c≤b≤a∨b和b∧c≤c≤a∨c∴b∧c≤（a∨b）∧（a∨c）②对于①和②，有：a∨（b∧c）≤（a∨b）∧（a∨c）类似可证明：（a∧b）∨（a∧c）≤a∧（b∨c）

定义：设<A，≤>是一个格，设非空集合S且S

A，若对任意的a，b∈S，有a∧b∈S，a∨b∈S，则称<S，

≤>是<A，≤>的子格。显然，子格必是格。而格的某个子集构成格，却不一定是子格。4、子格例

：设〈A，≤〉是一个格，其中A={a