布尔代数 (2)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,9.3,布尔代数,定义,9.3.1,设,L,是一个格，若,L,有最大元和最小元，则称,L,为有界格，最大元记为,I,，,最小元记为,O,。,例,9.3.1,设,S,是集合，则,(,P,(,S,),),是,有界格。,群,G,的全体子群,S,(,G,)，,群,G,的全体正规子群,H,(,G,),以及,环,R,的全体理想,I,(,R,),对于,偏序,构成的,格，,线性空间,V,的全体子空间,S,(,V,),对于,偏序,的,格,，,都,是,有界格。,如果,L,是一个有界格，则对任意,a,L,均有,（,1,）,O,a,I,（,2,）,a,O,=,a,a,O,=,O,（,3,）,a,I,=,I,a,I,=,a,例 设,Z,+,是正整数集合，偏序“,”为：,a,b,a,|,b,则格,(,Z,+,),不,是有界格，,(,Z,+,),无最大元,。,全序集,(,Z,),不,是有界格，,(,Z,),无最元,。,定义,9.3.2,设,L,是一个格，如果,L,是一个有限集合，则称,L,为有限格。,定理,9.3.1,设,L,是一个有限格，则,L,是有界格。,设有限格,L,=,x,1,x,2,x,n,则有,I=,x,1,x,2,x,n,O,=,x,1,x,2,x,n,定义,9.3.3,设,L,是格，若对任意,a,b,c,L,，,有,（,1,）,a,(,b,c,)=(,a,b,),(,a,c,),(,对,的,分配律,),（,2,）,a,(,b,c,)=(,a,b,),(,a,c,),(,对,的,分配律,),则称,L,是分配格。,例,9.3.2,设,S,是集合，则,(,P,(,S,),),是分配格。,例,9.3.3,设,L,是格，它的哈斯图为图,9.3.2,的,(,a),和,(,b),，,则,L,不是分配格。,图,9.3.2,定理,9.3.2,L,不是分配格的充要条件是,L,有一个子,格同构于图,9.3.2,中的二个图之一。,这里图的同构是指在拓扑意义下的同构。,例,9.3.4,请判断图,9.3.3,所示的格是否是分配格。,图,9.3.3,定理,9.3.3,如果对任意,a,b,c,L,均有,a,(,b,c,)=(,a,b,),(,a,c,),则一定有,a,(,b,c,)=(,a,b,),(,a,c,),；,反之也成立。,由于(,a,b,),(,a,c,)=(,a,b,),a,),(,a,b,),c,),=,a,(,a,b,),c,)=,a,(,a,c,),(,b,c,),=(,a,(,a,c,),(,b,c,)=,a,(,b,c,),因此一个,格是分配格,当且仅当格,存在一种,(,对,的或,对,的,),分配律,定义,9.3.4,设,L,是一个有界格，,O,和,I,分别为,L,的最小和最大元，如果对,a,L,，存在,b,L,，使得,a,b,=,I,a,b,=,O,则称,b,为,a,的补，如果,L,中的元素都有补，则称,L,为有补格。,例,9.3.5,幂集合格,(,P,(,S,),),是有补格。,由,O,I,=,O,O,I,=,I,可知,I,是,O,的补，,O,是,I,的,补。另外由补的定义知,若,a,是,b,的补,则,b,一定是,a,的补。,例,9.3.7,试问格,(,D,n,|,),是否是有补格？,（,1,）,D,20,=1,2,4,5,10,20,（,2,）,D,30,=1,2,3,5,6,10,15,30,解 在,D,20,中,O,=1,I,=20,由2,x,=1,知,x,=1,5,但2,1=2,2,5=10,故不存在,x,D,20,使得 2,x,=1,2,x,=20,D,20,不是有补格,。,在,D,30,中,O,=1,I,=30,1,的补是,30,2,的补是,15,3,的,补是,10,5,的补是,6,故,D,30,是有补格,。,定理,9.3.4,设,L,是一个有界分配格,a,L,，,如果元素,a,的补存在，则必定是唯一的。,设,L,是一个布尔代数，则,L,中的每个元素都有唯一的补。求补是布尔代数,L,上,的一元运算，用记号“,”表示求补运算。,求补运算具有如下性质：,定义,9.3.5,一个有补的分配格称为布尔代数。,一个有限集构成的布尔代数称为有限布尔代数。,例,9.3.2,布尔代数的一个最重要的例子是：,(,P,(,S,),),O,=,I,=,S,。,定理,9.3.5,设,(,B,),是布尔代数，则有,（,1,）交换律,x,y,=,y,x,x,y,=,y,x,（,2,）,结合律,x,(,y,z,)=(,x,y,),z,x,(,y,z,)=(,x,y,),z,（,3,）,等幂律,x,x=x,x,x=x,（,4,）,吸收律,x,(,x,y,)=,x,x,(,x,y,)=,x,（,5,）,分配律,x,(,y,z,)=(,x,y,),(,x,z,),x,(,y,z,)=(,x,y,),(,x,z,),（,6,）,同一律,x,O,=,x,x,I,=,x,（,7,）,零一律,x,I=I,x,O=O,（,8,）,互补律,x,x,=,I,x,x,=,O,（,9,）,对合律,x,=,x,（,10,）,德摩根律,x,y,=,x,y,x,y,=,x,y,事实上，前面的十条运算规律并不独立，可以由,交换律，分配律，同一律，互补律,四条得到。,布尔代数,与,布尔环,(,即,每个元都是幂等元的,含幺环,),等价,:,(,B,),为,布尔代数,(,B,+,x,),是,布尔环,且,(1),布尔代数,的,最大元,(,最小元,)对应于,环,B,的,单位元,(,零元,),(2),环,B,是,交换环，,a+b+,ab,+,ba,=,a,2,+b,2,+,ab,+,ba,=,(,a+b,),2,=,a,+,b,(3),加法群(,B,+,),中每个非零元的,阶都为2,，上式中取,a=b,其中,a,+,b,=(,a,b,),(,a,b,),即,a,与,b,的对称差,a,x,b,=,a,b,；,或,a,b,=,a,+,b,-,a,x,b,a,b=,a,x,b,.,定义,9.3.6,设,(,B,),是布尔代数，,S,是,B,的非空子集，如果,S,对于运算,都,封闭，则称,S,是布尔代数,B,的子代数。,例如，设,(,B,),是布尔代数，,S,=,O,I,则,S,是布尔代数,B,的子代数。,例,9.3.9,如果,S,是布尔代数,B,的子代数，则,O,I,S.,I=a,a,O=a,a,定义,9.3.7,设,(,B,1,),(,B,2,),是两个布尔代数，,f,是,B,1,到,B,2,的一个映射,若,对任意,a,b,B,1,均有,f,(,a,b,)=,f,(,a,),f,(,b,),f,(,a,b,)=,f,(,a,),f,(,b,),f,(,a,)=,f,(,a,),则称,f,是,B,1,到,B,2,的同态映射,，,称,f,(,B,1,),为,B,1,的同态像；,当,f,是单射,(,满射，双射,),时，称,f,为,单同态,(,满同态，同构,),。如果存在,B,1,到,B,2,的同构映射，则称,B,1,和,B,2,同构，用,B,1,B,2,表示。,定理,9.3.6,设,(,B,),是布尔代数，,S,是,B,的子代数，,T,是,B,的同态像，则,S,和,T,都,是布尔代数。,证（,1,）由于,S,是,B,的子代数，因此,S,对于运算封闭，说明,S,是,B,的子格，又由,S,对于求补封闭知,S,是有补格，而分配律在,B,中成立在,S,也成立，于是,S,是有补分配格，即,S,是布尔代数。,（,2,）设,T,=,f,(,B,),，,f,是,B,到,B,的同态。由,a,b,T,知存在,x,y,B,使得,a,=,f,(,x,),b,=,f,(,y,),，,所以,T,对于运算封闭，由此推出,T,是的子代数，根据（,1,）,T,是布尔代数。,