二元关系的传递性
时间:2019-09-18 12:47 来源:毕业论文 作者:毕业论文 点击:次
| 摘要：依据离散数学教材中给出的判断二元关系的传递性的定义，当集合中元素较多时，用此 方法过程比较麻烦，所以本文给出了关系矩阵法来判定二元关系的传递性，这样我们就能简便快速的判断其传递性。根据关系矩阵的逻辑加算法和矩阵中元素的特点，来判定二元关系的传递性。39175 毕业论文关键词： 离散数学；二元关系；传递性；关系矩阵 Use the matrix to judge a transitive binary-relation As the definition from the book of Discrete mathematics,It’s very difficult in judging the transmission by defection and graph.But it can become more easily throng matrix of relation.this pager sets up a new matrix distinguishing way of a transitive binary-relation based on analysis of transitive binary-relation Key words：discrete mathematics;binary-relation;transmission;matrix of relation 目录 摘 要 1 引言 1 1二元关系的定义 2 1.1.1二元关系的传递性定义2 2.1.1二元关系传递性的等价定义3 3.1.1关系图的定义 4 4.1.1关系矩阵的定义 5-6 4.1.2 十字形判别法 7 4.1.3 矩形判别法 8 4.1.4 三角形判别法 9 5.1.1 算法定义 10 5.1.2 算法得到的定理10-11 结束语12 致谢13 二元关系的传递性 引言 在涉及离散对象的许多问题中，往往需要研究这些对象之间的某种关系。如果 研究的是n个对象之间的关系，就把这种关系称为n元关系，其中二元关系在日常 生活和实际工作中，应用的非常广泛。在一个很小的集合上就可以定义很多个不同的二元关系，但是真正有实际意义的只是其中很少的一部分。它们一般都是有着某些性质的关系，其中传递性是二元关系的一条重要性质，。 二元关系的传递性是研究传递闭包、等价关系和偏序关系的基础，而传递闭包、等价关系和偏序关系在网络、语法分析以及开关电路等领域中，都有着广泛的应用。 目前有很多研究二元关系的传递性的文章，他们对二元关系的传递性都有所讨论，但仍有不足之处。例如文献[2]中，用二元关系的传递性的定义判定一个关系是否具有传递性，有时一个关系的传递性不太明显，用此方法判断是比较困难的。对于文献中[3]中二元关系传递性的判定定理，由于关系的表达方式不一样，这种方法有一定的局限性。而使用关系图法判断起来太麻烦。本文在上述文献的基础上，对二元关系的传递性进行了详细的归纳与总结，具有一定的理论意义和实践价值。 1二元关系的定义 1.1.1 [1]设A,B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系，记做R。特别地当A=B时叫做A上的二元关系。（它是一个集合，里面的元素是有序对）R=A×B= ｛〈x,y〉｜x A y B｝。 二元关系的传递性定义: 1.1.2[1]定义 设R 为A上的关系，若 x y z (x,y,z <x,y> <y,z> → <x，z> ) 则称 为 上传递的关系。 例1 设集合 ， 为 上的二元关系, = ,试判定 的传递性？ 解：该例中所给的二元关系是以有序对集合的形式给出的，由于该二元关系本身不明显， 要实现传递性的判定必须按照定义中的条依次对 中的每一个有序对< a,b>，检查是否存在有序对<b,c> ,以及<a,c> (责任编辑：qin) |