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

《离散数学第11讲 布尔代数ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第11讲 布尔代数ppt课件.ppt（22页珍藏版）》请在三一办公上搜索。

1、1,离散数学（二）,布尔代数,主要内容:,重点和难点:,一、布尔代数两个定义,布尔代数的定义：定义1 布尔代数：有界有补的分配格.定义1 是代数系统,*和是B上的二元运算，如果对任意的元素a,b,cB，满足下列4条，则称为布尔代数:(1)交换律 a*b=b*a 和 ab=ba(2)分配律 a*(bc)=(a*b)(a*c)和 a(b*c)=(ab)*(ac)(3)全上(下)界 B中存在两个元素0和1,对B中任意元素a,满足 a*1=a 和 a0=a(4)补元存在性 对B中每一元素a都存在一元素a,满足a*a=0 和 aa=1,一、布尔代数两个定义,定义1定义1,显然。下面证明定义1定义1:,(

2、1)交换律:运算*和是可交换的(2)吸收律:要证明 a*(ab)=a 和 a(a*b)=a a*(ab)=(a0)*(ab)=a(0*b)=a0=a 同理可证 a(a*b)=a,一、布尔代数两个定义,(3)结合律:要证明(ab)c=a(bc)(i)首先证明a*c=b*c,a*c=b*c,则a=b.a=a*1=a*(cc)=(a*c)(a*c)=(b*c)(b*c)=b*(cc)=b(ii)现证明(ab)c*a=a(bc)*a,(ab)c*a=a(bc)*a.(ab)c*a=(ab)*a(c*a)=a(c*a)=a.a(bc)*a=a,所以(ab)c*a=a(bc)*a.(ab)c*a=(ab)

3、*a(c*a)=(a*a)(b*a)(c*a)=0(b*a)(c*a)=(b*a)(c*a),a(bc)*a=(a*a)(b*a)(c*a)=(b*a)(c*a).所以,(ab)c*a=a(bc)*a.,一、布尔代数两个定义,例1(1)(2)(3)(4)S=a1,an,|(S)|=2n,为布尔代数.(5)X=A|A是由变元p1,p2,pn,构成的合式公 式集。等价公式视为同一公式，最小项有2n个,X共2(2n)个命题公式,为布尔代数.,结论:(1)每一正整数nN,一定存在2n个元素的布尔代数。S=a1,an,|(S)|=2n,;(2)反之,对于任一有限布尔代数L,总存在自然数nN,使得|L|=

4、2n(它的元素个数必为2的幂次)。,二、布尔同态,定义2 具有有限个元素的布尔代数称为有限布尔代数.,定义3 设和是两个布尔代数。定义一个映射f:AB,如果在f的作用下能够保持布尔代数的所有运算,且常数相对应,亦即对于任何a,bA有:f(a*b)=f(a)f(b)f(ab)=f(a)f(b)f(a)=f(a)f(0)=f(1)=则称映射f:AB是一个布尔同态。,三、有限布尔代数的结构,定义4()是格，有全下界0,aL,满足(1)a0;(2)不bL使得0ba;则称a为该布尔代数的一个原子。,定义5 设 是一个格，且具有全下界0，如果有元素a盖住0，则称元素a为原子。原子：与0相邻且比0“大”,盖

5、住关系:设a,b是一个格中的两个元素,如果ba且ba,即ba,并且在此格中再没有别的元素c,使得bc和ca,则称元素a覆盖元素b。,例子(参见右图)d,e均是原子。实际上，在布尔代数中，原子是B-0的极小元，因为原子与0之间不存在其他元素。,三、有限布尔代数的结构,布尔代数的原子有以下性质:定理1:设是布尔代数,aB是原子的充分必要条件是a0且对B中任何元素x有xa=a 或 xa=0 定理2:设a,b为布尔代数中任意两个原子且ab,则ab=0。,三、有限布尔代数的结构,定理1的证明:先证必要性.设a是原子,显然a0.另设xaa,由于xa a,故xa a.据原子的定义和0 xa,可得xa0.再证

6、充分性.设a0,且对任意xB,有xa=a或xa=0成立.若a不是原子,那么必有 bB,使0 b a.于是,bab.因为b0,ba,故bab与式(I)矛盾.因此,a只能是原子.,定理1:设是布尔代数,aB是原子的充分必要条件是a0且对B中任何元素x有xa=a 或 xa=0(I),三、有限布尔代数的结构,定理2的证明:(反证法)假如ab0,令ab=c,若a,b是原子且ab0,则 0c a 0c b c a 时与a为原子相矛盾.c=a时,结合0 c b 得0 a b,与b为原子相矛盾.所以ab=0.,定理2:设a,b为布尔代数中任意两个原子且ab,则ab=0。,三、有限布尔代数的结构,引理1:设是一

