第六章格與布爾代數(shù)

第六章格和布爾代數(shù)1在第一章我們介紹了命題邏輯。當(dāng)時(shí)被側(cè)重的只是形式系統(tǒng)。如果視P為全體命題的集合，于是邏輯聯(lián)詞∨，∧就可以被看作P上的兩個(gè)二元代數(shù)運(yùn)算。因而，(P,∨,∧)是一個(gè)代數(shù),即通常所說(shuō)的命題代數(shù)。在命題代數(shù)中，運(yùn)算∨,∧滿足冪等律，交換律，結(jié)合律，分配律和吸收律。格與布爾代數(shù)2在第三章我們介紹了集合的最為一般的一些理論，被關(guān)心的只是集合的基本概念，集合的運(yùn)算和基數(shù)等方面的事實(shí)。如果我們令S＝2A，對(duì)于X,YS,則都有X∪Y，X∩YS。在這兩種二元運(yùn)算下，(S,∪,∩)是代數(shù),即所謂冪集代數(shù)。3在冪集代數(shù)中,運(yùn)算∪,∩滿足冪等律,交換律,結(jié)合律,分配律和吸收律.在冪集代數(shù)中引進(jìn)了補(bǔ)集的概念和在命題代數(shù)中引進(jìn)了否定的概念之后,則在這兩種代數(shù)中,都具有了DeMorgan律.4從代數(shù)的觀點(diǎn)出發(fā)，我們是否能對(duì)一種更為抽象的代數(shù)系統(tǒng)進(jìn)行研究,使得冪集代數(shù),命題代數(shù)僅僅是它的特例?回答是肯定的.這種抽象的代數(shù)系統(tǒng)就是格和布爾代數(shù).研究布爾代數(shù)首先要研究格,因?yàn)椴紶柎鷶?shù)是一種特殊的格.5格作為數(shù)學(xué)中一個(gè)很有特色的分支,大體上說(shuō)形成于二十世紀(jì)的三十到四十年代.格作為一種理論,它不只是代數(shù)學(xué)的一個(gè)部分,而且在近代解析幾何,半序空間等方面也都有重要的作用.布爾代數(shù)的問(wèn)世比格要早,在十九世紀(jì)中葉,由英國(guó)數(shù)學(xué)家喬治·布爾研究并提出。6格和布爾代數(shù)在計(jì)算機(jī)科學(xué)中有廣泛的應(yīng)用，象有限自動(dòng)機(jī)理論,開(kāi)關(guān)網(wǎng)絡(luò)理論，邏輯設(shè)計(jì)等領(lǐng)域都直接地應(yīng)用了格和布爾代數(shù)的結(jié)論。7一個(gè)布爾代數(shù)是一個(gè)有補(bǔ)分配格.一個(gè)格是這樣的一個(gè)偏序集,在這個(gè)偏序集中,每?jī)蓚€(gè)元素都有唯一一個(gè)最小上界和唯一一個(gè)最大下界.可見(jiàn),我們首要的任務(wù)是討論偏序和確界的一些有關(guān)的性質(zhì),以作為我們本章要講述內(nèi)容的基礎(chǔ).86-1格的概念定義6-1.1設(shè)<A，>是一個(gè)偏序集，如果A中任意兩個(gè)元素都有最小上界(上確界)和最大下界(下確界)，則稱<A，>為格。1格的定義

9說(shuō)明：由于確界唯一，所以在格<A，>中，對(duì)A中任意元素a,b，求其上確界或下確界的結(jié)果是<A，>中唯一的元素.從代數(shù)的意義上說(shuō)，求上確界和下確界都是格<A，>中的二元運(yùn)算。由定義6-1.1及全序定義,有:任何一個(gè)全序集都是格.

但是任何一個(gè)偏序集并非總是格.這其實(shí)也是明顯的。從邏緝的角度講，格定義在偏序集上，其內(nèi)涵的增加必然導(dǎo)致外延的縮小。

