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

1、离散数学I课程教学大纲一、课程基本信息课程代码：12130118课程英文名称：Discrete Mathematics课程面向专业：信息与计算科学专业课程类型：必修课 先修课程：高等代数 学分：4 总学时：64 (其中理论学时：64 实验学时：0 ) 二、课程性质与目的本课程是现代数学的重要分支，是计算科学的理论基础，对于培养学生的逻辑思维和抽象思维以及分析问题解决问题的能力有重要作用。通过本课程的学习，使学生初步掌握离散数学的基本理论和方法，了解离散数学与计算科学中的数据结构与算法分析、可计算性与计算复杂性、程序设计语言、人工智能与机器人、网络、计算机图形学、操作系统、编译理论以及人机通讯等

2、课程的紧密联系，为学好这些课程打好基础。三、课程教学内容与要求第一部分：数理逻辑1、教学内容与要求（1）命题逻辑的基本概念与方法：熟练掌握命题与联结词的表示法和运算关系；掌握命题公式的翻译与真值表；掌握基本的等值式，会用等值演算法验证等值式；掌握析取范式与合取范式相关概念，会求命题公式的主析取范式与主合取范式；掌握推理的形式结构，掌握自然推理系统。（2）一阶逻辑的基本概念与方法：掌握一阶逻辑命题的符号化方法；了解一阶逻辑公式及其解释方法；掌握逻辑等值式及其置换规则；了解一阶逻辑的前束范式；掌握一阶逻辑的推理理论。2、教学重点命题与联结词的表示法和运算关系，命题公式的翻译与真值表，基本的等值式，

3、求命题公式的主析取范式与合取范式，推理的形式结构；3、教学难点逻辑等值式及其置换规则，一阶逻辑的推理理论。第二部分：集合论1、教学内容与要求（1）集合代数：熟练掌握集合的基本概念、运算；熟练掌握集合的恒等式；了解关系、关系的运算；熟练掌握关系的性质；熟练掌握等价关系与偏序关系；了解集合的基数。（2）函数论：了解函数的定义与性质；了解复合函数与反函数。2、教学重点：集合的恒等式，关系的性质3、教学难点：等价关系与偏序关系第三部分：代数结构1、教学内容与要求（1）代数系统：了解代数系统的概念，熟练掌握二元运算及其基本性质；了解半群与独异点；熟练掌握群的定义与性质；掌握子群的概念与性质；掌握陪集与拉

4、格朗日定理；掌握正规子群与商群；熟练掌握群的同构与同态；熟练掌握循环群，了解置换群；了解环与域的基本概念与性质，了解格与布尔代数。2、教学重点群的定义与性质，子群的概念与性质，陪集与拉格朗日定理3、教学难点 正规子群与商群，群的同构与同态，循环群第四部分：图论1、教学内容与要求（1）图的基本概念：熟练掌握图的基本概念；熟悉通路与回路及二部图；掌握图的矩阵表示；了解欧拉图与哈密顿图。（2）树：掌握无向树的基本概念及其性质；掌握生成树；熟练掌握根树及其运用。（3）平面图及其着色：掌握平面图的概念；熟练掌握欧拉公式，了解平面图的对偶图；了解平面图的判断方法；了解图的着色（4）支配集、覆盖集、独立集与

5、匹配：了解支配集、覆盖集、独立集的基本概念；了解图的匹配2、教学重点：图的基本概念，通路与回路及二部图，图的矩阵表示3、教学难点：无向树的基本概念及其性质，平面图的概念，欧拉公式四、学时分配学时分配表序号教 学 内 容学时课堂讲授实验课习题课讨论课其它1第一部分：分数理逻辑1422第二部分：集合论83第三部分：代数结构2224第四部分；图论142小计586比例91%9%合计64五、教学环节与教学要求如果本校计算机系使用本教学大纲，由于学时数安排比较少，可以适当采取“少而精”的原则将部分内容选讲。在具体讲授时，部分算法可以要求学生编写出具体的计算程序。六、课程考核办法闭卷考试七、教材与主要参考书1、离散数学（第2版）耿素云高等教育出版社2004 2、离散数学习题集数理逻辑与集合论分册耿素云北京大学出版社19933、离散数学习题集图论分册耿素云北京大学出版社1