离散数学 第9讲 格

1离散数学（二）格和布尔代数格与布尔代数：它们都是具有两个二元运算的代数系统，这两个代数系统与前面讨论的代数系统之间存在着一个重要区别：在格与布尔代数中，偏序关系具有重要意义。为了强调偏序关系的作用，我们将分别从偏序集和代数系统两个方面引入格的概念，给格附加一定的限制之后，格就转化为布尔代数，即布尔代数是特殊的格。格和布尔代数起源与发展:布尔代数最初是作为对逻辑思维法则的研究出现的。英国哲学家布尔(GeorgeBoole)于1847年利用数学方法研究了类与类(集合与集合)之间的关系法则。他的研究后来发展成为一个数学分支—布尔代数。自布尔之后，许多数学家对布尔代数一般化作了努力。在奠基工作方面，丰廷顿(E.V.Huntington)、雪弗尔(H.M.Sheffer)和斯通(M.H.Stone)都作出了贡献。毕克霍夫(GarrettBirkhoff)和麦克朗(SaundersMaclane)的研究进一步使布尔代数得到严谨的处理。格和布尔代数格是一种兼有序和代数的重要结构，它和模糊数学等现代数学有十分紧密的联系；格与布尔代数具体应用：格与布尔代数在计算机科学中具有非常重要的应用。如在保密学、计算机语义学、开关理论、计算机理论和逻辑设计以及其他一些科学和工程领域中都直接应用了格与布尔代数。格和布尔代数格(lattice)在闪存(flashmemory)编码中的应用:格的定义与基本性质格的两种定义11子格和格同态2主要内容:格的定义和性质重点:重点和难点:格的两种定义难点:一、格的两种定义预备知识：1.若集合A上的二元关系R是自反的、反对称的、传递的，则称R为A上的偏序，记为A,≤。2设A,≤是一偏序集合,B⊆A(i)若a∈A，对于每一x∈B,均有x≤a,称a∈A为B的上界；(ii)若b∈A，对于每一x∈B,均有b≤x,称b∈A为B的下界；(iii)c为B的上界,若对B的任一上界c',均有c≤c',称c为B的上确界(最小上界)；(iv)d为B的下界，若对B的任一下界d',均有d'≤d,称d为B的下确界(最大下界)。一、格的两种定义偏序格的定义：设L,≤是一偏序集合,若对于任意a,b∈L,{a,b}均有上确界(最小上界)和下确界(最大下界),则称此偏序集合L,≤为格。一、格的两种定义代数格的引入：设L,≤是一偏序集合，在L上定义两运算*与⊕如下,即对任意a,b∈L：a*b={a,b}的下确界=glb{a,b}保交a⊕b={a,b}的上确界=lub{a,b}保联那么L,*,⊕是代数吗？例1：I+,整除对任意a,b∈I+,有a*b={a,b}的下确界=GCD{a,b}(a,b的最大公约数)a⊕b={a,b}的上确界=LCM{a,b}(a,b的最小公倍数)一、格的两种定义代数格的定义：设L,*,⊕是代数系统,*和⊕是载体L上的二元运算,若满足(1)交换律a*b=b*aa⊕b=b⊕a(2)结合律a*(b*c)=(a*b)*ca⊕(b⊕c)=(a⊕b)⊕c(3)吸收律a⊕(a*b)=aa*(a⊕b)=a则称L,*,⊕是代数格。事实上代数格也满足等幂律，a⊕a=a,a*a=a,由吸收律可推出等幂律,因为a*a=a*(a⊕(a*a))=a。类似地可证a⊕a=a。例3(1)S={a,b,c},ρ(S),∩,∪为代数格；(2)定义X:由命题变元p1,p2,…,pn,﹁,∧,∨,→,构成的合式公式集。则X,∧,∨为代数格。一、格的两种定义定理1：如果L,≤是偏序格,定义L上两运算*与⊕如下:a*b=glb{a,b},a⊕b=lub{a,b},则L,*,⊕是代数格。证明:(1)可交换：由*与⊕的定义可知*与⊕是可交换的。(2)可结合：证明∀a,b,c∈L有a⊕(b⊕c)=(a⊕b)⊕c成立即要证明①a⊕(b⊕c)≤(a⊕b)⊕c②(a⊕b)⊕c≤a⊕(b⊕c)下面证明①，②类似可证。由b≤a⊕b≤(a⊕b)⊕c和c≤(a⊕b)⊕c可得，(b⊕c)≤(a⊕b)⊕c又a≤a⊕b≤(a⊕b)⊕c，所以a⊕(b⊕c)≤(a⊕b)⊕c。(3)吸收律：证明对∀a,b∈L，a⊕(a*b)=a。由a≤a,a*b≤a可得a⊕(a*b)≤a,又a≤a⊕(a*b),所以a⊕(a*b)=a。同理可证a*(a⊕b)=a。定理得证。一、格的两种定义定理2：如果L,*,⊕是代数格，定义L上一个二元关系≤如下,即对∀a,b∈L,a≤ba*b=aa⊕b=b,则L,≤是偏序格。证明:(1)≤是偏序关系：自反因∀a∈L,a≤aa*a=a。反对称设a≤b,b≤a,则有a*b=a,b*a=b,又a*b=b*a,所以a=b。传递性设a≤b,b≤c,则有a*b=a,b*c=b,则有a*c=(a*b)*c=a*(b*c)=a*b=a,则有a≤c。一、格的两种定义定理2：如果L,*,⊕是代数格，定义L上一个二元关系≤如下,即对∀a,b∈L,a≤ba*b=aa⊕b=b,则L,≤是偏序格。证明:(2)对任意a,b∈L,{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*b≤b.②证明对{a,b}的任一下界c,有c≤a*b,即c*(a*b)=c.设c是{a,b}的任意下界，即有c≤a且c≤b,则有c*a=c且c*b=c.而c*(a*b)=(c*a)*b=c*b=c,即c*(a*b)=c,所以有c≤a*b。一、格的两种定义例3(1)：S={a,b,c},ρ(S),∩,∪为代数格,∀A,B∈ρ(S)，A≤BA∩B=AA包含于B所以ρ(S),∩,∪诱导的偏序格是ρ(S),包含于.例3(2)：X={A|A是由变元p1,p2,…,pn,﹁,∧,∨,→,构成的合式公式集。∀P,Q∈X,P≤QP∧Q=PPQX,∧,∨诱导的偏序格是X,。一、格的两种定义定理3：设L,≤是偏序格，L,∧,∨(或L,*,⊕)是L,≤诱导的代数格，∀a,b,c∈L有以下式子成立:(1)自反性a≤a(2)反对称性(a≤b)且(b≤a)a=b(3)传递性(a≤b)且(b≤c)a≤c(4)a∧b≤a,a∧b≤ba≤a∨b,b≤a∨b(5)(c≤a)且(c≤b)c≤(a∧b),(b≤c)且(a≤c)c≥(a∨b)(6)交换律a∧b=b∧aa∨b=b∨a(7)结合律(a∧b)∧c=a∧(b∧c),(a∨b)∨c=a∨(b∨c)一、格的两种定义定理3(续)：(8)等幂律a∧a=a,a∨a=a(9)吸收律a∧(a∨b)=a,a∨(a∧b)=a(10)a≤b⇔a∧b=a⇔a∨b=b(11)a≤b且d≤ca∧d≤b∧ca≤b且d≤ca∨d≤b∨c(12)保序性b≤ca∧b≤a∧c,b≤ca∨b≤a∨c(13)分配不等式a∨(b∧c)≤(a∨b)∧(a∨c)a∧(b∨c)≥(a∧b)∨(a∧c)(14)模不等式a≤c⇔a∨(b∧c)≤(a∨b)∧c一、格的两种定义定理3证明：证明(10)：a≤b⇔a∧b=a⇔a∨b=b先证→由a≤b,a≤a,可得a≤a∧b;又由定义知a∧b≤a;所以a∧b=a再证←已知a=a∧b,a∧b≤b,可得a≤b，同理可证a≤ba∨b=b证明(11)：a≤b且d≤ca∧d≤b∧ca∧d≤a,a∧d≤d,由传递性得a∧d≤b,a∧d≤c;又由公式(5)可得a∧d≤b∧c一、格的两种定义定理3证明：证明(13)：a∨(b∧c)≤(a∨b)∧(a∨c)由a≤a∨b,a≤a∨c,可得a≤(a∨b)∧(a∨c);又b≤a∨b,c≤a∨c,可得b∧c≤(a∨b)∧(a∨c)。所以，a∨(b∧c)≤(a∨b)∧(a∨c)。二、子格和格同态子格的定义：设L,≤是偏序格，L,∧,∨是由L,≤所诱导的代数格,S⊆L且S≠Ø,若S关于∧和∨是封闭的，则称S,≤是L,≤的子格。【例题】图(a)、(b)中所示的格S1,≤分别是格S,≤的子格吗？(a)S,≤abecdffacdS1,≤eabdcedeabS,≤S1,≤(b)一个格中的部分元素在原偏序关系上构成一个格，不能说明它就是原格的子格。主要看该子集上的任意两个元素在原运算保交和保联下的结果是否也在该子集中。二、子格和格同态格同态的定义：设L,*,⊕和S,∧,∨是两个代数格，存在函数f:L→S,如果对于任何a,b∈L,有f(a*b)=f(a)∧f(b),f(a⊕b)=f(a)∨f(b)则称f是从L,*,⊕到S,∧,∨的格同态。若f是双射函数，则称f是格同构。二、子格和格同态定理4：设L,*,⊕和S,∧,∨是两个格，在集合L和S中，对应于保交和保联运算的偏序关系分别是≤和≤′，如果f:L→S是格同态，则对任意a,b∈L,当a≤b时,必有f(a)≤′f(b)。证明：因为a≤b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为载体的两个格L,D和S,≤,这里D是整除关系，≤是小于等于关系。函数f:L→S,f(x)=x是保序的，但不是格同态，如下图。但是当L,*,⊕和S,∧,∨同构时，a≤b⇔f(a)≤′f(b)。同构的两个格哈斯图是一样的，只是标记的结点不同。二、子格和格同态例：画出所有包含1～5个元素的互不同构的格。作业：P228习题7.11、5、6、725谢谢同学们!