格和布爾代數(shù)

格和布爾代數(shù)第1頁，共113頁，2023年，2月20日，星期五7.1格與子格

本章將討論另外兩種代數(shù)系統(tǒng)——格與布爾代數(shù)，它們與群、環(huán)、域的基本不同之處是：格與布爾代數(shù)的基集都是一個有序集。這一序關(guān)系的建立及其與代數(shù)運算之間的關(guān)系是介紹的要點。格是具有兩個二元運算的代數(shù)系統(tǒng)，它是一個特殊的偏序集，而布爾代數(shù)則是一個特殊的格。第2頁，共113頁，2023年，2月20日，星期五圖7.1.1第3頁，共113頁，2023年，2月20日，星期五

在第四章，對偏序集的任一子集可引入上確界（最小上界）和下確界（最大下界）的概念，但并非每個子集都有上確界或下確界，例如在圖7.1.1中哈斯圖所示的有序集里，{a，b}沒有上確界，{e，f}沒有下確界。不過，當(dāng)某子集的上、下確界存在時，這個上、下確界是唯一確定的。第4頁，共113頁，2023年，2月20日，星期五

定義7.1.1如果偏序集〈L，〉中的任何兩個元素的子集都有上確界和下確界,則稱偏序集〈L，〉為格（lattice）。雖然偏序集合的任何子集的上確界、下確界并不一定都存在，但存在，則必唯一，而格定義保證了上確界、下確界的存在性。因此我們通常用a∨b表示{a，b}的上確界，用a∧b表示{a，b}的下確界，第5頁，共113頁，2023年，2月20日，星期五圖7.1.2第6頁，共113頁，2023年，2月20日，星期五

并記作a∨b=LUB{a,b}（Leastupperbound）,a∧b=GLB{a,b}(Greatestlowerbound),∨和∧分別稱為并（join）和交（meet）運算。由于對任何a，b，a∨b及a∧b都是L中確定的成員，因此∨,∧均為L上的二元運算。由定義知道，并非所有的偏序集都能構(gòu)成格，我們用Hasse圖表示偏序集，圖7.1.2中哪個能構(gòu)成格？圖7.1.2中哈斯圖（a）、（b）、（c）所規(guī)定的偏序集是格，圖（d）、（e)及圖7.1.1所規(guī)定的偏序集不是格,因為圖中{a,b}無上確界。第7頁，共113頁，2023年，2月20日，星期五【例7.1.1】

（1）對任意集合S，偏序集〈P（S），〉為格，其中并、交運算即為集合的并、交運算，即

B∨C＝B∪C

B∧C＝B∩C

封閉于P(S),這里B,C∈P(S)。（2）設(shè)L為命題公式集合，邏輯蘊涵關(guān)系“”為L上的偏序關(guān)系（指定邏輯等價關(guān)系“

”為相等關(guān)系），那么，〈L,〉為格，對任何命題公式A，B，A∨B=A∨B，A∧B=A∧B（等式右邊的∨，∧為析取與合取邏輯運算符）。第8頁，共113頁，2023年，2月20日，星期五

（3）設(shè)Z+表示正整數(shù)集，|表示Z+上整除關(guān)系，那么〈Z+，|〉為格，其中并、交運算即為求兩正整數(shù)最小公倍數(shù)和最大公約數(shù)的運算，即

m∨n＝LCM（m,n）m∧n＝gcd（m,n）另外，若將〈L,〉中的小于等于關(guān)系換成大于等于關(guān)系，即對于L中任何兩個元素a,b定義ab的充分必要條件是ba,則〈L,〉也是偏序集。我們把偏序集〈L,〉和〈L,〉稱為是相互對偶的。并且它們所對應(yīng)的哈斯圖是互為顛倒的。關(guān)于格我們有同樣的性質(zhì)。

第9頁，共113頁，2023年，2月20日，星期五

定理7.1.1若〈L,〉是一個格，則〈L,〉也是一個格,且它的并、交運算∨r,∧r對任意a,b∈L滿足

a∨rb=a∧b

a∧rb=a∨b

于是，我們有下列對偶原理。第10頁，共113頁，2023年，2月20日，星期五

定理7.1.2如果命題P在任意格〈L，〉上成立，則將L中符號∨，∧，分別改為∧，∨，后所得的公式P*在任意格〈L，〉上也成立，這里P*稱為P的對偶式。在上述對偶原理中，“如果命題P在任意格

〈L，〉上成立”的含義是指當(dāng)命題P中的變量取值于L中，且上確界運算為∨，下確界運算為∧，則P對于它們也成立。現(xiàn)在我們深入地討論格的性質(zhì)。第11頁，共113頁，2023年，2月20日，星期五

定理7.1.3設(shè)〈L,〉是一個格，那么對L中任何元素a,b,c，有（1）aa∨b，ba∨b

a∧ba，a∧bb

（2）若ab，cd，則a∨cb∨d，a∧cb∧d。（3）若ab，則a∨cb∨c，a∧cb∧c。這個性質(zhì)稱為格的保序性。第12頁，共113頁，2023年，2月20日，星期五

證明（1）因為a∨b是a的一個上界，所以aa∨b；同理有ba∨b。由對偶原理可得a∧ba，a∧bb。（2）由題設(shè)知ab，cd，由（1）有bb∨d，db∨d，于是由的傳遞性有ab∨d，cb∨d。這說明b∨d是a和c的一個上界，而a∨c是a和c的最小上界，所以，必有

