“离散数学”中的等价关系-2019年文档

1、“离散数学”中的等价关系文献标识码： B“离散数学” 是计算机专业的重要基础课程和核心课程。通过该课程的教学，不仅要为学生们进一步学习本专业的后续课程提供必备的数学理论基础，更重要的是培养和提高学生的抽象思维能力和逻辑推理能力。与高等数学主要以连续量作为研究对象不同，离散数学主要以离散量作为主要的研究对象，内容包括数理逻辑、集合论、代数结构、图论以及组合数学、 数论和离散概率等。由于这些内容在描述形式、研究方法和计算机应用领域等方面均存在着较大差异，且含有大量比较抽象的概念、 定理和各种各样的形式化描述，因而学生普遍感到困难重重，学习效果不理想。因此，如何改进教学方法，提高教学效果，使学生们的

2、抽象思维能力和逻辑推理能力真正得到提升，是“离散数学”课程教学过程中必须认真解决的重要课题。1 离散数学课程中的等价关系1.1 离散数学课程中等价关系的概念定义 1 设 R为非空集合 A 上的二元关系。如果R是自反的、对称的和可传递的，则称R为 A 上的等价关系。定义2设 R为非空集合A 上的等价关系，x A，令x R= y| yAxRy ，则称 x R为x关于R的等价类，简记为 x 。定义3设 R为非空集合A 上的等价关系，以R的所有等价类作元素的集合称为A 关于 R的商集，记为 A/R，即 A/R= x R| xA 。根据定义 1，很容易证明矩阵理论中的矩阵合同关系、相似关系都是等价关系；

3、 线性空间的同构关系也是一种等价关系。下面主要讨论离散数学中一些常见的等价关系。1.2 离散数学课程中各种具体的等价关系数理逻辑中，命题公式 A 和 B 等值 ( 记为 A B) 是指由它们构成的等价式 A B 为永真式。命题公式的等值关系是建立在由所有命题公式构成的集合上的一种等价关系， 这种等价关系将所有命题公式按其是否等值划分成若干个等价类， 属于同一个等价类中的命题公式彼此等值，因而，只要清楚了等价类中某一个公式的性质，则与该公式同类的公式的性质也就完全清楚了。因此，命题公式的等值关系 ( 等价关系) 是获取命题公式性质的基石。集合论中，集合 A 和 B 的等势是指从 A 到 B 存在

4、一个双射函数即集合 A 中的元素与集合 B 中的元素存在着一一对应。 显然，集合的等势关系是建立在由所有集合作元素构成的集合上的一个等价关系， 它实际上是从集合所含元素多少的角度来对集合进行划分， 只要两个集合所含元素的个数相同， 就视它们为相同的集合， 可将它们归于同一类。图论中，无向图中点与点之间的连通关系是一种等价关系， 它是建立在由无向图中所有结点做成的集合上的等价关系， 只要两个结点间存在通路，则这两个结点就是等价的，它们便归于同一类，无向图中连通分支的概念就建立在连通关系的基础之上。 图的同构关系也是图论中又一种十分重要的等价关系， 它实际上是全体图集合上的一个同时具有自反、 对称

5、和可传递三个性质的二元关系， 可按此等价关系对全体图集合中的图进行划分， 使属于同一个等价类中的图具有完全相同的性质。代数结构中有一个重要的概念， 即代数系统的同构。 代数系统的同构关系是全部代数系统构成的集合上的等价关系， 利用代数系统的同构关系可以对代数系统集进行划分， 从而使属于同一个等价类但其表现形式不同的代数系统具有同样的运算性质， 只要知道了一个代数系统的性质，便可将其性质直接移植到与之同类但表现形式可能不同的新的代数系统上去。在组合计数问题中会碰到这样一种困难，即区分所讨论的组合计数问题中哪些应该看成是相同的，哪些应该看成是不同的， 在计数的过程中不能出现任何的重复或遗漏。这种困

6、难是概念性的， 因为它要依据具体问题的要求确切地给出对象异同的数学定义。也就是说，要在对象集合上定义一个等价关系，这样，计数的对象便是等价类，而不是元素本身。组合计数问题中的许多结论、 定理 ( 如著名的 Burnside引理、 Polya 计数定理 ) 都要以这类等价关系的概念为基础。通过上面各种具体等价关系的描述可以看到， 尽管这些具体的等价关系分属于离散数学课程中各个不同的分支， 所基于的集合中的对象表现形式和描述方式不同， 对象的性质也是千差万别， 但它们都是基于某一集合上的二元关系且均具有自反、对称和可传递三个性质，将它们的这种共性抽象出来便可使这些具体的等价关系都统一到定义 1 上

