地六章-格和布爾代數(shù)

第六

章格與布爾代數(shù)

數(shù)學(xué)是科學(xué)的大門鑰匙，忽視數(shù)學(xué)必將傷害所有的知識(shí)，因?yàn)楹鲆晹?shù)學(xué)的人是無法了解任何其他科學(xué)乃至世界上任何其他事物的。更為嚴(yán)重的是，忽視數(shù)學(xué)的人不能理解他自己這一疏忽，最終將導(dǎo)致無法尋求任何補(bǔ)救的措施。

BaconRoger環(huán)與域一、環(huán)定義：設(shè)是代數(shù)系統(tǒng)，為集合，為二元運(yùn)算，若

(1)為阿貝爾群，

(2)為半群，

(3)乘法對(duì)加法適合分配律，則稱是環(huán)。

例1.

，，都是環(huán)。是環(huán)。是模的整數(shù)環(huán)，其中表示模的加法和乘法，，。

二、域定義：環(huán)滿足：

(1)至少兩個(gè)元素，

(2)含有幺元，

(3)是可交換的，

(4)除加法幺元外，其余元素均有逆元，則稱為域。例2.

，都是域，但不是域，因?yàn)椴皇浅?外，其余元素都有逆元。不是域，因不是可交換的。是域，但不是域(，但不存在乘法的逆元，使)令，則為域。第六

章格與布爾代數(shù)

布爾代數(shù)是一個(gè)抽象代數(shù)系統(tǒng)。對(duì)于它的建立可循兩個(gè)途徑進(jìn)行：一是從抽象代數(shù)的觀點(diǎn)出發(fā)，把布爾代數(shù)看成是特殊的格——

布爾格，使其立于現(xiàn)代數(shù)學(xué)的抽象代數(shù)結(jié)構(gòu)之上；二是從數(shù)理邏輯觀點(diǎn)出發(fā)，把直觀布爾代數(shù)看成是形式布爾代數(shù)的標(biāo)準(zhǔn)模型，使其立于現(xiàn)代數(shù)學(xué)的形式化結(jié)構(gòu)之上。這樣兩種奠基法，無疑地將加深我們對(duì)于布爾代數(shù)的數(shù)學(xué)本質(zhì)的認(rèn)識(shí)。

布爾（GeorgeBool，1815~1864年，英國(guó)數(shù)學(xué)家）在戴德金（Dedekind）之前就曾引出過一種特殊的格——有余分配格，這種格被稱為布爾代數(shù)。歷史上最初出現(xiàn)的格是布爾于1854年提出的，是他在研究命題演算中發(fā)現(xiàn)的。大體于1935年左右形成的近代格論，正是來源于邏輯、數(shù)論、代數(shù)學(xué)與幾何學(xué)領(lǐng)域，并與其他數(shù)學(xué)分支廣泛地聯(lián)系著。格是伯克霍夫（Birkhoff1884~1944年）在20世紀(jì)30年代提出的，格的提出以子集為背景。格是一種特殊的偏序集，滿足一定條件的偏序集稱為格，同時(shí)格又可看成是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)。格和布爾代數(shù)的理論成為計(jì)算機(jī)硬件設(shè)計(jì)和通訊系統(tǒng)設(shè)計(jì)中的重要工具。6.1格

6.1.1格的定義定義6.1對(duì)于偏序集(L，≤)的任意兩個(gè)元素a、b，恒存在上確界（記為sup{a,b}）及下確界（記為inf{a,b}）時(shí)，稱該偏序集為格。格是一個(gè)抽象的代數(shù)結(jié)構(gòu)(代數(shù)系統(tǒng))。

顯然，一個(gè)全序集是一個(gè)格，但是，不是所有偏序集都是格。對(duì)于a∈L、b∈L，a、b的上確界和下確界分別用a∨b(或a

b，或a

b)和a∧b(或a

b,a.b)來表示，依次稱為a,b的并和交，這是格中的兩種基本運(yùn)算。在下圖中，給出了格的哈斯圖，（a）（b）（c）下圖左側(cè)給出了不是格的哈斯圖。右側(cè)是格的實(shí)例。

不是格的偏序集格的實(shí)例【例9.1】S是任意一個(gè)集合，

(S)是S的冪集合，于是， 偏序集(

(S),

)是一個(gè)格。對(duì)

A,B∈

(S)，

sup{A,B}＝A∪B∈

(S) inf{A,B}＝A∩B∈

(S)

（a）（b）【例6.2】設(shè)I

是是個(gè)正整數(shù)集，并用D表示I

中的“除法”關(guān)系，亦即對(duì)于任何a,b∈I

，aDb當(dāng)且僅當(dāng)a整除b，顯然，(I

,D)是一個(gè)格。其中a和b的并是a和b的最小公倍數(shù)；a和b的交是a和b的最大公因數(shù)。

【例6.3】設(shè)I+

是個(gè)正整數(shù)集，n是一個(gè)正整數(shù)，Sn

是n的所有因數(shù)的集合。例如，S6＝{1,2,3,6}，

S24＝{1,2,3,4,6,8,12,24}。設(shè)用D表示I+

中的“除法”關(guān)系，亦即對(duì)于任何a,b∈I+來說有，aDb，當(dāng)且僅當(dāng)a整除b。，于是，(S6,D),(S8,D),(S24,D)和(S30,D)都是格。

