离散数学教案格与布尔代数.ppt

第第1313章章 格与布尔代数格与布尔代数离散数学离散数学q 2本章内容本章内容13.1 13.1 格的定义与性质格的定义与性质13.2 13.2 子格与格同态子格与格同态13.3 13.3 分配格与有补格分配格与有补格13.4 13.4 布尔代数布尔代数本章总结本章总结作业作业q 313.1 13.1 格的定义与性质格的定义与性质 定义定义13.113.1 设设S, 是偏序集，是偏序集，如果如果 x, ,yS S， x, ,y 都有最小都有最小上界和最大下界上界和最大下界，则称，则称S S关于偏序关于偏序作成一个作成一个格格( (lattice) )说明：说明：由于最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯一性，可以把求 x, ,y 的最的最小上界和最大下界看成小上界和最大下界看成x x与与y y的二元运算的二元运算和和xy：表示表示x x与与y y的最小上界的最小上界xy：表示表示x x和和y y的最大下界的最大下界 本章出现的本章出现的和和符号只代表格中的运算，而不再有其它的符号只代表格中的运算，而不再有其它的含义q 4格的格的实实例例例例13.113.1 设设n n是正整数，是正整数，S Sn n是是n n的正因子的集合。

的正因子的集合D D为为整除关系，整除关系，则则偏序集偏序集 构成格 x,yx,yS Sn n，x xy y是是lcm(x,y)lcm(x,y)，即即x x与与y y的最小公倍数的最小公倍数x xy y是是gcd(x,ygcd(x,y) )，即即x x与与y y的最大公的最大公约约数下下图给图给出了格出了格S,D，S,D和和S,Dq 5例例13.213.2例例13.213.2 判断下列偏序集是否构成格判断下列偏序集是否构成格, ,并说明理由并说明理由1) P(B),(1) ，其中其中P(B)P(B)是集合是集合B B的幂集2) Z,(2) ，其中其中Z Z是整数集是整数集, ,为小于或等于关系为小于或等于关系3) (3) 偏序集的哈斯图分别在下图给出偏序集的哈斯图分别在下图给出q 6例例13.213.2解答解答 (1)(1)是格 x,yx,yP(B)P(B)，x xy y就是就是x xy y，x xy y就是就是x xy y由于由于和和运算在运算在P(B)P(B)上是封闭的，所以上是封闭的，所以x xy y，x xy yP(B)P(B)称称P(B), ,为为B B的的幂集格幂集格2)(2)是格。

是格 x,yx,yZ,xZ,xy ymax(x,y)max(x,y)，x xy ymin(x,y)min(x,y)，它们都是整数它们都是整数3)(3)都不是格都不是格a)(a)中的中的a,ba,b没有最大下界没有最大下界b)(b)中的中的b,db,d有两个上界有两个上界c c和和e,e,但没有最小上界但没有最小上界c)(c)中的中的b,cb,c有三个上界有三个上界d,e,f,d,e,f,但没有最小上界但没有最小上界d)(d)中的中的a,ga,g没有最大下界没有最大下界q 7例例13.313.3例例13.3 13.3 设设G G是群，是群，L(G)L(G)是是G G的所有子群的集合即的所有子群的集合即L(G)L(G) H|H H|HG G 对任意的对任意的H H1 1,H,H2 2L(G)L(G)，H H1 1H H2 2也是也是G G的子群，而的子群，而H 是由是由H H1 1H H2 2生成的子群（即包含着生成的子群（即包含着H H1 1H H2 2的最小的子群）的最小的子群）在在L(G)L(G)上定义包含关系上定义包含关系 ，则，则L(G)L(G)关于包含关系构成一个格，关于包含关系构成一个格，称为称为G G的的子群格子群格。

易见在易见在L(G)L(G)中，中，H H1 1H H2 2就是就是H H1 1H H2 2，H H1 1H H2 2就是就是H q 8对对偶原理偶原理定定义义13.213.2 设设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的的命命题题令f f* *是将是将f f中的中的替替换换成成，替替换换成成，替替换换成成，替替换换成成所得到的命所得到的命题题称f f* *为为f f的的对对偶命偶命题题例如例如 在格中令在格中令f f是是(ab)cc(ab)cc，则则f f* *是是(ab)cc(ab)cc格的格的对对偶原理偶原理 设设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的命的命题题若f f对对一切格一切格为为真，真，则则f f的的对对偶命偶命题题f f* *也也对对一切格一切格为为真例如例如 对对一切格一切格L L都有都有 a,bLa,bL，ababa a( (因因为为a a和和b b的交是的交是a a的一个下界的一个下界) )那么那么对对一切格一切格L L都有都有 a,bLa,bL，ababa a说说明明许许多格的性多格的性质质都是互都是互为对为对偶命偶命题题的。

