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

格

格：设S,≤是偏序集，如果?x,y?S，{x,y}都有最小上界和最大下界，则称S,≤是一个格。通常记：{x,y}的最小上界为x?y{x,y}的最大下界为x?y格

例：设n为正整数，Sn是n的正因子的集合，D为整除关系，验证Sn,D是格，并举例说明。解：如当n=6,8,30时，分别有下图：S6,D2163S8,D842113526101530S30,D格

证明：因为Sn,D是自反的，反对称的，传递的，从而是偏序集；例：设n为正整数，Sn是n的正因子的集合，D为整除关系，验证Sn,D是格，并举例说明。对于?x,y?Sn，x与y的最小公倍数[x,y]属于Sn，x与y的最大公约数(x,y)属于Sn，且x?y=[x,y]，x?y=(x,y)。因此，Sn,D是一个格。格

例：判断下列偏序集是否构成格，说明原因。格

格的对偶原理：设f为含有格中的元素及符号=,≤,≥,?,?的关系式。f*是将f中的≤改成≥,≥改成≤,?改成?,?改成?后所得的关系式,称之为f的对偶命题。若f为对一切格为真,则f*也对一切格为真。格的性质：如：若格中(a?b)?c≤c成立，则(a?b)?c≥c成立。格

(2)设L,≤是格，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?(b?c)；证明：(a?b)?c≥a?b≥b(2)(a?b)?c≥a?b≥a(1)由(2)(3)得(a?b)?c≥b?c(4)由(1)(4)得(a?b)?c≥a?(b?c)同理可证a?(b?c)≥(a?b)?c∴(a?b)?c=a?(b?c)(a?b)?c≥c(3)

格的另一个等价定义：格：设L,?,?是代数系统，?和?是二元运算，若?和?运算满足交换律，结合律和吸收律，则称L,?,?是一个格。子格：设L,?,?是格，L是L的非空子集，若L关于运算?和?是封闭的，则称L,?,?是格L,?,?的子格。格

例：格L,?,?如图，Si,?,?是否构成其子格。其中S1={a,e,g,h}，S2={a,c,e,h}，S3={a,b,d,f,h}abdcegfhS1,?,?不是子格，S2,?,?是子格，S3,?,?是子格。格