離散數(shù)學(xué)課件 格與布爾代數(shù)2

第十一章格與布爾代數(shù)布爾代數(shù)是計(jì)算機(jī)邏輯設(shè)計(jì)的基礎(chǔ)，它是由格引出的，格又是從偏序集引出的。所以我們先回顧一下偏序集。<A,≤>是偏序集:≤是A,反對稱和傳遞關(guān)系(偏序).偏序集中的元素間的次序可以通過它的Hasse圖反映出來.

例如A={1,2,3,6,12,24,36},≤是A上的整除其Hasse圖如圖所示另設(shè)有集合BA,且B≠Φ1.B的極小元與極大元

y是B的極小元y∈B∧x(x∈B∧x≤y)y是B的極大元y∈B∧x(x∈B∧y≤x)例如{2,3,6}的極小元:2,3極大元:6６。１。３。12。２。24。36。12.B的最小元與最大元

y是B的最小元y∈B∧x(x∈B

y≤x)y是B的最大元y∈B∧x(x∈B

x≤y){2,3,6}的最小元:無最大元:6B如果有最小元(最大元),則是唯一的。3.B的下界與上界y是B的下界y∈A∧x(x∈B

y≤x)y是B的上界y∈A∧x(x∈B

x≤y){2,3,6}的下界:1上界:6,12,24,364.B的最大下界(下確界)與最小上界(上確界)y是B的最大下界(下確界)：B的所有下界x,有x≤y。y是B的最小上界(上確界)：B的所有上界x,有y≤x。{2,3,6}下確界:1上確界:6(B若有下(上)確界，則唯一)６。１。３。12。２。24。36。211-1格

(Lattice)一.基本概念1.格的定義<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，則稱<A,≤>是格。右圖的三個(gè)偏序集，<A,≤>不是格，因?yàn)閧24,36}無最小上界。<B,≤><C,≤>是格。６。１。３。12。２。24。36。30。3。１。2。5。10。15。6。<A,≤><B,≤>3。4。1。2。<C,≤>3這三個(gè)偏序集，也都不是格，第一個(gè)與第三個(gè)是同構(gòu)的。因?yàn)閐和e無下界，也無最小上界；b,c雖有下界，但無最大下界。2,3無最大下界，4,5無最小上界。2.平凡格：所有全序都是格，稱之為平凡格。因?yàn)槿蛑腥魏蝺蓚€(gè)元素x,y，要么x≤y,要么y≤x。如果x≤y，則{x,y}的最大下界為x，最小上界為y。如果y≤x，則{x,y}的最大下界為y，最小上界為x。即這{x,y}的最大下界為較小元素，最小上界為較大元素.d

a

b

ce

1

2

34

5

6d

a

b

c

e43.由格誘導(dǎo)的代數(shù)系統(tǒng)設(shè)<A,≤>是格,在A上定義二元運(yùn)算∨和∧為:

a,b∈Aa∨b=LUB{a,b},{a,b}的最小上界.

LeastUpperBounda∧b=GLB{a,b},{a,b}的最大下界.

GreatestLowerBound稱<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng).(∨-并,∧-交)例如右邊的格中a∧b=b,a∨b=a,b∧c=e4.子格：設(shè)<A,≤>是格,<A,∨,∧>是由<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。B是A的非空子集，如果∧和∨在B上封閉，則稱<B,≤>是<A,≤>的子格。<C,≤>是<A,≤>的子格。而<B,≤>不是.b∧c=dB(運(yùn)算規(guī)則要從格<A,≤>中找)

e

ab

d

cb

a

c

fe

gb

a

c

fe

g

d<B,≤><A,≤>

a

cb

d<C,≤>5二.格的對偶原理設(shè)<A,≤>是格，≤的逆關(guān)系記作≥，≥也是偏序關(guān)系。<A,≥>也是格，<A,≥>的Hasse圖是將<A,≤>的Hasse圖顛倒180o即可。

格的對偶原理：設(shè)P是對任意格都為真的命題，如果將P中的≤換成≥，∧換成∨，∨換成∧，就得到命題P’,

稱P’為P的對偶命題，則P’對任意格也是為真的命題。例如：

P:a∧b≤a{a,b}的最大下界≤a

由對偶原理P’:a∨b≥a{a,b}的最小上界≥a三.格的性質(zhì)<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。a,b,c,d∈A1.a≤a∨b,b≤a∨b,a∧b≤a,a∧b≤b

