6.1格的概念

6.2子格和格同態(tài)

6.3特殊的格

6.4布爾代數(shù)

6.5布爾代數(shù)的結(jié)構(gòu)和布爾函數(shù)第6章格與布爾代數(shù)6.1.1格的定義

定義6.1.1

設(shè)〈L

，〉是一個偏序集合，若對任意a,b∈L，{a,b}均存在最小上界和最大下界，則稱〈L

，〉為偏序格(lattice)。

設(shè)〈L

，〉為偏序格，對于任何a,b∈L，不難證明，{a,b}的最小上界和最大下界都是存在且唯一的，以后將用glb{a,b}表示{a,b}的最大下界，用lub{a,b}表示{a,b}的最小上界。6.1格的概念???

例1

給出七個偏序集合的哈斯圖如圖6.1.1所示。

其中，圖(a)、(b)、(c)、(d)是偏序格，圖(e)、(f)、(g)不是偏序格。

圖6.1.1

例3

設(shè)n是一正整數(shù)，Sn是n的所有因子的集合。例如S6={1,2,3,6},S8={1,2,4,8},“|”是整除關(guān)系，則〈Sn，|〉是偏序格?！碨8,|〉,〈S6,|〉,〈S30|〉的哈斯圖如圖6.1.2(a)、(b)、(c)所示。

圖6.1.2

定義6.1.2

設(shè)〈L，∨，∧〉是代數(shù)系統(tǒng)，如果對任意的a，b，c∈L,有

(1)(交換律)a∨b=b∨a，a∧b=b∧a;

(2)(結(jié)合律)a∨(b∨c)=(a∨b)∨c，a∧(b∧c)=(a∧b)∧c;

(3)(吸收律)a∨(a∧b)=a，a∧(a∨b)=a,

則稱〈L，∨，∧〉是代數(shù)格。6.1.2格的性質(zhì)

定理6.1.1設(shè)〈L，∨，∧〉是代數(shù)格，則∨和∧滿足等冪律，即對于任何a∈L，有

a∨a=a,a∧a=a

證明任取a∈L，a∨a=a∨(a∧(a∨a))=a，a∧a=a∧(a∨(a∧a))=a。

證畢

定義6.1.3

設(shè)〈L，〉是一個偏序格，在L上定義兩個二元運算∨和∧,對于任何a，b∈L，a∨b=lub{a,b}，a∧b=glb{a,b}，則稱∨和∧分別為L上的并和交運算，稱〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)系統(tǒng)。

定理6.1.2

設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)系統(tǒng)，則

(1)對于a，b∈L，a

a∨b，b

a∨b。

(2)對于a，b∈L，

a∧b

a，a∧b

b。

(3)對于a，b，

c∈L，若a

c

且b

c，則a∨b

c。

(4)對于a，b，c∈L，若c

a且c

b，則c

a∧b。

證明略。?????????????

定理6.1.3

設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)系統(tǒng)，對于任何a，b，c，d∈L，如果a

b，c

d，則有a∨c

b∨d，a∧c

b∧d。

證明設(shè)a

b，c

d，由定理6.1.2知，b

b∨d，d

b∨d，利用滿足傳遞性，可得：

a

b∨d,c

b∨d

這表明b∨d是a和c的一個上界，而a∨c是a和c的最小上界，從而得到

a∨c

b∨d

類似地，可以證明a∧c

b∧d。

證畢?????????????

推論設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)系統(tǒng)，對于a，b，c∈L，如果b

c，則a∨b

a∨c

，a∧b

a∧c。這個性質(zhì)稱為偏序格的運算保序性。????

定理6.1.4

設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)系統(tǒng)，則〈L，∨，∧〉是代數(shù)格，并稱〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)格。

證明任取a，b∈L，因為a∨b=lub{a,b}=b∨a，a∧b=glb{a,b}=b∧a，所以，∨和∧均滿足交換律。

任取a,b,c∈L，先證(a∨b)∨c=a∨(b∨c)。

因為b

b∨c

a∨(b∨c),a

a∨(b∨c)，所以a∨b

a∨(b∨c)。

又因為c(b∨c)a∨(b∨c)，所以(a∨b)∨c

a∨(b∨c)。?????????因為b

