离散数学第2章关系

1、1,第2章 关 系,2,考察日常生活和科学技术中的“关系”： 人与人之间有： 父子关系 兄弟关系 师生关系 两数之间有： 大于关系 等于关系 小于关系,3,集合之间有： 包含关系 相等关系 元素与集合之间有： 属于关系 函数之间有： 调用关系 ,4,关系联系:事物间的多值对应。 本章讨论的是： 用集合理论刻画这些“联系”所建立的最一般的数学模型关系，这也是计算机科学中数据描述和信息处理的最常用的数学模型。,5,2.1 关系的概念 2.1.1 n元关系,设A1, A2 , An是集合，则称A1A2An的任意一个子集R为A1, A2 , An间的n元关系。,集合A1, A2, , An叫做关系的域

2、, n叫做它的阶。 若R An, 则称R为A上的n元关系。,6,可以利用n元关系表示计算机的数据库: 数据库由记录组成，这些记录是由字段构成的n元组。字段是n元组的数据项。,7,例 设R是ANSDT 的子集，其中A是所有航空公司的集合，N是航班号的集合，S是出发地的集合，D是目的地的集合，T是起飞时间的集合。则R是由5元组(a, n, s, d, t)组成的表示飞机航班的关系。 例如，设R表示由国内航空公司飞机航班构成的关系，如果南方航空公司在15:00有从广州到北京的2963航班，那么 ( 南方航空，2963，广州，北京，15:00) 属于R。,8,若 (a, b)R, 则称a与b有关系R,

3、 记为aRb; 若 (a, b)R, 则称a与b没有关系R, 记为aRb。,设有两个集合A和B，其笛卡儿积AB的任意一个子集R称为从A到B的一个二元关系（relation from A to B）。即: R AB 特别地，当AB时，R称为A上的关系（relation on A ）, 这时 R A2,2.1.2 二元关系,9,直观地看，二元关系就是反映“多值对应”的二维表，例如， 学生选课表：,10,把学生选课表用集合来表示： R= （张三,离散数学）, （李四,微积分）, （张三,高级语言）, 序偶的集合R同样也刻画了学生集合A=张三，李四，与课程集合B=离散数学，微积分，高级语言，之间“多值

4、对应”的联系。,11,【例】 设A1, 2, 3, 4, 5, Ba, b, c, 则 R1(1,a),(1,b),(2,b),(3,a) 是从A到B的关系,而 R2(a,2),(c,4),(c,5) 是从B到A的关系。,12,【定义】 设RAA, 1) 当R 时, 称R为A上的空关系; 2) 当RAA=A2时, 称R为集合A上的全域关系, 用EA表示。显然EA (x,y)|xA 且 yA 3) 若R(x, x)|xA, 则称R是A上的恒等关系, 用A表示。,13,【例】设A1, 2, 3, 4, 5，R是A上的二元关系，其定义为：当a，b A且a能整除b时，(a, b) R（R称为A上的整除

5、关系），求R。,14,【例】设A1, 2, 3, 4, 5, 6，R是A上的二元关系，其定义为：当a，b A且a和b被3除后余数相同时，(a, b) R（R也称为A上的模3同余关系, 记为3），求R。,15,设R是一个二元关系， (1) R中所有序偶的第一元素构成的集合称为R的定义域（ domain），记做dom R。 (2) R中所有序偶的第二元素构成的集合称为R的值域（range），记做ran R。,2.1.3 关系的定义域、值域,例如：A=a, b, c, d，B=1, 2, 3， R(a,2), (b,2), (c,1)，则： dom R=a, b, c，ran R=1,2,16,2.

