第8章格與布爾代數(shù)8.1格8.2布爾代數(shù)返回總目錄第8章

格與布爾代數(shù)

8.1格8.1.1格的概念和性質(zhì)

定義8.1.1

設(shè)

X,?

是偏序集，如果

x,y

X，集合

x,y

都有最小上界和最大下界，則稱

X,?

是格?！纠?.1】設(shè)S12＝

1,2,3,4,6,12

是12的因子構(gòu)成的集合。其上的整除關(guān)系R=

x,y

|x

S12∧y

S12∧x整除y

，R是S12上的偏序關(guān)系，

S12,R

是偏序集。寫出S12上的蓋住關(guān)系COVS12，畫出哈斯圖，驗證偏序集

S12,R

是格。解：S12上的蓋住關(guān)系

COVS12＝

1,2

,

1,3

,

2,4

,

2,6

,

3,6

,

4,12

,

6,12

，哈斯圖如圖8.1所示。從哈斯圖中可看出，集合S12的任意兩個元素都有最小上界和最大下界，故偏序集

S12,R

是格。

【例8.2】圖8.2中給出了一些偏序集的哈斯圖，判斷它們是否構(gòu)成格。解：它們都不是格。在(a)中，

1,2

沒有下界，因而沒有最大下界。在(b)中，

2,4

雖有兩個上界，但沒有最小上界。在(c)中，

1,3

沒有下界，因而沒有最大下界。在(d)中，

2,3

雖有三個上界，但沒有最小上界。設(shè)

X,?

是格，

x,y

X，今后用x∨y表示集合

x,y

的最小上界，二元運算∨稱為并運算；用x∧y表示集合

x,y

的最大下界，二元運算∧稱為交運算。

定義8.1.2設(shè)

X,?

是格，∨是X上的并運算，∧是X上的交運算。則稱

X,∨,∧

是格

X,?

導(dǎo)出的代數(shù)系統(tǒng)。在例4.28中，根據(jù)圖4.14，集合

a

,

b

的最小上界為

a,b

，即

a

∨

b

=

a,b

=

a

∪

b

；它的最大下界為?，即

a

∧

b

=?=

a

∩

b

。這個結(jié)果可以推廣到一般情況。

x,y

P

(A)，x∨y=x∪y，x∧y=x∩y。這樣，格

P(A),R

導(dǎo)出的代數(shù)系統(tǒng)

P(A),∨,∧

實際就是代數(shù)系統(tǒng)

P(A),∪,∩

，所以，二元運算∨和∧的運算表如表8.1和表8.2所示。在例8.1中，根據(jù)圖8.1，集合

4,6

的最小上界為12，即4∨6=12=4和6的最小公倍數(shù)；它的最大下界為2，即4∧6=2=4和6的最大公約數(shù)。同樣，這個結(jié)果也可以推廣到一般情況。即在格

S12,R

導(dǎo)出的代數(shù)系統(tǒng)

S12,∨,∧

中，二元運算∨是求最小公倍數(shù)；二元運算∧是求最大公約數(shù)。

表8.1

表8.2∨?

a

??

a

b

b

a,b

a

a

a

a,b

a,b

a,b

b

b

a,b

a,b

a,b

a,b

a,b

b

a,b

a,b

∧?

a

b

a,b

?????

a

?

a

?

a

b

??

b

b

a,b

?

a

b

a,b

下面介紹格的對偶原理。設(shè)

X,?

是偏序集，在X上定義二元關(guān)系?=

a,b

|

b,a

?

可以證明

X,?

也是偏序集。

定義8.1.3

設(shè)f是含有格中元素以及符號=,?,?,∨和∧的命題。將f中的?替換成?，?替換成?，∨替換成∧，∧替換成∨，得到一個新命題，所得的命題叫做f的對偶命題，記為f*。

例如，在格中，f為a∧(b∨c)?a，則f的對偶命題f*為a∨(b∧c)?a

命題f和它的對偶命題f*遵循下列的規(guī)則，這規(guī)則叫做格的對偶原理。設(shè)f是含有格中元素以及符號=,?,?,∨和∧的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。格的許多性質(zhì)都是互為對偶命題的。有了格的對偶原理，在證明格的性質(zhì)時，只需證明其中的一個就可以了。

定理8.1.1設(shè)

X,?

是格，

X,∨,∧

是格

X,?

導(dǎo)出的代數(shù)系統(tǒng)。則

a,b,c

X有⑴a∨b=b∨a，a∧b=b∧a(交換律)⑵(a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c)(結(jié)合律)⑶a∨a=a，a∧a=a(冪等律)⑷a∨(a∧b)=a

a∧(a∨b)=a

(吸收律)證明：⑴

a,b

X，

a,b

=

b,a

，所以它們的最小上界相等。即a∨b=b∨a，同理可證a∧b=b∧a⑵a和b的最大下界一定是a、b的下界，即a∧b?a，同理，(a∧b)∧c?a∧b，所以，(a∧b)∧c?a∧b?a

同理有(a∧b)∧c?a∧b?b

