☒有京大赞 NANJING UNIVERSITY 离散数学 Discrete Mathematics 偏序与偏序格 南京大学计算机科学与技术系
偏序与偏序格 离 散 数 学 Discrete Mathematics 南京大学计算机科学与技术系
&嘉 回顾 ·关系的闭包 ·闭包的定义 。 闭包的计算公式 ·传递闭包的Warshall?算法 等价关系 ·等价类 ·划分
回顾 2 • 关系的闭包 • 闭包的定义 • 闭包的计算公式 • 传递闭包的Warshall算法 • 等价关系 • 等价类 • 划分
&原 提要 ·偏序关系 (1111 1110 0111 ■偏序集与哈斯图 0110 1101T1011 1100 1010】 0101 001① ■偏序集中的特殊元素 0100 0010 10017 ■特殊元素的性质 1000】 (0001) (0000 ·偏序格 本讲主要内容 3
提要 本讲主要内容 3 偏序关系 偏序集与哈斯图 偏序集中的特殊元素 特殊元素的性质 偏序格
偏序关系(Partial Order) 定义（偏序关系）：非空集合A上的自反、 反对称和传递的关系称为A上的偏序关系， 记为：≤ 设≤为偏序关系，若(a,b)∈≤，则记为a≤b 读作“a小于或等于b” 实例 集合A上的恒等关系I4是A上的偏序关系 小于或等于关系，整除关系和包含关系也是相应集合上的 偏序关系 偏序关系
偏序关系(Partial Order) 偏序关系 4
& 偏序关系（续） 定义： 设R为非空集合A上的偏序关系， x,y∈A,x与y可比台xyVy<x 任取两个元素x和y,可能有下述几种情况发生： x<y(或y<x),x=少，x与y不是可此的 定义：R为非空集合A上的偏序关系 Vxy EA,x与y都是可比的，则称R为全序（或线序） 实例：数集上的小于或等于关系是全序关系 整除关系不是正整数集合上的全序关系 定义：xy∈A,如果x<y且不存在z∈A使得x<z<y,则称y覆盖x. 例如{1,2,4,6}集合上的整除关系，2覆盖1,4和6覆盖2.但4不 覆盖1 偏序关系 5
偏序关系（续） 偏序关系 5 ： ： ：