离散数学06-布尔代数.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,北 京 交 通 大 学,软件学院 电子教案,离散结构,第九章 格与布尔代数,9.1,格,9.2,布尔代数,9.3,子布尔代数、积布尔代数,和布尔代数同态,9.4,布尔代数的原子表示,9.5,布尔代数,B,r,2,9.6,布尔表达式及其范式定理,9.1,格,1,格作为偏序集,定义,9.1.1,设,是一个偏序集，若对任意,a,b,L,，存在,glba,b,和,luba,b,，则称,为格，并记为,a*b=,glba,b,，,a,b,=,luba,b,，称,和,分别为,L,上的交（或积）和并（或和）运算。称,为,所诱导的代数结构的格。若,L,是有限集合，称,为有限格。,格的对偶性原理是成立的：,令,是偏序集，且,是其对偶的偏序集。若,是格，则,也是格，反之亦然。这是因为，对于,L,中任意,a,和,b,，,中,luba,b,等同于,中,glb,a,b,，,中,glba,b,等同于,中的,luba,b,。若,L,是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。,从上讨论中，可知两格互为对偶。互为对偶的两个,和,有着密切关系，即格,中交运算,正是格,中的并运算,，而格,中的并运算,正是格,中的交运算,。因此，给出关于格一般性质的任何有效命题，把关系换成（或者换成），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。,定义,9.1.2,设,是格，且,S,L,。若对任意,a,b,S,，有,a*,b,S,和,a,b,S,，则称,是格,的子格。,2,格的基本性质,在证明格的性质前，回忆一下,a*b,和,a,b,的真正含义是有好处的。,a*,ba,和,a,bb,，则表明,a*b,是,a,和,b,的下界。,若,ca,和,cb,，则,ca,*b,，这表明,a*b,是,a,和,b,的最大下界。,aa,b,和,ba,b,，则表明,a,b,是,a,和,b,的上界。,若,ac,，且,bc,，则,a,bc,，这表明,a,b,是,a,和,b,的最小上界。,定理,9.1.1,设,是格，对任意,a,b,L,，有,a,b,=,b,ab,a*b=,a,ab,a*b=,a,a,b,=b,亦即,ab,a,b,=,b,a,*b=a,定理,9.1.2,设,是格，对任意,a,b,L,，有,a*b=a,a,a,=a,。（幂等律）,a*b=b*a,a,b,=,b,a,。（交换律）,a*(b*c)=(a*b)*c,a,(b,c,)=(,a,b),c,（结合律）,a*(,a,b,)=a,a,(a,*b)=a,（吸收律）,定理,9.1.3,设,是格，对任意,a,b,c,L,，有,若,ab,和,cd,，则,a*,cb,*d,，,a,cb,d,。,若,ab,，则,a*,cb,*c,，,a,cb,c,。,ca,和,cb,ca,*b,ac,和,bc,a,bc,定理,9.1.4,设,是格，对任意的,a,b,c,L,，有,a,(b,*,c)(a,b,)*(,a,c,),(a*,b),(a,*,c)a,*(,b,c,),通常称上二式为格中分配不等式。,定理,9.1.5,设,是格，对任意的,a,b,c,L,，有,ac,a,(b,*c)(,a,b,)*c,推论,：在格,中，对任意的,a,b,c,L,，有,(a*,b),(a,*,c)a,*(,b,(a,*c),a,(b,*(,a,c)(a,b,)*(,a,c,),3,特殊的格,定义,9.1.3,设,是格，若,L,中有最大元和最小元，则称,为有界格。一般把格中最大元记为,1,，最小元记为,0,。,由定义可知，对任意,a,L,，有,0a1,a*0=0,a,0=a,a*1=a,a,1=1,定理,9.1.6,设,是有限格，其中,L=,a,1,a,2,a,n,，则,是有界格。,定义,9.1.4,设,是有界格，对于,a,L,，存在,b,L,，使得,a*b=0,，,a,b,=1,称,b,为,a,的补元，记为,a,。,由定义可知，若,b,是,a,的补元，则,a,也是,b,的补元，即,a,与,b,互为补元。,显然，,0=1,和,1=0,，且易证补元是唯一的。,一般说来，一个元素可以有其补元，未必唯一，也可能无补元。,定义,9.1.5,设,是格，对任意的,a,b,c,L,，有,a*(,b,c,)=(a*,b),(a,*c),a,(b,*c)=(,a,b,)*(,a,c,),则称,为分配格，称和为格中分配律。,定义,9.1.6,设,是格，对任意的,a,b,c,L,，有,ac,a,(b,*c)=(,a,b,)*c,称,为模格。,定理,9.1.7,分配格是模格,定理,9.1.8,每个链都是分配格。,定理,9.1.9,一个格为分配格，当且仅当它不含有任何子格与这两个五元素格中任一个同构。,定理,9.1.10,设,是分配格，对任意,a,b,c,L,，有,(a*b=a*c),且,(,a,b,=,a,c),b,=c,定理,9.1.11,设,是有界分配格，若,a,L,，且补元存在，则其补元是唯一的。,定义,9.1.7,设,是格，若,L,中每个元素至少有一补元，则称,为有补格。,由于补元的定义是在有界格中给出的，可知，有补格一定是有界格。,定义,9.1.8,若一格既是有补又是分配的，则称该格为有补分配格，或布尔格，或布尔代数。,定理,9.1.12,设,是有补分配格，若任意元素,a,L,，则,a,的补元,a,是唯一的。,该定理,9.1.11,的直接推论，因为有补分配格当然是有界分配格。,由于有补分配格中，每个元素,a,都有唯一的补元,a,，因此可在,L,上定义一个一元运算,补运算“”。这样，有补分配格可看作具有两个二元运算和一个一元运算的代数结构，习惯上称它为布尔代数，记为,，其中,B=L,。,定理,9.1.13,设,是有补分配格，对任意,a,b,L,，则,(a)=a,(a*b)=,a,b,(,a,b,)=a*b,后两式称为格中德,摩根律。,定理,9.1.14,设,是有补分配格，对任意,a,b,L,，有,ab,a,*b=0,a,b,=1,格同态，格直积等概念可以接下来定义和研究，但这里不打算这样做，因为如此进行会相对较繁，而是将格作为一个代数结构而引入它们。,4,格是代数结构,能自然地把代数结构中有关子代数、同态、积代数等概念，引入到格中。,定义,9.1.9,设,是一代数结构，其中,和*是,L,上满足交换律、结合律和吸收律的二元运算，且对任意,a,b,L,，定义关系如下：,ab,a,*b=a,则,是格，称,为代数系统,所诱导的偏序集确立的格。,定义,9.1.10,设,和,是格。存在函数,f:L,S,，若对任意,a,b,L,，有,f(a,b,)=,f(a),f(b,),，,f(a,*b)=,f(a),f(b,),则称,f,是从,到,的格同态。,下述定理说明格同态是保序的。,定理,9.1.15,设,和,是格，而,和,分别是给定两个格所诱导的偏序集确立的格。若,f:L,S,是格同态，则对任意,a,b,L,，且,ab,，必有,f(a)f(b,),。,在定义,9.1.10,中，若,f,是双射函数，则称,f,是格同构。或称,和,两个格同构。由于同构是相互的，又是保序的，故对任意,a,b,L,，有,ab,f(a)f(b,),和,f(a)f(b),ab,这表明同构的两个格的哈斯图是一样的，只是各结点的标记不同而已。,定义,9.1.11,设,和,是格，定义一个代数结构,如下：,对任意,，,L,S,，有,+=,o=,称,是格,和,的直积。,两个格的直积也是格。这是因为在,L,S,上，运算,o,和,+,是封闭的，且满足交换律、结合律和吸收律。,格积的阶等于两个格的阶乘积。由于,是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。,9.2,布尔代数,前已指出，布尔代数是有补分配格，常记为,。对任意,a,b,c,B,，有,是格，且为,B,上由,或*所定义的偏序关系，满足,(L-1),a,b,=,luba,b,，,a*b=,glba,b,(L-2),ab,a,b,=,b,a,*b=a,(L-3),a,a,=a,，,a*a=a,（等幂律）,(L-4),a,b,=,b,a,，,a*b=b*a,（交换律）,(L-5)(,a,b),c,=,a,(b,c,),，,(a*b)*c=a*(b*c),（结合律）,(L-6),a,(a,*b)=a,，,a*(,a,b,)=a,（吸收律）,是分配格，满足,(D-1),a,(b,*c)=(,a,b,)*(,a,c,),，,a*(,b,c,)=(a*,b),(a,*c),（分配律）,(D-2)(,a,b,=,a,c),(a,*b=a*,c),b,=c,(D-3)(,a,b,)*(,b,c,)*(,c,a,)=(a*,b),(b,*,c),(c,*a),是有界格，满足,(B-1)0a1,(B-2)a,0=a,，,a*a=a,（幺律）,(B-3)a,1=1,，,a*0=0,（零律）,是有补格，满足,(C-1),a,a,=1,，,a*a=0,（互补律）,(C-2)1=0,，,0=1,是有补分配格，满足,(CD-1)(,a,b,)=a*a,，,(a*b)=,a,b,（德,摩根律）,(CD-2),ab,a,b,=1,a*b=0,ba,注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。,定义,9.2.1,设,是一代数结构，其中,和*是,B,上的二元运算，是,B,上的一元运算。,0,1,B,。若对任意,a,b,B,，有,a,b,=,b,a,，,a*b=b*a,（交换律）,a,(b,*c)=(,a,b,)*(,a,c,),，,a*(,b,c,)=(a*,b),(a,*c),（分配律）,a,0=a,，,a*1=a,（幺律）,a,a,=1,，,a*a=0,（互补律）,则称,是布尔代数，称,、*和分别是,B,上的并、交和补运算，,0,和,1,分别称为,和*的零元和幺元。,代数结构,满足定义,9.2.1,的条件，所以它是布尔代数，它是二元布尔代数。二元布尔代数其哈斯图是链的唯一布尔代数。,9.3,子布尔代数、积布尔代数和布尔代数同态,把子代数、积代数和同态的概念应用到布尔代数上，便得到了相应论题，本节不准备详尽叙述它，仅就其特点讨论之。,定义,9.3.1,给定布尔代数,，,T,B,，若,T,对所有运算封闭，且,0,，,1T,，则称,是子布尔代数。,显然，,和,是子布尔代数。,应该指出，没有必要对所有三个运算,，和都要检查封闭性，也没有必要验证,0,与,1,是否在,T,中，只要对运算集合,，,或,，,检查其封闭性即可。这可从布尔代数中这两个运算集合是全功能集得出。因为对任意,x,，,yS,，有,xy,=(,x,y,),，,0=(,x,x,),，,1=,x,x,，故对于,和的封闭便保证了的封闭以及,0,，,1T,。,对于,，,可用同样论证。,显然，每个子布尔代数都是布尔代数。,布尔代数的子集可以是个布尔代数，但也可能不是布尔代数，因为这可从它对运算是否封闭而定。,定义,9.3.2,给定两个布尔代数,和,，则两个布尔代数的积也是布尔代数，称为积布尔代数，记作,，其中对任意,，,B,1,B,2,，有,3,=,3,=,=,0,3,=,，,1,3,=,可见，积布尔代数能够生成新的布尔代数。,定义,9.3.3,给定两个布尔代数,和,，则,：,=(,f)(fT,B,(,x)(,y)(x,，,yS(f(x+y,)=,f(x,),f(y)f(xy,)=,f(x)f(y)f(x,)=f(0)=f(1)=),并称,f,为从,到,的布尔同态映射。,如前所述，同态的定义仍可简化成：若保持运算,，,或,，,则,fT,B,为布尔同态映射。又若,f,为双射，则,f,为布尔同构映射。,定理,9.3.1,若,f,为从,到,的布尔同态映射，且,|f(B)|2,，其中,f(B,)=,y|f(x,)=,yTxB,，则,是布尔代数。,9.4,布尔代数的原子表示,在布尔集合代数中，每个子集可表成单元集的并，而且这种表示在不计项的次序情况下是唯一的。对于任何有限布尔代数，也将有同样的结果，这里起着单元集作用的那些元素，称它们是原子。,定义,9.4.1,给定布尔代数,且,0,a,B,，则,a,为原子：,=(,x,)(,x,B,a,x,=,a,a,x,=0),因为,a,x,=,a,a,x,，所以上述定义又可表为,a,为原子：,=(,x,)(,x,S,a,x,a,x,=0),若,a,为原子且,x,a,，则,x,=0,或,x,=,a,。这表明原子在偏序图中是那些紧位于零元之上的元素。,定理,9.4.1,若,a,1,和,a,2,为布尔代数,的原子，且,a,1,a,2,0,，则,a,1,=,a,2,。,定理,9.4.2,若,x,是有限布尔代数,的非零元，则存在原子,a,S,，使得,a,x,。,定理,9.4.3,若,a,，,a,1,，,a,2,，,，,a,n,为有限布尔代数,的原子，则,a,a,1,a,2,a,n,(,i,)(,i,1,，,2,，,，,n,a,=,a,i,),定理,9.4.4,设有限布尔代数,的所有原子是,a,1,，,a,2,，,，,a,n,，且,y,B,，则,y,=0,(,i,)(,i,1,，,2,，,，,n,y,a,i,=0),定理,9.4.5(,原子表示定理,),给定布尔代数,，,0,x,B,以及,i,=1,，,2,，,，,n,，,a,i,x,，则,x,=,a,i,，且不计原子的次序表示式是唯一的。,定理,9.4.6(,斯通,(Stone),定理,),设,是有限布尔代数，且,A,表示该代数中的所有原子的集合，则,同构于幂集代数,。,本定理说明了，能够用布尔代数的各原子，完全确定该布尔代数，并且可用布尔集合代数,表示这一布尔代数。,由本定理可直接得到下面推论：,|,B,|=2,|,A,|,由此又可推出，若两个有限布尔代数中的集合有相同的基数，则它们的原子集合也有相同的基数。于是该二个布尔代数是同构的。因此可得到如下定理：,定理,9.4.7,每个有限布尔代数的集合基数均为,2,的方幂，具有同样集合基数的布尔代数都是同构的。,9.5,布尔代数,B,r,2,为了书写方便，用,B,n,表示具有,n,个元素的布尔代数,，即,B,n,=,。根据定理,9.4.7,可知，,n,必为,2,的方幂。因此，“最小”的布尔代数即是二元布尔代数,B,2,=,，其中,B,2,=0,，,1,。,B,2,的运算表如表,9.1.1,所示。下面再给出“次最小”的布尔代数,B,4,=,的运算表,9.5.1,，其中,B,4,=0,，,，,，,1,。,特别令人感兴趣的代数结构是,B,2,B,2,B,2,(,r,个,),，即,r,个相同的布尔代数,B,2,的直积。该系统记作,B,r,2,，且其运算符号仍与,B,2,中的,，和相同，即,B,r,2,=,。对任意,和,B,r,2,，其中,i,，,j,0,，,1,，,i,，,j,=1,，,2,，,，,n,。,=,=,=,0=,和,1=,由积代数的理论可知，,B,r,2,保持,B,2,中重要性质，于是断言，,B,r,2,是布尔代数，并且由定理,9.4.7,能得到下面定理：,定理,9.5.1,布尔代数,与,是同构的，并且每个布尔代数同构于某布尔代数,B,k,2,=,。,综上所述可知，每个布尔代数同构于某布尔集合代数。,9.6,布尔表达式及其范式定理,本节中先给出布尔表达式或布尔函数的定义，后讨论布尔表达式的范式定理。,定义,9.6.1,给定布尔代数,及,n,个变元,x,1,，,x,2,，,，,x,n,，则在,上由,n,个变元产生的布尔表达式可归纳定义如下：,(1)(,基础,),。,B,中的任何元素和变元,x,i,(,i,=1,，,2,，,，,n,),都是一个布尔表达式。,(2)(,归纳步,),。若,e,1,和,e,2,是布尔表达式，那么,e,1,，,(,e,1,),(,e,2,),和,(,e,1,)(,e,2,),也是布尔表达式。,注意，当约定先于,运算时，可适当省略表达式中的园括号。,如果限定,n,个变元,x,1,，,x,2,，,，,x,n,都取值于,B,中的元素，那么在布尔代数,上由变元,x,1,，,x,2,，,，,x,n,所产生的布尔表达式的值便表示,B,中的元素。因此，这些表达式便是一个函数,f,B,n,，这里,f,(,x,1,，,x,2,，,，,x,n,),对任意变元,x,1,，,x,2,，,，,x,n,可由布尔代数,中关于,，的运算来确定。因此，有时将在,上由变元,x,1,，,x,2,，,，,x,n,产生的布尔表达式称为在,上的,n,元布尔函数,(,以下简称布尔函数,),。,定义,9.6.2,形如 ,的布尔表达式称为由变元,x,1,，,x,2,，,，,x,n,产生的小项，其中,i,0,，,1,，用,x,1,i,表示,x,i,，,x,0,i,表示,x,i,，,i,1,，,2,，,，,n,，并用 表示该小项。,形如,的布尔表达式称为由变元,x,1,，,x,2,，,，,x,n,产生的大项，其中,i,0,，,1,，,x,1,i,表示,x,i,，,x,0,i,表示,x,i,，,i,1,，,2,，,，,n,，并用 表示该大项。,为书写方便，将二进制数,1,2,n,和,1,2,n,分别化为十进制数,i,和,j,作为,m,和,M,的下标，即,m,i,和,M,j,。,关于小项和大项有下列关系：,m,i,m,j,=0 (,i,j,),M,i,M,j,=1 (,i,j,),这是显然的，因为对于两个不同的小项,(,大项,),，必有一个变元,x,k,，使得这两个小项,(,大项,),之一含有,x,k,，而另一个含有,x,k,。于是，,x,k,x,k,=0,，,x,k,x,k,=1,。因此上列关系成立。,使用归纳法不难证明下列关系：,m,i,=1,M,i,=0,定理,9.6.1(,范式定理,),在布尔代数,上由变元,x,1,，,x,2,，,，,x,n,产生的每个布尔表达式,f,(,x,1,，,x,2,，,，,x,n,),均可表成：,f,(,x,1,，,x,2,，,，,x,n,)=(,c,k,m,k,)(1),f,(,x,1,，,x,2,，,，,x,n,)=(,C,l,M,l,)(2),这里，,k,和,l,分别取遍,2,n,个所有可能的组态,1,2,n,和,1,2,n,，并且,=,f,(,1,，,2,，,，,n,),=,f,(,1,，,2,，,，,n,)(3),由本定理可知，布尔代数,上的由变元,x,1,，,x,2,，,，,x,n,产生的每个布尔表达式均可表为所有小项的带“权”的并，或者所有大项的带“权”的交，其中这些“权”,(,即,c,1,2,n,或,C,1,2,n,),是,B,中的元素，它可用布尔表达式用公式,(3),计算得到。由于这些权是唯一的，故上述公式,(1),和,(2),便是唯一的，并称,(1),为小项范式或析取范式，称,(2),为大项范式或合取范式。,布尔表达式的范式也可由下面算法,9.6.1,（或,9.6.2,）得到。,算法,9.6.1,（或,9.6.2,）,本算法可求出,上的布尔表达式,f,(,x,1,，,x,2,，,，,x,n,),范式，其具体步骤是：,(1),使用定律和定理把,f,(,x,1,，,x,2,，,，,x,n,),表示成形如,c,（或,C,）的不同交（或并）的并（或交），其中,c,C,B,且,i,1,i,2,i,k,。,(2),若每个交（或并）是形如,c,m,（或,C,M,），其中,c,B,（或,C,B,），,m,是小项（或,M,是大项），则增加项,(0,m,1,),(0,m,2,),（或增加项,(1,M,1,)(1,M,2,),），其中,m,1,m,2,（或,M,1,M,2,）是表达式中缺乏的小项（或大项），否则转到,(3),。,(3),从最后得到的表达式中，选取形如,c,（或,C,）的交（或并），其中,k,n,和对某个,h,（或 ）不出现，则用,再在新的交（或并）中按下标增加次序重新排列 （或 ），于是使用,(,c,1,c,2,),m,(,或,(,C,1,C,2,),M,代替,c,1,m,c,2,m,（或,C,1,M,C,2,M,）的交（或并）。转到,(2),。,因为在,上的布尔表达式,f,(,x,1,，,x,2,，,，,x,n,),是由,2,n,个权唯一确定，又因为每个权是,B,中的元素，所以在,上共有 个不同布尔表达式。,另一方面，形如,f,的不同函数共有 个 。可见，当,|,B,|2,时，形如,f,的函数中确有那些函数，它不是布尔函数。而且可以精确计算,-,个函数不是布尔函数。,例如对于,S,=,0,1,，函数,f,的定义中有,f,(0,0)=0,，,f,(0,1)=1,，,f,(1,0)=,f,(1,1)=,，,f,(0,)=,则,f,不是布尔函数，为什么？读者从上面的说明中是不难给出正确地回答。,