10例：考查下面Hasse圖（哈斯圖）:是偏序集但非格的Hasse圖中,總有元素a,b,使得{a,b}沒(méi)有上確界或下確界。11(a)鏈?zhǔn)歉?(b)偏序,格;(c)偏序,格;(d)偏序,格;(e)偏序,非格;(f)偏序,非格.12例1設(shè)S是任意集合,則<P(S),?>是格。|S|=1時(shí)和|S|=2時(shí),此格的Hasse圖為:13例2設(shè)I+為正整數(shù)集,偏序關(guān)系為整除｜,則<I+,｜>是格,此時(shí)對(duì)a,b∈I+,a、b的上確界是[a,b](最小公倍數(shù))，a、b的下確界是(a,b)(最大公因數(shù))。14例設(shè)n為正整數(shù),Sn是n的全部正因數(shù)的集合,則<Sn,｜>是格.<S24,｜>和<S30,|>的Hasse圖如下:152格誘導(dǎo)的代數(shù)系統(tǒng)

定義6-1.2

設(shè)<A，>是一個(gè)格，如果在A上定義兩個(gè)二元運(yùn)算∨和∧，使得對(duì)于任意的a，b∈A，a∨b等于a和b的最小上界，a∧b等于a和b的最大下界，那么，就稱<A，∨，∧>為由格<A，>所誘導(dǎo)的代數(shù)系統(tǒng)。二元運(yùn)算∨和∧分別稱為并運(yùn)算和交運(yùn)算。

16例3給定S＝{a，b}，P(S)＝{φ，{a}，，{a，b}}，那么，格<P(S)，?>如圖6-1.3所示。

17由格<P(S)，?>所誘導(dǎo)的代數(shù)系統(tǒng)為<P(S)，∨，∧>，其中運(yùn)算∨是集合的并，運(yùn)算∧是集合的交。故∨和∧的運(yùn)算表可分別由表6-1.1的(a)和(b)所示。

183子格

定義6-1.3

設(shè)<A，>是一個(gè)格，由<A，>誘導(dǎo)的代數(shù)系統(tǒng)為<A，∨，∧>，設(shè)B?A且B≠φ，如果A中的這兩個(gè)運(yùn)算∨和∧關(guān)于B是封閉的，則稱<B，>是<A，>的子格。

可以證明子格必成為格。19注意：對(duì)于格<A，>，設(shè)B是A的非空子集，盡管<B，>必定是一個(gè)偏序集，然而<B，>不一定是格，而且即使<B，>是格，也不一定是<A，>的子格。

20例5設(shè)<S,>是一個(gè)格，其中S={a,b,c,d,e,f,g,h}，如圖所示。取S1={a,b,d,f,}S2={c,e,g,h}S3={a,b,c,d,e,g,h}從圖6-1.4上容易看出，<S1，>和<S2，>都是<S，>的子格，而<S3，>雖然是格，但它不是<S，>的子格，這是因?yàn)閎∧d＝fS3

21例題1

設(shè)<S，>是一個(gè)格，任取a∈S，構(gòu)造S的子集T為：T＝{x|x∈S且xa}

則<T，>是<S，>的一個(gè)子格。對(duì)于任意的x，y∈T,必有xa和ya

解：所以

x∨ya，

x∧ya

故

x∨y∈T，

x∧y∈T因此，<T，>是<S，>的一個(gè)子格。

224對(duì)偶

在命題代數(shù)、集合代數(shù)中,我們應(yīng)用了對(duì)偶原理。在比命題代數(shù)和集合代數(shù)更為一般的格與布爾代數(shù)中,我們也將應(yīng)用對(duì)偶原理。對(duì)偶原理是很重要的概念，它出現(xiàn)在許多不同的場(chǎng)合和領(lǐng)域。下面是兩個(gè)生活中的例：人體鏡面成像中,如果人體(或鏡中的像)X能將左手覆于右臂之上,那么X的像(或原像)X*就能將右手覆于左臂之上。

23國(guó)內(nèi)汽車交通規(guī)則,司機(jī)座在駕駛室左側(cè),并規(guī)定汽車前行要沿馬路右側(cè),超車須從左邊道,紅燈禁行時(shí)汽車可以右轉(zhuǎn)彎;英國(guó)汽車,司機(jī)座在駕駛室右側(cè),英國(guó)交通規(guī)則規(guī)定汽車前行要沿馬路左側(cè),超車要從右邊道,紅燈禁行時(shí)汽車可以左轉(zhuǎn)彎.在這里,左和右的概念都作互相交換;交換的結(jié)果形成了各自的交通規(guī)則。

左和右就是一種對(duì)偶概念24格<A,>上偏序關(guān)系作為二元關(guān)系,自然可逆，我們稱這一個(gè)逆關(guān)系為的對(duì)偶關(guān)系,記為。偏序關(guān)系的逆,把<A,