a∨cb∨d

將a∧c≤b∧d的證明留給讀者。（3）將（2）中的a代替b，b代替c，c代替d即可得證。第13頁，共113頁，2023年，2月20日，星期五

定理7.1.4設(shè)〈L,〉是一個格，那么對L中任意元素a,b,c，有（1）a∨a=a，a∧a＝a(冪等律)（2）a∨b=b∨a，a∧b=b∧a（交換律）（3）a∨（b∨c）=（a∨b）∨c,a∧（b∧c）

=（a∧b）∧c(結(jié)合律)（4）a∧(a∨b)=a，a∨(a∧b)=a(吸收律)第14頁，共113頁，2023年，2月20日，星期五

證明（1）由自反性可得aa，所以a是a的一個上界，因為a∨a是a與a的最小上界，因此a∨aa。由定理7.1.3的（1）可知aa∨a。由的反對稱性，所以a∨a=a。利用對偶原理可得a∧a＝a。（2）由格的并∨與交∧運算的定義知滿足交換律。第15頁，共113頁，2023年，2月20日，星期五

（3）由下確界定義知a∧（b∧c）b∧cb(7.1.1)a∧（b∧c）a(7.1.2)a∧（b∧c）b∧cc(7.1.3)由式(7.1.1)、(7.1.2)得a∧（b∧c）a∧b(7.1.4)第16頁，共113頁，2023年，2月20日，星期五

由式(7.1.3)、(7.1.4)得a∧（b∧c）(a∧b)∧c(7.1.5)

同理可證（a∧b）∧ca∧（b∧c）

（7.1.6）由的反對稱性和式(7.1.5)、(7.1.6)，所以

a∧（b∧c）=（a∧b）∧c。利用對偶原理可得

a∨（b∨c）=（a∨b）∨c。第17頁，共113頁，2023年，2月20日，星期五

（4）由定理7.1.3的（1）可知a∧（a∨b）a；另一方面，由于aa，aa∨b，所以aa∧（a∨b），因此有a∧(a∨b)=a。

a∧(a∨b)=a的證明留給讀者。由定理可知，格是帶有兩個二元運算的代數(shù)系統(tǒng)，它的兩個運算有上述四個性質(zhì)，那么具有上述四條性質(zhì)的代數(shù)系統(tǒng)〈L,∧,∨〉是否是格？回答是肯定的。為了解決這個問題，我們再進(jìn)一步介紹格的下述性質(zhì)。第18頁，共113頁，2023年，2月20日，星期五

定理7.1.5設(shè)〈L,〉是一個格。那么對L中任意元素a,b,c，有（1）ab當(dāng)且僅當(dāng)a∧b=a當(dāng)且僅當(dāng)a∨b=b。（2）a∨（b∧c）（a∨b）∧（a∨c）。（3）ac當(dāng)且僅當(dāng)a∨(b∧c)（a∨b）∧c。第19頁，共113頁，2023年，2月20日，星期五

證明（1）首先設(shè)ab，因為aa,所以aa∧b，而由定理7.1.3的（1）可知

a∧ba。因此有a∧b=a。再設(shè)a=a∧b，則a∨b=（a∧b）∨b=b（由吸收律），即a∨b=b。最后，設(shè)b＝a∨b，則由aa∨b可得ab。因此，（1）中3個命題的等價性得證。第20頁，共113頁，2023年，2月20日，星期五

（2）因為aa∨b，aa∨c,故

a（a∨b）∧（a∨c）。又因為b∧cba∨b，b∧cca∨c(7.1.7)所以有b∧c（a∨b）∧（a∨c）

(7.1.8)由式（7.1.7）和（7.1.8）可得

a∨（b∧c）（a∨b）∧（a∨c）第21頁，共113頁，2023年，2月20日，星期五（3）設(shè)a∨(b∧c)（a∨b）∧c。由于aa∨（b∧c），（a∨b）∧cc因此由傳遞性有ac。反之，設(shè)ac，則a∨c=c,代入本定理（2）即得a∨(b∧c)（a∨b）∧c第22頁，共113頁，2023年，2月20日，星期五

定理7.1.6設(shè)L為一非空集合，∨,∧為L上的兩個二元運算，如果〈L，∧,∨〉中運算∧,∨滿足交換律、結(jié)合律和吸收律，則稱〈L，∧,∨〉為格。即在L中可找到一種偏序關(guān)系，在作用下，對任意

