《离散数学第11讲布尔代数ppt课件》由会员分享，可在线阅读，更多相关《离散数学第11讲布尔代数ppt课件（22页珍藏版）》请在金锄头文库上搜索。
1、1离散数学（二）离散数学（二）布尔代数布尔代数布尔代数两个定义布尔代数两个定义1 11 1布尔同态布尔同态2 2主要内容主要内容: :布尔代数的定义布尔代数的定义重点重点: : 重点和难点重点和难点: :有限布尔代数的结构有限布尔代数的结构3 3有限布尔代数的结构有限布尔代数的结构难点难点: : 一、布尔代数两个定义一、布尔代数两个定义布尔代数的定义：布尔代数的定义：定义定义1 布尔代数：有界有补的分配格.定定义义1 是代数系统, *和是B上的二元运算，如果对任意的元素a,b,cB，满足下列4条，则称为布尔代数布尔代数: (1) 交换律交换律 a*b=b*a 和 ab=ba (2) 分配律分配
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:(1) 交换律交换律:运算*和是可交换的(2) 吸收律吸收律 :要证明 a*(ab)=a 和 a(a*b)=a a *(ab)=(a0)*(ab)=a(0*b)=a0=a 同理可证 a(a*b)=a一、布尔代数两个定义一、布尔代数
3、两个定义(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)*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
4、). 所以, (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|=2n (它的元素个数必为2的幂次)。二、布尔同态二、布尔同态定义定义2 具有有限个元素的布
5、尔代数称为具有有限个元素的布尔代数称为有限布尔代数有限布尔代数.定义定义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为原子。原
6、子：与原子：与0相邻且比相邻且比0“大大” 盖住关系盖住关系:设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。三、有限布
7、尔代数的结构三、有限布尔代数的结构定理定理1的证明的证明: 先证必要性先证必要性. 设a是原子,显然a0. 另设xaa, 由于xa a, 故xa a. 据原子的定义和0 xa,可得xa0. 再证充分性再证充分性. 设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的证明的证明: (反证法反证法)
8、 假如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: 设是一有限布尔代数, 则对于B中任一非零元素b, 恒有一原子aB, 使ab。证明证明: 任取bB且b0. 若b为原子, 有bb, 则命题已得证。 若b不是原子, 则必有b1B, 使得0 b1 b。 若b1不是原子,存在b2使0b2b1b,对b2重复上面的讨论。 因为B有限,这一过程必将
9、中止,上述过程产生的元素序列满足 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)(cc)=(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. 三、有限布尔代数的结
10、构三、有限布尔代数的结构引理引理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)得a b; 若ab=a, 得ab. 命题得证.三、有限布尔代数的结构三、有限布尔代数
11、的结构 引引理理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,k),则x
12、 = 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中
13、任意非零元素, a1, a2, ,ak是A中满足ajx的所有原子(j=1,2,k),则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. 这是因为 a
14、i(b1b2bt)=0, ai(a1a2ak)=ai. 与与ai是是原子原子矛盾矛盾, t k假设不成立假设不成立. 所以所以t=k, 定理得证定理得证。 三、有限布尔代数的结构三、有限布尔代数的结构定理定理3: (Stone 表示定理表示定理) 设 是由有限布尔格所诱导的一个有限布尔代数, S是布尔格中的所有原子的集合, 则和同构。证明证明:本定理的证明过程分两部分本定理的证明过程分两部分(1)构造一个映射构造一个映射, 并证明它是双射并证明它是双射(既是单射又是满射既是单射又是满射)；(2)描述代数系统描述代数系统 证明证明和和同构同构.推论推论1 有限布尔格的元素个数必定等于有限布尔格的
15、元素个数必定等于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,a2 , ak，则由于运算的封闭性，所以a1a2ak = aA这就说明对S1(S)，必存在aA，使得f(a)=S1。
16、 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 、 1222谢谢同学们谢谢同学们! !