6、1.4 关系表示 1、关系图 2、关系矩阵,17,1. 关系图 情形1：R是从A到B的关系, 采用如下的图示: 1）用大圆圈表示集合A和B，里面的小圆圈（或实心圆）表示集合中的元素; 2）若aA，bB，且(a,b)R，则在图中将表示a和b的小圆圈用直线或弧线连接起来, 并加上从结点a到结点b方向的箭头。,18,例如： A=a1, a2, a3, a4 B=b1, b2, b3, b4, b5 R=(a1, b1), (a2, b3), (a3, b2), (a4, b4), (a4, b5),19,情形2：R是A上的关系, 其画法如下: 1) 集合A中的每一个元素a用带有元素符号的顶点(称作顶

7、点a)表示。 2) 若a, bA, 且(a,b)R, 则将顶点a和顶点b用一条带有箭头的有向边连接起来, 其方向由顶点a指向顶点b。,20,【例】A=a1, a2, a3, a4, a5， R=(a1, a1), (a1, a2), (a2, a3), (a3, a4), (a4, a1), (a4, a5), (a5, a3)。 求R的关系图。,21,2. 关系矩阵 ：由表格法抽象而来 【定义】设集合Ax1,x2,xm, By1,y2, yn, R是从A到B的关系, 则mn矩阵MR(mij) mn叫R的关系矩阵, 其中:,22,【例】 设A1,2,3,4,5, Ba,b,c,求下面两个关系的

8、关系矩阵。 A到B的关系: R1(1,a),(1,b),(2,b),(3,a) B到A的关系: R2(a,2),(c,4),(c,5),23,设集合Aa1, a2, , an, 对于A上的关系R, 其关系矩阵MR(mij)nn是nn的, 其中:,【例】 求A1, 2, 3, 4上的关系、 EA和IA的关系矩阵。,24,2.1.5 函数的关系定义 函数如何转换成关系? 【例2-15】A = a, b, c, B = 1, 2, 3, f: A B, f(a) = 2, f(b) = 3, f(c) = 3. 注意： 一般来说, A到B的关系不是A到B的函数.,25,A到B的关系f 满足: (1)

9、 dom f = A; （像的存在性） (2) 对任意xA，若 (x, y1)f 且 (x, y2)f, 则y1 =y2； （像的唯一性） 则称f 为A到B的函数。,关系如何转换成函数?,26,作业： P44: 1, 3, 7，13(1)(2),27,2.2 关系的运算,2.2.1. 关系的集合运算 设 注意：,28,可以用n元关系上的集合运算构造新的n元关系。 例 设A和B分别是学校的所有学生和所有课程的集合。假设: R1由所有有序对(a,b)组成，其中a是选修课程b的学生; R2由所有的有序对(a,b) 构成，其中课程b是a的必修课。 问关系R1R2，R1R2，R1R2 ，R2R1，R1R

10、2是什么?,29,解 关系R1R2由所有的有序对(a,b) 组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。 R1R2是所有有序对(a,b)的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。,30,R1R2是所有有序对(a,b)的集合，其中a已经选修了课程b，但b不是a的必修课。 R2R1是所有有序对(a,b)的集合，其中b是a的必修课，但a没有选它。 R1R2由所有的有序对(a,b)组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但是a没有选修它。,31,如何用关系矩阵实现关系的集合运算?,记关系R的关系矩阵为MR= (u

11、ij)mn，关系S的关系矩阵为MS = (vij)mn ，则 1) RS 的关系矩阵M RS 是MR与MS的按位或(布尔和): M RS = MR+ MS= (uij + vij)mn = (uij vij)mn,布尔和,逻辑或,布尔和,32,2) RS 的关系矩阵M RS 是MR与MS的按位与(按位布尔积): M R S = (uij vij)mn = (uij vij)mn 3) 的关系矩阵M 是MR的按位取反: 把每个1改为0，每个0改为1 4) 利用AB A , 可计算MR-S 及MRS,布尔积,逻辑与,33,2.2.2 关系的逆运算,设R是A到B的二元关系，如果把R中的每一个有序对中

12、的元素顺序互换，所得到的B到A的二元关系称为R的逆关系，记作R-1。,例: R表示“课程-学生”关系，则R-1是“学生-课程”关系。,34,【例】A=a, b, c，B=x, y, z，R是A到B的二元关系，且有： R=(a, x), (b, y), (c, y)， 则R-1是B到A的二元关系，且有： R-1=(x, a), (y, b), (y, c) 【例】A=1, 2, 3，R是A上的二元关系，且有： R=(1, 2), (2, 3), (3, 1) 则其逆关系为： R-1=(2, 1), (3, 2), (1, 3),35,逆关系R-1的关系矩阵与关系R的关系矩阵有何联系？,如果二元关

