冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材(第34讲)

冯伟森,Email：fws3652020年5月5日星期二,离散数学,计算机学院,2020/5/5,计算机学院,2,格与布尔代数,下面讨论两个重要的代数系统格与布尔代数。布尔代数是人们利用数学方法研究人类思想规律的一项重要成果。布尔代数在逻辑电路设计和开关网络研究中有着广泛的应用，是计算机科学必需的基础知识。布尔代数是一类特殊的格代数，在格与布尔代数中，偏序关系具有重要意义。本章将从格的偏序定义出发，研究格系统的各种性质，建立布尔代数的基本理论。,2020/5/5,计算机学院,3,本章的主要内容,格的概念和基本性质子格的定义保序定理特殊的格及性质布尔代数的概念和基本性质布尔表达式,2020/5/5,计算机学院,4,格的定义,定义17.1（代数格）设是一个代数系统，如果，满足：交换律：ab=ba，ab=ba,结合律：a(bc)=(ab)c,a(bc)=(ab)c吸收律：a(ab)=a，a(ab)=a则称是一个代数格。,这样的代数系统满足幂等律、交换律、结合律、吸收律、和分配律,集合代数系统命题逻辑系统,对这样的代数系统，从运算性质进行抽象，提取共性，得到下述“格”的概念,2020/5/5,计算机学院,5,定理17.1(幂等律)：设是一个代数格,aL,则aa=a，aa=a。定义17.2设是一个偏序集，对a，bL，集合a，b都有最大下界(glb)和最小上界(lub)，则称是一个偏序格，简称L是一个格，若L是一个有限集，则称为有限格。,从定义知道：有限偏序集要成为格，必须有一个最大元和最小元。,2020/5/5,计算机学院,6,偏序集中，任何两个元素X、Y2A，都有lub（X，Y）=XY，glb（X，Y）=XY因此是一个偏序格，称为幂集格。定理17.2设是一个代数格，定义“”：ab当且仅当ab=a或ab=b，则是一个偏序格；,2020/5/5,计算机学院,7,定理17.3设是一个偏序格，在格上定义“”、“”：ab=glb（a，b），ab=lub（a，b），则是一个代数格。,定理17.2和定理17.3表明：格的两种定义是完全等价的。,2020/5/5,计算机学院,8,例17-1.1,如图所示的八个偏序集都是格；,2020/5/5,计算机学院,9,图17.1,2020/5/5,计算机学院,10,如图所示的五个偏序集都不是格。,图17.2,2020/5/5,计算机学院,11,子格与格同态,定义17.3设代数系统是一个格，SL，若S满足：S；运算和对子集S都是封闭的；则称是的子格。注意：即使构成一个格，但它不一定是的一个子格。,例17-2.1,设下图是格对应的Hasse图，S1=a,b,c,f,S2=a,c,d,f,那么不是的子格。因为b和c的最大下界是e,不在S1中，即S1不是封闭的，所以不是子格。同时b和c的最大下界在S中是f，而在L中是e,这也说明定义在L上的运算与定义在S1上的运算并不相同。而是的子格，因为它满足子格的条件。,2020/5/5,计算机学院,12,2020/5/5,计算机学院,13,对偶原理,定义17.4设和是二个偏序格，如果是的逆关系,则称这两个偏序格是互为对偶的格。定义17.5设是一个格，格中的最大元用1表示，最小元用0表示。E是格中的一个公式。将E中的0和1互换，和互换后得到的新公式E*称为E的对偶公式。,2020/5/5,计算机学院,14,对偶原理设X和Y是格上的两个公式，X*和Y*是相对应的对偶公式。如果X=Y，那么X*=Y*。,2020/5/5,计算机学院,15,例17-2.2,设L是由18的正因子组成的集合，则L关于整除关系构成格。整除关系的逆关系是倍数关系。设倍数关系用“”表示，那么是格，并和互为对偶。从代数的角度看，互为对偶的两个格，它们的运算也刚好是互换的。如对格，它对应的格中的运算是分别求最大公约数和最小公倍数；而格对应的格中的运算恰分别是求最小公倍数和最大公约数，,2020/5/5,计算机学院,16,定理17.4设X和Y是格上的两个公式。如果XY，则必有Y*X*。证明：根据偏序的定义和对偶原理，(偏序定义)(对偶原理)(偏序定义),2020/5/5,计算机学院,17,定理17.5设是一个格，是对应的偏序，a，b，c，dL，则abacbc.abacbc.ab，cdacbd.ab，cdacbd.ab，acabc.ac，bcabc.,2020/5/5,计算机学院,18,证明：abab=b(ac)(bc)=bcacbc.abab=a(ac)(bc)=acacbc.ab，cdacbc，bcbd(由)acbd。ab，acaabc(由)abc。,2020/5/5,计算机学院,19,定理17.6设是一个格，是对应的偏序，a，b，c，dL，则a(bc)(ab)(ac).(ab)(ac)a(bc).证明：根据定理17.4，只要证明成立即可。由于aab，aac，根据定理17.5式，a(ab)(ac)(A),2020/5/5,计算机学院,20,又因为bab，cac，根据定理17.5式，得bc(ab)(ac)(B)再根据定理17.5第式，由(A)和(B)可得a(bc)(ab)(ac),2020/5/5,计算机学院,21,同态和同构,定义17.6设和是两个格，f是L到P的映射。如果对任何a,bL,f(ab)=f(a)f(b),f(ab)=f(a)f(b)，则称f是从格到的格同态，特别，当f是双射时，称为格同构。,2020/5/5,计算机学院,22,例17-2.3,设D6表示6的正因子集，那么，因子格和幂集格之间可建立同态关系。解：定义映射f：D62a,b，使得f(1)=,f(2)=a,f(3)=b,f(6)=a,b,可以验证f满足格同态的定义。注意对应的运算是lcm和gcd，对应的运算为和。下面是一些验证数据：,2020/5/5,计算机学院,23,f(lcm(1,3)=f(3)=b=b=f(1)f(3),f(gcd(2,6)=f(2)=a=aa,b=f(2)f(6),f(lcm(2,3)=f(6)=a,b=ab