格与布尔代数学习培训模板课件.ppt

1、1山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11第第1515章章 格与布尔代数格与布尔代数集合的表示方法集合的表示方法2子格与格同态子格与格同态3特殊格特殊格4偏序格与代数格偏序格与代数格1格的性质格的性质2布尔代数布尔代数52山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11偏序格偏序格 efabdcabcd(a)(b)比较右边两个哈比较右边两个哈斯图的不同？斯图的不同？3山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.115.2.1设设是一个

2、偏序集，如果对任意是一个偏序集，如果对任意a,bLa,bL，a,ba,b都有最大下界和最小上界存在，则称都有最大下界和最小上界存在，则称L,是是格格，简称，简称L L是是格格。若。若L L为有限集，则称格为有限集，则称格L,为为有限格有限格。暂且把由偏序关系定义的格称为暂且把由偏序关系定义的格称为偏序格偏序格4山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11保交与保联保交与保联在格在格中，任取中，任取a,bGa,bG，则，则a,ba,b的最大的最大下界和最小上界都是惟一存在的，且均属于下界和最小上界都是惟一存在的，且均属于L L。用用a a*b b表

3、示表示a,ba,b的最大下界，称为的最大下界，称为a a与与b b的的保交保交，用用a a b b表示表示a,ba,b的最小上界，称为的最小上界，称为a a与与b b的的保联保联，即即a a*b=GLBa,bb=GLBa,b，a a b=LUBa,bb=LUBa,b也可用也可用和和、和、和、和和分别表示保交和保分别表示保交和保联联 5山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.115.2.1（1 1）考虑偏序集）考虑偏序集Z,D，其中，其中Z Z+是正整数，是正整数，D D是是一个整除关系，问此偏序集一个整除关系，问此偏序集Z,D是

4、否是一个格？是否是一个格？（2 2）设）设A A是一个集合，是一个集合，P(A)P(A)是是A A的幂集，是集合上的幂集，是集合上的包含关系，问此偏序集的包含关系，问此偏序集是否是一个格？是否是一个格？（3 3）考虑偏序集）考虑偏序集S,D，其中，其中D D是一个整除关系，是一个整除关系，S Sn n是是n n的所有因子的集合，问此偏序集的所有因子的集合，问此偏序集S,D是否是否是一个格？是一个格？（4 4）所有的全序集）所有的全序集都是格？都是格？6山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.115.2.1（续）（续）分析分析 判

5、断一个偏序集判断一个偏序集是否是格，要对是否是格，要对L L的的所有所有2 2元素子集看它是否都有最大下界和最小上界元素子集看它是否都有最大下界和最小上界解解 （1 1）对）对a,ba,bZ Z，有，有a a*b=GLBa,b=GCDa,bb=GLBa,b=GCDa,bZ ZGCDGCD表示表示a,ba,b的最大公因子的最大公因子(greatest common(greatest common divisor)divisor)。a a b=LUBa,b=LCMa,bb=LUBa,b=LCMa,bZ ZLCMLCM表示表示a,ba,b的最小公倍数的最小公倍数(lease common(lease

6、 common multiple)multiple)。所以，所以，Z,D是一个格。是一个格。7山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.1 15.2.1 解（续）解（续）（2 2）对）对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),是一个格。是一个格。（3 3）由）由(1)(1)可知：可知：S,

7、D一定是一个格。一定是一个格。举例如下：举例如下：当当n=6n=6和和n=24n=24时，有时，有S,D和和S,D是格。是格。此时此时S S6 6=1,2,3,6=1,2,3,6，S S2424=1,2,3,4,6,8,12,24=1,2,3,4,6,8,12,24，8山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.1 15.2.1 解（续）解（续）对对a,ba,bS S6 6(或或S S2424)，有，有a a*b=GLBa,bb=GLBa,b=GCDa,b=GCDa,bS S6 6(或或S S2424)a a b=LUBa,b b=