13、系R的关系矩阵为MR，则MR的转置矩阵MRT就是逆关系R-1的关系矩阵。,36,【定理2-2】 【定理2-3】 (1) (2) (3) R是A上的关系, 则,37,R是集合A到B的二元关系，S是集合B到C的二元关系，R和S的复合R S 定义为 R S = (x, z) | y B使得(x, y)R且(y, z)S 它是A到C的二元关系。,2.2.3 关系的复合运算 1. 关系R和S的复合,38,例: R表示“教师-课程”关系， S表示“课程-学生”关系， 则RS 是 “教师-学生”关系。 例: R表示“父子”关系， 则RR 是 “祖孙”关系。,39,例: R表示“教师-课程”关系， S表示“课

14、程-学生”关系， T表示“学生-家长”关系， 则(R S) T 是 “教师-学生家长”关系。 例: R表示“父子”关系， 则(RR) R是什么关系?,40,例: 设A1, 2, 3, 4, B2, 3, 4, C1, 2, 3, R(a, b)|(a, b) AB 且 (ab4) S(b, c)|(a, b) BC 且 (|bc|1) 求R S 。 解: R(1, 3), (2, 2) S(2, 1), (3, 2), (4, 3), (2, 3) R S (1, 2), (2, 1), (2, 3) 复合关系R S的图示如图所示。,41,复合关系,R S,42,2.复合关系的矩阵表示 设A=

15、a1, a2, , am，B=b1, b2, , bn，C=c1, c2, , cs，R是A到B的二元关系，R的关系矩阵为：,其中：,1 (ai, bj) R 0 (ai, bj) R,43,S是B到C的二元关系，S的关系矩阵：,其中：,1 (bi, cj) S 0 (bi, cj) S,44,令：,则有： 当u11v11=1 或 u12v21=1 或 或 u1nvn1=1 时 w11=1； 当u11v11=0 且 u12v21=0 且 且 u1nvn1=0 时 w11=0； 一般地有： 当ui1v1j=1 或 ui2v2j=1 或 或 uin vnj=1 时 wij=1； 当ui1v1j=0

16、 且 ui2v2j=0 且 且 uin vnj=0 时 wij=0；,45,引入布尔加法(逻辑或)（即0+0=0，1+0=0+1=1，1+1=1），则： w11=1 当且仅当 u11v11+ u12v21+ + u1nvn1=1； 一般地 wij=1 当且仅当 ui1v1j+ ui2v2j+ + uin vnj=1； 这说明：复合关系R S 的关系矩阵 MR S =MRMS 其中是矩阵的布尔乘法（矩阵的逻辑乘法）。,46,【例】A=1, 2, 3，B=a, b, c, d，C=x, y, z，R是A到B的二元关系，R=(1, a), (1, b), (2, b), (3, c)，S是B到C的二

