離散數(shù)學(xué)第六章第三節(jié)

1第6-3講布爾代數(shù)1.布爾代數(shù)2.原子3.Stone表示定理4.

課堂練習(xí)5.第6-3講作業(yè)21、布爾代數(shù)(1)定理1若a,b是布爾代數(shù)中任意兩個(gè)元素，則

(a’)’=a；

(ab)’=a’b’；(ab)’=a’b’定義1布爾格<A,

>誘導(dǎo)的代數(shù)系統(tǒng)<A,,,’>叫布爾代數(shù)。證：(1)按定義，a與a’互補(bǔ)，所以a’的補(bǔ)元是a，即

(a’)’=a。(2)可直接驗(yàn)證a

b的補(bǔ)元是(a’

b’):(ab)(a’b’)=(aba’)(abb’)(分配律)=(1b)(a1)=11=1(ab)(a’b’)=(aa’b’)(ba’b’)=(0b’)(a’0)=00=0(3)可仿照(2)證31、布爾代數(shù)(2)定義3具有有限個(gè)元素的布爾代數(shù)叫有限布爾代數(shù)。定義2設(shè)<A,,,’>和<B,,,’>是兩個(gè)布爾代數(shù)，如果存在雙射f:AB，對(duì)任意a,bA,有

f(ab)=f(a)f(b)

f(ab)=f(a)f(b)f(a’)=f’(a)則稱<A,,,’>和<B,,,’>同構(gòu)。關(guān)于有限布爾代數(shù)有如下重要結(jié)論：對(duì)任一正整數(shù)n，必存在含有2n個(gè)元素的布爾代數(shù)。任一有限布爾代數(shù)的元素的個(gè)數(shù)必為2n，n為正整數(shù)。元素個(gè)數(shù)相同的布爾代數(shù)都是同構(gòu)的。42、原子

(1)定義4設(shè)格<A,

>具有全下界0，如果元素a(0)A蓋住0，則稱a是原子。例如，右圖所示格中，元素d,e是原子。

顯然，如果a,b皆為原子，a

b，則ab=0。

為了證明上述關(guān)于有限布爾代數(shù)的結(jié)論，先引入原子的概念。52、原子

(2)定理2設(shè)有限格<A,

>具有全下界0，若b0，則至少存在一個(gè)原子a，使得a

b。

證：如果b本身為原子，因b

b，命題得證。如果b不是原子，按蓋住的定義，必存在b1A，使0<b1<b，若b1為原子，命題得證。否則，必存在b1A，使

0<b2<b1<b，因?yàn)锳是有限集合，經(jīng)過(guò)上述有限的步驟之后，必可找到一個(gè)原子bi，使

0<bi...<b2<b1<b證畢。63、Stone表示定理

(1)引理1在布爾格中，b

c’=0當(dāng)且僅當(dāng)bc。證：如果bc’=0，則

(bc’)c=0c=c(1)另一方面，

(bc’)c=(bc)(c’c)=(bc)1=bc(2)由(1)、(2)式得

bc=c再根據(jù)格的性質(zhì)8可知bc。

反之，如果bc，則bc’cc’（格的保序性），即bc’0，因0是全下界，要上式成立，只能是bc’=0。73、Stone表示定理

(2)引理2設(shè)<A,,,’>是有限布爾代數(shù)，若bA，且b0，又設(shè)a1,a2,…,ak是A中滿足aj

b(j=1,2,…,k)的所有原子，則b=a1a2

…ak，并且這種表示是唯一的。證：令c=a1a2

…ak

因aj

b（0

j

k），所以cb。下面證明bc。根據(jù)引理1，只須證bc’=0。用反證法，假設(shè)bc’0，根據(jù)定理2，存在原子a，使abc’。根據(jù)格的性質(zhì)8，bc’b，bc’

c’。

再由傳遞性得：

ab，ac’。因a是原子，且ab，所以a{a1,a2,…,ak}，故ac。由ac’和ac可得ac’c，從而a0，與a是原子矛盾。最后由cb和bc得:b=c=a1a2

…ak。83、Stone表示定理

(3)引理2設(shè)<A,,,’>是有限布爾代數(shù)，若bA且b0，又設(shè)a1,a2,…,ak是A中滿足aj

b(j=1,2,…,k)的所有原子，則b=a1a2

…ak，并且這種表示是唯一的。證(續(xù))：下面證明表示的唯一性。設(shè)b有另一表達(dá)式：b=aj1aj2

…ajt，其中ajr(0

r

t)是原子。于是有

ajrb(0

r

t)

因?yàn)橐言O(shè)a1,a2,…,ak是A中所有滿足ai

b的不同原子，所以tk。問(wèn)題轉(zhuǎn)化為證明t=k。假設(shè)t<k

，則至少存在一個(gè)aj0{a1,a2,…,ak}，使得aj0ajx(0

x

t)。因

aj0

(aj1aj2

…ajt)=aj0

(a1a2

…

aj0

…ak)即(aj0aj1)

(aj0aj2)...(aj0ajt)=(aj0a1)

(aj0a2)...(aj0aj0)...(aj0ak)亦即00...0=00...aj00...0那么得aj0=0，與aj0是原子相矛盾，故必有t=k。93、Stone表示定理

(4)引理3設(shè)<A,

>是布爾格，a為原子，b0，則a

b和a

b’

二式有且僅有一個(gè)成立。證：因ab

a，若a為原子，b也是原子，則ab=0。即a(b’)’=0，根據(jù)引理1，ab’。

如b不是原子，則ab=a，根據(jù)格的性質(zhì)8，ab。下面證明二式僅有一個(gè)成立。假設(shè)ab和ab’同時(shí)成立，則abb’，即a=0，與a是原子矛盾。

103、Stone表示定理

(5)定理3(Stone表示定理)設(shè)<A,,,’>是有限布爾格<A,

>所誘導(dǎo)的有限布爾代數(shù)，S是<A,

>中所有原子的集合，則<A,,,’>和<(S),,,~>同構(gòu)。證明線索：

(1)作映射f:A(S)，當(dāng)a=0時(shí)，f(a)=；當(dāng)a0時(shí)，f(a)=Si，Si表示所有滿足xa的原子x的集合。然后證明f是雙射。

(2)證明f是同構(gòu)映射：

f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(a’)=f’(a)113、Stone表示定理

(6)定理3的推論：推論1有限布爾格的元素的個(gè)數(shù)必等于2n，其中n是布爾格中所有原子的個(gè)數(shù)。（這是因?yàn)閨A|=|(S)|=2|S|）推論2元素的個(gè)數(shù)相同的有限布爾代數(shù)是同構(gòu)的。（這是因?yàn)槿魏斡邢薏紶柎鷶?shù)都與它的原子集合構(gòu)成的冪集代數(shù)<(S),,,~>同構(gòu)。）

問(wèn)題：四個(gè)元素的鏈?zhǔn)遣紶柎鷶?shù)嗎？答：不是布爾代數(shù)。因?yàn)殒湹闹虚g兩個(gè)元素沒(méi)有補(bǔ)元，鏈僅僅是分配格，不是有補(bǔ)格。124、課堂練習(xí)練習(xí)1設(shè)<S,,,’>是布爾代數(shù)，x,yS。證明，xy當(dāng)且僅當(dāng)y’x’解:由引理1

，y’x’當(dāng)且僅當(dāng)y’(x’)’=0,即y’x=0。再由引理1，xy’=0當(dāng)且僅當(dāng)xy。故在任何布爾代數(shù)中，xy當(dāng)且僅當(dāng)y’x’。提示：應(yīng)用教材P255引理6-4.1進(jìn)行證明13第6-3