和(a∧b)∧c?c由以上3式得(a∧b)∧c?b∧c和(a∧b)∧c?a∧(b∧c)類似地可證a∧(b∧c)?(a∧b)∧c根據(jù)偏序關(guān)系的反對稱性有(a∧b)∧c=a∧(b∧c)

由對偶原理得(a∨b)∨c=a∨(b∨c)⑶顯然a?a∨a，又由?的自反性得a?a，從而推出a∨a?a，根據(jù)偏序關(guān)系的反對稱性有a∨a=a

由對偶原理得a∧a=a⑷顯然a?a∨(a∧b)，

又由a?a，a∧b?a得a∨(a∧b)?a，從而得

a∨(a∧b)=a。

由對偶原理得a∧(a∨b)=a

定理8.1.2

設(shè)

X,∨,∧

是代數(shù)系統(tǒng)，其中∨,∧都是二元運算。如果∨和∧滿足吸收律，則∨和∧滿足冪等律。證明：a∨a=a∨(a∧(a∨b))=a，同理可證a∧a=a

定理8.1.3

設(shè)

X,∨,∧

是代數(shù)系統(tǒng)，其中∨,∧都是二元運算，滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義X的偏序關(guān)系?，使

X,?

構(gòu)成一個格。證明：定義X上的一個二元關(guān)系

?=

a,b

|a,b

X且a∧b=a

⑴證明?是X上的偏序關(guān)系。由定理8.1.2知∧滿足冪等律，即a∧a=a，所以a?a。故?是自反的。設(shè)a?b且b?a，則a∧b=a且b∧a=b，于是a=a∧b=b∧a=b。所以?是反對稱的。設(shè)a?b且b?c，則a∧b=a且b∧c=b，于是a∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a，即a?c，故?是傳遞的。這就證明了?是X上的偏序關(guān)系。⑵證明

a,b

X，a∧b是集合

a,b

的最大下界。因為(a∧b)∧a=a∧b和(a∧b)∧b=a∧b所以a∧b?a且a∧b?b，即a∧b是

a,b

的下界。下證a∧b是

a,b

的最大下界。設(shè)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，即a∧b是

a,b

的最大下界。⑶

證明a∧b=a的充分必要條件是a∨b=b

設(shè)a∧b=a，由吸收率可得

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

設(shè)a∨b=b，由吸收率可得

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

⑷

證明

a,b

X，a∨b是集合

a,b

的最小上界。根據(jù)⑶，偏序關(guān)系?可以等價的定義為：

?=

a,b

|a,b

X且a∨b=b

，用這個定義和類似于⑵的方法可以證明a∨b是集合

a,b

的最小上界。因此，

X,?

構(gòu)成一個格。根據(jù)定理8.1.3，可以給出格的另一個等價定義。

定義8.1.4

設(shè)

X,*,°

是代數(shù)系統(tǒng)，其中*和°都是二元運算，如果*和°在X上封閉且滿足交換律、結(jié)合律和吸收律，則稱

X,*,°

為格。根據(jù)定義8.1.4和定理8.1.1，格

X,?

導(dǎo)出的代數(shù)系統(tǒng)

X,∨,∧

是格，以后不再區(qū)分偏序集定義的格和代數(shù)系統(tǒng)定義的格，統(tǒng)稱為格。

定理8.1.4

設(shè)

X,?

是格，∨是X上的并運算，∧是X上的交運算。則

a,b

X有⑴a?b當(dāng)且僅當(dāng)a∧b=a

⑵a?b當(dāng)且僅當(dāng)a∨b=b

證明：⑴設(shè)a?b，下證a∧b=a

由a?a且a?b知a是集合

a,b

的下界，故有a?a∧b；另一方面，由于a∧b是

a,b

的最大下界，所以是

a,b

的下界，即a∧b?a。根據(jù)偏序關(guān)系的反對稱性得a∧b=a

設(shè)a∧b=a，下證a?ba=a∧b?b，即a?b⑵可類似⑴進行證明。定理8.1.5

設(shè)

X,?

是格，∨是X上的并運算，∧是X上的交運算。

a,b,c,d

X，若a?b且c?d，則a∨c?b∨d，a∧c?b∧d

證明：

a?b?b∨d，c?d?b∨d，因此a∨c?b∨d

類似的可以證明a∧c?b∧d

定理8.1.6

設(shè)

X,?

是格，∨是X上的并運算，∧是X上的交運算。則

a,b,c

X有⑴a∨(b∧c)?(a∨b)∧(a∨c)⑵(a∧b)∨(a∧c)?

a∧(b∨c)

證明：⑴根據(jù)定理8.1.5，由a?a和b∧c?b得

a∨(b∧c)?a∨b

又由a?a且b∧c?c得

a∨(b∧c)?a∨c

從而得到a∨(b∧c)?(a∨b)∧(a∨c)

利用對偶原理，即得⑵。一般地說，格中的∨和∧并不滿足分配律。

8.1.2子格和格的同態(tài)

定義8.1.5

設(shè)

X,∨,∧