a∨b,c

c，所以b∨c(a∨b)∨c。又因為a(a∨b)(a∨b)∨c，所以a∨(b∨c)(a∨b)∨c。

從而得到，(a∨b)∨c=a∨(b∨c)，即運算∨滿足結(jié)合律。

同理可證，任取a,b,c∈L，a∧(b∧c)=(a∧b)∧c，即運算∧也滿足結(jié)合律。

任取a,b∈L，先證a∨(a∧b)=a。

因為a

a∨(a∧b),又因為a

a和a∧b

a，所以a∨(a∧b)a。

故有，a∨(a∧b)=a。

同理可證，a∧(a∨b)=a。

所以，運算∨和∧滿足吸收律。

因此，〈L，∨，∧〉是代數(shù)格。

證畢??????????

定理6.1.5

設(shè)〈L，∨，∧〉是代數(shù)格，在L上定義二元關(guān)系：對于任何a，b∈L，

a

b

a∨b＝b，則〈L，〉是一個偏序格，并稱〈L，〉是由代數(shù)格〈L，∨，∧〉誘導(dǎo)的偏序格。

證明先證是L上的偏序關(guān)系。

任取a∈L，根據(jù)定理6.1.1可知，〈L，∨，∧〉滿足等冪律，有a∨a＝a，即a

a，所以，在L上是自反的。

任取a，b∈L，設(shè)a

b且b

a，由的定義知，a∨b＝b且b∨a＝a。

????????因為∨運算滿足交換律，推出a＝b∨a＝a∨b＝b，所以在L上是反對稱的。

任取a,b,c∈L，設(shè)a

b且b

c，由的定義知，a∨b＝b且b∨c＝c，因為∨運算滿足結(jié)合律，從而可推出，a∨c＝a∨(b∨c)＝(a∨b)∨c＝b∨c＝c，即a

c。

所以，在L上是傳遞的。

因此，為L上的偏序關(guān)系。???????再證明對于任何a，b∈L，{a,b}存在最小上界。這里直接證明a∨b=lub{a,b}。

任取a，b∈L，有

a∨(a∨b)＝(a∨a)∨b＝a∨b

b∨(a∨b)＝(b∨a)∨b＝a∨(b∨b)＝a∨b

根據(jù)的定義知，a

a∨b和b

a∨b，所以a∨b是{a,b}的上界。假設(shè)c為{a,b}的任一上界，a

c和b

c，則有a∨c＝c和b∨c＝c，從而有

(a∨b)∨c＝a∨(b∨c)＝a∨c＝c

這就證明了a∨b

c，所以a∨b是{a,b}的最小上界，即a∨b＝lub{a,b}。?????最后證明對于任何a，b∈L，{a,b}存在最大下界。這里直接證明a∧b=glb{a,b}。

由于〈L，∨，∧〉是代數(shù)格，滿足交換律和吸收律，于是有：

如果a∧b=a，可得b=(a∧b)∨b=a∨b，則a∨b=b。

如果a∨b=b，可得a=a∧(a∨b)=a∧b，則a∧b=a。

因此，a∧b=a當(dāng)且僅當(dāng)a∨b=b。

由此得到結(jié)論：對于任何a，b∈L

，有a

b

a∨b＝b

a∧b=a，這樣，任取a，b∈L，有

(a∧b)∧a＝a∧(a∧b)＝(a∧a)∧b＝a∧b

(a∧b)∧b＝a∧(b∧b)＝a∧b

??根據(jù)的定義知，a∧b

a和a∧b

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＝glb{a,b}。

因此，〈L，〉是偏序格。

證畢???????在進(jìn)一步討論格的性質(zhì)之前，下面先介紹格的對偶原理。

設(shè)〈L，〉是一個偏序集合,在L上定義一個二元關(guān)系，使得對于任何a，b∈L，a

b當(dāng)且僅當(dāng)b

a。不難證明，也是一種偏序關(guān)系，可稱是的逆關(guān)系，且〈L，〉也是一個偏序集合。這里將〈L，〉和〈L，〉稱為相互對偶的(哈斯圖相互顛倒)。可以證明，若〈L，〉是格，則〈L，〉也是格。

