《离散数学》课程教学大纲

1、离散数学课程教学大纲、课程基本信息开课单位信息与网络工程学院课程类别专业基础课程名称离散数学 Discrete Mathematics课程编码ZJ28104开课对象网络工程、计算机科学与技术专业本科学生开课学期3学时/学分64/4先修课程高等代数、线性代数课程简介：离散数学是计算机科学与技术、网络工程等专业的一门重要的专业基础课，也是专业基础理论的核心课程。本课程介绍信专业所需要的逻辑推理理论、集合与关系、特殊代数 系统、图论及其应用等离散数学基础知识,为进一步学习信息与计算科学的基本理论和方法奠 定基础。内容包括数理逻辑、集合论、代数结构、图论共四部分。二、课程教学目标本课程教学应按照大纲要

2、求， 注重培养学生系统学习知识的能力，使学生在学习过程中,在掌握离散数学基本理论和知识的同时，逐步提高自身的的抽象的逻辑思维和严密的逻辑推理能力，提升学生的专业理论水平、业务素质、分析和解决实际问题的能力。1、掌握命题逻辑和谓词逻辑基本方法、基本理论和基本应用。2、掌握集合运算、关系以及关系运算，理解集合划分和等价关系的联系。3、掌握代数系统的概念。4、掌握图、树相关理论、方法和应用。三、教学学时分配离散数学课程理论教学学时分配表章次主要内容学时分配教学方法或手段A章命题逻辑的基本概念4讲授法第F命题逻辑等值演算6讲授法第三章命题逻辑的推理理论4讲授法第四章一阶逻辑的基本概念4讲授法第五章一阶

3、逻辑等值演算与推理6讲授法用八早集合4讲授法第七章一儿大系12讲授法第八章函数4讲授法第九章代数系统4讲授法第1早图的基本概念6讲授法早欧拉图与哈密顿图4讲授法早树6讲授法合计64理论学时包括讨论、习题课等学时。四、教学内容和教学要求第一章 命题逻辑的基本概念（4学时）（一）教学要求通过本章内容的学习， 了解命题和命题公式的基本概念，理解命题公式赋值的意义，掌握命题的判断、逻辑联结词的定义、命题的符号化以及用真值表法判断命题公式的类型。（二）教学重点与难点教学重点：命题的概念及其符号化，逻辑联结词，命题公式的真值表表示教学难点：命题的符号化、命题公式类型的判断（三）教学内容第一节命题与逻辑联结

4、词1 .命题的基本概念2 .逻辑联结词的定义3 .命题的符号化第二节命题公式及其赋值1 .命题公式的基本概念2 .命题公式的赋值及其类型判断本章习题要点：命题的判断及其符号化，利用真值表判断公式的类型。第二章 命题逻辑等值演算（ 6 学时）（一）教学要求通过本章内容的学习， 了解等值式的基本概念和常见的联结词完备集， 掌握等值式的判断以及利用等值演算法、 真值表法将任给公式化为主析取 （主合取） 范式并判断公式的类型，了解常见的联结词完备集。（二）教学重点与难点教学重点：等值式，等值演算教学难点：析取范式和合取范式（三）教学内容第一节 等值式1等值式的基本概念及其判断2基本等值式和等值演算第二

5、节 析取范式与合取范式1析取范式和主析取范式2合取范式和主合取范式第三节 联结词的完备集1联结词的完备集本章习题要点： 等值式的证明， 求公式的主析取范式和主合取范式， 将公式化为仅含给定的联结词的与之等值的公式。第三章 命题逻辑推理理论（ 4 学时）（一）教学要求通过本章内容的学习， 了解自然推理系统P 的概念， 理解推理的形式结构和有效推理的意义，掌握常用的推理规则以及在自然推理系统中构造有效推理的证明。（二）教学重点与难点教学重点：推理的形式结构，自然推理系统教学难点：推理规则，自然推理系统（三）教学内容第一节 推理的形式结构1推理的形式结构和有效推理2推理定律第二节 自然推理系统P1自

