《离散数学及其应用》课程教学大纲 一、课程基本信息 课程代码：109533 课程名称：离散数学及其应用 英文名称：Discrete Mathematics and its Applications 课程类别：学科基础课 时： 48 学 分： 3 适用对象： 考核方式：考试 先修课程 二、课程简介 本课程是现代数学的一个重要分支，是计算机科学基础理论的核心课程，它所研究的对象是 离散的数量关系和离散结构的数学模型，为培养我国社会主义现代化建设所需要的计算机专业技 术人才服务。 "Discrete Mathematics"is an important branch of modern mathematics and a core course of computer science basic theory.In this course discrete volume relations and discrete mathematical model are researched and this course is to be training the computer professional technology persons for the socialist modernization construction of our country. 三、课程性质与教学目的 离散数学是计算机学科的重要专业基础课程。该果程结合计算机学科的特点，主 要研究离散量结构及相互关系，它是计算机各专业课程的基础，对提高学生抽象思维 与逻辑推理能力有重要作用。 掌握集合论、数理逻辑和图论等离散数学基本内容，为学习计算机专业各后续课 程做好必要的知识准备。使学生得到良好的数学训练，提高学生抽象思维和逻辑推理 能力，为从事计算机的应用提供理论基础。 四、教学内容及要求 第一章命题逻辑的基本概念 (一)目的与要求 1.理解命题和逻辑联结词的基本概念 1
1 《 离散数学及其应用 》课程教学大纲 一、课程基本信息 课程代码：109533 课程名称：离散数学及其应用 英文名称：Discrete Mathematics and its Applications 课程类别： 学科基础课 学 时： 48 学 分： 3 适用对象: 考核方式：考试 先修课程： 二、课程简介 本课程是现代数学的一个重要分支，是计算机科学基础理论的核心课程，它所研究的对象是 离散的数量关系和离散结构的数学模型，为培养我国社会主义现代化建设所需要的计算机专业技 术人才服务。 “Discrete Mathematics” is an important branch of modern mathematics and a core course of computer science basic theory. In this course discrete volume relations and discrete mathematical model are researched and this course is to be training the computer professional technology persons for the socialist modernization construction of our country. 三、课程性质与教学目的 离散数学是计算机学科的重要专业基础课程。该课程结合计算机学科的特点，主 要研究离散量结构及相互关系，它是计算机各专业课程的基础，对提高学生抽象思维 与逻辑推理能力有重要作用。 掌握集合论、数理逻辑和图论等离散数学基本内容，为学习计算机专业各后续课 程做好必要的知识准备。使学生得到良好的数学训练，提高学生抽象思维和逻辑推理 能力，为从事计算机的应用提供理论基础。 四、教学内容及要求 第一章 命题逻辑的基本概念 （一）目的与要求 1．理解命题和逻辑联结词的基本概念
2.掌握公式分类和真值表构造 (二)教学内容 第一节命题与联结词 1.主要内容 命题：逻辑联结词 2.基本概念和知识点 命题的概念：逻辑联结词。 3.问题与应用（能力要求） 理解命题概念：掌握几种重要的逻辑联结词。 第二节命题公式及其赋值 1.主要内容 命题公式：真值表 2.基本概念和知识点 公式的真值赋值：真值表。 3.问题与应用（能力要求） 理解五个逻辑联结词概念掌握由它们构成的公式及真值表：熟练掌握求给 定公式真值表的方法。 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的 掌握本章的重点和难点。 课程思政融入主要体现：通过具体的命题罗辑的例子，培养学生逻辑思维能力 望一音命颗罗辑连值演算 (一)目的与要求 1.理解命题等值关系式： 2.掌握公式的析取范式和合取范式： 3.了解联结词的完备集。 (二)教学内容 第一节 .主要内容 基本等值式：真值表法和等值演算法：公式等值变换。 2.基本概念和知识点 用直值表法和等值演算法判别公式类型和公式竿值变换 3. 颗与应用（能力要求 记住基本等值式：掌握用真值表法和等值演算法判别公式类型和公式 等值变换的方法。 第二节析取范式和合取范式 1,主要内容 析取范式：合取范式：主析取范式：主合取范式。 2.基本概念和知识点 2
2 2．掌握公式分类和真值表构造 （二）教学内容 第一节 命题与联结词 1．主要内容 命题；逻辑联结词。 2．基本概念和知识点 命题的概念；逻辑联结词。 3．问题与应用（能力要求） 理解命题概念；掌握几种重要的逻辑联结词。 第二节 命题公式及其赋值 1．主要内容 命题公式；真值表。 2．基本概念和知识点 公式的真值赋值；真值表。 3．问题与应用（能力要求） 理解五个逻辑联结词概念；掌握由它们构成的公式及真值表；熟练掌握求给 定公式真值表的方法。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的 掌握本章的重点和难点。 课程思政融入主要体现：通过具体的命题逻辑的例子，培养学生逻辑思维能力。 第二章 命题逻辑等值演算 （一）目的与要求 1．理解命题等值关系式； 2．掌握公式的析取范式和合取范式； 3．了解联结词的完备集。 （二）教学内容 第一节 等值式 1．主要内容 基本等值式；真值表法和等值演算法；公式等值变换。 2．基本概念和知识点 用真值表法和等值演算法判别公式类型和公式等值变换。 3．问题与应用（能力要求） 记住基本等值式；掌握用真值表法和等值演算法判别公式类型和公式 等值变换的方法。 第二节 析取范式和合取范式 1．主要内容 析取范式；合取范式；主析取范式；主合取范式。 2．基本概念和知识点
极小项：极大项：析取范式：合取范式。 3.问题与应用（能力要求） 会用等值演算法求公式的析取范式和合取范式：会列真值表求公式的 主析取范式和主合取范式。 第三节联结词的完备集 1.主要内容 联结词的完备集。 2.基本概念和知识点 真值函数的概念：联结词的完备集概念。 3.问题与应用（能力要求） 解一些常用的联结词的完备集 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过具体的等值演算的例子，培养学生逻辑思维能力。 第三章命题逻辑的推理理论 (一)目的与要求 1.掌握重要的重言蕴涵式 理解推理的形式结构和自然推理系统P (二)教学内容 第一节推理的形式结构 1,主要内容 重言菹函式，推理的形式结构 2.基本概念和知识点 重言蕴涵式 3.问题与应用（能力要求） 掌握重要的重言蕴涵式；理解推理的形式结构。 第二节自然推理系统P 1.主要内容 自然拍 理系统 2.基本概念和知识点 推理的方法：演绎法和附加前提法。 3.问题与应用（能力要求） 要求学生通过所掌握重言蕴涵式构造推理证明：掌握演绎法和附加前 提法 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 3
3 极小项；极大项；析取范式；合取范式。 3．问题与应用（能力要求） 会用等值演算法求公式的析取范式和合取范式；会列真值表求公式的 主析取范式和主合取范式。 第三节 联结词的完备集 1．主要内容 联结词的完备集。 2．基本概念和知识点 真值函数的概念；联结词的完备集概念。 3．问题与应用（能力要求） 了解一些常用的联结词的完备集。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过具体的等值演算的例子，培养学生逻辑思维能力。 第三章 命题逻辑的推理理论 （一）目的与要求 1．掌握重要的重言蕴涵式； 2．理解推理的形式结构和自然推理系统 P 。 （二）教学内容 第一节 推理的形式结构 1．主要内容 重言蕴涵式；推理的形式结构。 2．基本概念和知识点 重言蕴涵式。 3．问题与应用（能力要求） 掌握重要的重言蕴涵式；理解推理的形式结构。 第二节 自然推理系统 P 1．主要内容 自然推理系统 P 。 2．基本概念和知识点 推理的方法：演绎法和附加前提法。 3．问题与应用（能力要求） 要求学生通过所掌握重言蕴涵式构造推理证明；掌握演绎法和附加前 提法。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点
课程思政融入主要体现：通过具体的命趣逻辑推理理论的例子，培养学生逻辑思维能 第四章一阶逻辑基本概念 (一)目的与要求 1.掌握一阶逻辑的命题符号化： 2.理解谓词公式与解释。 (二)教学内 第一节 阶逻辑命题符号化 .主要内容 阶逻辑的基本概念。 2.基本概念和知识点 谓词：量词：个体词。 主案内容公式解有 第二节 阶逻辑 一阶逻辑公式。 2.基本概念和知识点 一阶逻辑公式；自由变元：约束变元：解释。 3.问题与应用（能力要求 要求学生掌握一阶逻辑公式在给定解释下的真值。 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过具体的一阶逻辑的例子，培养学生逻辑思维能力。 第五章一阶逻辑等值演算与推理 )目的与要求 1.掌握 一阶逻辑的等值关系式： 2.理解谓词公式的前束范式： 3.掌握一阶逻辑的推理理论。 (二)教学内容 第一节 一阶逻辑等值式与置换规则 .主要内容 阶逻辑等值式。 2.基本概念和知识点 一阶逻辑等值式：置换规则。 3.问题与应用（能力要求） 4
4 课程思政融入主要体现：通过具体的命题逻辑推理理论的例子，培养学生逻辑思维能 力。 第四章 一阶逻辑基本概念 （一）目的与要求 1．掌握一阶逻辑的命题符号化； 2．理解谓词公式与解释。 （二）教学内容 第一节 一阶逻辑命题符号化 1．主要内容 一阶逻辑的基本概念。 2．基本概念和知识点 谓词；量词；个体词。 3．问题与应用（能力要求） 掌握一阶逻辑命题符号化。 第二节 一阶逻辑公式及解释 1．主要内容 一阶逻辑公式。 2．基本概念和知识点 一阶逻辑公式；自由变元；约束变元；解释。 3．问题与应用（能力要求） 要求学生掌握一阶逻辑公式在给定解释下的真值。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过具体的一阶逻辑的例子，培养学生逻辑思维能力。 第五章 一阶逻辑等值演算与推理 （一）目的与要求 1．掌握一阶逻辑的等值关系式； 2．理解谓词公式的前束范式； 3．掌握一阶逻辑的推理理论。 （二）教学内容 第一节 一阶逻辑等值式与置换规则 1．主要内容 一阶逻辑等值式。 2．基本概念和知识点 一阶逻辑等值式；置换规则。 3．问题与应用（能力要求）
学握 一阶逻辑等值式会判断谓词公式在给定解释下的真值。 第二节一阶逻辑前束范式 1.主要内容 前束范式 2 基本概念和知识点 名规贝 前束范式 3.问题与应用（能力要求》 会用一阶逻辑等值演算法求公式的前束范式。 第三节一阶逻辑的推理理论 1.主要内容 阶逻辑的推理理论 2.基本概念和知识点 阶逻辑的各推理规则：自然推理系统F。 3.问题与应用（能力要求》 堂据一阶罗组推理过程 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过具体的一阶逻辑的等值演算和推理理论例子，培养学生 逻辑思维能力 (第四部分图论) 第十四章图的基本概念 (一)目的与要求 1.理解图的基本概念： 2.理解图的连通性、矩阵表示和运算。 (二)教学内容 第一节图 1. 主要内容 图的基本概念：结点、边、度数、自环和平行边等。 2.基本概念和知识点 有向图：无向图：握手原理：特殊图。 3.问题与应用（能力要求） 理解图的基本概念：掌握图的握手原理。 第二节 通路与回 1,主要内容 诵路与回路 2.基本概念和知识点 通路（简单通路、 初级通路和复杂通路)，回路（简单回路、初级回 5
5 掌握一阶逻辑等值式；会判断谓词公式在给定解释下的真值。 第二节 一阶逻辑前束范式 1．主要内容 前束范式。 2．基本概念和知识点 换名规则；前束范式。 3．问题与应用（能力要求） 会用一阶逻辑等值演算法求公式的前束范式。 第三节 一阶逻辑的推理理论 1．主要内容 一阶逻辑的推理理论。 2．基本概念和知识点 一阶逻辑的各推理规则；自然推理系统 F 。 3．问题与应用（能力要求） 掌握一阶逻辑推理过程。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过具体的一阶逻辑的等值演算和推理理论例子，培养学生 逻辑思维能力。 （第四部分 图论） 第十四章 图的基本概念 （一）目的与要求 1．理解图的基本概念； 2．理解图的连通性、矩阵表示和运算。 （二）教学内容 第一节 图 1．主要内容 图的基本概念：结点、边、度数、自环和平行边等。 2．基本概念和知识点 有向图；无向图；握手原理；特殊图。 3．问题与应用（能力要求） 理解图的基本概念；掌握图的握手原理。 第二节 通路与回路 1．主要内容 通路与回路。 2．基本概念和知识点 通路(简单通路、初级通路和复杂通路)，回路(简单回路、初级回
路和复杂回路) 3.问题与应用（能力要求） 了解有向图和无向图的通路与回路的概念。 第三节 图的连通性 图的连】 性 2.基本概念和知识点 有向图的连通性：无向图的连通分支数。 3.问题与应用（能力要求） 了解有向图的连通性和无向图连通分支数 第四节 图的矩 1. 主要内容 图的矩阵表示」 2.基本概念和知识点 关联矩阵：邻接矩阵 3. 问题与应用 能力要 了解图的矩阵表示方法 第五节图的运算 1,主要内容 图的坛算 2.基本概念和知识点 图的交 差运算 3.问题与应用（能力要求） 了解图的交、并、差运算。 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过图论的具体例子，培养学生实事求是，精 益求精的工匠精神。 第十五章 欧拉图与哈密顿图 (一)目的与要求 1.理解欧拉图的概念： 2.理解哈密顿图的概念 (二)教学内容 第一节欧拉图 1.主要内容 欧拉图 2.基本概念和知识点 欧拉通路与回路：欧拉图 6
6 路和复杂回路) 3．问题与应用（能力要求） 了解有向图和无向图的通路与回路的概念。 第三节 图的连通性 1．主要内容 图的连通性。 2．基本概念和知识点 有向图的连通性；无向图的连通分支数。 3．问题与应用（能力要求） 了解有向图的连通性和无向图连通分支数。 第四节 图的矩阵表示 1．主要内容 图的矩阵表示。 2．基本概念和知识点 关联矩阵；邻接矩阵。 3．问题与应用（能力要求） 了解图的矩阵表示方法。 第五节 图的运算 1．主要内容 图的运算。 2．基本概念和知识点 图的交、并、差运算。 3．问题与应用（能力要求） 了解图的交、并、差运算。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过图论的具体例子，培养学生实事求是，精 益求精的工匠精神。 第十五章 欧拉图与哈密顿图 （一）目的与要求 1．理解欧拉图的概念； 2．理解哈密顿图的概念。 （二）教学内容 第一节 欧拉图 1．主要内容 欧拉图。 2．基本概念和知识点 欧拉通路与回路；欧拉图
3.问题与应用（能力要求， 掌握欧拉图的判别方法。 第二节哈密顿图 1.主要内容 2。基本概念和知识点 哈密顿圈：哈密顿图 3.问题与应用（能力要求） 掌握哈密顿图的判别方法， (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过欧拉图，哈密顿图在现实中例子，培养学 生实事求是，精益求精的工匠精神。 第十六章树 (一)目的与要求 1.了解无向树和生成树的概念与性质： 2.了解根树的概念及其应用。 (一)教学内突 第一节 无向树及其性质 1.主要内容 无向树的概念及其性质 2.基本概念和知识点 无向树：树叶：分支点：森林：平凡树。 3.问题与应用（能力要求 湾二节生成树无同树的概念与任质 1.主要内容 生成树。 2.基本概念和知识点 了解生成树的概念与性质。 第三节根树及其应用 1.主要内容 根树及其应用 2. 本概念 和知识点 根树：树根：子树：有序树：最优二元树：带权二叉树：最优二叉树： 最优二叉树的哈夫曼算法。 7
7 3．问题与应用（能力要求） 掌握欧拉图的判别方法。 第二节 哈密顿图 1．主要内容 哈密顿图。 2．基本概念和知识点 哈密顿圈；哈密顿图。 3．问题与应用（能力要求） 掌握哈密顿图的判别方法。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段 使学生较好的掌握本章的重点和难点。 课程思政融入主要体现：通过欧拉图，哈密顿图在现实中例子，培养学 生实事求是，精益求精的工匠精神。 第十六章 树 （一）目的与要求 1．了解无向树和生成树的概念与性质； 2．了解根树的概念及其应用。 （二）教学内容 第一节 无向树及其性质 1．主要内容 无向树的概念及其性质。 2．基本概念和知识点 无向树；树叶；分支点；森林；平凡树。 3．问题与应用（能力要求） 了解无向树的概念与性质。 第二节 生成树 1．主要内容 生成树。 2．基本概念和知识点 生成树；最小生成树。 3．问题与应用（能力要求） 了解生成树的概念与性质。 第三节 根树及其应用 1．主要内容 根树及其应用。 2．基本概念和知识点 根树；树根；子树；有序树；最优二元树；带权二叉树；最优二叉树； 最优二叉树的哈夫曼算法
3.问题与应用（能力要求） 了解根树及其应用，会用哈夫曼算法求最优二叉树。 (三)教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较 好的掌握本章的重点和难点。 课程思政融入主要体现：通过欧拉图，哈密顿图在现实中例子，培养学生实事 求是，精益求精的工匠精神。 五、各教学环节学时分配 学环节 分 小 教学时数 实验 其他教 案 学环节 计 课程内容 第一章 第二章 第三章 4 第四章 第五章 6 7 第十四章 10 第十五章 第十六章 1 合计 3 8 六、推荐教材和教学参考资源 选用教材： 耿素云，屈婉玲，离散数学（修订版），高等教育出版社，2004年1月。 教学参考资源 1.左孝凌，李为监，刘永才编著，离散数学理论分析题解，上海科学技术文献 8
8 3．问题与应用（能力要求） 了解根树及其应用，会用哈夫曼算法求最优二叉树。 （三）教学方法与手段 本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较 好的掌握本章的重点和难点。 课程思政融入主要体现：通过欧拉图，哈密顿图在现实中例子，培养学生实事 求是，精益求精的工匠精神。 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教 学环节 小 计 第一章 3 3 第二章 6 1 7 第三章 4 4 第四章 4 4 第五章 6 1 7 第十四章 10 10 第十五章 5 5 第十六章 7 1 8 合计 45 3 48 六、推荐教材和教学参考资源 选用教材： 耿素云，屈婉玲，离散数学(修订版)，高等教育出版社，2004 年 1 月。 教学参考资源： 1．左孝凌，李为监，刘永才编著，离散数学理论分析题解，上海科学技术文献
出版社，1986年。 2.刘爱民，离散数学，北京邮电大学出版社，2004年5月。 3.Mathematical Structures(Fourth Edition)Bernard Kolman,Robert C.Busby,Sharon Cutler Ross.Discrete Beijing:Higher Education Press 2001. 七、其他说明 1.修订大纲的指导思想：根据专业特点，使学生掌握必备的离散数学基本理论和 基本方法，为学习后继专业课程、从事科学研究或工程技术打下一定的基础。 2.本课程与先修课程和后续课程的联系与分工：先修课程解决该课程所必须的数 学基础问题：本课程着重研究离散结构和相互关系：后续课程着重处理离散结构信息。 大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人： 吕律 修订日期：2017,9-10 大纲审定人：陈建超 审定日期：2017,9-10
9 出版社，1986 年。 2．刘爱民，离散数学，北京邮电大学出版社，2004 年 5 月。 3．Mathematical Structures(Fourth Edition) Bernard Kolman,Robert C.Busby,Sharon Cutler Ross.Discrete Beijing:Higher Education Press 2001. 七、其他说明 1．修订大纲的指导思想：根据专业特点，使学生掌握必备的离散数学基本理论和 基本方法，为学习后继专业课程、从事科学研究或工程技术打下一定的基础。 2．本课程与先修课程和后续课程的联系与分工：先修课程解决该课程所必须的数 学基础问题；本课程着重研究离散结构和相互关系；后续课程着重处理离散结构信息。 大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人： 吕律 修订日期：2017, 9-10 大纲审定人： 陈建超 审定日期：2017,9-10