离散数学教学大纲.doc

离散数学教学大纲课程名称：离散数学课程编码：适用专业及层次：计算机专业课程总学时：48课程总学分：3理论学时：48实践学时：0先修课程：一、课程的性质、目的与任务该课程是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学课程主要介绍数理逻辑、朴素集合论、二元关系、函数以及图的相关知识。教学过程中应注重理论、方法和实例的结合，努力使学生对于离散数学课程逐渐形成较为完整的知识体系，对于一些概念、性质、方法有更深刻的理解，不仅为学生的专业课学习及将来从事的软件开发打下坚实的基础，同时也能培养他们抽象思维和严格逻辑推理的能力。二、教学内容、教学要求及教学重难点（一）理论课时教学内容、教学要求及教学重难点第一章 数理逻辑第一节 命题逻辑的基本概念【教学内容】命题与联结词、命题公式及其赋值。【教学要求】深刻理解5种常用联结词的涵义，并能准确运用他们将命题符号化；深刻理解命题公式的赋值。【教学重难点】蕴含联结词与析取联结词；真值表。第二节 命题逻辑的等值演算【教学内容】等值式、析取范式与合取范式、联结词的完备集【教学要求】深刻理解等值式的定义；熟练应用基本等值式及置换规则进行等值演算；深刻理解极小项、极大项的定义，名称、下角标与成真赋值的关系，会求主析取范式与主合取范式；会将任何命题公式等值转化成某联结词完备集中的公式。【教学重难点】等值式的定义；极大项与极小项。第三节 命题逻辑的推理理论【教学内容】推理的形式结构、自然推理系统。【教学要求】熟练掌握判断推理是否正确的不同方法，如真值表法、等值演算法、主析取范式法等；牢记自然推理系统中的各条推理规则的内容和名称；熟练掌握在自然推理系统中的常用证明方法。【教学重难点】推理的形式结构；推理规则。第四节 一阶逻辑基本概念【教学内容】一阶逻辑命题符号化；一阶逻辑公式及其解释。【教学要求】掌握一阶逻辑的命题符号化；理解谓词公式与解释。【教学重难点】个体、谓词、量词；谓词公式及其解释。第二章 集合论【教学内容】集合的基本概念；集合的运算；有穷集的计数；集合恒等式。【教学要求】熟练掌握集合的两种表示法；能够判别两个集合之间是否存在包含、相等、真包含等关系；熟练掌握集合的基本运算；掌握有穷集合的计数方法；掌握证明集合等式或者包含关系的基本方法。【教学重难点】集合的基本概念和运算；集合元素中的计数问题。第三章 二元关系【教学内容】二重组与笛卡尔积；二元关系；关系的运算；关系的性质；关系的闭包；等价关系与划分；偏序关系。【教学要求】理解二重组、二元关系、集合A到B的关系、集合A上的关系（包含空关系、全关系、小于等于关系、整除关系、包含关系）的定义；掌握笛卡尔积的运算和性质；熟练掌握关系表达式、关系矩阵、关系图的表示法；熟练掌握关系的定义域、值域、逆、复合、幂的计算方法；熟练计算集合A上关系R的自反闭包、对称闭包和传递闭包；熟练掌握判断关系五种性质的方法，并能对关系的自反、对称、反对称、传递性给出证明；熟练掌握等价关系、等价类、商集、划分的概念，以及等价关系与划分的对应性质；熟练掌握偏序关系、偏序集、哈斯图等概念。【教学重难点】二元关系的运算；关系的闭包；等价关系与划分；偏序关系。第四章 函数【教学内容】函数的定义与性质；函数的复合与反函数；双射函数与集合的基数。【教学要求】掌握函数的基本概念；会判断和证明函数的单射、满射、双射的性质；给定集合A和B，会构造从A到B的双射函数；会计算复合函数、双射函数的反函数。【教学重难点】函数的复合与反函数；双射函数与集合的基数。第五章 图论第一节 图的基本概念【教学内容】图；通路与回路；图的连通性；图的矩阵表示；图的运算。【教学要求】了解无向图与有向图的定义、顶点的度数等概念；理解零图、平凡图、简单图、完全图、正则图、子图、补图、图的同构等概念；熟练掌握握手定理及应用；理解通路与回路、简单通路、简单回路、初级通路、初级回路、无向图顶点间的连通、有向图顶点间的可达等概念；理解无向连通图、连通分图等概念；深刻理解n阶有向图的邻接矩阵和可达矩阵的定义，熟练掌握通过邻接矩阵求顶点间长度为k的通路数、回路数以及图中长度为k的通路和回路数的方法。【教学重难点】图的基本概念；通路、回路和图的连通性；图的矩阵表示。第二节 欧拉图与哈密尔顿图【教学内容】欧拉图；哈密尔顿图；最短路径与货郎担问题。【教学要求】理解欧拉通路、回路和欧拉图的概念，熟练掌握判别欧拉图的方法；理解哈密尔顿通路、回路和哈密尔顿图的概念，会判断某些图是或不是哈密尔顿图。【教学重难点】欧拉图的概念、性质及判断方法；哈密尔顿图的判别。三、教学章节及学时分配（一）总体学时分配序号教学章节总学时其 中备注理论学时实践（验）学时11-14421-26631-36641-44452446388744485-16695-266四、教学方法与教学手段说明整个课程主要采用讲授法，尽量多结合例子来讲解。必要的算法可以借助编程实现来强化学生的掌握。需要给学生布置适量的课后作业。五、考核方式考核类型：考试。考核形式：闭卷。卷面成绩占总成绩的比重不应低于60%，其他部分成绩由课后作业和平时考勤成绩组成。六、使用说明讲课内容顺序可以适当改变，比如数理逻辑可以放在集合论、二元关系和函数之后介绍。七、主要参考资料方世昌.离散数学【M】.西安：西安电子科技大学出版社