6、然推理系统P 和推理规则2附加前提证明法和归谬法本章习题要点：推理的符号化，在自然推理系统P 中构造推理的证明。第四章 一阶逻辑的基本概念（ 4 学时）（一）教学要求通过本章内容的学习， 了解个体词、 谓词、 量词、 变元、 个体域、 量词辖域、 谓词公式、代换实例等概念，理解一阶逻辑公式的成真解释或成假解释，掌握一阶逻辑命题的符号化。（二）教学重点与难点教学重点：一阶逻辑命题的符号化教学难点：一阶逻辑命题的符号化，一阶逻辑公式的解释（三）教学内容第一节 一阶逻辑命题符号化1个体词、谓词、量词、变元、个体域的基本概念2一阶逻辑命题的符号化第二节 一阶逻辑公式及其解释1谓词公式、量词辖域的概念2

7、谓词公式的解释本章习题要点：一阶逻辑命题的符号化，谓词公式的解释，判断谓词公式的类型。第五章 一阶逻辑等值演算与推理（ 6 学时）（一）教学要求通过本章内容的学习， 了解一阶逻辑等值式的基本概念， 理解基本的逻辑等值式的意义，掌握一阶逻辑等值演算方法、 一阶逻辑的推理理论以及在自然推理系统中给出有效推理的证明。（二）教学重点与难点教学重点：基本的逻辑等值式，逻辑等值演算方法，一阶逻辑的推理理论教学难点：一阶逻辑的推理理论 （三）教学内容第一节 一阶逻辑等值式与置换规则1一阶逻辑等值式与置换规则2一阶逻辑等值演算第二节 一阶逻辑的推理理论1自然推理系统与推理规则本章习题要点：一阶逻辑的等值演算，

8、在自然推理下构造推理的证明。第六章 集合（ 4 学时）（一）教学要求通过本章内容的学习， 了解集合的基本概念及集合的表示法， 理解集合的运算及其性质，掌握集合中常见的恒等式以及集合恒等式的证明。（二）教学重点与难点教学重点：集合的运算，有穷集合的计数，集合恒等式教学难点：有穷集合的计数，集合恒等式（三）教学内容第一节 集合的基本概念及其运算1集合的基本概念及其表示2集合的运算第二节 有穷集的计数与集合恒等式1有穷集的计数2集合恒等式本章习题要点：集合的运算，集合的计数，集合恒等式的证明。第七章 二元关系 （ 12 学时）（一）教学要求通过本章内容的学习， 了解关系的基本概念及其表示方法， 理解

9、关系的闭包， 掌握关系的运算、性质等价关系和集合的划分以及偏序关系。（二）教学重点与难点教学重点：关系的运算和性质，等价关系和划分教学难点：关系的性质，等价关系和划分（三）教学内容第一节 有序对与笛卡尔积1有序对的基本概念2笛卡尔积的基本概念及其性质第二节 二元关系1二元关系的基本概念及其表示第三节关系的运算1二元关系的运算及其性质第四节关系的性质1关系的性质及其判定2具有特殊性质的关系经过运算后的性质第五节 关系的闭包1关系的闭包及其性质2关系的闭包的求解第六节 等价关系与划分1等价关系与等价类的概念及性质2等价关系与划分的关系第七节 偏序关系1偏序关系及其哈斯图表示2偏序集中的特殊元素本章

10、习题要点：关系的矩阵表示，关系的运算，关系的性质判断，求解关系的闭包，等价关系的判断，偏序关系的判断及哈斯图，寻找偏序关系中的上界、，确界、下界、下确界、极大元、最大元、极小元、最小元。第八章 函数 （ 4 学时）（一）教学要求通过本章内容的学习， 掌握函数的基本概念与性质， 掌握逆函数和复合函数的基本概念与性质，了解函数作为工具在集合的基数研究中所起的作用。（二）教学重点与难点教学重点：函数的基本概念与性质，逆函数和复合函数的基本概念与性质教学难点：复合函数的运算（三）教学内容第一节 函数的基本概念及其运算1函数的基本概念2函数的复合与反函数第二节 双射函数与集合的基数1双射函数与集合的基数

