离散数学243(偏序关系).ppt

主讲教师 常亮E mail changl QQ 737059669办公室电话 2291071手机 13481395869辅导教师 周小川答疑时间 星期四上午10 20 11 50答疑地点 5教5楼软件工程教研室 离散数学 回顾 关系可能具有的性质 自反反自反对称反对称传递特殊关系 具有上述某些性质的关系等价关系 自反 对称 传递偏序关系 自反 反对称 传递 2 4 3偏序关系 定义2 28设R为非空集合A上的关系 即A 并且R A A 如果R是自反的 反对称的和传递的 则称R为A上的偏序关系 一般用符号 来表示偏序关系 设R是一个偏序关系 如果 R 则记为x y 如果集合A上存在偏序关系 则称A为偏序集 记为 例 集合A 2 4 6 8 上的小于等于关系 偏序 例2 66 判断下列关系是否为偏序关系 集合A的幂集合P A 中元素之间的包含关系 实数集合R上的小于等于关系 实数集合R上的大于等于关系 自然数集合N上的模n同余关系 人群中的 父子 关系 例2 67 判断集合A 2 3 4 5 6 8 上的整除关系是否为偏序关系 并用关系矩阵和关系图表示 解 集合A上的整除关系为R 该关系具有自反性 反对称性和传递性 所以 它是偏序关系 该关系的关系矩阵和关系图表示如下 可比 盖住 定义2 29设R为非空集合A上的偏序关系 对于任意元素x y A 如果 R或 R 则称x与y是可比的 如果 R且 R 则称x与y是不可比的 若x y且x y 则称x排在y的前面 记作x y 读作 x小于y 若x y且不存在元素z A使得x z且z y 则称y盖住x 设R为非空集合A上的偏序关系 对于任意元素x y A 可能出现以下几种情况 x y 或y x x y x与y不是可比的 例2 68 考察集合A 2 3 4 5 6 8 上的整除关系R 可比的情况 不可比的情况 盖住的情况 哈斯图 对偏序关系的关系图可进行如下简化 自反 可以将各顶点上的环全部略去 反对称 边为单向 可以规定向上方向为箭头方向 省略箭头 传递 可以将由传递性导出的边省去 将经过上述简化后得到的关系图称为哈斯图 哈斯图的绘制步骤 1 以 表示元素 2 若x y 则y画在x的上层 3 若y盖住x 则连线 4 不可比的元素可画在同一层 例 对于集合A 2 3 4 5 6 8 上的整除关系 画出其哈斯图 解 集合A上的整除关系为R 该关系具有自反性 反对称性和传递性 所以 它是偏序关系 该关系的关系矩阵和关系图表示如下 哈斯图 例2 70 绘制如下偏序关系的哈斯图 集合A 1 2 3 4 6 12 上的整除关系 集合A 2 3 4 5 8 上的大于等于关系 集合A 2 3 6 12 24 36 上的整除关系 集合A a b c 的幂集P A 上的包含关系 解 偏序关系 和 的哈斯图绘制于图 偏序集中的8个特殊元素 最大元 最小元 定义2 30对于偏序集和集合A的任意子集B 如果存在元素b B 使得任意x B都有x b 则称b为B的最大元素 简称为最大元 如果存在元素b B 使得任意x B都有b x 则称b为B的最小元素 简称为最小元 例2 71 对于例2 70中偏序关系 即集合A 1 2 3 4 6 12 上的整除关系 令B1 1 6 B2 1 2 3 B3 4 6 12 B4 2 4 6 B5 1 2 6 12 B6 1 2 3 4 6 12 分别求出B1 B2 B3 B4 B5和B6的最大元和最小元 解 对于集合B1 1 6 最大元为6 最小元为1 对于集合B2 1 2 3 元素2和3不可比 所以 不存在最大元 最小元为1 对于集合B3 4 6 12 元素4和6不可比 所以 不存在最小元 最大元为12 对于集合B4 2 4 6 元素4和6不可比 所以 不存在最大元 最小元为2 对于集合B5 1 2 6 12 最大元为12 最小元为1 对于集合B6 1 2 3 4 6 12 最大元为12 最小元为1 练习 对于例2 70中偏序关系 即集合A 2 3 6 12 24 36 上的整除关系 令B1 6 12 B2 2 3 B3 12 36 B4 2 3 6 B5 2 3 6 12 B6 2 3 6 12 24 36 求B1 B2 B3 B4 B5和B6的最大元和最小元 偏序集中的8个特殊元素 极大元 极小元 定义2 31对于偏序集和集合A的任意子集B 如果存在元素b B 使得B中不存在其它元素x满足b x 则称b为B的极大元素 简称为极大元 如果存在元素b B 使得B中不存在其它元素x满足x b 则称b为B的极小元素 简称为极小元 注意 最大 小 元vs 极大 小 元最大 小 元必须与B中每个元素都可比 极大 小 元无此要求 只要求没有比它更大或更小的元素 例2 73 对于例2 70中偏序关系 即集合A 1 2 3 4 6 12 上的整除关系 令B1 1 6 B2 1 2 3 B3 4 6 12 B4 2 4 6 B5 1 2 6 12 B6 1 2 3 4 6 12 分别求出B1 B2 B3 B4 B5和B6的极大元和极小元 解 对于集合B1 1 6 极大元为6 极小元为1 对于集合B2 1 2 3 极大元为2和3 极小元为1 对于集合B3 4 6 12 极大元为12 极小元为4和6 对于集合B4 2 4 6 极大元为4和6 极小元为2 对于集合B5 1 2 6 12 极大元为12 极小元为1 对于集合B6 1 2 3 4 6 12 极大元为12 极小元为1 练习 对于例2 70中偏序关系 即集合A 2 3 6 12 24 36 上的整除关系 令B1 6 12 B2 2 3 B3 12 36 B4 2 3 6 B5 2 3 6 12 B6 2 3 6 12 24 36 求B1 B2 B3 B4 B5和B6的极大元和极小元 偏序集中的8个特殊元素 上界 下界 定义2 32对于偏序集和集合A的任意子集B 如果存在元素a A 使得任意x B都有x a 则称a为子集B的上界 如果存在元素a A 使得任意x B都有a x 则称a为子集B的下界 注意 B的上 下 界不一定是B中的元素 例2 75 对于例2 70中偏序关系 即集合A 1 2 3 4 6 12 上的整除关系 令B1 1 6 B2 1 2 3 B3 4 6 12 B4 2 4 6 B5 1 2 6 12 B6 1 2 3 4 6 12 分别求出B1 B2 B3 B4 B5和B6的上界和下界 解 对于集合B1 1 6 上界为6和12 下界为1 对于集合B2 1 2 3 上界为6和12 下界为1 对于集合B3 4 6 12 上界为12 下界为1和2 对于集合B4 2 4 6 上界为12 下界为1和2 对于集合B5 1 2 6 12 上界为12 下界为1 对于集合B6 1 2 3 4 6 12 上界为12 下界为1 练习 对于例2 70中偏序关系 即集合A 2 3 6 12 24 36 上的整除关系 令B1 6 12 B2 2 3 B3 12 36 B4 2 3 6 B5 2 3 6 12 B6 2 3 6 12 24 36 求B1 B2 B3 B4 B5和B6的上界和下界 偏序集中的8个特殊元素 上确界 下确界 定义2 33对于偏序集和集合A的任意子集B 如果存在B的某个上界a 使得对于B的任意上界x都有a x 则称a为子集B的最小上界或上确界 记为sup B a 如果存在子集B的某个下界a 使得B的任意下界x都有x a 则称a为子集B的最大下界或下确界 记为inf B a 说明 令C是由B的所有上界组成的集合 则C的最小元c称为B的上确界 令C是B的所有下界的集合 则C的最大元c称为B的下确界 例2 77 对于例2 70中偏序关系 即集合A 1 2 3 4 6 12 上的整除关系 令B1 1 6 B2 1 2 3 B3 4 6 12 B4 2 4 6 B5 1 2 6 12 B6 1 2 3 4 6 12 分别求出B1 B2 B3 B4 B5和B6的上确界和下确界 解 对于集合B1 上确界为6 下确界为1 对于集合B2 上确界为6 下确界为1 对于集合B3 上确界为12 下确界为2 对于集合B4 上确界为12 下确界为2 对于集合B5 上确界为12 下确界为1 对于集合B6 上确界为12 下确界为1 练习 对于例2 70中偏序关系 即集合A 2 3 6 12 24 36 上的整除关系 令B1 6 12 B2 2 3 B3 12 36 B4 2 3 6 B5 2 3 6 12 B6 2 3 6 12 24 36 求B1 B2 B3 B4 B5和B6的上确界和下确界 8大元的性质 定理2 24对于偏序集和集合A的任意子集B 若b为B的最大元 则b为B的极大元 上界和上确界 若b为B的最小元 则b为B的极小元 下界和下确界 若a为B的上界且a B 则a为B的最大元 若a为B的下界且a B 则a为B的最小元 8大元的性质 定理2 25对于偏序集和集合A的任意子集B 若B有最大元 则B的最大元惟一 若B有最小元 则B的最小元惟一 若B有上确界 则B的上确界惟一 若B有下确界 则B的下确界惟一 若B为有限集 则B的极大元 极小元恒存在 全序 线序 关系 全序集 线序集 定义2 34对于偏序集 如果A中任意两个元素x和y都是可比的 即x y或者y x 则称该偏序关系为全序关系 或者线序关系 并称为全序集 线序集 或者链 当一个偏序关系是全序时 其哈斯图将集合中元素排成一条线 像一条链子 充分体现了其 链 的特征 例2 79 判断下列关系是否为全序关系 并给出其哈斯图 集合 2 3 4 6 8 12 上的整除关系R1 集合 2 3 5 7 9 上的大于等于关系R2 实数集合上的小于等于关系R3 集合 a b c 上的关系R4 解 关系 和 都是偏序关系 和 都是全序关系 不是全序关系 良序关系 良序集 定义2 35对于偏序集 如果A的任意一个非空子集都有最小元素 则称该偏序关系为良序关系 简称为良序 并称称为良序集 例2 80 判断下列关系是否为良序关系 集合 2 3 4 6 8 12 上的整除关系R1 集合 2 3 5 7 9 上的大于等于关系R2 实数集合上的小于等于关系R3 集合 a b c 上的关系R4 解 首先判断是否为偏序关系 然后再判断其任何一个非空子集是否都有最小元 和 是良序关系 良序集一定是全序集 有限的全序集一定是良序集 作业 P72第52题 1 2 第54题第56题R1 R2 R6 R7