《离散数学》教学大纲

1、离散数学Discrete Mathematics一、课程基本情况课程类别：学科基础课课程学分： 3 学分课程总学时：48 学时，其中讲课： 48 学时，习题课： 学时课程性质： 必修开课学期： 第 3 学期先修课程： 高等数学，线性代数适用专业： 网络工程专业教 材： 冯伟森，栾新成，石兵编著，离散数学，机械工业出版社，2011开课单位： 计算机与软件 学院 计算机科学与技术 系二、课程性质、教学目标和任务离散数学是计算机专业的专业必修课，是数学中涉及面非常广泛的一门学科。它不仅是计算机科学中重要的基础理论之一，是学习后续计算机专业课程不可缺少的数学工具，也是培养学生抽象思维能力和逻辑推理能力

2、的核心课程。该课程结合计算机学科的特点，主要研究离散量结构及相互关系，是一门理论性较强，应用性较广的课程。该课程的教学任务是：为计算机专业本科生提供学习本专业必需的处理离散对象的数学知识；为计算机专业本科生提供学习本专业必须的理论过程训练；通过本课程的学习，使学生掌握处理离散结果所必需的描述工具和抽象、严格的数学方法以及这些方法在计算学科各领域的应用，初步形成使用理论过程描述问题的习惯，为今后其他计算机课程学习奠定必要的基础。三、教学内容和要求1、数理逻辑 （16+2学时）教学内容(1) 命题及其真值(2) 重言式(3) 范式(4) 联结词的扩充与归约。(5) 推理规则和证明方法。(6) 谓词

3、和量词(7) 谓词演算的永真公式。(8) 谓词演算的推理规则基本要求(1) 掌握命题、命题联结词的概念；理解命题公式的递归定义，熟练掌握命题符号化的方法，掌握命题公式真值表的求法。(2) 了解范式的概念，掌握求命题公式的析取范式、合取范式和主式的方法。(3) 了解与非、或非和异或等联结词及联结词的归约。(4) 掌握常用的推理规则和证明方法。(5) 理解谓词、量词、谓词公式、自由变元和约束变元的概念。(6) 掌握谓词演算基本的永真公式。(7) 会利用谓词演算的推理规则进行简单的推理重点：重言式与蕴含式；推理规则；谓词的概念；命题函数与量词；约束变元；谓词演算的等价式与蕴含式；谓词演算的推理规则难

4、点：命题公式与翻译；推理规则；谓词的概念；命题函数与量词；谓词公式与翻译；约束变元；谓词演算的推理规则 2、集合 （3学时）教学内容(1) 集合论的基本概念(2) 集合的运算(3) 集合的笛卡尔乘积基本要求 (1) 掌握子集、空集、全集、相等、密集等基本概念。(2) 理解集合的基本概念表示法；掌握集合的交、并、差和补等概念及交换律、结合律、分配律和De Morgan律等运算律，证明集合等式。(3) 掌握集合的笛卡尔乘积的运算。重点：集合的概念与表示；集合的运算；序偶与笛卡尔积难点：序偶与笛卡尔积3、二元关系 （10+2学时）教学内容(1) 关系的基本概念(2) 关系的运算(3) 关系上的闭包运

5、算(4) 次序关系(5) 等价关系和划分基本要求(1) 理解关系及有关概念，掌握关系图、关系矩阵及关系的特性（自反性、反自反性、对称性、反对称性和传递性）。(2) 掌握关系的合成、关系的幂关系、关系合成及其有关性质。(3) 掌握逆关系、关系的闭包运算（自反闭包、对称闭包和传递闭包）的性质及求法。(4) 掌握偏序集合、拟序集合、线序集合、良序集合及特殊元素的概念及性质。(5) 理解等价关系、覆盖及划分的概念，掌握求集合的等价类方法及划分的积与和。重点：关系的性质；关系的闭包运算；复合关系与逆关系；等价关系与等价类；序关系难点：关系的闭包运算；复合关系与逆关系；等价关系与等价类；序关系4、函数 （

6、4学时）教学内容(1) 函数的基本概念(2) 特殊函数类(3) 逆函数基本要求(1) 理解函数的概念，掌握函数的合成运算。(2) 理解满射、单射和双射函数的概念，了解置换、特征函数的概念及运算。(3) 理解逆函数和规范映射的概念及性质。重点：你函数与符合函数难点：逆函数与复合函数5、图论 （9+2学时）教学内容(1) 图的基本概念(2) 路径和回路(3) 图的矩阵表示(4) 二部图(5) 平面图(6) 树(7) 有向树基本要求(1) 理解图的基本概念，了解几类特殊的图。(2) 理解路径与回路及有关概念（基本路径、简单路径、基本回路和简单回路），了解连通图的概念（强连通、单向连通、弱连通、强分图

7、、单向分图和弱分图）。(3) 掌握求赋权图最短路径的Dijkstra算法。(4) 掌握欧拉路径、欧拉回路和欧拉图的判别法，理解哈密尔顿路径、哈密尔顿回路和哈密尔顿图的概念，了解其性质和最邻近算法。(5) 掌握图的矩阵表示（邻接矩阵和可达性矩阵）。(6) 了解二部图的概念，知道求最大匹配的方法。(7) 了解平面图的概念，会进行平面图（或非平图）的判别，了解Kuratowski定理、对偶图和五色问题。(8) 理解无向树和生成树的概念，掌握用Kruskal算法求最小生成树。(9) 了解有向树及有关概念，理解二元树的概念和性质，知道搜索树和决策树。重点：图的基本概念；连通性；图的表示；欧拉图与汉密尔顿图；平面图；树与生成树难点：欧拉图与汉密尔顿图；平面图；树与生成树。四、课程考核（1）作业等：作业： 6-8 次（2）考核方式：闭卷考试（3）总评成绩计算方式：平时成绩30%+期末成绩70%五、参考书目1、耿素云、屈婉玲编著，离散数学（修订版）(第二版)，高等教育出版社， 20072、左孝凌等编，离散数学(第一版)，上海科学技术文献出版社， 19823、段禅伦、魏仕民编著，