是格，B是X的非空子集，如果B關(guān)于運算∨和∧也構(gòu)成格，則稱

B,∨,∧

是

X,∨,∧

的子格。在例8.1中，令B1＝

1,2,3,6

，B2＝

2,4,6,12

，則

B1,∨,∧

和

B2,∨,∧

是格

S12,∨,∧

的子格。令B3＝

1,2,3,12

，由于2∨3=6，而6

B3，所以

B3,∨,∧

不是格

S12,∨,∧

的子格。以下定義格的同態(tài)。

定義8.1.6設(shè)

X1,∨1,∧1

和

X2,∨2,∧2

是格，其中∨1,∧1,∨2和∧2都是二元運算。f是從X1到X2的一個映射，對任意的a,b

X1有f(a∨1b)=f(a)∨2f(b)，

f(a∧1b)=f(a)∧2f(b)則稱f是格

X1,∨1,∧1

到格

X2,∨2,∧2

的格同態(tài)。如果f是單射、滿射和雙射，分別稱f是格單同態(tài)、格滿同態(tài)和格同構(gòu)。稱

f(X1),∨2,∧2

是

X1,∨1,∧1

的格同態(tài)像。定理8.1.7設(shè)

X1,?1

和

X2,?2

是格，

X1,∨1,∧1

和

X2,∨2,∧2

是它們導(dǎo)出的代數(shù)系統(tǒng)。f是格

X1,∨1,∧1

到格

X2,∨2,∧2

的格同態(tài)，則

a,b

X1，如果a?1b，必有f(a)?2f(b)

證明：設(shè)a?1b，根據(jù)定理8.1.4，a∧1b=a，由于f是格

X1,∨1,∧1

到格

X2,∨2,∧2

的格同態(tài)，所以f(a)=f(a∧1b)=f(a)∧2f(b)，再由定理8.1.4，f(a)?2f(b)。

定理8.1.7說明格同態(tài)是保序的。一般地說，定理8.1.7的逆并不成立。【例8.3】設(shè)A=

a,b,c,d,e

，

A,?

是格，其哈斯圖如圖8.3所示，P(A)是A的冪集合，R

=

x,y

|x

P(A)∧y

P

(A)∧x

y

是P(A)上的偏序關(guān)系。

P(A),R

也是格。作映射f：A→P(A)，定義為：

x

A，f(x)=

y|y

A且y?x，即：f(a)=

a,b,c,d,e

=A，f(b)=

b,e

，f(c)=

c,e

，f(d)=

d,e

，f(e)=

e

。證明f是保序的，但不是格同態(tài)。證明：

a,b

A，設(shè)a?b，

c

f(a)，c?a，由偏序關(guān)系的傳遞性得c?b，所以c

f(b)，即f(a)

f(b)，于是f(a)R

f(b)。故f是保序的。對于b,d

A，b∨d=af(b∨d)=f(a)=A

f(b)∪f(d)=

b,e

∪

d,e

=

b,d,e

f(b∨d)≠f(b)∪f(d)f不是格同態(tài)。但是，當(dāng)f是格同構(gòu)時，定理8.1.7的逆成立。定理8.1.8

設(shè)

X1,?1

和

X2,?2

是格，

X1,∨1,∧1

和

X2,∨2,∧2

是它們導(dǎo)出的代數(shù)系統(tǒng)。f是X1到X2的雙射，則f是

X1,∨1,∧1

到

X2,∨2,∧2

的格同構(gòu)的充分必要條件是

a,b

X1，a?1b

f(a)?2f(b)

證明：設(shè)f是

X1,∨1,∧1

到

X2,∨2,∧2

的格同構(gòu)，下證

a,b

X1，a?1b

f(a)?2f(b)

由定理8.1.7可知，

a,b

X1，如果a?1b，必有f(a)?2f(b)

設(shè)f(a)?2f(b)，由定理8.1.4有f(a)=f(a)∧2f(b)=f(a∧1b)，由于f是雙射，故a∧1b=a，所以a?1b

這就證明a?1b

f(a)?2f(b)

設(shè)

a,b

X1，a?1b

f(a)?2f(b)，下證f是

X1,∨1,∧1

到

X2,∨2,∧2

的格同構(gòu)。設(shè)a∧1b=c，則c?1a，c?1b，f(c)=f(a∧1b)，f(c)?2f(a)，f(c)?2f(b)，故f(c)?2f(a)∧2f(b)。

設(shè)f(a)∧2f(b)=f(d)，則有f(c)?2f(a)∧2f(b)=f(d)，即f(c)?2f(d)；還有f(d)?2f(a)和f(d)?2f(b)。所以有d?1a和d?1b，于是d?1a∧1b，即d?1c，故f(d)?2f(c)，再由偏序關(guān)系的反對稱性有f(c)=f(d)。即f(a∧1b)=f(c)=f(d)=f(a)∧2f(b)

類似地可以證明f(a∨1b)=f(a)∨2f(b)

這就證明了f是

X1,∨1,∧1

到

X2,∨2,∧2

的格同構(gòu)。

定義8.1.7

設(shè)

