十二章节格与布尔代数

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十二章,格与布尔代数,12.1,格定义的代数系统,12.2,格的代数定义,12.3,一些特殊的格,12.4,有限布尔代数的唯一性,12.5,布尔函数和布尔表达式,复习：偏序集、格,格是一个偏序集，在这个偏序集中，每两个元素有唯一一个最小上界和唯一一个最大下界。,定义（见第,85,页定义,1,） 设,A,是一个非空集合，,R,是,A,上的一个二元关系，若,R,有自反性、反对称性、传递性，说,R,是,A,上的一个偏序关系。,并称,(A,，,R),是一个偏序集。,注意：, 对于一个偏序关系，往往用记号“,”来表示。, 若,(a,，,b) ,，记为,a,b,，读做“,a,小于等于,b”,。, 一个偏序集，通常用符号,(A,，,),来表示。,格,例 如图用哈斯图给出了一个有,5,个元的格。,定义（见第,86,页定义,2,）,A,是一个非空集，,(A,，,),是一个偏序集，若对于任意的元素,a,和,b,属于,A,，在,A,中存在,a,和,b,的最小上界及最大下界，就说,(A,，,),是一个格。,a,1,a,2,a,4,a,5,a,3,例,30,6,10,15,2,3,5,1,右上图所示的偏序集,(D(30),，,R),是格。,（详见练习,7.33),例 右下图所示的偏序集,(1, 2, 3, 4,),不是格。,（详见第,85,页例,1,）,1,2,3,4,由格定义的代数系统,设,(A,，,),是一个格，定义代数系统,（,A,，）,其中和是,A,上的两个二元运算，,对于任意的,a,，,b,A,，,ab,等于,a,和,b,的最小上界，,ab,等于,a,和,b,的最大上界。,称（,A,，）是由格,(A,，,),所定义的代数系统。,注意：二元运算通常称为并运算，二元运算通常称为交运算，因此，,a,和,b,的最小上界，也称,a,和,b,的并；,a,和,b,的最大下界，也称,a,和,b,的交。,例,设,2,A,是集合,A,的幂集，（,2,A,，,）是一个格。,因此，它确定了一个对应的代数系统：,（,2,A,，）。,对于任意的,x,，,y,A,，由定义知,:,xy=x,y,，,xy=x,y,。,例,设,Z,+,是正整数集，是,Z,+,上一个二元关系，,（,Z,+,，）是一个格。,在格（,Z,+,，）所定义的代数系统：,（,Z,+,，）,中，对于任意的,m,，,nZ+,，,mn=m,和,n,的最小公倍数；,mn=m,和,n,的最大公约数。,定理,1,对于格,(A,，,),中的任意元素,a,和,b,，有：,a,ab (12.1),ab,a (12.2),定理,2,(A,，,),是一个格，对于,A,中的任意的,a,、,b,、,c,和,d,，,如果,a,b,且,c,d,，则有：,ac,bd (12.3),ac,bd (12.4),定理,3,设,(A,，,),是一个格， （,A,，）是格,(A,，,),定义的代数系统，则对于任意的,a,，,b,，,c,A,，以下算律成立：,L1,：,aa=a,，,aa=a,；（幂等律）,L2,：,ab=ba,，,ab=ba,；（交换律）,L3,：,(ab)c=a(bc),(ab)c=a(bc),；（结合律）,L4,：,a(ab)=a,，,a(ab)=a,。（吸收律）,第十二章,格与布尔代数,12.1,格定义的代数系统,12.2,格的代数定义,12.3,一些特殊的格,12.4,有限布尔代数的唯一性,12.5,布尔函数和布尔表达式,问题,设（,A,，）是具有两个二元运算和的代数系统，并且和运算适合上节定理,3,中描述的四个算律,L1,、,L2,、,L3,与,L4,。,如何设法利用和运算在,A,中引入一个偏序关系,，使,A,关于这个偏序关系构成一个格？,问题,(,续,),问题,: ab=a,和,ab=b,是否同时成立？,代数系统定义的二元关系,定义,:,在集合,A,上定义二元关系：,对于任意,a,，,b,A,，若,ab=a,成立,(,或,ab=b,成立,),，,则定义,a,b,。,验证,:,所定义的二元关系是偏序关系,自反性,反对称性,传递性,所以,是,A,上的偏序关系，（,A,，,）是一个偏序集。,验证,:,所定义的偏序集是格,首先，证明对于任意的,a,，,bA,，,ab,是,a,，,b,的最大下界。,可以证明,ab,是,a,，,b,的最小上界。,总之，由代数系统,(A,，,),定义的偏序集,(A,，,),是格。,格的等价定义,定义,1,：设（,A,，）是一个代数系统，和是,A,上的两个封闭的二元运算，且满足算律：,对于任意的,a,，,b,，,c,A,，,L1,：,aa=a,，,aa=a,； （幂等律）,L2,：,ab=ba,，,ab=ba,； （交换律）,L3,：,(ab)c=a(bc),(ab)c=a(bc),； （结合律）,L4,：,a(ab)=a,，,a(ab)=a,。 （吸收律）,则说（,A,，）是一个格。,例,1 (Z,+,，,)= (Z,+,，,|),Z,+,是正整数集，对于任意的,a,，,b,Z,+,，规定,ab=(a,，,b),（即,a,和,b,的最大公约数），,ab=a,，,b,（即,a,和,b,的最小公倍数）,ab,和,ab,是,Z,+,上的两个二元运算,可以证明：,(Z,+,，,),是一个格,且与格,(Z,+,，,|),是一致的。,第十二章,格与布尔代数,12.1,格定义的代数系统,12.2,格的代数定义,12.3,一些特殊的格,12.4,有限布尔代数的唯一性,12.5,布尔函数和布尔表达式,分配格,定义,1,设,(A,，,),是一个格，,若对于任意,a,，,b,，,c,A,，有,a(bc)= (ab)(ac),a(bc)= (ab)(ac),则称,(A,，,),是一个分配格。,例,(2,A,，,，,),是一个分配格。,泛下界、泛上界,定义,2,设,(A,，,),是一个格，,若存在,a,A,，对于任意,b,A,，,a,b,，,则称,a,为泛下界；,若存在,e,A,，对于任意,b,A,，,b,e,，,则称,e,为泛上界。,显然，泛上界和泛下界若存在必唯一。用,0,和,1,分别表示一个格的泛下界和泛上界。,例,在左图中，,a,是泛下界，,b,是泛上界。,d,c,b,a,e,d,b,a,c,在右图中，,a,是泛下界，,e,是泛上界,。,例,格,(2,A,，,，,),中，,A,是泛上界，而,是泛下界。,A=1,2,3,1,2,1,3,2,3,1,2,3,例,在格,(Z,+,，,| ),中，,1,是泛下界，没有泛上界。,补元、有补格,设,(A,，,),是一个格，,0,，,1 A,。,设,aA,，若存在,bA,，满足,ab=1,，,ab=0,，,则称,b,为,a,的补元。,一个格，如果每一个元素都有补元，则称它为有补格。,注意，若,a,是,b,的补，那么,b,也是,a,的补。,定理,(,分配格的必要条件,),在分配格中，如果一个元素有补元，那么这个补元是唯一的。,布尔格、补运算,定义：一个有补的分配格也称为布尔格。,设,(A,，,),是一个布尔格，因为对于每一个元素有唯一的补元，能定义,A,上的一个一元运算，并用“,”,表示，称之为补运算。,这样，对于,A,中的每一个元素,a,，,a,是,a,的补元。,布尔代数,(,Boolean Algebra,),定义： 称一个布尔格,(A,，,),所,定义代数系统,(A,，, ),是一个布尔代数。,布尔代数的例子,D=1,2,3,5,6,10,15,30,(D, |),30,6,10,15,2,3,5,1,布尔代数的例子,S=2,1,2,3,(S, ),1,2,3,1,2,1,3,2,3,1,2,3,德,摩根律,(A, ),是一个布尔代数。对于任意的,a,，,bA,，有,ab= ab,ab= ab,第十二章,格与布尔代数,12.1,格定义的代数系统,12.2,格的代数定义,12.3,一些特殊的格,12.4,有限布尔代数的唯一性,12.5,布尔函数和布尔表达式,布尔代数,(,(S),，,，,，,),S,是一个任意的集合，,2,S,是,S,的幂集合，,(2,S,，,),是一个格，且是布尔格，记为布尔代数,(,(S),，,，,，,),。,问题：,是否所有的布尔代数都是这样的形式呢？,当,A,是一个有限集，也就是,(A,，,),是一个有限布尔代数时，这一问题的答案是肯定的。,第十二章,格与布尔代数,12.1,格定义的代数系统,12.2,格的代数定义,12.3,一些特殊的格,12.4,有限布尔代数的唯一性,12.5,布尔函数和布尔表达式,问题,设,(A,，,),是一个布尔代数，,n(1),是一个正整数，,如何表示一个,A,n,到,A,的函数,(,映射,),、也就是,A,上的一个,n,元函数？,例,0,1,上的一个,3,元函数,(a),表,12.1,布尔表达式,(Boolean Expression),定义：设,(A,，,),是一个布尔代数，其上的一个布尔表达式是如下的表达式,：,(1) A,中的每个元素是一个布尔表达式。,(2),任意的一个变元名是一个布尔表达式。,(3),如果,e,1,和,e,2,是两个布尔表达式，那么，,e,1,，,e,1,e,2,，,e,1,e,2,都是布尔表达式。,(4),所有的布尔表达式都是有限次的运用,(1),、,(2),、,(3),所得。,E(x,1,，,x,2,，,，,x,n,),一个含有,n,个不同变元的布尔表达式，通常称为,n,个变元的布尔表达式。,通常用,E(x,1,，,x,2,，,，,x,n,),表达有,n,个变元,x,1,，,，,x,n,的一个布尔表达式。,E(x,1,，,x,2,，,，,x,n,),n,元函数,不难看出，一个布尔表达式,E(x,1,，,x,2,，,，,x,n,),就表示了一个从,A,n,到,A,的一个函数。,问题：,n,元函数,E(x,1,，,x,2,，,，,x,n,),？,是否从,A,n,到,A,的每一个函数,f,都可以用,(A,，,),上的一个布尔表达式来表示？,问题的答案是否定的,!,例,0,1,2,3,上的,一个,2,元函数。,函数,f,就不存在,布尔表达式。,布尔函数,(Boolean Function),定义,(A,，,),是一个布尔代数。从,A,n,到,A,的一个函数，如果它能由（,n,个变元的）的布尔表达式来表示，则称它为布尔函数。,二元素布尔代数,(0,1,，,),上的一个任意,n,元函数，都是布尔函数。,