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

有穷集上等价关系的判定及算法玉平县田坪镇迷路小学摘要: 等价关系是离散数学的一个重要内容,而等价关系的判定则一直是一个难点。对于某个二元关系来说,判定其是否等价的过程比较繁琐。文中给出了判断等价关系的一个充要条件及用关系矩阵判断的方法,并在计算机上实现了具体算法。关键词: 离散数学;等价关系;关系矩阵;算法; MATLAB A poor judge sets equivalence relation and algorithm Abstract: The equivalence relation is one of the important contents of discrete mathematics, and equivalence relation has the determination isa difficulty. For a binary relation speaking, decide its equivalent process whether is more tedious. This paper gives a sufficient and necessary condition for judging equivalence relation and the method with relation matrix judgment on puter, and realized the specific algorithm. Keywords: Discrete mathematics; Equivalence relation; Relation matrix; Algorithms; MATLAB 引言: 离散数学是计算机科学中重要的基础理论之一,在离散数学中等价关系是一个非常重要的概念。等价关系在模糊分析、模式识别、数字电路设计、数据库理论分析等众多学科中都有广泛的应用。正因为如此,才使得等价关系在集合论中占据着举足轻重的位置。由《离散数学》[4] 可知,要判断一个二元关系是否为等价关系,需要判断其是否同时具有自反性、对称性及传递性。而判定一个关系是否是等价关系通常的方法有定义法、关系矩阵法及关系图法三种方法。当然还有其他的判定方法,可参见文献[1] 。但当给定的集合的元素个数较多时, 如何能简便快捷地作出判定却不是一件容易的事。这里在判定等价关系的理论基础上,给出了等价关系的一个矩阵判别法,并在计算机上实现了具体算法。 1 预备知识定义 1设, A B 为集合,笛卡尔积{ , | } A B x y x A y B ? ??????的任何子集所定义的二元关系叫做从A 到B 的二元关系,特别当 A B ?时叫做 A 上的二元关系。定义 2设R 为二元关系, R 的逆关系,简称 R 的逆,记作 1R ?,其中 1 { , | , } R x y y x R ?? ? ????定义 3设, F G 为二元关系, G 对F 的右复合记作 F G ?,其中{ , | ( , , )} F G x y t x t F t y G ? ? ??????????定义 4设R 为集合 A 上的二元关系, ⑴若( , ) x x A x x R ? ?????,则称 R