离散数学 教学课件 作者 李盘林 第09章.ppt

《离散数学 教学课件 作者 李盘林 第09章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第九章格与布尔代数9.1格9.2布尔代数9.3子布尔代数、积布尔代数和布尔代数同态9.4布尔代数的原子表示9.5布尔代数Br29.6布尔表达式及其范式定理退出9.1格1．格作为偏序集定义9.1.1设是一个偏序集，若对任意a,b,L，存在glb{a,b}和lub{a,b}，则称为格，并记为a*b=glb{a,b}，ab=lub{a,b}，称和分别为L上的交（或积）和并（或和）运算。称为所诱导的代数结构的格。若L是有限集合，称为有限格。格的对偶性原理是成立的：令

2、是偏序集，且是其对偶的偏序集。若是格，则也是格，反之亦然。这是因为，对于L中任意a和b，中lub{a,b}等同于中glb{a,b}，中glb{a,b}等同于中的lub{a,b}。若L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。从上讨论中，可知两格互为对偶。互为对偶的两个和有着密切关系，即格中交运算正是格中的并运算，而格中的并运算正是格中的交运算。因此，给出关于格一

3、般性质的任何有效命题，把关系≤换成≥（或者≥换成≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。定义9.1.2设是格，且SL。若对任意a,bS，有a*bS和abS，则称是格的子格。2．格的基本性质在证明格的性质前，回忆一下a*b和ab的真正含义是有好处的。①a*b≤a和ab≤b，则表明a*b是a和b的下界。②若c≤a和c≤b，则c≤a*b，这表明a*b是a和b的最大下界。①’a≤ab和b≤ab，则表明ab是a和b的上界。②’若a≤c，且b≤c，

4、则ab≤c，这表明ab是a和b的最小上界。定理9.1.1设是格，对任意a,bL，有①ab=ba≤b②a*b=aa≤b③a*b=aab=b亦即a≤bab=ba*b=a定理9.1.2设是格，对任意a,bL，有①a*b=a,aa=a。（幂等律）②a*b=b*a,ab=ba。（交换律）③a*(b*c)=(a*b)*ca(bc)=(ab)c（结合律）④a*(ab)=aa(a*b)=a（吸收律）定理9.1.3设是格，对任意a,b,cL，有①若a≤b和c≤d，

5、则a*c≤b*d，ac≤bd。②若a≤b，则a*c≤b*c，ac≤bc。③c≤a和c≤bc≤a*b④a≤c和b≤cab≤c定理9.1.4设是格，对任意的a,b,cL，有a(b*c)≤(ab)*(ac)(a*b)(a*c)≤a*(bc)通常称上二式为格中分配不等式。定理9.1.5设是格，对任意的a,b,cL，有a≤ca(b*c)≤(ab)*c推论：在格中，对任意的a,b,cL，有(a*b)(a*c)≤a*(b(a*c))a(b*(ac))≤(ab)*

6、(ac)3．特殊的格定义9.1.3设是格，若L中有最大元和最小元，则称为有界格。一般把格中最大元记为1，最小元记为0。由定义可知，对任意aL，有0≤a≤1a*0=0,a0=aa*1=a,a1=1定理9.1.6设是有限格，其中L={a1,a2,···,an}，则是有界格。定义9.1.4设是有界格，对于aL，存在bL，使得a*b=0，ab=1称b为a的补元，记为a’。由定义可知，若b是a的补元，则a也是b的补元，即a与b互为补元。显然，0’=1和1’=0，且易

7、证补元是唯一的。一般说来，一个元素可以有其补元，未必唯一，也可能无补元。定义9.1.5设是格，对任意的a,b,cL，有①a*(bc)=(a*b)(a*c)②a(b*c)=(ab)*(ac)则称为分配格，称①和②为格中分配律。定义9.1.6设是格，对任意的a,b,cL，有a≤ca(b*c)=(ab)*c称为模格。定理9.1.7分配格是模格定理9.1.8每个链都是分配格。定理9.1.9一个格为分配格，当且仅当它不含有任何子格与这两个五元素格中任一个同构。定理9.1

8、.10设是分配格，对任意a,b,cL，有(a*b=a*c)且(ab=ac)b=c定理9.1.11设是有界分配格，若aL，且补元存在，则其补元是唯一的。定义9.1.7设是格，若L中每个元素至少有一补元，则称为有补格。由于补元的定义是在有界格中给出的，可知，有补格一定是有界格。定义9.