离散数学关系的性质.ppt

《离散数学关系的性质.ppt》由会员分享，可在线阅读，更多相关《离散数学关系的性质.ppt（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，而R=(a,a),(b,b)时，

2、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,R=(a,b),(b,c),(b,a)，则是反自反的。,又如1,

3、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).关系矩阵的特点：,关系矩阵中主对角线上的元素全为0。,(3).关系图的特点：,关系图中每个顶点都没有环。,7,例1 A=1,2,3,R1,

4、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)R,则称为对称的二元关系。,9,实例：A上的全域关系EA,恒等关系IA和空关系都是对称关系。,(2).关系矩阵的特点：,关系矩阵为

5、对称矩阵。,(3).关系图的特点：,关系图中如果两个顶点之间有边一定是一对方向相反的边。,10,4反对称的二元关系,即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上的反对称关系.,11,注意，“对称的

6、”和“反对称的”这两个概念并非相互对立，相互排斥的。存在着既不是对称的又不是反对称的二元关系，也存在着既是对称的又是反对称的二元关系。,又如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上的反对称关系。,(2).关系矩阵的特点：,关系矩阵中以主对角线对称的元素不能同时为1。,(3).关系图的特点：,关系

7、图中如果两个顶点之间有边一定是一条有向边。,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，所以必有（a，c）R。,又如A=a，b，c，d，e，其中a、b、c、d、e分别是表示5个人，且a、b、c同住一个房间；d和e同住另一个房间。如

8、果同住一房间的人认为是相关的，显然这种同房间关系是可传递的。,每当有(a,b)R和(b,c)R时，必有(a,c)R，则称为可传递的二元关系。,15,实例：A上的全域关系EA,恒等关系IA和空关系 小于等于关系,小于关系，整除关系，包含关系，真包含关系都是传递的二元关系。,(2).关系矩阵的特点：,(3).关系图的特点：,关系图中如果两个顶点xi到xj之间有边,xj到xk之间有边,则从xi到xk之间有边。,16,关系性质判别汇总,例3 设A1,2,3,R1,R2是A上的关系,其中 R1,R2,R1 是A上的传递关系 R2不是A上的传递关系,18,例4 判断下图中关系的性质,并说明理由.,(2)反

9、自反，不是自反的；反对称，不是对称的；,(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.自反性证明,证明模式 证明R在A上自反 任取x,xA.R 前提 推理过程 结论,例5 证明若 IA R，则 R在A上自反.,三、关系类型的证明,证 任取x,xA IA R 因此 R 在 A 上是自反的.,21,2.

10、对称性证明,证明模式 证明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 IA x=y 因此 R 在 A 上是反对称的.,23,4.传递性证明,证明模式 证明R在A上传递 任取，RR.R 前提 推理过程 结论,例8 证明若 RRR,则R在A上传递.,证 任取，R R RR R 因此 R 在 A 上是传递的.,思考1

11、.设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不是反对称关系；,由于(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上的

12、自反关系必须含有(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上的反自反关系也有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

13、,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)的子集后，其它子集都是反对称关系，共有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)

14、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

15、,an，R是A上的二元关系，R 的关系矩阵为MR，R是A上的传递关系的充要条件是若MR中的零元素aij=0所对应的MR2的元素bij=0时，则R是A上的传递关系。,思考：设A=a1，a2，a3，a4，a5，R=,试判断R的传递性。,31,四、运算与性质的关系,32,思考：1.当|A|=n时，(1)在A上有多少种不同的自反关系？(2)有多少种不同的反自反关系？(3)有多少种不同的对称关系？(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),画出R的关系图；(2)写出R的关系矩阵；(3)判断R的性质。,