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

《玉平县田坪镇迷路小学 蔡明光》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有穷集上等价关系的判定及算法玉平县田坪镇迷路小学摘要：等价关系是离散数学的一个重要内容，而等价关系的判定则一直是一个难点。对于某个二元关系来说，判定其是否等价的过程比较繁琐。文中给出了判断等价关系的一个充要条件及用关系矩阵判断的方法，并在计算机上实现了具体算法。关键词：离散数学；等价关系；关系矩阵；算法；MATLABApoorjudgesetsequivalencerelationandalgorithmAbstract:Theequivalencerelationisoneoftheimportantcontentsofdiscretemathematics

2、,andequivalencerelationhasthedeterminationisadifficulty.Forabinaryrelationspeaking,decideitsequivalentprocesswhetherismoretedious.Thispapergivesasufficientandnecessaryconditionforjudgingequivalencerelationandthemethodwithrelationmatrixjudgmentonthecomputer,andrealizedthespecificalgo

3、rithm.Keywords:Discretemathematics;Equivalencerelation;Relationmatrix;Algorithms;MATLAB引言：离散数学是计算机科学中重要的基础理论之一，在离散数学中等价关系是一个非常重要的概念。等价关系在模糊分析、模式识别、数字电路设计、数据库理论分析等众多学科中都有广泛的应用。正因为如此，才使得等价关系在集合论中占据着举足轻重的位置。由《离散数学》[4]可知，要判断一个二元关系是否为等价关系，需要判断其是否同时具有自反性、对称性及传递性。而判定一个关系是否是等价关系通常的方法有定义法、关系

4、矩阵法及关系图法三种方法。当然还有其他的判定方法，可参见文献[1]。但当给定的集合的元素个数较多时，如何能简便快捷地作出判定却不是一件容易的事。这里在判定等价关系的理论基础上，给出了等价关系的一个矩阵判别法，并在计算机上实现了具体算法。1预备知识定义1设为集合，笛卡尔积的任何子集所定义的二元关系叫做从到的二元关系，特别当时叫做上的二元关系。定义2设为二元关系，的逆关系，简称的逆，记作，其中定义3设为二元关系，对的右复合记作，其中定义4设为集合上的二元关系，⑴若，则称在上是自反的。⑵若，则称在上是对称的。⑶若，则称在上是传递的。定义5设为非空集合上的二元关系。如

5、果是自反的、对称的和传递的，则称为上的等价关系。定理1设为上的二元关系，则⑴在上自反当且仅当。⑵在上对称当且仅当。⑶在上传递当且仅当。定义6设，为集合上的二元关系。令则是的关系矩阵，记作定义7设，为上的二元关系，令图，其中顶点集合，边集为。，满足称图为的关系图，记作.表示性质自反性对称性传递性集合表达式关系矩阵主对角线元素全是1矩阵是对称矩阵对中1所在的位置，中相应的位置都是1关系图每个顶点都有环如果两个顶点之间有边，一定是一对方向相反的边如果顶点到有边，到有边，则从到也有边表1关系的自反、对称、传递性在关系矩阵和关系图中的特点2等价关系的矩阵判别法由以上的定

6、义及相关理论可以得出等价关系的矩阵判别法。定理2设集合，是上的二元关系，和的关系矩阵分别是，则为集合上的等价关系的充要条件是证明：由等价关系的定义（上述定义5）可知，要判断二元关系是否为等价关系，需要判断其是否同时具有自反性、对称性及传递性。而定理1又分别给出了满足自反性、对称性及传递性的等价条件。因此为集合上的等价关系的充要条件是，且，而①在的关系矩阵中，主对角线元素全是1，即若，则；②关系矩阵是对称阵，即；③对中1所在的位置，中相应的位置都是1，即当时，必有，又由定义6知，等于1或0，所以当时，必有，。综上所述，为集合上的等价关系的充要条件是3等价关系矩阵

7、判别法的算法实现设和的关系矩阵分别是，则，其中是矩阵的布尔乘运算。由定理2可知，要判定一个二元关系是否为等价关系，首先要根据题设写出关系的关系矩阵，再算出的关系矩阵，然后判断中的元素是否同时满足和，其中，最后得出结论。下面先给出判别流程图（见图1），并在此基础上以MATLAB为工具给出程序。否输入关系矩阵开始不是等价关系的主对角元素全为1？的元素不大于的相应元素？矩阵是对称阵？是等价关系结束否是是是否图1等价关系矩阵判别流程程序：functionDengJiaPanDing(M)%****************************************

8、********%函数名称：DengJ