格對偶原理：設(shè)P是對任意格都真的命題，如果在命題P中把換成，∨換成∧，∧換成∨，就得到另一個命題P′，則P′對任意格也是真的命題，稱P′為P的對偶命題。??????????????

定理6.1.6

設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)格，則對任意的a,b,c∈L，有下述的分配不等式成立：

a∨(b∧c)(a∨b)∧(a∨c)

(a∧b)∨(a∧c)a∧(b∨c)

???

證明由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)

應(yīng)用對偶原理可得

(a∧b)∨(a∧c)a∧(b∨c)

證畢????????

定理6.1.7

設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)格，對任意的a,b,c∈L，則有a

b當(dāng)且僅當(dāng)a∨(b∧c)b∧(a∨c)(模不等式)。

證明設(shè)a

b，則a∨b=b，由定理6.1.6得到

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

設(shè)a∨(b∧c)b∧(a∨c)，則有a

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

b。

證畢

??????????

推論設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)格，對任意的a,b,c∈L，則有(a∧b)∨(a∧c)a∧(b∨(a∧c))，a∨(b∧(a∨c))(a∨b)∧(a∨c)。

證明利用a∧c

a，a

a∨c即可得證。

證畢?????為便于讀者查閱，將偏序格〈L，〉及其所誘導(dǎo)的代數(shù)格〈L，∨，∧〉的有關(guān)性質(zhì)歸納為表6.1.1。表中，a、b、c、d是L中任意元素。表6.1.16.2.1子格

定義6.2.1

設(shè)〈L，∨，∧〉是由偏序格〈L，〉所誘導(dǎo)的代數(shù)格，設(shè)B

L且B≠，如果運算∨和∧關(guān)于B是封閉的(即對任意a,b∈B，有a∨b∈B和a∧b∈B)，則稱〈B，〉是格〈L，〉的子格(sublattice)。

6.2子格和格同態(tài)?????若〈B，〉是格〈L，〉的子格，對任意a∈B，a

a，〈a，a〉∈，所以在B上是自反的。對任意a,b∈B，若a

b，b

a,則a=b，所以是反對稱的。對任意a,b，c∈B，a

b，b

c，則a

c，所以是傳遞的。故〈B，〉是一個偏序集合。又由于對任意a,b∈B，有a∨b∈B和a∧b∈B，由運算∨和∧的定義可知，a∨b=lub{a,b}，a∧b=glb{a,b}。所以〈B，〉是格。因此，若〈B，〉是格〈L，〉的子格，則〈B，〉一定是格。????????????????

例3

設(shè)S={a，b，c}，L=ρ(S)是它的冪集，偏序集合〈L，〉是格，如圖6.2.1所示。圖6.2.1?6.2.2格同態(tài)

定義6.2.2

設(shè)〈L1，∨1，∧1〉和〈L2，∨2，∧2〉是由偏序格〈L1，1〉和〈L2，2〉分別誘導(dǎo)的代數(shù)格，如果存在從L1到L2的映射f，使得對于任意的a，b∈L1，

f(a∨1

b)=f(a)∨2

f(b)

f(a∧1

b)=f(a)∧2

f(b)??????

例5

圖6.2.2所示為格〈L1，〉，〈L2，〉，〈L3，〉。

圖6.2.2???

定理6.2.1

設(shè)f是格〈L1，1〉和〈L2，2〉的格同態(tài)映射，則對于任意的x，y∈L1,若x

1y，必有f(x)2f(y)(格的同態(tài)保序性)。

證明任取x，y∈L1，設(shè)x

1y，則有

x∧1y=x

f(x∧1y)=f(x)

f(x)∧2f(y)=f(x∧1y)=f(x)

因此，f(x)2f(y)成立。

證畢??????

例6

具有一、二、三個元素的格分別同構(gòu)于一、二、三個元素的鏈。四個元素的格必同構(gòu)于圖6.2.3(a)和(b)之一，五個元素的格必同構(gòu)于圖6.2.4(a)、(b)、(c)、(d)、(e)之一。圖6.2.3圖6.2.46.3.1分配格

定義6.3.1

設(shè)〈L，〉是格，對任意的a,b,c∈L，有

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

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

則稱〈L，〉為分配格。6.3特殊的格??圖6.3.1