X1,?1

和

X2,?2

是格，

X1,∨1,∧1

和

X2,∨2,∧2

是它們導(dǎo)出的代數(shù)系統(tǒng)。其中∨1,∧1,∨2和∧2都是二元運算。

a1,b1

X1×X2和

a2,b2

X1×X2，定義X1×X2上的二元運算∨3和∧3為：

a1,b1

∨3

a2,b2

=

a1∨1a2,b1∨2b2

a1,b1

∧3

a2,b2

=

a1∧1a2,b1∧2b2

代數(shù)系統(tǒng)

X1×X2,∨3,∧3

稱為格

X1,∨1,∧1

到格

X2,∨2,∧2

的直積。如果

X1,∨1,∧1

和

X2,∨2,∧2

是格，可以證明代數(shù)系統(tǒng)

X1×X2,∨3,∧3

也是格8.1.3分配格

定義8.1.8

設(shè)

X,?

是格，

X,∨,∧

是

X,?

導(dǎo)出的代數(shù)系統(tǒng)，如果

a,b,c

X有

a∨(b∧c)=(a∨b)∧(a∨c)(并運算對交運算可分配)

a∧(b∨c)=(a∧b)∨(a∧c)(交運算對并運算可分配)則稱

X,∨,∧

為分配格。因為a∨(b∧c)=(a∨b)∧(a∨c)和

a∧(b∨c)=(a∧b)∨(a∧c)互為對偶命題，根據(jù)對偶原理，定義8.1.8還可以改寫為：一個格如果交運算對并運算可分配或并運算對交運算可分配，則稱該格為分配格。【例8.4】設(shè)A=

a,b,c

，P(A)=

?,

a

,

b

,

c

,

a,b

,

a,c

,

b,c

,

a,b,c

是A的冪集合，P(A)上的包含關(guān)系R

=

x,y

|x

P

(A)∧y

P

(A)∧x

y

是P

(A)上的偏序關(guān)系。

P

(A),R

是偏序集，P(A)上的蓋住關(guān)系

COVP(A)=

?,

a

,

?,

b

,

?,

c

,

a

,

a,b

,

b

,

a,b,a

,

a,c

,

c

,

a,c

,

b

,

b,c

,

c

,

b,c

,

a,b

,

a,b,c

,

a,c

,

a,b,c

,

b,c

,

a,b,c

其哈斯圖如圖8.4所示。

P

(A),∨,∧

是

P(A),R

導(dǎo)出的代數(shù)系統(tǒng)，證明

P(A),∨,∧

是分配格。

證明：前面已經(jīng)證明了格

P(A),R

導(dǎo)出的代數(shù)系統(tǒng)

P

(A),∨,∧

實際就是代數(shù)系統(tǒng)

P(A),∪,∩

，其中∪是集合的并運算，∩是集合的交運算。而集合的并、交運算滿足分配律：

P,Q,R

P

(A)

P∪(Q∩R)=(P∪Q)∩(P∪R)P∩(Q∪R)=(P∩Q)∪(P∩R)所以，

P

(A),∨,∧

分配格?！纠?.5】A=

a,b,c,d,e

，

A,?

是格，其哈斯圖如圖8.3所示，證明

A,?

不是分配格。

證明：

b∨(c∧d)=b∨e=b

(b∨c)∧(b∨d)=a∧a=a b∨(c∧d)≠(b∨c)∧(b∨d)

所以，

A,?

不是分配格。

本例中的格叫做鉆石格，鉆石格不是分配格。

【例8.6】設(shè)A=

a,b,c,d,e

，

A,?

是格，其哈斯圖如圖8.5所示，證明

A,?

不是分配格。證明：d∨(b∧c)=d∨e=d(d∨b)∧(d∨c)=a∧c=cd∨(b∧c)≠(d∨b)∧(d∨c)所以，

A,?

不是分配格。本例中的格叫做五角格，五角格也不是分配格。鉆石格和五角格是兩個很重要的格。

定理8.1.9一個格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。這個定理的證明已經(jīng)超過了本書的范圍，故略去。推論1設(shè)

A,?

是格，如果|A|＜5，則

A,?

一定是分配格。

推論2設(shè)

A,?

是格，如果

A,?

是全序集，則

A,?

一定是分配格。【例8.7】圖8.6給出了兩個格的哈斯圖。試證明它們都不是分配格。證明：在圖8.6

(a)中含有與五角格同構(gòu)的子格，所以不是分配格；在圖8.6

(b)中含有與鉆石格同構(gòu)的子格，所以不是分配格。

定理8.1.10

設(shè)

X,?

是格，

X,∨,∧

是格

X,?

導(dǎo)出的代數(shù)系統(tǒng)。

X,?

是分配格的充分必要條件是

a,b,c

X，當(dāng)a∧b=a∧c且a∨b=a∨c時，必有b=c

證明：設(shè)

X,?

是分配格，

a,b,c

X，a∧b=a∧c且a∨b=a∨cb=b∨(b∧a)=b∨(a∧b)

