离散数学第11章课件PPT_高等教育出版社_屈婉玲_耿素云_张立昂主编.ppt

离散数学第11章课件PPT_高等教育出版社_屈婉玲_耿素云_张立昂主编.ppt

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

第十一章 格与布尔代数 主要内容 格的定义及性质 子格 分配格、有补格 布尔代数 11.1 格的定义与性质 定义11.1 设S, ?是偏序集,如果?x,y?S,{x,y}都有最小上 界和最大下界,则称S关于偏序?作成一个格. (偏序关系P126) 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧, 格的性质:算律 定理11.1 设L, ?是格, 则运算∨和∧适合交换律、结合律、 幂等律和吸收律, 即 (1) ?a,b∈L 有 a∨b = b∨a, a∧b = b∧a (2) ?a,b,c∈L 有 (a∨b)∨c = a∨(b∨c), (a∧b)∧c = a∧(b∧c) (3) ?a∈L 有  a∨a = a, a∧a = a (4) ?a,b∈L 有  a∨(a∧b) = a, a∧(a∨b) = a 格的性质:序与运算的关系 定理11.3 设L是格, 则?a,b∈L有 a ? b ? a∧b = a ? a∨b = b 可以用集合的例子来验证 幂集格 P(B),? ,其中P(B)是集合B的幂集. 幂集格. ?x,y∈P(B),x∨y就是x∪y,x∧y就是x∩y. 格的性质:保序 定理11.4 设L是格, ?a,b,c,d∈L,若a ? b 且 c ? d, 则 a∧c ? b∧d, a∨c ? b∨d 格作为代数系统的定义 定理11.4 设S,?,?是具有两个二元运算的代数系统, 若对于 ?和?运算适合交换律、结合律、吸收律, 则可以适当定义S中 的偏序 ?,使得 S,? 构成格, 且?a,b∈S 有 a∧b = a?b, a∨b = a?b. 证明省略. 根据定理11.4, 可以给出格的另一个等价定义.? 11.2 分配格、有补格与布尔代数 定义11.5 设L,∧,∨是格, 若?a,b,c∈L,有  a∧(b∨c) = (a∧b)∨(a∧c)   a∨(b∧c) = (a∨b)∧(a∨c) 则称L为分配格. 注意:可以证明以上两个条件互为充分必要条件 有界格的定义 定义11.6 设L是格, (1) 若存在a∈L使得?x∈L有 a ? x, 则称a为L的全下界 (2) 若存在b∈L使得?x∈L有 x ? b, 则称b为L的全上界? 说明: 格L若存在全下界或全上界, 一定是惟一的. 一般将格L的全下界记为0, 全上界记为1. 定义11.7 设L是格,若L存在全下界和全上界, 则称L 为有界 格, 一般将有界格L记为L,∧,∨,0,1. 定理11.6 设L,∧,∨,0,1是有界格, 则?a∈L有 a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1 有界格中的补元及实例 定义11.8 设L,∧,∨,0,1是有界格, a∈L, 若存在b∈L 使得  a∧b = 0 和 a∨b = 1 成立, 则称b是a的补元. 注意:若b是a的补元, 那么a也是b的补元. a和b互为补元. 解答 (1) L1中 a 与 c 互为补元, 其中 a 为全下界, c为全上界, b 没有 补元. (2) L2中 a 与 d 互为补元, 其中 a 为全下界, d 为全上界, b与 c 也互为补元. (3) L3中a 与 e 互为补元, 其中 a 为全下界, e 为全上界, b 的补 元是 c 和 d ; c 的补元是 b 和 d ; d 的补元是 b 和 c ; b, c, d 每个元素都有两个补元.? (4) L4中 a 与 e 互为补元, 其中 a 为全下界, e 为全上界, b 的补 元是 c 和 d ; c 的补元是 b ; d 的补元是 b . 有界分配格的补元惟一性 定理11.7 设L,∧,∨,0,1是有界分配格. 若L中元素 a 存在 补元, 则存在惟一的补元. 证 假设 c 是 a 的补元, 则有   a∨c = 1, a∧c = 0, 又知 b 是 a 的补元, 故   a∨b = 1, a∧b = 0  从而得到 a∨c = a∨b, a∧c = a∧b, 由于L是分配格. b=b ∧ (b∨a) = b ∧ (c∨a )= (b ∧ c)∨ (b ∧ a )= (a∨c ) ∧c=c

文档评论(0)

yan698698 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档