【例6.4】設(shè)S是所有的命題集合，定義“

”關(guān)系如下：

A

B當(dāng)且僅當(dāng)B蘊(yùn)涵A

則(S,

)是一個(gè)格。對(duì)

A,B∈S，

sup{A,B}＝A∧B∈Sinf{A,B}＝A∨B∈S定義6.2若格L的一個(gè)子集M≠Ф對(duì)于運(yùn)算

和

封閉，則M稱作子格。例如：a是格L的一個(gè)固定元素，則使X≥a(或X≤a)的L中元素X的集合，顯然是一個(gè)子格。若a≥b，則使a≥X≥b的L中元素X的集合是一個(gè)子格，這樣的子格叫作一個(gè)閉區(qū)間(商)，記作M(a,b)。

還可以將格定義為一個(gè)代數(shù)系統(tǒng)，在這個(gè)代數(shù)系統(tǒng)中，可以定義一個(gè)偏序關(guān)系。這樣就可以把與代數(shù)系統(tǒng)有關(guān)的許多概念應(yīng)用于格。定義6.3設(shè)(L,

,

)是一個(gè)代數(shù)系統(tǒng)，其中L是一個(gè)集合，

,

是L上兩個(gè)二元代數(shù)運(yùn)算，如果若對(duì)于L中任意元素a、b、c，二元運(yùn)算都滿足下列條件時(shí)： 交換律：a

b＝b

a，a

b＝b

a。 結(jié)合律：a

(b

c)＝(a

b)

c，a

(b

c)＝(a

b)

c。 吸收律：a

(a

b)＝a，a

(a

b)＝a。 則稱此代數(shù)系統(tǒng)(L,

,

)為一個(gè)格。

定義中沒有要求

,

運(yùn)算滿足等冪律，實(shí)際上由

,

滿足吸收律即可推出它們一定滿足等冪律。任取L中元素a，由

,

滿足吸收律知

a

(a

a)＝a a

(a

a)＝a

故 a

a＝a

(a

(a

a)) a

a＝a

(a

(a

a))

又由

,

滿足吸收律知，上面兩式的等式右端都等于a。因此， a

a＝a a

a＝a 即定義6.3中的

,

運(yùn)算亦滿足等冪律。同樣，

,

運(yùn)算滿足保序性。設(shè)(L,≤)是一個(gè)格，任取L中元素a,b,c,d，容易得出，

b≤c

a

b≤a

c，a

b≤a

c a≤c，b≤d

a

b≤c

d，a

b≤c

d可以看出，定義6.3給出了格的充分條件?！纠?.5】設(shè)S是一個(gè)集合，

(S)是S的冪集合，集合的交∩，并∪是

(S)上的兩個(gè)代數(shù)運(yùn)算，于是，(

(S),∩,∪)是一個(gè)格。而由例9.1知(

(S),

)是半序格。易見對(duì)

A,B∈

(S)，有

A

B

A∩B＝AA∪B＝B【例6.6】設(shè)Z

是所有正整數(shù)集合，兩個(gè)正整數(shù)的最大公因數(shù)

，最小公倍數(shù)

可看作是Z

上兩個(gè)代數(shù)運(yùn)算，于是，(Z

,

,

)是一個(gè)格。而由例6.2知(Z

,D)是半序格。易見，對(duì)任意a,b∈Z

，有

(a整除b)aDb

a

b＝a

a

b＝b

【例6.7】設(shè)n是一個(gè)正整數(shù)，Sn

是n的所有因數(shù)的集合，兩個(gè)正整數(shù)的最大公因數(shù)

，最小公倍數(shù)

可看作是Sn

上兩個(gè)代數(shù)運(yùn)算，于是，(Sn,

,

)是一個(gè)格。定理6.1關(guān)于格的兩種定義（定義6.1和定義6.3）是等價(jià)的。亦即，任意一個(gè)偏序格都可以對(duì)應(yīng)一個(gè)代數(shù)格；任意一個(gè)代數(shù)格也都可以對(duì)應(yīng)一個(gè)偏序格。證明：⑴若(L,≤)是一個(gè)格，則對(duì)任意a,b∈L，記 inf{a,b}為a

b；sup{a,b}為a

b。 由于對(duì)任意a,b，其inf{a,b}，sup{a,b}

是唯一的，所以，如上定義的

,

是集合L上的兩種二元代數(shù)運(yùn)算。不難證明，對(duì)于

,

滿足交換律，結(jié)合律，吸收律。只證明吸收律：a

(a

b)＝a，其它算律的證明留給讀者。因?yàn)閍

(a

b)是a與(a

b)的最大下界，所以a

(a

b)≤a；

另一方面，由于a≤a，a≤a

b，所以，a是a與a

b的下界， 故a≤a

(a

b)，故a＝a

(a

b)。 因此，根據(jù)定義6.3，(L,

,

)是一個(gè)格。⑵若代數(shù)系統(tǒng)(L,

,

)是一個(gè)格，在集合L上定義一個(gè)關(guān)系≤如下：對(duì)任意a,b∈L，a≤b

a

b＝a

求證≤是一個(gè)偏序關(guān)系。 因?yàn)閍

a＝a

(a

(a

a))＝a，所以有a≤a。 若有a≤b，b≤a，則應(yīng)有a

b＝a，b

a＝b，而a

b＝b

