离散数学-第11讲-布尔代数课件

1离散数学（二）1离散数学（二）布尔代数布尔代数两个定义11布尔同态2主要内容:布尔代数的定义重点:

重点和难点:有限布尔代数的结构3有限布尔代数的结构难点:

布尔代数布尔代数两个定义11布尔同态2主要内容:布尔代数的定一、布尔代数两个定义布尔代数的定义：定义1布尔代数：有界有补的分配格<L,∧,∨,',0,1>.定义1′<B,*,⊕>是代数系统,*和⊕是B上的二元运算，如果对任意的元素a,b,c∈B，满足下列4条，则称<B,*,⊕>为布尔代数:(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一、布尔代数两个定义布尔代数的定义：一、布尔代数两个定义定义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一、布尔代数两个定义定义1→定义1′,显然。下面证明定义1一、布尔代数两个定义(3)结合律:要证明(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)现证明[(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'.一、布尔代数两个定义(3)结合律:要证明(a⊕b)⊕c=一、布尔代数两个定义例1(1)

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

(2)

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

(3)

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

(4)

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

<ρ(S),∩,∪>为布尔代数.

(5)

X={A|A是由变元p1,p2,…,pn,﹁,∧,∨,→,构成的合式公式集}。等价公式视为同一公式，最小项有2n个,

X共2^(2n)个命题公式,<X,∧,∨,┒,F,T>为布尔代数.结论:(1)每一正整数n∈N,一定存在2n个元素的布尔代数。

S={a1,…,an},

|ρ(S)|=2n,

<ρ(S),∩,∪,

¯,

Ø,

S>;(2)反之,对于任一有限布尔代数L,总存在自然数n∈N,使得|L|=2n(它的元素个数必为2的幂次)。一、布尔代数两个定义例1(1)<B1,∧,∨,',0二、布尔同态定义2具有有限个元素的布尔代数称为有限布尔代数.定义3设<A,*,⊕,′,0,1>和<B,∩,∪,-,α,β>是两个布尔代数。定义一个映射f:A→B,如果在f的作用下能够保持布尔代数的所有运算,且常数相对应,亦即对于任何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是一个布尔同态。二、布尔同态定义2具有有限个元素的布尔代数称为有限布尔代三、有限布尔代数的结构定义4<L,≤>(<L,∧,∨>)是格，有全下界0,a∈L,满足

(1)a≠0;(2)不∃b∈L使得0<b<a;则称a为该布尔代数的一个原子。定义5设<L,≤>是一个格，且具有全下界0，如果有元素a盖住0，则称元素a为原子。原子：与0相邻且比0“大”

盖住关系:设a,b是一个格中的两个元素,如果b≤a且b≠a,即b＜a,并且在此格中再没有别的元素c,使得b＜c和c＜a,则称元素a覆盖元素b。例子(参见右图)

d,e均是原子。实际上，在布尔代数中，原子是B-{0}的极小元，因为原子与0之间不存在其他元素。三、有限布尔代数的结构定义4<L,≤>(<L,∧,∨>三、有限布尔代数的结构布尔代数的原子有以下性质:定理1:设<B,∧,∨,

′,0,1>是布尔代数,

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

或

x∧a=0定理2:

设a,b为布尔代数<B,∨,∧,′,0,1>中任意两个原子且a≠b,则a∧b=0。三、有限布尔代数的结构布尔代数的原子有以下性质:三、有限布尔代数的结构定理1的证明:

先证必要性.

设a是原子,显然a≠0.另设x∧a≠a,由于x∧a≤a,故x∧a<a.据原子的定义和0≤x∧a,可得x∧a＝0.

再证充分性.

设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:设<B,∧,∨,

′,0,1>是布尔代数,

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

或

x∧a=0(I)

三、有限布尔代数的结构定理1的证明:定理1:设<B,∧,∨三、有限布尔代数的结构定理2的证明:

(反证法)

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

0<c≤a0<c≤b

c<a时与a为原子相矛盾.

c=a时,结合0<c≤b得0<a<b,与b为原子相矛盾.所以a∧b=0.定理2:

设a,b为布尔代数<B,∨,∧,′,0,1>中任意两个原子且a≠b,则a∧b=0。三、有限布尔代数的结构定理2的证明:(反证法)

假如三、有限布尔代数的结构引理1:

设<B,∨,∧,′,0,1>是一有限布尔代数,则对于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重复上面的讨论。

因为B有限,这一过程必将中止,上述过程产生的元素序列满足

0<…<b2<b1<b

即存在br,br为原子,且0<br<b,否则此序列无限长。三、有限布尔代数的结构引理1:设<B,∨,∧,′,0,三、有限布尔代数的结构引理2:

设<B,∨,∧,

′,

0,1>是有限布尔代数,则(1)任意b,c∈B,有b∧c'=0当且仅当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.

三、有限布尔代数的结构引理2:设<B,∨,∧,′,0三、有限布尔代数的结构引理2:

设<B,∨,∧,

′,

0,1>是有限布尔代数,则(1)任意b,c∈B,有b∧c'=0当且仅当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.命题得证.三、有限布尔代数的结构引理2:设<B,∨,∧,′,0三、有限布尔代数的结构

引理2说明:

原子是这样的元素,它把B中的元素分为两类,第一类是与自己可比较的(包括自身),它小于等于这一类中的任一元素。第二类是与自己不可比较的或是0,它小于等于这一类中任一元素的补元。为了加深对原子和定理7.4―2的认识,试考察图7.4―3,(a)中,a1是原子;

(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子.在(a),(b)(c)三图中,虚线都是表示原子a1将B的元素划分成两类。三、有限布尔代数的结构引理2说明:原子是这样的三、有限布尔代数的结构引理3:

设<A,∨,∧,′,0,1>是一个有限布尔代数,若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,

反设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假设不成立。

综合(1)和(2)引理得证。三、有限布尔代数的结构引理3:设<A,∨,∧,′,0三、有限布尔代数的结构引理4:

设<A,∨,∧,′,0,1>是一个有限布尔代数,若x是A中任意非零元素,a1,a2,…,ak是A中满足aj≤x的所有原子(j=1,2,…,k),则x=a1∨a2∨…∨ak是将x表示为原子之并的唯一形式。证明:

设有另一种表示形式为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假设不成立.所以t=k,

定理得证。

三、有限布尔代数的结构引理4:设<A,∨,∧,′,0,三、有限布尔代数的结构定理3:(Stone表示定理)

设<A,∨,∧,′,

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

>所诱导的一个有限布尔代数,

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

0,1

>和<(S),∪,∩,¯,Ø,

S>同构。证明:本定理的证明过程分两部分(1)构造一个映射,并证明它是双射(既是单射又是满射)；(2)描述代数系统证明<A,∨,∧,′，0，1>和<(S),∪,∩,¯,

Ø,

S>同构.推论1

有限布尔格的元素个数必定等于2n，其中n是该布尔格中所有原子的个数。推论2

任何一个具有2n个元素的有限布尔代数都是同构的。三、有限布尔代数的结构定理3:(Stone表示定理)三、有限布尔代数的结构第(1)部分证明：构造函数f:

A→(S),∀aA,当a=0时,

f(0)=Ø;当a=1时,f(1)=S.当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,当a≠b时有f(a)≠f(b).

等价于证明若f(a)=f(b),则a=b.

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