的有了格的有了格的对对偶原理，在偶原理，在证证明格的性明格的性质时质时，只只须证须证明其中的一个命明其中的一个命题题即可q 9格的运算性质格的运算性质定理定理13.113.1 设设L, 是格，则运算是格，则运算和和适合适合交换律交换律、结合结合律律、幂等律幂等律和和吸收律吸收律，即，即(1)(1)交换律交换律 a,bL a,bL 有有ababbabaababbaba(2)(2)结合律结合律 a,b,cL a,b,cL 有有(ab)c(ab)ca(bc)a(bc)(ab)c(ab)ca(bc)a(bc)(3)(3)幂等律幂等律 aL aL 有有aaaaa aaaaaa a(4)(4)吸收律吸收律 a,bL a,bL 有有a(ab)a(ab)a aa(ab)a(ab)a aq 10定理定理13.113.1(1)ab(1)ab和和baba分别是分别是a,ba,b和和b,ab,a的最小上界的最小上界由于由于a,ba,bb,ab,a，所以所以ababbaba由对偶原理，由对偶原理，ababbaba得证2)(2)由最小上界的定义有由最小上界的定义有(a(ab)b)cca abba a (13.1)(13.1)(a(ab)b)cca abbb b (13.2)(13.2)(a(ab)b)ccc c (13.3)(13.3)由式由式13.213.2和和13.313.3有有(a(ab)b)ccb bc c(13.4)(13.4)再由式再由式13.113.1和和13.413.4有有(a(ab)b)cca a(b(bc)c)同理可证同理可证(a(ab)b)cca a(b(bc)c)根据偏序关系的反对称性有根据偏序关系的反对称性有(a(ab)b)c ca a(b(bc)c)由对偶原理，由对偶原理，(a(ab)b)c ca a(b(bc)c)得证。

得证q 11定理定理13.113.1(3)(3)显显然然aaa,aaa,又由又由aaaa可得可得 aaaaaa根据反根据反对对称性有称性有 aaaaa a，由由对对偶原理，偶原理，aaaaa a 得得证证4)(4)显显然然a(ab)aa(ab)a(13.5)(13.5)又由又由 aaaa，aba aba 可得可得a(ab)a a(ab)a (13.6)(13.6)由式由式13.513.5和和13.613.6可得可得 a(ab)a(ab)a a，根据根据对对偶原理，偶原理，a(ab)a(ab)a a 得得证证q 12定理定理13.213.2定理定理13.213.2 设设S,*, 是具有两个二元运算的代数系统，若对是具有两个二元运算的代数系统，若对于于* *和和 运算适合运算适合交换律交换律、结合律结合律、吸收律吸收律，则可以适当定，则可以适当定义义S S中的偏序中的偏序，使得使得S, 构成一个格，且构成一个格，且a,bSa,bS有有ababa*ba*b，ababa a b b思路思路 (1)(1)证明证明在在S S中中* *和和 运算都适合幂等律运算都适合幂等律2)(2)在在S S上定义二元关系上定义二元关系R R，并证明并证明R R为偏序关系。

为偏序关系3)(3)证明证明构成格说明说明通过规定运算及其基本性质可以给出格的定义通过规定运算及其基本性质可以给出格的定义q 13定理定理13.213.2 a aSS，由吸收律得由吸收律得(1)(1)证明在证明在S S中中* *和和 运算都适合幂等律运算都适合幂等律a*aa*a a*a*( (a a (a*a)(a*a) a a同理有同理有 a a a aa a2)(2)在在S S上定义二元关系上定义二元关系R R， a,ba,bS S 有有 R R a a b bb b下面证明下面证明R R在在S S上的偏序上的偏序根据幂等律，根据幂等律， a aSS都有都有a a a aa a，即即RR，所以所以R R在在S S上是自反的上是自反的 a,bS a,bS 有有aRbaRb且且bRabRa a a b bb b且且b b a aa a a ab b a aa a b bb (b (由于由于a a b=bb=b a)a)所以所以R R在在S S上是反对称的上是反对称的q 14定理定理13.213.2 a,b,ca,b,cSS 有有aRbaRb且且bRc bRc a a b bb b 且且 b b c cc c a a c ca a (b(b c)c) a a c c(a(a b)b) c c a a c cb b c cc c aRcaRc这就证明了这就证明了R R在在S S上是传递的。

上是传递的综上所述，综上所述，R R为为S S上的偏序上的偏序以下把以下把R R记作记作q 15定理定理13.213.2(3) (3) 证明证明S 构成格 即证明即证明ababa a b b，ababa*b a*b a,ba,bSS 有有a a (a(a b)b)(a(a a)a) b ba a b bb b (a(a b)b)a a (b(b b)b)a a b b根据根据的定义有的定义有 aaaa b b和和baba b b，所以所以a a b b是是a,ba,b的上界假设假设 c c为为a,ba,b的上界，的上界， 则有则有a a c cc c和和b b c cc c，从而有从而有(a(a b)b) c c a a (b(b c)c) a a c c c c这就证明了这就证明了a a bcbc，所以所以a a b b是是a,ba,b的最小上界，即的最小上界，即 a ab ba a b b为证为证a*ba*b是是a,ba,b的最大下界，的最大下界， 先证先证首先由首先由a a b bb b 可知可知 a*b a*b a*(aa*(a b)b) a a反之由反之由a*ba*ba a 可知可知a a b b(a*b)(a*b) b b b b (b*a)(b*a)b b再由式再由式(13.7)(13.7)和和的定义有的定义有 ab ab a*b a*ba a，依照前边的证明依照前边的证明, ,类似地可证类似地可证 a*ba*b是是a,ba,b的最大下界，的最大下界， 即即 a ab ba*ba*b。

a a b bb b a*b a*ba a(13.7)(13.7)q 16格的等价定义格的等价定义根据定理根据定理13.213.2，可以给出格的另一个等价定义可以给出格的另一个等价定义定义定义13.313.3 设设S,*, 是代数系统，是代数系统，* *和和 是二元运算，如果是二元运算，如果* *和和 满满足交换律，结合律和吸收律，则足交换律，结合律和吸收律，则S,*, 构成一个构成一个格格( (lattice) )说明说明格中的幂等律可以由吸收律推出。