a，所以a＝b。 若a≤b，b≤c，則有a

b＝a，b

c＝b， 故a

c＝(a

b)

c＝a

(b

c)＝a

b＝a， 亦即，有a≤c。

由此證明了關(guān)系≤具有反身性，反對(duì)稱性，傳遞性。故≤是偏序關(guān)系。不難證明：a

b＝a

a

b＝b。若a

b＝a，則a

b＝(a

b)

b＝b。若a

b＝b，則a

b＝a

(a

b)＝a。因此，對(duì)任意a,b∈L，a≤b

a

b＝b。下面證明，對(duì)任意{a,b}?L，存在inf{a,b}，sup{a,b}， 就此結(jié)束定理的證明。由吸收律知

a

(a

b)＝a，b

(a

b)＝b故有a≤(a

b)，b≤(a

b)。 亦即，a

b是{a,b}的上界。若c∈L，且c是{a,b}的上界，亦即a≤c,b≤c，則有a

c＝c,b

c＝c，于是，

(a

b)

c＝(a

b)

(c

c)＝(a

c)

(b

c)＝c

c＝c故有(a

b)≤c。這就說明了(a

b)是{a,b}的最小上界，即sup{a,b}＝(a

b)。同理可證，inf{a,b}＝(a

b)。 證畢

故(L,≤)稱為半序格，(L,

,

)稱為代數(shù)格。由此定理知，給出一個(gè)半序格(L,≤)，就有一個(gè)與之等價(jià)的代數(shù)格(L,

,

)。反之，給出一個(gè)代數(shù)格(L,

,

)，就有一個(gè)與之等價(jià)的半序格(L,≤)。 互為等價(jià)的兩個(gè)格：(L,≤)和(L,

,

)，其

,

分別是在偏序關(guān)系≤下的最大下界運(yùn)算和最小上界運(yùn)算。 基于上述結(jié)果，我們對(duì)偏序格和代數(shù)格不從概念上加以區(qū)分，而統(tǒng)一將它們稱為格，當(dāng)提及一個(gè)格時(shí)，既可以將其理解為偏序格，也可以將其理解為代數(shù)格。

定義6.4設(shè)(L,

,

)是一個(gè)格，S是L的一個(gè)子集，(S,

,

)稱為(L,

,

)的一個(gè)子格，當(dāng)且僅當(dāng)在運(yùn)算

,

下，S是封閉的。顯然，子格是一個(gè)格。例如，(Sn,

,

)是(Z

,

,

)的子格，其中

,

分別是最大公因數(shù)和最小公倍數(shù)。從定義6.4不難說明，若(L,

,

)是一個(gè)格，S?L，并且(S,

,

)也是格，則(S,

,

)是(L,

,

)的子格。亦即：(S,

,

)是格(L,

,

)的子格的充要條件是：S?L且(S,

,

)是一個(gè)格。

最后指出一點(diǎn)：設(shè)(L,≤)是一個(gè)格，與其等價(jià)的代數(shù)格為(L,

,

)，S是L的一個(gè)子集。若(S,≤)是定義6.4下的(L,

,

)的子格，則顯然，(S,≤)是定義6.2下的(L,≤)的子格；若(S,≤)是定義6.2下的(L,≤)的子格，則(S,

,

)不一定是定義6.4下的(L,

,

)的子格。下面給出與格相關(guān)的重要概念和事實(shí)。一個(gè)元的格是顯見的。兩個(gè)元的格即B＝{0,1}，三個(gè)元的格僅有一種，四個(gè)元的格有兩種，五個(gè)元的格有五種，六個(gè)元的格有十五種……，它們中的部分哈斯圖如下圖所示：

一元格二元格三元格四元格

五元格

一元格、二元格、三元格、四元格、五元格的哈斯圖

定義6.5若一個(gè)格的集合的每一個(gè)非空子集，都含有一個(gè)上確界和一個(gè)下確界，則稱此種格是完全格。例如：任一集的所有子集的集合與包含關(guān)系構(gòu)成的格是完全格，有理數(shù)與數(shù)的大小關(guān)系構(gòu)成的格不是完全格。由定義可知，每一個(gè)完全格都必定有一個(gè)最大元素和一個(gè)最小元素。

定義6.6由有限元素所作成的格，稱為有限格。在有限格的圖示中，不出現(xiàn)以三個(gè)元素為頂點(diǎn)并且邊上不含其他元素的三角形。顯然每一個(gè)有限格必定是完全格。

6.1.2格的性質(zhì)

1.對(duì)偶原理設(shè)有兩個(gè)格(L,≤)和(L,≥)，

和

是其中的并與交運(yùn)算，若用

取代

，用

代替

；用≥取代≤，用≤取代≥，則關(guān)于格(L,≤)和(L,≥)的任何命題，都仍歸保持有效。這就是格的對(duì)偶性原理，這個(gè)對(duì)偶性原理說明：如同關(guān)系≤和≥互為對(duì)偶一樣，運(yùn)算

和

也互為對(duì)偶；類似地得到，格(L,≤)和(L,≥)也互為對(duì)偶。從格的定義可知，格的對(duì)偶仍是格，即格的概念是自對(duì)偶的。對(duì)有限格，互相對(duì)對(duì)偶的格的哈斯圖正好上下顛倒。下面我們將對(duì)這一原理進(jìn)行詳細(xì)闡述。