>的Hasse圖作了上下的翻轉(zhuǎn).于是,對(duì)集合A的任意子集B,B在偏序<A,>中的上確界,便成了B在偏序<A,>中的下確界;B在<A,>中的下確界,就是B在<A,>中的上確界.<A,>之所以可稱之為偏序集,是因?yàn)槎P(guān)系的逆關(guān)系，保持原關(guān)系的自反、反對(duì)稱和傳遞性不變,即偏序關(guān)系之逆關(guān)系仍為偏序關(guān)系.從以上分析,我們可以斷言:若<A,>是格,則<A,>也是格,當(dāng)然反之亦真.并稱格<A,>與格<A,>為對(duì)偶的格.

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

265格的基本性質(zhì)

格是偏序集,具有偏序集的性質(zhì).<A,>是格，對(duì)a,b,cA,則:(1)aa;(自反性)(2)若ab且ba則a=b;(反對(duì)稱性)(3)若ab且bc則ac;(傳遞性)27證明：28證明：29格的保序性

30定理6-1.3設(shè)<A，>是一個(gè)格，由格<A，>所誘導(dǎo)的代數(shù)系統(tǒng)為<A，∨，∧>，則對(duì)任意的a，b，c，d∈A，有

(1)a∨b=b∨aa∧b=b∧a（交換律）

(2)a∨(b∨c)=(a∨b)∨ca∧(b∧c)=(a∧b)∧c（結(jié)合律）

(3)a∨a=aa∧a=a(4)a∨(a∧b)=aa∧(a∨b)=a（冪等律）

（吸收律）31證明：(1)格中任何兩個(gè)元素a，b的最小上界（最大下界）當(dāng)然等于b，a的最小上界（最大下界），故a∨b=b∨a（a∧b=b∧a）32其它結(jié)論利用對(duì)偶原理可證33例6設(shè)<N，≤>是一個(gè)偏序集合，這里N是自然數(shù)集，≤是普通的數(shù)與數(shù)之間的“小于等于”關(guān)系．因?yàn)閷?duì)于任意的a，b∈N，有a∨b＝max(a，b)，a∧b＝min(a，b)，所以，<N，≤>是一個(gè)格，由這個(gè)格所誘導(dǎo)的代數(shù)系統(tǒng)是<N，∨，∧>。

分析：在此代數(shù)系統(tǒng)中，任意兩個(gè)數(shù)a和b的最大值(最小值)與b和a的最大值(最小值)是相等的，因此，并運(yùn)算和交運(yùn)算都是可交換的；又因?yàn)閙ax(max(a，b)，c)和max(a，max(b，c))都是三個(gè)數(shù)a，b，c中的最大值，所以在<N，∨，∧>中并運(yùn)算是可結(jié)合的，同理min(min(a，b)，c)＝min(a，min(b，c))，說(shuō)明交運(yùn)算的可結(jié)合性；由于max(a，a)＝min(a，a)＝a，所以冪等性成立；又由于max(a，max(a，b))＝a和min(a，max(a，b))＝a，因此，吸收性也成立。346從代數(shù)系統(tǒng)到格引理6-1.1

設(shè)<A,∨,∧>是一個(gè)代數(shù)系統(tǒng)，其中∨，∧都是二元運(yùn)算且滿足吸收律，則∨和∧都滿足冪等律。

證明：因?yàn)檫\(yùn)算∨和∧滿足吸收律，即對(duì)任意a，b∈A，有a∨(a∧b)=a(1)a∧(a∨b)=a(2)將(1)式中的b取為a∨b，便得a∨(a∧(a∨b))=a再由(2)，即得a∨a=a同理可證a∧a=a35證明：363738證明a∨b是a和b的最小上界。

397格的性質(zhì)

證明：40證明：41證明：4243448格同態(tài)

45證明：定理6-1.8說(shuō)明格同態(tài)是保序的

46定理6-1.8的逆命題不一定成立。

例7設(shè)<S，>是一個(gè)格，其中S={a，b，c，d，e}，如圖所示。

我們知道，<P(S)，?>也是一個(gè)格

作映射f：S→P(S)

4748證明：4950作業(yè)：P243(5)(8)516-2分配格

1分配格的定義

5253圖(a)中：

