离散数学-第9讲-格ppt课件.ppt

《离散数学-第9讲-格ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-第9讲-格ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学（二）离散数学（二）格和布尔代数格和布尔代数 格与布尔代数格与布尔代数：它们都是具有两个二元运算的代数系统，这两个代数系统与前面讨论的代数系统之间存在着一个重要区别：在格与布尔代数中，在格与布尔代数中，偏序关系偏序关系具有重要意义具有重要意义。 为了强调偏序关系的作用，我们将分别从偏序集偏序集和代数系代数系统统两个方面引入格的概念，给格附加一定的限制之后，格就转化为布尔代数，即布尔代数是特殊的格布尔代数是特殊的格。格和布尔代数格和布尔代数起源与发展起源与发展: 布尔代数最初是作为对逻辑思维法则的研究出现的。英国哲英国哲学家布尔学家布尔(George Boole)于于1847年利用数学

2、方法研究了类与年利用数学方法研究了类与类类(集合与集合集合与集合)之间的关系法则之间的关系法则。他的研究后来发展成为一个数学分支布尔代数布尔代数。 自布尔之后，许多数学家对布尔代数一般化作了努力。在奠基工作方面，丰廷顿丰廷顿(E. V. Huntington)、雪弗尔、雪弗尔(H. M. Sheffer)和斯通和斯通(M. H. Stone)都作出了贡献。毕克霍夫毕克霍夫(Garrett Birkhoff)和麦克朗麦克朗(Saunders Maclane)的研究进一步使布尔代数得到严谨的处理。格和布尔代数格和布尔代数 格是一种兼有序有序和代数代数的重要结构，它和模糊数学等现代数学有十分紧密的联

3、系； 格与布尔代数具体应用：格与布尔代数具体应用： 格与布尔代数在计算机科学中具有非常重要的应用。如在保密学保密学、计算机语义学计算机语义学、开关理论开关理论、计算机理论计算机理论和逻辑设计逻辑设计以及其他一些科学和工程领域中都直接应用了格与布尔代数。格和布尔代数格和布尔代数格格( (lattice) )在闪存在闪存( (flash memory) )编码中的应用编码中的应用: : 格的定义与基本性质格的定义与基本性质格的两种定义格的两种定义1 11 1子格和格同态子格和格同态2 2主要内容主要内容: :格的定义和性质格的定义和性质重点重点: : 重点和难点重点和难点: :格的两种定义格的两种

4、定义难点难点: : 一、格的两种定义一、格的两种定义预备知识：预备知识： 1. 若集合A上的二元关系R是自反的、反对称的、传递的，则称R为A上的偏序偏序，记为。 2 设是一偏序集合,BA (i) 若若aA，对于每一xB, 均有xa, 称aA为为B的上界；的上界； (ii) 若若bA，对于每一xB, 均有bx, 称bA为为B的下界；的下界； (iii) c为B的上界, 若对B的任一上界c, 均有c c, 称c为为B的的 上确界上确界(最小上界最小上界)； (iv) d为B的下界，若对B的任一下界d, 均有d d,称d为为 B的下确界的下确界(最大下界最大下界)。一、格的两种定义一、格的两种定义偏

5、序格的定义：偏序格的定义： 设是一偏序集合,若对于任意a,bL, a,b均有上确界(最小上界)和下确界(最大下界),则称此偏序集合偏序集合为格为格。一、格的两种定义一、格的两种定义代数格的引入：代数格的引入： 设是一偏序集合，在L上定义两运算*与 如下, 即对任意a,b L：a * b=a,b 的下确界=glba,b 保交保交a b=a,b 的上确界=luba,b 保联保联 那么是代数吗？例例1：对任意a,bI+,有 a*b=a,b的下确界=GCDa,b (a,b的最大公约数) a b=a,b的上确界=LCMa,b (a,b的最小公倍数)一、格的两种定义一、格的两种定义代数格的定义：代数格的定