7、有限布尔代数,则对于B中任一非零元素b,恒有一原子aB,使ab。,证明:任取bB且b0.若b为原子,有bb,则命题已得证。若b不是原子,则必有b1B,使得0 b1 b。若b1不是原子,存在b2使0b2b1b,对b2重复上面的讨论。因为B有限,这一过程必将中止,上述过程产生的元素序列满足 0 b2 b1 b即存在br,br为原子,且0 br b,否则此序列无限长。,三、有限布尔代数的结构,引理2:设是有限布尔代数,则(1)任意b,cB,有bc=0当且仅当b c；(2)对于B中任一原子a和任一非零元素b,ab 和ab两式中有且仅有一式成立。,(1)证明:必要性 若bc=0,证明b c.(bc)(c

8、c)=(bc)c=0c=c(bc)(cc)=(bc)1=bc 所以bc=c,故b c.充分性 若b c,证明bc=0.c c,且b c,有bc cc=0,所以bc=0.,三、有限布尔代数的结构,引理2:设是有限布尔代数,则(1)任意b,cB,有bc=0当且仅当b c；(2)对于B中任一原子a和任一非零元素b,ab 和ab两式中有且仅有一式成立。,(2)证明:先证a b 和a b两式不可能同时成立.假如a b 和a b同时成立,就有a bb=0,这与a是原子相矛盾。再证a b 和a b两式中必有一式成立.因为ab a,a是原子,所以只能是ab=0或ab=a.若ab=0,则 a(b)=0,由(1)

9、得a b;若ab=a,得ab.命题得证.,三、有限布尔代数的结构,引理2说明:原子是这样的元素,它把B中的元素分为两类,第一类是与自己可比较的(包括自身),它小于等于这一类中的任一元素。第二类是与自己不可比较的或是0,它小于等于这一类中任一元素的补元。为了加深对原子和定理7.42的认识,试考察图7.43,(a)中,a1是原子;(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子.在(a),(b)(c)三图中,虚线都是表示原子a1将B的元素划分成两类。,三、有限布尔代数的结构,引理3:设是一个有限布尔代数,若x是A中任意非零元素,a1,a2,ak是A中满足aj x的所有原子(j=1,2,

10、k),则x=a1a2ak,证明:(1)先证 a1a2ak x.记a1a2ak=c,因为aj x,所以c x。(2)再证 x a1a2ak=c.由引理2(1)知,要证x c只需证xc=0,反设xc 0,于是必有一个原子a,使得a xc。又因xc x,和 xcc,所以 a x 和 a c.因为a是原子,且a x,所以a必是a1,a2,ak中的一 个,因此 ac,已有ac,得a cc,即a 0,与a是原子矛盾。xc 0假设不成立。综合(1)和(2)引理得证。,三、有限布尔代数的结构,引理4:设是一个有限布尔代数,若x是A中任意非零元素,a1,a2,ak是A中满足ajx的所有原子(j=1,2,k),则

11、x=a1a2ak是将x表示为原子之并的唯一形式。,证明:设有另一种表示形式为x=b1b2bt,其中b1,b2,bt是原子。因为x是b1,b2,bt的最小上界,所以必有b1 x,b2 x,.,bt x。而a1,a2,ak是A中满足ai x(i=1,2,k)的所有原子.所以,必有tk且b1,b2,bta1,a2,ak.如果tk,那么在a1,a2,ak中必有一ai与b1,b2,bt全不相同.于是由ai(b1b2bt)=ai(a1a2ak)可得ai=0.这是因为 ai(b1b2bt)=0,ai(a1a2ak)=ai.与ai是原子矛盾,tk假设不成立.所以t=k,定理得证。,三、有限布尔代数的结构,定理

12、3:(Stone 表示定理)设 是由有限布尔格所诱导的一个有限布尔代数,S是布尔格中的所有原子的集合,则和同构。,证明:本定理的证明过程分两部分(1)构造一个映射,并证明它是双射(既是单射又是满射)；(2)描述代数系统 证明和同构.,推论1 有限布尔格的元素个数必定等于2n，其中n是该布尔格中所有原子的个数。推论2 任何一个具有2n个元素的有限布尔代数都是同构的。,三、有限布尔代数的结构,第(1)部分证明：构造函数f:A(S),aA,当a=0时,f(0)=;当a=1时,f(1)=S.当a0时,f(a)=ai|ai Sai a.令S1=ai|ai Sai a f满射:一S1(S)，令S1=a1,

13、a2,ak，则由于运算的封闭性，所以a1a2ak=aA这就说明对S1(S)，必存在aA，使得f(a)=S1。f单射:证明 a,bA,当ab时有f(a)f(b).等价于证明若f(a)=f(b),则a=b.令f(a)=f(b)=a1,a2,ak(S),由f(a)=a1,a2,ak知 a=a1a2ak 由f(b)=a1,a2,ak知 b=a1a2ak所以a=b.,三、有限布尔代数的结构,第(2)部分证明：证明和同构，即需要证明a,bA,有f(ab)=f(a)f(b)。首先证明f(ab)f(a)f(b).a0,b0时,令a=a1a2ak,b=b1b2bk xf(ab),则x必是满足xab的原子 xaxbx是原子 x f(a)x f(b)xf(a)f(b)所以f(ab)f(a)f(b).其次证明f(a)f(b)f(ab).反之,若xf(a)f(b)xf(a)xf(b)xa xb x是原子 x ab x是原子 x f(ab),这就证明了f(a)f(b)f(ab)。所以,f(ab)=f(a)f(b),同理可证:f(ab)=f(a)f(b),f(a)=f(a).,作业：P252 习题7.4 1(3)(4)、11、12,22,谢谢同学们!,