b∧(c∨d)=b∧a=b而(b∧c)∨(b∧d)=e∨e=e所以b∧(c∨d)≠(b∧c)∨(b∧d)

5455注意：

在分配格的定義中，必須是對(duì)任意的a，b，c∈A都要滿足分配等式，因此，決不能驗(yàn)證格中的某些元素滿足分配等式就斷定該格是分配格。

56例2中給出的兩個(gè)具有五個(gè)元素的格是很重要的，因?yàn)橛幸粋€(gè)定理證明了如下的結(jié)論：一個(gè)格是分配格的充要條件是該格中沒(méi)有任何子格與這兩個(gè)五元素格中的任一個(gè)同構(gòu)。572分配格的性質(zhì)

定理6-2.1

如果在一個(gè)格中交運(yùn)算對(duì)于并運(yùn)算可分配，則并運(yùn)算對(duì)于交運(yùn)算也一定是可分配的。反之亦然。

證明：58定理6-2.2每個(gè)鏈?zhǔn)欠峙涓瘛?/p>

證明：

5960證明：

613模格

62證明：636465證明：66定理6-2.6

分配格必定是模格。

證明：因此

676-3有補(bǔ)格

1有界格

68證明:697071定義6-3.3

如果一個(gè)格中存在全下界和全上界，則稱該格為有界格。

證明：72注意：由a∨0=0∨a=a和a∧1=1∧a=a說(shuō)明0和1分別是關(guān)于運(yùn)算∨和∧的幺元。另外，0和1分別是關(guān)于運(yùn)算∧和∨的零元。

732有補(bǔ)格

定義6-3.4設(shè)<A，>是一個(gè)有界格，對(duì)于A中的一個(gè)元素a，如果存在b∈A，使得a∨b=1和a∧b=0，則稱元素b是元素a的補(bǔ)元。

說(shuō)明：在定義6-3.4中，a和b是對(duì)稱的，即如果a是b的補(bǔ)元，則b也是a的補(bǔ)元，因此，a和b這兩個(gè)元素是互補(bǔ)的。對(duì)于元素a∈A，可以存在多個(gè)補(bǔ)元，也可以不存在補(bǔ)元。在有界格中，0是1的唯一補(bǔ)元，1是0的唯一補(bǔ)元。74例3在如圖所示的有界格中，因?yàn)閐∨c=1和d∧c=0，所以，d和c是互補(bǔ)的。但是b是沒(méi)有補(bǔ)元的。此外，a和d都是e的補(bǔ)元；c和e都是d的補(bǔ)元。

75定義6-3.5

在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元素，則稱此格為有補(bǔ)格。例4圖6-3.3中給出了一些有補(bǔ)格。

76定理6-3.4

在有界分配格中，若一個(gè)元素有補(bǔ)元素，則必是唯一的。

證明：

設(shè)a有兩個(gè)補(bǔ)元素b和c，即有a∨b=1

a∧b=0a∨c=1

a∧c=0由定理6-2.3即得b=c。這就證明了a的補(bǔ)元素是唯一的。773有補(bǔ)分配格

定義6-3.6

一個(gè)格如果它既是補(bǔ)格，又是分配格，則稱它為有補(bǔ)分配格。有補(bǔ)分配格中任一元素a的唯一補(bǔ)元記為。

786-4布爾代數(shù)

1布爾格

定義6-4.1一個(gè)有補(bǔ)分配格稱為布爾格。

注明：792布爾代數(shù)

8081證明：823一些概念

834原子

例2如圖所示的格中，d，e都是原子且d∧e=0，說(shuō)明原子不是唯一的。1蓋住a，b，c；a蓋住d；c蓋住e；b蓋住d，e，這說(shuō)明一個(gè)元素可以蓋住多個(gè)元素。84證明：85說(shuō)明：865布爾代數(shù)的性質(zhì)

證明：87證明：8889證明:9091證明：926布爾代數(shù)的同構(gòu)形式

證明：93949596現(xiàn)分別證明如下：

979899100推論6-4.1有限布爾格的元素個(gè)數(shù)必定等于2n，其中n是該布爾格中所有原子的個(gè)數(shù)。

推論6-4.2任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)都是同構(gòu)的。1016-5布爾表達(dá)式

1布爾表達(dá)式及其值