定理6.3.1

如果在一個格中交運算對于并運算可分配，則并運算對交運算也一定是可分配的，反之亦然。

證明設(shè)〈L，〉是格，首先證明若∧對∨可分配，則∨對∧也一定可分配。

?任取a,b,c∈L，設(shè)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

判斷圖6.3.2中的格〈L1，〉、〈L2，〉、〈L3，〉、〈L4，〉是否為分配格。其中〈L3，〉被稱為鉆石格，〈L4，〉被稱為五角格。

圖6.3.2??????

定理6.3.2

設(shè)〈L，〉是格，則〈L，〉是分配格當(dāng)且僅當(dāng)〈L，〉中既不存在與鉆石格同構(gòu)的子格,也不存在與五角格同構(gòu)的子格。

證明略。

例3

判斷圖6.3.3中的格是否為分配格并說明理由。

圖6.3.3???

定理6.3.3

任何鏈都是分配格。

證明設(shè)〈L，〉是一個鏈，所以〈L，〉一定是格。對任意的a,b,c∈L，分情況討論如下：

(1)a

b或a

c(a不是最大元)。

無論是a

b還是a

c，都有

a∧(b∨c)=a

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

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

??????

(2)b

a且c

a(a是最大元)。

由b

a和c

a，可得

b∨c

a

a∧(b∨c)=b∨c

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

所以a∧(b∨c)=(a∧b)∨(a∧c)成立。

由(1)、(2)可知,∧運算對∨運算可分配，由定理6.3.1知，∨運算對∧運算也可分配。故每個鏈都是分配格。

證畢?????

定理6.3.4

設(shè)〈L，〉是分配格，對于任何a,b,c∈L，如果a∧b＝a∧c且a∨b＝a∨c，則b＝c。

證明任取a,b,c∈L，有

b＝b∨(a∧b)(吸收律,交換律)

＝b∨(a∧c)

(已知條件代入)

＝(b∨a)∧(b∨c)

(分配律)

＝(a∨c)∧(b∨c)

(已知條件代入,交換律)

＝(a∧b)∨c

(分配律)

＝(a∧c)∨c

(已知條件代入)

＝c

(交換律,吸收律)

證畢6.3.2模格

定義6.3.2

設(shè)〈L，∨，∧〉是由偏序格〈L，〉誘導(dǎo)的代數(shù)格，如果對于任意的a,b,c∈L，當(dāng)b

a時，有a∧(b∨c)=b∨(a∧c)，則稱〈L，〉是模格。???

定理6.3.5

分配格必定是模格。

證明設(shè)〈L，〉是分配格，對任意a,b,c∈L，若b

a，有a∧b=b。因此

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

證畢??6.3.3有界格

定義6.3.3

設(shè)〈L，〉是格，若L中有最大元(全上界)和最小元(全下界)，則稱〈L，〉為有界格。一般把格的全上界記為1，全下界記為0。

圖6.3.4??

定理6.3.6

對于任何一個格〈L，〉，若有全下界(全上界)，則是唯一的。

證明設(shè)a，b∈L且a和b是L的全下界，因為a是全下界，所以a

b。又因為b是全下界，所以b

a。由于是反對稱的，所以a=b。因此，全下界是唯一的。

采用類似方法可以證明全上界也是唯一的。

證畢????

定理6.3.7

設(shè)〈L，〉是一個有界格，則對任意

a∈L，有

a∨1=1，a∧1=a(1是∨運算的零元，∧運算的幺元)

a∨0=a，a∧0=0(0是∨運算的幺元，∧運算的零元)

證明因為1是全上界，a1，所以a∨1=1,a∧1=a。又因為0是全下界，0a,所以a∨0=a,a∧0=0。

證畢???6.3.4有補格

定義6.3.4

設(shè)〈L，〉是一個有界格，對于任意a∈L，如果存在b∈L，使得a∧b=0，a∨b=1，則稱b為a的補元(complement)。

由定義可知，若b是a的補元，則a也是b的補元，即a與b互為補元。

顯然，在有界格中，0是1的唯一補元，1是0的唯一補元。一般來說，一個元素可以有多個補元，也可能無補元。?

例6