17、元关系，S=(a, x), (b, x), (b, y), (b, z)。 则有：,47,【例】A=1, 2, 3, 4，R和S都是A上的二元关系 R=(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (4, 3), (4, 4) S=(1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (4, 3) 则有：,48,设R是A到B的二元关系，S是B到C的二元关系， T是C到D的二元关系，则： (R S) T = R (S T),二元关系与其关系矩阵是一一对应的，复合关系RS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法运算满足

18、结合律，所以关系的复合也满足结合律，即：,49,设 R AB，则： (1) IA R = R (2) R IB = R,设R是A到B的二元关系，S是B到C的二元关系，则(R S)-1 = S-1 R-1。,50,设R是A上的关系，n为自然数，则R 的n 次幂定义为： (1) R0 = (x,x) | x A = IA (2) Rn+1 = Rn R,由于二元关系的复合满足结合律，所以二元关系的幂运算是有意义的。,3. 关系的幂运算,51,【例】 设R是世界上所有人的集合上的关系，如果a认识b，那么R包含(a,b)。问Rn是由怎样的序偶构成的?其中n是大于等于2的正整数。 解 如果存在人c，使得

19、(a,c)R且(c,b) R，即存在人c使得a认识c，c认识b，那么关系R2包括(a,b)。 类似地，如果存在人x1，x2，xn-1使得a认识x1，x1认识x2， ，xn-1认识b，那么Rn包含对(a,b)。,52,【例】 设R是广州市所有地铁站的集合上的关系。如果可以从站a不换车就旅行到站b，那么R包含对(a,b)。当n是正整数时， Rn是由怎样的序偶构成的? 解 如果经过至多n-1次换车就可以从站a旅行到站b，关系Rn就包含(a,b)。,53,设R是A上的关系，m,n N，则 (1) Rm Rn = Rm+n (2) (Rm)n = Rmn (3) (Rm)-1 = ( R-1) m,54

20、,作业： P51: 1, 3, 11,55,设R是A上的关系, (1) 若对于所有的xA, 都有(x,x)R , 则称R是自反的(reflexive) 。 (2) 若对于所有的xA, 都有(x,x) R, 则称R是反自反的(irreflexive) 。,2.3 关系的性质,56,【例】 设A1,2,3, R1 , R2 , R3 是A上的关系，其中 R1(1, 1), (2, 2) R2(1, 1), (2, 2), (3, 3), (1, 2) R3(1, 3) 说明它们是否为A上的自反关系或反自反关系。 【例】全域关系EA , 恒等关系A是A上的自反关系; 小于等于关系A ,整除关系DA是

21、A上的自反关系; 小于关系 A是反自反关系。,57,分析上述关系的关系图和关系矩阵，可得出结论: 若关系R是自反的, 当且仅当其关系图中每个结点都有自回路(环), 其关系矩阵中, 主对角线上的元素均为; 若关系R是反自反的, 当且仅当其关系图中每个结点都没有自回路(环), 其关系矩阵中, 主对角线上的元素全为。 注意, 一个关系不是自反的, 不一定就是反自反的。,58,设 R AA，则： (1) R自反 IA R. (2) R反自反 IAR = .,59,设R是A上的关系， (1) 若对于任意的x, yA, 每当(x,y)R 时就有 (y,x)R, 则称R 是对称的(symmetric) 。

22、(2) 若(x,y)R 且xy时, 必有(y,x) R, 则称R是反对称的(antisymmetric) 。,60,【例】 设A1,2,3, R1 , R2 , R3 , R4是A上的关系，其中 R1(1, 1), (2, 2) R2(1, 1), (1, 2), (2, 1) R3(1,2), (1, 3) R4(1,2), (2,1), (1, 3) 说明它们是否为A上的对称关系或反对称关系。,61,【例】全域关系EA , 恒等关系A是A上的对称关系; 小于等于关系 A ,整除关系DA是A上的反对称关系。,62,分析这些关系的关系矩阵和关系图，可得出结论: 若关系R是对称的, 当且仅当其关

23、系图中, 若有顶点a到顶点b的边, 则一定有顶点b到顶点a的边, 其关系矩阵是一个对称矩阵。 若关系R是反对称的, 当且仅当其关系图中, 若有顶点a到顶点b的边, 则一定没有顶点b到顶点a的边, 其关系矩阵关于主对角线对称的元素不同时为, 即当rij=(ij)时, 必有rji=。,63,设 R AA，则： (1) R对称 R = R-1. (2) R反对称 RR-1 IA .,64,设R是A上的关系, 若对任意x, y, zA, 每当(x,y)R且(y,z)R时，就有(x,z)R, 则称R是传递的(transitive) 。,关系图上传递的特征： 如果顶点x到y有边，y到z有边，则x到z也有边

24、。,65,【例 】 设A1,2,3, R1 , R2 是A上的关系，其中 R1(1, 1), (1, 2), (1, 3), (2, 3) R2(1, 1) , (2, 2), (2, 3), (3, 2) 说明它们是否为A上的传递关系。,66,【例 】全域关系EA , 恒等关系A ，小于等于关系 A ,整除关系DA，包含关系是传递的。,67,设 R AA，则： R传递 RR R,68,【示例】 判断下列关系的性质: 1) 实数集上的“”关系, 2) 实数集上的“”关系, 3) 实数集上的“”关系。 解 : 1) “”关系是自反、 对称、 传递的。 2) “”关系是自反、 反对称、 传递的。

