[2018年必威体育精装版整理]06离散数学课件资料.pptVIP

离散数学 离散数学 一、格的基本概念和性质（续） 例4：设n为正整数，Sn是n的正因子的集合，R为整除 关系，验证Sn, R是格，并举例说明。 如当n = 6, 8, 30时，分别有下图： S8, R 8 4 2 1 S6, R 2 1 6 3 1 3 5 2 6 10 15 30 S30, R 解： 离散数学 一、格的基本概念和性质（续） 例5：判断下列偏序集是否构成格，说明原因。 d b a c f e c b a d e a b e c d f {e，f}没有上界 {b，d}有上界c、e，但没有最小上界 {d，e}有下界a、b、c，但没有最大下界 离散数学 (1) 格的对偶原理：设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 ? a≥a a≥a ? a = a ? a ? a≥a ? a 离散数学 (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)； 离散数学 格：设L, ?, ?是代数系统，? 和? 是二元运算， 若? 和? 运算满足交换律，结合律和吸收律， （隐含幂等律），则称L, ?, ?是一个格。 一、格的基本概念和性质（续） 子格：设L, ?, ?是格，S 是L 的非空子集，若S 关于运算? 和? 是封闭的，则称S, ?, ?是 格L, ?, ?的子格。 格的另一个等价定义： 离散数学 一、格的基本概念和性质（续） 例6：格L, ?, ?如图，Si, ?, ?是否构成其子格。 其中S1 = { a, e, g, h}，S2 = { a, c, e, h}， S3 = { a, b, d, f , h} a b d c e g f h S1, ?, ?不是子格， S2, ?, ?是子格， S3, ?, ?是子格， 离散数学 b e a c d 五角格 1、分配格：设L, ?, ?是格，若对? a, b, c?L有 a ? (b ? c) = (a ? b) ? (a ? c) a ? (b ? c) = (a ? b) ? (a ? c) 成立，则称L, ?, ?为分配格。 二、特殊的格 d c b a b a d c a d e c b 钻石格 离散数学 二、特殊的格（续） 格L, ?, ?是分配格当且仅当它不含有 与五角格或钻石格同构的子格。 分配格的 判定定理 例6：判断下列格是否为分配格。 c a f e d b c a e d b f c a e d b g f c a h e f b g d 离散数学 二、特殊的格（续） 2、有界格： 全下界(或全上界)：设L, ?, ?为格， 若存在a?L，对? b?L有a≤b(或a≥b)， 则称a为格L, ?, ?的全下界(全上界)。 有界格：具有全上界和全下界的格。 记作L, ?, ?, 0, 1。 记全下界为0，全上界为1。 所有的有限元的格都是有界格。 离散数学 二、特殊的格（续） 3、有补格： 补元：设L