求出圖6.3.5中各格的元素的補元。

圖6.3.5

定義6.3.5

設(shè)〈L，〉是一個有界格，若L中每個元素至少有一補元，則稱〈L，〉為有補格。

例如,圖6.3.5(a)所示的格中，有些元素?zé)o補元，故不是有補格，圖(b)、(c)所示的格為有補格。

由于補元的定義是在有界格中給出的，因此，有補格一定是有界格。

??

定理6.3.8

設(shè)〈L，〉是有界分配格，若a∈L，且存在補元，則a的補元是唯一的。

證明設(shè)a有兩個補元素b和c，即有

a∨b=1和a∧b=0

a∨c=1和a∧c=0

由定理6.3.4得b=c。

證畢?

定義6.4.1

設(shè)〈B，〉是一個格，如果〈B，〉既是有補格，又是分配格，則稱〈B，〉是布爾格。

由于在布爾格〈B，〉中，每個元素a都有唯一的補元，因此可在B上定義一個一元運算——補運算“ˉ”。這樣，布爾格〈B，〉所誘導(dǎo)的代數(shù)格可看做是具有兩個二元運算“∨”、“∧”和一個一元運算“ˉ”的代數(shù)結(jié)構(gòu)，記做〈B，∨，∧，ˉ〉，稱為布爾代數(shù)(BooleanAlgebra)。6.4布爾代數(shù)?????

定理6.4.1

設(shè)〈B，∨，∧，ˉ〉是由布爾格〈B，〉誘導(dǎo)的布爾代數(shù)，對于任意a,b∈B，則有

(1)(對合律)。

(2)(德·摩根律)，。

?

證明

(1)因為a∨

=1，a∧

=0，所以。

(2)因為

(a∨b)∨(∧)=((a∨b)∨)∧((a∨b)∨)=1∧1=1

又因為

(a∨b)∧(∧)=(a∧(∧))∨(b∧(∧))=0∨0=0

所以，。

可用類似方法證明。

證畢下面列舉布爾代數(shù)的一些重要性質(zhì)，并進(jìn)一步討論布爾代數(shù)的判斷條件。設(shè)〈B，∨，∧，ˉ〉是由布爾格〈B，〉誘導(dǎo)的布爾代數(shù)，其中全上界是1，全下界是0，對于任意a，b，c∈B，則有:

(1)交換律:a∨b=b∨a，a∧b=b∧a。

(2)吸收律:a∨(a∧b)=a，a∧(a∨b)=a。

(3)結(jié)合律:(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)。

(4)等冪律:a∨a=a，a∧a=a。

(5)分配律:a∨(b∧c)=(a∨b)∧(a∨c)，a∧(b∨c)=

(a∧b)∨(a∧c)。?

(6)同一律:a∧1=a，

a∨0=a。

(7)零律:a∨1=1，a∧0=0。

(8)排中律:。

(9)矛盾律:

。

(10)對合律:。

(11)德·摩根律:

，

。

定理6.4.2

設(shè)〈B，∨，∧，ˉ〉是一個至少含有兩個元素的封閉的代數(shù)系統(tǒng)，∨和∧是B上的二元運算，ˉ是B上的一元運算，對任意的a,b,c∈Ｂ，如果滿足

(H1)交換律:a∨b＝b∨a,a∧b＝b∧a;

(H2)分配律:a∧(b∨c)＝(a∧b)∨(a∧c),a∨(b∧c)＝(a∨b)∧(a∨c);

(H3)同一律:存在元素0、1∈B，使得對任意a∈B，有

a∧1＝a，

a∨0＝a

(H4)排中律和矛盾律:對任意a∈B，有∈B，使得

，

則〈B，∨，∧，ˉ〉是一個布爾代數(shù)。

證明

(1)證明a∨1＝1，a∧0＝0。

a∨1＝(a∨1)∧1=(a∨1)∧(a∨

)=a∨(1∧

)

=a∨

=1

a∧0＝(a∧0)∨0=(a∧0)∨(a∧

)=a∧(0∨

)

=a∧

=0

(2)證明如果a∨c=b∨c，a∨

=b∨，則a=b。

設(shè)a∨c=b∨c，a∨

=b∨，可得a＝a∨0

