离散数学-第10讲-分配格、有界格与有补格

1离散数学（二）特殊格:分配格,有界格与有补格分配格11有界格和有补格2主要内容:分配格,有界格与有补格重点:重点和难点:布尔格(布尔代数)3有补格的定义难点:一、分配格分配格的定义：设L,*,⊕是一个格,若对于任何a,b,c∈L,有a*(b⊕c)=(a*b)⊕(a*c)保交对保联可分配(1)a⊕(b*c)=(a⊕b)*(a⊕c)保联对保交可分配(2)则称L,*,⊕是一个分配格。Note:上述定义中(1)和(2)是等价的,只要一个成立,应用吸收律可推出另外一个。因此,判断一个格是否是分配格只需判断(1)或(2)其中之一.例1:S={a,b,c},ρ(S),∩,∪为分配格,因为任取A,B,C∈ρ(S),(a)A∪(B∩C)=(A∪B)∩(A∪C)(b)A∩(B∪C)=(A∩B)∪(A∩C)一、分配格例2:图中钻石格与五角格是分配格吗？(a)b*(c⊕d)＝b*a＝b(b*c)⊕(b*d)＝e⊕e＝e所以b*(c⊕d)≠(b*c)⊕(b*d)(b)c*(b⊕d)＝c*a＝c(c*b)⊕(c*d)＝e⊕d=d所以c*(b⊕d)≠(c*b)⊕(c*d)一、分配格定理1设L,≤是偏序格，则L,≤是分配格当且仅当(i)在此格中不存在与钻石格同构的子格;(ii)且不存在与五角格同构的子格。推论:设L,≤是格，|L|5,则L,≤是分配格。定理2每个链都是分配格。证明:设L,≤是链，则L,≤必是格.任取a,b,c∈L,讨论以下两种情况:(1)a≤b或a≤c;(2)a≥b和a≥c。对于情况(1)有:a*(b⊕c)=a;(a*b)⊕(a*c)=a⊕a=a.对于情况(2)有:a*(b⊕c)=b⊕c;(a*b)⊕(a*c)=b⊕c.因此有a*(b⊕c)=(a*b)⊕(a*c).所以,每个链都是分配格.一、分配格定理3设L,*,⊕是一个格，若*运算对⊕运算可分配，则⊕对*也可分配，反之亦然。证明:设*运算对⊕运算可分配，即任取a,b,c∈L,满足a*(b⊕c)=(a*b)⊕(a*c),现要证a⊕(b*c)=(a⊕b)*(a⊕c).(a⊕b)*(a⊕c)=((a⊕b)*a)⊕((a⊕b)*c)=a⊕[(a*c)⊕(b*c)]=[a⊕(a*c)]⊕(b*c)=a⊕(b*c)同理可由a⊕(b*c)=(a⊕b)*(a⊕c)推出a*(b⊕c)=(a*b)⊕(a*c).一、分配格定理4设L,*,⊕是一个分配格，那么对于任意a,b,c∈L,若有a*b=a*c和a⊕b=a⊕c，则必有b=c。证明:c=(a*c)⊕c=(a*b)⊕c=(a⊕c)*(b⊕c)=(a⊕b)*(b⊕c)=((a⊕b)*b)⊕((a⊕b)*c)=b⊕((a*c)⊕(b*c))=b⊕((a*b)⊕(b*c))=b⊕(a*c)=b⊕(a*b)=b二、有界格和有补格全上/下界定义:设L,≤是一个格,若∃a∈L,对所有x∈L均有x≤a,称a为格L,≤的全上界；若∃b∈L,对所有x∈L均有b≤x,称b为格L,≤的全下界。通常将全上界记为“1”，而将全下界记为“0”。定理5对于一个格L,≤,若全上界存在,那么它是唯一的(若全下界存在,则唯一).Note:1有限格必有全上界(全下界)2无限格不一定有全上界(全下界)如I,≤无全上界.有界格的定义:具有全上界和全下界的格称为有界格,记作L,∧,∨,0,1.二、有界格和有补格例2(1)S={a,b,c},偏序格是ρ(S),⊆，全上界S∀A∈ρ(S),有A⊆S全下界Ø∀A∈ρ(S),有Ø⊆A(2)X={A|A是由变元p1,p2,…,pn,﹁,∧,∨,→,构成的合式公式集}。X,∧,∨诱导的偏序格是X,.全上界T∀P∈X,有PT全下界F∀P∈X,有FP.二、有界格和有补格定理6设L,≤是一个有界格，则对于∀aA,都有a∨1=1a∧1=a(1是∨运算的零元,∧运算的幺元)a∨0=aa∧0=0(0是∨运算的幺元,∧运算的零元)证明:(1)证a∨1=1因为a∨1L且1是全上界，所以a∨1≤1;又因为1≤a∨1，所以a∨1=1.(2)证a∧1=a因为a≤a，a≤1,所以a≤a∧1;又因为a∧1≤a，所以a∧1=a.(3)(4)类似可证.二、有界格和有补格补元的定义:设L,∧,∨,0,1是有界格a∈L,若存在b∈L使得a∨b=1和a∧b=0,则称b为a的补元。(1)中a,b,c都不存在补元,0与1互为补元.(2)中a,b,c中任意两个都互为补元,0与1互为补元.(3)中a的补元都是b和c,而c的补元是a,0与1互为补元.Note:在格中有的元素无补元,有的元素有补元,有的元素有多个补元.二、有界格和有补格有补格定义:如果在一个有界格中，每个元素都至少有一个补元,则称这个格为有补格.上图中(2)和(3)是有补格,而(1)不是有补格.证明:∵0∧1=0，0∨1=1，∴0、1互为补元。设c也是0的补元，∵0∨c=1，∴必有c=1，故0的补元唯一。同理可证1的补元也唯一。定理7在有界格L,∧,∨,0,1中,0和1互为补元,且是唯一的.证明:设b,c都是a的补元,则a∧b=0=a∧c,a∨b=1=a∨c,分配格满足消去律,可知b=c.消去律:(即对于任意a,b,c∈L有(a∧b=a∧c)∧(a∨b=a∨c)⇒b=c)定理8在分配格中，如果元素a∈L有一个补元a'，则此补元a'是唯一的.三、布尔格(布尔代数)布尔格的定义如果格L,∧,∨,0,1,既是有补格,又是分配格,则称此格为布尔格(或有补分配格),也叫做布尔代数.例3设S是非空有限集合,ρ(S),∩,∪为代数格∀A,B∈ρ(S)，A≤BA∩B=AA⊆B由ρ(S),∩,∪诱导的偏序格是ρ(S),⊆.说明ρ(S),⊆是布尔格.证明(1)ρ(S),⊆是格;(2)ρ(S),⊆是有界格,因为全上界S∀A∈ρ(S),有A⊆S全下界Ø∀A∈ρ(S),有Ø⊆A;(3)ρ(S),⊆是有补格,因任取A∈ρ(S),A的补元是S-A;(4)ρ(S),⊆是分配格,因∩和∪运算满足相互分配律.综上可知,ρ(S),⊆是一个布尔格。三、布尔格(布尔代数)例4X={A|A是由变元p1,p2,…,pn,﹁,∧,∨,→,构成的合式公式集}。X,∧,∨诱导的偏序格是X,.说明X,是布尔格.证明(1)X,是格，(2)X,是有界格,因为全上界T∀P∈X,有PT全下界F∀P∈X,有FP.(3)X,是有补格，因任取∀P∈X,P的补元是┒P(4)X,∧,∨是分配格,因∧和∨运算满足相互分配律，综上可知,X,是一个布尔格。三、布尔格(布尔代数)由于布尔代数L中的每个元都有唯一的补元.求一个元素的补元素可以看作一元运算,称为补运算.因此,布尔代数L可记为L,∧,∨,',0,1,其中'表示求补运算.证明(1)由于a∧a′=1,a∨a′=0;根据交换律有,a′∧a=1,a′∨a=0;所以(a′)′=a;(2)(a∨b)∧(a′∧b′)=(a∧a′∧b′)∨(b∧a′∧b′)=0(a∨b)∨(a′∧b′)=(a∨a′∨b′)∧(b∨a′∨b′)=1根据补元的唯一性,可得(a∨b)′=a′∧b′定理8设L,≤是布尔格(L,∧,∨,0,1)，对于所有a,b∈L,有(1)(a′)′=a(2)(a∨b)′=a′∧b′(3)(a∧b)′=a′∨b′(4)a≤b⇔a∧b′=0⇔a′∨b=1作业：P239习题7.39、1317谢谢同学们!