a,b∈L,a∧b=GLB{a,b},a∨b=LUB{a,b}。證明先證冪等性成立。由吸收律知a∧a＝a∧（a∨（a∧b））＝aa∨a＝a∨(a∧（a∨b））＝a第23頁，共113頁，2023年，2月20日，星期五

下證有偏序關(guān)系。先定義L上關(guān)系如下；對任意a，b∈L，ab當(dāng)且僅當(dāng)a∧b=a。（1）證為L上偏序關(guān)系。①因為a∧a＝a，故aa。自反性得證。②設(shè)ab，ba，則a∧b=a，b∧a=b。由于a∧b=b∧a，故a=b。反對稱性得證。第24頁，共113頁，2023年，2月20日，星期五③設(shè)ab，bc，則a∧b=a，b∧c=b，于是a∧c=（a∧b）∧c＝a∧（b∧c）＝a∧b=a故ac。傳遞性得證。（2）可證ab當(dāng)且僅當(dāng)a∨b＝b。設(shè)ab，那么a∧b=a，從而（a∧b）∨b＝a∨b,由吸收律即得b=a∨b。反之，設(shè)a∨b＝b，那么a∧（a∨b）＝a∧b，由吸收律可知a＝a∧b，即ab。第25頁，共113頁，2023年，2月20日，星期五

（3）下證在這個關(guān)系下，對任意a,b∈L，a∨b為{a,b}的上確界，即a∨b=LUB{a,b}。由吸收律a∧（a∨b）＝a，所以aa∨b。又因為b∧（a∨b）＝b，所以ba∨b,故a∨b為{a,b}的一個上界。設(shè)c為{a，b}任一上界，即ac，bc，那么，

a∨c＝c,b∨c＝c,于是a∨c∨b∨c＝c∨c亦即a∨b∨c＝c,故a∨b≤c。這表明a∨b為{a，b}的上確界。第26頁，共113頁，2023年，2月20日，星期五

（4）下證在這個關(guān)系下，對任意a,b∈L，a∧b為{a,b}的下確界，即a∧b=GLB{a,b}。由吸收律(a∧b)∧a＝a∧a∧b=a∧b，所以a∧ba。又因為(a∧b)∧b＝a∧(b∧b)=a∧b，所以a∧bb,故a∧b為{a,b}的一個下界。設(shè)c為{a，b}任一下界，即ca且cb，由的定義知a∧c＝c,b∧c＝c,于是c∧（a∧b）＝(c∧a)∧b=c∧b=c所以ca∧b，即a∧b為{a，b}的下確界。因此〈L,〉是格。第27頁，共113頁，2023年，2月20日，星期五

定義7.1.2設(shè)〈S,*,。〉是代數(shù)系統(tǒng)，*，。是S上的二元運算，且*，。滿足交換律、結(jié)合律和吸收律，則〈S,*,?！禈?gòu)成格。

【例7.1.2】

（1）〈P(S),∩,∪〉是一個代數(shù)系統(tǒng)，P(S)是集合S的冪集，因為∩,∪滿足可交換、可結(jié)合并滿足吸收律，所以〈P(S),∩,∪〉是格。事實上該格對應(yīng)的偏序關(guān)系就是S的子集之間的包含關(guān)系。第28頁，共113頁，2023年，2月20日，星期五

（2）〈Sn,*,?！凳且粋€代數(shù)系統(tǒng)，Sn是n的所有因子作元素構(gòu)成的集合,這里對于任意的x,y∈Sn,x*y={x,y}的最大公約數(shù)，x。y={x,y}的最小公倍數(shù)，因為*,。滿足可交換、可結(jié)合并滿足吸收律，所以〈Sn,*,?！凳歉瘢⑶以摳駥?yīng)的偏序關(guān)系就是整除關(guān)系。簡單地說，子格即為格的子代數(shù)。第29頁，共113頁，2023年，2月20日，星期五

定義7.1.3設(shè)〈L,∧,∨〉是一個格，設(shè)非空集合S且SL,若對任意的a,b∈S,有a∧b∈S,a∨b∈S,則稱〈S,∧,∨〉是〈L,∧,∨〉的子格。顯然，子格必是格。而格的某個子集構(gòu)成格，卻不一定是子格。這一點請讀者思考。第30頁，共113頁，2023年，2月20日，星期五

圖7.1.3第31頁，共113頁，2023年，2月20日，星期五【例7.1.3】設(shè)〈L,〉是一個格，其中L={a,b,c,d,e},其哈斯圖如圖7.1.3所示。S1={a,b,c,d}，S2={a,b,c,e},則〈S1,〉是〈L,〉是一個子格，

〈S2,〉不是〈L,〉是一個子格，因為b∧c=dS2，〈S2,〉不是格。類似群的同態(tài)，也可以定義格的同態(tài)。第32頁，共113頁，2023年，2月20日，星期五

定義7.1.4設(shè)〈L,*,〉,〈S,∧,∨〉是兩個格，存在映射f:L→S,a,b∈L滿足f(a*b)=f(a)∧f(b),稱f是交同態(tài);若滿足f(ab)=f(a)∨f(b),稱f是并同態(tài)。若f既是交同態(tài)又是并同態(tài)，稱f為格同態(tài)。若f是雙射，則稱f為格同構(gòu)。定義7.1.5設(shè)〈L,*,〉,〈S,∧,∨〉是兩個格，其中1,2分別為格L,S上的偏序關(guān)系，存在映射f:L→S,a,b∈L，若a1bf(a)2f(b),稱f是序同態(tài)。若f是雙射。則稱f是序同構(gòu)。第33頁，共113頁，2023年，2月20日，星期五

下面介紹格同態(tài)的定理。定理7.1.7設(shè)f是格〈L,1〉到格〈S,2〉的格同態(tài)，則f是序同態(tài)。即同態(tài)是保序的。證明因為a1b，所以

a*b=af(a*b)=f(a)f(a)∧f(b)=f(a)。因此，f(a)2f(b)。第34頁，共113頁，2023年，2月20日，星期五圖7.1.4第35頁，共113頁，2023年，2月20日，星期五【例7.1.4】設(shè)〈L,〉,〈S,〉是格，其中L={a,b,c,d},S={e,g,h}，如圖7.1.4(a)、(b)所示。

