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

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

課堂練習(xí)5.第6-3講作業(yè)11、布爾代數(shù)(1)定理1若a,b是布爾代數(shù)中任意兩個元素，則(a’)’=a；(ab)’=a’b’；(ab)’=a’b’定義1布爾格<A,>誘導(dǎo)的代數(shù)系統(tǒng)<A,,,’>叫布爾代數(shù)。證：(1)按定義，a與a’互補，所以a’的補元是a，即(a’)’=a。(2)可直接驗證ab的補元是(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)證21、布爾代數(shù)(2)定義3具有有限個元素的布爾代數(shù)叫有限布爾代數(shù)。定義2設(shè)<A,,,’>和<B,,,’>是兩個布爾代數(shù)，如果存在雙射f:AB，對任意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é)論：對任一正整數(shù)n，必存在含有2n個元素的布爾代數(shù)。任一有限布爾代數(shù)的元素的個數(shù)必為2n，n為正整數(shù)。元素個數(shù)相同的布爾代數(shù)都是同構(gòu)的。32、原子

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

顯然，如果a,b皆為原子，ab，則ab=0。為了證明上述關(guān)于有限布爾代數(shù)的結(jié)論，先引入原子的概念。42、原子

(2)定理2設(shè)有限格<A,>具有全下界0，若b0，則至少存在一個原子a，使得ab。

證：如果b本身為原子，因bb，命題得證。如果b不是原子，按蓋住的定義，必存在b1A，使0<b1<b，若b1為原子，命題得證。否則，必存在b1A，使0<b2<b1<b，因為A是有限集合，經(jīng)過上述有限的步驟之后，必可找到一個原子bi，使0<bi...<b2<b1<b證畢。53、Stone表示定理

(1)引理1在布爾格中，bc’=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。63、Stone表示定理

(2)引理2設(shè)<A,,,’>是有限布爾代數(shù)，若bA，且b0，又設(shè)a1,a2,…,ak是A中滿足ajb(j=1,2,…,k)的所有原子，則b=a1a2…ak，并且這種表示是唯一的。證：令c=a1a2…ak

因ajb（0jk），所以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。73、Stone表示定理

(3)引理2設(shè)<A,,,’>是有限布爾代數(shù)，若bA且b0，又設(shè)a1,a2,…,ak是A中滿足ajb(j=1,2,…,k)的所有原子，則b=a1a2…ak，并且這種表示是唯一的。證(續(xù))：下面證明表示的唯一性。設(shè)b有另一表達式：b=aj1aj2…ajt，其中ajr(0rt)是原子。于是有

ajrb(0rt)因為已設(shè)a1,a2,…,ak是A中所有滿足ai

b的不同原子，所以tk。問題轉(zhuǎn)化為證明t=k。假設(shè)t<k，則至少存在一個aj0{a1,a2,…,ak}，使得aj0ajx(0xt)。因aj0(aj1aj2…ajt)=aj0(a1a2…aj0…ak)即(aj0aj1)(aj0aj2)...(aj0ajt)=(aj0a1)(aj0a2)...(aj0aj0)...(aj0ak)亦即00...0=00...aj00...0那么得aj0=0，與aj0是原子相矛盾，故必有t=k。83、Stone表示定理

(4)引理3設(shè)<A,>是布爾格，a為原子，b0，則ab和ab’二式有且僅有一個成立。證：因aba，若a為原子，b也是原子，則ab=0。即a(b’)’=0，根據(jù)引理1，ab’。

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

93、Stone表示定理

(5)定理3(Stone表示定理)設(shè)<A,,,’>是有限布爾格<A,>所誘導(dǎo)的有限布爾代數(shù)，S是<A,>中所有原子的集合，則<A,,,’>和<(S),,,~>同構(gòu)。證明線索：(1)作映射f:A(S)，當(dāng)a=0時，f(a)=；當(dāng)a0時，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)103、Stone表示定理

(6)定理3的推論：推論1有限布爾格的元素的個數(shù)必等于2n，其中n是布爾格中所有原子的個數(shù)。（這是因為|A|=|(S)|=2|S|）推論2元素的個數(shù)相同的有限布爾代數(shù)是同構(gòu)的。（這是因為任何有限布爾代數(shù)都與它的原子集合構(gòu)成的冪集代數(shù)<(S),,,~>同構(gòu)。）

問題：四個元素的鏈?zhǔn)遣紶柎鷶?shù)嗎？答：不是布爾代數(shù)。因為鏈的中間兩個元素沒有補元，鏈僅僅是分配格，不是有補格。114、課堂練習(xí)練習(xí)1設(shè)<S,,,’>是布爾