离散数学--关系的性质

《离散数学--关系的性质》由会员分享，可在线阅读，更多相关《离散数学--关系的性质（32页珍藏版）》请在金锄头文库上搜索。

1、1,4.3 关系的性质,关系的性质及特点 关系性质的充要条件 关系性质的证明 运算和性质的关系,2,1. 自反的二元关系,(1).定义：R是上的二元关系，若x(xAR), 则称R在A上是自反的二元关系。,例如 a,b,c, R= (a,a),(b,b),(c,c),(a,b)， 则是自反的。,又如1,2,3, R是上的整除关系， 显然，是自反的，因为（1, 1）,（2, 2）,（3, 3） 都属于R。,即如果对于中的每一个元素a,都有(a,a) R，则称为自反的二元关系。,一、关系的性质及特点,3,注意，在关系的自反性定义中，要求对于A中 的每一个元素a都有(a,a) R。所以当A=a,b,c

2、，而 R=(a,a),(b,b)时，R并不是自反的，因为(c,c) R。,又如A=1,2,3，R是A上的二元关系，当a,bA， 且a和b都是素数时，(a,b) R。,可见(2,2),(3,3),(2,3),(3,2)，也不是自反关 系，因为(1,1) R。,4,(2). 关系矩阵的特点：,关系矩阵中主对角线上的元素全为1。,(3). 关系图的特点：,关系图中每个顶点都有环。,实例： A上的全域关系EA, 恒等关系IA，小于等于关系LA, 整除关系DA都是自反关系：,5,2反自反的二元关系,(1). 定义： R是上的二元关系，若x(xAR), 则称R在A上是反自反的二元关系.,例如a,b,c,

3、R= (a,b),(b,c),(b,a)，则是反自反的。,又如1,2,3, R是上的小于关系，即当ab时， (a,b) R。显然，是反自反的。,注意，非自反的二元关系不一定是反自反的二元关系， 因为存在着这样的二元关系，它既不是自反的又不是反自 反的，如=a,b,c,R=(a,a),(a,b)，那么不是自反的(因 为(b,b), (c,c)都不属于)，也不是反自反的(因为(a,a) R)。,即对于中的每一个元素a,都有(a,a) R，则称为 反自反的二元关系。,6,实例： 实数集上的小于关系，空关系，幂集上的 真包含关系都是反自反关系。,(2). 关系矩阵的特点：,关系矩阵中主对角线上的元素全

4、为0。,(3). 关系图的特点：,关系图中每个顶点都没有环。,7,例1 A=1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R3,R1既不是自反也不是反自反的,R2为自反关系,R3为反自反关系。,8,3. 对称的二元关系,(1). 定义: R是上的二元关系， 若x，y(x,yARR), 则称R为A上对称的二元关系.,例如=a,b,c,d, R=(a,a),(a,b),(b,a),(b,d),(d,b) 则是对称的二元关系。,又如=1,2,3,4,5,对于中元素a和b,如果a,b是模 3同余关系，则(a,b) , 易见是对称关系。,即如果(a,b) R, 就一定有(b,a

5、) R, 则称为对称的二元关系。,9,实例： A上的全域关系EA, 恒等关系IA和空关系 都是对称关系。,(2). 关系矩阵的特点：,关系矩阵为对称矩阵。,(3). 关系图的特点：,关系图中如果两个顶点之间有边一定是一对方向相反的边。,10,4反对称的二元关系,反对称的定义也可写为：是上的二元关系， 当ab时，如果(a,b) ,则必有(b,a) R, 称为反对称的二元关系。,例如=1,2,3,R是上的小于关系，即ab，（a,b）。 易见=(1,2),(1,3),(2,3),所以是反对称的。,又如是一些整数组成的集合，如果a整除b，则(a,b) , R也是反对称的。,(1). 定义：若 x，y(

6、x,yARRx=y), 则称R为A上的反对称关系.,11,注意，“对称的”和“反对称的”这两个概念并非相互对立， 相互排斥的。存在着既不是对称的又不是反对称的二元 关系，也存在着既是对称的又是反对称的二元关系。,又如A=a,b,c, R=(a,a), 可知是对称的，又是反对称的。,因为虽有(a,b) R, (b,a) R，但(c,d) R时(d,c) R, 因此R不是对称的，,例如 A=a,b,c,d R=(a,b),(b,a),(c,d) 这里R既不是对称的，也不是反对称的。,因为有(a,b) R和(b,a) R，因此R不是反对称的。,12,实例： 恒等关系IA，空关系都是A上的反对称关系。

7、,(2). 关系矩阵的特点：,关系矩阵中以主对角线对称的元素不能同时为1。,(3). 关系图的特点：,关系图中如果两个顶点之间有边一定是一条有向边。,13,例2 设A1,2,3, R1, R2, R3和R4都是A上的关系, 其中 R1,， R2, R3,， R4,R1 对称、反对称. R2 对称，不反对称. R3 反对称，不对称. R4 不对称、也不反对称.,14,5. 可传递的二元关系,(1). 定义： R是A上的二元关系，xyz(x,y,zARRR), 则称R是A上的传递关系.,例如整除关系是可传递的，因为每当（a，b） R时， 即 a 能整除 b，b能整除c时，显然 a 能整除 c， 所