7、来，从而实现了从特殊到一般的抽象。由此可见，等价关系实质上是对相应集合中的具有同一性的对象即具有共性特征的对象的一种抽象，从认识论的角度来看，这符合从特殊到一般的认识规律。在很多教材中， 数理逻辑往往是最先介绍的内容， 而等价关系的定义往往在其后介绍，所以，可以由命题公式的等值关系的性质 ( 自反、对称和可传递 ) 来引入 ( 抽象 ) 出等价关系的定义 ( 定义 1) ，这是从特殊到一般的认识过程； 其他的内容如图论和代数系统等则往往在等价关系的定义之后讲授， 因此，可用一般等价关系的定义来阐述图的同构关系、代数系统的同构关系和组合计数中的等价关系等， 这是从一般到特殊的认识过程。在离散数学

8、各个部分的教学过程中， 可以等价关系作为一条重要的线索，将离散数学中的各个部分有机地组织和联系起来， 使学生们能够深刻理解等价关系这一重要的概念，学会用联系的观点去分析、思考和解决问题， 尽可能做到对各部分的相关内容融会贯通， 这对学生的抽象思维能力和逻辑推理能力的提高非常有益。2 等价关系的发展和应用任何事物都是不断发展的，等价关系的概念也同样如此。自从美国计算机与控制论专家于 1965 年首次提出Fuzzy 集的概念，从而对经典的Cantor 集合理论做出了深刻的推广以来，模糊数学已经逐步发展成为一个较为完善的数学分支，并在众多的领域特别是人工智能领域获得了卓有成效的应用。经典的二元关系理

9、论中存在一个缺限，即没有考虑元素与元素间关系程度的不同。在 Zadeh 提出了 Fuzzy 集的概念以后，人们便将经典的二元关系扩充为模糊数学中的模糊二元关系， 通过模糊二元关系可以较好地刻画元素与元素间关系程度的不同， 以模糊二元关系为基础， 人们很自然地提出了模糊等价关系的概念。 借助于模糊等价关系， 可以较好地解决具有 Fuzzy 性的聚类分析问题， 而聚类分析则是数据挖掘领域中的重要课题之一。比较建立在经典集合理论基础上的等价关系和建立在模糊二元关系基础上的模糊等价关系的定义，容易看出，在 Cantor 集合理论基础上的等价关系是模糊等价关系的特例，而模糊等价关系则是Cantor 集合

10、理论基础上的等价关系的推广，是更高层次上的抽象。在教学过程中适当介绍模糊等价关系， 一方面可以使学生们加深对等价关系概念的理解， 学会用发展的眼光分析和解决问题， 另一方面可以克服大多数离散数学教材只注重阐述理论而很少涉及其理论在计算机领域中的应用的缺陷， 使学生们尽可能多地了解离散数学在计算机领域中的具体应用，提高学习离散数学的兴趣。事实上，等价关系在计算机领域中还有很多应用， 例如在软件工程领域，为了尽可能多的找出软件设计过程中可能存在的各种错误，常常使用一种被称之为“等价类划分”的软件测试方法。这种方法实际上就是将所有待测试的数据所构成的集合划分成若干个符合软件需求规格及设计规定的有效等

11、价类和若干个不符合软件需求规格及设计规定的无效等价类， 然后在每个有效等价类和无效等价类中只各取一个数据进行测试。 若某个等价类中的一个数据能测出软件中的错误，则该等价类中的其余数据也能测出错误；相反地，若某个等价类中的一个数据不能测出软件中的错误， 则该等价类中的其余数据也不能测出错误，从而可以大大提高软件测试的效率。又如，在数据库理论中，分组查询是一种重要的数据库操作，它在本质上也是一种等价类的划分， 即将相关数据表中的所有记录作为一个集合，根据记录的一个或多个属性 ( 字段 ) 的值是否相同来对表中的记录进行分类， 字段值相同的归于同一类， 在此基础上可以进行进一步的分组统计等操作。再如，粗糙集理论是一种处理模糊和不确定性知识的数学工具，其主要思想就是在保持分类能力不变的前提下，通过知识约简， 导出问题的决策或分类规则。在经典粗糙集理论(Pawlak 粗糙集模型 ) 中，等价关系是最为重要的基本概念之一，经典粗糙集理论的大部分概念均建立在等价关系的概念之上。目前，粗糙集理论已被成功地应用于机器学习、决策分析、模式识别、过程控制和知识