离散数学：r03关系b

1、1n关系的概念及运算关系的概念及运算n关系的性质关系的性质n关系的闭包运算关系的闭包运算n等价关系等价关系n序关系序关系 关系关系2关系的性质关系的性质(1) 设设R是集合是集合X上的二元关系，如果对于上的二元关系，如果对于X中的每个中的每个x，有有xRx， 则称二元关系则称二元关系R是是自反的自反的（reflexive）。）。()()RXxxXxRx 在在 上上自自反反例例a)在实数集合中，在实数集合中，“”是自反的。是自反的。 b)集合集合X=1,2,3，R=,是自反的。是自反的。n关系关系R是自反的，当且仅当其关系图中每个结点都有是自反的，当且仅当其关系图中每个结点都有自回自回 路路，其

2、关系矩阵的，其关系矩阵的主对角线主对角线上元素都为上元素都为1。n关系关系R是自反的，当且仅当是自反的，当且仅当IXR 3关系的性质关系的性质(2) 设设R是集合是集合X上的二元关系，如果对于上的二元关系，如果对于X中的每个中的每个x，有有xRx， 则称二元关系则称二元关系R是是反自反的反自反的（irreflexive） 。例例a)在实数集合中，在实数集合中，“ ”是反自反的。是反自反的。 b)集合集合X=1,2,3，R=, ,是反自反的。是反自反的。n关系关系R是反自反的，当且仅当其关系图中每个结点都没有自是反自反的，当且仅当其关系图中每个结点都没有自 回路，其关系矩阵的回路，其关系矩阵的主

3、对角线上元素都为主对角线上元素都为0。n关系关系R是反自反的，当且仅当是反自反的，当且仅当R IX = ()()RXxxXxRx 在在上上反反自自反反4 有些关系既不是自反的又不是反自反的；有些关系既不是自反的又不是反自反的； 如如 A=1,2,R=1,1,1,2 有些关系既是自反的又是反自反的。有些关系既是自反的又是反自反的。 如如 空集上的空关系。空集上的空关系。（非空集上的空关系是反自反的）（非空集上的空关系是反自反的） ？ ？ 关系的性质关系的性质5关系的性质关系的性质(3) 设设R是集合是集合X上的二元关系，如果对于上的二元关系，如果对于X中的每个中的每个x，y，每每当当xRy，就有

4、就有yRx，则称二元关系则称二元关系R是是对称的对称的（symmetric）。）。()()()RXxyxXyXxRyyRx 在在 上上对对称称例例a)平面上三角形集合中三角形的相似关系是对称的。平面上三角形集合中三角形的相似关系是对称的。 b)集合集合X=1,2,3，R=,是对是对 称的。称的。n关系关系R是对称的，当且仅当其关系图中任意两个结点间是对称的，当且仅当其关系图中任意两个结点间若有若有定向弧，必是成对出现定向弧，必是成对出现的，其关系矩阵关于主对角线对称。的，其关系矩阵关于主对角线对称。n关系关系R是对称的，当且仅当是对称的，当且仅当R = R-1 6关系的性质关系的性质 (4)

5、设设R是集合是集合X上的二元关系，如果对于上的二元关系，如果对于X中的每个中的每个x，y，每当每当 xRy和和yRx,必有必有x=y,则称二元关系则称二元关系R是是反对称的反对称的 (antisymmetric) 。()()()RXxy xXyXxRyyRxxy 在在 上上反反对对称称()()()RXxy xXyXxyxRyyRx 在在 上上反反对对称称()()()()()()()()()()xRyyRxxyxyxRyyRxxyxRyyRxxyxRyyRxxyxRyyRxxyxRyyRx 7关系的性质关系的性质例例a)集合上的集合上的“”是反对称的。是反对称的。 b)集合集合X=1,2,3，R

6、=, 是反对称的。是反对称的。n关系关系R是反对称的，当且仅当其关系图中任意两个不同结点是反对称的，当且仅当其关系图中任意两个不同结点 间的定向弧不能成对出现，其关系矩阵中关于主对角线对称间的定向弧不能成对出现，其关系矩阵中关于主对角线对称 的元素不能同时为的元素不能同时为1 （但可同时为但可同时为0） 。n关系关系R是反对称的，当且仅当是反对称的，当且仅当R R-1 IX 8关系的性质关系的性质1,x yRx yRx yRy xR ，Rxy 因因为为 是是反反对对称称的的，故故，1,XXx yx xIRRI 所所以以，即即。1,Rx yRR 证证明明：设设 是是反反对对称称的的，假假定定，则

7、则1,XRRIx, yRy,xR 反反之之，假假定定设设且且证明：关系证明：关系R是反对称的，当且仅当是反对称的，当且仅当R R-1 IX 11,x yRx yRx yRR 则则,Xx yI，xyR 故故，所所以以 是是反反对对称称的的。9 有些关系既不是对称的，也不是反对称的。有些关系既不是对称的，也不是反对称的。 如如 A=a,b,c, R=, 有些关系既是对称的，也是反对称的。有些关系既是对称的，也是反对称的。 如如 恒等关系和空关系。恒等关系和空关系。 ？ ？ 关系的性质关系的性质10关系的性质关系的性质(5) 设设R是集合是集合X上的二元关系，如果对于上的二元关系，如果对于X中的每个

8、中的每个x，y，z，每每 当当xRy，yRz，就有就有xRz，则称二元关系则称二元关系R是是传递的传递的(transitive)。()()()()RXxyzxXyXzXxRyyRzxRz 在在 上上传传递递例例a)在实数集合中，在实数集合中，“”是传递的。是传递的。 b)集合集合X=1,2,3,4，R=, 是传递的。是传递的。11关系的性质关系的性质n关系关系R是传递的，当且仅当其关系图中，如果从是传递的，当且仅当其关系图中，如果从a到到b存在一条存在一条 有向路径，则从有向路径，则从a到到b也存在一条弧。也存在一条弧。 (从从a到到b的的有向路径有向路径：指存在一结点序列：指存在一结点序列a

9、=a0,a1,a2,.,an=b， 对每一对每一i，0in-1，ai到到ai+1都存在一条弧。都存在一条弧。)n其关系矩阵特点不明显。其关系矩阵特点不明显。n关系关系R是传递的，当且仅当是传递的，当且仅当R RR 12关系的性质关系的性质 具有这几种特性的关系在关系图、关系矩阵上的特征以及具有这几种特性的关系在关系图、关系矩阵上的特征以及集合形式的定义：集合形式的定义：关系性质关系图特征关系矩阵特征集合表达式自反性每一结点处都有自回路主对角线元素均为1IX R反自反性每一结点处都无自回路主对角线元素均为0R IX =对称性两结点间若有边，则有方向相反的双边对称矩阵R = R-1反对称性任何两个

10、结点间都没有方向相反的双边当Cij=1（ij）时， Cji=0R R-1 IX传递性如果从a到b存在一条 有向路径，则从a到b也存在一条弧无R RR13 (1) (1)设集合设集合X=1,2,3,4，X上的关系上的关系R, R=,。 自反的，对称的自反的，对称的 (2)(2)任何集合上的相等关系。任何集合上的相等关系。 自反的、对称的、反对称的、传递的自反的、对称的、反对称的、传递的。 (3)(3)集合上的集合上的 关系和关系和 关系。关系。 前者是自反的、反对称的、传递的。前者是自反的、反对称的、传递的。 后者是反自反的、反对称的、传递的。后者是反自反的、反对称的、传递的。 (4)(4)非空集合上的空关系和空集上的空关系。非空集合上的空关系和空集上的空关系。 前者是反自反的、对称的、