南京大学《离散数学》课件-第9周.pdfVIP

格 离散数学 第17讲 上一讲内容的回顾 变换群诱导的等价关系 轨道 轨道的大小 轨道的个数-Burnside定理 Burnside定理的应用 格 偏序格 格的对偶原理 格的性质 代数格 子格 格同态与保序 偏序格 lub : “least upper bound” 定义： glb : “greatest lower bound 〈S,≼ 〉是偏序集 x,y S, 存在{x,y}的最小上界lub {x,y} x,y S, 存在{x,y}的最大下界glb {x,y} 则称S关于≼ 构成格。 在格中定义运算 在格中可以定义如下的运算： “保联”：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 所以P也是格 • 这里a⋀ *b, a⋁ *b分别是a,b关于偏序≼ *的最大下界和最小上界。 P *在 〈S, ≼ *〉中为真当且仅当 P在 〈S, ≼ 〉中为真。 P在一切格中为真，P *在一切格中为真。 格的性质 若 〈S, ≼ 〉是格，则：a,b S: a≼ b  a⋀ b a