8、LUBa,b=LCMa,b=LCMa,bS S6 6(或或S S2424)对应的对应的HasseHasse图如图图如图(a)(a)和图和图(b)(b)所示。所示。61232412123684(a)(b)9山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.1 15.2.1 解（续）解（续）（4 4）因为在全序集）因为在全序集中，对任意中，对任意a,ba,bL L，都有都有a ba b或或b ab a成立。成立。若若a ba b成立，则成立，则a,ba,b有最大下界为有最大下界为a a，最小上，最小上界为界为b b；若若b ab a成立，则成

9、立，则a,ba,b有最大下界为有最大下界为b b，最小上，最小上界为界为a a；故故是一个格。是一个格。10山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.215.2.2判断哈斯图如下图所示的几个偏序集是否是格。判断哈斯图如下图所示的几个偏序集是否是格。(a)abcdefg(a)(b)abcde(c)abcdea(e)bcdea(d)bc deba(f)cefd11山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.215.2.2（续）（续）a(g)bdfhceghadbcf(h)g

10、e(i)abcdeffb(j)baceca(k)bdea(l)bcde12山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.215.2.2（续）（续）分析分析 图图(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元素子元素子集

11、集d,ed,e不存在最大下界，因此它们都不是格。不存在最大下界，因此它们都不是格。解解 图图(a)(a)至至(g)(g)中的偏序集都是格，图中的偏序集都是格，图(h)(h)至至(L)(L)中的偏序集都不是格。中的偏序集都不是格。13山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.215.2.2设设是具有两个二元运算的代数系统，是具有两个二元运算的代数系统，如果运算如果运算和和满足交换律、结合律和吸收律，则满足交换律、结合律和吸收律，则称称为为格格。把由代数系统定义的格称为把由代数系统定义的格称为代数格代数格。14山东农业大学离散数学

12、课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.315.2.3设设A A是一个集合，是一个集合，P(A)P(A)是是A A的幂集，的幂集，和和分别是集分别是集合的交和并运算，试证明代数系统合的交和并运算，试证明代数系统是一个格。是一个格。证明证明 由集合的运算性质知，交和并运算都满足交由集合的运算性质知，交和并运算都满足交换律、结合律和吸收律，因此由定义换律、结合律和吸收律，因此由定义15.2.215.2.2知，知，是一个格。是一个格。15山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.115.

13、2.1偏序格与代数格是等价的。偏序格与代数格是等价的。证明（略）证明（略）P449P449注意注意：偏序格与代数格等价，今后就不再区分偏：偏序格与代数格等价，今后就不再区分偏序格与代数格了，而把它们统称为格。序格与代数格了，而把它们统称为格。16山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11自然运算与自然偏序自然运算与自然偏序任何偏序格任何偏序格都存在两个二元运算都存在两个二元运算保交保交(*)和保联和保联()，称之为格，称之为格的的自然运算自然运算；代数格代数格都可以得到一个偏序关系都可以得到一个偏序关系 ，称之为格称之为格的的自然偏序自然偏序。

14、17山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11对偶格对偶格对于集合对于集合L L的任何偏序关系的任何偏序关系“”，其逆关系，其逆关系“”也是集合也是集合L L上的偏序关系；上的偏序关系；对对L L的任意子集的任意子集T T，T T在偏序集在偏序集中的最大下中的最大下界和最小上界分别是界和最小上界分别是中的最小上界和最大中的最小上界和最大下界。下界。因此偏序集因此偏序集是格当且仅当是格当且仅当是格，是格，我们称此两个格为我们称此两个格为对偶格对偶格；格格的保联运算与保交运算分别是对偶格的保联运算与保交运算分别是对偶格L,的保交运算和保联运算。的保

15、交运算和保联运算。18山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11对偶原理对偶原理对于格对于格的任何命题，将保联运算与保交运的任何命题，将保联运算与保交运算分别换成对偶格算分别换成对偶格的保交运算和保联运算，的保交运算和保联运算，将命题中的将命题中的“”换成对偶格换成对偶格中的中的“”，得到的一个关于对偶格，得到的一个关于对偶格中的命题，中的命题，称这个命题为称这个命题为对偶命题对偶命题。容易证明，关于格容易证明，关于格的任何真命题，其对应的任何真命题，其对应的对偶命题在对偶格的对偶命题在对偶格中也是真命题，把这中也是真命题，把这个原理称为个原理

16、称为对偶原理对偶原理。19山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11性质性质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；abab且且bc acbc ac（4 4）a a*b ab a；a a baba（5 5）c ac a且且c

17、 b c b c a c a*b b；ca ca且且cb cacb ca b b20山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11性质性质15.2.115.2.1（续）（续）（6 6）交换律交换律：a a*b=bb=b*a a；a a b=bb=b a a。（7 7）结合律结合律：(a(a*b)b)*c=ac=a*(b(b*c)c)；(a(a b)b)c=ac=a (b(b c)c)（8 8）吸收律：吸收律：a a*(a(a b)=ab)=a；a a (a(a*b)=ab)=a（9 9）幂等律：幂等律：a a*a=aa=a；a a a=aa=a（1

18、010）a b a b a a*b=a b=a a a b=bb=b21山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11性质性质15.2.115.2.1（续）（续）（1111）a ba b且且c dc da a*c bc b*d d；a b a b且且c d c d a a c bc b d d（1212）保序性：保序性：a b a b a a*c bc b*c c；a b a b a a c bc b c c（1313）分配不等式分配不等式：a a (b(b*c)(ac)(a b)b)*(a(a c)c)；a a*(b(b c)(ac)(a*b)b

19、)(a(a*c)c)（1414）模不等式模不等式：a c a c a a (b(b*c)(ac)(a b)b)*c c22山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义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的的子格。子格。23山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2

20、.415.2.4在正整数集合在正整数集合Z Z+中规定中规定、为：对任意为：对任意a,bPa,bP，a a b=a,bb=a,b，其中，其中a,ba,b表示表示a,ba,b的最小公倍数的最小公倍数a a b=(a,b)b=(a,b)，其中，其中(a,b)(a,b)表示表示a,ba,b的最大公因数的最大公因数则则,是是Z Z+上的二元运算，且满足交换律、结合律、上的二元运算，且满足交换律、结合律、吸收律和等幂律，于是吸收律和等幂律，于是Z 是一个格。是一个格。S=S=3k|kZ3k|kZ+ZZ+，试证明，试证明S,是是Z 的的子格。子格。24山东农业大学离散数学课程组山东农业大学离散数学课程组2

21、022-11-112022-11-11例例15.2.4 15.2.4 证明证明显然显然SS。因为对任意。因为对任意3m,3nS3m,3nS，都有，都有3m3m 3n=3m,3n=3m,nS3n=3m,3n=3m,nS，3m3m 3n=(3m,3n)=3(m,n)S3n=(3m,3n)=3(m,n)S所以，所以，S,是是Z+,的子格。的子格。25山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11子格子格定义定义15.2.4 15.2.4 设设是一个格，是一个格，S S L L，若，若S S满足：满足：（1 1）SS；（2 2）对任意）对任意a,bSa,b

22、S，的保交和保联运的保交和保联运算都有算都有a a b=GLBa,bSb=GLBa,bS，a a b=LUBa,bSb=LUBa,bS，则称则称是是的一个的一个子格子格，简称，简称S S是是L L的的子格。子格。26山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.515.2.5在如下图在如下图(a)(a)所示的偏序格所示的偏序格中，考虑如下中，考虑如下子集：子集：B B1 1=a,b,g,h=a,b,g,h，B B2 2=a,b,c,d=a,b,c,d，B B3 3=a,b,c,h =a,b,c,h，问，问B B1 1，B B2 2，B

23、 B3 3中那些是中那些是L,的子格？的子格？habca(a)bdfhceg(b)27山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.515.2.5（续）（续）分析分析 显然显然B B1 1，B B2 2，B B3 3都是都是L L的非空子集，的非空子集，B B1 1是是L L的的子格；子格；B B2 2的的2 2元素子集元素子集b,cb,c的最小上界的最小上界e e不在不在B B2 2中，中，因此因此B B2 2不是不是L L的子格；的子格；B B3 3的的2 2元素子集元素子集b,cb,c的最小的最小上界上界e e不在不在B B3

24、3中，因此中，因此B B3 3不是不是L L的子格。的子格。注意注意，偏序集，偏序集B,的哈斯图如上图的哈斯图如上图(b)(b)所示，所示，因此因此B,是格。即存在子集关于偏序能构成是格。即存在子集关于偏序能构成格，但不是子格，主要原因是它们的保交或保联运格，但不是子格，主要原因是它们的保交或保联运算不一样。算不一样。解解 B B1 1是是L L的子格，的子格，B B2 2,B,B3 3,都不是都不是L L的子格。的子格。28山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.515.2.5设设和和S,是两个格，是两个格，f f是是L

25、L到到S S的的映射。如果对任意映射。如果对任意x,yLx,yL，都有，都有f(xy)=f(x)f(xy)=f(x)*f(y)f(y)，f(xy)=f(x)f(xy)=f(x)f(y)f(y)则称则称f f为从格为从格到格到格S,的的格同态格同态映射映射，简称，简称格同态格同态。如果如果f f是格同态，当是格同态，当f f分别是单射、满射和双射时，分别是单射、满射和双射时，f f分别称为分别称为单一格同态、满格同态和格同构单一格同态、满格同态和格同构。29山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.3(15.2.3(保序定理保序

26、定理)设设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)。证明证明 （略）（略）30山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.615.2.6设

27、设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,是一个是一个分配格分配格。31山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.715.2.7（1 1）设）设A A为任意一个集合，格为任意一个集合，格是是否是分配格？否是分配格？（2 2）设）设P P为命题公式集合，为命题公式集合，与与分别是命题公式分别是命题公式的合取与析取运算

28、，格的合取与析取运算，格是否是分配格？是否是分配格？解解 （1 1）因集合的交、并运算满足分配律，所以，）因集合的交、并运算满足分配律，所以，格格是一个分配格。是一个分配格。（2 2）因命题公式的析取、合取运算满足分配律，）因命题公式的析取、合取运算满足分配律，所以，格所以，格是分配格。是分配格。32山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.415.2.4所有链都是分配格。所有链都是分配格。证明证明 设设是链，因此是链，因此是格，任取是格，任取a,b,cLa,b,cL，只有以下两种情况：，只有以下两种情况：（1 1）a a是三

29、者中最大的，即是三者中最大的，即b ab a，c ac a；（2 2）a a不是三者中最大的，即不是三者中最大的，即a ba b或或a ca c。在情况在情况(1)(1)中，中，b b c ac a，故，故a a (b(b c)=bc)=b c c。显然，显然，a a b=bb=b，a a c=cc=c。所以。所以a a (b(b c)=bc)=b c=(ac=(a b)b)(a(a c)c)。33山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.415.2.4（续）（续）在情况在情况(2)(2)中，中，a ba b c c，而，而a

30、 a b=ab=a或或a a c=ac=a，从而从而(a(a b)b)(a(a c)=ac)=a，所以，所以(a(a b)b)(a(a c)=a=ac)=a=a (b(b c)c)所以所以是分配格。是分配格。34山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.815.2.8右图所示的两个格都不右图所示的两个格都不是分配格。是分配格。分析分析 由于链是分配格，由于链是分配格，因此在同一条链上的元因此在同一条链上的元素都满足分配等式，最素都满足分配等式，最有可能不满足分配等式有可能不满足分配等式的元素不在同一条链上。的元素不在同一条链上。选

31、取选取b,c,db,c,d来验证即可。来验证即可。e(b)bdcae(a)bcda35山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例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)中，中，c c (b(b d)=cd)=c a=c a=c，而，而(c(c b)b)(c(c d)=ed)=e d=dd=d。故它们都不是分配格。故它们

