《离散数学243(偏序关系)》由会员分享，可在线阅读，更多相关《离散数学243(偏序关系)（29页珍藏版）》请在金锄头文库上搜索。
1、主讲教师：常亮 E-mail: QQ：737059669 办公室电话: 2291071 手机: 13481395869 辅导教师：周小川 答疑时间：星期四 上午 10:20-11:50 答疑地点：5教5楼 软件工程教研室,离散数学,回顾,关系可能具有的性质： 自反 反自反 对称 反对称 传递 特殊关系：具有上述某些性质的关系 等价关系：自反、对称、传递 偏序关系：自反、反对称、传递,2.4.3 偏序关系,定义2.28 设R为非空集合A上的关系（即A并且RAA）。 如果R是自反的、反对称的和传递的， 则称R为A上的偏序关系。 一般用符号“”来表示偏序关系。 设 R 是一个偏序关系。如果R, 则
2、记为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 =, , 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关
3、系矩阵和关系图表示如下：,可比、盖住,定义2.29 设R为非空集合A上的偏序关系，对于任意元素x, yA， 如果R或R，则称x与y是可比的。 如果R且R，则称x与y是不可比的。 若xy且xy，则称x排在y的前面，记作xy，读作“x小于y”。 若xy且不存在元素zA使得xz且zy，则称y盖住x。 设R为非空集合A上的偏序关系，对于任意元素x, yA， 可能出现以下几种情况： xy（或yx）； x = y； x与y不是可比的。,例2.68,考察集合A=2, 3, 4, 5, 6, 8上的整除关系 R =, ,。 可比的情况： 不可比的情况： 盖住的情况：,哈斯图,对偏序关系的关系图可进行如下简化：
4、 自反：可以将各顶点上的环全部略去； 反对称：边为单向，可以规定向上方向为箭头方向，省略箭头； 传递：可以将由传递性导出的边省去。 将经过上述简化后得到的关系图称为哈斯图。 哈斯图的绘制步骤： （1）以“” 表示元素； （2）若xy，则y画在x的上层； （3）若y盖住x，则连线； （4）不可比的元素可画在同一层。,例,对于集合A=2, 3, 4, 5, 6, 8上的整除关系，画出其哈斯图。 解: 集合A上的整除关系为 R =, , 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关系矩阵和关系图表示如下：,哈斯图,例2.70:绘制如下偏序关系的哈斯图 集合A = 1, 2,
5、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， 如果存在元素bB，使得任意xB都有xb， 则称b为B的最大元素，简称为最大元； 如果存在元素bB，使得任意xB都有bx， 则称b为B的最小元素，简称为最小元。,例2.71,对于例2.70中偏序关系 （即集合A = 1, 2, 3, 4, 6, 12
6、上的整除关系）， 令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,
7、 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， 如果存在元素bB，使得B中不存在其它元素x满足bx， 则
8、称b为B的极大元素，简称为极大元； 如果存在元素bB，使得B中不存在其它元素x满足xb， 则称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的极大元和
9、极小元。 解: 对于集合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=
10、 2, 3, 6, 12、B6= 2, 3, 6, 12, 24, 36， 求B1、B2、B3、B4、B5和B6的极大元和极小元。,偏序集中的8个特殊元素(上界、下界),定义2.32 对于偏序集和集合A的任意子集B， 如果存在元素aA，使得任意xB都有xa， 则称a为子集B的上界； 如果存在元素aA，使得任意xB都有ax， 则称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=
11、 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上
12、的整除关系）， 令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都有ax， 则称a为子集B的最小上界或上确界，记为 sup(B) = a； 如果存在子集B的某个下界a，使得B的任意下界x都有xa， 则称a为子集B的最大下界或下确界，记为inf(B) = a。 说明： 令C是由B的所有上界组
13、成的集合， 则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
14、，下确界为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
15、为B的上界且aB，则a为B的最大元； 若a为B的下界且aB，则a为B的最小元。,8大元的性质,定理2.25 对于偏序集和集合A的任意子集B： 若B有最大元，则B的最大元惟一； 若B有最小元，则B的最小元惟一； 若B有上确界，则B的上确界惟一； 若B有下确界，则B的下确界惟一； 若B为有限集，则B的极大元、极小元恒存在。,全序(线序)关系 / 全序集(线序集),定义2.34 对于偏序集， 如果A中任意两个元素x和y都是可比的(即xy或者yx)， 则称该偏序关系为全序关系，或者线序关系； 并称为全序集、线序集、或者链。,当一个偏序关系是全序时，其哈斯图将集合中元素排成一条线，像一条链子，充分体现了其“链”的特征。,例2.79,判断下列关系是否为全序关系？并给出其哈斯图。 集合2, 3, 4, 6, 8, 12上的整除关系R1； 集合2, 3, 5, 7, 9上的大于等于关系R2； 实数集合上的小于等于关系R3； 集合a, b, c上的关系R4 =, , , , ,