(吸收律和交換律)=b∨(a∧c)=(b∨a)∧(b∨c)(已知代入和分配律)=(a∨c)∧(b∨c)(交換律和已知代入)=(a∧b)∨c

(分配律)=(a∧c)∨c

(已知條件代入)=c

(交換律和吸收律) 設(shè)

a,b,c

X，當(dāng)a∧b=a∧c且a∨b=a∨c時，有b=c，但

X,∨,∧

不是分配格。由定理8.1.9知

X,∨,∧

中必含有與鉆石格或五角格同構(gòu)的子格。假設(shè)

X,∨,∧

含有與鉆石格同構(gòu)的子格，且此子格為

S,∨,∧

，其中S=

u,v,x,y,z

，u為它的最大元，v為它的最小元。從而x∨y=u=x∨z，x∧y=v=x∧z，但y≠z，與已知矛盾。對五角格的情況，可類似證明。例如，在圖8.6(a)中，b∧c=g=b∧f且b∨c=a=b∨f，但c≠f；在圖8.6(b)中，b∧c=f=b∧e且b∨c=a=b∨e，但c≠e。根據(jù)定理8.1.10它們不是分配格。8.1.4有補格

定義8.1.9

設(shè)

X,?

是格，如果

a

X，

x

X都有

a?x(x?a)則稱a為格

X,?

的全下(上)界，記為0(1)。

定理8.1.11設(shè)

X,?

是格，若格

X,?

有全下界或全上界，則它們一定是惟一的。

證明：用反證法。如果有兩個全下界a和b，a,b

X。因為a是全下界，所以a?b；又因為b是全下界，所以b?a。再由?的反對稱性有a=b

類似地可證明全上界的惟一性。

定義8.1.10設(shè)

X,?

是格，

X,∨,∧

是格

X,?

導(dǎo)出的代數(shù)系統(tǒng)。若格

X,∨,∧

存在全下界0和全上界1，則稱

X,∨,∧

為有界格，記為

X,∨,∧,0,1

。

在例8.4中，

P(A),R

是格。

P

(A),∨,∧

是

P(A),R

導(dǎo)出的代數(shù)系統(tǒng)。空集?是格的全下界，而集合A是格的全上界。因而

P

(A),∨,∧

是有界格，可記為

P(A)∨,∧,?,A

。在例8.6中，從哈斯圖(圖8.5)中可以看出，a是全上界，而e是全下界，所以

A,?

是有界格。

定理8.1.12設(shè)

X,∨,∧,0,1

為有界格，則

a

X有

a∧0=0，a∨0=aa∧1=a，a∨1=1

證明：因為0是全下界且a∧0

X，所以0?a∧0，又因為a∧0?0，由?的反對稱性有a∧0=0

顯然a?a，由于1是全上界，所以有a?1，從而推出a?a∧1，又因為a∧1?a，再由?的反對稱性有a∧1=aa∨0=a

和a∨1=1可以類似地證明。設(shè)

X,∨,∧,0,1

為有界格，a

X有a∧0=0，因為格滿足交換律，所以0∧a=0，這說明0是交運算的零元；同樣的道理，0是并運算的幺元，而1是交運算的幺元和并運算的零元。

定義8.1.11設(shè)

X,∨,∧,0,1

為有界格，如果對于a

X，

b

X，使得a∨b=1且a∧b=0，則稱b是a的補元。如果b是a的補元，從定義8.1.11可以看出，a也是b的補元。因此，可以說a和b是互補的，或者說a和b互為補元。例如，在例8.6中，從哈斯圖(圖8.5)中可以看出，b和c互為補元，b和d也互為補元，b有兩個補元c和d。所以格中元素的補元并不惟一。【例8.8】圖8.7是一個有界格的哈斯圖。找出a,b,c,d,e的補元。解：從圖8.7中可以看出，a的補元是e；b沒有補元；c的補元是d；d的補元是c和e，e的補元是a和d，0和1互為補元。顯然，在有界格中，全上界1的惟一補元是全下界0，而全下界0的惟一補元是全上界1。除了1和0，其它元素有的有補元，有的沒有補元。如果某個元素的補元存在，補元可能有一個，也可能有多個。但在有界分配格中，如果元素的補元存在，則一定惟一。

定理8.1.13設(shè)

X,∨,∧,0,1

為有界分配格，如果對于a

X，a存在補元b，則b是a的惟一補元。證明：因為b是a的補元，所以有a∨b=1，a∧b=0

設(shè)c

X，c是a的另一個補元，同樣也有a∨c=1，a∧c=0

從而有a∨b=a∨c，a∧b=a∧c

由于

X,∨,∧,0,1

為分配格，根據(jù)定理8.1.10必有b=c，即a的補元惟一。

定義8.1.12設(shè)

X,∨,∧,0,1

為有界格，如果

a

X，在X中都有a的補元存在，則稱

X,∨,∧,0,1

為有補格例如，圖8.8是三個有界格的哈斯圖，由于每一個元素至少有一個補元，所以它們都是有補格。返回章目錄8.2布爾代數(shù)

定義8.2.1

