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

1离散数学（二）布尔代数布尔代数两个定义11布尔同态2主要内容:布尔代数的定义重点:重点和难点:有限布尔代数的结构3有限布尔代数的结构难点:一、布尔代数两个定义布尔代数的定义：定义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)=aa*(a⊕b)=(a⊕0)*(a⊕b)=a⊕(0*b)=a⊕0=a同理可证a⊕(a*b)=a一、布尔代数两个定义(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'.一、布尔代数两个定义例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的幂次)。二、布尔同态定义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是一个布尔同态。三、有限布尔代数的结构定义4L,≤(L,∧,∨)是格，有全下界0,a∈L,满足(1)a≠0;(2)不∃b∈L使得0ba;则称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之间不存在其他元素。三、有限布尔代数的结构布尔代数的原子有以下性质:定理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∧aa.据原子的定义和0≤x∧a,可得x∧a＝0.再证充分性.设a≠0,且对任意x∈B,有x∧a=a或x∧a=0成立.若a不是原子,那么必有b∈B,使0ba.于是,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)三、有限布尔代数的结构定理2的证明:(反证法)假如a∧b≠0,令a∧b=c,若a,b是原子且a∧b≠0,则0c≤a0c≤bca时与a为原子相矛盾.c=a时,结合0c≤b得0ab,与b为原子相矛盾.所以a∧b=0.定理2:设a,b为布尔代数B,∨,∧,′,0,1中任意两个原子且a≠b,则a∧b=0。三、有限布尔代数的结构引理1:设B,∨,∧,′,0,1是一有限布尔代数,则对于B中任一非零元素b,恒有一原子a∈B,使a≤b。证明:任取b∈B且b≠0.若b为原子,有b≤b,则命题已得证。若b不是原子,则必有b1∈B,使得0b1b。若b1不是原子,存在b2使0b2b1b,对b2重复上面的讨论。因为B有限,这一过程必将中止,上述过程产生的元素序列满足0…b2b1b即存在br,br为原子,且0brb,否则此序列无限长。三、有限布尔代数的结构引理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,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,它小于等于这一类中任一元素的补元。为了加深对原子和定理7.4―2的认识,试考察图7.4―3,(a)中,a1是原子;(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子.在(a),(b)(c)三图中,虚线都是表示原子a1将B的元素划分成两类。三、有限布尔代数的结构引理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)引理得证。三、有限布尔代数的结构引理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}.如果tk,那么在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是原子矛盾,tk假设不成立.所以t=k,定理得证。三、有限布尔代数的结构定理3:(Stone表示定理)设A,∨,∧,′,0,1是由有限布尔格A,≤所诱导的一个有限布尔代数,S是布尔格中的所有原子的集合,则A,∨,∧,′,0,1和(S),∪,∩,¯,Ø,S同构。证明:本定理的证明过程分两部分(1)构造一个映射,并证明它是双射(既是单射又是满射)；(2)描述代数系统证明A,∨,∧,′，0，1和(S),∪,∩,¯,Ø,S同构.推论1有限布尔格的元素个数必定等于2n，其中n是该布尔格中所有原子的个数。推论2任何一个具有2n个元素的有限布尔代数都是同构的。三、有限布尔代数的结构第(1)部分证明：构造函数f:A→(S),∀aA,当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=aA这就说明对∀S1∈(S)，必存在aA，使得f(a)=S1。f单射:证明∀a,bA,当a≠b时有f(a)≠f(b).等价于证明若f(a)=f(b),则a=b.令f(a)=f(b)={a1,a2,…,ak}(S),由f(a)={a1,a2,…,ak}知a=a1∨a2∨…∨ak由f(b)={a1,a2,…,ak}知b=a1∨a2∨…∨ak所以a=b.三、有限布尔代数的结构第(2)部分证明：证明A,∨,∧,′,0,1和(S),∪,∩,¯,Ø,S同构，即需要证明∀a,bA,有f(a∧b)=f(a)∩f(b)。首先证明f(a∧b)f(a)∩f(b).{a≠0,b≠0时,令a=a1∨a2∨…∨ak,b=b1∨b2∨…∨bk}∀xf(a∧b),则x必是满足x≤a∧b的原子⇒x≤a∧x≤b∧x是原子⇒xf(a)∧xf(b)⇒xf(a)∩f(b)所以f(a∧b)f(a)∩f(b).其次证明f(a)∩f(b)f(a∧b).反之,若xf(a)∩f(b)⇒xf(a)∧xf(b)⇒x≤a∧x≤b∧x是原子⇒x≤a∧b∧x是原子⇒xf(a∧b),这就证明了f(a)∩f(b)f(a∧b)。所以,f(a∧b)=f(a)∩f(b),同理可证:f(a∨b)=f(a)∪f(b),f(a′)=f(a).作业：P252习题7.41(3)(4)、11、1222谢谢同学们!