定義6.7集合L中的偏序關(guān)系R與其逆關(guān)系R

1，稱為互相對(duì)偶的兩個(gè)關(guān)系。對(duì)任意x,y∈L，xR

1y

yRx。

6.1.1節(jié)例6.4中的

關(guān)系即為蘊(yùn)涵關(guān)系

的逆關(guān)系。因此，對(duì)任意P,Q∈S，

(P

Q)

(Q

P)命題6.1若R是偏序關(guān)系，則R

1也是偏序關(guān)系。證明：因?yàn)閷?duì)任意x∈L，xRx，因此有xR

1x。故R

1滿足反身性。 若xR

1y，yR

1x，則有yRx，xRy，因此，x＝y(tǒng)。故R

1

滿足反對(duì)稱性。 若xR

1y，yR

1z，則有yRx，zRy，因此，zRx，即xR

1z。故R

1滿足傳遞性。命題6.2(L,R)中sup{a,b}＝d

(L,R

1)

中inf{a,b}＝d(L,R)中inf{a,b}＝d

(L,R

1)

中sup{a,b}＝d

該結(jié)論的證明留給讀者作為練習(xí)。 顯然，對(duì)于L的任意子集A，A在偏序集(L,R)中的最小上界就是A在偏序集(L,R

1)中的最大下界，A在(L,R)中的最大下界就是A在(L,R

1)中的最小上界。因此有：

命題6.3如果偏序集(L,R)是格，則偏序集(L,R

1)也是格，反之亦然。設(shè)格(L,R)是有最小元素0，最大元素1的格。格(L,R)與格(L,R

1)稱為互相對(duì)偶的兩個(gè)格。定義6.8格(L,R)中的表達(dá)式是由如下規(guī)則生成的符號(hào)串：

(1)0,1及變量X是表達(dá)式，X可以是L中任意元素，0,1分別是(L,R)中最小、最大元素。

(2)若A,B是表達(dá)式，則(A

B),(A

B)是表達(dá)式，其中

,

分別是格(L,R)中的最小上界和最大下界運(yùn)算。

(3)格(L,R)中所有表達(dá)式，都是有限次使用⑴、⑵生成的符號(hào)串。定義6.9設(shè)(L,R)是一個(gè)格。(L,R)中的最小上界和最大下界運(yùn)算分別為

1,

1；(L,R

1)中的最小上界和最大下界運(yùn)算分別為

2,

2；E是格(L,R)中一個(gè)表達(dá)式。如果將E中

1

換為

2，

1

換為

2，將所得的格(L,R

1)中的表達(dá)式記為E*，則稱E*為E在其對(duì)偶格中的對(duì)偶表達(dá)式。定義6.10設(shè)(L,R)是一個(gè)格，其中最小上界和最大下界運(yùn)算分別為

,

,E是格(L,R)中的表達(dá)式。如果將E中的

換為

，

換為

，0換為1（當(dāng)E中有0時(shí)），1換為0（當(dāng)E中有1時(shí)），所得的表達(dá)式記為E*，則稱E*為E之對(duì)偶表達(dá)式。引理6.1若XRY在格(L,R)中成立，則Y*R

1X*在對(duì)偶格(L,R

1)中成立，其中X*,Y*分別是表達(dá)式X,Y的在對(duì)偶格中的對(duì)偶表達(dá)式。證明：因?yàn)閷?duì)任意a,b∈L，都有

a

1b＝a

2b a

1b＝a

2b

所以，將X,Y,X*,Y*中每一變量都以L中任意元素代替，得X0,Y0,X0*,Y0*，有

X0*＝X0，Y0*＝Y(jié)0

故有X0*RY0*，即有Y0*R

1X0*。由于代入變量的元素的任意性，故有Y*R

1X*。定理6.2對(duì)偶原理1若XRY在格(L,R)中成立，則Y*RX*也在此格中成立，其中表達(dá)式X*,Y*分別是表達(dá)式X,Y的對(duì)偶表達(dá)式。證明：因?yàn)閄RY在(L,R)中成立，所以X’R

1Y’

在(L,R

1)中成立，其中X’’,Y’’

分別是將X,Y中的

1

換為

2，

1

換為

2，0換為1（當(dāng)X或Y中有0時(shí)），1換為0（當(dāng)X或Y中有1時(shí)）所得之表達(dá)式。由引理6.1知，(Y’)*R(X’)*在(L,R)中成立，其中(Y’)*,(X’)*分別是,在其對(duì)偶格中的對(duì)偶表達(dá)式。 由X’,Y’,(X’)*,(Y’)*的定義知：

(X’)*＝X*,(Y’)*＝Y(jié)*， 其中X*,Y*分別是X,Y的對(duì)偶表達(dá)式。 故Y*RX*在(L,R)中成立。

將格看作一種代數(shù)系統(tǒng)，我們知道，這個(gè)代數(shù)的公理系統(tǒng)是對(duì)偶的。亦即，對(duì)于該系統(tǒng)的每一條公理，其對(duì)偶表達(dá)式組成的等式也是該系統(tǒng)的公理。所以，在格中利用公理推導(dǎo)出的一切結(jié)論都應(yīng)該是對(duì)偶的。也就是說，如果從格的公理H1,H2,…,Hm