有補分配格稱為布爾格。在布爾格中每一個元素都有補元。因為有補格一定是有界格，所以布爾格一定是有界分配格，根據(jù)定理8.1.13，布爾格中的每一個元素的補元存在且惟一。于是可以將求補元的運算看作一元運算且把a的補元記為a′。

定義8.2.2設(shè)

X,?

是布爾格，

X,∨,∧,′

是格

X,?

導(dǎo)出的代數(shù)系統(tǒng)。稱代數(shù)系統(tǒng)

X,∨,∧,′

為布爾代數(shù)。在8.1節(jié)中證明了

P

(A),R

是格，其中A=

a,b

。

P

(A),∪,∩

是

P

(A),R

導(dǎo)出的代數(shù)系統(tǒng)，其中∪和∩是集合并運算和交運算。以后又進一步說明了

P

(A),∪,∩

是分配格和有界格，?是全下界、A是全上界。從而

P(A),∪,∩

是有界分配格。令A(yù)為全集，

T

P

(A)，T的補集~T=A–T

P

(A)，滿足T∪~T=A和T∩~T=?，所以T的補元T′=~T。根據(jù)定義8.2.2，

P(A),∪,∩,~

是布爾代數(shù)。

可以證明，當(dāng)A為任意集合時，

P(A),∪,∩,~

也是布爾代數(shù)。稱為集合代數(shù)。集合代數(shù)是布爾代數(shù)的一個具體模型。布爾代數(shù)一定是格。根據(jù)定理8.1.1，布爾代數(shù)中的兩個二元運算滿足交換律、結(jié)合律、冪等律和吸收律。此外，布爾代數(shù)還有下面的性質(zhì)：

定理8.2.1

設(shè)

X,∨,∧,′

為布爾代數(shù)，

a,b

X，必有⑴(a′)′=a⑵(a∨b)′=a′∧b′

⑶(a∧b)′=a′∨b′

證明：⑴a′是a的補元，a也是a′的補元，由布爾代數(shù)中補元的惟一性有(a′)′=a⑵(a∨b)∨(a′∧b′)=((a∨b)∨a′)∧((a∨b)∨b′)=(b∨(a∨a′))∧(a∨(b∨b′))=(b∨1)∧(a∨1)=1∧1=1(a∨b)∧(a′∧b′)=(a∧(a′∧b′))∨(b∧(a′∧b′))=((a∧a′)∧b′)∨((b∧b′)∧a′)=(0∧b′)∨(0∧a′)=0∨0=0所以(a∨b)′=a′∧b′⑶同理可證(a∧b)′=a′∨b′

定理8.2.1中的⑴稱為雙重否定律，⑵和⑶稱為德摩根律。布爾代數(shù)滿足雙重否定律和德摩根律。

定理8.2.2

設(shè)

X,*,°,′

是代數(shù)系統(tǒng)，其中*和°都是二元運算，′是一元運算。

X,*,°,′

是布爾代數(shù)的充分必要條件是：⑴*和°在X上封閉且滿足交換律。⑵*和°滿足分配律(滿足*對°的分配律和°對*的分配律)。⑶X中存在運算*的幺元和運算°的幺元。設(shè)運算*的幺元為0，運算°的幺元為1。即

a

X，有a*0=a，a°1=a⑷

a

X，

a′

X，使得a*a′=1，a°a′=0

由于篇幅的限制，證明從略。定理8.2.2給出的四個條件可以作為布爾代數(shù)的等價定義。布爾代數(shù)

X,*,°,′

也可以表示成為

X,*,°,′,0,1

，其中0是運算*的幺元，1是運算°的幺元。【例8.9】設(shè)P是所有命題構(gòu)成的集合，∨,∧和?分別是命題的析取、合取和否定聯(lián)結(jié)詞。證明代數(shù)系統(tǒng)

P,∨,∧,?

是布爾代數(shù)。證明：根據(jù)第1章的內(nèi)容，∨和∧在P上封閉且滿足交換律、分配律。命題常元0(假)和1(真)是集合P的元素，滿足

q

P，q∨0=q，q∧1=q。

q

P，?q

P，滿足q∨?q=1，q∧?q=0。

根據(jù)定理8.2.2，

P,∨,∧,?

是布爾代數(shù)。例8.9中的布爾代數(shù)

P,∧,∨,?

叫做命題代數(shù)，它是布爾代數(shù)的又一個模型。8.2.2布爾代數(shù)的子代數(shù)和同態(tài)

定義8.2.3

設(shè)

X,∨,∧,′,0,1

是布爾代數(shù)，B是X的非空子集，若0,1

B且

B,∨,∧,′,0,1

也是布爾代數(shù)。則稱

B,∨,∧,′,0,1

是

X,∨,∧,′,0,1

子布爾代數(shù)。

定理8.2.3

設(shè)

X,∨,∧,′,0,1

是布爾代數(shù)，B是X的非空子集，若0,1

B且運算∨,∧,′在B上封閉，則

B,∨,∧,′,0,1

是

X,∨,∧,′,0,1

子布爾代數(shù)證明：⑴

