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

1、离散数学教学大纲一、课程基本信息中文名称离散数学英文名称Discrete Mathematics适用专业信息管理与信息系统/信息工程先修课程高等数学、线性代数课程类别学科基础课程修读性质必修学分/学时3学分/51学时（实践学时0）考核方式考试二、教学目标本课程对计算机应用人才的培养目标是使学生能够熟练运用离散数学的知识进行系统的建模和分析，具体包括：能够清晰、准确地定义一个概念；能够形式化地表述问题；能够应用这些概念、原理、方法和思想对实际问题和系统进行建模和分析，同时在学科思维方法、逻辑推理、抽象思维能力方面得到提高。三、教学内容及基本要求第一章 命题逻辑（10学时）（一）教学目标1.熟练掌

2、握语句的形式化表示、真值表技术、等值演算方法，运用等值式和推理规则进行推理；2.能够运用本单元的知识解决相应的实际问题；3.培养学生严密的逻辑思维能力、推理证明能力以及形式化表示能力。（二）重点、难点重点：命题、联结词与语句形式化，命题公式及重言式，基本等值式模式，范式，蕴含重言式，命题逻辑推理；难点：语句形式化，重言式，范式的应用，命题逻辑的推理证明。（三）教学方法通过趣味离散数学问题引入，激发学生的学习兴趣。教学内容以讲授为主，辅以多媒体课件。采用以关键词绘制概念地图的方法梳理本单元的知识点及其联系。（四）教学内容1.命题、联结词与语句形式化（2学时）（1）命题及其抽象（2）常用的逻辑联结

3、词（3）语句形式化2. 命题公式及其赋值（2学时）（1）命题公式（2）命题公式的赋值及真值表（3）命题公式的类型3. 命题逻辑等值演算（4学时）（1）等值式（2）范式与联结词的归约4. 命题逻辑的推理理论（2学时）（1）推理的形式结构（2）自然推理系统P（五）作业及要求本单元是数理逻辑的基础知识，既是所有其他理论的逻辑基础，同时也是形式化表示的重要工具。因此，要重视本单元的练习，包括语言的形式化表示、等值演算、求范式和推理证明。第二章 谓词逻辑（8学时）（一）教学目标1.能够熟练运用谓词逻辑进行语句形式化表示并判断谓词的真值；2.能正确理解谓词公式的有效性，熟记谓词公式的基本等值式模式和自然推

4、理系统F的推理规则，并能在谓词逻辑下完成推理证明。（二）重点、难点重点：个体词、谓词、量词与语句形式化，谓词公式及重言式，基本等值式模式，蕴含重言式，谓词逻辑的推理证明。难点：个体词、谓词、量词与语句形式化，谓词公式重言式，谓词逻辑的推理证明。（三）教学方法采用类比教学法，与命题逻辑的相应内容进行对比教学。（四）教学内容1.谓词逻辑的基本概念（4学时）（1）个体词、谓词和量词（2）语句形式化（3）谓词公式（4）谓词公式及其解释2.谓词逻辑等值演算与推理（4学时）（1）等值式与置换规则（2）谓词逻辑前束范式（3）自然推理系统F与推理规则（五）作业及要求熟练掌握谓词逻辑语句的形式化表示、谓词公式的

5、解释，能够灵活运用谓词逻辑等值式和推理规则进行推理证明。第三章 集合论（15-16学时）（一）教学目标1.本单元是其他离散结构的重要基础，需要熟练掌握集合运算及性质，二元关系的性质及运算，函数的性质及运算；2.熟练掌握集合恒等式的证明以及数学归纳法的证明技术。（二）重点、难点重点：集合的基本运算及其性质，幂集的定义与计算，二元关系的表示与性质，等价关系与序关系，函数的定义与性质；难点：集合相等的证明，幂集的计算、二元关系的性质，运算及闭包的性质，偏序关系的哈斯图及特殊元，复合函数与逆函数的性质。（三）教学方法讲授和多媒体教学相结合的教学方法。关系和函数大量应用于计算机软、硬件系统的建模中，教学