演繹出結(jié)論C，即C在格中成立，那么將此演繹的每一步中，凡是使用公理Hi(i＝1,2,…,m)的地方，都換成對(duì)偶公理Hi*(i＝1,2,…,m)，于是演繹出的結(jié)論就是C的對(duì)偶關(guān)系式C*，即C*在格中也成立。所謂C的對(duì)偶關(guān)系是指將C中的表達(dá)式換為對(duì)偶表達(dá)式，C中的關(guān)系換為對(duì)偶關(guān)系所得的關(guān)系式。例如：在格中等冪律是成立的。

a

a＝a

(a

(a

a))＝a對(duì)偶地可得：

a

a＝a

(a

(a

a))＝a

所以，如果在格L中，加入某一個(gè)條件G，而能得出一個(gè)結(jié)論C，那么將G看作是格中一條新的公理，把G的對(duì)偶關(guān)系式G*也作為新公理加到格中，于是C的對(duì)偶關(guān)系式C*，在格中，在條件G*下也應(yīng)該成立。因此，下面的對(duì)偶原理是成立的。定理6.3對(duì)偶原理2在格(L,R)中，若在條件HRG下，有XRY，則在對(duì)偶條件H*R

1G*下，有X*R

1Y*。其中H*,G*,X*,Y*分別是H,G,X,Y的對(duì)偶表達(dá)式。 證明略。2.格的其它性質(zhì)定理6.4設(shè)(L,≤)是一個(gè)格，a,b是L中任意元素，于是 a≤b

a

b＝a

a

b＝b證明：若a≤b，因?yàn)閍≤a，所以a是{a,b}的下界， 故a≤a

b。 而a

b是{a,b}的最大下界，所以a

b≤a。 故a

b＝a。 若a

b＝a，由吸收律知a

b＝(a

b)

b＝b， 若a

b＝b，由a

b的定義知，b是{a,b}的最小上界，當(dāng)然有a≤b。定理6.5設(shè)(L,≤)是一個(gè)格，a,b,c是L中任意元素，如果b≤c，則有

a

b≤a

c a

b≤a

c證明：因?yàn)閎≤c，所以由定理6.4知b

c＝b，又因?yàn)?/p>

(a

b)

(a

c)＝(a

a)

(b

c)＝a

(b

c)＝a

b

再由定理9.3知：a

b≤a

c。 同理可證得第二個(gè)不等式。定理6.6設(shè)(L,≤)是一個(gè)格，a,b,c是L中任意元素。于是有a

(b

c)≤(a

b)

(a

c) a

(b

c)≥(a

b)

(a

c)

其中關(guān)系“≥”是關(guān)系“≤”的對(duì)偶關(guān)系。證明：因?yàn)閍≤a

b，a≤a

c，所以，由

的定義知

a≤(a

b)

(a

c)(6.1)

又因?yàn)閎

c≤b≤a

b,b

c≤c≤a

c

所以，再由

的定義知

b

c≤(a

b)

(a

c)(6.2)

由

的定義及(9.1),(9.2)式知

a

(b

c)≤(a

b)

(a

c)

對(duì)偶地可證得另一不等式。注意，在一般格中，分配律不是總成立的，但上述分配不等式總是成立的。定理6.7設(shè)(L,≤)是一個(gè)格，a,b,c是L中任意元素，于是，a≤b

a

(b

c)≤b

(a

c)證明：若a≤b，則由定理6.4知：a

b＝b。由定理6.6知

a

(b

c)≤(a

b)

(a

c)＝b

(a

c)

若a

(b

c)≤b

(a

c)，則由

的定義知

a

(b

c)≥a

由

的定義知

b

(a

c)≤b

故a≤b。6.1.3格的同態(tài)與同構(gòu)定義6.11設(shè)(L,

,

)和(S,∧,∨)是兩個(gè)格，L到S內(nèi)的映射g稱為(L,

,

)到(S,∧,∨)的格同態(tài)映射，如果對(duì)任意a,b∈L，都有

