離散數(shù)學(xué)-第11講-布爾代數(shù)課件

1離散數(shù)學(xué)（二）1離散數(shù)學(xué)（二）布爾代數(shù)布爾代數(shù)兩個定義11布爾同態(tài)2主要內(nèi)容:布爾代數(shù)的定義重點:

重點和難點:有限布爾代數(shù)的結(jié)構(gòu)3有限布爾代數(shù)的結(jié)構(gòu)難點:

布爾代數(shù)布爾代數(shù)兩個定義11布爾同態(tài)2主要內(nèi)容:布爾代數(shù)的定一、布爾代數(shù)兩個定義布爾代數(shù)的定義：定義1布爾代數(shù)：有界有補的分配格<L,∧,∨,',0,1>.定義1′<B,*,⊕>是代數(shù)系統(tǒng),*和⊕是B上的二元運算，如果對任意的元素a,b,c∈B，滿足下列4條，則稱<B,*,⊕>為布爾代數(shù):(1)交換律

a*b=b*a和a⊕b=b⊕a(2)分配律

a*(b⊕c)=(a*b)⊕(a*c)和

a⊕(b*c)=(a⊕b)*(a⊕c)(3)全上(下)界B中存在兩個元素0和1,對B中任意元素a,滿足a*1=a和a⊕0=a(4)補元存在性對B中每一元素a都存在一元素a′,滿足a*a′=0和a⊕a′=1一、布爾代數(shù)兩個定義布爾代數(shù)的定義：一、布爾代數(shù)兩個定義定義1→定義1′,顯然。下面證明定義1←定義1′:(1)

交換律:運算*和⊕是可交換的(2)

吸收律:要證明a*(a⊕b)=a和a⊕(a*b)=a

a*(a⊕b)=(a⊕0)*(a⊕b)=a⊕(0*b)=a⊕0=a

同理可證a⊕(a*b)=a一、布爾代數(shù)兩個定義定義1→定義1′,顯然。下面證明定義1一、布爾代數(shù)兩個定義(3)結(jié)合律:要證明(a⊕b)⊕c=a⊕(b⊕c)

(i)首先證明a*c=b*c,a*c'=b*c',則a=b.a=a*1=a*(c⊕c')=(a*c)⊕(a*c')=(b*c)⊕(b*c')=b*(c⊕c')=b(ii)現(xiàn)證明[(a⊕b)⊕c]*a=[a⊕(b⊕c)]*a,[(a⊕b)⊕c]*a'=[a⊕(b⊕c)]*a'.[(a⊕b)⊕c]*a=[(a⊕b)*a]⊕(c*a)=a⊕(c*a)=a.[a⊕(b⊕c)]*a=a,所以[(a⊕b)⊕c]*a=[a⊕(b⊕c)]*a.

[(a⊕b)⊕c]*a'=[(a⊕b)*a']⊕(c*a')=(a*a')⊕(b*a')⊕(c*a')=0⊕(b*a')⊕(c*a')=(b*a')⊕(c*a'),[a⊕(b⊕c)]*a'=(a*a')⊕(b*a')⊕(c*a')=(b*a')⊕(c*a').

所以,[(a⊕b)⊕c]*a'=[a⊕(b⊕c)]*a'.一、布爾代數(shù)兩個定義(3)結(jié)合律:要證明(a⊕b)⊕c=一、布爾代數(shù)兩個定義例1(1)

<B1,∧,∨,',0,1>

(2)

<B2,∧,∨,',0,1>

(3)

<B4,∧,∨,',0,1>

(4)

S={a1,…,an},|ρ(S)|=2n,

<ρ(S),∩,∪>為布爾代數(shù).

(5)

X={A|A是由變元p1,p2,…,pn,﹁,∧,∨,→,構(gòu)成的合式公式集}。等價公式視為同一公式，最小項有2n個,

X共2^(2n)個命題公式,<X,∧,∨,┒,F,T>為布爾代數(shù).結(jié)論:(1)每一正整數(shù)n∈N,一定存在2n個元素的布爾代數(shù)。

