二元关系的传递性的矩阵判别.doc

二元关系传递性的矩阵判别法 摘 要：通过关系矩阵MR研究有限集合上关系R的性质既直观又迅速在有关二元关系的自反、反自反、对称、反对称以及可传递的研究中前四种性质已有了关系矩阵判别方法。而可传递关系R的特征较为复杂所以不易从其关系矩阵MR中直接判别。本文对有限集合上的可传递关系进行了一般的讨论并给出了定理及其证明在此基础上给出通过其关系矩阵MR判别关系R的可传递性的方法使得对可传递关系的判别变得非常简洁、有效。判断一个二元关系是否具有传递性从定义与关系图的方法比较繁琐利用关系矩阵判断其传递性,能避免繁琐的过程文中通过对二元关系传递性定义的深入分析, 利用关系矩阵中元素的特点与关系通过深入研究二元关系性质和相关定理，提出了四种利用关系矩阵判断传递性的有效方法，分别为中途点判别法、复合矩阵法、十字型法、传递闭包法，同时给阐述了各方法的实用性，给出了利用关系矩阵判定二元关系传递性的简捷高效的算法，具体算法在计算机上能够高速有效的运行，然后对传递性程度进行了研究，具有一定的理论价值跟现实价值。 Matrix Criterion For Transitive of Binary Relation Abstract:Through the relationship matrix MR,studying the nature of a finite set of relations R is intuitive and fast, in the reflexive anti-reflexive,symmetric, antisymmetric and transitive binary relations study, the nature of the first four have a relationship matrix Identification methods. But transitive relation R is complicated, so It is not easy to determine directly from their relationship matrix MR. In this paper, it passed on a general discussion of a finite set of the transitive relationship , and gives the theorem and its proof, on this basis, identification methods for transitive of the relationship R is given by matrix MR so that the identification for transitive of the relationship R could be passed very simply and effectively. Determining whether a binary relation is transitive or not is more complicated from the definition and diagram, the use of relation matrix can avoid the cumbersome process, the paper proposed four effective methods with relationship matrix through in-depth analysis for the definition of binary relation , the use of Characteristics and relationship of the elements in relationship matrix and through studying the nature of binary relations and related theorems,whichwere half-way point criterion, composite matrix, cross-shaped method, transitive closure Method, the methods were also be explained the practicality, the paper also given some simple and efficient algorithms based on relation matrix and the specific algorithms can run fast and ef