11、2可数集及其判断本章习题要点：判断函数的类型（单射、满射、双射），函数的复合运算，计算集合的基数，判断可数集与不可数集。第九章 代数系统（ 4 学时）（一）教学要求通过本章内容的学习， 掌握二元运算的概念和相关性质， 掌握代数系统的基本概念和性质，了解代数系统之间的同构关系和同态关系。（二）教学重点与难点教学重点：二元运算，运算律，特异元素教学难点：代数系统的同态与同构（三）教学内容第一节 二元运算及其性质1二元运算2二元运算律及特异元素第二节 代数系统及其同态与同构1代数系统与子代数系统2代数系统的同态与同构本章习题要点： 判断运算的封闭性， 判断运算满足的定律，判断子代数系统，判断代数系统

12、的同态与同构。第十章 图的基本概念（ 6 学时）（一）教学要求通过本章内容的学习， 掌握图的基本概念与性质及表示法， 了解图中路径、 通路和回路的基本概念和应用，掌握图中可达性和连通性的概念和求解方法。（二）教学重点与难点教学重点：图的矩阵表示，图的连通性和可达性教学难点：图的连通性和可达性判定（三）教学内容第一节 图1有向图和无向图的基本概念2子图、生成子图与导出子图3图的同构4图的运算第二节 通路与回路1通路与简单通路2回路与简单回路第三节 图的连通性1无向图的连通性与连通分支2有向图的连通性3二部图及其判断第四节 图的矩阵表示1无向图和有向图的关联矩阵2有向图的邻接矩阵和可达矩阵及应用本

13、章习题要点：图的概念及其图形表示，判断正整数列是否可图化，判断图的连通性，求解连通图的边割集和点割集以及边连通度和点连通度， 图的矩阵表示及其在寻找通路和回路中的应用，二部图的判断。第十一章 欧拉图与哈密顿图 （ 4 学时）（一）教学要求通过本章内容的学习， 掌握欧拉图与哈密顿图的基本概念， 掌握欧拉图的判定方法。 了解哈密顿图的判定方法，掌握哈密顿图的应用。（二）教学重点与难点教学重点：欧拉图的判定，哈密顿图的应用。教学难点：哈密顿图的判定（三）教学内容第一节 欧拉图1欧拉回路和欧拉路径2欧拉图的判断第二节 哈密顿图1哈密顿回路与哈密顿路径2哈密顿的判断本章习题要点： 寻找欧拉路径和欧拉回路

14、， 寻找哈密顿路径和哈密顿回路， 欧拉图和哈密顿图的判断。第十二章 树 （ 6 学时）（一）教学要求通过本章内容的学习， 掌握树的概念及等价定义， 了解子树、 生成树的概念， 掌握根树、二叉树及其应用。（二）教学重点与难点教学重点：树的概念及性质教学难点：树的等价定义，根树及应用（三）教学内容第一节 无向树及其性质1无向树的基本概念2无向树的等价命题第二节 生成树1连通图的生成树2带权图的最小生成树第三节 根树及其应用1根树与最优二叉树2二叉树的周游及应用本章习题要点： 画出具有给定要求的不同构的树， 求连通图的生成树和带权图的最小生成树，求最优二叉树及其周游。五、教学方法或手段教学方法：主要

15、采取讲授法。教学手段：板书，自主学习网站。六、考核方式及评价要求考核方式：课堂考勤、理论课考查、作业、综合测试。 1 平时成绩占20%，包含课堂考勤、理论课考查和作业； 2 期末考试占80%，采用综合测试的方式。考核要求： 本课程教学应按照大纲要求， 注重培养学生系统学习知识的能力， 使学生在学习过程中， 不仅掌握离散数学基本理论和知识， 更注重掌握各章节之间的内在联系， 同时加强利用所学知识解决实际问题的能力，从而达到对本课程系统掌握的目的。1掌握数理逻辑, 集合论 , 代数结构和图论的基本概念和原理；2熟练运用数理逻辑、集合论、图论中的理论和方法，分析和解决实际问题；3掌握关系理论、图论中的经典算法及其应用。七、教材及教学主要参考书推荐教材：屈婉玲、耿素云、张立昂主编，离散数学，高等教育出版社， 2008 年 3 月第 1 版，2011 年 11 月第 9 次印刷。参考书目：1屈婉玲、耿素云、张立昂主编，离散数学题解（修订版），清华大学出版社，2004；2. 左孝凌等主编，离散数学，上海科技文献出版