32、都不是分配格。e(b)bdcae(a)bcda36山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.515.2.5一个格是分配格的充分必要条件是该格中没有任何一个格是分配格的充分必要条件是该格中没有任何子格与图子格与图15.2.715.2.7（例（例15.2.815.2.8）中的两个五元素格中）中的两个五元素格中的任何一个同构。的任何一个同构。37山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11性质性质15.2.215.2.2（1 1）四个元素以下的格）四个元素以下的格都是分配格；都是分配格

33、；（2 2）五个元素的格仅有）五个元素的格仅有两个格是非分配格两个格是非分配格(图图15.2.7(a)15.2.7(a)和和(b)(b)，其余，其余三个格三个格(右图右图(a),(b)(a),(b)和和(c)(c)都是分配格。都是分配格。(a)(a)abcde(b)abcde(c)abcde38山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理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。证明证明 x=xx

34、=x (a(a x)x)(吸收律吸收律)=x=x (a(a y)y)(已知已知a a x=ax=a y)y)=(x=(x a)a)(x(x y)y)(分配律分配律)=(a=(a y)y)(x(x y)y)(交换律，已知交换律，已知a a x=ax=a y)y)=y=y (a(a x)x)(交换律，分配律交换律，分配律)=y=y (a(a y)y)(已知已知a a x=ax=a y)y)=y=y(吸收律吸收律)39山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.815.2.8设设是一个格，若存在元素是一个格，若存在元素aLaL，使得对

