离散数学243(偏序关系)[20141015].pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * 主讲教师：常亮 E-mail: changl@guet.edu.cn QQ：737059669 办公室电话: 2291071 手机: 辅导教师：周小川 答疑时间：星期四 上午 10:20-11:50 答疑地点：5教5楼 软件工程教研室 离散数学 回顾 关系可能具有的性质： 自反 反自反 对称 反对称 传递 特殊关系：具有上述某些性质的关系 等价关系：自反、对称、传递 偏序关系：自反、反对称、传递 2.4.3 偏序关系 定义2.28 设R为非空集合A上的关系（即A??并且R?A?A）。 如果R是自反的、反对称的和传递的， 则称R为A上的偏序关系。 一般用符号“?”来表示偏序关系。 设 R 是一个偏序关系。如果x, y∈R, 则记为x ? y。 如果集合A上存在偏序关系，则称A为偏序集，记为A, ?。? 例：集合A={2,4,6,8}上的小于等于关系 ? = { 2,2, 2,4, 2,6, 2,8, 4,4, 4,6, 4,8, 6,6, 6,8, 8,8 }。 “偏序” 例2.66 判断下列关系是否为偏序关系 ① 集合A的幂集合P(A)中元素之间的包含关系“?”； ② 实数集合R上的小于等于关系“?”； ③ 实数集合R上的大于等于关系“?”； ④ 自然数集合N上的模n同余关系； ⑤ 人群中的“父子”关系。 例2.67 判断集合A={2, 3, 4, 5, 6, 8}上的整除关系是否为偏序关系？ 并用关系矩阵和关系图表示。 解: 集合A上的整除关系为 R ={2,2,2,4,2,6,2,8,3,3,3,6,4,4, 4,8,5,5,6,6,8,8} 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关系矩阵和关系图表示如下： 6 2 5 3 4 8 R 可比、盖住 定义2.29 设R为非空集合A上的偏序关系，对于任意元素x, y?A， 如果x, y?R或y, x?R，则称x与y是可比的。 如果x, y?R且y, x?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 ={2,2,2,4,2,6,2,8,3,3,3,6,4,4, 4,8,5,5,6,6,8,8}。 可比的情况： 不可比的情况： 盖住的情况： 哈斯图 对偏序关系的关系图可进行如下简化： ① 自反：可以将各顶点上的环全部略去； ② 反对称：边为单向，可以规定向上方向为箭头方向，省略箭头； ③ 传递：可以将由传递性导出的边省去。 将经过上述简化后得到的关系图称为哈斯图。 哈斯图的绘制步骤： （1）以“?”?表示元素； （2）若x?y，则y画在x的上层； （3）若y盖住x，则连线； （4）不可比的元素可画在同一层。 例 对于集合A={2, 3, 4, 5, 6, 8}上的整除关系，画出其哈斯图。 解: 集合A上的整除关系为 R ={2,2,2,4,2,6,2,8,3,3,3,6,4,4, 4,8,5,5,6,6,8,8} 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关系矩阵和关系图表示如下： 6 2 5 3 4 8 R 8 4 6 2 3 5 关系R的哈斯图 哈斯图 例2.70:绘制如下偏序关系的哈斯图 ① 集合A = {1, 2, 3, 4, 6, 12}上的整除关系； ② 集合A = {2, 3, 4, 5, 8}上的大于等于关系“?”； ③ 集合A = {2, 3, 6, 12, 24, 3