离散数学课件：6-2几种特殊的格

1、(一一)模格模格：设：设是由格是由格所诱导的代数系统，所诱导的代数系统，若若 a,b,c A, 当当a b时，满足时，满足a (b c)=b (a c),则称则称是是模格模格.判断以下格是否是模判断以下格是否是模格格.(1)ecbda解：解： x, y, z a, b, c, d, e, 钻石格钻石格则必有则必有x=e或或y=a.若若x=e, 则则x (y z)=y (x z)=y z ,y z .若若y=a, 则则x (y z)=y (x z)=x z ,x z .所以钻石格是模格所以钻石格是模格.若若x y,二、几种特殊的格二、几种特殊的格判断以下格是否是模判断以下格是否是模格格.ecbd

2、a五角格五角格(2)解：解： 因为因为d c, 但但c (d b)=d (c b)=c ad e=c,=d.所以五角格不是模格所以五角格不是模格.二、几种特殊的格二、几种特殊的格模格的判定模格的判定定理一定理一：格格L是模格当且仅当是模格当且仅当L不含与五角格同构不含与五角格同构的子格的子格.证明：证明：（充分性）（充分性）假设假设L不是模格，不是模格，则由定义，存在则由定义，存在a,b,c L, 满足满足a b, 但但a (b c) b (a c),实际上：必有实际上：必有a b, 且且a (b c) b (a c), (b (a c)是是a, (b c)的上界。的上界。)令：令：x=a (

3、b c), y=b (a c), 又令：又令：u=b c, v=a c, 下面证明下面证明L=x,y,u,v,c构成构成L的的5阶子格阶子格, 且且L与五角格同构与五角格同构.（L到五角格的同构映射到五角格的同构映射 : (x)=d, (y)=c, (u)=e, (v)=a, (c)=b, 如右图所示如右图所示)ecbda(u)(v)(y)(x)(c)二、几种特殊的格二、几种特殊的格定理一定理一：格格L是模格当且仅当是模格当且仅当L不含与五角格同构不含与五角格同构的子格的子格.ecbda(u)(v)(y)(x)(c)x=a (b c), y=b (a c), u=b c, v=a c证明（续）

4、证明（续）：（充分性）：（充分性）显然显然u x y v, u c v, 由由 所以所以L关于关于 和和 封闭，且封闭，且c x, c y.可得可得x c=y c=u. 又由又由 可得可得x c=y c=v.下面证明下面证明c u, c v且且x u, y v: 假设假设c=u, 则则c x x c=xx=v, 矛盾矛盾, 故故c u；假设假设c=v, 则则y c c y=y y=u,矛盾矛盾, 故故c v；假设假设x=u, 则则x c x c=cc=v, 矛盾矛盾, 故故x u ；假设假设y=v, 则则c y c y=c c=u,矛盾矛盾, 故故y v .x c y c=b (a c) c=

5、b c=uu c u=x c y c a c=va c=v=二、几种特殊的格二、几种特殊的格定理二定理二：格格L是模格的充分必要条件是：是模格的充分必要条件是： a,b,c L, 假设假设a b, 则：则： a c=b c且且a c=b c a=b.模格的判定模格的判定证法一证法一：(必要性必要性) 设设L是模格，则是模格，则a (a c)=b (a c)a= b (b c)=b(充分性充分性) 若若L不是模格，不是模格， 不妨设不妨设L有如下图的有如下图的与五角格同构的子格，与五角格同构的子格， 则则b,c,d导致矛盾导致矛盾.ecbda(b)(a)(c)二、几种特殊的格二、几种特殊的格a

