玉平县田坪镇迷路小学蔡明光.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肂%函数功能:用关系矩阵判