离散数学第七章格与布尔代数ppt课件.ppt

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

1、第7章 格与布尔代数,7.1 格 7.2 格是代数系统7.3 特殊的格7.4 布尔代数,7.1 格,在第三章曾讨论过偏序集合,定义了有关的术语。并曾证明过:(1)一个偏序集合的子集,如果存在最小上界(lub),则它是唯一的,如果存在最大下界(glb),则它也是唯一的;(2)如果偏序集合拥有最小元素,则它是唯一的,如果偏序集合拥有最大元素,则它也是唯一的。我们就以这些知识为基础介绍格的概念和有关性质。,7.11 格的定义 定义7.11设L,是一个偏序集合,如果L中每一对元素a,b,都有最大下界和最小上界,则称此L,为格。通常用ab表示a,b的最大下界,用ab表示a,b的最小上界。即 a*b=gl

2、ba,b ab=luba,b,例1(a)设D是正整数集合I+中的整除关系,则I+,D是格,因为对任意a,bI+,a*b=glba,b=GCDa,b(a,b的最大公因数)a b=luba,b=LCMa,b(a,b的最小公倍数)(b)设n是一正整数,Sn是n的所有因子的集合。例如S6=1,2,3,6,S8=1,2,4,8,D是整除关系,则Sn,D是格,例如S8,D,S6,D,S30,D的哈斯图如图7.11(a),(b),(c)所示。,(c)设S是任意集合,是它的幂集,偏序集合(S),是格,因为对S的任意子集A,B,AB就是A,B的最小上界,AB就是A,B的最大下界。当集合S仅含有二个或三个元素时,

3、相应的格的哈斯图亦如图7.11(b)和(c)所示。(d)设S是非空集合,(S)是S的所有划分,(S)中的偏序关系可定义为细分,ij当且仅当i中的每一块都在j的某一块中。于是划分积与划分和+分别是保交和保联。所以(S),是格。,例如S=a,b,c,则(S)=1,2,3,4,5 1=a,b,c,2=a,b,c,3=a,c,b,4=a,b,c5=a,b,c(S),的哈斯图如图7.11(d)所示。(e)图7.11(e)所示的哈斯图也是一个格。,图 7.11,图 7.12,7.1.2 格的对偶性原理和基本性质 给定一个偏序集合S,的逆关系也是S中的偏序关系,S,也是偏序集合,我们称偏序集合S,和S,互为

4、对偶。从图形上看,后者的哈斯图就是前者哈斯图的上下颠倒。如果A S,则关系的lub(A)和glb(A)就分别等同于关系的glb(A)和lub(A)。因此,如果L,是一个格,则L,也是一个格,我们说这两个格互为对偶。互为对偶的两个格L,和L,有着密切关系:格L,中的保交正是格L,中的保联,而格L,中的保联正是格L,中的保交。因此,给出关于格一般性质的任何有效命题,把关系换成,(或把换成),把保交换成保联,保联换成保交,我们能够得到另一个有效命题,这就是关于格的对偶性原理。格的基本性质如表7.11所示。如果一个公式的对偶公式是其自身,则对偶式不重复列出。,表7.11 格的基本性质,表7.11 格的

5、基本性质,现证明表中各公式。证 公式(1)(3)是偏序集合定义所要求的,对一切偏序集合均成立,格是偏序集合,所以对一切格也成立。公式(4)(5)是根据保交和保联的定义所得的,所以对一切格成立。(6)交换律的证明。由保联的定义得ab=luba,b=lubb,a=ba。由对偶原理得a*b=b*a。(下边都仅证两对偶恒等式中的一个。),(7)结合律的证明。设R=a(b c)和R=(a b)c,由公式(4)(加撇表示右侧的公式,下同)得Ra,Rb c,根据公式(4)和(3)得Rb和Rc。这样,根据公式(5)得Ra b;由Ra b和Rc得R(a b)c=R。类似地可证Ra(b c)=R。因此,根据公式(

6、2)得(a b)c=a(b c)。结合律说明,无括号表达式a1 a2 an 和a1*a2*an都是单义的。因此,可以论述任何数目的格的元素的保交和保联。,(8)等幂律的证明。由公式(1)有aa,根据公式(5)得aa a。又由公式(4)a aa,因此,根据公式(2)得a a=a。(9)吸收律的证明。由公式(1)有aa,由公式(4)有aa*b,因此,根据公式(5)得aa(a*b),但由公式(4)有a(a*b)a,这样,根据公式(2)得a(a*b)=a。,(10)aba*b=a a b=b的证明。先证aba*b=a,由公式1知aa,由假设ab,所以,由公式5得aa*b,但a*ba。因此,a*b=a。