此性質(zhì)由運(yùn)算∨和∧的定義直接得證。62.如果a≤b，c≤d，則a∨c≤b∨d，a∧c≤b∧d。證明：如果a≤b，又b≤b∨d,由傳遞性得a≤b∨d,類似由c≤d，d≤b∨d，由傳遞性得c≤b∨d,這說明b∨d是a,c的一個(gè)上界而a∨c是a,c的最小上界所以

a∨c≤b∨d。類似可證a∧c≤b∧d。推論：在一個(gè)格中，任何a,b,c∈A，如果b≤c，則

a∨b≤a∨c，a∧b≤a∧c。

此性質(zhì)稱為格的保序性。3.∨和∧都滿足交換律。即

a∨b=b∨a，a∧b=b∧a。

此性質(zhì)由運(yùn)算∨和∧的定義直接得證。74.∨和∧都滿足結(jié)合律。即

(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)。

證明：⑴先證明(a∨b)∨c≤a∨(b∨c)∵a≤a∨(b∨c),且b≤b∨c≤a∨(b∨c)∴(a∨b)≤a∨(b∨c)∵c≤b∨c≤a∨(b∨c)∴(a∨b)∨c≤a∨(b∨c)

⑵同理可證a∨(b∨c)≤(a∨b)∨c最后由反對稱性得(a∨b)∨c=a∨(b∨c)

類似可證(a∧b)∧c=a∧(b∧c)。5.∨和∧都滿足冪等律。即a∨a=a,a∧a=a證明：由性質(zhì)1得a≤a∨a(再證a∨a≤a)

又≤自反得a≤a,這說明a是a的上界,

而a∨a是a的最小上界,所以a∨a≤a。

最后由反對稱性得a∨a=a。由對偶原理得a∧a=a86.

∨和∧都滿足吸收律。即

a∨(a∧b)=a，a∧(a∨b)=a。證明：⑴顯然有a≤a∨(a∧b)⑵再證a∨(a∧b)≤a∵a≤aa∧b≤a∴a∨(a∧b)≤a最后由反對稱得a∨(a∧b)=a，類似可證a∧(a∨b)=a。97.

∨和∧不滿足分配律。但有分配不等式：

a∨(b∧c)≤(a∨b)∧(a∨c)，

(a∧b)∨(a∧c)≤a∧(b∨c)。我們先看右圖的例子：

d∨(b∧e)=d∨c=d(d∨b)∧(d∨e)=a∧e=e而d≤e即

d∨(b∧e)≤(d∨b)∧(d∨e)證明：⑴∵a≤a∨ba≤a∨c∴a≤(a∨b)∧(a∨c)∵b∧c≤b≤a∨b,b∧c≤c≤a∨c∴b∧c≤(a∨b)∧(a∨c)于是有a∨(b∧c)≤(a∨b)∧(a∨c)由對偶原理得a∧(b∨c)≥(a∧b)∨(a∧c)。

即(a∧b)∨(a∧c)≤a∧(b∨c)。

c

ab

e

d108.a≤ba∧b=a

a∨b=b證明：⑴先證明a≤ba∧b=a

先證a≤b

a∧b=a

由a≤b，又a≤a所以a≤a∧b

又由a∧b的定義有a∧b≤a由反對稱得a∧b=a

再證

a∧b=a

a≤b

由a∧b=a則a=a∧b≤b。

綜上得a≤ba∨b=b⑵下面證明a≤ba∨b=b

先證a≤b

a∨b=b

由a≤b，又b≤b所以a∨b≤b

又因?yàn)閎≤a∨b由反對稱得a∨b=b

再證

a∨b=b

a≤b

由a∨b=b因a≤a∨b所以a≤b。

綜上得a≤ba∨b=b11四.格的同態(tài)與同構(gòu)1.定義：設(shè)<A1,≤1>和<A2,≤2>是兩個(gè)格，由它們誘導(dǎo)的代數(shù)系統(tǒng)分別是<A1,∨1,∧1>和

<A2,∨2,∧2>如果存在映射f:A1A2使得對任何a,b∈A1,有

f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)則稱f是從<A1,∨1,∧1>到

<A2,∨2,∧2>的格同態(tài)。也稱<f(A1),≤2>是<A1,≤1>的格同態(tài)像。如果f是雙射的,就稱f是<A1,∨1,∧1>到

<A2,∨2,∧2>的格同構(gòu),也稱格<A1,≤1>和<A2,≤2>同構(gòu)。12例如<A,≤>,A={1,2,3,6},≤是A上整除關(guān)系。