定義6-5.1設(shè)<A，∨，∧，－>是一個(gè)布爾代數(shù)，在這個(gè)布爾代數(shù)上定義布爾表達(dá)式如下：1.A中任何元素是一個(gè)布爾表達(dá)式。2.任何變?cè)且粋€(gè)布爾表達(dá)式。3.如果e1和e2是布爾表達(dá)式，那么，

，(e1∨e2)和(e1∧e2)也都是布爾表達(dá)式。4.只有通過(guò)有限次運(yùn)用規(guī)則2和3所構(gòu)造的符號(hào)串是布爾表達(dá)式。102例2設(shè)<{0，1，2，3}，∨，∧，－>是一個(gè)布爾代數(shù)。

布爾表達(dá)式：

含有單個(gè)變?cè)獂1的布爾表達(dá)式

含有兩個(gè)變?cè)獂1，x2的布爾表達(dá)式含有三個(gè)變?cè)獂1，x2，x3的布爾表達(dá)式103定義6-5.2

一個(gè)含有n個(gè)相異變?cè)牟紶柋磉_(dá)式，稱為含有n元的布爾表達(dá)式。記為E(x1，x2，…，xn)，其中x1，x2，…，xn為變?cè)?/p>

定義6-5.3

布爾代數(shù)<A，∨，∧，－>上的一個(gè)含有n元的布爾表達(dá)式E(x1，x2，…，xn)的值是指：將A中的元素作為變?cè)獂i(i＝1，2，…，n)的值來(lái)代替表達(dá)式中相應(yīng)的變?cè)?即對(duì)變?cè)x值)，從而計(jì)算出表達(dá)式的值。

1041052布爾表達(dá)式的等價(jià)

106如：107說(shuō)明：由于布爾代數(shù)是有補(bǔ)分配格，當(dāng)對(duì)布爾表達(dá)式賦值后，表達(dá)式中運(yùn)算∨對(duì)于運(yùn)算∧是可分配的，運(yùn)算∧對(duì)于運(yùn)算∨也是可分配的。因此，如果將布爾表達(dá)式中的變?cè)醋魇且呀?jīng)賦值的，那么，上例中的E1和E2的等價(jià)性可以直接寫(xiě)為

108對(duì)于布爾代數(shù)<A，∨，∧，－>上的任何一個(gè)布爾表達(dá)式，E(x1，x2，…，xn)。由于運(yùn)算∨，∧，－在A上的封閉性，所以對(duì)于任何一個(gè)有序n元組<x1，x2，…，xn>，xi∈A，可以對(duì)應(yīng)著一個(gè)表達(dá)式E(x1，x2，…，xn)的值，這個(gè)值必屬于A。由此可見(jiàn)，可以說(shuō)布爾表達(dá)式E1(x1，x2，…，xn)確定了一個(gè)由An到A的函數(shù)。109例：110不是任意一個(gè)從An到A的函數(shù)都一定能列出一個(gè)在<A，∨，∧，－>上的布爾表達(dá)式。1113布爾函數(shù)及合取范式、析取范式

定義6-5.5設(shè)<A，∨，∧，－>是一個(gè)布爾代數(shù)，一個(gè)從An到A的函數(shù)，如果它能夠用<A，∨，∧，－>上的n元布爾表達(dá)式來(lái)表示，那么，這個(gè)函數(shù)就稱為布爾函數(shù)。

定理6-5.1對(duì)于兩個(gè)元素的布爾代數(shù)<{0,1}，∨，∧，－>，任何一個(gè)從{0,1}n到{0，1}的函數(shù)都是布爾函數(shù)。

112證明：

一個(gè)在<{0，1}，∧，∨，－>上的布爾表達(dá)式，如果它能表示成小項(xiàng)的并，則稱這個(gè)布爾表達(dá)式為析取范式。

113114例5討論表6-5.3所給的函數(shù)f的析取范式和合取范式。

115116117118正因?yàn)槿魏我粋€(gè)從{0，1}n到{0，1}的函數(shù)，它的函數(shù)值只可能是1或0，因此，總可以用上述方法得到該函數(shù)所對(duì)應(yīng)的析取范式、合取范式。

1194析取范式、合取范式的進(jìn)一步討論

120定理6-5.2設(shè)E(x1，x2，…，xn)是布爾代數(shù)<A，∨，∧，－>上的任意一個(gè)布爾表達(dá)式，則它一定能寫(xiě)成析取范式。

證明：

令E(xi＝a)＝E(x1，x2，…，xi-1，a，xi+1，…，xn