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

卜 瓦而磊磊习豳舞蠢隧 q 文章编号 1 6 7 2 5 9 1 3 2 0 0 9 0 1 0 0 5 0 0 3 离散数学 中的等价关系 吴国兵 南京审计学院信息科学学院 南京2 1 0 0 2 9 摘要 本文阐述了离散数学课程中的一个非常重要的概念即等价关系以及各种具体的等价关系和等价关系 在计算机领域中的应用 并运用认识论中的同一性原理和联系与发展的观点 分析了各种等价关系间的联系 说明了对等价关系的概念以及各种具体的等价关系及其应用的教学对促进学生抽象思维能力和逻辑推理能力 提高的重要性 关键词 离散数学 等价关系 认识论 教学 中图分类号 G 6 4 2 文献标识码 B 离散数学 是计算机专业的重要基础课程和核心课 程 通过该课程的教学 不仅要为学生们进一步学习本专 业的后续课程提供必备的数学理论基础 更重要的是培养 和提高学生的抽象思维能力和逻辑推理能力 与高等数学 主要以连续量作为研究对象不同 离散数学主要以离散量 作为主要的研究对象 内容包括数理逻辑 集合论 代数 结构 图论以及组合数学 数论和离散概率等 由于这些 内容在描述形式 研究方法和计算机应用领域等方面均存 在着较大差异 且含有大量比较抽象的概念 定理和各种 各样的形式化描述 因而学生普遍感到困难重重 学习效 果不理想 因此 如何改进教学方法 提高教学效果 使 学生们的抽象思维能力和逻辑推理能力真正得到提升 是 离散数学 课程教学过程中必须认真解决的重要课题 l 离散数学课程中的等价关系 1 1离散数学课程中等价关系的概念 定义1设R 为非空集合A 上的二元关系 如果R 是自反的 对称的和可传递的 则称R 为A 上的等价关系 定义2设R 为非空集合A 上的等价关系 V X A 令 X R YY A 八x R y 则称 X R 为X 关于R 的等价类 简记为 x 定义3设R 为非空集合A 上的等价关系 以R 的 所有等价类作元素的集合称为A 关于R 的商集 记为A R 即A R x RX A 函阿 根据定义1 很容易证明矩阵理论中的矩阵合同关系 相似关系都是等价关系 线性空间的同构关系也是一种等 价关系 下面主要讨论离散数学中一些常见的等价关系 1 2 离散数学课程中各种具体的等价关系 数理逻辑中 命题公式A 和B 等值 记为A 甘B 是指 由它们构成的等价式A 七号B 为永真式 命题公式的等值 关系是建立在由所有命题公式构成的集合上的一种等价 关系 这种等价关系将所有命题公式按其是否等值划分成 若干个等价类 属于同一个等价类中的命题公式彼此等 值 因而 只要清楚了等价类中某一个公式的性质 则与 该公式同类的公式的性质也就完全清楚了 因此 命题公 式的等值关系 等价关系 是获取命题公式性质的基石 集合论中 集合A 和B 的等势是指从A 到B 存在一 个双射函数即集合A 中的元素与集合B 中的元素存在着一 一对应 显然 集合的等势关系是建立在由所有集合作元 素构成的集合上的一个等价关系 它实际上是从集合所含 元素多少的角度来对集合进行划分 只要两个集合所含元 素的个数相同 就视它们为相同的集合 可将它们归于同 一类 图论中 无向图中点与点之间的连通关系是一种等价 关系 它是建立在由无向图中所有结点做成的集合上的等 价关系 只要两个结点间存在通路 则这两个结点就是等 价的 它们便归于同一类 无向图中连通分支的概念就建 立在连通关系的基础之上 图的同构关系也是图论中又一 万方数据 爹爹 一 1 圉雹黛蟹圈鱼型堕型i 皇 碉删 种十分重要的等价关系 它实际上是全体图集合上的一个 同时具有自反 对称和可传递三个性质的二元关系 可按 此等价关系对全体图集合中的图进行划分 使属于同一个 等价类中的图具有完全相同的性质 代数结构中有一个重要的概念 即代数系统的同构 代数系统的同构关系是全部代数系统构成的集合上的等 价关系 利用代数系统的同构关系可以对代数系统集进行 划分 从而使属于同一个等价类但其表现形式不同的代数 系统具有同样的运算性质 只要知道了一个代数系统的性 质 便可将其性质直接移植到与之同类但表现形式可能不 同的新的代数系统上去 在组合计数问题中会碰到这样一种困难 即区分所讨 论的组合计数问题中哪些应该看成是相同的 哪些应该看 成是不同的 在计数的过程中不能出现任何的重复或遗 漏 这种困难是概念性的 因为它要依据具体问题的要求 确切地给出对象异同的数学定义 也就是说 要在对象集 合上定义一个等价关系 这样 计数的对象便是等价类 而不是元素本身 组合计数问题中的许多结论 定理 如著 名的B u r n s i d e 引理 P o l y a 计数定理 都要以这类等价关系 的概念为基础 通过上面各种具体等价关系的描述可以看到 尽管这 些具体的等价关系分属于离散数学课程中各个不同的分 支 所基于的集合中的对象表现形式和描述方式不同 对 象的性质也是千差万别 但它们都是基于某一集合上的二 元关系且均具有自反 对称和可传递三个性质 将它们的 这种共性抽象出来便可使这些具体的等价关系都统一到 定义1 上来 从而实现了从特殊到一般的抽象 由此可见 等价关系实质上是对相应集合中的具有同一性的对象即 具有共性特征的对象的一种抽象 从认识论的角度来看 这符合从特殊到一般的认识规律 在很多教材中 数理逻辑往往是最先介绍的内容 而 等价关系的定义往往在其后介绍 所以 可以由命题公式 的等值关系的性质 自反 对称和可传递 来引入 抽象 出等 价关系的定义 定义1 这是从特殊到一般的认识过程 其 他的内容如图论和代数系统等则往往在等价关系的定义 之后讲授 因此 可用一般等价关系的定义来阐述图的同 构关系 代数系统的同构关系和组合计数中的等价关系 等 这是从一般到特殊的认识过程 在离散数学各个部分的教学过程中 可以等价关系作 为一条重要的线索 将离散数学中的各个部分有机地组织 和联系起来 使学生们能够深刻理解等价关系这一重要的 概念 学会用联系的观点去分析 思考和解决问题 尽可 能做到对各部分的相关内容融会贯通 这对学生的抽象思 维能力和逻辑推理能力的提高非常有益 2 等价关系的发展和应用 任何事物都是不断发展的 等价关系的概念也同样 如此 自从美国计算机与控制论专家L A Z a d e h 于1 9 6 5 年首 次提出F u z z y 集的概念 从而对经典的C a n t o r 集合理论做 出了深刻的推广以来 模糊数学已经逐步发展成为一个较 为完善的数学分支 并在众多的领域特别是人工智能领域 获得了卓有成效的应用 经典的二元关系理论中存在一个 缺限 即没有考虑元素与元素间关系程度的不同 在z a d e h 提出了F u z z y 集的概念以后 人们便将经典的二元关系扩 充为模糊数学中的模糊二元关系 通过模糊二元关系可以 较好地刻画元素与元素间关系程度的不同 以模糊二元关 系为基础 人们很自然地提出了模糊等价关系的概念 借 助于模糊等价关系 可以较好地解决具有F u z z y 性的聚类分 析问题 而聚类分析则是数据挖掘领域中的重要课题之一 比较建立在经典集合理论基础上的等价关系和建立 在模糊二元关系基础上的模糊等价关系的定义 容易看 出 在C a n t o r 集合理论基础上的等价关系是模糊等价关系 的特例 而模糊等价关系则是C a n t o r 集合理论基础上的等 价关系的推广 是更高层次上的抽象 在教学过程中适当介绍模糊等价关系 一方面可以使 学生们加深对等价关系概念的理解 学会用发展的眼光分 析和解决问题 另一方面可以克服大多数离散数学教材只 注重阐述理论而很少涉及其理论在计算机领域中的应用 的缺陷 使学生们尽可能多地了解离散数学在计算机领域 中的具体应用 提高学习离散数学的兴趣 事实上 等价关系在计算机领域中还有很多应用 例 如在软件工程领域 为了尽可能多的找出软件设计过程中 可能存在的各种错误 常常使用一种被称之为 等价类划 万方数据 轸妒一一1 磊面i 五石磊1 豳豳闽豳豳霾 一 卅 分 的软件测试方法 这种方法实际上就是将所有待测试 的数据所构成的集合划分成若干个符合软件需求规格及 设计规定的有效等价类和若干个不符合软件需求规格及 设计规定的无效等价类 然后在每个有效等价类和无效等 价类中只各取一个数据进行测试 若某个等价类中的一个 数据能测出软件中的错误 则该等价类中的其余数据也能 测出错误 相反地 若某个等价类中的一个数据不能测出 软件中的错误 则该等价类中的其余数据也不能测出错 误 从而可以大大提高软件测试的效率 又如 在数据库理论中 分组查询是一种重要的数据 库操作 它在本质上也是一种等价类的划分 即将相关数 据表中的所有记录作为一个集合 根据记录的一个或多个 属性 字段 的值是否相同来对表中的记录进行分类 字段 值相同的归于同一类 在此基础上可以进行进一步的分组 统计等操作 再如 粗糙集理论是一种处理模糊和不确定性知识的 数学工具 其主要思想就是在保持分类能力不变的前提 下 通过知识约简 导出问题的决策或分类规则 在经典 粗糙集理论 P a w l a k 粗糙集模型 中 等价关系是最为重要 的基本概念之一 经典粗糙集理论的大部分概念均建立在 等价关系的概念之上 目前 粗糙集理论已被成功地应用 于机器学习 决策分析 模式识别 过程控制和知识发现 与数据挖掘等众多领域 3 结束语 为了提高教学效果 使学生的抽象思维能力和逻辑推 理能力真正得到提升 教师可在离散数学各个部分的教学 过程中 以等价关系作为一条重要的线索 将离散数学中 的各个部分有机地组织和联系起来 使学生们能够深刻理 解等价关系这一重要的概念 并学会用联系与发展的观点 去分析 思考和解决问题 这对学生的抽象思维能力和逻 辑推理能力的提高非常有益 圈 参考文献 1 耿素云 屈婉玲 离散数学 M 北京 高等教育出版社 2 0 0 4 2 张文修 吴伟志 梁吉业等 粗糙集理论与方法 M 北京 科学出版社 2 0 0 1 3 胡宝清 模糊理论基础M 武汉大学出版社 2 0 0 4 上接6 6 页 得突出成绩 可申请获得相应的创新实践学分 学生取得 创新实践学分 可以替代教学计划中任选课程的学分 通 过设置灵活多样的考核和评价方式 鼓励 引导学生参与 技术创新 培养学生创新的自觉性 4 意义 通过深入调查研究和教学实践 我们确立了以创新素 质作为素质教育的核心内容 将素质教育与技能型I T 人才 参考文献 培养有机地结合在一起 提出了从基础能力 创造性思维 能力 实践能力 自主学习能力等方面对学生进行有针对 性地培养创新素质的观点和方法 对教学理念和方法进行 了改革和创新 将创新素质的培养融入到了课程设置和教 学过程中 探索出一套目标明确 切实可行的培养方法和 途径 这是在当今I T 职业教育研究领域中进行的一次非常 有意义地探索 具有一定的应用价值 圈 1 薛娇 增强自主创新能力防止科研不端行为 访教育部科技委主任 中国工程院院士倪维斗 中国高校科技与产业 化 2 0 0 7 0 5 2 9 3 1 2 李云芝 大学生创新能力的培养 J 河南商业高等专科学校学报 2 0 0 3 0 3 9 5 9 7 3 朱峰 思想政治教育与大学生创造性思维培养研究 D 大连海事大学 4 郑婧 大学生自主创新能力培养研究 D 西北工业大学 2 0 0 7 5 晁蓉 熊万里 关于培养大学生创新能力与实践能力的思考 J 武汉交通管理干部学院学报 2 0 0 3 0 1 7 7 8 0 6 牟艳娟 科技活动与大学生创新能力的培养 J 改革与战略 2 0 0 3 0 9 6 9 7 1 7 邱丽萍 张凤华 张继红 着重培养大学生创新能力的教学法研究与改革 J 中国包装工业 2 0 0 3 1 2 8 徐建洪 浅析非智力因素对大学生创新能力的影响 J 江苏经贸职业技术学院学报 2 0 0 3 3 8 7 8 8 万方数据 离散数学 中的等价关系 离散数学 中的等价关系 作者 吴国兵 作者单位 南京审计学院 信息科学学院 南京 210029 刊名 计算机教育 英文刊名 COMPUTER EDUCATION 年 卷 期 2009 1 参考文献 3条 参考文献 3条 1 耿素云 屈婉玲 离散数学 2004 2 张文修 吴伟志 梁吉业 粗糙集理论与方法 2001 3 胡宝清 模糊理论基础 2004 本文读者也读过 10条 本文读者也读过 10条 1 李夕广 LI Xi guang 集合上的等价关系的构造 期刊论文 科学技术与工程2008 8 11 2 许会峰 尚玉伟 XU Hui feng SHANG Yu wei 等价关系 商集和集合的划分 期刊论文 保定学院学报 2009 22 4 3 王新春 李晓颖 马俊红 WANG Xin chun LI Xiao ying MA Jun hong 离散数学中等价关系的教学导入与导出 期 刊论文 河北理工大学学报 社会科学版 2010 10 5 4 谢晋 Xie Jin 试谈离散数学在计算机学科中的重要性 期刊论文 黄石理工学院学报2006 22 1 5 李克清 周贤善 LI Ke qing ZHOU Xian shan 等价关