第15章-格与布尔代数课件

12024/7/27第第1515章章 格与布尔代数格与布尔代数集合的表示方法集合的表示方法2子格与格同态子格与格同态3偏序格与代数格偏序格与代数格1格的性质格的性质2布尔代数布尔代数42023/8/172023/8/17第第1515章章 格与布尔代数集合的表示方法格与布尔代数集合的表示方法2 2子格子格22024/7/27偏序格偏序格 efabdcabcd(a)(b)比较右边两个哈比较右边两个哈斯图的不同？斯图的不同？2023/8/172023/8/17偏序格偏序格 efabdcabcd(a)(b)efabdcabcd(a)(b)比比32024/7/27定义定义15.2.115.2.1设设是一个偏序集，如果对任意是一个偏序集，如果对任意a,bLa,bL，a,ba,b都有最大下界和最小上界存在，则称都有最大下界和最小上界存在，则称L,是是格格，简称，简称L L是是格格。若。若L L为有限集，则称格为有限集，则称格L,为为有限格有限格。暂且把由偏序关系定义的格称为暂且把由偏序关系定义的格称为偏序格偏序格2023/8/172023/8/17定义定义15.2.115.2.1设设是一个偏序是一个偏序42024/7/27保交与保联保交与保联在格在格中，任取中，任取a,bGa,bG，则，则a,ba,b的最大的最大下界和最小上界都是惟一存在的，且均属于下界和最小上界都是惟一存在的，且均属于L L。用用a*ba*b表示表示a,ba,b的最大下界，称为的最大下界，称为a a与与b b的的保交保交，用用a a b b表示表示a,ba,b的最小上界，称为的最小上界，称为a a与与b b的的保联保联，即即a*b=GLBa,ba*b=GLBa,b，a a b=LUBa,bb=LUBa,b也可用也可用和和、和、和、和和分别表示保交和保分别表示保交和保联联 2023/8/172023/8/17保交与保联在格保交与保联在格中，任取中，任取a,a,52024/7/27例例15.2.115.2.1（1 1）考虑偏序集）考虑偏序集Z,D，其中，其中Z Z+是正整数，是正整数，D D是整是整除关系，问此偏序集除关系，问此偏序集Z,D是否是一个格？是否是一个格？分析分析 判断一个偏序集判断一个偏序集是否是格，要对是否是格，要对L L的的所有所有2 2元素子集看它是否都有最大下界和最小上界元素子集看它是否都有最大下界和最小上界解解 对对a,ba,bZ Z，有，有a*b=GLBa,b=GCDa,a*b=GLBa,b=GCDa,bbZ Za a b=LUBa,b=LCMa,bb=LUBa,b=LCMa,bZ ZLCMLCM表示表示a,ba,b的最小公倍数。的最小公倍数。所以，所以，Z,D是一个格。是一个格。2023/8/172023/8/17例例15.2.115.2.1（1 1）考虑偏序集）考虑偏序集Z+,DZ+,D62024/7/27例例15.2.1 15.2.1（续）（续）（2 2）设）设A A是一个集合，是一个集合，P(A)P(A)是是A A的幂集，是集合上的幂集，是集合上的包含关系，问此偏序集的包含关系，问此偏序集是否是一个格？是否是一个格？解解:对对S S1 1，S S2 2P(S)P(S)，有，有S S1 1*S S2 2=GLBS=GLBS1 1,S,S2 2=S=S1 1SS2 2P(S)P(S)S S1 1 S S2 2=LUBS=LUBS1 1,S,S2 2=S=S1 1S S2 2P(S)P(S)所以，所以，P(S),是一个格。是一个格。2023/8/172023/8/17例例15.2.1 15.2.1（续）（续）（2 2）设）设A A是一个集合是一个集合72024/7/27例例15.2.215.2.2判断哈斯图如下图所示的几个偏序集是否是格。判断哈斯图如下图所示的几个偏序集是否是格。(a)abcdefg(a)(b)abcde(c)abcdea(e)bcdea(d)bc deba(f)cefd2023/8/172023/8/17例例15.2.215.2.2判断哈斯图如下图所示的几个偏判断哈斯图如下图所示的几个偏82024/7/27例例15.2.215.2.2（续）（续）hadbcf(h)ge(i)abcdeffb(j)baceca(k)bdea(l)bcde(h)(h)中中2 2元素子集元素子集g,hg,h不存在最小上界，不存在最小上界，(i)(i)中中2 2元素子集元素子集e,fe,f不存在最小上界不存在最小上界(j)(j)中中2 2元素子集元素子集e,fe,f不存在最小上界，不存在最小上界，(k)(k)中中2 2元素子集元素子集a,ba,b不存在最大下界，不存在最大下界，(l)(l)中中2 2元素子集元素子集d,ed,e不存在最大下界。不存在最大下界。2023/8/172023/8/17例例15.2.215.2.2（续）（续）hadbcf(h)gehadbcf(h)ge92024/7/27定义定义15.2.215.2.2设设是具有两个二元运算的代数系统，是具有两个二元运算的代数系统，如果运算如果运算和和满足交换律、结合律和吸收律，则满足交换律、结合律和吸收律，则称称为为格格。把由代数系统定义的格称为把由代数系统定义的格称为代数格代数格。2023/8/172023/8/17定义定义15.2.215.2.2设设是具有是具有102024/7/27例例15.2.315.2.3设设A A是一个集合，是一个集合，P(A)P(A)是是A A的幂集，的幂集，和和分别是集分别是集合的交和并运算，试证明代数系统合的交和并运算，试证明代数系统是一个格。是一个格。证明证明 由集合的运算性质知，交和并运算都满足交由集合的运算性质知，交和并运算都满足交换律、结合律和吸收律，因此由定义换律、结合律和吸收律，因此由定义15.2.215.2.2知，知，是一个格。是一个格。2023/8/172023/8/17例例15.2.315.2.3设设A A是一个集合，是一个集合，P(A)P(A)是是A A112024/7/27定理定理15.2.115.2.1偏序格与代数格是等价的。偏序格与代数格是等价的。注意注意：偏序格与代数格等价，今后就不再区分偏：偏序格与代数格等价，今后就不再区分偏序格与代数格了，而把它们统称为格。序格与代数格了，而把它们统称为格。2023/8/172023/8/17定理定理15.2.115.2.1偏序格与代数格是等价的。注偏序格与代数格是等价的。注122024/7/27自然运算与自然偏序自然运算与自然偏序任何偏序格任何偏序格都存在两个二元运算都存在两个二元运算保交保交(*)(*)和保联和保联()，称之为格，称之为格的的自然运算自然运算；代数格代数格都可以得到一个偏序关系都可以得到一个偏序关系 ，称之为格，称之为格的的自然偏序自然偏序。2023/8/172023/8/17自然运算与自然偏序任何偏序格自然运算与自然偏序任何偏序格132024/7/27对偶格对偶格对于集合对于集合L L的任何偏序关系的任何偏序关系“”，其逆关系，其逆关系“”也是集合也是集合L L上的偏序关系；上的偏序关系；对对L L的任意子集的任意子集T T，T T在偏序集在偏序集中的最大下中的最大下界和最小上界分别是界和最小上界分别是中的最小上界和最大中的最小上界和最大下界。下界。因此偏序集因此偏序集是格当且仅当是格当且仅当是格，是格，我们称此两个格为我们称此两个格为对偶格对偶格；格格的保联运算与保交运算分别是对偶格的保联运算与保交运算分别是对偶格的保交运算和保联运算。的保交运算和保联运算。2023/8/172023/8/17对偶格对于集合对偶格对于集合L L的任何偏序关系的任何偏序关系“”“”，142024/7/27对偶原理对偶原理对于格对于格的任何命题，将保联运算与保交运的任何命题，将保联运算与保交运算分别换成对偶格算分别换成对偶格的保交运算和保联运算，的保交运算和保联运算，将命题中的将命题中的“”换成对偶格换成对偶格中的中的“”，得到的一个关于对偶格，得到的一个关于对偶格中的命题，中的命题，称这个命题为称这个命题为对偶命题对偶命题。容易证明，关于格容易证明，关于格的任何真命题，其对应的任何真命题，其对应的对偶命题在对偶格的对偶命题在对偶格中也是真命题，把这中也是真命题，把这个原理称为个原理称为对偶原理对偶原理。2023/8/172023/8/17对偶原理对于格对偶原理对于格的任何命题，将的任何命题，将152024/7/27性质性质15.2.115.2.1设设是格，是格，“”是是“”的逆关系。则对的逆关系。则对任意任意a,b,c,dLa,b,c,dL，有，有（1 1）自反性：自反性：a aa a；aaaa（2 2）反对称性：反对称性：a ba b且且b ab aa=b a=b ab ab且且ba ba a=b a=b （3 3）传递性：传递性：a ba b且且b c b c a c a c；a b a b且且b c b c a c a c（4 4）a*b aa*b a；a a baba（5 5）c ac a且且c b c b c a*b c a*b；c a c a且且c b c b c a c a b b2023/8/172023/8/17性质性质15.2.115.2.1设设是格，是格，“162024/7/27性质性质15.2.115.2.1（续）（续）（6 6）交换律交换律：a*b=b*aa*b=b*a；a a b=bb=b a a。（7 7）结合律结合律：(a*b)*c=a*(b*c)(a*b)*c=a*(b*c)；(a(a b)b)c=ac=a (b(b c)c)（8 8）吸收律：吸收律：a*(aa*(a b)=ab)=a；a a (a*b)=a(a*b)=a（9 9）幂等律：幂等律：a*a=aa*a=a；a a a=aa=a（1010）a b a b a*b=a a*b=a a a b=bb=b2023/8/172023/8/17性质性质15.2.115.2.1（续）（续）（6 6）交换律：）交换律：a*b a*b172024/7/27性质性质15.2.115.2.1（续）（续）（1111）a ba b且且c dc da*c b*da*c b*d；a b a b且且c dac da c bc b d d（1212）保序性：保序性：a b a b a*c b*c a*c b*c；a b a b a a c bc b c c（1313）分配不等式分配不等式：a a (b*c)(a(b*c)(a b)*(ab)*(a c)c)；a*(b a*(b c)(a*b)c)(a*b)(a*c)(a*c)（1414）模不等式模不等式：a c a c a a (b*c)(a(b*c)(a b)*cb)*c2023/8/172023/8/17性质性质15.2.115.2.1（续）（续）（1111）a ba b且且182024/7/27定义定义15.2.315.2.3设代数系统设代数系统L,是一个格，是一个格，S S L L，若，若S S满足：满足：（1 1）SS；（2 2）运算）运算 和和 对子集对子集S S都是封闭的；都是封闭的；则称则称S,是是L,的的子格子格，简称，简称S S是是L L的的子格。子格。2023/8/172023/8/17定义定义15.2.315.2.3设代数系统设代数系统L,L,192024/7/27子格子格定义定义15.2.4 15.2.4 设设是一个格，是一个格，S S L L，若，若S S满足：满足：（1 1）SS；（2 2）对任意）对任意a,bSa,bS，的保交和保联运的保交和保联运算都有算都有a a b=GLBa,bSb=GLBa,bS，a a b=LUBa,bSb=LUBa,bS，则称则称是是的一个的一个子格子格，简称，简称S S是是L L的的子格。子格。2023/8/172023/8/17子格定义子格定义15.2.4 15.2.4 设设是一个格是一个格202024/7/27定义定义15.2.515.2.5设设和和S,*,是两个格，是两个格，f f是是L L到到S S的的映射。如果对任意映射。如果对任意x,yLx,yL，都有，都有f(xy)=f(x)*f(y)f(xy)=f(x)*f(y)，f(xy)=f(x)f(xy)=f(x)f(y)f(y)则称则称f f为从格为从格到格到格S,*,的的格同态格同态映射映射，简称，简称格同态格同态。如果如果f f是格同态，当是格同态，当f f分别是单射、满射和双射时，分别是单射、满射和双射时，f f分别称为分别称为单一格同态、满格同态和格同构单一格同态、满格同态和格同构。2023/8/172023/8/17定义定义15.2.515.2.5设设和和SS212024/7/27定理定理15.2.3(15.2.3(保序定理保序定理)设设L 和和L 是两个格，对应的偏是两个格，对应的偏序关系为序关系为 1 1、2 2，则有：，则有：（1 1）如）如f f：L L1 1L L2 2是格同态，则对任意是格同态，则对任意a,ba,bL L1 1，a a 1 1b bf(a)f(a)2 2f(b)f(b)；（2 2）如）如f f：L L1 1L L2 2是格同构，则对任意是格同构，则对任意a,ba,bL L1 1，a a 1 1b b f(a)f(a)2 2f(b)f(b)。2023/8/172023/8/17定理定理15.2.3(15.2.3(保序定理保序定理)设设L1,L1,222024/7/27定义定义15.2.615.2.6设设L,是一个格，如果对任意是一个格，如果对任意a,b,cLa,b,cL，都，都有有a a(b(b c)=(ac)=(a b)b)(a(a c)c)，a a(b(b c)=(ac)=(a b)b)(a(a c)c)，即运算满足分配律，则称即运算满足分配律，则称L,是一个是一个分配格分配格。2023/8/172023/8/17定义定义15.2.615.2.6设设L,是一个是一个232024/7/27例例15.2.715.2.7（1 1）设）设A A为任意一个集合，格为任意一个集合，格是是否是分配格？否是分配格？（2 2）设）设P P为命题公式集合，为命题公式集合，与与分别是命题公式分别是命题公式的合取与析取运算，格的合取与析取运算，格是否是分配格是否是分配格？解解 （1 1）因集合的交、并运算满足分配律，所以，）因集合的交、并运算满足分配律，所以，格格是一个分配格。是一个分配格。（2 2）因命题公式的析取、合取运算满足分配律，）因命题公式的析取、合取运算满足分配律，所以，格所以，格是分配格。是分配格。2023/8/172023/8/17例例15.2.715.2.7（1 1）设）设A A为任意一个集合，格为任意一个集合，格242024/7/27例例15.2.815.2.8右图所示的两个格都不右图所示的两个格都不是分配格。是分配格。分析分析 由于链是分配格，由于链是分配格，因此在同一条链上的元因此在同一条链上的元素都满足分配等式，最素都满足分配等式，最有可能不满足分配等式有可能不满足分配等式的元素不在同一条链上。的元素不在同一条链上。选取选取b,c,db,c,d来验证即可。来验证即可。a(b)bcdea(a)bcde2023/8/172023/8/17例例15.2.815.2.8右图所示的两个格都不是分配格右图所示的两个格都不是分配格252024/7/27例例15.2.815.2.8（续）（续）解解 取图中取图中b,c,db,c,d三个元素验证。在图三个元素验证。在图(a)(a)中，中，b b (c(c d)=bd)=b a=ba=b，而，而(b(b c)c)(b(b d)=ed)=e e=ee=e。在图在图(b)(b)中，中，b b (c(c d)=bd)=b a=ba=b，而，而(b(b c)c)(b(b d)=ed)=e d=dd=d。因此，在图因此，在图(a)(a)和和(b)(b)中都有，中都有，b b (c(c d)(bd)(b c)c)(b(b d)d)故它们都不是分配格。故它们都不是分配格。2023/8/172023/8/17例例15.2.815.2.8（续）解（续）解 取图中取图中b,c,b,c,262024/7/27定理定理15.2.515.2.5一个格是分配格的充分必要条件是该格中没有任何一个格是分配格的充分必要条件是该格中没有任何子格与图子格与图15.2.715.2.7（例（例15.2.815.2.8）中的两个五元素格中）中的两个五元素格中的任何一个同构。的任何一个同构。2023/8/172023/8/17定理定理15.2.515.2.5一个格是分配格的充分必要条一个格是分配格的充分必要条272024/7/27性质性质15.2.215.2.2（1 1）四个元素以下的格）四个元素以下的格都是分配格；都是分配格；（2 2）五个元素的格仅有）五个元素的格仅有两个格是非分配格两个格是非分配格(图图15.2.7(a)15.2.7(a)和和(b)(b)，其余，其余三个格三个格(右图右图(a),(b)(a),(b)和和(c)(c)都是分配格。都是分配格。(a)(a)abcde(b)abcde(c)abcde2023/8/172023/8/17性质性质15.2.215.2.2（1 1）四个元素以下的格都是）四个元素以下的格都是282024/7/27定理定理15.2.615.2.6设设L,是分配格，对于任何是分配格，对于任何a,x,yLa,x,yL，如，如果果a a x=ax=a y y且且a a x=ax=a y y，则，则x=yx=y。2023/8/172023/8/17定理定理15.2.615.2.6设设L,是分配是分配292024/7/27定义定义15.2.815.2.8设设是一个格，若存在元素是一个格，若存在元素aLaL，使得对任，使得对任意意xLxL，都有：，都有：a x(a x(或或x a)x a)，则称则称a a为格为格的的全下界全下界(或或全上界全上界)，分别记，分别记为为0(0(或或1)1)，具有全上界和全下界的格称为，具有全上界和全下界的格称为有界格有界格。显然，对任意显然，对任意xLxL，有，有1 x=x 1=x，1 x=x 1=10 x=x 0=0，0 x=x 0=x2023/8/172023/8/17定义定义15.2.815.2.8设设是一个格，是一个格，302024/7/27有限格与有界格有限格与有界格若若是有限格，设是有限格，设L=aL=a1 1,a,a2 2,a,an n，由于运算由于运算“”和和“”满足结合律，所以有满足结合律，所以有(a(a1 1 a a2 2)a an n)=a)=a1 1 a a2 2 a an n(a(a1 1 a a2 2)a an n)=a)=a1 1 a a2 2 a an n此时，此时，a a1 1 a a2 2 a an n和和a a1 1 a a2 2 a an n分别是格分别是格L L的全的全下界和全上界，即有下界和全上界，即有a a1 1 a a2 2 a an n=0=0a a1 1 a a2 2 a an n=1=1所以，所以，有限格一定是有界格有限格一定是有界格。2023/8/172023/8/17有限格与有界格若有限格与有界格若是有限格，设是有限格，设312024/7/27定理定理15.2.815.2.8在格在格中，全下界和全上界分别是集合中，全下界和全上界分别是集合L L的的最小元和最大元，由于最大元和最小元的惟一性，最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：有下面的定理：定理定理15.2.815.2.8 设设是一个格，若格是一个格，若格的全上界和全下界存在，则必惟一。的全上界和全下界存在，则必惟一。2023/8/172023/8/17定理定理15.2.815.2.8在格在格中，全下中，全下322024/7/27定义定义15.2.915.2.9设设L,为有界格，为有界格，1 1和和0 0分别为它的全上界和全分别为它的全上界和全下界，下界，aLaL。如果存在。如果存在bLbL，使得，使得a a b=0b=0，a a b=1b=1，则称则称b b为为a a的的补元补元，记为，记为aa。若有界格。若有界格L,中的中的所有元素都存在补元，则称所有元素都存在补元，则称L,为为有补格有补格。2023/8/172023/8/17定义定义15.2.915.2.9设设L,为有界为有界332024/7/27例例15.2.915.2.9如下图有界格，求其所有元素的补元如下图有界格，求其所有元素的补元(如果有的话如果有的话)。a0(b)bd1c0(a)abd1ce2023/8/172023/8/17例例15.2.915.2.9如下图有界格，求其所有元素的如下图有界格，求其所有元素的342024/7/27例例15.2.915.2.9（续）（续）解解 对于图对于图a 0a 0 =1=1，1 1 =0=0，aa=e e，dd=c c，cc=d d，ee=a a，b b无补元。无补元。对于图对于图b 0b 0 =1=1，1 1 =0=0，aa=d d，aa=c c，bb=d d，bb=c c，cc=a a，cc=b b，dd=a a，dd=b b则图则图a a不是有补格，图不是有补格，图b b是有补格。是有补格。2023/8/172023/8/17例例15.2.915.2.9（续）解（续）解 对于图对于图a a 352024/7/27定理定理15.2.915.2.9在有界分配格在有界分配格(既是有界格又是分配格，简称为有既是有界格又是分配格，简称为有界分配格界分配格)L,)中，如元素中，如元素aLaL有补元存在，有补元存在，则此元素的补元必惟一。则此元素的补元必惟一。推论推论15.2.115.2.1 在有补分配格在有补分配格(既是有补格又是分配既是有补格又是分配格，简称为有补分配格格，简称为有补分配格)L,)中，每个元素中，每个元素都存在惟一的补元。都存在惟一的补元。2023/8/172023/8/17定理定理15.2.915.2.9在有界分配格在有界分配格(既是有界格又既是有界格又362024/7/27定理定理15.2.1015.2.10设设L,是有补分配格，是有补分配格，“”是该格的自是该格的自然偏序，则对任意然偏序，则对任意a,bLa,bL，都有，都有（1 1）(a)=a(a)=a；(对合律对合律)（2 2）(a(a b)=a b)=a b b，(a (a b)=ab)=a bb；(De Morgan(De Morgan律律)（3 3）a b a b b a b a；（4 4）a b a b a a b=0 b=0 a a b=1b=1。2023/8/172023/8/17定理定理15.2.1015.2.10设设L,是有是有372024/7/27定义定义15.3.115.3.1称有补分配格称有补分配格L,为为布尔格布尔格。在有补分配格中每个元都有补元而且补元惟一，可在有补分配格中每个元都有补元而且补元惟一，可以将求元素的补元作为一种一元运算，则此布尔格以将求元素的补元作为一种一元运算，则此布尔格L,可记为可记为L,0,1，此时，称，此时，称L,0,1为布尔代数。因此有：为布尔代数。因此有：定义定义15.3.215.3.2 一个布尔格一个布尔格L,称为称为布尔代数布尔代数。若一个布尔代数的元素个数是有限的，则称此布尔若一个布尔代数的元素个数是有限的，则称此布尔代数为代数为有限布尔代数有限布尔代数，否则称为，否则称为无限布尔代数无限布尔代数。2023/8/172023/8/17定义定义15.3.115.3.1称有补分配格称有补分配格L,L,382024/7/27布尔代数布尔代数布尔代数是有补分配格，有补分配格布尔代数是有补分配格，有补分配格L 必必须满足它是须满足它是格格、有、有全上界全上界和和全下界全下界、分配律分配律成立、成立、每个元素都有每个元素都有补元存在补元存在。显然，全上界。显然，全上界1 1和全下界和全下界0 0可以用下面的同一律来描述：可以用下面的同一律来描述：同一律同一律：在在L L中存在两个元素中存在两个元素0 0和和1 1，使得对任意，使得对任意aLaL，有，有a a 1=a1=a，a a 0=a0=a。2023/8/172023/8/17布尔代数布尔代数是有补分配格，有补分配格布尔代数布尔代数是有补分配格，有补分配格 392024/7/27布尔代数布尔代数补元的存在可以用下面的互补律来描述。补元的存在可以用下面的互补律来描述。互补律互补律：对任意：对任意aLaL，存在，存在a aLL，使得，使得a a a a=0=0，a a a a=1=1。格可以用交换律、结合律、吸收律来描述。格可以用交换律、结合律、吸收律来描述。因此，一个有补分配格就必须满足交换律、结合律、因此，一个有补分配格就必须满足交换律、结合律、吸收律、分配律、同一律、互补律。吸收律、分配律、同一律、互补律。另外，可以证明，由交换律、分配律、同一律、互另外，可以证明，由交换律、分配律、同一律、互补律可以得到结合律、吸收律。所以布尔代数有下补律可以得到结合律、吸收律。所以布尔代数有下面的面的等价定义等价定义：2023/8/172023/8/17布尔代数补元的存在可以用下面的互补律来描述布尔代数补元的存在可以用下面的互补律来描述402024/7/27定义定义15.2.315.2.3设设B,是代数系统，其中是代数系统，其中、是是B B中的二元运算，中的二元运算，如果对任意如果对任意a,b,cBa,b,cB，满足，满足（1 1）交换律交换律：a a b=bb=b a a，a a b=bb=b a a；（2 2）分配律分配律：a a (b(b c)=(ac)=(a b)b)(a(a c)c)，a a (b(b c)=(ac)=(a b)b)(a(a c)c)；（3 3）同一律同一律：在：在B B中存在两个元素中存在两个元素0 0和和1 1，使得对任意，使得对任意aBaB，有，有a a 1=a1=a，a a 0=a0=a；（4 4）互补律互补律：对任意：对任意aBaB，存在，存在a aBB，使得，使得a a a=0a=0，a a a=1a=1。则称则称B,为为布尔代数。布尔代数。2023/8/172023/8/17定义定义15.2.315.2.3设设B,是代数是代数412024/7/27定义定义15.2.315.2.3（续）（续）通常将布尔代数通常将布尔代数B,记为记为B,1。为方便起见，也简称。为方便起见，也简称B B是是布尔代数布尔代数。2023/8/172023/8/17定义定义15.2.315.2.3（续）通常将布尔代数（续）通常将布尔代数B,B,422024/7/27定义定义15.2.415.2.4设设B,0,1是布尔代数，是布尔代数，S S是是B B的非空的非空子集，如果运算子集，如果运算，和和 都对都对S S是封闭的，则称是封闭的，则称S,0,1为为B,0,1的的子布尔代数，简称子布尔代数，简称S S为为B B的的子布尔代数子布尔代数。显然，对任意布尔代数显然，对任意布尔代数B,0,1，子，子集集0,10,1和和B B总能构成总能构成B B的子布尔代数，这两个子布的子布尔代数，这两个子布尔代数称为尔代数称为B,0,1的的平凡子布尔代平凡子布尔代数数。2023/8/172023/8/17定义定义15.2.415.2.4设设B,B,432024/7/27定义定义15.2.515.2.5设设B,0,1和和B是两个布尔代数，是两个布尔代数，f f是是L L到到S S的映射。如果对任意的映射。如果对任意x,yx,yB B1 1，都有，都有f(x*y)=f(x)f(x*y)=f(x)f(y),f(x f(y),f(x y)=f(x)y)=f(x)f(y)f(y)f(x)=f(x),f(0)=,f(1)=f(x)=f(x),f(0)=,f(1)=则称则称f f为从布尔代数为从布尔代数B,0,1到到B,的的布尔同态映射布尔同态映射，简称，简称布尔布尔同态同态。2023/8/172023/8/17定义定义15.2.515.2.5设设B1,*,B1,*,442024/7/27定义定义15.2.515.2.5（续）（续）如果如果f f是格同态，当是格同态，当f f分别是单射、满射和双射时，分别是单射、满射和双射时，f f分别称为单一布尔同态、满布尔同态和布尔同构。分别称为单一布尔同态、满布尔同态和布尔同构。2023/8/172023/8/17定义定义15.2.515.2.5（续）如果（续）如果f f是格同态，当是格同态，当f fThank You!第第15章章-格与布格与布尔尔代数代数课课件件