=a∨(c∧)

=(a∨c)∧(a∨)

=(b∨c)∧(b∨)

=b∨(c∧)

=b∨0

=b

(3)證明〈B，∨，∧，ˉ〉是格。

由(H1)知，∨和∧滿足可交換律。

因為

a∨(a∧b)=(a∧1)∨(a∧b)=a∧(1∨b)=a∧1=a

a∧(a∨b)=(a∨0)∧(a∨b)=a∨(0∧b)=a∨0=a

所以，∨和∧滿足吸收律。令s=(a∨b)∨c，t=a∨(b∨c)，s,t∈B,s∧c=((a∨b)∨c)∧c=c，則

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

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

=(a∧c)∨c

=c

所以s∧c=t∧c。又因為

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

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

=(a∨b)∧

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

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

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

=(a∧)∨(b∧)

=(a∨b)∧采用類似的方法，令s=(a∧b)∧c，t=a∧(b∧c)，s,t∈B，通過證明s∨c=t∨c，s∨=t∨，得到s=t，即(a∧b)∧c=a∧(b∧c)，從而證明運算∧也滿足結(jié)合律。

由以上論證知，〈B，∨，∧，ˉ〉滿足交換律、結(jié)合律、吸收律。

因此，〈B，∨，∧，ˉ〉是格。

(4)設(shè)〈B，〉是由代數(shù)〈B，∨，∧，ˉ〉誘導(dǎo)的偏序格，由(H3)知，存在元素0,1∈B，對任意a∈B，有a∧1＝a，a∨0＝a，得到a1，0a。

因此，〈B，∨，∧，ˉ〉是有界格，全上界是1，全下界是0。

(5)由(H4)知，對于任意a∈B，有∈B，使得a∨=1，a∧=0,因此，〈B，∨，∧，ˉ〉是有補格。???

(6)由(H2)知：

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

＝(a∨b)∧(a∨c)

因此，〈B，∨，∧，ˉ〉是分配格。

綜合以上證明，得到〈B，∨，∧，ˉ〉是一個布爾代數(shù)。

證畢

例1

設(shè)B＝{0，1}，B上的一元運算“ˉ”與二元運算∧和∨的定義見表6.4.1。表6.4.1

例2

圖6.4.1給出了S={a}，S={a，b}，S={a，b，

c}相應(yīng)的布爾格的哈斯圖表示。

圖6.4.1

定義6.5.1

具有有限個元素的布爾代數(shù)稱為有限布爾代數(shù)。

定義6.5.2

設(shè)〈L1，∨，∧，ˉ〉和〈L2，∨，∧，ˉ〉是兩個布爾代數(shù)，如果存在著A到B的映射f，對于任意的a,b∈L1，都有6.5布爾代數(shù)的結(jié)構(gòu)和布爾函數(shù)

定義6.5.3

設(shè)〈L，〉是一個格，且具有全下界0，如果有元素a蓋住0(0a，且沒有其他元素b∈L滿足0b

a)，則稱元素a為原子(atom)。

原子在偏序圖中是那些與0有直接連線的元素。顯然，在格中若有原子a、b且a≠b，則必有a∧b=0。????

定理6.5.1

設(shè)〈L，〉是一個具有全下界的有限格，則對任何一個非零元素b(即不等于全下界0的元素)至少存在一個原子a，使得a

b。

證明若b本身是原子，則b

b，得證。若b不是原子，則存在b1∈L，使得0b1

b。如果b1是原子，得證。如果b1不是原子，則存在b2∈L，使得0b2

b1

b。如此重復(fù)進(jìn)行下去，由于〈L，〉是一個具有全下界的有限格，必然存在bk∈L使得

0bk

bk－1…b2

b1

b

且bk為原子。

證畢?????????????

定理6.5.2

設(shè)〈L，〉是格，a、b是L中的原子，若a≠b，則a∧b＝0。

證明用反證法。假設(shè)a∧b≠0，則有0a∧b

a，0a∧b

b。由于a、b是原子，因此有a∧b＝a和a∧b＝b，從而有a＝b，與a≠b矛盾。

故對L中的原子a、b，若a≠b，必有a∧b＝0。

證畢?????

引理6.5.1

