《【管理精品】计算机数学基础》由会员分享，可在线阅读，更多相关《【管理精品】计算机数学基础（7页珍藏版）》请在金锄头文库上搜索。
1、四、布尔代数1、定义和典型例子：定义16：一个有余分配格称为布尔代数,如果一个布尔代数中的元素是有限的,则称之为有限布尔代数。 在布尔代数中运算*简记为,称为乘法,运算。记为十,称为加法。布尔代数是有界格,存在最小元记为0,存在最大元记为1,由于是有余格,每个元素均存在余元,由于是有余分配格,每个无法素均存在且有唯一的余元,因而求余元可以看作是一个运算,记作把a的补元记为a,今后用（B,+, ,0,1)来表示一个布尔代数,对于乘法ab简称为ab。格有界格有余格布尔代数分配格结合律 吸收律交换律 幂等律同一律零一律互补律分配律德摩根律双重否定律例13,设A是一非空集合,P(A)是A的幂集,可以验
2、证,(P(A),A)是个布尔代数,称此为集合代数,其中加法,乘法,补运算,最小元,最大元A,S是命题公式的全体,则(S,0,1)是一个布尔代数,称之为命题代数。其中加法是,乘法是,补运是,最小元是恒假公式0,最大元是恒真公式。例14：设Bn是由分量仅为0,1的所有n元向量集合,（共有2n个元素), a,bBn,其中a=(a1,an),b=(b1,bn),bi,ai=0或1定义Bn上的运算,ab=(a1b1,a2b2,anbn)a+b=(a1+b1,a2+b2, an+bn)a=(a1,a2,an)其中分量运算均为布尔运算最小元0=（0,0,0),最大元（1,1,1)则（Bn,+, ,0,1)为
3、布尔代数,称为开关代数。例如：a=(1,0,1,1,0),b=(1,0,1,0,1)ab=(1,0,1,0,0),a+b=(1,0,1,1,1)a=(0,1,0,0,1)2、布尔代数中的运算律定理9:设（B,+,0,1)是布尔代数,则成立如下运算律,(1)交换律 a+b=b+a,ab= ba(2)结合律 (a+b)+c=a+(b+c), (ab)c= a( bc)(3)幂等律 a+a=a,aa=a(4)吸收律 a+( ab)=a,a（a+b)=a(5)分配律 a+(bc)=(a+b)(a+c),a(b+c)=ab+ac(6)同一律 a+0=a,a1=a(7)零一律 a+1=1,a0=0(8)互
4、补律 a+a=1,aa=0(9)双重否定律=a(10)德摩律=ab,=a+b说明：（1)实数集对于实数的加法和乘法,其不是布尔代数,在布尔代数中的运算不能用实数的运算来理解它,而用集合代数来理解它。例如：布尔代数中a,bB,如ab,则以下正确的是ab=0ab=0a+b=1a+b=1那么,用集合代数中,已知AB则AB=成立ABAB=不成立AB=E不成立AB=E成立 所以结论中,成立用布尔代数来证明,因ab,ab=a,a+b=bab=(ab)b=a0=0成立a+b=a+(a+b)=(a+a)+b=1+b=1成立.说明(2),布尔代数中10个律不是互相独立的,其中某些律可以由其它一些来推出,因而要证
5、明是布尔代数不必要验证10个律,而只须验证某些律就可以了。例,结合律和吸收律可以推幂等律 a+a=a+(a*(a+b)=a定理10：设B是至少含有两个元素的集合,+是定义在B上的两种运算,如果a,b,cB,满足如下：H1:ab=ba,a+b=b+a(交换律)H2:a(b+c)=ab+ac, a+bc=(a+b)(a+c) (分配律)H3:B中有元素0和1,对aB,a1=a,a+0=a (同一律)H4:aB,有aB,使a+a=1,aa=0(互补律)则（B,+,-,0,1)是布尔代数。说明：即只要交换律,分配律,同一律和互补律,可以推出其它6个律。例15：设S110=1,2,5,10,11,22,
6、55,110是110的所有因数的集合,令ged,lcm是最大公约数和最小公倍数运算。下面简记为ged乘,lcm+加则(S110,+,)是一个布尔代数。证明:110=2511质因子分解式中因子是不重复的。而24=2223,质因子分解中,因子是重复的。(S110,D)的哈斯图与(S30,D),(P(A),),A=a,b,c是完全相同的,记(x)为x的质因数分解的质因数的集合,例(55)=5,11容易验证,交换律显然成立。x,y,zS110,x(y+z)=(x)(y)(z)=(x)(y)(x)(z)=xy+xz分配律成立。显然1是S110的最小元,110是S110的最大元。x1=1,x+110=11
7、0,同一律成立,记x=110/x,因110中质因数分解中质因数不重复。故x与x的质因数没有重复的。xx=1,x+x=(x)x=110故在补律是成立,(S110,+, ,1,110)是布尔代数。3、子布尔代数定义17：设(B,+,-,0,1)是一个布尔代数,H是B的一个子集,如H对+,运算封闭,则称H是B的子布尔代数。例：对任一个布尔代数B,H=0,1对运算是封闭的,所以H是B的子布尔代数。S30=1,2,3,5,6,10,15,30,(S30,lcm,ged,1,30)是布尔代数,H=1,2,15,30,运算具有封闭是子布尔代数,而集合G=1,2,3,30运算不具有封闭性,2+3=6GG不是子
8、布尔代数。4、关于布尔代数的同态和同构定义18：设(B,+,-,0,1)和(B, , ,0,1)是两个布尔代表,f是从B到B的映射,且满足f(a+b)=f(a) f(b),f(ab)=f(a)f(b),f(a)=(简称运算的象等于象的运算),则称f是B到B的一个同态映射。若f是单射,称f是单同态；如f是满射,称f是满同态。若f是双射,称f是同构映射,且称B和B是同构的。例如：A=a,b,c,则(P(A), ,A)和(S30,lcm,ged, ,1,30),(S110,lcm,ged,1,110)三个布尔代数是同构的。定理11,设B是布尔代数,H是B的子布尔代数,B是B的同态像,H是H的同态像,
9、则(1)B是一个布尔代数,(2)H是一个布尔代数。说明：布尔代数的同态像是一个布尔代数。5、关于布尔代数的运算题,证明题举例。例16,证明布尔等式,a+(ab)+(b)=a+b证明：a+(ab)+(b)=a+(b)(吸收律)=(a+)(a+b)(分配律) =1(a+b)(互补律)=a+b(同一律)例17,化简布尔表达式,(ab)+(ab)c+b+bc解：(ab)+(ab)c+b+bc=(ab)+b)+(bac+bc)交换律,结合律=b+b(ac+c) 吸收律,分配律=b+b(a+c)(c+c) 分配律=b+b(a+c) 互补律,同一律=(b+b)(b+a+c) 分配律=b+a+c 互补律,同一
10、律例:在布尔代数中,a,bB,则a=b的充要条件是ab+ab=0证明：必要性,a=b,ab+ab=a+a=0+0=0充分性,因ab+b=0,两边乘以aa(ab)+(b)=0a 即aab+ab=0ab=0,两边加上b,左边=ab+b=(a+b)(b+b)=(a+b)1=a+b右边=0+b=ba+b=b,ab同样两边乘以b得,ab=0,两边加上a得a+b=a,ba,a=b例：求证(a+b)(+c)=ac+b求证：左边=a+b+ac+bc(分配律)=b+ac+bc(a+)(互补律)=ac+abc+b+bc分配律=(ac)+(ac)b+(b)+(b)c=ac+b(吸收律)例：ab的充要条件是a+bc=(a+c)b证明：ab,a+b=b左边=a+bc=(a+b)(a+c)=b(a+c) =右边a+bc=(a+c)b 两边乘以b左边=(a+bc)b=ab+bbc=ab+0=ab右边=(a+c)bb=(a+c)0=0ab=0 两边加上b左边=ab+b=(a+b)(b+b)=(a+b)1=a+b右边=0+b=ba+b=b ab作业P275 练习8.1(A)1,4,5 练习8.1(B)1,2,3,4,5,6,7P285 练习8.2(A)3,4,5 练习8.2(B)1,2,3,4,5,6,7,8P290 习题8:6,7,8