<P(E),>,E={a,b}它們誘導(dǎo)的代數(shù)系統(tǒng)分別是<A,∨,∧>和<P(E),∪,∩>其中∨和∧分別是求兩個(gè)數(shù)的最小公倍數(shù)和最大公約數(shù).f(2∨3)=f(6)={a,b}f(2)∪f(3)={a}∪={a,b}f(2∧3)=f(1)=Φf(2)∩f(3)={a}∩=Φf(2∨6)=f(6)={a,b}f(2)∪f(6)={a}∪{a,b}={a,b}f(2∧6)=f(2)={a}f(2)∪f(6)={a}∪{a,b}={a}可見它們同構(gòu)。格同構(gòu)，它們的哈斯圖的形狀一定相同。

Φ

{a}

{a,b}

1

32

6f6

3

2

1

{a}

{a,b}

ΦA(chǔ)

P(E)13具有四個(gè)素的格分別同構(gòu)于下面兩種格形式之一：具有五個(gè)素的格分別同構(gòu)于下面五種格形式之一：

d

a

b

c

d

a

b

c

e

c

d

d

a

b

c

e

a

b

c

e

a

b

d

a

e

b

c

d

d

a

b

c

e1411-2幾個(gè)特殊格一.分配格

前面我們介紹一般的格，∧和∨只滿足分配不等式。

a∨(b∧c)≤(a∨b)∧(a∨c)，

(a∧b)∨(a∧c)≤a∧(b∨c)。下面介紹的是滿足分配律的格----分配格。1.定義：<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。如果對a,b,c∈A，有

a∨(b∧c)=(a∨b)∧(a∨c)，

a∧(b∨c)=(a∧b)∨(a∧c)則稱<A,≤>是分配格。152.二個(gè)重要的五元素非分配格

2∧(3∨5)=2∧30=2(2∧3)∨(2∧5)=1∨1=1c∧(b∨d)=c∧a=c(c∧b)∨(c∧d)=e∨d=d可見它們都不是分配格。3.分配格的判定：

一個(gè)格是分配格的充分且必要條件是在該格中沒有任何子格與上述兩個(gè)五元素非分配格之一同構(gòu)。用此方法判定下面兩個(gè)格是不是分配格?

3

1

30

2

5

d

e

a

b

c

4

1

6

3

5

2

f

g

a

d

c

e

b

164.分配格的性質(zhì)1.定理7-2.1.在格中，如果∧對∨可分配，則∨對∧也可分配.反之亦然。證明：設(shè)<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。且∧對∨可分配。任取a,b,c∈A，a∧(b∨c)=(a∧b)∨(a∧c)而(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)分配=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))吸收、分配=(a∨(a∧c))∨(b∧c)結(jié)合=a∨(b∧c)

吸收同理可證:如果∨對∧可分配，則∧對∨也可分配.2.定理11-2.2.所有鏈均為分配格。證明：顯然任何鏈都不會(huì)含有與五元素非分配格之一同構(gòu)的子格，所以鏈必是分配格。173.

定理11-2.3.設(shè)<A,≤>是分配格，對任何a,b,c∈A,如果有a∧b=a∧c及a∨b=a∨c則必有b=c.證明：任取a,b,c∈A,設(shè)有a∧b=a∧c及a∨b=a∨cb=b∨(a∧b)(吸收律)=b∨(a∧c)(代換)=(b∨a)∧(b∨c)(分配)=(a∨b)∧(b∨c)(交換)=(a∨c)∧(b∨c)(代換)=(a∧b)∨c(分配)=(a∧c)∨c(代換)=c(吸收律)18二.有界格1.格的全上界與全下界1).全上界:設(shè)<A,≤>是格，如果存在元素a∈A對任何x∈A,x≤a,則稱a是格的全上界,記作1。(即是A的最大元)定理7-2.4一個(gè)格如果有全上界，則是唯一的。(我們已證明過，最大元如果有，則是唯一的)2).全下界:設(shè)<A,≤>是格，如果存在元素a∈A對任何x∈A,a≤x,則稱a是格的全下界,記作0。(即是A的最小元)定理11-2.5一個(gè)格如果有全下界，則是唯一的。從格的圖形看：全上界1，就是圖的最上邊元素(只一個(gè))，全下界0，就是圖的最下邊元素(只一個(gè))。

b

0

1

a

c

1

c

