1、1离散数学离散数学Discrete Mathematics 主讲：陈哲云主讲：陈哲云青岛理工大学计算机工程学院青岛理工大学计算机工程学院2013.2013.0909第第4章章 二元关系二元关系二元关系二元关系4.1二元关系基本概念二元关系基本概念 (重点重点)4.2 关系的运算关系的运算4.3 关系的性质关系的性质 (重点重点)4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系(重点及难点重点及难点)4.6 函数的基本概念函数的基本概念偏序关系偏序关系l偏序关系偏序关系lHasse图（图（重点重点）l重要元素（重要元素（重点重点）l拓扑排序拓扑排序偏序关系偏序关系定义定义
2、 偏序关系：偏序关系：设设A上的二元关系上的二元关系R,如果如果R是是自反的自反的,反对称的反对称的，传递的传递的，则称，则称R为偏序为偏序关系关系，记为，记为“”,称为偏序称为偏序集。集。若若R，称，称“x小于等于小于等于y”，记作，记作x y。偏序关系偏序关系例例1 几个常见的偏序关系：几个常见的偏序关系：(1)A上的小于等于关系，上的小于等于关系，A=1,2,3,4,5,6：1=xy，x，yA (2)A上的整除关系，上的整除关系，A=1,2,3,4,5,6：2 x|y，x，yA(3)P(A)上的包含关系，上的包含关系，A=1,2,3：3s1 s2，s1，s2P(A)(4)任务集任务集S=
3、T1,T2,.,Tn 上的关系上的关系R4=|Ti=Tj或或Ti必须在必须在Tj之前完成之前完成 偏序关系偏序关系关于例关于例1(4)的一个举例：的一个举例：如完成室内闪光拍照的任务，任务集如完成室内闪光拍照的任务，任务集T包括任务：包括任务：1、打开镜头盖；、打开镜头盖；2、照相机调焦；、照相机调焦；3、打开闪光灯；、打开闪光灯；4、按下快门按钮。、按下快门按钮。在在T上定义关系上定义关系R：R如果如果i=ji=j或者任务或者任务i必须在任务必须在任务j之前完成。之前完成。则则R=,偏序关系偏序关系定义定义 设设R 为非空集合为非空集合A上的偏序关系上的偏序关系,x,yA,则则 x与与y可比
4、可比 x yy x 定义定义 设设R 为非空集合为非空集合A上的偏序关系上的偏序关系,x,yA,则则 y盖住盖住x x y 且不存在且不存在 zA 使得使得 x z yHasse（哈斯）图（哈斯）图例例2 设设A=2,3,6,12,24,36，“”是是A上的整除关系上的整除关系R，画出其关系图。，画出其关系图。关系图关系图2 23 36 61212363624242 23 36 6121236362424简化的关系图简化的关系图Hasse图图Hasse图图简化的关系图简化的关系图Hasse图（哈斯图）图（哈斯图）(1)自反性：自反性：每个顶点都有自回路，省去。每个顶点都有自回路，省去。(2)反
5、对称性：反对称性：两个顶点间只可能有一个箭头，两个顶点间只可能有一个箭头，从小到从小到 大大(或从低到高或从低到高)安置顶点，可省略箭头。安置顶点，可省略箭头。(3)传递性：传递性：由于有由于有，R，则，则R，故只画故只画，对应的边，省略边对应的边，省略边。Hasse图图Hasse图的画法图的画法“层次层次”与与“连线连线”(1)极小元放在第一层（最底层）。极小元放在第一层（最底层）。(2)若第若第n层已放好，则第层已放好，则第n+1层的元素满足至少能层的元素满足至少能盖住盖住第第n层的一个元素。（层的一个元素。（层次层次）(3)若若y盖住盖住x，则，则x，y之间连线。（之间连线。（连线连线）
6、注：注：哈斯图体现了偏序集中元素间的哈斯图体现了偏序集中元素间的“大小大小”和和“层次层次”关系。关系。Hasse图图例例3 画出例画出例1中各关系的中各关系的Hasse图：图：A1,2,3,4,5,6,7,8,9,Ba,b,c,S=1,2,3,4 1 x y，x，yA 2 x|y，x，yA 3s1 s2，s1，s2P(B)R 4=|Ti=Tj或或Ti必须在必须在Tj之前完成且之前完成且Ti,Tj S =,Hasse图图 1 2全序集全序集Hasse图图1243 3 4全序关系全序关系定义定义 全序关系全序关系任意两个元素都可比任意两个元素都可比 设设是一个偏序集，若对任意是一个偏序集，若对任
7、意x,yA，总有，总有x y或或y x，二者必居其一，则称，二者必居其一，则称“”“”为全序关系，或为全序关系，或者线序关系。称者线序关系。称为为全序集全序集，或者，或者线序集线序集，或者，或者链链。偏序集中的重要元素偏序集中的重要元素设偏序集设偏序集,B A，b表示相应的特殊元素，表示相应的特殊元素，lB的的极小元极小元B中没有比中没有比b 小的元素小的元素 bB 且且 x(x B x b)lB的的最小元最小元B中所有的元素都比中所有的元素都比b大大 bB 且且 x(xBb x)l极大元和最大元类似定义。极大元和最大元类似定义。注：注：上述元素都在上述元素都在B中寻找。中寻找。偏序集中的重要
8、元素偏序集中的重要元素设偏序集设偏序集,B A，b表示相应的特殊元素，表示相应的特殊元素，lB的的上界上界B中所有的元素都比中所有的元素都比b小小 bA 且且 x(xBx b)lB的的上确界上确界 上确界上确界B的上界的最小元的上界的最小元l下界和下确界类似定义。下界和下确界类似定义。注：注：上述元素都在上述元素都在A中寻找。中寻找。偏序集中的重要元素偏序集中的重要元素例例4 设偏序集设偏序集，求，求A的极小元、极大元、最小元的极小元、极大元、最小元、最大元。设、最大元。设B b,c,d,求求B的下界、上界、下确界的下界、上界、下确界、上确界、上确界.解：解：极小元：极小元：a,b,c,g；极
9、大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界和下确界都不存在；的下界和下确界都不存在；上界有上界有 d 和和 f,上确界为上确界为 d.偏序集中的重要元素偏序集中的重要元素性质：性质：(1)对于有穷集，极小元和极大元一定存在，可能存在对于有穷集，极小元和极大元一定存在，可能存在多个。多个。(2)最小元和最大元不一定存在，如果存在一定惟一。最小元和最大元不一定存在，如果存在一定惟一。(3)最小元一定是极小元；最大元一定是极大元。最小元一定是极小元；最大元一定是极大元。(4)孤立结点既是极小元，也是极大元。孤立结点既是极小元，也是极大元。(5)下界、上界、下确界、上确界
10、不一定存在，存在不下界、上界、下确界、上确界不一定存在，存在不一定唯一。一定唯一。(6)下确界、上确界如果存在，则惟一。下确界、上确界如果存在，则惟一。偏序集中的重要元素偏序集中的重要元素练习练习 的的Hasse图如下所示图如下所示，讨论当讨论当B取取相应相应集合时，其集合时，其最大元，最小元，极大元，极小元，上界最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。，下界，上确界，下确界。B1=a,b,B2=a,b,c,B3=a,b,c,d,B4=b,c,d,f,B5=a,c,f,i abcdefghiB极小元极小元极大元极大元最小元最小元最大元最大元a,ba,b,ca,ba,b无无无
11、无a,bc无无ca,b,c,db,c,d,fa,c,f,ia,bc,d无无bfbaia无无fiabcdefghi 无无bB上界上界下界下界上确界上确界下确界下确界a,ba,b,cc,d,e,f,g,h,i 无无无无c,e,f,h,i无无c无无a,b,c,db,c,d,fa,c,f,if,h,i 无无f无无f,h,i bfiai aabcdefghi小结小结l偏序关系是偏序关系是“次序次序”关系，但不一定是关系，但不一定是“全序全序”关系关系。l哈斯图是偏序集的简化图，通过哈斯图是偏序集的简化图，通过“层次层次”关系来表达关系来表达元素的元素的“大小大小”关系。关系。l偏序集中的特殊元素可以通过哈斯图来寻找。偏序集中的特殊元素可以通过哈斯图来寻找。作业作业1.下图中给出了偏序集下图中给出了偏序集的的Hasse图。图。(1)试分别以集合、关系矩阵、关系图三种方式写出该偏试分别以集合、关系矩阵、关系图三种方式写出该偏序关系；序关系；(2)求求A的最大、最小元（若存在的话）；的最大、最小元（若存在的话）；(3)求求A的极大、极小元；的极大、极小元；(4)求子集求子集 b,c,d,c,d,e 和和 a,b,c的上下界以及的上下界以及上下确界。上下确界。abced