作映射f:L→S，f(b)=f(c)=g，f(a)=e，f(d)=h,顯然f滿足序同態(tài)。但f(b*c)=f(a)，f(b)∧f(c)=g≠f(a)，所以不滿足交同態(tài)，因此f不是格同態(tài)。第36頁，共113頁，2023年，2月20日，星期五

定理7.1.8映射f是格〈L,1〉到格〈S,2〉的格同構(gòu)的充分必要條件是a,b∈L，有a1bf(a)2f(b)。證明設(shè)映射f是格〈L,1〉到格〈S,2〉的格同構(gòu)。由定理7.1.7可知a,b∈L，有a1bf(a)2f(b)。反之，f(a)2f(b)f(a)∧f(b)=f(a)f(a*b)=f(a)a*b=a

（f是雙射）a1b第37頁，共113頁，2023年，2月20日，星期五

設(shè)a,b∈L，有a1bf(a)2f(b)。設(shè)a*b=c(要證f(c)是f(a)、f(b)的最大下界),有

c1af(c)2f(a)

c1bf(c)2f(b)

所以f(c)是f(a)、f(b)的一個下界。再設(shè)x是f(a),f(b)的任意下界，因為f是滿射，所以有d∈L,使x=f(d)且

f(d)2f(a)d1a,f(d)2f(b)d1b第38頁，共113頁，2023年，2月20日，星期五

所以d1a*b,即d1cf(d)2f(c)。因此f(c)是f(a),f(b)的最大下界，即f(c)=f(a*b)=f(a)∧f(b)。類似可證f(ab)=f(a)∨f(b)。所以f是〈L,1〉到〈S,2〉的格同構(gòu)。第39頁，共113頁，2023年，2月20日，星期五【例7.1.5】在同構(gòu)意義下，具有1個、2個、3個元素的格分別同構(gòu)于元素個數(shù)相同的鏈。

4個元素的格必同構(gòu)于圖7.1.5中給出的含4個元素的格之一；5個元素的格必同構(gòu)于圖7.1.5中的含5個元素的格之一。其中圖7.1.5(g)稱作五角格，圖7.1.5(h)稱作鉆石格，這兩個格在討論特殊格時會很有用。第40頁，共113頁，2023年，2月20日，星期五圖7.1.5第41頁，共113頁，2023年，2月20日，星期五7.2特殊格

本節(jié)討論幾個特殊的格。定義7.2.1如果在格〈L,〉中，存在一個元素a∈L,均有

ax(xa)

則稱a為格的全下界（全上界）（相應(yīng)于偏序集中的最小元、最大元），且記全下界為0，全上界為1。全下界（全上界）有如下性質(zhì)。第42頁，共113頁，2023年，2月20日，星期五

定理7.2.1全下（上）界如果存在，則必唯一。證明設(shè)1與1′均是全上界，則因為1是全上界，所以1′1；又因為1′是全上界，所以11′。由的反對稱性，所以1=1′。類似可證全下界唯一。第43頁，共113頁，2023年，2月20日，星期五【例7.2.1】在格〈P(S),∩,∪〉中，S是全上界，是全下界。定義7.2.2如果〈L，∧,∨〉中既有全上界1，又有全下界0。稱0，1為格L的界（bound），并稱格L為有界格（boundedlattice）。不難看出，任何有限格必是有界格。而對于無限格，有的是有界格，有的不是有界格。有界格有如下性質(zhì)。第44頁，共113頁，2023年，2月20日，星期五

定理7.2.2設(shè)〈L,〉是有界格，則a∈L,有

a∧0=0,a∧1=a，a∨0=a，a∨1=1。證明留作練習(xí)。定義7.2.3如果格〈L，∧,∨〉若滿足：對任意元素a,b,c∈L，有

aca∨（b∧c）=（a∨b）∧c

則L稱為模格（modulerlattice）。定理7.2.3格L是模格的充分必要條件是它不含有同構(gòu)于五角格的子格。第45頁，共113頁，2023年，2月20日，星期五圖7.2.1第46頁，共113頁，2023年，2月20日，星期五【例7.2.2】如圖7.2.1所示的五角格，它不是模格。因為0cb1,而c∨(a∧b)=c,(c∨a)∧b=b。

定理7.2.4格〈L，∧,∨〉為模格的充分必要條件是：對L中任意元素a,b,c，若ba，a∧c=b∧c,a∨c＝b∨c，則a=b。第47頁，共113頁，2023年，2月20日，星期五

證明先證必要性。設(shè)〈L，∧,∨〉為模格，且

ba，a∧c=b∧c,a∨c＝b∨c，那么，a＝a∨（a∧c）

＝a∨（b∧c）

=b∧(a∨c)

=b∧(b∨c)

=b

第48頁，共113頁，2023年，2月20日，星期五

再證充分性。為證〈L，∧,∨〉為模格，設(shè)ba，需證