a,b

B，因為B

X，所以a,b

X。又因為

X,∨,∧,′,0,1

是布爾代數(shù)，故a∨b=b∨a，a∧b=b∧a⑵類似⑴可以證明*和°滿足分配律。⑶

已知0,1

B，

a

B

X，a

X，有a∨0=a和a∧1=a⑷

a

B，由′在B上封閉知有a′

B，使得a∨a′=1，a∧a′=0

根據(jù)定理8.2.2，

B,∨,∧,′,0,1

是布爾代數(shù)，它是

X,∨,∧,′,0,1

的子布爾代數(shù)。為了方便，以下將x?y且x≠y記為x?y。

【例8.10】設(shè)

X,∨,∧,′,0,1

是布爾代數(shù)，a,b

X，a?b，令S=

x|x

X，a?x且x?b

試證明

S,∨,∧,′,0,1

是

X,∨,∧,′,0,1

的子布爾代數(shù)。

證明：由于a?a且a?b，所以a

S，S是X的非空子集，由S的定義知a是S的全下界，b是S的全上界。

x,y

S，a?x且x?b，a?y且y?ba?x∨y且x∨y?b，a?x∧y且x∧y?b從而x∨y

S且x∧y

S，即運算∨和∧在S上封閉。

x

S，令y=(a∨x′)∧b

由于a?a∨x′，a?b，故a?(a∨x′)∧b；

又由于(a∨x′)∧b?b，所以y=(a∨x′)∧b

S，又

x∨y=x∨((a∨x′)∧b)=x∨((a∧b)∨(x′∧b))

(分配律)=x∨(a∨(x′∧b))(由定理8.1.4，a?b

a∧b=a)=(x∨a)∨(x′∧b)

(結(jié)合律)=x∨(x′∧b)

(由定理8.1.4，a?x

a∨x=x)=(x∨x′)∧(x∨b)(分配律)=1∧(x∨b)

(x′是x的補元)=x∨b

(1是∧的幺元)=b

(由定理8.1.4，x?b

x∨b=b)x∧y=x∧((a∨x′)∧b)=(x∧b)∧(a∨x′)

(交換律和結(jié)合律)=x∧(a∨x′)

(由定理8.1.4，x?b

x∧b=x)=(x∧a)∨(x∧x′)(分配律)=(x∧a)∨0

(x′是x的補元)=(x∧a)

(0是∨的幺元)=a

(由定理8.1.4，a?x

a∧x=a)所以x′=y

S，一元運算′在S上封閉。

根據(jù)定理8.2.3，

S,∨,∧,′,0,1

是

X,∨,∧,′,0,1

的子布爾代數(shù)。

定義8.2.4

設(shè)

X1,∨1,∧1,′,0,1

和

X2,∨2,∧2,",

,E

是兩個布爾代數(shù)，其中∨1,∧1,∨2和∧2都是二元運算，′和"是一元運算，0和1是X1的全下界和全上界，

,E是X2的全下界和全上界。f是從X1到X2的一個映射，對任意的a,b

X1有

f(a∨1b)=f(a)∨2f(b)

f(a∧1b)=f(a)∧2

f(b)f(a′)=(f(a))"則稱f是布爾代數(shù)

X1,∨1,∧1,′,0,1

到

X2,∨2,∧2,",

,E

的同態(tài)，簡稱布爾代數(shù)同態(tài)。如果f是單射、滿射和雙射，分別稱f是布爾代數(shù)單同態(tài)、布爾代數(shù)滿同態(tài)和布爾代數(shù)同構(gòu)。稱

f(X1),∨2,∧2,",

,E

是

X1,∨1,∧1,′,0,1

的布爾代數(shù)同態(tài)像。

定義8.2.5

設(shè)

X,?

是格，具有全下界0，若X中的元素a蓋住了0，則稱元素a為原子。根據(jù)蓋住的定義，a蓋住了0可以描述為：0?a且

b

X，如果有0?b?a，則a=b。

圖8.10是三個格的哈斯圖，在(a)中，a是原子；在(b)中，a,b,c是原子；在(c)中，a,b是原子。8.2.3有限布爾代數(shù)的結(jié)構(gòu)

定理8.2.4

設(shè)

X,?

是格，具有全下界0，a和b是原子，如果a≠b，則a∧b=0。

證明：設(shè)a∧b≠0，0?a∧b?a且0?a∧b?b，因為a是原子，所以a∧b=a。同樣的道理a∧b=b。于是，a=a∧b=b。與假設(shè)矛盾。在圖8.10的(b)中，a∧b=0，a∧c＝0，b∧c=0；在圖8.10的(c)中，a∧b=0。

設(shè)

X,?

是格，如果集合X是有限集，則稱

X,?

是有限格。

定理8.2.5

設(shè)

X,?

是有限格，具有全下界0，則

b

X且b≠0，至少存在一個原子a，使得a?b。

證明：如果b是一個原子，則b?b。定理得證。如果b不是原子，必有b1使得0?b1?b。如果b1是一個原子，定理得證。否則，必有b2使得0?b2?b1?b。……

