19_代数格.ppt

代数格 离散数学－代数结构 南京大学计算机科学与技术系 内容提要 代数格的定义 格的对偶原理 子格 格同态、格同构 分配格 有界格 有补格 有补分配格 2 格（回顾） (S,≼)的一个（偏序）格，如果下列条件成立： 设(S,≼)是偏序集 x, yS, 存在{x,y}的最小上界lub{x,y} , 记为xy。 x, yS, 存在{x,y}的最大下界glb{x,y}, 记为xy。 设(S, ≼)是格，则(S, ,  )有下列性质: 结合律：(ab)  c = a  (bc), (ab)  c = a  (bc) 交换律：ab = ba, ab = ba 吸收律： a  (ab) = a, a  (ab)=a 3 代数格（定义） 设L是一个集合， 和是L上的二元运算，且满足结合律、交换律、吸收律，则称(L, , )是代数格。 等 式 名 称 x(yz)=(xy)z x(yz)=(xy)z 结合律 xy =yx xy= yx 交换律 x(xy) = x x(xy) = x 吸收律 4 代数格中的偏序关系  x, yB, xy =x iff xy =y 若 xy =x，则 xy = (xy)  y = y //吸收律 若 xy =y，则 x y = x (xy) = x //吸收律  x, yB, 定义 x ≼ y iff xy =x (即 xy =y) 证明这个关系满足自反性、反对称性、传递性。 这个偏序构成一个格。 lub{x,y} 即为 xy。 glb{x,y} 即为 xy。 代数格等同于（偏序）格 5 格的代数性质 x  x = x  ( x  (xx) ) = x （两次应用吸收律） 同理可证：x  x = x 6 关于格的对偶命题 对偶命题的例子 ab≼a和ab≽a互为对偶命题 对偶命题构成规律 格元素名不变 ≼与≽，与全部互换。 7 格的对偶原理 如果命题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*在一切格中为真。 8 子 格 9   格同态 10 格同态与格同构 11   格同态的保序性（续） 12 格同构的直观特征 13 观察以下2个格的哈斯图： 格同构的直观特征（续） 14 格同构的直观特征（续） 15 几种典型的格 16   分配格 17   分配格（续） 18 分配格的判定定理 19   分配格的判定定理（续） 20 分配格的判定定理（续） 21   分配格的判定定理（续） 22 分配格的判定定理（续） 23 有界格 24   有界格（续） 25   有界格（续） 26   有界格（续） 27   有补格 28   有补格（续） 29 有补格（续） 30   有补格（续） 31   有补格（续） 32   有补分配格 代数格：结合律、交换律、吸收律、（幂等律） 分配格：分配律 有 界：同一律、（支配律） 有 补：补 律、（双重补律、德摩根律） 33 有补分配格（代数性质） 34 作业 35 教材内容：[屈婉玲] 11.1，11.2节 课后习题：见课程网站