离散数学(贾振华主编) 第九章 格与代数

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

1、第9章格与代数本章学习目标本章将介绍另外的代数系统——格和布尔代数，格论大体形成于20世纪30年代，它是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。（1）掌握格的定义和性质（2）掌握分配格与有补格的概念和性质（3）掌握布尔代数的概念和性质（4）掌握布尔表达式的概念和性质，掌握同构的概念及其判定第9章格与代数9.1格的定义和性质9.2分配格和有补格9.3布尔代数第9章格与代数9.1格的定义和性质9.1.1

2、格的定义定理9.1(对偶原理)一个关于格的上、下确界以及偏序关系≤，≥的命题是真命题，当且仅当将命题中的上确界换成下确界、下确界换成上确界、将关系“≤”换成“≥”、将“≥”换成“≤”后是一个真命题。定义9.1设是一个偏序集，如果A中任意两个元素x，y∈A，都有最小上界（上确界）和最大下界（下确界），则称为格。第9章格与代数9.1格的定义和性质9.1.2格的性质定理9.3在一个格中，对于a，b，c，d∈A，如果a≤b，c≤d则，a∨c≤b∨da∧c≤b∧d定理9.2在一个格中，对任意的a，b∈A，

3、都有a≤a∨bb≤a∨ba∧b≤aa∧b≤b第9章格与代数9.1格的定义和性质9.1.2格的性质定理9.5在一个格中，对任意的a，b，c∈A，都有a∨（b∧c）≤（a∨b）∧（a∨c）（a∧b）∨（a∧c）≤a∧（b∨c）定理9.4设是一个格，由格所诱导的代数系统为，则对任意的a，b，c，d∈A，有如下的规律：（1）a∨b=b∨a(交换律)（2）a∨（b∨c）=（a∨b）∨c(结合律)（3）a∨a=a(等幂律)（4）a∨（a∧b）=a(吸收律)第9章格与代数9.1格的定义和性质9.1.2格的

4、性质定理9.7设是一个格，那么，对于任意的a，b,c∈A，有a≤ca∨（b∧c）≤（a∨b）∧c定理9.6设是一个格，那么,对于任意的a，b，c∈A有，a≤b等价于a∧b=a等价于a∨b=b第9章格与代数9.1格的定义和性质9.1.3格与代数系统的对应定理9.8任何一个偏序格与一代数格等价。定义9.2设L是非空集合，在其上定义一个“加法”运算和一个“乘法”运算，即“+”和“*”。并且满足交换律、结合律和吸收律。代数系统就称为代数格。定义9.3设〈L，*，+〉是一个格，S是L的子集。〈S，*，+〉是L

5、的子格，当且仅当运算*和+在S上是封闭的。第9章格与代数9.2分配格和有补格9.2.1分配格定义9.4设是由格所诱导的代数系统。如果对任意的a，b，c∈A，满足a∧（b∨c）=（a∧b）∨（a∧c）（交运算对于并运算可分配）和a∨（b∧c）≤（a∨b）∧（a∨c）（并运算对于交运算可分配）则称是分配格.第9章格与代数9.2分配格和有补格9.2.2有补格定义9.5设是一个格，如果存在元素a∈A，对于任意的x∈A，都有a≤x，则称a为格的全下界，记格的全下界为0；同理若存在元素b∈A，

6、对于任意的x∈A，都有x≤b，称b为格的全上界，记格的全上界为1。定义9.6如果一个格中存在全下界和全上界，则称该格为有界格。第9章格与代数9.2分配格和有补格9.2.2有补格定义9.5设是一个格，如果存在元素a∈A，对于任意的x∈A，都有a≤x，则称a为格的全下界，记格的全下界为0；同理若存在元素b∈A，对于任意的x∈A，都有x≤b，称b为格的全上界，记格的全上界为1。定义9.6如果一个格中存在全下界和全上界，则称该格为有界格。第9章格与代数9.2分配格和有补格9.2.2有补格定理9.12一个

7、格若有全下界，则其是唯一的；同理若一个格若有全上界，则其也是唯一的。定义9.7设是一个有界格，∧和∨是对应的二元运算，0是其全下界，而1是其全上界，对于x，y∈A，有x∨y=1，x∧y=0，称y为x的补元，简称补第9章格与代数9.2分配格和有补格9.2.2有补格定义9.8在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。定理9.13设即是一个有界格，同时还是一个分配格，那么若某一个元素有补元素，则其补元素必是唯一的。第9章格与代数9.3布尔代数9.3.1布尔代数的概念定义

8、9.9设即是一个有补格，同时还是一个分配格，那么称为布尔格。定义9.10由布尔格，诱导出的代数系统为布尔代数。定理9.14设为布尔代数，对任意的元a∈G，