25、3) “”关系是反自反、 反对称、 传递的。,69,【例】 若Aa, b, c, d, A上的3个关系为： R1(a, a), (a, b), (c, b), (d, a), (d, b) R2(a, a), (a, b), (a, d), (c, b) R3(a, a), (a, b), (a, d), (b, c), (d, b) 说明它们是否为A上的传递关系。,70,分析它们的关系图： 则可判断出R1和R2是传递的, R3不是传递的（ (a, b), (b, c) ）。,71,练习：作出下列关系的关系图和关系矩阵, 并判断其性质: 1) A1, 2, 3, 4, 5, R是A上关系, R

26、=(a, b)|(a, b)A2且,2) A0, 1, R是集合2A上的“ ”关系。,72,解 1) R=(1, 1), (1, 4), (2, 2), (2, 5), (3, 3), (4, 1), (4, 4), (5, 2),(5, 5) 画出关系图，写出关系矩阵。 由关系图可知, R是自反、 对称、 传递的。,73,解 2) 2A, 0, 1, 0, 1 令 A1, A20, A31, A40, 1 则 R=(A1, A1), (A1, A2), (A1, A3), (A1, A4), (A2, A2), (A2, A4), (A3, A3), (A3, A4), (A4, A4) 画

27、出关系图，写出关系矩阵。 由关系图可知, R是自反、 反对称、 传递的。,74,作业： P58: 8，9,75,2.4 关系的闭包,任给一个A上的关系R, R不一定具有自反、对称或传递等性质。 希望在R中增加一些序偶，得到一个包含R的新关系R: 1) R具有自反(对称、传递)性质 2) R同原关系R尽可能接近(亦即增加的序偶尽可能少) 这就是闭包的思想，即： 闭包具有某种性质（如对称性）的最小扩充关系。,76,设R、 R是集合A上的关系，如果满足： (1) R是自反的（对称的或传递的） (2) R R (3) 对A上任何包含R的自反（对称或传递）关系R”，均有：R R ，则称R是R的自反（对称

28、或传递）闭包。,2.4.1 闭包的定义,77,一般的， R的 自反(reflexive)闭包记为r(R) 对称(symmetric)闭包记为s(R) 传递(transitive)闭包记为t(R),78,例1 R表示中山市所有居民组成的集合上“父母-子女”的亲子关系， 问t(R)是什么关系？ 先辈-后代关系 例2 设R是广州市所有地铁站的集合上的关系。如果可以从站a不换车就旅行到站b，那么R包含对(a,b)。问t(R) 是什么? 可达关系,79,2.4.2 闭包的构造 【定理2-14,15,16】 设R为集合A上的关系, 则有 1) r(R) RIA 2) s(R) RR-1 3) t(R) R

29、R2R3,80,【例】 设A1, 2, 3, 4, 5, R是A上的关系, R(2, 1), (2, 4), (2, 5), (3, 4), (4, 4), (5, 2), 求r(R), s(R), t(R) , 并作出它们及R的关系图。 解: r(R) RIA (2, 1), (2, 4), (2, 5), (3, 4), (4, 4), (5, 2), (1, 1), (2, 2),(3, 3), (5, 5),81,R1(1, 2), (4, 2), (5, 2), (4, 3), (4, 4), (2, 5) s(R) RR1 (1, 2), (2, 1), (2, 4), (2, 5

30、), (3, 4), (4, 2), (4, 3), (4, 4), (5, 2),82,R2(2, 2), (2, 4), (3, 4), (4, 4), (5, 1), (5, 4), (5, 5) R3(2, 1), (2, 4), (2, 5), (3, 4), (4, 4), (5, 2), (5, 4) R4(2, 2), (2, 4), (3, 4), (4, 4), (5, 1), (5, 4), (5, 5) R2 继续做下去显然有 R2n+1=R3 R2n=R2 (n1, 2, ) t(R) = RR2R3 = RR2R3 = (2, 1), (2, 4), (2, 5),

