18lattice.ppt

* * * * * * * * * * * * * * * * * * * * * * * * 格 离散数学 第18讲 格 偏序格 格的对偶原理 格的性质 代数格 分配格 有界格与有补格 偏序格 定义： 〈S,?〉是偏序集 ?x,y?S, 存在{x,y}的最小上界lub{x,y} ?x,y?S, 存在{x,y}的最大下界glb{x,y} 则称S关于?构成格。 lub : “least upper bound” glb : “greatest lower bound 在格中定义运算 在格中可以定义如下的运算： “保联”：?x,y?S, x?y=lub{x,y} “保交”：?x,y?S, x?y=glb{x,y} 偏序格的例子 〈{1,2,3,4,6,8,12,16,24,48},|〉 x?y=gcd(x,y), x?y=lcm(x,y) 〈?(B), ?〉 x?y=x?y, x?y=x?y 〈整数集，?〉 x?y=min{x,y}, x?y=max{x,y} 格与哈斯图 右边两个哈斯图所表示的偏序集不是格 格的基本关系式 根据“最小上界”和“最大下界”的定义，有如下关系式： a?a?b, b?a?b 如果a?c, b?c, 则a?b?c a?b?a, a?b?b 如果c?a, c?b, 则c?a?b 关于格的对偶命题 对偶命题的例子(a,b是格中元素) a?b?a和a?b?a互为对偶命题 对偶命题构成规律 格元素名不变 ?与?，?与?全部互换。 格的对偶原理 如果命题P对一切格为真，则P的对偶命题P*也对一切格为真。 证明思路：证明P*对任意格〈S, ?〉为真 证明过程： 定义S上的二元关系?*, ?a,b?S, a?*b ? b?a, 显然?*是偏序。 ?a,b?S, a?*b=a?b, a?*b=a?b 所以〈S, ?*〉也是格 这里a?*b, a?*b分别是a,b关于偏序?*的最大下界和最小上界。 P*在〈S, ?〉中为真当且仅当 P在〈S, ?*〉中为真。 P在一切格中为真，?P*在一切格中为真。 格的性质 若〈S, ?〉是格，则：?a,b?S: a?b ? a?b=a ? a?b=b 采用循环证明： a?b ? a?b=a：由下界定义：a?b?a, 而a?a, a?b, 由最大下界定义：a?a?b, ?a?b=a a?b=a ? a?b=b: 由上界定义：b?a?b, 而由a?b?b和a?b=a可知：a?b, 又b?b, 由最小上界定义可知：a?b?b, ?a?b=b a?b=b ? a?b: a?a?b, 而a?b=b, ?a?b 格导出的代数系统 若〈S, ?〉是格，则〈S, ?, ?〉称为格S导出的代数系统。 〈S, ?, ?〉满足下列性质： (证明利用偏序的反对称性 以及 格命题的对偶原理) 交换律：a?b=b?a, a?b=b?a ?a?b?b, a?b?a, ?a?b?b?a, 同理可得b?a?a?b 结合律：(a?b)?c=a?(b?c), (a?b)?c=a?(b?c) 注意：(a?b)?c?a?b?a, (a?b)?c?a?b?b, 当然还有(a?b)?c?c 等幂律：a?a=a, a?a=a 由偏序的自反性：a?a且a?a, ?a?a?a, 当然还有a?a?a 吸收律：a?(a?b)=a, a?(a?b)=a 由a?a和a?a?b可得：a?a?(a?b), 当然还有a?(a?b)?a 代数格 定义：设〈L, *, ?〉是代数系统，其中*, ?是二元运算，且满足交换律、结合律、吸收律，则称〈L, *, ?〉是(代数)格。 代数格满足等幂律：即?a?L, a*a=a, a?a=a 根据吸收律：a=(a?(a*a))=(a*(a?a)), ?a*a=a*(a?(a*a))=a, a?a=a?(a*(a?a))=a a?b=b 当且仅当 a*b=a ? 若a?b=b, 则a*b=a*(a?b)=a ? 若a*b=a, 则a?b=(a*b)?b=b?(b*a)=b 在代数格中定义偏序关系 设〈L, *, ?〉是代数格，定义L上的关系R如下： ?a,b?L, aRb ? a?b=b 则R是偏序。 自反性：注意?满足等幂律 反对称性：若aRb, bRa, 则a?b=b, b?a=a, 但a?b=b?a, ?a=b 传递性：若aRb, bRc, 则a?b=b, b?c=c, 则a?c=a?(b?c)=(a?b)?c=b?c=c, 即aRc a?b即{a,b}的最小上界 a?b即{a,b}的上界 ?a?(a?b)=(a?a)?b=a?b, ?aR(a?b)