由于

X,?

是有限格，通過有限步總可找到一個原子bi，使得

0?bi?…?b2?b1?b

由?的傳遞性，bi?b

定理8.2.5中的原子a不一定惟一，圖8.10的(c)是有限格，元素c有惟一的原子b，使得b?c。圖8.10的(b)也是有限格，元素d卻有三個原子a,b,c，使得a?d,b?d,c?d。

引理8.2.1設(shè)

X,?

是布爾格，0是全下界，a,b

X，則a∧b′=0當(dāng)且僅當(dāng)a?b。

證明：設(shè)a∧b′=0，由0∨b=b，有

b=0∨b=(a∧b′)∨b=(a∨b)∧(b′∨b)=(a∨b)∧1=a∨b由定理8.1.4知，a?b。

設(shè)a?b，由于b′?b′，根據(jù)定理8.1.5有a∧b′?b∧b′，而b∧b′=0，所以a∧b′?0。又因為0?a且0?b′，故有0?a∧b′。由?的反對稱性知a∧b′=0。

引理8.2.2設(shè)

X,∨,∧,′

是有限布爾代數(shù)，0是全下界，如果

b

X且b≠0，a1,a2,…,ak是X中滿足aj?b(j=1,…,k)的所有原子，則b=a1∨a2∨…∨ak

證明：因為aj?b(j=1,…,k)，所以a1∨a2∨…∨ak?b

再證b?a1∨a2∨…∨ak，根據(jù)引理8.2.1，只需證明b∧(a1∨a2∨…∨ak)′=0。用反證法。設(shè)b∧(a1∨a2∨…∨ak)′≠0

由定理8.2.5，至少存在一個原子a，使得a?b∧(a1∨a2∨…∨ak)′又因為b∧(a1∨a2∨…∨ak)′?b和

b∧(a1∨a2∨…∨ak)′?(a1∨a2∨…∨ak)′

由?的傳遞性可得a?b和a?(a1∨a2∨…∨ak)′

因為a是原子且滿足a?b，所以a必是原子a1,a2,…,ak中的一個，因此

a?a1∨a2∨…∨ak于是有a?(a1∨a2∨…∨ak)∧(a1∨a2∨…∨ak)′=0即a?0

這與a是原子相矛盾。所以b∧(a1∨a2∨…∨ak)′＝0，根據(jù)引理8.2.1有

b?a1∨a2∨…∨ak由?的反對稱性知b＝a1∨a2∨…∨ak引理8.3.3

設(shè)

X,∨,∧,′

是有限布爾代數(shù)，如果

b

X且b≠0，a1,a2,…,ak是X中滿足aj?b(j=1,…,k)的所有原子。則b=a1∨a2∨…∨ak是將b表示為原子的惟一形式。

證明：設(shè)有b的另外一種表示形式b=∨∨…∨且是X中的原子。因為b是的最小上界，所以必有?b(i=1,…,t)，而a1,a2,…,ak是X中滿足aj?b(j=1,…,k)的所有不同的原子。所以，必有t≤k。

當(dāng)t＜k時，a1,a2,…,ak中必有使得≠，i=1,…,t于是，∧=(∧a1)∨(

∧a2)∨…∨(∧)∨…∨(∧ak)=∧(a1∨a2∨…∨ak)=∧(∨∨…∨)=(∧)∨(∧)∨…∨(∧

)=0∨0∨…

∨0=0從而=0，與是原子矛盾。所以只能有t=k

定理8.2.6(有限布爾代數(shù)表示定理)設(shè)

X,∨,∧,′

是由有限布爾格

X,?

導(dǎo)出的有限布爾代數(shù)，S是布爾格

X,?

中所有原子的集合，則

X,∨,∧,′

和

P

(S),∪,∩,~

同構(gòu)。

證明：

x

X，令T(x)=

a|a

S且a?x

，顯然T(x)

S。

定義函數(shù)f：X→P(S)，f(x)=T(x)，

x

X⑴證明f是X到P

(S)的雙射函數(shù)。設(shè)f(x)=f(y)，令f(x)=f(y)=

a1,a2,…,an

，由引理8.2.3知x＝a1∨a2∨…∨an＝y(tǒng)。于是f是單射。設(shè)

b1,b2,…,bn

P(S)，令x=b1∨b2∨…∨bn，由運算∨的封閉性得x

X且bi?x，i=1,…,n，f(x)=T(x)=

b1,b2,…,bn

，所以f是滿射。故f是X到P(S)的雙射函數(shù)。⑵證明f是

X,∨,∧,′

和

P(S),∪,∩,~

同構(gòu)。

x,y

X，對于任意的bb

T(x∧y)

b

S且b?x∧y

(b

S且b?x)且(b

S且b?y)

b

T(x)且b

T(y)

b

T(x)∩T(y)從而有T(x∧y)=T(x)∩T(y)，因此f(x∧y)=T(x∧y)=T(x)∩T(y)=f(x)∩f(y)

x,y

X，

令T(x)=

a|a

S且a?x

=

a1