31、 (3, 4), (4, 4), (5, 2), (2, 2), (5, 1),(5, 4), (5, 5),83,图 R, r(R), s(R), t(R) 的关系图,84,设 |A| = n1，R AA，则： t(R) RR2 Rn.,85,2.4.3 闭包的矩阵计算 设关系R的关系矩阵为M, r(R)、 s(R) 和 t(R)的关系矩阵分别为Mr、Ms和Mt，则 Mr=M+I Ms=M+MT Mt=M+M2+M3+ 其中“”为布尔加。,86,【例2-44】P62,87,作业： P64: 2, 3,10,88,2.5 等价关系,实数集R上的“”关系, 三角形集合中的全等关系等同时具有自反、

32、对称和传递的特性, 这是一种重要而常见的关系。,89,设R是A上的关系, 若R具有： （1）自反性 （2）对称性 （3）传递性 则称R是A上的等价关系。 若有(a, b)R, 则称a与b等价。,显然, 对任何集合A, A上的恒等关系IA 和全域关系EA 是等价关系。,2.5.1 等价关系的定义,90,【例】设Aa, b, c, d, e, f, g，A中元素分别表示7位大学生，其中a，b，c都姓张，d和e都姓李，f和g都姓王。 如果同姓氏的大学生认为是相关的，不同姓氏的大学生是无关的，那么这种同姓关系R是等价关系。,91,【例】设Aa, b, c, d, e, f, g，A中元素分别表示7位大

33、学生，其中a，c，d，f 都是20岁，b，e，g都是23岁。 如果年龄相同的大学生认为是相关的，不同年龄的大学生是无关的，那么这种同龄关系R是等价关系。,92,“血缘关系”是否是等价关系?,解：否,93,【例】设A=1,2,8，定义A上的关系R如下： R = (x,y) | x,yA 且 x 3 y 可以验证R为等价关系。,若把A中元素按除3后的余数进行分组，则可以 得到3, 6, 1, 4, 7, 2, 5, 8。可见一个等价关系一定可以确定一种分组，等价关系就是分组后的同组关系。,94,2.5.2 等价类(equivalence classes),设R是A上的等价关系, aA, 称集合 x

34、| xA 且 aRx 为元素a关于R的等价类, 记为 aR 。,由定义知, aR是A中所有与a等价的元素x组成的集合。,95,【例】设A=1,2,8，定义A上的关系R如下： R = (x,y) | x,yA 且 x y(mod 3) 则A中各元素关于R的等价类分别为： 1R = 4R = 7R = 1, 4, 7 2R = 5R = 8R = 2, 5, 8 3R = 6R = 3, 6,96,【例】 设A是全院学生构成的集合, R为A上的关系：如果x与y是主修同一专业的学生，则xRy。那么 (1) R是等价关系 (2) R将A中的学生分为不相交的子集（等价类），其中每个子集包含了某个特定专业

35、的所有学生。 例如，一个子集（等价类）包含了所有（主修）软件工程专业的学生，另一个子集（等价类）包含了所有网络工程专业的学生。,97,设R是A上的等价关系, 则等价类的集合xR | xA称为A关于R的商集, 用A/R表示(读作A模R)。,前例中，A/R分别是： A/R= 1, 4, 7， 2, 5, 8， 3, 6 A/R= 软件工程专业的学生， 网络工程专业的学生，.,98,设R是集合A上的等价关系, 则商集A/R 构成A的一个划分。,前例中， A/R= 1, 4, 7， 2, 5, 8， 3, 6 A/R= 软件工程专业的学生， 网络工程专业的学生，. 分别构成A的划分。,99,等价关系导