g(a

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

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

格L到L內(nèi)的同態(tài)映射稱為格的自同態(tài)映射。若g是L到S上的同態(tài)映射，且是一對(duì)一的，則稱g是格同構(gòu)映射，并稱格L與格S是同構(gòu)的。顯然，若g是格L到格S上的同構(gòu)映射，則必定存在S到L上的g的逆映射g

1，并且對(duì)L中任意元素х，S中任意元素y，都有

g

1(g(х))＝х,g(g

1(y))＝y(tǒng)【例6.8】設(shè)S＝{a,b}，

(S)＝{Φ,{a},,{a,b}}是S的冪集合，則(

(S),∩,∪)是一個(gè)格。證明：設(shè)L＝{0,1}，規(guī)定0≤1，∧,∨分別是集合L中兩個(gè)元素在≤下的最大下界，最小上界運(yùn)算，則(L,∧,∨)是一個(gè)格。規(guī)定映射g為：

g({a})＝1,g({a,b})＝1,g()＝0,g(Φ)＝0

則顯然g是

(S)到L上的映射，求證g是同態(tài)映射。 首先證對(duì)任意A,B∈

(S)，g(A∩B)＝g(A)∧g(B)

（1）若a∈A∩B，則a∈A，a∈B，故

g(A∩B)＝1,g(A)∧g(B)＝1∧1＝1 （2）若a

A∩B，則 g(A∩B)＝0,1∧0＝0a∈A,a

B g(A)∧g(B)＝0∧1＝0 a

A,a∈B 0∧0＝0a

A,a

B

綜上，g(A∩B)＝g(A)∧g(B)。再證對(duì)任意A,B∈

(S)，g(A∪B)＝g(A)∨g(B)

（1）若a∈A∪B，則g(A∪B)＝1,1∨0＝1a∈A,a

Bg(A)∨g(B)＝0∨1＝1a

A,a∈B1∨1＝1a∈A,a∈B

（2）若a

A∪B，則a

A，a

B，故

g(A∪B)＝0,g(A)∨g(B)＝0∨0＝0。 綜上，g(A∪B)＝g(A)∨g(B)。 因此，g是

(S)到L上的同態(tài)映射。【例6.9】設(shè)S＝{a,b}，

(S)＝{Φ,{a},,{a,b}}是S的冪集合，則(

(S),∩,∪)是一個(gè)格。證明：規(guī)定映射g為：

g(Φ)＝g({a})＝Φ，g()＝g({a,b})＝

顯然，g為

(S)到

(S)內(nèi)的映射。求證g是同態(tài)映射。 不難驗(yàn)證對(duì)任意A,B∈

(S)，有： 若b∈A∪B，則g(A∪B)＝g(A)∪g(B)＝； 若b

A∪B，則g(A∪B)＝g(A)∪g(B)＝Φ。 若b∈A∩B，則g(A∩B)＝g(A)∩g(B)＝； 若b

A∩B，則g(A∩B)＝g(A)∩g(B)＝Φ。 因此，g(A∪B)＝g(A)∪g(B)，

g(A∩B)＝g(A)∩g(B)。g為此格的自同態(tài)映射?！纠?.10】設(shè)S＝{a,b,c}，則

(S)＝{Φ,{a},,{c},{a,b},{b,c},{a,b,c}}是S的冪集合，則(

(S),∩,∪)是一個(gè)格。證明：設(shè)S30是30的所有正因數(shù)的集合，

,

分別是求兩個(gè)正整數(shù)的最大公因數(shù)、最小公倍數(shù)，則(S30,

,

)是一個(gè)格。規(guī)定映射g為：

Φ

1,{a}

2,

3,{c}

5,{a,b}

6, {a,c}

10,{b,c}

15,{a,b,c}

30

則顯然g為

(S)到S30上的1－1映射。不難驗(yàn)證對(duì)任意A,B∈

(S)，有：

g(A∪B)＝g(A)

g(B),g(A∩B)＝g(A)

g(B)

因此，g為

(S)到S30上的同構(gòu)映射。且g

1是S30到

(S)上的同構(gòu)映射，有：

g

1(g(х))＝х,x∈

(S)g(g

1(y))＝y(tǒng),y∈S30定理6.8設(shè)(L,

,

)和(S,∧,∨)是兩個(gè)格。集合L上對(duì)應(yīng)于運(yùn)算

,

的偏序?yàn)椤躄，集合S上對(duì)應(yīng)于運(yùn)算∧,∨的偏序?yàn)椤躍。如果g是L到S內(nèi)的同態(tài)映射，則g是保序映射，亦即，對(duì)任意a,b∈L，若a≤Lb，則g(a)≤Sg(b)。證明：因?yàn)閍≤b

a

b＝a，所以g(a

b)＝g(a)，而

g(a

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

故g(a)≤Sg(b)。定理6.9設(shè)(L,

,

)是一個(gè)格，g是此格的自同態(tài)映射，于是g(L)是(L,

,

)的子格（定義6.2）。證明：任取g(L)中兩個(gè)元素a’,b’

。于是a’,b’

一定是L中某兩個(gè)元素a,b在g下的映像。亦即，

a’＝g(a),b’＝g(b)

因?yàn)間是格(L,

,

)的自同態(tài)映射，所以

a’b’＝g(a)

g(b)＝g(a

b)∈g(L) a’b’＝g(a)

g(b)＝g(a

b)∈g(L)

即在運(yùn)算

,

下，g(L)是封閉的。 故(g(L),

,

)是(L,

,

)的子格。定理6.10設(shè)(L,

,

)，(S,∧,∨)是兩個(gè)格，若g是L到S上的同構(gòu)映射，則g的逆映射g

1是S到L上的同構(gòu)映射。 證明：顯然g

1是S到L上的一對(duì)一映射。 下面證明g

1是S到L上的同態(tài)映射。 任取a’,b’∈S，令g

1(a’)＝a,g

1(b’)＝b。于是g(a)＝a’,g(b)＝b’ g

1(a’∧b’)＝g

1(g(a)∧g(b))

＝g

1(g(a

b))

＝a

b＝g

1(a’)

g

1(b’) g

1(a’∨b’)＝g

1(g(a)∨g(b))

＝g

1(g(a

b))

＝a

b＝g

1(a’)

g

1(b’)

故g

1是S到L上的同構(gòu)映射。推論6.1若格(L,

,

)和格(S,∧,∨)同構(gòu)，g是其同構(gòu)映射，則對(duì)L中任意兩個(gè)元素a,b，有

a≤Lb

g(a)≤Sg(b)

其中≤L,≤S分別是集合L,S上對(duì)應(yīng)于運(yùn)算

,∧的偏序關(guān)系。 此推論的證明留給讀者。