S={a1,…,an},

|ρ(S)|=2n,

<ρ(S),∩,∪,

ˉ,

?,

S>;(2)反之,對于任一有限布爾代數(shù)L,總存在自然數(shù)n∈N,使得|L|=2n(它的元素個數(shù)必為2的冪次)。一、布爾代數(shù)兩個定義例1(1)<B1,∧,∨,',0二、布爾同態(tài)定義2具有有限個元素的布爾代數(shù)稱為有限布爾代數(shù).定義3設(shè)<A,*,⊕,′,0,1>和<B,∩,∪,-,α,β>是兩個布爾代數(shù)。定義一個映射f:A→B,如果在f的作用下能夠保持布爾代數(shù)的所有運算,且常數(shù)相對應(yīng),亦即對于任何a,b∈A有:

f(a*b)=f(a)∩f(b)f(a⊕b)=f(a)∪f(b)f(a′)=f(a)f(0)=αf(1)=β則稱映射f:A→B是一個布爾同態(tài)。二、布爾同態(tài)定義2具有有限個元素的布爾代數(shù)稱為有限布爾代三、有限布爾代數(shù)的結(jié)構(gòu)定義4<L,≤>(<L,∧,∨>)是格，有全下界0,a∈L,滿足

(1)a≠0;(2)不?b∈L使得0<b<a;則稱a為該布爾代數(shù)的一個原子。定義5設(shè)<L,≤>是一個格，且具有全下界0，如果有元素a蓋住0，則稱元素a為原子。原子：與0相鄰且比0“大”

蓋住關(guān)系:設(shè)a,b是一個格中的兩個元素,如果b≤a且b≠a,即b＜a,并且在此格中再沒有別的元素c,使得b＜c和c＜a,則稱元素a覆蓋元素b。例子(參見右圖)