6、中通过引入多种典型事例进行介绍。（四）教学内容1.集合代数（2学时）（1）集合的表示、基本运算和幂集2.二元关系（11-12学时）（1）有序对与笛卡尔积（1学时）（2）二元关系的概念与表示（2学时）（3）二元关系的性质（1-2学时）（4）二元关系的运算与闭包（3学时）（5）等价关系与序关系（4学时）3.函数（2学时）（1）函数的定义与性质（2）复合函数与逆函数（五）作业及要求本单元是离散数学的基础，应适当多布置习题，如集合恒等式的证明，幂集的计算，关系的表示，关系性质的判定，等价关系和偏序关系的辨别，偏序集特殊元的求解，函数性质的讨论，复合函数和逆函数的计算等。（六）课外学习要求加强关系和函数

7、在计算机软、硬件系统中应用的建模学习。第四章 图与树（12-14学时）（一）教学目标1.本单元是图论的核心基础知识，图和树既是十分重要的数学建模工具，又是应用十分广泛的数据存储结构；2.熟练掌握图的基本概念，树的性质及应用，握手定理等重要定理，典型的图算法。（二）重点、难点重点：握手定理，图的连通性，图的矩阵表示及应用，树的定义与性质，生成树的求法及应用，根树的应用；难点：图论知识的理解与应用，结论的证明（构造证明和反证法）。（三）教学方法在讲授基本概念、定理和相应证明的基础上，结合航班安排、程序调用、通信网络、路由分配、决策与博弈等典型实例让学生掌握图的建模和分析方法。（四）教学内容1.图的

8、基本概念（8学时）（1）无向图与有向图、子图与补图、握手定理、图的同构（2学时）（2）图的连通性（通路与回路、连通性、连通度、连通分支）（2学时）（3）有向网络、图的最短路径与关键路径（2学时）（4）图的矩阵表示（2学时）2.树（4-6学时）（1）树的定义与性质（1-2学时）（2）生成树（1学时）（3）根树及应用（2-3学时）（五）作业及要求习题安排时，除图、树的基本概念、定理的应用问题外，注意训练学生利用图和树进行表示问题、解决问题等数学建模的能力。第五章 特殊的图（6学时）（一）教学目标1.特殊图在实际问题的建模中有着广泛的应用，熟练掌握特殊图的特性；2.重点掌握特殊图的相关典型算法。（二

9、）重点、难点重点：欧拉图、哈密顿图、偶图（二分图）、平面图达的定义和应用，平面图的欧拉公式及推论；难点：欧拉图、哈密顿图、偶图、平面图的判断定理及实际应用。（三）教学方法在讲授基本概念、定理和相应证明的基础上，注意结合它们在建模中的应用，比如，一笔画问题、蚂蚁比赛问题、计算机鼓轮设计、中国邮路问题等。（四）教学内容1.欧拉图与哈密顿图（2学时）（1）欧拉图（2）哈密顿图2.平面图（2学时）（1）平面图的基本概念（2）欧拉公式（3）平面图的判断3.偶图与匹配（2学时）（五）作业及要求针对各类特殊图的特点，布置适当数量的课后习题。以特殊图和算法的应用为主，适当考虑一些实际应用问题以培养学生的建模能

10、力。四、考核形式及成绩评定（一）考核形式 闭卷笔试。（二）成绩评定课程考核由平时成绩（作业、小测验等）和期末考试成绩两部分综合评定，分别占课程总成绩的30%和70%。（三）考题设计考试内容大体由4部分组成：（1）考查基础知识、基本概念掌握情况的选择题和填空题，大致占考试内容总量的30%；（2）考查数学建模能力和问题求解能力的分析或计算题，大致占考试内容总量的40%；（3）考查逻辑思维能力、逻辑推理能力的证明题，大致占考试内容总量的10%；（4）考查综合应用能力的试题，大致占考试内容总量的20%。五、教材与参考书教 材：屈婉玲,耿素云,张立昂.离散数学.北京:高等教育出版社,2008年3月参考书

11、：1 左孝凌.离散数学.上海：上海交通大学出版社,1982年02月2 王元元,桂芸.离散数学导论.北京：科学出版社,2002年02月3 徐洁磐.离散数学导论.（第3版）.北京：高等教育出版社,2004年06月4 美D.S.Malik著，邱仲潘译.离散数学结构.（第1版）.北京：高等教育出版社,2005年11月5 美 Kenneth H,Rosen著,袁崇义,屈婉玲等译.离散数学及其应用.（第4版）.北京：机械工业出版社,2002年01月6 傅彦,顾小丰,王庆先,刘启和.离散数学及其应用.北京：高等教育出版社,2007年07月六、其他本课程学时非常紧张，注意对学生的导学，给学生一定的思考空间。要有效利用课堂时间，