- 1、本文档共27页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
18lattice
* * * * * * * * * * * * * * * * * * * * * * * * 格 离散数学 第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)
文档评论(0)