d,e均是原子。實際上，在布爾代數(shù)中，原子是B-{0}的極小元，因為原子與0之間不存在其他元素。三、有限布爾代數(shù)的結(jié)構(gòu)定義4<L,≤>(<L,∧,∨>三、有限布爾代數(shù)的結(jié)構(gòu)布爾代數(shù)的原子有以下性質(zhì):定理1:設(shè)<B,∧,∨,

′,0,1>是布爾代數(shù),

a∈B是原子的充分必要條件是a≠0且對B中任何元素x有x∧a=a

或

x∧a=0定理2:

設(shè)a,b為布爾代數(shù)<B,∨,∧,′,0,1>中任意兩個原子且a≠b,則a∧b=0。三、有限布爾代數(shù)的結(jié)構(gòu)布爾代數(shù)的原子有以下性質(zhì):三、有限布爾代數(shù)的結(jié)構(gòu)定理1的證明:

先證必要性.

設(shè)a是原子,顯然a≠0.另設(shè)x∧a≠a,由于x∧a≤a,故x∧a<a.據(jù)原子的定義和0≤x∧a,可得x∧a＝0.

再證充分性.

設(shè)a≠0,且對任意x∈B,有x∧a=a或x∧a=0成立.若a不是原子,那么必有b∈B,使0<

b<

a.于是,b∧a＝b.因為b≠0,b≠a,故b∧a＝b與式(I)矛盾.因此,a只能是原子.定理1:設(shè)<B,∧,∨,

′,0,1>是布爾代數(shù),

a∈B是原子的充分必要條件是a≠0且對B中任何元素x有x∧a=a

或

x∧a=0(I)

三、有限布爾代數(shù)的結(jié)構(gòu)定理1的證明:定理1:設(shè)<B,∧,∨三、有限布爾代數(shù)的結(jié)構(gòu)定理2的證明:

(反證法)

假如a∧b≠0,令a∧b=c,若a,b是原子且a∧b≠0,則

0<c≤a0<c≤b

c<a時與a為原子相矛盾.

c=a時,結(jié)合0<c≤b得0<a<b,與b為原子相矛盾.所以a∧b=0.定理2:

設(shè)a,b為布爾代數(shù)<B,∨,∧,′,0,1>中任意兩個原子且a≠b,則a∧b=0。三、有限布爾代數(shù)的結(jié)構(gòu)定理2的證明:(反證法)

假如三、有限布爾代數(shù)的結(jié)構(gòu)引理1:

設(shè)<B,∨,∧,′,0,1>是一有限布爾代數(shù),則對于B中任一非零元素b,

恒有一原子a∈B,使a≤b。證明:

任取b∈B且b≠0.若b為原子,有b≤b,則命題已得證。

若b不是原子,則必有b1∈B,使得0<b1<b。

若b1不是原子,存在b2使0<b2<b1<b,對b2重復(fù)上面的討論。

因為B有限,這一過程必將中止,上述過程產(chǎn)生的元素序列滿足

0<…<b2<b1<b

即存在br,br為原子,且0<br<b,否則此序列無限長。三、有限布爾代數(shù)的結(jié)構(gòu)引理1:設(shè)<B,∨,∧,′,0,三、有限布爾代數(shù)的結(jié)構(gòu)引理2:

設(shè)<B,∨,∧,

′,

0,1>是有限布爾代數(shù),則(1)任意b,c∈B,有b∧c'=0當(dāng)且僅當(dāng)b≤c；(2)對于B中任一原子a和任一非零元素b,

a≤b和a≤b'兩式中有且僅有一式成立。(1)證明:

必要性?若b∧c'=0,證明b

≤

c.

(b∨c)∧(c'∨c)=(b∧c')∨c=0∨c=c(b∨c)∧(c'∨c)=(b∨c)∧1=b∨c所以b∨c=c,故b≤c.充分性?

若b≤c,證明b∧c'=0.c'≤c',且b≤c,有b∧c'≤c∧c'=0,所以b∧c'=0.

三、有限布爾代數(shù)的結(jié)構(gòu)引理2:設(shè)<B,∨,∧,′,0三、有限布爾代數(shù)的結(jié)構(gòu)引理2:

設(shè)<B,∨,∧,

′,

0,1>是有限布爾代數(shù),則(1)任意b,c∈B,有b∧c'=0當(dāng)且僅當(dāng)b≤c；(2)對于B中任一原子a和任一非零元素b,

a≤b和a≤b'兩式中有且僅有一式成立。(2)證明:

先證a≤

b和a≤

b'兩式不可能同時成立.假如a≤

b和a≤

b'同時成立,就有a≤

b∧b'=0,這與a是原子相矛盾。

再證a≤

b和a≤

b'兩式中必有一式成立.因為a∧b≤

a,a是原子,所以只能是a∧b=0或a∧b=a.若a∧b=0,則a∧(b')'=0,由(1)得a≤

b';若a∧b=a,得a≤b.命題得證.三、有限布爾代數(shù)的結(jié)構(gòu)引理2:設(shè)<B,∨,∧,′,0三、有限布爾代數(shù)的結(jié)構(gòu)

引理2說明:

原子是這樣的元素,它把B中的元素分為兩類,第一類是與自己可比較的(包括自身),它小于等于這一類中的任一元素。第二類是與自己不可比較的或是0,它小于等于這一類中任一元素的補元。為了加深對原子和定理7.4―2的認(rèn)識,試考察圖7.4―3,(a)中,a1是原子;

(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子.在(a),(b)(c)三圖中,虛線都是表示原子a1將B的元素劃分成兩類。三、有限布爾代數(shù)的結(jié)構(gòu)引理2說明:原子是這樣的三、有限布爾代數(shù)的結(jié)構(gòu)引理3:

設(shè)<A,∨,∧,′,0,1>是一個有限布爾代數(shù),若x是A中任意非零元素,a1,a2,…,ak是A中滿足aj≤x的所有原子(j=1,2,…,k),則x=a1∨a2∨…∨ak證明:(1)先證a1∨a2∨…∨ak≤x.

記a1∨a2∨…∨ak=c,因為aj≤

x,所以c

≤

x。(2)再證x≤a1∨a2∨…∨ak=c.

由引理2(1)知,要證x≤c只需證x∧c'=0,

反設(shè)x∧c'≠0,于是必有一個原子a,使得a≤

x∧c'。又因x∧c'≤x

,和x∧c'≤c',所以a≤

x和a≤

c'.

因為a是原子,且a≤

x,所以a必是a1,a2,…,ak中的一個,因此a≤c,已有a≤c',得a≤

c∧c',即a≤0,與a是原子矛盾。x∧c'≠0假設(shè)不成立。

綜合(1)和(2)引理得證。三、有限布爾代數(shù)的結(jié)構(gòu)引理3:設(shè)<A,∨,∧,′,0三、有限布爾代數(shù)的結(jié)構(gòu)引理4:

設(shè)<A,∨,∧,′,0,1>是一個有限布爾代數(shù),若x是A中任意非零元素,a1,a2,…,ak是A中滿足aj≤x的所有原子(j=1,2,…,k),則x=a1∨a2∨…∨ak是將x表示為原子之并的唯一形式。證明:

設(shè)有另一種表示形式為x=b1∨b2∨…∨bt,其中b1,b2,…,bt是原子。因為x是b1,b2,…,bt的最小上界,所以必有b1≤

x,b2≤

x,...,bt≤

x。而a1,a2,…,ak是A中滿足ai≤x

(i=1,2,…,k)的所有原子.所以,必有t≤k且{b1,b2,…,bt}?{a1,a2,…,ak}.

如果tk,那么在a1,a2,…,ak中必有一ai與b1,b2,…,bt全不相同.于是由ai∧(b1∨b2∨…∨bt)=ai∧(a1∨a2∨…∨ak)可得ai=0.這是因為

ai∧(b1∨b2∨…∨bt)=0,

ai∧(a1∨a2∨…∨ak)=ai.

與ai是原子矛盾,

tk假設(shè)不成立.所以t=k,

定理得證。

三、有限布爾代數(shù)的結(jié)構(gòu)引理4:設(shè)<A,∨,∧,′,0,三、有限布爾代數(shù)的結(jié)構(gòu)定理3:(Stone表示定理)

設(shè)<A,∨,∧,′,

0,1>是由有限布爾格<A,≤

>所誘導(dǎo)的一個有限布爾代數(shù),

S是布爾格中的所有原子的集合,則<A,∨,∧,′,

0,1

>和<(S),∪,∩,ˉ,?,

S>同構(gòu)。證明:本定理的證明過程分兩部分(1)構(gòu)造一個映射,并證明它是雙射(既是單射又是滿射)；(2)描述代數(shù)系統(tǒng)證明<A,∨,∧,′，0，1>和<(S),∪,∩,ˉ,

?,

S>同構(gòu).推論1

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

任何一個具有2n個元素的有限布爾代數(shù)都是同構(gòu)的。三、有限布爾代數(shù)的結(jié)構(gòu)定理3:(Stone表示定理)三、有限布爾代數(shù)的結(jié)構(gòu)第(1)部分證明：構(gòu)造函數(shù)f:

A→(S),?aA,當(dāng)a=0時,

f(0)=?;當(dāng)a=1時,f(1)=S.當(dāng)a≠0時,

f(a)={ai|ai

S∧ai≤

a}.令S1={ai|ai

S∧ai≤

a}f滿射:?一S1∈(S)

，令S1={a1,a2,…,ak}，則由于運算∨的封閉性，所以a1∨a2∨…∨ak=aA這就說明對?S1∈(S)，必存在aA，使得f(a)=S1。f單射:證明?a,bA,當(dāng)a≠b時有f(a)≠f(b).

等價于證明若f(a)=f(b),則a=b.

令f(a)=f(b)={a1,a2,…,ak}(S),由f(a)={a1