(44)--4.9 格离散数学离散数学.ppt

《(44)--4.9 格离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(44)--4.9 格离散数学离散数学.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、格格：格：设设是偏序集，如果是偏序集，如果 x,y S，x,y都有都有 最小上界和最大下界，则称最小上界和最大下界，则称是一个格是一个格。通常记：通常记：x,y的的最小上界最小上界为为x y x,y的的最大下界最大下界为为x y格例例：设：设n为正整数，为正整数，Sn是是n的正因子的集合，的正因子的集合，D为整除为整除关系，验证关系，验证是格，并举例说明。是格，并举例说明。解解：如当：如当n=6,8,30时，分别有下图：时，分别有下图：2163 842113526101530格证明证明：因为：因为是自反的，反对称的，传递的，从而是偏序集；是自反的，反对称的，传递的，从而是偏序集；例例：设：设n

2、为正整数，为正整数，Sn是是n的正因子的集合，的正因子的集合，D为整除为整除关系，验证关系，验证是格，并举例说明。是格，并举例说明。对于对于 x,y Sn，x与与y的最小公倍数的最小公倍数x,y属于属于Sn，x与与y的最大公约数的最大公约数(x,y)属于属于Sn，且且x y=x,y，x y=(x,y)。因此因此，是一个格。是一个格。格例例：判断下列偏序集是否构成格，说明原因。：判断下列偏序集是否构成格，说明原因。格(1)格的对偶原理：格的对偶原理：设设f 为含有格中的元素及符号为含有格中的元素及符号=,的关系式。的关系式。f*是将是将f 中的中的改成改成,改成改成,改成改成 ,改成改成 后所得

3、的关系式后所得的关系式,称之为称之为f 的对偶命题。若的对偶命题。若f 为对一切格为真为对一切格为真,则则f*也对一切格为真。也对一切格为真。格的性质：格的性质：如：若格中如：若格中(a b)cc成立，则成立，则(a b)cc成立。成立。格(2)设设是格是格，a,b,c是是L中任意元素，则有：中任意元素，则有：交换律：交换律：a b=b a，a b=b a；结合律：结合律：(a b)c=a (b c)，(a b)c=a (b c)；幂等律：幂等律：a a=a，a a=a；吸收律：吸收律：a (a b)=a，a (a b)=a；格结合律：结合律：(a b)c=a (b c)，(a b)c=a (

4、b c)；证明证明：(a b)ca bb (2)(a b)c a ba (1)由由(2)(3)得得 (a b)cb c (4)由由(1)(4)得得 (a b)c a (b c)同理可证同理可证 a (b c)(a b)c (a b)c=a (b c)(a b)cc (3)格的另一个等价定义：格的另一个等价定义：格：格：设设是代数系统，是代数系统，和和 是二元运算，是二元运算，若若 和和 运算满足交换律，结合律和吸收律，运算满足交换律，结合律和吸收律，则称则称是一个格。是一个格。子格：子格：设设是格，是格，L是是L 的非空子集，若的非空子集，若L 关于运算关于运算 和和 是封闭的，则称是封闭的，则称是是 格格的子格。的子格。格例例：格：格如图，如图，是否构成其子格。是否构成其子格。其中其中S1=a,e,g,h，S2=a,c,e,h，S3=a,b,d,f,habdcegfh不是不是子格，子格，是是子格，子格，是是子格。子格。格THANK YOU