取L＝{0,1}，規(guī)定0≤1。于是，不難看出(L,≤)是一個(gè)格，并且令(L,∧,∨)是與之等價(jià)的代數(shù)格，則∧,∨分別是集合L中兩個(gè)元素的最大下界，最小上界運(yùn)算。令Ln＝{(a1,a2,…,an)∣ai∈L,i＝1,2,…,n}

規(guī)定：(a1,a2,…,an)≤n(b1,b2,…,bn)

ai≤bi

(i＝1,2,…,n)

指出一點(diǎn)，對(duì)于格的一個(gè)無窮子集，引理6.2的結(jié)論不成立。例如，在格(Z

,≤)中，所有正偶數(shù)組成的集合記為E

，顯然，E

?Z

，但E

沒有最小上界。于是，不難證明：(Ln,≤n)是一個(gè)格，通常稱為n維格。令與(Ln,≤n)等價(jià)的代數(shù)格為(Ln,

,

)，對(duì)Ln中任意兩個(gè)元素(a1,a2,…,an),(b1,b2,…,bn)，顯然有

(a1,a2,…,an)

(b1,b2,…,bn)＝(a1∧b1,a2∧b2,…,an∧bn)(a1,a2,…,an)

(b1,b2,…,bn)＝(a1∨b1,a2∨b2,…,an∨bn)【例6.11】設(shè)S是含n個(gè)元素的集合，

(S)是S的冪集合，于是，格(

(S),?)與格(Ln,≤n)同構(gòu)。證明：令S＝{s1,s2,…,sn}。令g是

(S)到Ln上的映射如下：任取A∈

(S)，

g(A)＝(a1,a2,…,an)

其中ai＝1

si∈A，i＝1,2,…,n。顯然，g是

(S)到Ln上的一對(duì)一映射。任取A,B∈

(S)，令g(A)＝(a1,a2,…,an)，

g(B)＝(b1,b2,…,bn)，

g(A∩B)＝(c1,c2,…,cn)，于是由g的定義知：

ai＝1

si∈A，i＝1,2,…,n bi＝1

si∈B，i＝1,2,…,n ci＝1

si∈A∩B，i＝1,2,…,n于是，不難看出：

ci＝1

ai＝1同時(shí)bi＝1，i＝1,2,…,n因此，ci＝ai∧bi，故

(c1,c2,…,cn)＝(a1∧b1,a2∧b2,…,an∧bn)

＝(a1,a2,…,an)

(b1,b2,…,bn)

即，g(A∩B)＝g(A)

g(B)。同理可證得：g(A∪B)＝g(A)

(B)。故(

(S),∩,∪)與(Ln,

,

)同構(gòu)。1.有界格在一個(gè)格里，任意一對(duì)元素都有一個(gè)最大下界和一個(gè)最小上界，推廣這個(gè)事實(shí)。引理6.2設(shè)(L,≤)是一個(gè)格。若S是L的任意一個(gè)有限非空子集，則S有一個(gè)最大下界和一個(gè)最小上界。 證明留給讀者。記集合S的最大下界為infS；集合S的最小上界為supS。6.1.4幾種特殊的格定義6.12在格(L,≤)中，若存在最大元素和最小元素，通常稱之為格的域界或界，并分別記作1和0。若一個(gè)格有域界1和0，則稱此種格為有界格。設(shè)：(L,

,

,0,1)是一個(gè)有界格，根據(jù)依定義6.12，對(duì)于所有的a∈L有a≤1和a≥0。顯然得到有界格的如下性質(zhì)：引理6.3在有界格(L,

,

,0,1)中，對(duì)于所有的a∈L，都有如下恒等式成立：

a

0＝a，a

1＝a a

1＝1，a

0＝0

另外，在一個(gè)有界格中，1和0是互為對(duì)偶的，因此根據(jù)對(duì)偶性原理也可以交換1和0。定義6.13在有界格(L,

,

,0,1)中，若元素a、b∈L，且有

a

b＝0，a

b＝1

則稱元素a和元素b互為余元素或余。A的余元素通常用a’

或來表示。任意元素a可以有余元素，也可以沒有余元素；如果有余元素，則可以有一個(gè)或一個(gè)以上的余元素。由引理6.3可知0和1互為余元素。引理6.4在有界格(L,

,

,0,1)中，1是0的唯一余元素，0也是1的唯一余元素。證明：因?yàn)橛梢?.3知，

0

1＝0，0

1＝1

所以，0,1互為余元素。 若c∈L，且c≠1，c是0的余元素，

0

c＝0，0

c＝1

但是，由引理6.3知，

0

c＝c

故c＝1。因而由c≠1導(dǎo)至一個(gè)矛盾，故1是0的唯一余元素。 同理可證0也是1的唯一余元素。2.有余格定義6.14對(duì)于有界格(L,

,

,0,1)，若L中每一個(gè)元素，都至少有一個(gè)余元素，則稱(L,

,

,0,1)是一個(gè)有余格。【例6.12】n維格(Ln,≤n)是一個(gè)有余格，其中1n＝(1,1,…,1)，0n＝(0,0,…,0)是界。對(duì)任意Ln中元素(a1,a2,…,an)，元素(b1,b2,…,bn)是其余元素，其中

bi＝0

ai＝1i＝1,2,…,nbi＝1

ai＝0i＝1,2,…,n