在一個布爾格〈B，〉中，對于任何b，c∈B，

當(dāng)且僅當(dāng)b

c。

證明必要性。設(shè)

，因為0∨c=c，可得

c=0∨c

=(b∧)∨c

=(b∨c)∧(∨c)

=(b∨c)∧1

=b∨c

因此，b

c。

充分性。設(shè)b

c，因為，所以b∧c∧=0。

因此，b∧=0。

證畢??????

引理6.5.2

設(shè)〈B，∨，∧，ˉ〉是一個有限布爾代數(shù)，若b是B中任意非零元素，a1，a2，…，ak是B中滿足ai

b的所有原子(1，2，…，k)，則

b=a1∨a2∨…∨ak

證明

(1)令c＝a1∨a2∨…∨ak，因為ai

b(i=1，2，…，k)，所以c

b。

(2)下面證明b

c。由引理6.5.1，只需證明b∧

=0。

用反證法。設(shè)b∧≠0，由定理6.5.1，必然存在一個原子a，使得a

b∧。?????又由于

b∧

b，b∧

由傳遞性可得

a

b，a

由于a是原子，結(jié)合a

b，必有a∈{a1，a2，…，ak}，因而a

a1∨a2∨…∨ak=c,得到a

c，再結(jié)合a

，就有a

c∧

=0,即a0，與a是原子矛盾，故b∧

=0，即b

c。

綜合(1)和(2)的結(jié)論，必有b=c＝a1∨a2∨…∨ak。

證畢?????????

引理6.5.3(原子表示定理)設(shè)〈B，∨，∧，ˉ〉是一個有限布爾代數(shù)，若b是B中任意非零元素，a1，a2，…，ak是B中滿足ai

b的所有原子(i=1，2，…，k)，則b=a1∨a2∨…∨ak是將b表示為原子的并的唯一形式。

證明任取b的一種原子并的表示形式：b=ai1∨ai2∨…∨ait，其中ai1，ai2，…,ait是B中的原子，由于ai1

b，ai2

b，…,ait

b，因此可以得到ai1，ai2，…,ait∈{a1，a2，…，ak}。????假設(shè){ai1，ai2，…,ait}≠{a1，a2，…，ak}，則存在ai∈{a1，a2，…，ak}，但是ai∈{ai1，ai2，…,ait}，于是有

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

ai∧b=ai∧(ai1∨ai2∨…∨ait)=0

即ai=0，與ai是原子矛盾，故假設(shè){ai1，ai2，…,ait}≠{a1，a2，…，ak}不成立。因此，{ai1，ai2，…,ait}={a1，a2，…，ak}。

這就證明了b=a1∨a2∨…∨ak是將b表示為原子的并的唯一形式。

證畢

定理6.5.3(斯通(Stone)定理)設(shè)〈B，∨，∧，ˉ〉是由有限布爾格〈B,〉所誘導(dǎo)的一個有限布爾代數(shù)，S是布爾格〈B，〉中的所有原子的集合，則〈B，∨，∧，ˉ〉與集合代數(shù)〈ρ(S)，∪，∩，ˉ〉同構(gòu)。

證明任取x∈B且x≠0，令Sx

＝{a|a∈S，a

x}，Sx

S，構(gòu)造函數(shù)f：B→ρ(S)為

f(0)＝

對于任何x∈B且x≠0，f(x)＝Sx。???下面證明f是B到ρ(S)的同構(gòu)映射。

(1)證明f為雙射。任取x,y∈B，設(shè)f(x)＝f(y)={a1，a2，…，an}，由引理6.5.3知

x=a1∨a2∨…∨an＝y(tǒng)

故f為單射。

任取{b1，b2，…，bm}∈ρ(S)，令x＝b1∨b2∨…∨bm，則

f(x)＝Sx＝{b1，b2，…，bm}

故f為滿射。

(2)證明對于任何x，y∈B，

f(x∧y)＝f(x)∩f(y)。任取b∈B

，因為

b∈f(x∧y)=Sx∧y

b∈S∧b(x∧y)

b∈S∧b

x∧b

y

b∈Sx∧b∈Sy

b∈Sx∩Sy