35、任，使得对任意意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=x40山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11有限格与有界格有限格与有界格若若是有限格，设是有限格，设L=aL=a1 1,a,a2 2,a,an n，由于运算由于运算“”和和“”满足结合律

36、，所以有满足结合律，所以有(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所以，所以，有限格一定是有界格有限格一定是有界格。41山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11

37、-11定理定理15.2.815.2.8在格在格中，全下界和全上界分别是集合中，全下界和全上界分别是集合L L的的最小元和最大元，由于最大元和最小元的惟一性，最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：有下面的定理：定理定理15.2.815.2.8 设设是一个格，若格是一个格，若格L,的全上界和全下界存在，则必惟一。的全上界和全下界存在，则必惟一。42山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.915.2.9设设L,为有界格，为有界格，1 1和和0 0分别为它的全上界和全分别为它的全上界和全下界，下界，aLaL。如果

38、存在。如果存在bLbL，使得，使得a a b=0b=0，a a b=1b=1，则称则称b b为为a a的的补元补元，记为，记为aa。若有界格。若有界格L,中的中的所有元素都存在补元，则称所有元素都存在补元，则称L,为为有补格有补格。43山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.915.2.9如下图有界格，求其所有元素的补元如下图有界格，求其所有元素的补元(如果有的话如果有的话)。a0(b)bd1c0(a)abd1ce44山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11例例15.2.915

39、.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是有补格。是有补格。a0(b)bd1c0(a)abd1ce45山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.915.2.9在有界分配格在有界分配格(既是有界格又是分配

40、格，简称为有既是有界格又是分配格，简称为有界分配格界分配格)L,)中，如元素中，如元素aLaL有补元存在，有补元存在，则此元素的补元必惟一。则此元素的补元必惟一。证明证明 设设a a有两个补元有两个补元b b和和c c，由补元的定义知，由补元的定义知a a b=0=ab=0=a c c，a a b=1=ab=1=a c c由定理由定理15.2.615.2.6知，知，b=cb=c。推论推论15.2.115.2.1 在有补分配格在有补分配格(既是有补格又是分配既是有补格又是分配格，简称为有补分配格格，简称为有补分配格)L,)中，每个元素中，每个元素都存在惟一的补元。都存在惟一的补元。46山东农业大

