離散數學第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′