离散数学--关系的性质.ppt

14.3 关系的性质l关系的性质及特点关系的性质及特点l关系性质的充要条件关系性质的充要条件l关系性质的证明关系性质的证明l运算和性质的关系运算和性质的关系.121.自反的二元关系自反的二元关系(1).定定 义义：R是是 上上 的的 二二 元元 关关 系系，若若 x(xA R),则称则称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，则则称称为自反的二元关系。为自反的二元关系。一、关系的性质及特点一、关系的性质及特点.23注意，在关系的自反性定义中，要求对于注意，在关系的自反性定义中，要求对于A中中的每一个元素的每一个元素a都有都有(a,a)R。所以当。所以当A=a,b,c，而，而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。.34(2).关系矩阵的特点：关系矩阵的特点：关系矩阵中主对角线上的元素全为关系矩阵中主对角线上的元素全为1。(3).关系图的特点：关系图的特点：关系图中每个顶点都有环。关系图中每个顶点都有环。实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA，小于等于关系，小于等于关系LA,整除关系整除关系DA都是自都是自反关系：反关系：.452反自反的二元关系反自反的二元关系(1).定义：定义：R是上的二元关系，若是上的二元关系，若 x(xA R),则称则称R在在A上是上是反自反反自反的二元关系的二元关系.例如例如a,b,c,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，则称为，则称为反自反的二元关系。反自反的二元关系。.56实例：实例：实数集上的小于关系，空关系实数集上的小于关系，空关系，幂集上的，幂集上的真包含关系都是反自反关系。真包含关系都是反自反关系。(2).关系矩阵的特点：关系矩阵的特点：关系矩阵中主对角线上的元素全为关系矩阵中主对角线上的元素全为0。(3).关系图的特点：关系图的特点：关系图中每个顶点都没有环。关系图中每个顶点都没有环。.67例例1 A=1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中R1,R2,R3R1既不是自反也不是反自反的既不是自反也不是反自反的R2为自反关系为自反关系,R3为反自反关系。为反自反关系。.783.对称的二元关系对称的二元关系(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)R,则称为对称的二元关系。则称为对称的二元关系。.89实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系都是都是对称关系。对称关系。(2).关系矩阵的特点：关系矩阵的特点：关系矩阵为对称矩阵。关系矩阵为对称矩阵。(3).关系图的特点：关系图的特点：关系图中如果两个顶点之间有边一定是一对关系图中如果两个顶点之间有边一定是一对方向相反的边。方向相反的边。.9104反对称的二元关系反对称的二元关系即即R是上的二元关系，每当有是上的二元关系，每当有(a,b)和有和有(b,a)时，必有时，必有a=b,则称是反对称的二元关系。则称是反对称的二元关系。反对称的定义也可写为：是上的二元关系，反对称的定义也可写为：是上的二元关系，当当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(x,yARRx=y),则称则称R为为A上的上的反对称反对称关系关系.1011注意，注意，“对称的对称的”和和“反对称的反对称的”这两个概念并非相互对立，这两个概念并非相互对立，相互排斥的。存在着既不是对称的又不是反对称的二元相互排斥的。存在着既不是对称的又不是反对称的二元关系，也存在着既是对称的又是反对称的二元关系。关系，也存在着既是对称的又是反对称的二元关系。又如又如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不是反对称的。不是反对称的。.1112实例：实例：恒等关系恒等关系IA，空关系空关系都是都是A上的反对称关系。上的反对称关系。(2).关系矩阵的特点：关系矩阵的特点：关系矩阵中以主对角线对称的元素不能同时为关系矩阵中以主对角线对称的元素不能同时为1。(3).关系图的特点：关系图的特点：关系图中如果两个顶点之间有边一定是一条有向边。关系图中如果两个顶点之间有边一定是一条有向边。.1213例例2 设设A1,2,3,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中 R1,，R2,R3,，R4,R1 对称、反对称对称、反对称.R2 对称，不反对称对称，不反对称.R3 反对称，不对称反对称，不对称.R4 不对称、也不反对称不对称、也不反对称.1314 5.可传递的二元关系可传递的二元关系(1).定义：定义：R是是A上的二元关系，上的二元关系，x y z(x,y,zARRR),则称则称R是是A上的上的传递传递关系关系.例如整除关系是可传递的，因为每当（例如整除关系是可传递的，因为每当（a，b）R时，时，即即 a 能整除能整除 b，b能整除能整除c时，显然时，显然 a 能整除能整除 c，所以必有（所以必有（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，则称为可传递的二元关系。，则称为可传递的二元关系。.1415实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系 小于等于关系小于等于关系,小于关系，整除关系，包含关系，小于关系，整除关系，包含关系，真包含关系都是传递的二元关系。真包含关系都是传递的二元关系。(2).关系矩阵的特点：关系矩阵的特点：(3).关系图的特点：关系图的特点：关系图中如果两个顶点关系图中如果两个顶点xi到到xj之间有边之间有边,xj到到xk之间有边之间有边,则从则从xi到到xk之间有边。之间有边。.1516关系性质判别汇总.162024/4/22 周一17例例3 设设A1,2,3,R1,R2是是A上的关系上的关系,其中其中 R1,R2,R1 是是A上的传递关系上的传递关系 R2不是不是A上的传递关系上的传递关系.1819例例4 判断下图中关系的性质判断下图中关系的性质,并说明理由并说明理由.(2)反自反，不是自反的；反对称，不是对称的；反自反，不是自反的；反对称，不是对称的；(1)不自反也不反自反；对称不自反也不反自反；对称,不反对称；不传递不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递自反，不反自反；反对称，不是对称；不传递.1920二、关系性质的充要条件设设R为为A上的关系上的关系,则则 (1)R在在A上上自反自反当且仅当当且仅当 IA R (2)R在在A上上反自反反自反当且仅当当且仅当 RIA=(3)R在在A上上对称对称当且仅当当且仅当 R=R 1 (4)R在在A上上反对称反对称当且仅当当且仅当 RR 1 IA (5)R在在A上上传递传递当且仅当当且仅当 R R R.20211.自反性证明自反性证明证明模式证明模式 证明证明R在在A上自反上自反 任取任取x,x A .R 前提前提 推理过程推理过程 结论结论例例5 证明若证明若 IA R，则则 R在在A上自反上自反.三、关系类型的证明三、关系类型的证明证证 任取任取x,x A IA R 因此因此 R 在在 A 上是自反的上是自反的.21222.对称性证明对称性证明证明模式证明模式 证明证明R在在A上对称上对称 任取任取 R .R 前提前提 推理过程推理过程 结论结论例例6 证明若证明若 R=R 1,则则R在在A上对称上对称.证证 任取任取 R R 1 R 因此因此 R 在在 A 上是对称的上是对称的.22233.反对称性证明反对称性证明证明模式证明模式 证明证明R在在A上反对称上反对称 任取任取 R R .x=y 前提前提 推理过程推理过程 结论结论例例7 证明若证明若 RR 1 IA,则则R在在A上反对称上反对称.证证 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反对称的上是反对称的.23244.传递性证明传递性证明证明模式证明模式 证明证明R在在A上传递上传递 任取任取，R R.R 前提前提 推理过程推理过程 结论结论例例8 证明若证明若 R R R,则则R在在A上传递上传递.证证 任取任取，R R R R R 因此因此 R 在在 A 上是传递的上是传递的.24思考思考1.设设A=a,b,c,R是是A上的二元关系上的二元关系 且且 R=(a,a),(b,b),(a,c),(c,a),问问R是自反的吗？是自反的吗？是反自反的吗？是对称的吗？是反对称的吗？是反自反的吗？是对称的吗？是反对称的吗？是可传递的吗？是可传递的吗？解：由于解：由于c R,但但(c,c)R,所以所以R不是自反关系；不是自反关系；又由于又由于(c,a)R,(a,c)R,但但(c,c)R,所以所以R不是传递关系。不是传递关系。显然显然R是对称关系，是对称关系，R不是反对称关系；不是反对称关系；由于由于(a,a)R,(b,b)R,所以所以R也不是反自反关系；也不是反自反关系；.25思考思考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)。.26(2)由于由于A上的反自反关系必须不含有上的反自反关系必须不含有(a,a),(b,b)。所以所以A上的反自反关系也有上的反自反关系也有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种。种。.2728所以在所以在AA的子集中删去同时含有的子集中删去同时含有(a,b)和和(b,a)的子集的子集后，其它子集都是反对称关系，共有后，其它子集都是反对称关系，共有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。.2829思考思考3.设设A=1，2，3，问在，问在A上有多少种不同的自反关系？上有多少种不同的自反关系？解：当解：当R R是是A A上的自反关系时，上的自反关系时，R R必须含有表格中对角线上的必须含有表格中对角线上的 3 3个小方格所表示的有序对，对于表格中余下的个小方格所表示的有序对，对于表格中余下的6 6个小个小 方格，可以依次选取方格，可以依次选取1 1个，个，2 2个，个，6 6个小方格，个小方格，也可以不取，它们所表示的二元关系都是也可以不取，它们所表示的二元关系都是A A上的自反关系，上的自反关系，因此，因此，A A上共有上共有6464个自反关系。个自反关系。.295.传递性的判定方法传递性的判定方法判定判定定理定理1 1：设集合：设集合A=aA=a1 1,a,a2 2,a,an n，R R是是A A上的上的二元关系，二元关系，R R 的关系矩阵为的关系矩阵为M MR R，令令M MR R2 2=M MR R M MR R，则则R R是是A A上的传递关系的充要条件是对上的传递关系的充要条件是对M MR R2 2中中1 1所在所在位置位置,M MR R中相应位置都是中相应位置都是1 1。例例9：设：设A=a，b，c，d，e，R=,试判断试判断R的传递性。的传递性。判定判定定理定理2 2：设集合：设集合A=aA=a1 1,a a2 2,a,an n，R R是是A A上的上的二元关系，二元关系，R R 的关系矩阵为的关系矩阵为M MR R，R R是是A A上的传递关上的传递关系的充要条件是若系的充要条件是若M MR R中的零元素中的零元素a aijij=0=0所对应的所对应的M MR R2 2的元素的元素bij=0时，时，则则R R是是A A上的传递关系。上的传递关系。.30思考：设思考：设A=a1，a2，a3，a4，a5，R=,试判断试判断R的传递性。的传递性。.3132四、运算与性质的关系.3233思考：思考：1.当当|A|=n时，时，(1)(1)在在A A上有多少种不同的自反关系？上有多少种不同的自反关系？(2)(2)有多少种不同的反自反关系？有多少种不同的反自反关系？(3)(3)有多少种不同的对称关系？有多少种不同的对称关系？(4)(4)有多少种不同的自反且对称关系？有多少种不同的自反且对称关系？2.设设A=1，2，3，4，R是是A上的二元关系，上的二元关系，R=(1,1),(1,2),(1,3),(3,1),(3,2),(3,3),),(4,1),),(4,2),),(4,3),(1)画出画出R的关系图；的关系图；(2)写出写出R的关系矩阵；的关系矩阵；(3)判断判断R的性质。的性质。.332024/4/22 周一34