a∧（b∨c）＝b∨（a∧c）。首先，據(jù)定理7.1.5之（3），由ba可知b∨（c∧a）（b∨c）∧a(7.2.1）由此

a∧c＝（a∧c）∧c

（b∨（c∧a））∧c

（(b∨c）∧a）∧c

（由式（7.2.1））

=（(b∨c）∧c）∧a=c∧a第49頁，共113頁，2023年，2月20日，星期五

于是（b∨（c∧a））∧c＝（(b∨c）∧a）∧c=c∧a（7.2.2）仿此也可推得（請讀者完成）（b∨(a∧c））∨c=(a∧（b∨c））∨c＝b∨c（7.2.3）因此,根據(jù)題設(shè)及式（7.2.1）、(7.2.2)和（7.2.3）得出a∧（b∨c）＝b∨（a∧c）這表明L滿足模性條件，故〈L，∨,∧〉為模格得證。第50頁，共113頁，2023年，2月20日，星期五

定義7.2.4格〈L，∧,∨〉如果滿足分配律，即對任意a,b,c∈L，有a∧（b∨c）=（a∧b）∨（a∧c）

（7.2.4）

a∨（b∧c）=（a∨b）∧（a∨c）

（7.2.5）則L稱為分配格（distributivelattice）。第51頁，共113頁，2023年，2月20日，星期五

注意到，上述兩個分配等式中有一個成立，則另一個必成立。如式（7.2.4）成立，則

（a∨b）∧（a∨c）

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

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

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

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

=a∨（b∧c）第52頁，共113頁，2023年，2月20日，星期五【例7.2.3】設(shè)S是一個集合，則〈P(S),∩,∪〉構(gòu)成格，而集合中求并∪與求交∩這兩種運算滿足分配律，所以〈P(S),∩,∪〉是分配格。并不是所有的格都是分配格。圖7.2.2第53頁，共113頁，2023年，2月20日，星期五【例7.2.4】如圖7.2.1和圖7.2.2所示的Hasse圖中的格均不是分配格。在圖7.2.2中，有

a∨（b∧c）=a∨0=a(a∨b）∧（a∨c）=1∧1=1

所以不是分配格。第54頁，共113頁，2023年，2月20日，星期五

分配格有以下性質(zhì)：定理7.2.5設(shè)〈L，∧,∨〉為分配格，那么對L中任意元素a，b，c，若c∧a=c∧b并且c∨a=c∨b，則a=b。證明因為（c∧a）∨b＝（c∧b）∨b=b(因c∧a=c∧b）（c∧a）∨b=（c∨b）∧（a∨b）第55頁，共113頁，2023年，2月20日，星期五=（c∨a）∧（a∨b）(因c∨a=c∨b)=a∨（c∧b）＝a∨（c∧a）（因c∧a=c∧b）=a所以a=b。第56頁，共113頁，2023年，2月20日，星期五

定理7.2.6若〈L,〉是鏈，則〈L，〉是分配格。證明設(shè)〈L,〉是鏈，則〈L,〉是全序集，設(shè)對于該集合中任意的a,b,c三個元素，分情況討論：

(1)ba,ca，此時a∧（b∨c）=b∨c，同時（a∧b）∨（a∧c）=b∨c(2)ab,ac，此時a∧（b∨c）=a，同時（a∧b）∨（a∧c）=a因此無論任何情況，皆有a∧（b∨c）=（a∧b）∨（a∧c）。所以〈L，〉是分配格。第57頁，共113頁，2023年，2月20日，星期五

定理7.2.7設(shè)〈L，∧,∨〉為分配格，則〈L，∧,∨〉是模格。證明對于任意的a,b,c∈L，若ab,則a∧b=a,并有

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

因此，〈L，∧,∨〉是模格。下面我們討論補格。定義7.2.5設(shè)〈L，∧,∨〉為有界格，a為L中任意元素，如果存在元素b∈L,使a∨b=1，a∧b=0，則稱b是a的補元或補（complements）。第58頁，共113頁，2023年，2月20日，星期五

補元有下列性質(zhì)：（1）補元是相互的，即若b是a的補，那么a也是b的補。（2）并非有界格中每個元素都有補元，而有補元也不一定唯一。（3）全下界0與全上界1互為補元且唯一。第59頁，共113頁，2023年，2月20日，星期五【例7.2.5】考察圖7.2.3中Hasse圖所示的其格中其元素的補。圖7.2.3（a）中除0，1之外a,b,c均沒有補元。圖7.2.3（b）中a的補元是b,b的補元是a。圖7.2.3（c）中元素a,b,c兩兩互為補元，但不唯一。圖7.2.3（d）中除0，1之外沒有元素有補元。事實上，多于兩個元素的鏈除0，1之外沒有元素有補元。在有界格中，顯然0是1的唯一補元，同時1是0的唯一補元。第60頁，共113頁，2023年，2月20日，星期五圖7.2.3第61頁，共113頁，2023年，2月20日，星期五

定義7.2.6如果有界格〈L，∨,∧〉中每個元素都至少有一個補元，則稱L為補格（complementedlattice）。例7.2.5中（2）、（3）均是有補格，（1）、（4）不是補格。多于兩個元素的鏈都不是有補格。第62頁，共113頁，2023年，2月20日，星期五

定理7.2.8若〈L,∧,∨〉是有補分配格，則a∈L,其補元是唯一的。因此,可用a′來表示a的補元。證明采用反證法：若存在a為L中一元素，有兩補元b，c，且b≠c,則a∨b＝a∨c＝1，a∧b＝a∧c＝0由定理7.2.5有，b＝c，與前面矛盾。因此a只有唯一補元a′。第63頁，共113頁，2023年，2月20日，星期五

定理7.2.9若〈L,∧,∨〉是有補分配格，則a∈L，有a″=（a′）′＝a。證明a″∧a′=0,a″∨a′=1,由補元唯一可得a″=a。定理7.2.10德·摩根律，設(shè)〈L，∨,∧〉是有補分配格，則對L中任意元素a，b，有

(1)（a∧b）′=a′∨b′

（2）（a∨b）′＝a′∧b′第64頁，共113頁，2023年，2月20日，星期五

證明(1)由于（a∧b）∧（a′∨b′）＝((a∧b）∧a′)∨((a∧b）∧b′)＝0（a∧b）∨（a′∨b′）=（a∨a′∨b′）∧（b∨a′∨b′）＝1

因此a′∨b′為a∧b的補元。由補元的唯一性得知：(a∧b）′＝a′∨b′同樣可證（2），其證明留作練習(xí)。第65頁，共113頁，2023年，2月20日，星期五

定理7.2.11對有補分配格的任何元素a，b，有ab當(dāng)且僅當(dāng)a∧b′=0當(dāng)且僅當(dāng)a′∨b=1。

證明若ab，則有a∨b=b，所以a∧b′=(a∧b′)∨(b∧b′)=(a∨b)∧b′=b∧b′=0。若a∧b′=0，則其對偶式a′∨b=1必成立。若a′∨b=1，則a∨b=(a∨b)∧1=(a∨b)∧(a′∨b)=(a∧a′)∨b=0∨b=b。第66頁，共113頁，2023年，2月20日，星期五7.3布爾代數(shù)

定義7.3.1設(shè)B是至少有兩個元素的有補分配格，則稱B是布爾代數(shù)（Booleanalgebra）。

【例7.3.1】〈{0,1},∧,∨,′〉是一個布爾代數(shù)。第67頁，共113頁，2023年，2月20日，星期五【例7.3.2】S≠,則〈P(S),∩,∪,∽〉是一個布爾代數(shù)。其中∩表示集合的交運算,∪表示集合的并運算,∽表示集合的為一元求補集的運算（這里的全集是S）。布爾代數(shù)通常用序組〈B，∧，∨，′，0，1〉來表示。其中′為一元求補運算。為此介紹布爾代數(shù)的另一個等價定義。第68頁，共113頁，2023年，2月20日，星期五

定義7.3.2〈B，∧，∨,′〉是代數(shù)系統(tǒng)，B中至少有兩個二元元素，∧，∨是B上二元運算，′是一元運算，若∧，∨滿足：（1）交換律;

（2）分配律;

（3）同一律。存在0,1∈B,對a∈B，有a∧1=a,a∨0=a;

（4）補元律。對B中每一元素a，均存在元素a′，使a∧a′=0,a∨a′＝1，則稱〈B，∧，∨,′〉是布爾代數(shù)。第69頁，共113頁，2023年，2月20日，星期五

為證定義7.3.1與定義7.3.2等價，只需證B是格，進(jìn)而由（2）、(3)、（4）可斷定B為有補分配格。要證B是格，據(jù)定義7.1.2，只要證B滿足交換律（已有）、結(jié)合律和吸收律。下證B滿足吸收律。先證a∈B，有a∧0=0。第70頁，共113頁，2023年，2月20日，星期五a∧0=(a∧0)∨0(同一律)=（a∧0）∨（a∧a′）（補元律）=a∧（0∨a′）（分配律）=a∧a′(同一律)=0（補元律）第71頁，共113頁，2023年，2月20日，星期五

因為a,b∈B,

a∧(a∨b)＝（a∨0）∧（a∨b）(同一律)

＝a∨（0∧b）（分配律）

=a∨0=a(同一律)

類似可證a∨（a∧b）＝a。因此B滿足吸收律。前面已證明由吸收律可推出滿足冪等律。第72頁，共113頁，2023年，2月20日，星期五

再證B滿足結(jié)合律。因為a,b，c∈B,可如下證明

a∧（b∧c）＝（a∧b）∧c，從而對偶地可證a∨（b∨c）＝（a∨b）∨c。令

X=a∧（b∧c），Y=（a∧b）∧c

那么

a∨X＝a∨(a∧（b∧c）)＝a

（吸收律）

a∨Y=a∨(（a∧b）∧c)

＝(a∨（a∧b）)∧(a∨（a∧c）)（分配律）

=a∧a＝a（冪等律）第73頁，共113頁，2023年，2月20日，星期五

故a∨X＝a∨Y（7.3.1）

a′∨X=a′∨（a∧（b∧c））＝(a′∨a）∧（a′∨(b∧c）)(分配律）

=1∧（a′∨(b∧c）)(補元律）

=（a′∨(b∧c）)(同一律)=（a′∨b）∧（a′∨c）(分配律）

a′∨Y=a′∨（(a∧b）∧c)第74頁，共113頁，2023年，2月20日，星期五=(a′∨（a∧b）)∧(a′∨c)(分配律）=（（a′∨a）∧（a′∨b））∧（a′∨c）(分配律）=（1∧（a′∨b））∧（a′∨c）(補元律）=（a′∨b）∧（a′∨c）(同一律)故a′∨X=a′∨Y（7.3.2）第75頁，共113頁，2023年，2月20日，星期五

由式（7.3.1）和（7.3.2）得（a∨X）∧（a′∨X）＝（a∨Y）∧(a′∨Y)（a∧a′）∨X=(a∧a′）∨Y分配律)0∨X=0∨Y(補元律）X＝Y(jié)（同一律）故a∧（b∧c）＝（a∧b）∧c得證。第76頁，共113頁，2023年，2月20日，星期五【例7.3.3】〈P，∧，∨，，0,1〉為布爾代數(shù)。這里P為命題公式集，∧，∨，為合取、析取、否定的真值運算，0，1分別為假命題、真命題。定義7.3.3設(shè)〈B，∧，∨，′，0，1〉是布爾代數(shù)，S(B,若S含有0,1,且在運算∧，∨，′下是封閉的，則稱S是B的子布爾代數(shù)，記作〈S，∧，∨，′，0，1〉。第77頁，共113頁，2023年，2月20日，星期五圖7.3.1第78頁，共113頁，2023年，2月20日，星期五【例7.3.4】(1)對任何布爾代數(shù)〈B，∨，∧，′，0，1〉恒有子布爾代數(shù)〈B，∨，∧，′，0，1〉和〈{0，1}，∨，∧，′，0，1〉，它們被稱為B的平凡子布爾代數(shù)。（2）如圖7.3.1給出的布爾代數(shù)S1={1，a，f,0}是子布爾代數(shù)，S2={1,a,c,e}不是子布爾代數(shù)，因為0不在S2中。關(guān)于子布爾代數(shù)除了定義外我們還有如下判別定理。第79頁，共113頁，2023年，2月20日，星期五

定理7.3.1設(shè)〈B，∧，∨，′，0，1〉是布爾代數(shù)，SB且S≠,若a,b∈S，a∨b∈S，a′∈S,則S是B的子布爾代數(shù)，記作〈S，∧，∨，′，0，1〉。證明若a,b∈S,則a′,b′∈S,(a′∨b′)′=a∧b∈S。因為S≠,所以存在a∈S，因此a′∈S,所以a∧a′=0∈S和a∨a′=1∈S。第80頁，共113頁，2023年，2月20日，星期五

定義7.3.4設(shè)〈B，∧，∨，′，0，1〉和

〈B*，∩，∪，∽，0，1〉是兩個布爾代數(shù)，若存在映射f：B→B*滿足，對任何元素a，b∈B，有

f（a∧b）＝f（a）∩f（b）

（7.3.4）

f（a∨b）=f（a）∪f（b）

（7.3.5）

f（a′）=∽(f(a))

（7.3.6）則稱f是〈B，∧，∨，′，0，1〉到〈B*，∩，∪，∽，0，1〉的布爾同態(tài)。若f是雙射，則稱f是

〈B，∧，∨，′，0，1〉到〈B*，∩，∪，∽，0，1〉的布爾同構(gòu)。第81頁，共113頁，2023年，2月20日，星期五

下面討論有限布爾代數(shù)的表示定理。定義7.3.5設(shè)B是布爾代數(shù)，如果a是元素0的一個覆蓋，則稱a是該布爾代數(shù)的一個原子（atoms）。例如圖7.3.1中d,e,f均是原子。實際上，在布爾代數(shù)中，原子是B-{0}的極小元，因為原子與0之間不存在其它元素。關(guān)于布爾代數(shù)的原子我們有以下性質(zhì)。第82頁，共113頁，2023年，2月20日，星期五

定理7.3.2設(shè)〈B，∧，∨，′，0，1〉是布爾代數(shù)，B中的元素a是原子的充分必要條件是a≠0且對B中任何元素x有x∧a=a

或x∧a=0

（7.3.7）證明先證必要性。設(shè)a是原子,顯然a≠0。另設(shè)x∧a≠a。由于x∧aa，故0x∧a，x∧aa。據(jù)原子的定義，有x∧a＝0。第83頁，共113頁，2023年，2月20日，星期五

再證充分性。設(shè)a≠0，且對任意x∈B，有x∧a=a或x∧a=0成立。若a不是原子，那么必有b∈B，使0ba。于是，b∧a＝b。因為b≠0，b≠a，故b∧a＝b與式（7.3.7）矛盾。因此a只能是原子。第84頁，共113頁，2023年，2月20日，星期五

定理7.3.3設(shè)a，b為布爾代數(shù)

〈B，∨，∧，′，0，1〉中任意兩個原子，則a=b或a∧b=0。證明分兩種情況來證明。（1）若a,b是原子且a∧b≠0，則

0＜a∧ba(因為a是原子，所以a=a∧b)0＜a∧bb(因為b是原子，所以b=a∧b)

故a=b。第85頁，共113頁，2023年，2月20日，星期五

（2）若a,b是原子且a≠b由原子的性質(zhì)可知:a∧b≠a,a∧b≠b(否則ab或ba)。用反證法，若a∧b≠0，則0＜a∧b＜a,0＜a∧b＜b

與a，b為原子矛盾，故a∧b=0。第86頁，共113頁，2023年，2月20日，星期五

定義7.3.6設(shè)B是布爾代數(shù),b∈B,定義集合A(b)={a|a∈B,a是原子且ab}。例如，圖7.3.1中

A(b)={d,f},A(c)={e,f},A(0)=,A(1)={d,e,f}。引理1設(shè)〈B，∨，∧，′，0，1〉是一有限布爾代數(shù)，則對于B中任一非零元素b，恒有一原子a∈B,

使ab。第87頁，共113頁，2023年，2月20日，星期五

證明b∈B且b≠0:

若b為原子，有bb,則命題已得證。若b不是原子，則必有b1∈B，0＜b1＜b。若b1不是原子，存在b2使0b2b1b,對b2重復(fù)上面的討論。因為B有限，這一過程必將中止，上述過程中產(chǎn)生的元素序列滿足0…b2b1b

即存在br,br為原子，且0brb,否則此序列無限長。引理1得證。第88頁，共113頁，2023年，2月20日，星期五

引理2設(shè)〈B，∨，∧，′，0，1〉是一有限布爾代數(shù)，b為B中任一非零元素，設(shè)A(b)={a1，a2，…,am}，則b=a1∨a2∨…∨am=a,且表達(dá)式唯一。證明令c=a1∨a2∨…∨am。要證b=c。由于aib（i=1,2,…,m），因為c是A(b)中最小上界，所以cb。欲證bc。據(jù)定理7.2.11，只要證b∧c′=0。第89頁，共113頁，2023年，2月20日，星期五

用反證法，設(shè)b∧c′≠0,從而存在原子a使得

0ab∧c′，所以有ab，ac′。由于ab,a是原子，因此a為a1，a2，…,am之一，故ac。所以ac∧c′=0,與a是原子矛盾。因此b∧c′=0，即bc。b=c=a1∨a2∨…∨am得證。第90頁，共113頁，2023年，2月20日，星期五

下證唯一性。設(shè)b也可表示為b=a,S={b1,b2,…,bj},b1,b2,…,bj是原子。需證S=A(b)。若q∈S，有qb,所以q∈A(b),因此SA(b)。若q∈A(b)，有qb,q=q∧b=q∧a∈S

a=a∈S(q∧a)。由定理7.3.3知，存在a0∈S,使q=a0，所以q∈S。故S=A(b)，引理2得證。第91頁，共113頁，2023年，2月20日，星期五

定理7.3.4若a是原子，則ab∨c的充分必要條件是ab或ac。

證明先證必要性。若a是原子，且ab∨c,不妨設(shè)x≤b，因為a是原子，由定理7.3.3有a∧b=0。

因為ab∨c,所以有a=a∧(b∨c)=(a∧b)∨(a∧c)=(a∧c),故ac,得證。充分性顯然。第92頁，共113頁，2023年，2月20日，星期五

定理7.3.5設(shè)〈B，∨，∧，′，0，1〉為有限布爾代數(shù)，令A(yù)={a|a∈B且a是原子}，則B同構(gòu)于布爾代數(shù)〈P(A)，∪,∩,∽,,A〉。證明構(gòu)造映射f：B→P(A)，使得對任意b∈B,f(b)=A(b)。

(1)證明f為一單射。若f(b)=f(c),有A(b)=A(c)。由引理2得b=a∈A(b),

c=a∈A(c)a,所以b=c,故f是單射。第93頁，共113頁，2023年，2月20日，星期五

（2）證明f是滿射。S∈P(A),則SA。令b=a∈S

a,由引理2得b=a∈A(b)a。由唯一性有S=A(b)=f(b)。若

S==A(b)=f(b),所以f為滿射得證。第94頁，共113頁，2023年，2月20日，星期五(3)接著要證明f保持運算，即f滿足式（7.3.4）、式（7.3.5）和式（7.3.6）。設(shè)b，c為B中任意兩個元素且b≠0，c≠0。對任意的原子x,x∈A(b∧c)xb∧cxb且xcx∈A(b)且x∈A(c)x∈A(b)∩A(c)所以A(b∧c)=A(b)∩A(c),即f(b∧c)=f(b)∩f(c)。第95頁，共113頁，2023年，2月20日，星期五

對任意的原子x,

x∈A(b∨c)xb∨cxb或xcx∈A(b)

或x∈A(c)x∈A(b)∪A(c)

所以A(b∨c)=A(b)∪A(c),即f(b∨c)=f(b)∪f(c)。b∈B,且b≠0,對任意的原子x,x∈A(b′)x∧b=0x∧b≠xx≤bxA(b)x∈∽A(b)所以A(b′）=∽A(b),即f(b′)=∽(f(b))，定理得證。第96頁，共113頁，2023年，2月20日，星期五

本定理有如下推論：推論1若有限布爾代數(shù)有n個原子，則它有2n個元素。推論2任何具有2n個元素的布爾代數(shù)互相同構(gòu)。注意這一定理對無限布爾代數(shù)不能成立。根據(jù)這一定理，有限布爾代數(shù)的基數(shù)都是2的冪。同時在同構(gòu)的意義上對于任何2n，n為自然數(shù)，僅存在一個2n元的布爾代數(shù)，如圖7.3.2中的Hasse圖所示的1元、2元、4元、8元的布爾代數(shù)。第97頁，共113頁，2023年，2月20日，星期五

圖7.3.2第98頁，共113頁，2023年，2月20日，星期五7.4例題選解【例7.4.1】設(shè)〈L，≤〉是格，a,b,c∈L，a≤b，證明：(a∨b∧c))∨c=(b∧(a∨c))∨c

證明因為a≤b，且a≤a∨c，所以a≤b∧(a∨c)，故a∨c≤（b∧(a∨c)）∨c。由格的吸收律、結(jié)合律知（a∨b∧c)）∨c=a∨c，所以（a∨(b∧c)）∨c≤（b∧(a∨c)）∨c第99頁，共113頁，2023年，2月20日，星期五

又由格的分配不等式知