离散数学第3章(7-8)(新教材).ppt

《离散数学第3章(7-8)(新教材).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七节关系的性质定义7.1(自反性)设R是集合A上一个二元关系,如果对每个xA,都有xRx,则称R在A上是自反的.即R在A上自反的(x)(xAxRx).例如实数集的“”关系是自反的.此外,从关系的关系矩阵以及关系图也很容易对自反性加以判断.一个关系有自反性的充分必要条件是它的关系矩阵的主对角线的元素全都是1;一个关系有自反性的充分必要条件是它的关系图中每个顶点(即集合的每个元素对应画出的小圆圈)都有一条自回路(也称为一个环，即出发点和终点是同一个点的边).定义7.2(反自反性)设R是集合A上一个二元关系,如果对每个xA,都有R

2、,则称R在A上是反自反的.R在X上是反自反的(x)(xXR).反自反性也很容易从关系矩阵和关系图中看出来.一个关系有反自反性的充分必要条件是它的关系矩阵的主对角线上所有的元素全都是0;一个关系有反自反性的充分必要条件是它的关系图中每个顶点都没有自回路.定义7.3(对称性)设R是集合A上一个二元关系,如果对每一对元素x,yA,当xRy时,就有yRx,则称R在A上是对称的.即R在A上是对称的(x)(y)((xA)(yA)(xRy)yRx).对称性很容易从关系矩阵和关系图中看出来.一个关系有对称性的充分必要条件是它的关系

3、矩阵是一个对称阵;一个关系有对称性的充分必要条件是它的关系图中任意两个结点之间要么没有有向边相连,要么恰有一对方向相反的有向边相连.定义7.4(反对称性)设R是集合A上的二元关系,,如果对每一对x,yA,当xRy和yRx同时成立时,必有x=y,则称R在A上是反对称的.即R在X上是反对称的(x)(y)((xX)(yX)(xRy)(yRx)(x=y)).反对称性也很容易从关系矩阵和关系图中看出来.一个关系有反对称性的充分必要条件是它的关系矩阵中关于主对角线对称的任何一对元素要么两个数都是0,要么一个数是0而另一个数是1,或者换句话说:关

4、于主对角线对称的任意一对数中至多只能有一个元素是1;类似地,一个关系有反对称性的充分必要条件是它的关系图中任意两个结点之间至多只有一条有向边相连.定义7.5(传递性)设R是集合A上的二元关系,如果对每个x,y,zX,当xRy且yRz时就有xRz,则称R在A上是可传递的.R在X上是可传递的(x)(y)(z)(xXyXzXxRyyRzxRz);例如,实数集的关系“<”,“”,“=”都是可传递的。例2.设A={1,2,3,4},A上的关系R1={<1,2>,<2,3>,<1,3>,<3,4>,<1,4>}(不可传递)R2={<

5、1,1>,<1,2>,<2,2>,<3,4>}(可传递)R3={<1,2>,<3,4>}(可传递)R4={<1,2>}(可传递)要想通过关系矩阵或者关系图来判断一个给定的关系有没有传递性是比较困难和复杂的.(注)(1)有自反性的关系一定没有反自反性,有反自反性的关系也一定没有自反性,这说明自反性与反自反性不可能共存于同一个关系之中.但是有这样的关系存在,它既不是自反的,也不是反自反的.(2)对称性和反对称性有可能共存于同一个关系之中.同时也存在这样的关系,它既不是对称的,也不是反对称的.请读者举出相应的例子来说明上面注解中的结论.例1.给定一个非空

6、集合A,试讨论集合A上的全域关系AA以及空关系的性质.解:(1)全域关系显然有自反性、对称性和传递性.但显然没有反自反性.至于反对称性,要看集合的元素个数而定.情形一.如果

7、A

8、=1,那么显然它上面的全域关系有反对称性.情形二.如果

9、A

10、>1,那么显然它上面的全域关系没有反对称性.(2)因为A是非空集合,所以容易验证A上的空关系有对称性、传递性、反自反性、反对称性,但没有自反性.例2．给定一个非空集合A={a,b,c,d},试计算(1)A上所有有自反性的二元关系的个数;(2)A上所有有反自反性的二元关系的个数;(3)A上所有有对称性的二元关系的个

11、数.解:(1)有自反性的关系必须含有,,,这四个序偶,而16-4=12,所以A上所有有自反性的二元关系的个数等于.(2)有反自反性的关系必须不含有,,,这四个序偶中的任何一个,所以A上所有有反自反性的二元关系的个数同样等于212.(3)除了,,,这四个序偶之外(任何有对称性的关系可以不含这四个序偶中的任何一个,也可以含有这四个序偶中的任意个数),对AA中剩下的16-4=12个序偶,一个有对称性的关系在含有其中任何一个序偶的

12、同时,必须同时含有序偶.所以这12个剩下的序偶必须两两分成6对,每一对视为一个不可分