6、(b c)= 而由给定条件，只而由给定条件，只需证：需证：定理二定理二：已知已知 a,b,c L, 假设假设a b, 必有：必有： a c=b c且且a c=b c a=b, 证明证明L是模格是模格.定理二充分性的第二种证法：定理二充分性的第二种证法：直接证明直接证明证法二证法二： 需证：若需证：若a b, 则则a (b c)= b (a c).以及以及a (b c) b (a c)(III). (a (b c) c =(b (a c) c (I)(a (b c) c=a (b c) c)=a c; a b (a c),又：又：a a c, a b,a c (b (a c) c,但但b (a

7、c) a c,(b (a c) c (a c) c=a c,故故(a c) b) c=a c.(a (b c) c=(b (a c) c (II)(1) 先证先证(I)式：式： (a (b c) c =(b (a c) c.二、几种特殊的格二、几种特殊的格(2) 再证再证(II)式：式： (a (b c) c=(b (a c) c (3) 最后证不等式最后证不等式(III)： a (b c) b (a c).根据分配不等式，根据分配不等式，a (b c) (a b) (a c), a b, a b=b, a (b c) b (a c).由由I. 若若a b, 则：则：(a (b c) c=(b

8、 (a c) c根据对偶原理得：根据对偶原理得：若若b a, 则：则： a,b,c L, 若若a b,有：有：(a (b c) c=(b (a c) c, a,b是是L中任意元素，中任意元素，(b (a c) c=(a (b c) c.定理二充分性的第二种证法：定理二充分性的第二种证法：直接证明直接证明二、几种特殊的格二、几种特殊的格：设：设是由格是由格所诱导的代数所诱导的代数系统，若系统，若 a, b, c A, 满足满足a (b c)=(a b) (a c)(1)a (b c)= (a b) (a c)(2) 则称则称是是分配格分配格.(二二)分配格分配格二、几种特殊的格二、几种特殊的格定

9、理三定理三：若在一个格中交运算对并运算可分配，则：若在一个格中交运算对并运算可分配，则并运算对交运算也一定可分配并运算对交运算也一定可分配. 反之亦然反之亦然.证明：证明： 如果格中任意元素如果格中任意元素x, y, z满足满足x (y z)=(x y) (x z), 那么对格中任意取定的元素那么对格中任意取定的元素a, b, c, 有有(a b) (a c)=a (a b) c) =a (a c) (b c) =(a (a c) (b c) =a (b c). (a b) a) (a b) c) 类似可证，逆命题也成立类似可证，逆命题也成立.F分配格定义中的条件可减弱为：需且只需分配格定义中

10、的条件可减弱为：需且只需(1)式式或或(2)式其中之一成立式其中之一成立.二、几种特殊的格二、几种特殊的格判断以下格是否是分配判断以下格是否是分配格格。(1) 解：解：因为因为 P, Q, R P(S), P(QR)= (PQ)(PR)P(QR)= (PQ)(PR)所以该格是分配格。所以该格是分配格。 F 特别地，当特别地，当S=a, b, c时时, 哈斯图如右图所示哈斯图如右图所示: a, b, c a, bb, c a, cbac 二、几种特殊的格二、几种特殊的格判断以下格是否是分配判断以下格是否是分配格格。(2)解：解：因为因为b (c d)=b e=b,(b c) (b d)=a a=

11、a,所以所以b (c d) (b c) (b d), 从而该格不是分配格从而该格不是分配格.钻石格钻石格ecbda二、几种特殊的格二、几种特殊的格判断以下格是否是分配判断以下格是否是分配格格.(3)解：解：因为因为d (b c)=d e=d,(d b) (d c)=a c=c,所以所以d (b c) (d b) (d c),从而该格不是分配格。从而该格不是分配格。五角格五角格ecbda二、几种特殊的格二、几种特殊的格定理四定理四：分配格必是模格：分配格必是模格.证：证：a b=b.因此因此 a (b c)= b (a c),则则 a, b, c A, 有有a (b c)= (a b) (a c

12、)设设是一个分配格，是一个分配格，即即是是模格模格.当当a b时，有时，有F模格不一定是分配格模格不一定是分配格.分配格与模格分配格与模格如：钻石格是模格，但不是分配格。如：钻石格是模格，但不是分配格。二、几种特殊的格二、几种特殊的格什么样的模格是分配格？什么样的模格是分配格？定理五定理五：模格模格L是分配格是分配格 当且仅当当且仅当 a,b,c L：(a b) (b c) (a c)=(a b) (b c) (a c)证明：证明：（充分性）（充分性）a (b c)= a (a c) (b c)=a (a b) (a c) (b c)=a (a b) (a c) (b c)=a (a b) (

13、a c) (b c)注意到注意到a b a, a c a, 而而L是模格，是模格，上式上式=所以所以(a b) (a (a c) (b c)=(a b) (a c) (a b c)=(a b) (a c)即即 a,b,c L,(a b) (b c) (a c)=(a b) (b c) (a c) a,b,c L, a (b c)=(a b) (a c)二、几种特殊的格二、几种特殊的格什么样的模格是分配格？什么样的模格是分配格？定理五定理五：模格模格L是分配格是分配格 当且仅当当且仅当 a,b,c L：(a b) (b c) (a c)=(a b) (b c) (a c)证明证明(续续)： （必

14、要性）（必要性） a,b,c L,(a b) (b c) (a c)=(a b) (b c) (a c)即即 a,b,c L, a (b c)=(a b) (a c) a (b c)=(a b) (a c)(a b) (b c) (a c)=(b (a b) c) (a c)(a b) b) (a b) c) (a c)=(b (a c) (b c) (a c)=(b (a c) (a c) (a c)=(a b) (b c) (a c) 二、几种特殊的格二、几种特殊的格=(b (a c) (a c)什么样的模格是分配格？什么样的模格是分配格？定理六定理六：模格模格L是分配格当且仅当是分配格当

15、且仅当L不含与钻石不含与钻石格同构的子格格同构的子格.证明：证明： 显然显然.(钻石格不是分配格钻石格不是分配格) 则由定理五，必有则由定理五，必有a,b,c L, 满足：满足：假设假设L是模格但非分配格，是模格但非分配格，(a b) (b c) (a c) (a b) (b c) (a c)(为什么一定为什么一定是是 ？参见？参见教材教材6-1习题习题(9)令：令：u= (a b) (b c) (a c), v= (a b) (b c) (a c), 又令：又令：x=u (a v), y=u (b v), z=u (c v),下面证明下面证明L=u,v,x,y,z构成构成L的子格的子格, 且

16、与钻石格同构且与钻石格同构.（L到五角格的同构映射到五角格的同构映射 : (u)=e, (v)=a, (x)=b, (y)=c, (z)=d, 如右图所示如右图所示)ecbdavuxyz二、几种特殊的格二、几种特殊的格定理六定理六：模格模格L是分配格当且仅当是分配格当且仅当L不含与钻石不含与钻石格同构的子格格同构的子格.证明（续）：证明（续）：ecbdavuxyzu= (a b) (b c) (a c), v= (a b) (b c) (a c),x=u (a v), y=u (b v), z=u (c v)先证先证L=u,v,x,y,z关于关于 和和 是是封闭封闭的：的：以计算以计算x y,

17、 x y为例：为例：而而a v=代入，得：代入，得：注意到注意到a (b c) a c, 注意到注意到b b c, x y=b v=x y=x y =u (b (a (b c) (a c)x y =u (a b) (b c) (a c)u (a v) (b v)a (a b) (b c) (a c)=a (b c)b (a b) (b c) (a c)=b (a c)u (a (b c) (b (a c)=u v=v (u v)二、几种特殊的格二、几种特殊的格定理六定理六：模格模格L是分配格当且仅当是分配格当且仅当L不含与钻石不含与钻石格同构的子格格同构的子格.证明（续）：证明（续）：ecbd

18、avuxyzu= (a b) (b c) (a c), v= (a b) (b c) (a c),x=u (a v), y=u (b v), z=u (c v)而而a u=代入，得：代入，得：注意到注意到a c a (b c), 注意到注意到b c b, 从而从而x y=b u=x y=x y=v (b (a (b c) (a c)x y =v (a b) (b c) (a c)同理可以推出：同理可以推出：x z=y z=u, x z=y z=vv (a u) (b u)a (a b) (b c) (a c)=a (b c)b (a b) (b c) (a c)=b (a c)v (a (b

19、c) (b (a c)=v u=u (u v) x=u (a v)=注意到注意到u v, v (a u),y=u (b v)= v (b u)二、几种特殊的格二、几种特殊的格定理六定理六：模格模格L是分配格当且仅当是分配格当且仅当L不含与钻石不含与钻石格同构的子格格同构的子格.证明（续）：证明（续）：再证再证L中元素中元素u,v,x,y,z互不相等：互不相等：u x v, u y v, u z v.由关于封闭性的讨论可知：由关于封闭性的讨论可知：假设假设x=u, 则则x y=y=z=v, 但但y z=u, 且且u v,矛盾，矛盾，y, x z= z,所以所以x u.同理可证：同理可证：y u,

20、 z u, x v, y v, z v.假设假设x=y, 则则x y=x, 但但x y=v,且且x v, 矛盾，矛盾， 所以所以x y.同理可证：同理可证：x z, y z.从而从而y z=v,二、几种特殊的格二、几种特殊的格分配格的判定分配格的判定 L是分配格是分配格. 定理七定理七：格格L是分配格当且仅当是分配格当且仅当L中中没有任何没有任何子格子格与与钻石格钻石格或或五角格五角格同构同构.证明：证明：因为因为L是分配格，是分配格，根据定理四，根据定理四，L必是模格必是模格.根据定理一，根据定理一， L不含与五角格同构的子格不含与五角格同构的子格.再根据定理六，再根据定理六， L也也不含与

21、钻石格同构的子格不含与钻石格同构的子格.因为因为L不含与五角格同构的子格，不含与五角格同构的子格，根据定理一，根据定理一， L是模格是模格.根据定理六，根据定理六，又因为又因为L也也不含与钻石格同构的子格不含与钻石格同构的子格.二、几种特殊的格二、几种特殊的格判断以下格是否是分配判断以下格是否是分配格格.dgabcfe解：解： 因为因为是该格的是该格的子格，子格，二、几种特殊的格二、几种特殊的格 而这个子格与五角格同而这个子格与五角格同构，构， 所以该格不是分配格所以该格不是分配格.五角格五角格ecbda分配格的判定分配格的判定 定理八定理八：格格L是分配格是分配格 当且仅当当且仅当 a,b,

22、c L, 有：有：a c=b c且且a c=b c a=b.证明证明：假设假设L不是分配格不是分配格, a=a (b c)=(a b) (a c)= (b a) (b c)= b (a c)= b (b c) =b 若若L是分配格，假设是分配格，假设a c=b c且且a c=b c, 则：则： 则由定理七，有子格则由定理七，有子格L同构于钻同构于钻石格或五角格石格或五角格.若若L同构于钻石格同构于钻石格，设其最大元是，设其最大元是v, 最小元是最小元是u, 其其它元素是它元素是x,y,z, 则则x z=y z, x z=y z, 但但x y,若若L同构于五角格同构于五角格，设其最大元是，设其最

23、大元是v, 最小元是最小元是u, 其其它元素是它元素是x,y,z, 且且x y, 则则x z=y z, x z=y z, 但但x y.二、几种特殊的格二、几种特殊的格a (a c)=与条件矛盾与条件矛盾;与条件矛盾与条件矛盾.分配格与模格充要条件的比较分配格与模格充要条件的比较&格格L是分配格是分配格 当且仅当当且仅当 a,b,c L, 有：有：a c=b c且且a c=b c a=b.&格格L是模格的充分必要条件是：是模格的充分必要条件是： a,b,c L, 假设假设a b, 则：则： a c=b c且且a c=b c a=b.&分配格一定是模格，模格未必是分配格分配

24、格一定是模格，模格未必是分配格二、几种特殊的格二、几种特殊的格 该子格中必有子格与该子格中必有子格与钻石格钻石格或或五角格五角格同构，同构， 假设存在一个分配格，它的某个子格不假设存在一个分配格，它的某个子格不是分配格，是分配格， 则由定理七，则由定理七， 从而原分配格中含有从而原分配格中含有与与钻石格钻石格或或五角格五角格同构的子格，同构的子格， 设设是一个分配格，是一个分配格，是是由它诱导的代数系统，设由它诱导的代数系统，设 是是的子格，的子格，分配格的判定分配格的判定定理九定理九 分配格的子格必是分配格。分配格的子格必是分配格。证一：证一：a (b c)= (a b) (a c)所以所以

25、B是一个分配格。是一个分配格。证二证二 ： (反证法反证法)与定理七矛盾与定理七矛盾. A, 有有则则 a, b, c B二、几种特殊的格二、几种特殊的格分配格的判定分配格的判定定理十定理十：每个链是分配格：每个链是分配格.证：证： a, b, c A, 分以下两种情况讨论：分以下两种情况讨论： 设设是链，是链， 则则必是格必是格.二、几种特殊的格二、几种特殊的格情况情况1：a b且且a c:a (b c)= 所以所以a (b c)=(a b) (a c). 又又(a b) (a c)=b c, b c,此时必有此时必有a b c,从而从而定理十定理十：每个链是分配格：每个链是分配格.续证：续

26、证：分配格的判定分配格的判定二、几种特殊的格二、几种特殊的格因为因为a (b c)= 所以所以a (b c)=(a b) (a c).情况情况2：b a或或c a:(a b) (a c)=a, a,(6-2习题习题(2) 判断下图中给出的格是否是判断下图中给出的格是否是分配格。分配格。解法一解法一解：解： 因为子格因为子格 和子格和子格均与五角格同构，所以均与五角格同构，所以该格不是分配格。该格不是分配格。根据定理七根据定理七， 设设是格，是格，是由是由所诱导的代数系统所诱导的代数系统，设设B A且且B，若运算若运算 和和 在在B中封闭中封闭，则称则称是是的的子格子格。fcdebafcdeaf

27、cdba(1)二、几种特殊的格二、几种特殊的格(教材教材6-2习题习题(2) 判断下图中给出的格是判断下图中给出的格是否是分配格。否是分配格。解法二解法二解：解： 根据根据定义，定义，当且仅当当且仅当 x, y, z A, 满足满足x (y z)=(x y) (x z)时时, 是分配格。是分配格。=60组。组。共要计算共要计算36Afcdeba2/计算量太计算量太大了！大了！(1)二、几种特殊的格二、几种特殊的格编程求解编程求解界面设计：界面设计：二、几种特殊的格二、几种特殊的格ecbda图图1：钻石格：钻石格编程求解编程求解 利用程序判断钻石格是否是分配格。利用程序判断钻石格是否是分配格。1

28、3245二、几种特殊的格二、几种特殊的格ecbda编程求解编程求解 利用程序判断五角格是否是分配格。利用程序判断五角格是否是分配格。图图2：五角格：五角格14235二、几种特殊的格二、几种特殊的格编程求解编程求解利用程序判断格利用程序判断格是否是分是否是分配格。配格。a, b, c a, bb, c a, cbac 图图3：格：格13245678二、几种特殊的格二、几种特殊的格编程求解编程求解(6-2习题习题(2) 判断下图中给出的格是否是分判断下图中给出的格是否是分配格配格.fcdeba123456(1)二、几种特殊的格二、几种特殊的格a, b, c a, bb, c a, cbac 因为因

29、为是分配是分配格，格，(6-2习题习题(2) 判断下图中给出的格是否是判断下图中给出的格是否是分配格。分配格。解法三解法三解：解： 根据定理九根据定理九, 其子格其子格也是分配格。也是分配格。而本题中的格与该子格同构，所而本题中的格与该子格同构，所以也是分配格。以也是分配格。fcdebaa, b, c a, bb, c a, cbac (1)二、几种特殊的格二、几种特殊的格 (6-2习题习题(2)判断下图中给出的几个格是判断下图中给出的几个格是否是分配格否是分配格.(2)ecdba解：解：因为该格与因为该格与(1)中的分配格中的分配格的子格的子格同构，所以同构，所以它是分配格它是分配格.二、几

30、种特殊的格二、几种特殊的格fcdeba (6-2习题习题(2)判断下图中给出的几个格是判断下图中给出的几个格是否是分配格否是分配格.(3)gcedbaf解：解：因为该格的子格因为该格的子格与与五角格同构，五角格同构，二、几种特殊的格二、几种特殊的格五角格五角格ecbda所以该格不是分配格所以该格不是分配格. (6-2习题习题(1)试举两个含有试举两个含有6个元素的格，个元素的格，其中一个是分配格，另一个不是分配格其中一个是分配格，另一个不是分配格.解：解：图图(a)中的格是分配格，图中的格是分配格，图(b)中的格不是分配格中的格不是分配格. 图图(b)ecbdaf子格子格与与钻石格同构钻石格同

31、构二、几种特殊的格二、几种特殊的格fcdeba图图(a)(三三)有界格有界格：设：设 是格，若存在是格，若存在a A, 对对任意任意x A,有有 a x 则称则称a为为的全下界，记为的全下界，记为0. ：设：设 是格，若存在是格，若存在a A, 对对任意任意x A,有有 x a 则称则称a为为的全上界，记为的全上界，记为1. 二、几种特殊的格二、几种特殊的格全下界、全上界全下界、全上界解：解：定理十一定理十一：格的全下（上）界若存在必唯一：格的全下（上）界若存在必唯一.那么按全下界的定义，有那么按全下界的定义，有同时成立，同时成立，从而从而a=b.假设假设格格有两个全下界有两个全下界a和和b,

32、 a,b A, a b和和b a, 二、几种特殊的格二、几种特殊的格有界格有界格有界格有界格：具有全下界和全上界的格称为：具有全下界和全上界的格称为有界格有界格.判断以下格是否是有界判断以下格是否是有界格格.(1) 解：解：全下界：全下界：所以该格是有界格所以该格是有界格. 全上界：全上界： S 二、几种特殊的格二、几种特殊的格判断以下格是否是有界判断以下格是否是有界格格.abd hcf eg (2) 解：解：全下界：全下界：所以该格是有界格所以该格是有界格. 全上界：全上界：h a 二、几种特殊的格二、几种特殊的格有界格的性质有界格的性质证：证：a 1= 1,a 1= a;a 0= a,a

33、0= 0.所以所以 a A, 有有再由格的性质六，得：再由格的性质六，得：a 1= 1,a 1= a;a 0= a,a 0= 0.1是是 的的零元零元.0是是 的的幺元幺元.0是是 的的零元零元.1是是 的的幺元幺元.0 a 1. 定理十二定理十二： 设设有界格，则有界格，则 a A, 有有 因为因为是有界格，是有界格， 二、几种特殊的格二、几种特殊的格补元补元格格中的各个元素是否有补元，若有，中的各个元素是否有补元，若有，请求出请求出.解：解：全下界是全下界是全上界是全上界是,S. 在格在格中，中， A P(S), A(S-A) =A(S-A) =S,.所以所以S-A是是A的补元的补元.Fa和和b互为补元互为补元.：设：设 是有界格，是有界格，a A, 若若 b A, 使使 a b=1, a b=0,则称则称b是是a的的补元补元. 二、几种特殊的格二、几种特殊的格