《《离散数学(贾振华主编)》电子教案 第九章 格与代数》由会员分享，可在线阅读，更多相关《《离散数学(贾振华主编)》电子教案 第九章 格与代数（23页珍藏版）》请在金锄头文库上搜索。
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， yA，都有最小上界（上确界）和最大下界（下确界），则称 为格。,第9章 格与代数,9.1 格的定义和性质 9.1.2 格的性质,定理9.3 在一个格中，对于a，b，c，dA，如果 ab ， cd 则， acbd acbd,定理9.2 在一个格中，对任意的a，bA，都有 aab bab aba abb,第9章 格与代数,9.1 格的定义和性质 9.1.2 格的性
3、质,定理9.5 在一个格中，对任意的a，b，cA，都有 a（bc）（ab）（ac） （ab）（ac）a（bc）,定理9.4 设是一个格，由格所诱导的代数系 统为，则对任意的a，b，c，dA，有如下的规律： （1）ab=ba (交换律) （2）a（bc）=（ab）c (结合律) （3）aa=a (等幂律) （4）a（ab）=a (吸收律),第9章 格与代数,9.1 格的定义和性质 9.1.2 格的性质,定理9.7 设是一个格，那么，对于任意的a，b,cA， 有 ac a（bc）（ab） c,定理9.6 设是一个格，那么,对于任意的a，b，cA有， ab等价于ab=a等价于ab=b,第9章 格与代
4、数,9.1 格的定义和性质 9.1.3 格与代数系统的对应,定理9.8 任何一个偏序格与一代数格等价。,定义9.2 设L是非空集合，在其上定义一个“加法”运算和一个 “乘法”运算，即“+”和“*”。并且满足交换律、结合律和吸收律。 代数系统就称为代数格。,定义9.3 设L，*，+是一个格，S是L的子集。S，*，+ 是L的子格，当且仅当运算*和+在S上是封闭的。,第9章 格与代数,9.2 分配格和有补格 9.2.1 分配格,定义9.4 设是由格所诱导的代数系统。如 果对任意的a，b，cA，满足 a（bc）=（ab）（ac）（交运算对于并运算可分配） 和 a（bc）（ab）（ac） （并运算对于交
5、运算可分配） 则称是分配格.,第9章 格与代数,9.2 分配格和有补格 9.2.2 有补格,定义9.5 设是一个格，如果存在元素aA，对于任意 的xA，都有ax，则称a为格的全下界，记格的全下界 为0；同理若存在元素bA，对于任意的xA，都有xb，称b为 格的全上界，记格的全上界为1。,定义9.6 如果一个格中存在全下界和全上界，则称该格为有界 格。,第9章 格与代数,9.2 分配格和有补格 9.2.2 有补格,定义9.5 设是一个格，如果存在元素aA，对于任意 的xA，都有ax，则称a为格的全下界，记格的全下界 为0；同理若存在元素bA，对于任意的xA，都有xb，称b为 格的全上界，记格的全
6、上界为1。,定义9.6 如果一个格中存在全下界和全上界，则称该格为有界 格。,第9章 格与代数,9.2 分配格和有补格 9.2.2 有补格,定理9.12 一个格若有全下界，则其是唯一的；同理 若一个格若有全上界，则其也是唯一的。,定义9.7 设是一个有界格，和是对应的二元 运算，0是其全下界，而1是其全上界，对于x，yA，有xy=1， xy=0，称y为x的补元，简称补,第9章 格与代数,9.2 分配格和有补格 9.2.2 有补格,定义9.8 在一个有界格中，如果每个元素都至少有一个补元素， 则称此格为有补格。,定理9.13 设即是一个有界格，同时还是一个分配 格，那么若某一个元素有补元素，则其
7、补元素必是唯一的。,第9章 格与代数,9.3 布尔代数 9.3.1 布尔代数的概念,定义9.9 设即是一个有补格，同时还是一个分配格， 那么称为布尔格。,定义9.10 由布尔格，诱导出的代数系统为布尔代数。,定理9.14 设为布尔代数，对任意的元aG， 有且仅有一个补元素存在。,第9章 格与代数,9.3 布尔代数 9.3.2 布尔代数的性质,定理9.15 设有布尔代数，对于任意两个元素 a，bG，必定有 a-1=a （a-1为a的逆元素） （ab）-1=a-1b-1 （ab）-1=a-1b-1,定义9.11 具有有限个元素的布尔代数称为有限布尔代数。,第9章 格与代数,9.3 布尔代数 9.3
8、.2 布尔代数的性质,定义9.12 设和是两个布尔 代数，如果存在着A到B的双射f，对于任意的a，bA，都有 f（ab）=f（a）f（b） f（ab）=f（a）f（b） f（a-1）=（f（a）-1 则称和同构。,第9章 格与代数,9.3 布尔代数 9.3.2 布尔代数的性质,定义9.13 设是一个格，且具有全下界0，如果有元素a 盖住0，则称元素a为原子。,定理9.16 （Stone表示定理）设是由有限尔 格所诱导的一个有限布尔代数，S是布尔格中 的所有原子的集合，则和同构。,第9章 格与代数,9.3 布尔代数 9.3.3 布尔表达式,定义9.14 含n个变元x1，x2，x3，xn的有限次引
9、用以下规则 生成的符号串叫做合式的布尔表达式，简称为布尔表达式。 （1）0和1是布尔表达式。 （2）每一个变元x1，x2，x3，xn是布尔表达式。 （3）若a，b是布尔表达式，则(a*b)，(a+b)是布尔表达式。 （4）若a是布尔表达式，则a-1是布尔表达式。,第9章 格与代数,9.3 布尔代数 9.3.3 布尔表达式,定义9.15 两个布尔表达式(x1，x2，x3，xn)和(x1，x2， x3，xn)是等价(相等)的，当且仅当有限次利用布尔代数所满 足的恒等式可将其中一个表达式化作另一个。,第9章 格与代数,9.3 布尔代数 9.3.3 布尔表达式,定义9.15 两个布尔表达式(x1，x2
10、，x3，xn)和(x1，x2， x3，xn)是等价(相等)的，当且仅当有限次利用布尔代数所满 足的恒等式可将其中一个表达式化作另一个。,例9.13 设B=0，1，设为布尔代数， 考虑到Bn到B的函数个数问题。 特别地，做B3到B的函数个数等于28个。如图所示:,第9章 格与代数,9.3 布尔代数 9.3.3 布尔表达式,第9章 格与代数,9.3 布尔代数 9.3.3 布尔表达式,例9.14 B=0，1，2，3，考虑从B3到B的函数f如图9.5所示， 根据表可以清楚地看到，含有n个变元的集合所对应的布尔表达 式总共有|B|2n个，必然有一些函数不能用布尔表达式表示。,第9章 格与代数,9.3 布尔代数 9.3.3 布尔表达式,第9章 格与代数,本章小结 本章从偏序集开始，然后介绍格代数，并重点介绍了分配 格和有补格，最后介绍了布尔代数和布尔表达式，这些知识， 在计算机的理论和设计中起重要的作用，在数字电子电路的简 化和其它和工程领域中也有重要的作用。,