6、义： 设是代数系统,*和 是载体L上的二元运算,若满足 (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 * b)=a a * (a b)=a 则称是代数格是代数格。 事实上代数格也满足等幂律等幂律，a a=a, a*a=a, 由吸收律可推出 等幂律, 因为a*a=a*(a (a*a)=a。类似地可证a a=a。例例3 (1) S=a,b,c, 为代数格； (2) 定义X:由命题变元p1,p2,pn, , 构成的合式公式集。则为代数格。一、格的两种定义一、格

7、的两种定义定理定理1 1：如果是偏序格,定义L上两运算*与 如下:a*b=glba,b, a b=luba,b ,则是代数格。证明证明: (1)可交换可交换：由*与 的定义可知*与 是可交换的。(2)可结合：可结合：证明 a,b,cL有a (b c)=(a b) c成立 即要证明 a (b c)(a b) c (a b) ca (b c) 下面证明，类似可证。 由ba b(a b) c和c(a b) c可得，(b c)(a b) c 又aa b(a b) c，所以a (b c)(a b) c。(3)吸收律：吸收律：证明对a,bL，a (a*b)=a。 由aa, a*ba可得a (a*b)a,又

8、aa (a*b),所以a (a*b)=a。 同理可证a * (a b)=a。定理得证。定理得证。一、格的两种定义一、格的两种定义定理定理2 2：如果是代数格，定义L上一个二元关系如下,即对a,bL, aba*b=aa b=b,则是偏序格。证明证明: (1) 是偏序关系是偏序关系： 自反自反 因aL, aa a*a = a。 反对称反对称 设ab,ba, 则有a*b=a, b*a=b,又a*b=b*a,所以a=b。 传递性传递性 设ab, bc,则有a*b=a, b*c=b,则有a*c=(a*b)*c=a*(b*c)=a*b=a, 则有 a c。 一、格的两种定义一、格的两种定义定理定理2 2：

9、如果是代数格，定义L上一个二元关系如下,即对a,bL, aba*b=aa b=b,则是偏序格。证明证明: (2) 对任意对任意a,bL,a,b均有上确界和下确界均有上确界和下确界,下面只证下面只证有下确界有下确界 a*b即为a,b的下确界: 先证下界先证下界 (a*b)*a = a*(b*a)= a*(a*b) = (a*a)*b = a*b,即(a*b)*a = a*b,则a*b a; 同理可得(a*b)*b = a*b,则a*bb. 证明对证明对a,b的任一下界的任一下界c,有有c a*b,即即c*(a*b) = c.设c是a,b的任意下界，即有ca且cb,则有c*a=c且c*b=c.而c

10、*(a*b)=(c*a)*b=c*b=c,即c*(a*b)=c,所以有ca*b。一、格的两种定义一、格的两种定义例例3(1)：S=a,b,c, 为代数格,A,B(S)，AB AB=A A包含于B 所以诱导的偏序格是 .例例3(2)：X=A|A是由变元p1,p2,pn, ,构成的合式公式集。P,QX,PQ PQ=PPQ 诱导的偏序格是 。一、格的两种定义一、格的两种定义定理定理3 3：设是偏序格，(或)是诱导的代数格，a,b,cL 有以下式子成立: (1)自反性 a a (2)反对称性 (ab) 且 (ba) a = b (3)传递性 (ab) 且 (bc) ac (4) aba, abb aa

11、b, bab (5) (ca)且(cb) c(ab), (bc)且(ac) c (ab) (6)交换律 ab=ba ab= ba (7)结合律 (ab)c=a(bc), (ab)c=a(bc)一、格的两种定义一、格的两种定义定理定理3( 3(续续) )：(8)等幂律 aa=a, aa=a (9)吸收律 a(ab)= a, a(ab)=a(10) ab ab=a ab=b(11) ab 且d c ad bc ab 且d c a d bc(12)保序性 bc abac, bc a bac(13)分配不等式 a(bc) (ab)(ac) a(bc) (ab)(ac)(14)模不等式 a c a(bc

12、)(ab)c一、格的两种定义一、格的两种定义定理定理3 3证明：证明：证明(10)： ab ab=a ab=b 先证 由 ab, aa, 可得aab;又由定义知ab a;所以ab=a 再证 已知a=ab, abb,可得ab，同理可证abab=b证明(11)： ab且d c adbc ada, add,由传递性得adb, adc;又由公式(5)可得adbc一、格的两种定义一、格的两种定义定理定理3 3证明：证明：证明(13)：a(bc) (ab)(ac)由aab, aac,可得a(ab)(ac);又bab, cac,可得bc(ab)(ac)。所以， a(bc) (ab)(ac)。 二、子格和格同

13、态二、子格和格同态子格的定义：子格的定义： 设是偏序格，是由所诱导的代数格, SL且S ,若S关于和是封闭的，则称是的子格子格。【例题例题】图图(a)、(b)中所示的格中所示的格分别是格分别是格的子格吗？的子格吗？(a)abecdffacdea abdcedeab(b)一个格中的部分元素在原偏序关系上构成一个格中的部分元素在原偏序关系上构成一个格，不能说明它就是原格的子格一个格，不能说明它就是原格的子格。主主要看该子集上的任意两个元素在原运算保要看该子集上的任意两个元素在原运算保交和保联下的结果是否也在该子集中。交和保联下的结果是否也在该子集中。二、子格和格同态二、子格和格同态格同态的定义：格

14、同态的定义： 设和是两个代数格，存在函数f: LS, 如果对于任何a,bL,有f(a*b)=f (a)f (b), f(a b)=f (a)f (b) 则称f是从到的格同态格同态。若f是双射函数，则称f是格同构格同构。二、子格和格同态二、子格和格同态 定理定理4：设和是两个格，在集合L和S中，对应于保交和保联运算的偏序关系分别是和，如果f: LS是格同态，则对任意a,bL,当ab时,必有f (a)f (b)。 证明证明：因为ab a*b=a, 所以f(a*b)=f(a), 根据格同态定义有，f(a*b)= f(a)f(b)，所以f(a)f(b)=f(a),于是可得f(a)f(b)。 Note: f是是格同态格同态, 则则f保序的保序的; 反之反之,当当f保序时保序时, f不一定是不一定是格同态。格同态。 二、子格和格同态二、子格和格同态定理定理4的逆的逆反例反例：对都以12的因子集合S12为载体的两个格和,这里D是整除关系，是小于等于关系。函数f:LS, f(x)=x是保序的，但不是格同态，如下图。 但是当和同构时，abf(a)f(b)。同构的两个格哈斯图是一样的，只是标记的结点不同。二、子格和格同态二、子格和格同态例：画出所有包含例：画出所有包含15个元素的互不同构的格。个元素的互不同构的格。作业： P228 习题7.1 1、 5、6 、725谢谢同学们谢谢同学们! !