离散数学第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,有PT全下界F∀P∈X,有FP.二、有界格和有补格定理6

设<L,≤>是一个有界格，则对于∀aA,都有

a∨1=1a∧1=a(1是∨运算的零元,∧运算的幺元)

a∨0=aa∧0=0(0是∨运算的幺元,∧运算的零元)证明:

(1)证a∨1=1因为a∨1L且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≤BA∩B=AA⊆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),⊆>是一个布尔格。三、布尔格(布尔代数)例4

X={A|A是由变元p1,p2,…,pn,﹁,∧,∨,→,构成的合式公式集}。<X,∧,∨>诱导的偏序格是<X,>.说明<X,>是布尔格.

证明

(1)<X,>是格，

(2)<X,>是有界格,因为全上界T∀P∈X,有PT全下界F∀P∈X,有FP.(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′