《离散数学理论（计科版）》课程教学大纲

1、离散数学教学大纲一、课程基本信息中文名称离散数学英文名称Discrete Mathematics适用专业计算机科学与技术专业先修课程高等数学、线性代数课程类别学科基础课程修读性质必修学分/学时4学分/68学时（0实践学时）考核方式考试二、教学目标离散数学是计算机科学与技术专业的核心基础课程之一，在计算机科学与技术专业课程体系中起到重要的基础理论支撑作用。本课程的教学总体目标是：一，熟悉形式描述、变换、推理和证明方法；二，熟练掌握离散系统的描述和分析方法；三，了解实际离散系统的建模。本课程教学内容为后续专业课程数字逻辑、算法与数据结构、数据库系统原理、操作系统、编译原理、计算机网络和软件工程等奠

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

3、结词与语句形式化（2学时）（1）命题及其抽象（2）常用的逻辑联结词（3）语句形式化2.命题公式及其赋值（2学时）（1）命题公式（2）命题公式的赋值及真值表（3）命题公式的类型3.命题逻辑等值演算（4学时）（1）等值式（2）范式与联结词的归约4.命题逻辑的推理理论（2学时）（1）推理的形式结构（2）自然推理系统P（五）作业及要求本单元是数理逻辑的基础知识，既是所有其他理论的逻辑基础，也是形式化表示的重要工具。因此，要重视本单元的练习，包括语言的形式化表示、等值演算、求范式和推理证明。（六）课外学习要求了解命题公式的合取范式的可满足问题的消解算法，对学有余力的学生可以借助网络资源对该问题进行深入研

4、究。第二章 谓词逻辑（6-8学时）（一）教学目标1.能够熟练运用谓词逻辑进行语句形式化表示并判断谓词的真值；2.能正确理解谓词公式的有效性，熟记谓词公式的基本等值式模式和自然推理系统F的推理规则，并能在谓词逻辑下完成推理证明。（二）重点、难点重点：个体词、谓词、量词与语句形式化，谓词公式及重言式，基本等值式模式，蕴含重言式，谓词逻辑的推理证明。难点：个体词、谓词、量词与语句形式化，谓词公式重言式，谓词逻辑的推理证明。（三）教学方法采用类比教学法，与命题逻辑的相应内容进行对比教学。（四）教学内容1.谓词逻辑的基本概念（3-4学时）（1）个体词、谓词和量词（2）语句形式化（3）谓词公式（4）谓词公

5、式及其解释2.谓词逻辑等值演算与推理（3-4学时）（1）等值式与置换规则（2）谓词逻辑前束范式（3）自然推理系统F与推理规则（五）作业及要求熟练掌握谓词逻辑语句的形式化表示、谓词公式的解释，能够灵活运用谓词逻辑等值式和推理规则进行推理证明。（六）课外学习要求强化学生的逻辑思维能力，学习用谓词逻辑进行证明这种有效的证明技术。第三章 集合论（14-16学时）（一）教学目标1.本单元是其他离散结构的重要基础，需要熟练掌握集合运算及性质，二元关系的性质及运算，函数的性质及运算；2.熟练掌握集合恒等式的证明以及数学归纳法的证明技术。（二）重点、难点重点：集合的基本运算，幂集，数学归纳法，二元关系的性质，

6、等价关系与序关系，函数的定义与性质；难点：集合的归纳定义、集合相等和包含的证明，二元关系的运算及闭包，复合函数与逆函数。（三）教学方法讲授和多媒体教学相结合的教学方法。关系和函数大量应用于计算机软、硬件系统的建模中，教学中通过引入多种典型事例进行介绍。（四）教学内容1.集合代数（2学时）（1）集合的表示、基本运算和幂集（2）集合的归纳定义与归纳法证明2.二元关系（10-12学时）（1）有序对与笛卡尔积（1学时）（2）二元关系的概念与表示（1-2学时）（3）二元关系的性质（2学时）（4）二元关系的运算与闭包（2学时）（5）集合的覆盖与划分（1学时）（6）等价关系与序关系（3-4学时）3.函数（2

7、学时）（1）函数的定义与性质（2）复合函数与逆函数（五）作业及要求本单元是离散数学的基础，应适当多布置习题，包括计算题和证明题以及一些较简单的应用关系或函数的建模联系。特别是有关集合恒等式的证明应熟练掌握。（六）课外学习要求加强关系和函数在计算机软、硬件系统中应用的建模学习。第四章 基本计数（6学时）（一）教学目标1.熟练掌握基本的计数解题方法和思路；2.理解组合计数问题的求解思路和利用递推关系进行建模。（二）重点、难点重点：多重集合的组合计数，递推关系及应用；难点：鸽笼原理，包含排斥原理，递推关系在数学建模中的应用。（三）教学方法对于中学已经学过的鸽笼原理、组合计数公式与二项式定理可以让学生

8、自行讨论完成。其它以实例讲授和直观演示为主。（四）教学内容1.基本的组合计数公式（6学时）（1）鸽笼原理和计数基本原理（2）基本的组合计数公式与二项式定理（3）多重集合的组合计数（4）包含排斥原理（5）递推关系及应用（五）作业及要求本单元的习题普遍难度较大，有利于培养学生数学建模、映射归约、归纳证明等解决实际问题的综合能力。要求学生对典型应用题目能顺利求解。（六）课外学习要求鼓励学生用多种思路和方法去思考和求解问题，特别是鼓励学生用映射归约的建模技巧，使复杂问题迎刃而解。第五章 图与树（8学时）（一）教学目标1.本单元是图论的核心基础知识，图和树既是十分重要的数学建模工具，又是应用十分广泛的数