0192.有界格定義：如果一個(gè)格存在全上界1與全下界0，則稱此格為有界格。設(shè)<A,≤>是有界格，則對任何a∈A,有因?yàn)閍≤1,所以a∧1=aa∨1=10≤a所以a∧0=0a∨0=a是否所有格都是有界格？所有有限個(gè)元素的格都是有界格而無限個(gè)元素的格可能是無界格。例如<I,≤>就是既無全上界與全下界。20三.有補(bǔ)格回顧：集合的補(bǔ)集，若A∪B=EA∩B=Φ則~A=B，~B=A如E={a,b}~E=Φ~Φ=E~{a}=,~={a}1.元素的補(bǔ)元設(shè)<A,≤>是個(gè)有界格，a∈A,如果存在b∈A,使得

a∨b=1和a∧b=0則稱a與b互為補(bǔ)元。例：右邊的格中

a的補(bǔ)元：c,eb的補(bǔ)元：

無

c的補(bǔ)元：a,dd的補(bǔ)元：ce的補(bǔ)元：a0的補(bǔ)元：11的補(bǔ)元：0

Φ

{a,b}

{a}



e

0

1

b

c

d

a

212.有補(bǔ)格的定義一個(gè)有界格中,如果每個(gè)元素都有補(bǔ)元,則稱之為有補(bǔ)格.上述有界格中，哪些是有補(bǔ)格？上述有補(bǔ)格中，有些元素的補(bǔ)元不唯一，如(2)中的b,那么什么樣的格中元素的補(bǔ)元唯一呢？

--------------有界分配格。請看下面定理：

Φ

{a,b}

{a}



b

0

1

a

c

e

0

1

b

c

d

a

1

c

0(1)(2)(3)(4)22定理11－2.6在有界分配格中，如果元素有補(bǔ)元，則補(bǔ)元是唯一的。證明：設(shè)<A,≤>是有界分配格，任取a∈A,假設(shè)a有兩個(gè)補(bǔ)元b和c，則

a∧b=0,a∨b=1及a∧c=0,a∨c=1于是有，a∧b=a∧ca∨b=a∨c由分配格的定理11－2.3得b=c∴a的補(bǔ)元是唯一的。四.布爾格

如果一個(gè)格既是分配格又是有補(bǔ)格，則稱之為布爾格。布爾格中每個(gè)元素都有唯一補(bǔ)元，元素a的補(bǔ)元記作顯然<P(E),

>是布爾格。2311－3布爾代數(shù)BooleanAlgebra一.定義由布爾格<B,≤>誘導(dǎo)的代數(shù)系統(tǒng)<B,∨,∧,ˉ>稱之為布爾代數(shù)。其中ˉ是取補(bǔ)元運(yùn)算。如果B是有限集合，則稱它是有限布爾代數(shù)。例如：令B＝{F,T}，∧表示合取，∨析取，

否定,<B,∨,∧,

>就是個(gè)布爾代數(shù)。如上圖所示。

<P(E),∪,∩,~>也是個(gè)布爾代數(shù)。如下圖所示。

T

F

Φ

{a,b}

{a}

24二.布爾代數(shù)的性質(zhì)設(shè)<B,∨,∧,ˉ>布爾代數(shù),任意x,y,z∈B,有⑴交換律x∨y=y∨xx∧y=y∧x⑵結(jié)合律x∨(y∨z)=(x∨y)∨zx∧(y∧z)=(x∧y)∧z

⑶冪等律x∨x=xx∧x=x

⑷吸收律x∨(x∧y)=xx∨(x∧y)=x⑸分配律x∨(y∧z)=(x∨y)∧(x∨z)

x∧(y∨z)=(x∧y)∨(x∧z)⑹同一律x∨0=xx∧1=x

⑺零律x∨1=1x∧0=0

⑻互補(bǔ)律

⑼對合律⑽底－摩根定律25上述性質(zhì)都可以由格，分配格,有界格，布爾格得到。下面只證明底－摩根定律。所以類似可證另一個(gè)。26三.布爾代數(shù)的同構(gòu)1.定義：令<B1,∨1,∧1,ˉ>和

<B2,∨2,∧2,~>是兩個(gè)布爾代數(shù)，如果存在映射f:B1B2,對任何a,b∈B1,有

f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)則稱f是<B1,∨1,∧1,ˉ>到<B2,∨2,∧2,~>的同態(tài)映射。若f是雙射,則稱f是<B1,∨1,∧1,ˉ>到<B2,∨2,∧2,~>的同構(gòu)映射。

與格同構(gòu)比較,多了一個(gè)關(guān)于補(bǔ)運(yùn)算的同構(gòu)關(guān)系等式.為了引出有限布爾代數(shù)的Stone的定理，下面介紹原子的概念。