下载文档原格式
离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。
命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。
命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。
给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。
若指定的一组值使A的值为真，则称成真赋值。
真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。
将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。
命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。
（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。
（3）若A至少存在一组赋值是成真赋值，则A是可满足式。
主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。
主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。
命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B 是等值的，记作A<=>B。
约束变元和自由变元：在合式公式xA和 xA中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。
一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。
前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Qk…xkB，称A为前束范式。
集合的基本运算：并、交、差、相对补和对称差运算。
笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。
二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。
等价关系是设R是非空集合A上的二元关系，若R是自反的、对称的、传递的，则称R是A上的等价关系。
给定非空集合A,若有集合S={S ,S ,…,S }，其中S A，S（i=1,2,…,m）且S S = (i j)同时有S =A，称S是A的划分。
研究等价关系的目的在于将集合中的元素进行分类，选取每类的代表元素来降低问题的复杂度，如软件测试时，可利用等价类来选择测试用例。
扩展资料：
定义：
若关系R在集合A中是自反、对称和传递的，则称R为A上的等价关系。
所谓关系R 就是笛卡尔积 A×A 中的一个子集。
A中的两个元素x,y有关系R，如果(x,y)∈R。
我们常简记为xRy。
自反：任意x属于A，则x与自己具有关系R，即xRx；
对称：任意x,y属于A，如果x与y具有关系R，即xRy，则y与x 也具有关系R，即yRx；
传递：任意x,y,z属于A，如果xRy且yRz，则xRz
x,y具有等价关系R，则称x,y R等价，有时亦简称等价。
浅谈等价关系的应用
《浅谈等价关系的应用》
等价关系是抽象代数中的一种基本概念,它在数学中有着多样的
应用,研究其应用非常重要。
本文将介绍等价关系的应用及其重要性。
首先,等价关系的应用主要是应用于抽象代数、几何学、离散数
学等领域。
在抽象代数中,它常用于研究分组、环、体、域等抽象概念。
例如,在环上,我们可以定义等价关系,用来表示两个元素具有特
定的性质。
其次,等价关系也能够应用于几何学。
在几何学中,它可以用来分类几何形状,比如三角形、矩形、正方形等。
同时,我们也可以用等价关系来描述两个几何图形之间的相似性。
例如,两个三角形它们可以
通过旋转、缩放进行变换,这就表明它们是一致的。
再次,等价关系也可以应用于离散数学领域。
在离散数学中,我们经常会用到等价关系来分析和求解复杂的数学问题。
例如,我们可以
用等价关系来分析图的属性,以及分析组合和组合查找算法的有效性。
最后,等价关系也能够用来在现实生活中的解决实际问题。
例如,等价关系可以用来解决路径规划问题,可以用来分析不同城市之间的
距离,以及可以用来分析两个城市之间的密度等等。
综上所述,等价关系在数学中有着广泛的应用。
它不仅可以用来
分析抽象数学问题,也可以用来分析具体的现实问题。
因此,等价关系的研究非常重要,它对于我们理解和应用数学抽象概念具有重要的意
义。
等价类：在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质。
设R是定义在集合A上的等价关系，与A中一个元素a有关系的所有元素的集合叫做a的等价类。
等价类应用十分广泛，如在编程语言中，我们使用等价类来判定标识符是不是表示同一个事物。
定义：在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质。
设R是定义在集合A上的等价关系，与A中一个元素a有关系的所有元素的集合叫做a的等价类。
A的关于R的等价类记作。
当只考虑一个关系时，我们省去下表R并把这个等价类写作[a]。
在软件工程中，是把所有可能输入的数据，即程序的输入域划分成若干部分（子集），然后从每一个子集中选取少数具有代表性的数据作为测试用例，从而减少了数据输入量从而提高了效率，称之为等价类方法，该方法是一种重要的、常用的黑盒测试用例设计方法。
分类：在离散数学中，等价类的划分基于以下定理：设R是定义在集合A上的等价关系。
那么R的等价类构成S的划分。
反过来，给定集合S的划分{ |i∈I},则存在一个等价关系R，它以集合作为它的等价类。
因为等价关系的a 在a 中和任何两个等价类要么相等要么不交集不相交的性质。
得出X 的所有等价类的集合形成X 的集合划分划分: 所有X 的元素属于一且唯一的等价类。
反过来，X 的所有划分也定义了在X 上等价关系。
在软件工程中等价类划分及标准如下：划分等价类等价类是指某个输入域的子集合。
在该子集合中，各个输入数据对于揭露程序中的错误都是等效的，并合理地假定：测试某等价类的代表值就等于对这一类其他值的测试，因此，可以把全部输入数据合理划分为若干等价类，在每一个等价类中取一个数据作为测试的输入条件就可以用少量代表性的测试数据取得较好的测试结果。
等价类划分有两种不同的情况：有效等价类和无效等价类。
1）有效等价类是指对于程序的规格说明来说是合理的、有意义的输入数据构成的集合。
利用有效等价类可检验程序是否实现了规格说明所规定的功能和性能。
概念问题二进制关系：A和B的笛卡尔积的子集称为从A到B的二进制关系。
集合上的关系：从a到a的关系。
关系的性质反射，抗反射，对称，抗对称和传输。
没有列出概念，但应注意以下方面：（1）所有属性的概念都是逻辑表达式，即判断是非，必须严格按照定义判断是非；（2）它们都是用全名量词表示的逻辑表达式，因此必须为真才能保持一致；（3）它们全部由隐含条件语句表示。
如果前提为假，则它也为真，也就是说，所有未出现在真之后再为假的内容都为真。
关系代表（1）设置符号（适合定义和表示）；（2）图表表示（适合直观感觉和观察特性）；（3）关系矩阵表示（适合计算）；特别地，关系矩阵是布尔矩阵，即逻辑矩阵，其描述A中的第i个元素是否与B中的第j个元素有关。
关系运作（1）交叉，合并与区别R1ÇR2————M1ÙM2R1ÈR2————M1ÚM2（2）综合合成操作非常重要且容易出错。
注意其顺序以及对集合，图形和矩阵的相应计算。
自我及其综合运算形成力量。
例如，R 2对应于由点直接连接的边，这些点可以从图形上的每个点分两步到达。
另一个例子R1°R2 ————M2M1R ^ 2 ————M ^ 2关系的应用（1）n元关系的应用一般来说，当2元关系扩展到N元关系时，它就成为数据库的基本框架。
N元有序对是N个字段的记录，因此关系操作对应于数据库操作。
我们只知道这部分内容（与数据库重复）。
（2）封闭的应用首先，介绍了三种闭包的概念。
如果用一句话来概括，R的自反/对称/传递闭包是包含R的自反/对称/传递关系中最小的。
然后其应用着重于掌握传递闭包的应用，它可以显示传递性直接通过连接边可到达的点的连通性。
然后讨论三个闭包的计算：（3）等价关系的应用首先是等价关系的概念，以及等价类和划分的扩展概念。
其次，等价关系的应用仅仅是分类。
因为等价与划分之间存在一一对应的关系。
A.如果一个关系是集合a上的等价关系，写出每个元素的等价类，然后删除重复项，则由非重复等价类组成的集合就是原始集合a的除法。
“离散数学”中的等价关系
“离散数学”是计算机专业的重要基础课程和核心课程。
通过该课程的教学，不仅要为学生们进一步学习本专业的后续课程提供必备的数学理论基础，更重要的是培养和提高学生的抽象思维能力和逻辑推理能力。
与高等数学主要以连续量作为研究对象不同，离散数学主要以离散量作为主要的研究对象，内容包括数理逻辑、集合论、代数结构、图论以及组合数学、数论和离散概率等。
由于这些内容在描述形式、研究方法和计算机应用领域等方面均存在着较大差异，且含有大量比较抽象的概念、定理和各种各样的形式化描述，因而学生普遍感到困难重重，学习效果不理想。
因此，如何改进教学方法，提高教学效果，使学生们的抽象思维能力和逻辑推理能力真正得到提升，是“离散数学”课程教学过程中必须认真解决的重要课题。
1离散数学课程中的等价关系
1.1离散数学课程中等价关系的概念
定义1 设R为非空集合A上的二元关系。
如果R是自反的、对称的和可传递的，则称R为A上的等价关系。
定义2 设R为非空集合A上的等价关系，x∈A，令[ x ]R={ y | y ∈A ∧xRy }，
则称[ x ]R 为x关于R的等价类，简记为[ x ]。
定义3 设R为非空集合A上的等价关系，以R的所有等价类作元素的集合称为A关于R的商集，记为A/R，即A/R={ [ x ]R| x∈A }。
根据定义1，很容易证明矩阵理论中的矩阵合同关系、相似关系都是等价关系；线性空间的同构关系也是一种等价关系。
下面主要讨论离散数学中一些常见的等价关系。
1.2离散数学课程中各种具体的等价关系
数理逻辑中，命题公式A和B等值(记为A B)是指由它们构成的等价式A B 为永真式。
命题公式的等值关系是建立在由所有命题公式构成的集合上的一种等价关系，这种等价关系将所有命题公式按其是否等值划分成若干个等价类，属于同一个等价类中的命题公式彼此等值，因而，只要清楚了等价类中某一个公式的性质，则与该公式同类的公式的性质也就完全清楚了。
因此，命题公式的等值关系(等价关系)是获取命题公式性质的基石。
集合论中，集合A和B的等势是指从A到B存在一个双射函数即集合A中
的元素与集合B中的元素存在着一一对应。
显然，集合的等势关系是建立在由所有集合作元素构成的集合上的一个等价关系，它实际上是从集合所含元素多少的角度来对集合进行划分，只要两个集合所含元素的个数相同，就视它们为相同的集合，可将它们归于同一类。
图论中，无向图中点与点之间的连通关系是一种等价关系，它是建立在由无向图中所有结点做成的集合上的等价关系，只要两个结点间存在通路，则这两个结点就是等价的，它们便归于同一类，无向图中连通分支的概念就建立在连通关系的基础之上。
图的同构关系也是图论中又一种十分重要的等价关系，它实际上是全体图集合上的一个同时具有自反、对称和可传递三个性质的二元关系，可按此等价关系对全体图集合中的图进行划分，使属于同一个等价类中的图具有完全相同的性质。
代数结构中有一个重要的概念，即代数系统的同构。
代数系统的同构关系是全部代数系统构成的集合上的等价关系，利用代数系统的同构关系可以对代数系统集进行划分，从而使属于同一个等价类但其表现形式不同的代数系统具有同样的运算性质，只要知道了一个代数系统的性质，便可将其性质直接移植到与之同类但表现形式可能不同的新的代数系统上去。
在组合计数问题中会碰到这样一种困难，即区分所讨论的组合计数问题中哪些应该看成是相同的，哪些应该看成是不同的，在计数的过程中不能出现任何的重复或遗漏。
这种困难是概念性的，因为它要依据具体问题的要求确切地给出对象异同的数学定义。
也就是说，要在对象集合上定义一个等价关系，这样，计数的对象便是等价类，而不是元素本身。
组合计数问题中的许多结论、定理(如著名的Burnside引理、Polya计数定理)都要以这类等价关系的概念为基础。
通过上面各种具体等价关系的描述可以看到，尽管这些具体的等价关系分属于离散数学课程中各个不同的分支，所基于的集合中的对象表现形式和描述方式不同，对象的性质也是千差万别，但它们都是基于某一集合上的二元关系且均具有自反、对称和可传递三个性质，将它们的这种共性抽象出来便可使这些具体的等价关系都统一到定义1上来，从而实现了从特殊到一般的抽象。
由此可见，等价关系实质上是对相应集合中的具有同一性的对象即具有共性特征的对象的一种抽象，从认识论的角度来看，这符合从特殊到一般的认识规律。
在很多教材中，数理逻辑往往是最先介绍的内容，而等价关系的定义往往在其后介绍，所以，可以由命题公式的等值关系的性质(自反、对称和可传递)来引入(抽象)出等价关系的定义(定义1)，这是从特殊到一般的认识过程；其他的内容如图论和代数系统等则往往在等价关系的定义之后讲授，因此，可用一般等价关系的定义来阐述图的同构关系、代数系统的同构关系和组合计数中的等价关系等，这是从一般到特殊的认识过程。
在离散数学各个部分的教学过程中，可以等价关系作为一条重要的线索，将离散数学中的各个部分有机地组织和联系起来，使学生们能够深刻理解等价关系这一重要的概念，学会用联系的观点去分析、思考和解决问题，尽可能做到对各
部分的相关内容融会贯通，这对学生的抽象思维能力和逻辑推理能力的提高非常有益。
2等价关系的发展和应用
任何事物都是不断发展的，等价关系的概念也同样如此。
自从美国计算机与控制论专家L.A.Zadeh于1965年首次提出Fuzzy集的概念，从而对经典的Cantor集合理论做出了深刻的推广以来，模糊数学已经逐步发展成为一个较为完善的数学分支，并在众多的领域特别是人工智能领域获得了卓有成效的应用。
经典的二元关系理论中存在一个缺限，即没有考虑元素与元素间关系程度的不同。
在Zadeh提出了Fuzzy集的概念以后，人们便将经典的二元关系扩充为模糊数学中的模糊二元关系，通过模糊二元关系可以较好地刻画元素与元素间关系程度的不同，以模糊二元关系为基础，人们很自然地提出了模糊等价关系的概念。
借助于模糊等价关系，可以较好地解决具有Fuzzy性的聚类分析问题，而聚类分析则是数据挖掘领域中的重要课题之一。
比较建立在经典集合理论基础上的等价关系和建立在模糊二元关系基础上的模糊等价关系的定义，容易看出，在Cantor集合理论基础上的等价关系是模糊等价关系的特例，而模糊等价关系则是Cantor集合理论基础上的等价关系的推广，是更高层次上的抽象。
在教学过程中适当介绍模糊等价关系，一方面可以使学生们加深对等价关系概念的理解，学会用发展的眼光分析和解决问题，另一方面可以克服大多数离散数学教材只注重阐述理论而很少涉及其理论在计算机领域中的应用的缺陷，使学生们尽可能多地了解离散数学在计算机领域中的具体应用，提高学习离散数学的兴趣。
事实上，等价关系在计算机领域中还有很多应用，例如在软件工程领域，为了尽可能多的找出软件设计过程中可能存在的各种错误，常常使用一种被称之为”等价类划分”的软件测试方法。
这种方法实际上就是将所有待测试的数据所构成的集合划分成若干个符合软件需求规格及设计规定的有效等价类和若干个不符合软件需求规格及设计规定的无效等价类，然后在每个有效等价类和无效等价类中只各取一个数据进行测试。
若某个等价类中的一个数据能测出软件中的错误，则该等价类中的其余数据也能测出错误；相反地，若某个等价类中的一个数据不能测出软件中的错误，则该等价类中的其余数据也不能测出错误，从而可以大大提高软件测试的效率。
又如，在数据库理论中，分组查询是一种重要的数据库操作，它在本质上也是一种等价类的划分，即将相关数据表中的所有记录作为一个集合，根据记录的一个或多个属性(字段)的值是否相同来对表中的记录进行分类，字段值相同的归于同一类，在此基础上可以进行进一步的分组统计等操作。
再如，粗糙集理论是一种处理模糊和不确定性知识的数学工具，其主要思想
就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。
在经典粗糙集理论(Pawlak粗糙集模型)中，等价关系是最为重要的基本概念之一，经典粗糙集理论的大部分概念均建立在等价关系的概念之上。
目前，粗糙集理论已被成功地应用于机器学习、决策分析、模式识别、过程控制和知识发现与数据挖掘等众多领域。
3结束语
为了提高教学效果，使学生的抽象思维能力和逻辑推理能力真正得到提升，教师可在离散数学各个部分的教学过程中，以等价关系作为一条重要的线索，将离散数学中的各个部分有机地组织和联系起来，使学生们能够深刻理解等价关系这一重要的概念，并学会用联系与发展的观点去分析、思考和解决问题，这对学生的抽象思维能力和逻辑推理能力的提高非常有益。
参考文献：
[1] 耿素云,屈婉玲. 离散数学[M]. 北京:高等教育出版社,2004.
[2] 张文修,吴伟志,梁吉业等. 粗糙集理论与方法[M]. 北京:科学出版社,2001.
[3] 胡宝清. 模糊理论基础[M]. 武汉大学出版社,2004.
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”。