8、以必有（a，c） R 。,又如A=a，b，c，d，e，其中a、b、c、d、e分别是表示 5个人，且a、b、c同住一个房间；d和e同住另一个房间。 如果同住一房间的人认为是相关的，显然这种同房间关系 是可传递的。,每当有(a,b) R和(b,c) R 时，必有(a,c) R ，则称为可传递的二元关系。,15,实例： A上的全域关系EA,恒等关系IA和空关系 小于等于关系, 小于关系，整除关系，包含关系， 真包含关系都是传递的二元关系。,(2). 关系矩阵的特点：,(3). 关系图的特点：,关系图中如果两个顶点xi到xj之间有边, xj到 xk之间有边,则从xi到xk之间有边。,16,关系性质判别

9、汇总,例3 设A1,2,3, R1, R2是A上的关系, 其中 R1, R2, ,R1 是A上的传递关系 R2不是A上的传递关系,18,例4 判断下图中关系的性质, 并说明理由.,(2)反自反，不是自反的；反对称，不是对称的；,(1)不自反也不反自反；对称, 不反对称；不传递.,(3)自反，不反自反；反对称，不是对称；不传递.,19,二、关系性质的充要条件,设R为A上的关系, 则 (1) R在A上自反当且仅当 IA R (2) R在A上反自反当且仅当 RIA= (3) R在A上对称当且仅当 R=R1 (4) R在A上反对称当且仅当 RR1IA (5) R在A上传递当且仅当 RRR,20,1.自

10、反性证明,证明模式 证明R在A上自反 任取x, xA . R 前提 推理过程 结论,例5 证明若 IA R ，则 R在A上自反.,三、关系类型的证明,证 任取x, xA IA R 因此 R 在 A 上是自反的.,21,2. 对称性证明,证明模式 证明R在A上对称 任取 R . R 前提 推理过程 结论,例6 证明若 R=R1 , 则R在A上对称.,证 任取 R R 1 R 因此 R 在 A 上是对称的.,22,3. 反对称性证明,证明模式 证明R在A上反对称 任取 RR . x=y 前提 推理过程 结论,例7 证明若 RR1IA , 则R在A上反对称.,证 任取 R R R R 1 RR 1

11、IA x=y 因此 R 在 A 上是反对称的.,23,4. 传递性证明,证明模式 证明R在A上传递 任取， RR . R 前提 推理过程 结论,例8 证明若 RRR , 则R在A上传递.,证 任取， R R RR R 因此 R 在 A 上是传递的.,思考1. 设A=a,b,c, R是A上的二元关系 且 R=(a,a),(b,b),(a,c),(c,a),问R是自反的吗？ 是反自反的吗？是对称的吗？是反对称的吗？ 是可传递的吗？,解：由于cR,但(c,c)R,所以R不是自反关系；,又由于 (c,a)R, (a,c)R,但(c,c) R, 所以R不是传递关系。,显然R是对称关系， R不是反对称关系

12、；,由于 (a,a) R, (b,b) R, 所以R也不是反自反关系；,思考2. 设A=a,b，写出 （1）A上所有的自反关系；（2）A上所有的反自反关系； （3）A上所有的对称关系；（4）A上所有的反对称关系。,解 （1） 由于AA= (a,a),(b,b),(a,b),(b,a)，,而A上的自反关系必须含有(a,a),(b,b)。,所以A上的自反关系共有4种。,它们是 (a,a),(b,b)， (a,a),(b,b),(a,b)， (a,a),(b,b),(b,a)， (a,a),(b,b),(a,b),(b,a)。,(2) 由于A上的反自反关系必须不含有(a,a),(b,b)。,所以A上

13、的反自反关系也有4种。,它们是(空关系)， (a,b)，(b,a)，(a,b),(b,a)。,(3) 由于A上的对称关系R, 当(a,b) R时,必有(b,a) R, 所以只需考虑在(a,a),(b,b),(a,b)中选取0个，1个，2个， 3个有序对构成的集合。,它们是空关系, (a,a), (b,b), (a,b) ,(b,a), (a,a),(b,b), (a,a),(a,b),(b,a)， (b,b),(a,b),(b,a), (a,a),(b,b),(a,b),(b,a)。,所以A上的对称关系有8种。,27,所以在AA的子集中删去同时含有(a ,b)和(b,a) 的子集 后，其它子集

14、都是反对称关系，共有12种。,即(空关系)， (a,a), (a,b), (b,a), (b,b), (a,a) ,(a,b), (a,a),(b,a), (a,a),(b,b), (a,b),(b,b), (b,a),(b,b), (a,a),(a,b),(b,b)， (a,a),(b,a),(b,b)。,（4）由于A上的反对称关系，当(a,b) R必有(b,a)R。,28,思考3. 设A=1，2，3，问在A上有多少种不同的自反关系？,解：当R是A上的自反关系时，R必须含有表格中对角线上的 3个小方格所表示的有序对，对于表格中余下的6个小 方格，可以依次选取1个，2个，6个小方格， 也可以不取，它们所表示的二元关系都是A上的自反关系，,因此，A上共有64个自反关系。,5.传递性的判定方法,判定定理1：设集合A=a1,a2, ,an，R是A上的二元关系，R 的关系矩阵为MR，令MR2 = MR MR，则R是A上的传递关系的充要条件是对MR2中1所在位置,MR中相应位置都是1。,例9：设A=a，b，c，d，e， R=, 试判断R的传递性。,判定定理2：设集合A=a1,a2 , ,an，R是A上的二元关系，R 的关系矩阵为MR， R是A上的传递关系的充要条件是若MR中的零元素aij=