“离散数学”中的等价关系

《“离散数学”中的等价关系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、¨卜—瓦而磊磊习豳舞蠢隧万方数据。．q文章编号：1672-5913(2009)01-0050-03“离散数学"中的等价关系吴国兵(南京审计学院信息科学学院，南京210029)摘要：本文阐述了离散数学课程中的一个非常重要的概念即等价关系以及各种具体的等价关系和等价关系在计算机领域中的应用，并运用认识论中的同一性原理和联系与发展的观点，分析了各种等价关系间的联系，说明了对等价关系的概念以及各种具体的等价关系及其应用的教学对促进学生抽象思维能力和逻辑推理能力提高的重要性。关键词：离散数学；等价关系；认识论；教学中图分类号：G642文献标识码：B“离

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

3、的抽象思维能力和逻辑推理能力真正得到提升，是“离散数学”课程教学过程中必须认真解决的重要课题。l离散数学课程中的等价关系1．1离散数学课程中等价关系的概念定义1设R为非空集合A上的二元关系。如果R是自反的、对称的和可传递的，则称R为A上的等价关系。定义2设R为非空集合A上的等价关系，VX∈A，令[X】R-{YY∈A八xRy)，则称【X】R为X关于R的等价类，简记为【x】。定义3设R为非空集合A上的等价关系，以R的所有等价类作元素的集合称为A关于R的商集，记为A／R，即A／R={【x】RX∈A}。■函阿根据定义1，很容易证明矩阵理论中的矩阵合同

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

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

6、》一～————1圉雹黛蟹圈鱼型堕型i皇!《碉删种十分重要的等价关系，它实际上是全体图集合上的一个同时具有自反、对称和可传递三个性质的二元关系，可按此等价关系对全体图集合中的图进行划分，使属于同一个等价类中的图具有完全相同的性质。代数结构中有一个重要的概念，即代数系统的同构。代数系统的同构关系是全部代数系统构成的集合上的等价关系，利用代数系统的同构关系可以对代数系统集进行划分，从而使属于同一个等价类但其表现形式不同的代数系统具有同样的运算性质，只要知道了一个代数系统的性质，便可将其性质直接移植到与之同类但表现形式可能不同的新的代数系统上去。在组

7、合计数问题中会碰到这样一种困难，即区分所讨论的组合计数问题中哪些应该看成是相同的，哪些应该看成是不同的，在计数的过程中不能出现任何的重复或遗漏。这种困难是概念性的，因为它要依据具体问题的要求确切地给出对象异同的数学定义。也就是说，要在对象集合上定义一个等价关系，这样，计数的对象便是等价类，而不是元素本身。组合计数问题中的许多结论、定理(如著名的Burnside引理、Polya计数定理)都要以这类等价关系的概念为基础。通过上面各种具体等价关系的描述可以看到，尽管这些具体的等价关系分属于离散数学课程中各个不同的分支，所基于的集合中的对象表现形式和

8、描述方式不同，对象的性质也是千差万别，但它们都是基于某一集合上的二元关系且均具有自反、对称和可传递三个性质，将它们的这种共性抽象出来便可使这些具体的等价关系都统一到