41、学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理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。47山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11

42、-112022-11-11定理定理15.2.1015.2.10（续）（续）证明证明 （1 1）因）因aa是是a a的补元，反过来，的补元，反过来，a a也是也是aa的的补元，由推论补元，由推论15.2.115.2.1得，得，(a)=a(a)=a。（2 2）因为）因为(a(a b)b)(a(a b)b)=(a=(a b)b)a)a)(a(a b)b)b)b)(分配律分配律)=(a=(a a)a)b)b)(a(a (b(b b)(b)(交换律，结合律交换律，结合律)=(0=(0 b)b)(a(a 0)0)=0=0 0=00=048山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-

43、112022-11-11定理定理15.2.1015.2.10（续）（续）(a(a b)b)(a(a b)b)=(a=(a (a(a b)b)*(b(b (a(a b)(b)(分配律分配律)=(a=(a a)a)b)b)*(a(a (b(b b)(b)(交换律，结合律交换律，结合律)=(1=(1 b)b)(a(a 1)1)=1=1 1=11=1所以，所以，aa bb是是a a b b的补元，由补元的惟一性得，的补元，由补元的惟一性得，(a(a b)b)=a=a b b。同理可证，同理可证，(a(a b)=ab)=a bb。49山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-1

44、12022-11-11定理定理15.2.1015.2.10（续）（续）（3 3）“”，由，由a ba b，可得，可得a a b=ab=a，则有，则有(a(a b)=ab)=a由由De MorganDe Morgan律律(即即(2)(2)，有，有a a b b=a =a，即是，即是b ab a“”，上述过程可逆，故成立。，上述过程可逆，故成立。（4 4）“”由由a ba b，根据，根据(3)(3)，有，有b b a a则则a a b ab a a=0a=0，即是，即是50山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.1015.2.1

45、0（续）（续）a a b 0b 0，又又0 0是全下界，有是全下界，有0 a0 a bb则根据偏序关系则根据偏序关系“”的反对称性，有的反对称性，有a a b=0b=0，对上式使用对上式使用De MorganDe Morgan律，自然有律，自然有aa b=1b=151山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定理定理15.2.1015.2.10（续）（续）“”如果如果aa b=1b=1，由，由De MorganDe Morgan律，有律，有a a b=0b=0，则有，则有aa(a(a b)=ab)=a 0=a0=a对上式的左边使用分配律，可得对

46、上式的左边使用分配律，可得aa(a(a b)=(ab)=(a a)a)(a(a b)b)=1 =1 (a(a b)=ab)=a bb即是即是 a a b b=a=a，所以有，所以有 b b a a，由，由(3)(3)可得可得a ba b。52山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.3.115.3.1称有补分配格称有补分配格L,为为布尔格布尔格。在有补分配格中每个元都有补元而且补元惟一，可在有补分配格中每个元都有补元而且补元惟一，可以将求元素的补元作为一种一元运算，则此布尔格以将求元素的补元作为一种一元运算，则此布尔格L,可记为可

47、记为L,0,1，此时，此时，称称L,0,1为布尔代数。因此有：为布尔代数。因此有：定义定义15.3.215.3.2 一个布尔格一个布尔格L,称为称为布尔代数布尔代数。若一个布尔代数的元素个数是有限的，则称此布尔若一个布尔代数的元素个数是有限的，则称此布尔代数为代数为有限布尔代数有限布尔代数，否则称为，否则称为无限布尔代数无限布尔代数。53山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11布尔代数布尔代数布尔代数是有补分配格，有补分配格布尔代数是有补分配格，有补分配格L 必必须满足它是须满足它是格格、有、有全上界全上界和和全下界全下界、分配律分配律成立、

48、成立、每个元素都有每个元素都有补元存在补元存在。显然，全上界。显然，全上界1 1和全下界和全下界0 0可以用下面的同一律来描述：可以用下面的同一律来描述：同一律同一律：在在L L中存在两个元素中存在两个元素0 0和和1 1，使得对任意，使得对任意aLaL，有，有a a 1=a1=a，a a 0=a0=a。54山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11布尔代数布尔代数补元的存在可以用下面的互补律来描述。补元的存在可以用下面的互补律来描述。互补律互补律：对任意：对任意aLaL，存在，存在a aLL，使得，使得a a a a=0=0，a a a a=

49、1=1。格可以用交换律、结合律、吸收律来描述。格可以用交换律、结合律、吸收律来描述。因此，一个有补分配格就必须满足交换律、结合律、因此，一个有补分配格就必须满足交换律、结合律、吸收律、分配律、同一律、互补律。吸收律、分配律、同一律、互补律。另外，可以证明，由交换律、分配律、同一律、互另外，可以证明，由交换律、分配律、同一律、互补律可以得到结合律、吸收律。所以布尔代数有下补律可以得到结合律、吸收律。所以布尔代数有下面的面的等价定义等价定义：55山东农业大学离散数学课程组山东农业大学离散数学课程组2022-11-112022-11-11定义定义15.2.315.2.3设设B,是代数系统，其中是代数

50、系统，其中、是是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