7、即ab a*b=a。现设a*b=a,由公式(4)知a*bb,所以ab,既a*b=a ab。再证a*b=a a b=b由a*b=a得b(a*b)=a b,即a b=b。反之,若a b=b,则a*(a b)=a*b,即a*b=a。公式(10)建立了格中偏序关系和保交,保联间的一种联系。,(11)adbc a*bd*c和adbc a bd c的证明。因为dd c,cd c,由传递性得ad c,bd c,由公式5得a bd c,因为a*ba,a*bb,由传递性得a*bd,a*bc,由公式(5)得a*bd*c。(12)保序性的证明。公式(11)中d取为a即得。(13)分配不等式的证明。由aa b和aa

8、c得a(a b)*(a c),由ba b和ca c得b*c(a b)*(a c)。,所以,a(b*c)(a b)*(a c)(14)模不等式的证明。若ac,则a c=c,代入公式(13)得 a(b*c)(a b)*c 若a(b*c)(a b)*c,由于aa(b*c),(a b)*cc,根据传递性得ac。,7.2 格是代数系统,7.2.1 格 定义7.21设L,*,是代数系统,*和 是载体L上的二元运算。如果二元运*算 和都是可交换和可结合的,并且满足吸收律和等幂律,则代数系统 L,*,是格。,定义中等幂律可以删除,因为a*a=a*(a(a a)=a,由吸收律可推出等幂律。类似地可证a a=a。

9、这一定义和上节的定义实际上是等价的,下述定理说明这一点。,定理7.21 如果L,*,是一个格,那么,L中存在一偏序关系,在此偏序关系作用下,对所有a,bL有 a b=luba,b(1)a*b=glba,b(2)证首先我们在L上定义一个关系。对任意a,bL ab a*b=a 现在我们证明是偏序关系。因为,(1)对任一元素aL,由等幂律a*a=a,有aa,即是自反的。(2)对某一a,bL,如果ab和ba,那么a*b=a和b*a=b。但a*b=b*a,所以a=b。即是反对称的。(3)对某一a,b,cL。如果ab和bc,那么a*b=a和b*c=b,于是 a*c=(a*b)*c=a*(b*c)=a*b=

10、a 所以,ac,即是传递的。,7.2.2 子格,格同态和格的积代数 定义7.22 L,*,是一个格,S L,如果S对运算和封闭,那么称S,*,是L,*,的子格。子格本身是一个格,因为交换律,结合律,吸收律都是继承的。显然,不是L的任意子集都可构成子格。例如图7.21所示的格中,a,b,d,是子格,b,c,不是子格,因为b,c对运算不封闭。,图 7.21,定义7.23 L,*,和S,是两个格。定义一个映射f:LS,如果对于任何a,bL,有 f(a*b)=f(a)f(b)和 f(a*b)=f(a)f(b)则称f是从L,*,到S,的格同态。,图 7.22,定理7.22 L,*,和S,是两个格,在集合

11、L和S中,对应于保交和保联运算的偏序关系 分别是和,如果f:LS 是格同态,则对任何a,bL,且ab,必有f(a)f(b)。证根据ab a*b=a有 f(a*b)=f(a)f(b)=f(a)所以,f(a)f(b)。证毕,在定义7.23中,若f是双射函数,则称f是格同构。或说L,*,和S,两个格同构。由于同构是相互的,又是保序的,所以对任何a,bL有,abf(a)f(b)和 f(a)f(b)ab 这说明同构的两个格的哈斯图是一样的,只是各结点的标记不同而已。,图 7.23,例1(a)设L1=a,b,c,L2=(a,b,c),如图7.23 所示。f:a,b,c(a,b,c),f(x)=y|yx。因

12、为f(x1*x2)=f(minx1,x2)=y|yminx1,x2=y|yx1y|yx2=f(x1)f(x2)f(x1 x2)=f(maxx1,x2)=y|ymaxx1,x2=y|yx1y|yx2=f(x1)f(x2)所以,f是L1到L2的格同态。,(b)具有一,二,三个元素的格,分别同构于一、二,三个元素的链。四个元素的格必同构于图7.24(a)和(b)之一,五个元素的格必同构于图7.25(a),(b),(c),(d),(e)之一。,图 7.24,图 7.25,定义7.24设L,*,和S,是两个格。定义一个代数系统LS,+如下:对任意a1,b1,a2,b2LS,有 a1,b1。a2,b2=a

13、1*a2,b1b2 a1,b1+a2,b2=a1 a2,b1b2 我们称LS,*,+是格L,*,和S,的直接乘积或积代数。,例2(a)图7.26给出了格1,2,4,D和1,3,D的积代数。这个积代数和格S12,D的图完全一样,只不过前者结点用a,b标记,后者结点用ab标记而已。(b)记L=0,1,考虑格L,自身的积代数。这里是通常意义的“小于或等于”。这些积代数是 L2,2,L3,3Ln,n。一般地说,在格 Ln,n中,任意元素a,b有以下形式:,a=a1,a2,an b=b1,b2,bn 这里的ai,bi是0或1。anb a1b1a2b2anbn 也不难定义出Ln上的运算*和。我们称格Ln,

14、n为0,1n重组的格。图7.27给出了格L,L2,2和 L3,3的哈斯图,一般地说,格Ln,n的图是一个n维立方体。,图 7.26,图 7.27,7.3 特殊的格,7.3.1 分配格 任何格的元素都能满足分配不等式,但某些特殊格,其所有元素都能满足分配律。定义7.31设L,*,是一个格,如果对于任何a,b,cL,有 a*(b c)=(a*b)(a*c)(1)a(b*c)=(a b)*(a c)(2)则称L,*,是一个分配格。,定理7.31 分配格是模格。证 由于a(b*c)=(a b)*(a c),若ac,则a c=c,代入上式得 a(b*c)=(a b)*c 证毕。格可分为模格和非模格,本定

15、理和以下例子说明,模格又可分为分配格和非分配格。,例1(a)如图7.31所示的格不是分配格,因为 a*(b c)=a*1=a a*b a*c=0 0=0 所以,a*(b c)(a*b)(a*c)但可以验证它是模格。注意,格中某些元素满足分配律,但这不能保证是分配格。(b)图7.32所示的格不是分配格,因为它不是模格。图中 ba但b(c*a)(b c)*a,图7.31,图7.32,定理7.32每个链都是分配格。证设L,是一个链,且a,b,cL,考察下述可能情况:(1)ab或ac;(2)ab和ac。对于情况(1)有 a*(b c)=a和(a*b)(a*c)=a 对于情况(2)有 a*(bc)=b

16、c和(a*b)(a*c)=b c 这就证明了元素a,b,c满足分配律(1)。,定理7.33分配格的子格是分配格;两个分配格的积代数是分配格。从子格和积代数的定义易知定理成立。定理7.34设L,*,是一个分配格。对于任何元素a,b,cL有(a*b=a*c)(a b=a c)b=c 证(a*b)c=(a*c)c=c(a*b)c=(a c)*(b c)=(a b)*(b c)=b(a*c)=b(a*b)=b 证毕。,7.3.2 有界格和有补格 设L,*,是一个格,格中每一对元素都有最小上界和最大下界。用归纳法不难证明,格中每一个有穷子集,也都有一个最小上界和一个最大下界。设S=a1,a2,an是有穷

17、子集,一般地说,S的最大下界和最小上界可表示为:,定义7.32如果在格L,中存在一个元素a,对于任何元素b,都有ab(ba),则称a为格L,的全下界(全上界)。定理7.35一个格L,的全下界(全上界)是唯一的。证用反证法。如果有两个全下界a和b,a,bL且ab。因为a是全下界,所以ab。又因为b是全下界,所以ba。因此,a=b,得出矛盾。类似地,可证全上界的唯一性。,例2(a)在格(S),中,S是全上界,是全下界。(b)在图7.33所示的格中,a是全上界,h是全下界。定义7.33如果一个格中存在全下界和全上界,则把它们称为格的界,并分别用0和1来表示。有0和1的格称为有界格。,图 7.33,定

18、理7.36设L,是一个有界格,对任意元素aL,必有:a 0=a a*1=a(3)a 1=1 a*0=0(4)证由于0a1,所以上述各式显然成立。证毕。式(3)说明,对,0是么元;对,1是么元。式(4)说明,对,1是零元;对,0是零元。这两式还说明在有界格中,0和1互为对偶。,定义7.34设L,*,0,1是一有界格。对于L中的一个元素a,如果存在元素bL,使 a*b=0 a b=1 则称元素b是元素a的补元或补,记为a。上述定义中,a和b是对称的,如果b是a的补元,则a也是b的补元。一般地说,一个元素aL,可以不存在补元;如果存在补元则补元也未必是唯一的。,例4观察图7.34中各格的元素的补元。

19、在(a)中a,b,c三个结点都无补元。在(b)中a,b,c都互为补元,补元不唯一。在(c)中,c的补元是a和b;a的补元是c;b的补元是c。,图 7.34,定理7.37在有界格L,*,0,1中,0和1互为补元,且是唯一的。证 因为0*1=0,0 1=1,所以0和1互为补元。若0的补元不唯一,另有补元c,则 0*c=0,0 c=1 但0 c=c,c=1,得出矛盾。类似地可证1的补元也是唯一的。证毕。定理7.38在分配格中,如果元素aL有一个补元,则此补元是唯一的。证 假定b和c都是a的补元,则 a*b=0=a*c a b=1=a c 由定理7.34得b=c。证毕。,定义7.35如果在一个有界格中

20、,每个元素都至少有一个补元素,则称此格为有补格。图7.34的(b)和(c)都是有补格。定义7.36如果一个格,既是有补格,又是分配格,则称此格为有补分配格,又称布尔格。,7.3.3 有补分配格的性质 定理7.39有补分配格L,*,中,任何元素aL的补元a是唯一的。定理7.310 有补分配格L,*,中,对于每一个aL,都有(a)=a 证由于a*a=0,a a=1和(a)*a=0,(a)a=1,而补元是唯一的,所以,(a)=a。证毕。,定理7.311有补分配格L,*,中,对于所有a,bL,有(1)(a b)=a*b(2)(a*b)=a b 此即德摩根定律。证(a b)(ab)=aab b*a*b=

21、0(a b)a*b=(a b a)(a b b)=1 所以,(a b)=a*b。根据对偶性原理得(a*b)=a b。证毕。,定理7.312有补分配格L,*,中,对所有a,bL,有 ab a*b=0a b=1 证 由于 ab a*b=aa b=b 根据德摩根定律得 ab ab=ba b=a 因而 ab a*b=0 a b=1,反之,a*b=0 b(a*b)=b b a=b ab a b=1 a*(a b)=a(a*a)(a*b)=a a*b=a ab 证毕。,7.4 布尔代数,7.4.1 布尔代数 上节已指出,布尔代数就是有补分配格,常记以B,*,0,1,现将其性质综合如下:1.B,*,是一个格

22、,满足(L-1)a*a=a(L-1)a a=a(L-2)a*b=b*a,(L-2)a b=b a(L-3)(a*b)*c=a*(b*c)(L-3)(a b)c=a(b c)(L-4)a*(a b)=a(L-4)a(a*b)=a,2.B,*,是一个分配格,满足(D-1)a*(b c)=(a*b)(a*c)(D-1)a(b*c)=(a b)*(a c)(D-2)(a*b)(b*c)(c*a)=(a b)*(b c)*(c a)(D-3)(a*b=a*c)(a b=a c)b=c,3.B,*,0,1是一个有界格,满足(B-1)0a1(B-2)a*0=0(B-2)a 1=1(B-3)a*1=a(B-3

23、)a 0=a,4.B,*,0,1是一个有补格,满足(C-1)a*a=0(C-1)a a=1(C-2)0=1(C-2)1=05.B,*,0,1是一个有补分配格,满足(C-3)(a*b)=a b(C-3)(a b)=a*b,6.在集合B上存在偏序,满足(P-1)a*b=glba,b(P-1)a b=luba,b(P-2)ab a*b=a a b=b(P-3)ab a*b=0 a b=1 ba 以上公式,不都是独立的,可以从其中选定一些作为基本公式,推出其它公式。也就是说,可以用这些基本公式定义布尔代数。,例1(a)设B=0,1,B上的运算*,由下面的表定义:,代数B,*,0,1能满足定义7.41的

24、要求。所以它是布尔代数,它是二元素布尔代数。二元素布尔代数是图为链的唯一布尔代数。,(b)设S是非空集合。(S)是它的幂集,(S),-,S能满足定义7.41的要求,所以是布尔代数。如果S有n个元素,则(S)有2n个元素,该布尔代数的图形是n维立方体。图7.41给出了S=a,S=a,b,S=a,b,c时布尔代数的图形。若S是空集,则(S)仅有一个元素,于是=0=1,我们称它为退化了的布尔代数,我们不研究它。,图 7.41,(c)用S表示含有n个命题变元的命题公式集合。代数系统S,F,T是一布尔代数,其中,和 分别是合取,析取和否定运算,F和T是永假式和永真式,并把互为等价的两个命题公式看成是相等

25、的。对应于运算和,偏序关系是永真蕴含。,(d)设Bn是0和1组成的n重组集合,记 a=a1,a2,anb=b1,b2,bn 0n=0,0,01n=1,1,1a,b为Bn中的任意元素,定义 a*b=a1b1,a2b2,anbn a b=a1b1,a2b2,anbn a=a1,a2,an,7.4.2 子布尔代数 定义7.42设B,*,0,1是一个布尔代数,SB。如果S含有元素0和1,并且在运算*,和的作用下封闭,则称S,*,0,1是B,*,0,1的子布尔代数。实际检测一个子集S是否是子布尔代数,不需要按定义进行,只须该子集对运算集合*,或,封闭就可以了。因为 a b=(a*b),1=(a*a)和0

26、=a*a,定理 7.41子布尔代数是一个布尔代数。证设S,*,0,1是B,*,0,1的子布尔代数。则0和1属于S;由于S对*,和是封闭的,所以,如果aS,则aS,于是定义7.41中的第3和4条显然在S中成立;又交换律和分配律是继承的,所以S,*,0,1是一个布尔代数。证毕。,例2考察图7.42所示的布尔代数 B,*,0,1。(a)S1=a,a,0,1,由于S1含有0和1,且对运算*、,封闭。所以,S1,*,0,1是B,*,0,1的子布尔代数。这个子布尔代数也可以说由元素a生成的。一般地说,B的任意非空子集都可以生成B,*,0,1的子布尔代数。,图 7.42,(b)S2=c,b,a,1,S2不包

27、含特异元素0,所以不是B,*,0,1的子布尔代数。但若补运算是对1(作为全上界)和c(作为全下界)定义的,则S2,*,c,1是布尔代数。(c)S3=0,b,a,1对运算不封闭,所以S3不能构成布尔代数,当然也不能成为子布尔代数。(d)对任意布尔代数B,*,0,1子集0,1和B总能构成子布尔代数,这两种子布尔代数称为平凡的。,7.4.3 布尔同态 定义7.43设A,*,0,1和B,-,是两个布尔代数。定义一个映射f:AB,如果在f的作用下能够保持布尔代数的所有运算,且常数相对应,亦即对于任何a,bA有:f(a*b)=f(a)f(b)f(a b)=f(a)f(b)f(a)=f(a)f(0)=f(1

28、)=则称映射f:AB是一个布尔同态。,7.4.4 有限布尔代数的原子表示 本小节研究有限布尔代数的一个重要性质,就是任何有限布尔代数B,*,0,1都同构于某一集合S的幂集代数(S),-,S。我们探讨这一问题的思路是这样的:第一步:介绍B中的特殊元素原子及其性质。第二步:证明B中除0外的每一元素x,都可唯一地表示成原子的保联,即x=a1 a2 ak(ai是原子)第三步:证明上述断言。,定义7.44设a,b是一个格中的两个元素,如果ba且ba,即ba,并且在此格中再没有别的元素c,使得bc和ca,则称元素a覆盖元素b。定义7.45设B,*,0,1是一布尔代数,aB,如果a复盖0,则称元素a是该布尔

29、代数的一个原子。定理7.42元素a是布尔代数B,*,0,1的原子,当且仅当a0时,对任意元素xB,有 x*a=a 或 x*a=0 证必要性。因为x*aa,而a是原子,所以,x*a=a或x*a=0。,充分性。若a0不是原子,则存在一元素xB,合ax0,于是有x*a=x,这与假设“a0时对任意xB有x*a=a或x*a=0”相矛盾。所以,a是原子。证毕 推论7.42 a是布尔代数B,*,0,1的原子,x是B的任意元素,则或者ax,或者ax,但不能同时成立。证由于 x*a=a ax,x*a=0 ax 所以,根据定理7.42,如果a是原子,x是B的任意元素,有 ax 或 ax 若两者同时成立,则ax*x

30、=0,这与a0矛盾。,定理7.42及其推论说明:原子是这样的元素,它把B中的元素分为两类,第一类是与自己可比较的(包括自身),它小于等于这一类中的任一元素。第二类是与自己不可比较的或是0,它小于等于这一类中任一元素的补元。为了加深对原子和定理7.42的认识,试考察图7.43,(a)中,a1是原子;(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子。在(a),(b)崐和(c)三图中,虚线都是表示原子a1将B的元素划分成两类。,图 7.43,定理7.43 设B,*,0,1是一个有限布尔代数,则对于每一个非零元素xB,至少存在一个原子a,使x*a=a(即ax)。证若x是原子,则x*x=x,

31、此x就是所求的原子a。若x不是原子,因为x0,所以,从x下降到0有一条路径,又由于B是有限的,此路径所经过的结点是有限的,不妨设为 xa1a2ak0 则ak覆盖0,而x*ak=ak,此ak就是所求的原子a。证毕。,定理7.44 如果元素a1和a2是布尔代数B,*,0,1中的两个原子,且a1*a20,则a1=a2。证由定理7.42有a1*a2=a2和a2*a1=a1,所以a1=a2。本定理的逆反是:若a1a2,则a1*a2=0,它是关于原子的重要性质。下面进行第二步。,定理7.45设B,*,0,1是有限布尔代数,x是B中任意非0元素,a1,a2,ak是满足aix的所有原子(i=1,2,k),则

32、x=a1 a2 ak 证记 a1 a2 ak=y,因为 aix(i=1,2,k)所以,yx。如果能进一步证明xy,那么问题就解决了。由定理7.312知,只需证明x*y=0就可以了。为此,我们用反证法。,设x*y0,于是必有一原子a,使ax*y,又因x*yx和x*yy,所以,由传递性得 ax 和 ay 因为a是一原子,且满足ax,所以a必是a1,a2,ak中的一个,因此ay。但这与ay矛盾。故x*y=0,即xy。证毕。,定理7.46 定理7.45中的表示式 x=a1 a2 ak 是唯一的。证 若另有一种表示式为 x=b1 b2 bt 其中b1,b2,bt是B中不同的原子。,因为x是b1,b2,b

33、t的最小上界,所以,bix(i=1,2,t)。而a1,a2,ak是B中满足aix(i=1,2,k)的所有原子。所以,b1,b2,bt a1,a2,ak且tk。如果tk,那么a1,a2,ak中必有一ai与b1,b2,bt全不相同。于是,由 ai*(b1 b2 bt)=ai*(a1 a2 ak)得 0=ai 于是得到矛盾。所以,只有t=k,b1,b2,bt就是a1,a2,ak。证毕。现在进行第三步。,定理7.47设B,*,0,1是一个有限布尔代数,S是此代数中的所有原子的集合,则B,*,0,1同构于幂集代数(S),-,S。,推论7.47(a)B,*,0,1与(S),-,S同构,|(S)|=2|s|

34、,所以,|B|=2|s|,故任一有限布尔代数载体的基数是2的幂。(b)任一有限布尔代数和它的原子集合S构成的幂集集合代数(S),-,S同构,但后者又与任一基数相同的幂集集合代数同构。故具有相同载体基数的有限布尔代数都同构。注意,定理7.47对无限布尔代数并不成立。,命题演算(集合论)中的极小项就是由n元命题公式构成的布尔代数的原子。除0外,每一公式都可化成极小项的析取(并)是大家已知的事实。此外,还可用布尔代数的反原子的保交来表示布尔代数的元素。反原子是被最大元素1所复盖的元素。事实上,一个反原子是一个原子的补,所以称为反原子。根据对偶性原理,若把和,0和1,和,原子和反原子互换,重复上面的全

35、部讨论,就可得出相应的结论。,图 7.44,7.4.5 布尔代数的积代数 定义7.46设U=A,*,01,11和 V=B,02,12是两个布尔代数。定义一个布尔代数 W=AB,+,-,03,13如下,其中“”“.”“-”都是求补运算。对于任何a1,b1,a2,b2AB,a1,b1a2,b2=a1a2,b1b2 a1,b1+a2,b2=a1 a2,b1b2 a1,b1=a1,b1 则称W是 U和V的积代数。记为W=UV。,定理7.48布尔代数的积代数是一布尔代数。证因为交换律,分配律,公式(B-3)(B-3)(C-1)和(C-1)均成立,符合定义7.41,所以,布尔代数的积代数是一布尔代数。证毕

36、。我们用An=Bn,*,0,1表示具有n个元素的布尔代数。由推 论7.47知,这里的n必定是2的幂。因此,最小的布尔代数是 A2=B2,*,0,1 这里B2=0,1,运算表如例1(a)所定义。其次是 A4=B4,*,0,1 设B4=0,a,b,1,其运算表如下表所示:,表 7.4-1,表 7.42,定理7.49布尔代数 和 同构,且每一有限布尔代数都同构于某一个。证 和 基数相同,所以同构。任一布尔代数的基数为2n,所以必与 同构。证毕。本定理说明,只要对 研究清楚了,一切有限布尔代数也就清楚了。,例4(a)A4与A22同构,对比运算表7.41和运算表7.42即知。(b)设E=a1,a2,an

37、,则布尔代数(E),-,E和An2同构。同构 f 可以这样作出:f:(E)Bn2 f(S)=1,2,n,当 时,当 时,这里,例如,n=4时,f(a1,a3,a4)=1,0,1,1,7.4.6 布尔函数 B,*,0,1是一个布尔代数,现在考虑一个从Bn到B的函数。设B=0,1,表7.43给出了一个从B3到B的函数。设B=0,a,b,1,表7.44给出了一个从B2到B的函数。,表 7.43,表 7.44,定义7.47设B,*,0,1是一个布尔代数,取值于B中元素的变元称为布尔变元;B中的元素称为布尔常元。定义7.48设B,*,0,1是一个布尔代数,这个布尔代数上的布尔表达式定义如下:(1)单个布

38、尔常元是一个布尔表达式;单个布尔变元是一个布尔表达式。,(2)如果e1和e2是布尔表达式,则(e1),(e1 e2),(e1*e2)也是布尔表达式。(3)除了有限次应用条款1和2形成的表达式外,没有其它字符串是布尔表达式。布尔表达式一般用f,g表示,或更明确地表示成f(x1,x2,xn),称为n元布尔表达式,其中x1,x2,xn是式中可能含有的布尔变元。布尔表达式中的某些圆括号可以省略,约定类似于命题公式。,例5设0,a,b,1,*,0,1是布尔代数,则 f1=a f 2=0*x f 3=(1*x1)x2 f 4=(a b)(x1 x2)*(x1*x2)都是这个布尔代数上的布尔表达式。布尔表达

39、式中的符号,和,就是相应布尔代数中,和三种运算,它们满足布尔代数的所有公式,可以按照这些公式进行计算。,定义7.49布尔代数B,*,0,1上的布尔表达式 f(x1,x2,xn)的值指的是:将B的元素作为变元xi(i=1,2,n)的值而代入表达式以后,计算出来的表达式的值。例6(a)取x1=a,x2=b,则例5中的f3的值是 f3=(1*a)b=a b=1(b)设布尔代数0,1,*,0,1上的表达式 f(x1,x2,x3)=(x1*x2)(x1 x2)(x2 x3),则 f(1,0,1)=(0*1)(0 1)*(0 1)=0*1*1=0,定义7.410布尔代数B,*,0,1上两个n元布尔表达式f

40、1(x1,x2,xn)和f2(x1,x2,xn),如果对n个变元的任意指派,f1和f2的值均相等,则称这两个布尔表达式是等价的或相等的。记作 f1(x1,x2,xn)=f2(x1,x2,xn)。在实践上,如果能有限次应用布尔代数公式,将一个布尔表达式化成另一个表达式,就可以判定这两个布尔表达式是等价的。,定义7.410给出的等价关系将n元布尔代数表达式集合划分成等价类,处于同一个等价类中的表达式都相互等价。可以证明等价类数目是有限的。为此,我们考察以下定义。定义7.411给定n个布尔变元x1,x2,xn,表达式 称为极小项。这里 表示xi或xi两者之一。,定义7.412 型式的布尔表达式称为主

41、析取范式。这里mi是极小项,i是布尔常元。(i=0,1,2,2n-1)。因为i有|B|种取法,故不同的主析取范式有 个。特别,B=0,1时有 个。任何一个n元布尔表达式都唯一地等价于一个主析取范式。把一个n元布尔表达式化成等价的主析取范式,主要应用德摩根定律等,其方法与“数理逻辑”和“数字逻辑”中化成主析取范式的方法完全一致。,2n个极小项最多只能造出 个不同的主析取范式,所以,一个n元布尔表达式必等价于这 个主析取范式之一。平行地可讨论极大项和合取范式。定义7.413给定n个布尔变元x1,x2,xn。表达式,称为极大项。这里 表示xi或xi两者之一。,显然,有2n个不同的极大项。分别记为M0

42、,M1,M2,足标是二进制数a1,a2,an的十进制表示。,当 时,当 时,(i=1,2,n),注意:足标规定与极小项不同。极大项满足以下性质:,时,定义7.414 型式的布尔表达式称为主合取范式。这里Mi是极大项,i是布尔常元,(i=0,1,2,2n-1)。任何一个n元布尔表达式都唯一地等价于一个主合取范式。2n个极大项最多只能造出 个不同的主合取范式。所以,一个n元布尔表达式必等价于这 个主合取范式之一。,定义7.413 给定n个布尔变元x1,x2,xn。表达式,称为极大项。这里 表示xi或xi两者之一。,显然,有2n个不同的极大项。分别记为 M0,M1,M2,足标是二进制数a1,a2,a

43、n的十进制表示。,极大项满足以下性质:,时,定义 7.414(0 M0)*(1 M1)*()型式的布尔表达式称为主合取范式。这里Mi是极大项,i是布尔常元,(i=0,1,2,2n-1)。任何一个n元布尔表达式都唯一地等价于一个主合取范式。2n个极大项最多只能造出 个不同的主合取范式。所以,一个n元布尔表达式必等价于这 个主合取范式之一。,例7(a)将布尔代数 上的布尔表达式 化成主析取范式。,(b)将布尔代数0,1,*,0,1上的布尔表达式f(x1,x2,x3)=x1x2 x3化成主合取范式。,一个n元布尔表达式,对n个变元的每一指派,都可得到相应的表达式的值,这值属于B。所以,每一布尔表达式

44、都代表一个函数。但n个变元的主析取范式(或主合取范式)最多只有 个,所以,至多只能代表 个不同的函数。从Bn到B的函数共有 个。现分情况讨论:(1)B=0,1时,从Bn到B的函数共有 个,主析取范式也有 个,恰好每一主范式代表一个函数。所以,在B=0,1时,每一函数均可用布尔表达式表示。,例如,表7.43所表示的函数可表达为,(2)B0,1时,例如B=0,a,b,1时,从Bn到B的函数共有 个,但主析取范式仍只有 个,所以,不是每一函数都可用布尔表达式表示。,定义7.415设B,*,0,1是一个布尔代数,一个从Bn到B的函数,如果能够用该布尔代数上的n元布尔表达式表示,那么这个函数就称为布尔函数。例如,表7.44所示的函数不是布尔函数。若不然,不妨设,这里Cij取值于0,a,b,1,根据表的第一行 f(0,0)=C22*1*1=C22=1,根据表的第二行,不管C21取什么值,上式都不可能成立。所以,布尔 表达式表示不了这个函数,它不是布尔函数。,