9、据存储结构。因此，熟练掌握图的基本概念，树的性质及应用，握手定理等重要定理。（二）重点、难点重点：握手定理，图的同构，图的连通性，树的性质及应用；难点：图的同构和图的连通度。（三）教学方法在讲授基本概念、定理和相应证明的基础上，结合通信网络、关键路径技术、最小费用问题、决策树等实际问题分析其应用。（四）教学内容1.图的基本概念（4学时）（1）无向图与有向图、子图与补图、握手定理、图的同构（2学时）（2）图的连通性（通路与回路、连通性、连通度、连通分支）（2学时）2.树（4学时）（1）树的定义与性质（1学时）（2）生成树（1学时）（3）根树及应用（2学时）（五）作业及要求习题安排时注意训练学生利

10、用图和树进行数学建模的能力以及构造性的证明表述能力。（六）课外学习要求在学生理解图的同构的概念的基础上，指出图同构的判定是图论中的一个重要的但是还未解决的问题，鼓励学生积极探索。第六章 特殊的图（6-8学时）（一）教学目标1.特殊图在实际问题的建模中有着广泛的应用，熟练掌握特殊图的特性；2.重点掌握特殊图的相关典型算法。（二）重点、难点重点：欧拉图、哈密顿图、偶图（二分图）、平面图等特殊图，平面图的欧拉公式；难点：平面图的库拉托夫斯基定理。（三）教学方法在讲授基本概念、定理和相应证明的基础上，注意结合它们在建模中的应用，比如，一笔画问题、蚂蚁比赛问题、计算机鼓轮设计、中国邮路问题等。（四）教学

11、内容1.欧拉图与哈密顿图（3学时）（1）欧拉图（2）哈密顿图2.平面图（2-3学时）（1）平面图的基本概念（2）欧拉公式（3）平面图的判断3.偶图与匹配（1-2学时）（五）作业及要求针对各类特殊图的特点，布置适当数量的课后习题。有些经典的理论证明，要求学生能用自己的语言重述。（六）课外学习要求图论中的理论证明是对学生的一个挑战，涉及的证明技术包括构造性证明、归纳法证明、反证法证明，以及它们的联合应用。通过课外学习促进学生对图论证明技术的初步理解和简单应用。第七章 代数结构（14-16学时）（一）教学目标1.掌握代数模型的基本概念和性质，尤其是群代数；2.能够对群代数的相关问题进行证明。（二）重

12、点、难点重点：代数系统的概念，群和格；难点：同态与同构、同余、格与布尔代数。（三）教学方法代数结构的教学展示了数学抽象的学科方法，讲授时以“群代数”为核心，讲透代数模型的基本概念、性质和应用背景，其他的代数模型可以触类旁通。（四）教学内容1. 代数系统（3学时）（1）代数系统的构成（2）同态、同构、同余2.群与环（8-9学时）（1）群的定义与性质（2）子群与群的陪集分解（3）循环群与置换群（4）环与域3.格与布尔代数的基本概念（3-4学时）（1）格的定义与性质（2）分配格、有补格与布尔代数（五）作业及要求本单元的习题难度比较大，应注意习题难易程度的递进和合理搭配，并选择典型习题进行讲解。第八章

13、 初等数论（4学时）（一）教学目标1.掌握本单元的基本概念及相应定理。（二）重点、难点重点：整除，最大公约数与最小公倍数，同余；难点：同余，欧拉定理与费马小定理。（三）教学方法以讲授基本概念为主，并结合代数系统引入同余概念和运算，适当介绍其在信息安全密码学中的应用。（四）教学内容1.初等数论（4学时）（1）整除与素数（2）最大公约数与最小公倍数（3）同余与一次同余式（4）欧拉定理与费马小定理（五）作业及要求选择适当数量的计算题。四、考核形式及成绩评定（一）考核形式 闭卷笔试。（二）成绩评定课程考核由平时成绩（作业、小测验等）和期末考试成绩两部分综合评定，分别占课程总成绩的30%和70%。（三）

14、考题设计考试内容大体由4部分组成：（1）考查基础知识、基本概念掌握情况的选择题和填空题，大致占考试内容总量的20%；（2）考查数学建模能力和问题求解能力的分析或计算题，大致占考试内容总量的40%；（3）考查逻辑思维能力、逻辑推理能力的证明题，大致占考试内容总量的20%；（4）考查综合应用能力的试题，大致占考试内容总量的20%。五、教材与参考书教 材：屈婉玲,耿素云,张立昂.离散数学.北京:高等教育出版社,2008年3月参考书：1 左孝凌.离散数学.上海：上海交通大学出版社,1982年02月2 王元元,桂芸.离散数学导论.北京：科学出版社,2002年02月3 徐洁磐.离散数学导论.（第3版）.北京：高等教育出版社,2004年06月4 美D.S.Malik著，邱仲潘译.离散数学结构.（第1版）.北京：高等教育出版社,2005年11月5 美 Kenneth H,Rosen著,袁崇义,屈婉玲等译.离散数学