偏序关系与偏序集
偏序关系与偏序集 1
回顾问题1：关系具有哪些重要性质?口自反性、对称性/反对称性、传递性问题2：如果计算关系的闭包？口自反闭包并上恒等关系、对称闭包并上逆关系、传递闭包的Warshall算法口问题3：什么是等价关系与等价类？口等价关系：自反、对称、传递；具有等价关系的元素构成等价类；所有等价类的集合为商集，商集即划分
问题1：关系具有哪些重要性质？ 自反性、对称性/反对称性、传递性 问题2：如果计算关系的闭包？ 自反闭包并上恒等关系、对称闭包并上逆关系、传递闭 包的Warshall算法 问题3：什么是等价关系与等价类？ 等价关系：自反、对称、传递；具有等价关系的元素构 成等价类；所有等价类的集合为商集，商集即划分 回顾
本节提要内容1：偏序关系与偏序集7内容2：偏序集中的特殊元素与偏序格7上
本节提要 内容1：偏序关系与偏序集 内容2：偏序集中的特殊元素与偏序格 3
偏序关系（PartialOrder）定义（偏序关系）：非空集合A上的自反反对称和传递的关系称为A上的偏序关系记为：八设为偏序关系，若(α,b)E人，则记为α从b读作“a小于或等于b"实例集合A上的恒等关系L是A上的偏序关系小于或等于关系，整除关系和包含关系也是相应集合上的偏序关系
偏序关系(Partial Order) 4
偏序关系（续）定义7.20设R为非空集合A上的偏序关系xyEAx与y可比xyVVAx任取两个元素×和可能有下述儿种情况发生：x<y(或y<x)，x=y，x与y不是可比的定义7.21R为非空集合A上的偏序关系VxyEAx与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系定义7.22xyEA，如果x<V且不存在zEA使得x<z<y则称y覆盖x例如12.4.6集合上的整除关系，2覆盖14和6覆盖2.但4不覆盖1
偏序关系（续） 5