36、出的等价划分是唯一的; 反之, 给出集合A的一个划分, 存不存在相应的等价关系呢？,100,设A1, A2, , Am是集合A的一个划分, 定义R为: R(a, b)|a, b属于同一划分块Ai, i1, 2, , m 则R是A上的等价关系且A/R。,所以, A上的等价关系与集合A的划分是一一对应的。等价关系实质上是同组关系。,101,【思考题】 在你们班所有同学构成的集合上定义3个等价关系，并确定关于这些等价关系的等价类。,同龄，同桌，同性，同乡，同舍，同社团（非社团）,102,作业： P68: 2，4，8,103,设R是A上的关系, 且满足： （1）自反性； （2）反对称性； （3）传递性

37、； 则称R是A上的一个偏序关系, 简称为偏序(partial order), 常记为“”并读作“小于等于”。,2.7 偏序关系,2.7.1 偏序关系的定义,104,集合A和A上的偏序一起称为一个偏序集(partially ordered set, poset), 用(A, )表示。 【示例】 小于等于关系LA ,整除关系DA是偏序关系； P(A)上的“”关系是偏序关系。,105,设（A, ）是偏序集, 若对任意的x, yA, 有xy或yx , 则称是线性序关系(linear order)，又称全序关系。,注：全序关系的哈斯图是一条直线，故称为线性序关系。,106,例： 小于等于关系LA 是全序

38、关系； 整除关系DA一般不是全序关系； P(A)上的“”关系一般不是全序关系。,107,设（A, ）是偏序集，x, y A，若下列三个条件同时成立，则称元素y盖住x： （1）xy （2）xy （3）不存在异于x和y的元素zA，使得x z y。,y盖住x意味着y比x只“高（大）”一层（级）。,2.7.2 偏序集的哈斯图,108,记 COV(A) = (x, y)| x, y A且y盖住x.,109,【例】设A=1, 2, 3, 4, 6, 12，R是A上的整除关系。则R的关系图如下图（a）所示。,110,为了更清楚地表示偏序集中元素间的一种层次关系, 我们引入哈斯图(Hasse图) 。,哈斯(H

39、asse, 1898-1979), 生于德国。高中毕业后在海军服役。后在大学学习数论。对代数数论作出了基础性的贡献。二战时曾为德国海军从事应用数学研究。,111,哈斯图是一种简化的关系图： 1) 只画相邻层间的有向弧，自反性不在图中表示出来; 2) “大”的元素画在较“小”元素的上方（如果y盖住x，则在x和y之间连一条线）; 3) 有向弧简化为无向线段（方向性由上、下方体现）。,112,哈斯图的画法： 方法1: 从关系图开始， 1）去掉环； 2）去掉由传递性形成的有向弧； 3）重新排列顶点，使每条有向弧的始点在终点的下边； 4）去掉有向弧的箭头。,113,114,方法2: 1) 求出A上的盖住

40、关系 COV(A) = (x, y)| x, y A且y盖住x； 2) 按盖住关系COV(A)分层画出顶点，并用直线连接。,115,【例】设A=1, 2, 3, 4, 6, 8, 12, 24，R是A上的整除关系，画出R的哈斯图。 COV(A) = (1,2), (1,3), (2,4), (3,6), (4,8), (6,12), (8,24), (12,24),116,【例】设集合S=1, 2, 3，其幂集P(S)上的包含关系为偏序关系，请画出其哈斯图。,117,2.7.3 偏序集中的特殊元素 从前面例子的哈斯图可以看出, 偏序集中元素的结点层次清楚, 有的结点在哈斯图的最上层, 有的在最下层; 有的最上（下）层只有一个结点, 有的有多个结点。 下面我们将着重研究哈斯图中这些特殊位置上的结点。,118,设(A, )是偏序集, S A, b S。 1） b是S的最大元（greatest element) : x S ，都有 x b 。 2） b是S的最小元（least element) : x S ，都有 b x 。,119,【