所以，Sx∧y＝Sx∩Sy，即對于任何x，y∈B，f(x∧y)＝f(x)∩f(y)成立。???

(3)證明對于任何x，y∈B，f(x∨y)＝f(x)∪f(y)。

設(shè)x＝a1∨a2∨…∨an，y＝b1∨b2∨…∨bm是x、y的原子表示，顯然

x∨y＝a1∨a2∨…∨an∨b1∨b2∨…∨bm

由引理6.5.3可知

Sx∨y＝{a1，a2，…，an，b1，b2，…，bm}

由于Sx＝{a1，a2，…，an}，Sy＝{b1，b2，…，bm}，所以Sx∨y＝Sx∪Sy

又因為f(x∨y)＝Sx∨y，f(x)∪f(y)＝Sx∪Sy,所以，對于任何x，y∈B，f(x∨y)＝f(x)∪f(y)成立。

(4)證明對于任何x∈B，f(

)＝

。

設(shè)x的補元∈B，x∨＝1，x∧＝0，則有

f(x)∪f(

)＝f(x∨

)＝f(1)＝S

f(x)∩f(

)＝f(x∧

)＝f(0)＝

而和S分別為ρ(S)的全下界和全上界，因此f(

)是f(x)在ρ(S)中的補元，即

f(

)＝f(x)

綜上所述，f是B到ρ(S)的同構(gòu)映射，即有限布爾格〈B，〉所誘導(dǎo)的有限布爾代數(shù)〈B，∨，∧，ˉ〉與集合代數(shù)〈ρ(S)，∪，∩，ˉ〉同構(gòu)，其中S是布爾格〈B，〉中的所有原子的集合。

證畢????

推論1

有限布爾格的元素的個數(shù)必定等于2n，其中n是該布爾格中所有原子的個數(shù)。

由此又可推出，若兩個有限布爾代數(shù)中的集合有相同的基數(shù)，則它們的原子集合也有相同的基數(shù),于是這兩個布爾代數(shù)是同構(gòu)的。因此可得到如下推論：

推論2

任何兩個具有相同元素數(shù)目的有限布爾代數(shù)都是同構(gòu)的。

設(shè)〈B，∨，∧，ˉ〉是布爾代數(shù)，下面討論從Bn

到B的布爾函數(shù)(或布爾表達(dá)式)。

定義6.5.4

給定布爾代數(shù)〈B，∨，∧，ˉ〉及n個變元x1，x2，…，xn，則在〈B，∨，∧，ˉ〉上由n個變元x1，x2，…，xn產(chǎn)生的布爾表達(dá)式可歸納定義如下：

(1)B中的任何元素是一個布爾表達(dá)式。

(2)任何變元xi(i=1，2，…，n)是一個布爾表達(dá)式。

(3)若e1和e2是布爾表達(dá)式，那么、(e1∨e2)和(e1∧e2)也是布爾表達(dá)式。

(4)只有通過有限次運用規(guī)則(1)、(2)和(3)所構(gòu)造的符號串才是布爾表達(dá)式。

為了討論方便，通常將含有n個變元x1，x2，…，xn

的布爾表達(dá)式采用由代表函數(shù)符的小寫(或大寫)字母以及變元序列組成的“緊式”進(jìn)行描述，記為f(x1，x2，…，xn)、E(x1,x2，…，xn)等。

定義6.5.5

布爾代數(shù)〈B，∨，∧，ˉ〉上的一個含有n個變元的布爾表達(dá)式E(x1，x2，…，xn)的值是將B的元素作為變元xi(i=1，2,…，n)的值來代入表達(dá)式中相應(yīng)的變元(即對變元賦值)，從而計算出的表達(dá)式的值。

定義6.5.6

設(shè)布爾代數(shù)〈B，∨，∧，ˉ〉上兩個n元的布爾表達(dá)式為E1(x1，x2，…，xn)和E2(x1，x2，…，xn)，如果對于任意賦值，xi=bi，bi∈B，

i=1,2,…,n，均有

E1(b1，b2，…，bn)=E2(b1，b2，…，bn)

定義6.5.7

設(shè)〈B，∨，∧，ˉ〉是一個布爾代數(shù)，f為一個從Bn到B的函數(shù)，如果它能夠用〈B，∨，∧