离散数学 第9讲 格.ppt

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

2、了努力。在奠基工作方面，丰廷顿(E. V. Huntington)、雪弗尔(H. M. Sheffer)和斯通(M. H. Stone)都作出了贡献。毕克霍夫(Garrett Birkhoff)和麦克朗(Saunders Maclane)的研究进一步使布尔代数得到严谨的处理。,格和布尔代数,格是一种兼有序和代数的重要结构，它和模糊数学等现代数学有十分紧密的联系； 格与布尔代数具体应用： 格与布尔代数在计算机科学中具有非常重要的应用。如在保密学、计算机语义学、开关理论、计算机理论和逻辑设计以及其他一些科学和工程领域中都直接应用了格与布尔代数。,格和布尔代数,格(lattice)在闪存(flash

3、 memory)编码中的应用:,格的定义与基本性质,主要内容:,重点和难点:,一、格的两种定义,预备知识： 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的下确界(最大下界)。,一、格的两种定义,偏序格的定义： 设是一偏序集合,若对于任意a

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

5、* c)=(a * b) * c a(bc)=(ab)c (3)吸收律 a(a * b)=a a * (ab)=a 则称是代数格。 事实上代数格也满足等幂律，aa=a, a*a=a, 由吸收律可推出 等幂律, 因为a*a=a*(a(a*a)=a。类似地可证aa=a。 例3 (1) S=a,b,c, 为代数格； (2) 定义X:由命题变元p1,p2,pn, , 构成的合式公式集。则为代数格。,一、格的两种定义,定理1：如果是偏序格,定义L上两运算*与如下: a*b=glba,b, ab=luba,b ,则是代数格。 证明: (1)可交换：由*与的定义可知*与是可交换的。 (2)可结合：证明 a,

6、b,cL有a(bc)=(ab)c成立 即要证明 a(bc)(ab)c (ab)ca(bc) 下面证明，类似可证。 由bab(ab)c和c(ab)c可得，(bc)(ab)c 又aab(ab)c，所以a(bc)(ab)c。 (3)吸收律：证明对a,bL，a(a*b)=a。 由aa, a*ba可得a(a*b)a,又aa(a*b),所以a(a*b)=a。 同理可证a * (ab)=a。 定理得证。,一、格的两种定义,定理2：如果是代数格，定义L上一个二元关系如下,即对a,bL, aba*b=aab=b,则是偏序格。 证明: (1) 是偏序关系： 自反 因aL, aa a*a = a。 反对称 设ab,

7、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：如果是代数格，定义L上一个二元关系如下,即对a,bL, aba*b=aab=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,

8、则a*bb. 证明对a,b的任一下界c,有c a*b,即c*(a*b) = c.设c是a,b的任意下界，即有ca且cb,则有c*a=c且c*b=c.而c*(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：设是偏序格，(或)是诱导的代数格，a,b,cL 有以下式子成立: (1)自反性 a a (2

9、)反对称性 (ab) 且 (ba) a = b (3)传递性 (ab) 且 (bc) ac (4) aba, abb aab, 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(续)： (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)

10、分配不等式 a(bc) (ab)(ac) a(bc) (ab)(ac) (14)模不等式 a c a(bc)(ab)c,一、格的两种定义,定理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证明： 证明(13)：a(bc) (ab)(ac) 由aab, aac,可得a(ab)(ac); 又bab, cac,可得bc(ab)

11、(ac)。 所以， a(bc) (ab)(ac)。,二、子格和格同态,子格的定义： 设是偏序格，是由所诱导的代数格, SL且S ,若S关于和是封闭的，则称是的子格。,【例题】图(a)、(b)中所示的格分别是格的子格吗？,一个格中的部分元素在原偏序关系上构成一个格，不能说明它就是原格的子格。主要看该子集上的任意两个元素在原运算保交和保联下的结果是否也在该子集中。,二、子格和格同态,格同态的定义： 设和是两个代数格，存在函数f: LS, 如果对于任何a,bL,有 f(a*b)=f (a)f (b), f(ab)=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