《离散数学》教学大纲

1、离散数学教学大纲课程名称：离散数学离散数学离散数学课程编号：408008420008436008适用专业：计算机科学与技术网络工程软件工程课程类别：专业必修课专业必修课专业必修课课程学分：333总学时：545454其中：理论学时545454实验学时000先修课程：高等数学、线性代数一、课程的性质、目的与任务离散数学是现代数学的一个重要分支。离散数学用数学语言来描述离散系统的状态、关系和变化过程，是计算机科学与技术的形式化描述语言，也是进行数量分析和逻辑推理的工具。离散数学为计算机科学和技术的发展奠定了重要的数学基础，其基本思想、概念和方法广泛渗透到计算机科学和技术的各个领域。离散数学是计算机科

2、学及相关学科的一门非常重要的专业基础课。教学的目的是进一步提高学生的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础,并为后续课程的学习打下良好的基础。通过本课程的学习，要求学生：1.理解命题逻辑、一阶逻辑、关系、图所包含的基本概念2.理解研究对象所具有的性质和相互关系3.掌握各种典型的论证推理方法4.在抽象思维和逻辑推理能力上有较好提高二、课程基本内容与要求第一章命题逻辑（一）教学内容：1.1命题与联结词1.2命题公式与赋值1.3等值演算1.4析取范式与合取范式1.5命题逻辑的推理理论（二）教学要求：教学目的：了解命题和五种联结词的概念，熟练掌握用五重联结词将复合命题符

3、号化的方法；理解合式公式，成真和成假赋值以及公式的类型等概念，熟练掌握求真值表和判定公式类型的方法；了解等值式的概念，掌握置换定理的简单应用，熟记24个重要等值式并熟练掌握它们的应用；熟练掌握求主析取范式和主合取范式的方法及主范式的应用；了解推理、前提、有效结论、证明的概念，理解推理的形式结熟练掌握；掌握判断推理是否正确的方法，熟练掌握用已知的推理规则构造证明的方法。教学重点：命题公式与赋值，等值演算，析取与合取范式，命题逻辑的推理理论。教学难点：主析取与主合取范式的应用，用已知的推理规则构造证明的方法。第二章 一阶逻辑（一）教学内容：2.1一阶逻辑的基本概念2.2一阶逻辑公式及解释2.3一阶

4、逻辑等值式与前束范式2.4一阶逻辑推理理论。（二）教学要求：教学目的：了解个体词、谓词、量词的概念。理解指定个体域与全总个体域的概念；掌握命题在全总个体域或指定个体域的符号化形式；了解合式公式、辖域、自由与约束出现、闭式与代换实例等概念，掌握换名规则、代换规则的应用；理解解释的组成及公式类型，掌握在给定解释下判断公式真值的方法；熟练掌握求已知公式的前束范式的方法；熟练掌握在一阶逻辑中构造推理证明的方法。教学重点：一阶逻辑公式及解释，一阶逻辑等值式与前束范式，一阶逻辑推理理论。教学难点：一阶逻辑公式解释，一阶逻辑前束范式，一阶逻辑推理理论。第三章集合的基本概念和运算（一）教学内容：3.1集合的基

5、本概念3.2集合的基本运算3.3集合恒等式3.4有穷集合的计数。（二）教学要求：教学目的：理解元素与集合的隶属关系、集合之间的包含、相等、不等、真包含关系，掌握集合的表示方法；熟练掌握集合的基本运算；掌握证明简单的集合恒等式或包含关系的方法；掌握有穷集合的计数问题。教学重点：集合的基本概念和运算，集合元素中的计数问题。教学难点：幂集、有穷集合的计数。第4章二元关系和函数（一）教学内容：4.1集合的笛卡尔积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系与偏序关系4.6函数的定义和性质4.7函数的复合和反函数。（二）教学要求：教学目的：了解有序对、二元关系、集合A到B的关

6、系、集合A上的关系的定义，掌握笛卡儿积的运算和性质；熟练掌握关系表达式、关系矩阵、关系图的表示法；掌握关系的定义域只值域、逆、复合、幂的计算方法；理解自反、对称、传递闭包的概念并能求出给定集合上关系的闭包；深刻理解等价关系、等价类、商集、划分、偏序关系、偏序集、哈斯图、偏序集中的特定元素概念，并能熟练求出等价关系的等价类、商集、偏序关系的哈斯图及特定元素；理解函数、集合到的函数、函数的像的概念，、熟练掌握判断函数单射、满射、双射的方法。会构造双射函数。会求复合函数和双射函数的反函数。教学重点：二元关系的运算，关系的闭包、等价关系与偏序关系，函数的复合和反函数。教学难点：等价关系与偏序关系第七章

7、图的基本概念（一）教学内容：7.1无向图及有向图7.2通路、回路和图的连图性7.3图的矩阵表示。（二）教学要求：教学目的：了解无向图与有向图的定义、顶点的度数等概念；理解零图、平凡图、简单图、完全图、正则图、子图、补图、图的同构等概念；熟练掌握握手定理及应用；理解通路与回路、简单通路、简单回路、初级通路、初级回路（圈）、无向图顶点间的连通、有向图顶点间的可达等概念；理解无向连通图、连通分支、点割集、割点、边割集、桥等概念；掌握求短程线与距离的方法。熟练掌握判断通路与回路类型的方法；深刻理解n阶有向图的邻接矩阵和可达矩阵的定义，熟练掌握通过邻接矩阵求顶点间长度为k的通路数、回路数以及图中长度为k

8、的通路和回路数的方法。教学重点：图的基本概念，通路、回路和图的连通性，图的矩阵表示。教学难点：图的同构，点连通度、边连通度，邻接矩阵的应用。第八章树（一）教学内容：8.1无向树8.2根树与应用。（二）教学要求：教学目的：了解无向树、分支点、有向树、根树、根子树等概念；掌握求对应于生成树的基本回路和基本割集的方法；熟练掌握利用无向树的性质及握手定理求顶点度数的方法；熟练掌握用闭圈法求最小生成树的方法；熟练掌握用算法求最优树、最佳前缀码的方法。教学重点：无向树、根树及其应用。教学难点：求最优树、最佳前缀码的方法。第九章 二部图、欧拉图、哈密顿图（一）教学内容：9.1二部图9.2欧拉图9.3哈密顿图

9、（二）教学要求：教学目的：理解二部图的判别定理，会用二部图描叙某些实际问题；理解欧拉通路、回路和欧拉图的概念，熟练掌握判定欧拉图的方法；理解哈密顿通路、回路和哈密顿图的概念，会判断某些图是或不是哈密顿图。教学重点：二部图，二部图中的匹配，欧拉图，哈密顿图。教学难点：二部图中的匹配，寻找哈密顿通路三、课程各章节学时分配序号内容理论学时计科网工软工1命题逻辑1212122一阶逻辑8883集合的基本概念和运算2224二元关系和函数1414145图的基本概念8886树4447二部图、欧拉图、哈密顿图666合计545454四、本课程课外学习与修学指导由于该课程概念多且较为抽象，内容多且较为零散，所以要学好本课程，要求学生多参阅相关书籍，做好预习，多做练习，掌握离散数学的基本慨念、基本理论和基本方法。五、本课程成绩的考查方法及评定标准考核方式：闭卷考试成绩评定标准：本课程的考核是平时成绩和期终考试成绩相结合，平时成绩的评定包括作业、出勤两部分，平时成绩占课程考核成绩的30%，期末考试成绩占课程考核成绩的70%。其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：判断题、选择题、填空题、简答题、计算题、证明