《离散数学幻灯片--第十三章--格与布尔代数》由会员分享，可在线阅读，更多相关《离散数学幻灯片--第十三章--格与布尔代数（84页珍藏版）》请在金锄头文库上搜索。
1、第13章 格与布尔代数,本章内容,13.1 格的定义与性质 13.2 子格与格同态 13.3 分配格与有补格 13.4 布尔代数 本章总结 作业,13.1 格的定义与性质,定义13.1 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格(lattice)。 说明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x与y的二元运算和。 xy：表示x与y的最小上界 xy：表示x和y的最大下界。 本章出现的和符号只代表格中的运算，而不再有其它的含义。,格的实例,例13.1 设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集构成格。x,ySn
2、， xy是lcm(x,y)，即x与y的最小公倍数。 xy是gcd(x,y)，即x与y的最大公约数。 下图给出了格，和。,例13.2,例13.2 判断下列偏序集是否构成格,并说明理由。 (1) ，其中P(B)是集合B的幂集。 (2) ，其中Z是整数集,为小于或等于关系。 (3) 偏序集的哈斯图分别在下图给出。,例13.2,解答 (1)是格。 x,yP(B)，xy就是xy，xy就是xy。 由于和运算在P(B)上是封闭的，所以xy，xyP(B)。 称,为B的幂集格。 (2)是格。 x,yZ,xymax(x,y)，xymin(x,y)，它们都是整数。 (3)都不是格。 (a)中的a,b没有最大下界。
3、(b)中的b,d有两个上界c和e,但没有最小上界。 (c)中的b,c有三个上界d,e,f,但没有最小上界。 (d)中的a,g没有最大下界。,例13.3,例13.3 设G是群，L(G)是G的所有子群的集合。即 L(G) H|HG 对任意的H1,H2L(G)，H1H2也是G的子群，而是由H1H2生成的子群（即包含着H1H2的最小的子群）。 在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。 易见在L(G)中，H1H2就是H1H2，H1H2就是。,对偶原理,定义13.2 设f是含有格中元素以及符号、和的命题。令f*是将f中的替换成，替换成，替换成，替换成所得到的命题。称f*
4、为f的对偶命题。 例如 在格中令f是(ab)cc，则f*是(ab)cc。 格的对偶原理 设f是含有格中元素以及符号、和的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。 例如 对一切格L都有 a,bL，aba (因为a和b的交是a的一个下界) 那么对一切格L都有 a,bL，aba 说明 许多格的性质都是互为对偶命题的。 有了格的对偶原理，在证明格的性质时， 只须证明其中的一个命题即可。,格的运算性质,定理13.1 设是格，则运算和适合交换律、结合律、幂等律和吸收律，即 (1)交换律 a,bL 有 abba abba (2)结合律 a,b,cL 有 (ab)ca(bc) (ab)ca(
5、bc) (3)幂等律 aL 有 aaa aaa (4)吸收律 a,bL 有 a(ab)a a(ab)a,定理13.1,(1)ab和ba分别是a,b和b,a的最小上界。 由于a,bb,a，所以abba。 由对偶原理，abba得证。 (2)由最小上界的定义有 (ab)caba (13.1) (ab)cabb (13.2) (ab)cc (13.3) 由式13.2和13.3有 (ab)cbc (13.4) 再由式13.1和13.4有 (ab)ca(bc) 同理可证 (ab)ca(bc) 根据偏序关系的反对称性有 (ab)ca(bc) 由对偶原理，(ab)ca(bc)得证。,定理13.1,(3)显然a
6、aa, 又由aa可得 aaa。 根据反对称性有 aaa， 由对偶原理，aaa 得证。 (4)显然 a(ab)a (13.5) 又由 aa，aba 可得 a(ab)a (13.6) 由式13.5和13.6可得 a(ab)a， 根据对偶原理，a(ab)a 得证。,定理13.2,定理13.2 设是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得构成一个格，且a,bS有aba*b，abab。 思路 (1)证明在S中*和运算都适合幂等律。 (2)在S上定义二元关系R，并证明R为偏序关系。 (3)证明构成格。 说明 通过规定运算及其基本性质可以给出格的定
7、义。,定理13.2,aS，由吸收律得,(1)证明在S中*和运算都适合幂等律。,a*a, a*(a(a*a), a,同理有 aaa。,(2)在S上定义二元关系R，,a,bS 有,R abb,下面证明R在S上的偏序。,根据幂等律，,aS都有aaa，,即R，,所以R在S上是自反的。,a,bS 有,aRb且bRa, abb且baa, abaabb (由于a b=ba),所以R在S上是反对称的。,定理13.2,a,b,cS 有 aRb且bRc abb 且 bcc aca(bc) ac(ab)c acbcc aRc 这就证明了R在S上是传递的。 综上所述，R为S上的偏序。 以下把R记作。,定理13.2,(
8、3) 证明构成格。 即证明abab，aba*b 。,a,bS 有,a(ab)(aa)bab,b(ab)a(bb)ab,根据的定义有 aab和bab，,所以ab是a,b的上界。,假设 c为a,b的上界，,则有acc和bcc，,从而有,(ab)c, a(bc), ac, c,这就证明了abc，,所以ab是a,b的最小上界，即,abab,为证a*b是a,b的最大下界，,先证,首先由abb 可知,a*b,a*(ab),a,反之由a*ba 可知,ab,(a*b)b,b(b*a),b,再由式(13.7)和的定义有 ab a*ba，,依照前边的证明,类似地可证 a*b是a,b的最大下界，,即 aba*b。,
9、abb a*ba (13.7),格的等价定义,根据定理13.2，可以给出格的另一个等价定义。 定义13.3 设是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则构成一个格(lattice)。 说明 格中的幂等律可以由吸收律推出。 以后我们不再区别是偏序集定义的格， 还是代数系统定义的格，而统称为格L。,格的性质,定理13.3 设L是格，则a,bL 有 ab aba abb 证明 先证 ab aba 由aa和ab可知，a是a,b的下界， 故aab。显然又有aba。 由反对称性得aba。 再证 aba abb。 根据吸收律有 bb(ba) 由aba得 bba, 即abb。 最后证a
10、bb ab。 由aab得 aabb。,格的性质,定理11.4 设L是格，a,b,c,dL，若ab且cd，则 acbd， acbd 证明 acab accd 因此， acbd。 同理可证 acbd。,例13.4,例13.4 设L是格，证明 a,b,cL 有 a(bc)(ab)(ac) 证明 由 aa，bcb 得 a(bc)ab 由 aa，bcc 得 a(bc)ac 从而得到 a(bc)(ab)(ac) 说明 在格中分配不等式成立。 一般说来，格中的和运算并不是满足分配律的。,本节小结,偏序集构成格的条件：任意二元子集都有最大下界和最小上界。 格的实例：正整数的因子格，幂集格，子群格。 格的性质：
11、对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。 格作为代数系统的定义。 格的证明方法,13.2 子格与格同态,定义13.4 设是格，S是L的非空子集，若S关于L中的运算和仍构成格，则称S是L的子格。,例13.5 设格L如右图所示。令,S1a,e,f,g S2a,b,e,g,则S1不是L的子格，S2是L的子格。 因为对于e和f,有efc， 但cS1。,格同态,定义13.5 设L1和L2是格，: L1L2，若a,bL1 有 (ab)(a)(b), (ab)(a)f(b) 成立，则称为格L1到L2的同态映射，简称格同态。 例13.6 (1)设 L12n|nZ+， L22n+1|n
12、N 则L1和L2关于通常数的小于或等于关系构成格。 令 : L1L2，(x)x-1 不难验证是L1到L2的同态映射，因为对任意的x,yL1有,(xy),(max(x,y),max(x,y)-1,(x)(y),(x-1)(y-1),max(x-1,y-1),max(x,y)-1,(xy),(min(x,y),min(x,y)-1,(x)(y),(x-1)(y-1),min(x-1,y-1),min(x,y)-1,即 (xy)(x)(y), (xy)(x)(y),例13.6,(2)如图中的格L1，L2和L3，若定义,1:L1L2 1(a)1(b)1(c)a1， 1(d)d1 2:L1L3 2(a)
13、a2，2(b)b2, 2(c)c2，2(d)d2,则1和2都不是格同态，因为 1(bc)1(d)d1 1(b)1(c)a1a1a1 2(bc)2(d)d2 2(b)2(c)b2c2c2 从而 1(bc)1(b)1(c) 2(bc)2(b)2(c),格同态的性质,定理13.5 设是格L1到L2的映射， (1)若是格同态映射，则是保序映射，即x,yL1，有 xy (x)(y) (2)若是双射，则是格同构映射当且仅当x,yL1，有 xy (x)(y) 证明 (1) 任取x,yL1，xy， 由格的性质知 xyy。 又由于是格同态映射，必有 (y)(xy)(x)(y) 从而得到(x)(y)。,定理13.
14、5(2)的证明,充分性。,(2)若是双射，则是格同构映射当且仅当x,yL1，有 xy (x)(y),只须证明是L1到L2的同态映射即可。,任取x,yL1，,令xyz，由 xz和yz 知,(x)(z)，(y)(z),从而有 (x)(y)(z)(xy),另一方面，由(x)(y)L2和的满射性可知， 必存在uL1使得 (u)(x)(y) 因此有 (x)(u)，(y)(u)。,由已知条件可得 xu，yu。,从而推出 xyu。,再次使用已知条件得 (xy)(u)(x)(y)。 综合上述有 (xy)(x)(y)。 同理可证 (xy)(x)(y)。,定理13.5(2)的证明,必要性。由(1)的结论必有 xy (x)(y) 反之，若(x)(y)，由于是同构映射，则 (xy)(x)(
