离散数学 贾振华 第11章 格与布尔代数

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

1、第11章格与布尔代数本章学习目标通过本章的学习，读者应掌握如下内容：（1）掌握格的定义和性质（2）掌握模格、分配格与有补格的概念和性质（3）掌握布尔代数的概念和性质（4）掌握布尔表达式的概念和性质，并掌握同构的概念及其判定第11章格与布尔代数11.1格的定义和性质11.2分配格和有补格11.3布尔代数11.1格的定义和性质11.1格的定义定义11.1.1设（S，≤）是一个偏序集，如果S中任意两个元素都有上确界（最小上界）和下确界（最大下界），则称（S，≤）为格。把S中元素a和b得上确界和下确界，分别记为：a∨b和a∧b，即a∨b=sup{a，b}，a∧b=inf{a，b}。a∨b读作

2、a并b，a∧b读作a交b。11.1格的定义和性质11.1格的定义例11.1.1正整数集合上整除关系就是一个偏序关系，对于正整数集合上的任意两个元素a，b，一定有上确界和下确界。事实上，a∨b=[a，b]，a∧b=（a，b），其中，[a，b]、（a，b）分别为a与b的最小公倍数和最大公因数。这样正整数集和关于整除关系构成格。11.1格的定义和性质11.1格的定义例11.1.2设S是一个集合，P（S）是S的幂集，即P（S）是由S的所有子集组成的集合，则P（S）关于集合的包含关系构成一个格，称为S的幂集格。对于任意的A，B∈P（S），A∨B=A∪B，A∧B=A∩B，其中∪和∩分别为集合的并

3、与交。当S是无限集时，令Pf（S）是由S的所有有限子集组成的集合，则Pf（S）关于集合的包含关系仍构成一个格。11.1格的定义和性质11.1格的定义例11.1.3设V是域F上的一个向量空间，维数可以有限也可以无限。令L（V）是V的所有子空间组成的集合，则L（V）关于集合的包含关系构成一个格。对于任意的A，B∈L（V），子空间A∩B是A与B的下确界A∧B，由子集A∪B生成的子空间（包含A∪B的所有子空间的交）是A与B的上确界A∨B。11.1格的定义和性质11.1.2格的对偶原理定义11.1.2设（S，≤）是格，将关系式P中的≤与≥互换，∨与∧互换得到关系式P*，其中≥定义为b≥a当且仅

4、当a≤b，称P*为P的对偶式，简称对偶。例如P是a≤a∨b，那么P的对偶式是a≥a∧b。11.1格的定义和性质11.1.2格的对偶原理定理11.1.1（格的对偶原理）在任何格（S，≤）上成立的关系式P，其对偶式P*也成立。证明设（S，≤）为任意的格，只须证明P*对（S，≤）成立即可。如下定义S上的二元关系：任意a，b∈S，有abab。易证也是S上的偏序。11.1格的定义和性质11.1.2格的对偶原理定理11.1.1（格的对偶原理）在任何格（S，≤）上成立的关系式P，其对偶式P*也成立。设任意a，b∈S，集合{a，b}的上确界和下确界存在，分别记作ab和ab，并且ab=ab，ab=ab

5、。所以（S，）也是格，且P*在（S，≤）中成立，当且仅当P在（S，）中成立。由于P在任何格（S，≤）中都成立，所以P*在（S，≤）中也成立。11.1格的定义和性质11.1.3格的性质定理11.1.2设（S，≤）是格，对于任意a，b，c∈S有（1）a≤a∨b，b≤a∨b；（2）a∧b≤a，a∧b≤b；（3）若b≤a，c≤a，则b∨c≤a；（4）若a≤b，a≤c，则a≤b∧c。11.1格的定义和性质11.1.3格的性质设（S，≤）是格。对于任意的a，b∈S，都有a∨b，a∧b∈S，即∨与∧是S的两个代数运算。这样（S，∨，∧）就构成了代数系统，称为由格S诱导出的代数系统。下面讨论这个代数

6、系统的性质。11.1格的定义和性质11.1.3格的性质定理11.1.3（S，≤）是一个格，由格（S，≤）所诱导的代数系统为（S，∨，∧），则对任意的a，b，c∈S，下列性质成立：（1）交换律a∨b=b∨a，a∧b=b∧a；（2）结合律（a∨b）∨c=a∨（b∨c），（a∧b）∧c=a∧（b∧c）；（3）幂等律a∨a=a，a∧a=a；（4）吸收律（a∨b）∧a=a，（a∧b）∨a=a。11.1格的定义和性质11.1.3格的性质证明根据格的对偶原理只须证明每条性质的前半部分。（1）a∨b是{a，b}的上确界，b∨a是{b，a}的上确界，由集合定义的无序性有{a，b}={b，a}，可得a∨

7、b=b∨a。（2）因为a≤a∨b≤（a∨b）∨c，b≤a∨b≤（a∨b）∨c，c≤（a∨b）∨c，于是有b∨c≤（a∨b）∨c，a∨（b∨c）≤（a∨b）∨c。同理可证（a∨b）∨c≤a∨（b∨c）。根据≤的反对称性可知，（a∨b）∨c=a∨（b∨c）。11.1格的定义和性质11.1.3格的性质证明根据格的对偶原理只须证明每条性质的前半部分。3）显然a≤a∨a，又由a≤a，a是{a，a}的上界，所以a∨a≤a。根据≤的反对称性，有a∨a=a。（4）因为a≤