《计算机科技专业《离散数学》教学大纲》由会员分享，可在线阅读，更多相关《计算机科技专业《离散数学》教学大纲（21页珍藏版）》请在金锄头文库上搜索。
1、离散数学教学大纲安徽大学计算机科学与技术学院二 OO六 年 六 月前言离散数学 课程是计算机科学与技术专业高等教育的专业基础课程。离散数学是现代数学的一个重要分支， 是学习计算机科学与技术专业理论必不可少的数学工具。 本课程主要研究离散对象的结构及相互关系，对提高学生的抽象思维与逻辑推理能力有重要作用。设置本课程的目的是： 培养学生的数学思维能力， 使学生得到良好的数学训练，提高学生的抽象思维和逻辑推理能力，并使学生掌握处理离散结构所必须的描述工具和方法，为其从事计算机的应用提供坚实的理论基础。学习本课程的要求是： 通过本课程的学习， 学生应正确理解和熟练掌握基本概念、基本定理及其证明方法，提
2、高运用基本理论分析和解决实际问题的能力，为在后续专业课和实际工作中运用本课程的基本知识打下基础。先修课程要求：高等数学。本课程计划 144 学时，7 学分，分两学期完成，分别称为离散数学（上）和离散数学（下）。离散数学（上）计划72 学时，3.5 学分；离散数学（下）计划72 学时， 3.5 学分。选用教材：离散数学，方世昌，西安电子科技大学出版社，2000 出版。教学手段：多媒体教学。考核方法：考试。教学进程安排表：离散数学（上）周次学时数教 学 主 要 内 容教学方法备注1 4 命题、逻辑联结词及真值表、命题符号化命题公式的概念及命题公式的基本等值式讲授2 4 命题演算的规则和对偶原理析取
3、范式与合取范式的概念及计算讲授3 4 主析取范式与主合取范式的概念及计算联结词的扩充与归约讲授4 4 命题逻辑的推理规则命题逻辑的证明方法讲授5 4 个体、谓词和量词等概念、谓词符号化谓词公式和自由变元等基本概念讲授6 4 谓词演算的基本等值式谓词演算的推理规则及证明方法讲授7 4 第一章习题课集合的基本概念习题课讲授8 4 集合上的基本运算、文氏图集合的归纳定义及数学归纳法讲授9 4 序偶和集合的笛卡尔乘积第二章习题课讲授习题课10 4 二元关系的基本概念、关系矩阵和关系图二元关系的特性讲授11 4 关系的合成及合成关系的矩阵表达逆关系、关系的闭包运算讲授12 4 偏序关系及其哈斯图表示偏序
4、集中的特殊元素、拟序、良序和线序讲授13 4 等价关系的概念和性质、等价类划分的概念、划分的积与和讲授14 4 第三章习题课函数的基本概念及函数的合成习题课讲授15 4 函数的性质、特殊函数类逆函数的概念及性质、单侧逆函数讲授16 4 第四章习题课有限与无限集合、可数与不可数集合等概念习题课讲授17 4 可数与不可数集合的性质基数的比较、无限集合的特性讲授18 4 第五章习题课总复习习题课离散数学（下）周次学时数教 学 主 要 内 容教学方法备注1 4 代数的构成和分类、么元和零元概念及性质逆元的概念及性质、子代数讲授2 4 代数同态和同构的概念及性质同余关系的概念及判定讲授3 4 商代数和积
5、代数的概念及性质半群和独异点的概念及性质讲授4 4 群的定义及性质置换群和循环群的概念及性质讲授5 4 子群的定义及判定、群同态的概念陪集和拉格朗日定理讲授6 4 正规子群和商群环、整环和域的概念讲授7 4 子环和理想第六章习题课讲授习题课8 4 作为偏序集的格的定义及性质作为代数系统的格的定义及性质讲授9 4 子格、格同态、格的积代数分配格和有界格的定义、判定及性质讲授10 4 有补格和有补分配格的定义及性质布尔代数的定义及性质、子布尔代数讲授11 4 有限布尔代数的原子表示布尔表达式和布尔函数讲授12 4 第七章习题课图的基本概念、结点次数、图的同构和运算习题课讲授13 4 子图与补图、路
6、径和回路连通图的概念及性质、赋权图的最短路径讲授14 4 欧拉路径（回路） 、哈密尔顿路径（回路）图的矩阵表示讲授15 4 二部图的概念、判定及应用平面图和欧拉公式讲授16 4 对偶图和五色原理无向树的定义及性质讲授17 4 生成树及最小生成树有向树的定义及性质、搜索树和决策树讲授18 4 第八章习题课总复习习题课第一章数理逻辑一、学习目的通过本章的学习，理解命题、联结词、命题公式、（主）析/合取范式、个体、谓词、量词、谓词公式、指派等概念；掌握公式真值表的构造及命题符号化方法、 常用的基本等值式及其应用、 常用的永真蕴涵式及其在逻辑推理中的应用、（主）析 /合取范式的计算、命题演算和谓词演算
7、的推理规则和证明方法。第一章计划 26 学时。二、课程内容1.1 命题（一）命题的概念。（二）命题联结词及其真值表。（三）命题符号化。（四）命题变元和命题公式的概念。1.2 重言式（一）指派、重言式、逻辑恒等式、永真蕴含式等基本概念。（二）常见的逻辑恒等式和永真蕴含式。（三）逻辑恒等式和永真蕴含式的基本性质。（四）命题演算的基本规则：代入规则、替换规则。（五）命题演算中的对偶原理。1.3 范式（一）基本积与基本和的概念。（二）析取范式与合取范式的概念。（三）析取范式与合取范式的计算。（四）极小项与极大项的概念。（五）主析取范式与主合取范式的概念。（六）主析取范式与主合取范式的计算。（七）主析取
8、范式与主合取范式的个数。1.4 联结词的扩充与归约（一）与非、或非、异或 ( 排拆或 ) 、蕴含否定的定义。（二）与非、或非、异或 ( 排拆或 ) 、蕴含否定的基本性质。（三）联结词完备集的概念。（四）联结词完备集的判定。1.5 推理规则和证明方法（一）推理的有效性的概念。（二）推理规则： T 规则（前提引入）、 P 规则（结论引入）等。（三）形式推理的表上作业。（四）证明方法：演绎法、归谬法等。1.6 谓词和量词（一）个体和谓词的概念。（二）全称量词和存在量词的概念。（三）谓词符号化。（四）量化断言与命题的关系。（五）谓词公式的概念。（六）自由变元与约束变元的概念。（七）谓词公式中的改名规则
9、。1.7 谓词演算的永真公式（一）谓词公式的解释。（二）谓词演算的基本永真公式。（三）谓词演算的几条规则：代入规则、替换规则和对偶原理。1.8 谓词演算的推理规则（一）术语“ A(x)对 y 是自由的”的意义。（二）全称指定规则（ US ）（全称量词消去规则）。（三）存在指定规则 (ES)（存在量词消去规则）。（四）存在推广规则 (EG)（存在量词引入规则）。（五）全称推广规则（ UG ）（全称量词引入规则）。三、重点、难点提示和教学手段（一）本章的重点是各个概念、公式演算和推理方法的教学。（二）本章的难点是谓词符号化和应用公式进行逻辑推理。四、思考与练习（一）简单命题与符合命题的区分。（二）
10、可兼或和排斥或的联系和区别。（三）含有 n 个命题变元的命题公式有多少不同的指派？（四）关于 n 个命题变元可以构造多少个真值表？（五）如何构造结论形式为PQR 或（PQ）R 的证明。（六）如何用存在量词和全称量词来表示存在唯一？第二章集合一、学习目的通过本章的学习， 了解自然数的归纳定义； 理解数学归纳法第一原理及第二原理；掌握集合的基本概念、基本运算的相关性质和文氏图表示、幂集的概念、有限集的计数方法、集合的归纳定义、n 元组和笛卡儿乘积等概念和性质。第二章计划 10 学时。二、课程内容2.1 集合论的基本概念（一）集合的基本概念。（二）集合的表示方法。（三）罗素悖论。（四）集合间的包含关
11、系。2.2 集合上的运算（一）集合上的交、并、差、补、环和与环积等运算的定义和性质。（二）集合上的交和并运算的扩展。（三）集合运算的文氏图表示。（四）幂集合的概念。（五）有限集的基数公式及应用。2.3 归纳法和自然数（一）集合的归纳定义法。（二）自然数的归纳定义和皮亚诺(Peano)公设。（三）数学归纳法第一原理和第二原理。2.5 集合的笛卡儿乘积（一）序偶和 n 重组的概念。（二）集合的笛卡儿乘积的概念。（三）集合的笛卡儿乘积的性质。三、重点、难点提示和教学手段（一） 本章的重点是集合的基本概念和运算、 集合的归纳定义和笛卡儿乘积。（二）本章的难点是集合的交和并运算的推广、自然数的归纳定义。
12、四、思考与练习（一）集合论中的包含和属于关系的区别。（二）数学归纳法第一原理和第二原理的联系和区别。第三章二元关系一、学习目的通过本章的学习，理解关系的合成及逆关系的概念、 等价关系和划分的联系；掌握关系的基本概念、 二元关系的关系矩阵和关系图表示、关系的特性、 关系的闭包运算、 偏序关系及其哈斯图表示、 等价关系和等价类的概念和性质、划分的概念。第三章计划18 学时。二、课程内容3.1 基本概念（一）关系的概念。（二）空关系、全域关系、恒等关系等一些特殊的关系。（三）二元关系的表示：集合表示法、关系图、关系矩阵。（四）二元关系的特性：自反性、反自反性、对称性、反对称性、传递性。3.2 关系的
13、合成（一）关系的合成运算的概念。（二）关系的合成运算的性质。（三）关系的幂的概念。（四）关系的幂运算的性质。（五）合成关系的矩阵表达。3.3 关系的闭包运算（一）逆关系的概念。（二）逆关系的性质。（三）关系的闭包运算的概念。（四）构造关系的闭包的方法。（五）关系的闭包运算的性质。3.4 次序关系（一）偏序关系和偏序集合的概念。（二）偏序集合的哈斯图表示。（三）偏序集中的特殊元素。（四）拟序集合、线序集合、良序集合的概念。（五）偏序、拟序、线序、良序的性质。3.5 等价关系（一）等价关系和等价类的概念。（二）等价关系的性质。（三）划分的概念。（四）等价关系与划分的联系：等价关系与化分可相互诱导且
14、保持一致性。（五）划分的积与和的概念。（六）划分的积与和的性质。三、重点、难点提示和教学手段（一）本章的重点是各种关系的基本概念、性质及其联系；关系的闭包运算。（二）本章的难点是关系的特性的判定、闭包运算、等价关系与划分的联系。四、思考与练习（一）空关系具有哪些特性？（二）关系的合成运算保持哪些关系的特性？（三）在交、并、差、补等运算下，关系的哪些特性仍保持？（四）偏序集合中最小元素与极小元素的联系和区别。（五） n 元集合上可定义多少个不同的二元关系、偏序关系、等价关系？第四章函数一、学习目的通过本章的学习，了解一些特殊的函数；理解映射、单射、满射、双射等概念；掌握单射、满射、双射的判别方法
15、， 函数的合成运算、 逆函数的概念及性质。第四章计划 8 学时。二、课程内容4.1 函数的基本概念（一）函数和映象等基本概念。（二）函数的合成。（三）函数的归纳定义。（四）偏函数的概念。（五）函数前域的扩大与缩小。4.2 特殊函数类（一）单射、满射、双射的概念。（二）单射、满射、双射的性质。（三）一些特殊的函数。（四）特征函数的概念及性质。4.3 逆函数（一）逆函数的概念。（二）逆函数的性质。（三）逆像和规范映射（自然映射）的概念。（四）单侧逆函数的概念。（五）单侧逆函数的性质。三、重点、难点提示和教学手段（一）本章的重点是函数的基本概念和基本性质。（二）本章的难点是逆函数与单侧逆函数的定义和
16、性质。四、思考与练习（一）函数与关系的联系和区别。（二）逆函数与逆关系的联系和区别。第五章无限集合一、学习目的通过本章的学习， 了解可数与不可数集合的概念， 理解集合基数的概念及比较，掌握一些常见的无限集合所属类别的判定方法。第五章计划10 学时。二、课程内容5.1 可数和不可数集合（一）有限集合和无限集合的概念（二）可数集合的概念。（三）可数集合的性质。（四）基数 c 的概念。5.2 基数的比较（一）集合的等势和优势的概念。（二）集合等势的性质。（三）无限集合的特性。（四）基数的无限性和连续统假设。三、重点、难点提示和教学手段（一）本章的重点是对无限集合的理解和区分。（二）本章的难点是可数无限集合与不可数集合的区别和判定。四、思考与练习（一）自然数集合、整数集合、有理数集合、实数集合等基数的大小关系。（二）集合 A、A 的幂集合和 0,1A这三个集合的基数的关系。第六章代数一、学习目的通过本章的学习， 了解商代数和积代数的构造； 掌握代数系统的概念和有关性质、代数的同态和同构概念、 代数系统的同余关系、 一些重要
