玉平县田坪镇迷路小学 蔡明光.doc

袁有穷集上等价关系的判定及算法虿玉平县田坪镇迷路小学莇摘要:等价关系是离散数学的一个重要内容,而等价关系的判定则一直是一个难点。对于某个二元关系来说,判定其是否等价的过程比较繁琐。文中给出了判断等价关系的一个充要条件及用关系矩阵判断的方法,并在计算机上实现了具体算法。芃关键词:离散数学;等价关系;关系矩阵;算法;MATLAB羀腿Apoorjudgesetsequivalencerelationandalgorithm袃Abstract:Theequivalencerelationisoneoftheimportantcontentsofdiscretemathematics,,,:Discretemathematics;Equivalencerelation;Relationmatrix;Algorithms;MATLAB莂薈引言:离散数学是计算机科学中重要的基础理论之一,在离散数学中等价关系是一个非常重要的概念。等价关系在模糊分析、模式识别、数字电路设计、数据库理论分析等众多学科中都有广泛的应用。正因为如此,才使得等价关系在集合论中占据着举足轻重的位置。由《离散数学》[4]可知,要判断一个二元关系是否为等价关系,需要判断其是否同时具有自反性、对称性及传递性。而判定一个关系是否是等价关系通常的方法有定义法、关系矩阵法及关系图法三种方法。当然还有其他的判定方法,可参见文献[1]。但当给定的集合的元素个数较多时,如何能简便快捷地作出判定却不是一件容易的事。这里在判定等价关系的理论基础上,给出了等价关系的一个矩阵判别法,并在计算机上实现了具体算法。薄肂蒁1预备知识羇定义1设为集合,笛卡尔积的任何子集所定义的二元关系叫做从到的二元关系,特别当时叫做上的二元关系。莄膃定义2设为二元关系,的逆关系,简称的逆,记作,其中蕿 莇肅定义3设为二元关系,对的右复合记作,其中芅 羁袆定义4设为集合上的二元关系,袅⑴若,则称在上是自反的。肂⑵若,则称在上是对称的。肀⑶若,则称在上是传递的。蕿定义5设为非空集合上的二元关系。如果是自反的、对称的和传递的,则称为上的等价关系。薅定理1设为上的二元关系,则肄⑴在上自反当且仅当。蒂⑵在上对称当且仅当。罿⑶在上传递当且仅当。莆定义6设,为集合上的二元关系。令袁 薀则莈 肆是的关系矩阵,记作羂定义7设,为上的二元关系,令图,其中顶点集合,边集为。,满足虿 螈称图为的关系图,,中相应的位置都是1袄关系图蚀每个顶点都有环蝿如果两个顶点之间有边,一定是一对方向相反的边薄如果顶点到有边,到有边,则从到也有边蚁表1关系的自反、对称、传递性在关系矩阵和关系图中的特点蝿膈2等价关系的矩阵判别法芄由以上的定义及相关理论可以得出等价关系的矩阵判别法。螃定理2设集合,是上的二元关系,和的关系矩阵分别是,则为集合上的等价关系的充要条件是肁 蚈羅证明:由等价关系的定义(上述定义5)可知,要判断二元关系是否为等价关系,需要判断其是否同时具有自反性、对称性及传递性。而定理1又分别给出了满足自反性、对称性及传递性的等价条件。因此为集合上的等价关系的充要条件是,且,而①在的关系矩阵中,主对角线元素全是1,即若,则;②关系矩阵是对称阵,即;③对中1所在的位置,中相应的位置都是1,即当时,必有,又由定义6知,等于1或0,所以当时,必有,。袄综上所述,为集合上的等价关系的充要条件是艿 肇螅蚁3等价关系矩阵判别法的算法实现薂设和的关系矩阵分别是,则,其中是矩阵的布尔乘运算。由定理2可知,要判定一个二元关系是否为等价关系,首先要根据题设写出关系的关系矩阵,再算出的关系矩阵,然后判断中的元素是否同时满足和,其中,最后得出结论。蒇下面先给出判别流程图(见图1),并在此基础上以MATLAB为工具给出程序。蒅蚃否蚀输入关系矩阵膀开始芆螄不是等价关系衿的主对角元素全为1?虿的元素不大于的相应元素?羆矩阵是对称阵?薁是等价关系膁结束聿螇否薃是艿是蒈是蒇否蚄图1等价关系矩阵判别流程蚂程序:袇functionDengJiaPanDing(M)***%************************************************蒂%函数名称:DengJiaPanDing螀%函数功能:用关系矩阵判