【例6.13】設(shè)S是一個(gè)集合，

(S)是它的冪集。只要S有n個(gè)元素，(

(S),

)就是有余格。它的域界是Φ和S。其中S的任何子集A的余是集合S

A。顯然，構(gòu)成有余格的必要條件是此格是個(gè)有界格，但這條件并不是充分的。在下圖所示的一些格，格中的某些元素的余元如下：（a）（b）（c）

有余格

圖(a)所示的元素a1

的余元是a2；圖(b)所示的b1

的余元是b2

和b3，

b2

的余元是b1

和b3，b3

的余元是b1

和b2；圖(c)所示的格中a1

的余元是a2

和a3，等等。111000a1a2a1a2a3b1b2b33.分配格分配格是另一種特殊的格。由6.1節(jié)中定理6.6知，對(duì)于任意格，其格中元素都滿足分配不等式，下面我們引進(jìn)一種滿足分配恒等式的特殊格。定義6.15設(shè)(L,

,

)是一個(gè)格，若對(duì)于任意a,b,c∈L，恒有

a

(b

c)＝(a

b)

(a

c) a

(b

c)＝(a

b)

(a

c)

則稱(L,

,

)是一個(gè)分配格。

不是所有的格都是分配格，例如，圖9.4中的一元格、二元格、三元格是分配格，四元格、五元格不是分配格。應(yīng)當(dāng)指出：在分配格定義中的兩個(gè)等式是互為等價(jià)的。因此，對(duì)于格的各元素的所有可能組合，證明這兩個(gè)恒等式之一就夠了。下面給出構(gòu)成分配格的定理及其基本性質(zhì)。引理6.5任意一個(gè)鏈都是一個(gè)分配格。證明：設(shè)格(L,≤)是一個(gè)鏈，任取L中三個(gè)元素a,b,c，試考察下列兩種情況：

(1)a≥b，a≥c，于是a≥b

c， 故

a

(b

c)＝b

c

而 a

b＝b，a

c＝c，所以

(a

b)

(a

c)＝b

c

故 a

(b

c)＝(a

b)

(a

c)。

(2)a≤b或者a≤c，于是a≤(b

c)， 故 a

b(b

c)＝a。 而 (a

b)

(a

c)＝a

所以 a

(b

c)＝(a

b)

(a

c)。

也有很多不是鏈的格是分配格。例如，n維格(Ln,≤n)，格(

(S),)，格(Z

,D)，格(Sn,D)都是分配格。 注意，分配格的任何子格也是分配格，而且對(duì)于所有分配格而言對(duì)偶性原理全都有效。定理6.11德·摩根（DeMorgan）定律設(shè)(L,

,

)是一個(gè)分配格，對(duì)任意元素a,b，若a,b有余元素a’,b’

，則(ab)’

＝a’

b’(ab)＝a’

b’

證明：因?yàn)?a’

b’

)

(a

b)

＝(a’

b’

a)

(a’

b’

b)

＝(1b’

)

(a’

1)

＝1

1＝1

而且(a’

b’

)

(a

b)

＝(a’

a

b)

(b’

a

b)

＝(0

b)

(0

a)

＝0

0＝0

故由余元素定義知，(ab)’＝a’

b’

同理可證另一等式。定理6.12設(shè)格(L,,)是分配格，對(duì)任意a,b,c∈L，如果

a

c＝b

c，a

c＝b

c

則有 a＝b。證明：若(L,,)是分配格， 且a

c＝b

c，a

c＝b

c，則

a＝a(a

c)＝a(b

c)

＝(a

b)(a

c)

＝(a

b)(b

c)＝b(a

c)

＝b(b

c)＝b

推論6.2設(shè)格(L,

,

)是一個(gè)有余分配格，則對(duì)任意a∈L，a的余元素是唯一的。證明：因(L,

,

)是有余格，設(shè)和都是a的余元素，即

aa’＝0，aa’＝1 aa’’＝0，aa’’＝1

故aa’＝aa’’，aa’＝aa’’。 由定理9.5知，a’＝a’’。6.2布爾代數(shù)6.2.1布爾代數(shù)的定義定義6.17一個(gè)有余分配格是一個(gè)布爾代數(shù)。 有余格僅保證了余的普遍性(即每一個(gè)元素皆至少有一個(gè)余元)，但不保證余的唯一性(即對(duì)于同一個(gè)元素可能有多個(gè)余元)；而分配格僅保證了余的唯一性，但不保證余的普遍性；只是在有余分配格中，才吸取了以上兩者的特點(diǎn)，既保證了余元的普遍性又保證了它的唯一性。

布爾代數(shù)首先是一個(gè)格，是個(gè)特殊的格(布爾格)，其特殊性表現(xiàn)在三個(gè)方面，即有界性，有余性和可分配性。另外顯見，在集合B中存在一個(gè)偏序關(guān)系≤，同時(shí)因布爾代數(shù)是個(gè)有余分配格，故前述的關(guān)于有余格、分配格的性質(zhì)在其中皆成立，亦即為布爾代數(shù)的一般性質(zhì)。 因?yàn)椴紶柎鷶?shù)是一個(gè)格，今后將布爾代數(shù)中的運(yùn)算

簡(jiǎn)記為?，稱為乘法。運(yùn)算

簡(jiǎn)記為

，稱為加法。因?yàn)椴紶柎鷶?shù)是有