《离散数学》课程教学大纲
课程代码： 课程负责人：陈远 课程中文名称：离散数学
课程英文名称：Discrete Mathematics 课程类别：选修 课程学分数：3 课程学时数：54
授课对象：信息管理与信息系统、电子商务本科生
本课程的前导课程：计算机原理、信息管理概论、电子商务概论
一、教学目的和要求
《离散数学》是信息管理与信息系统、电子商务专业本科生的专业基础课程。离散数学是研究离散量的结构及相互关系的学科，它综合了计算机科学中所用到的各数学分支，为计算机科学及相关学科提供了有力的理论基础和工具，其应用在信息管理与开发领域相当广泛。通过学习本课程，培养了学生的逻辑推理、抽象思维和形式化思维能力，为学习各专业课程，如数据结构、程序设计、操作系统、数据库原理、计算机网络、信息组织、信息检索、项目管理、决策支持系统等课程，作了必要的数学准备，是将信息由人工处理转为计算机自动化处理的“桥梁”，从而提高学生的理论素质以及独立学习与工作的能力。
《离散数学》是应用数学课，因此教学方式主要还是定理证明、例题讲解以及学生课后的习题练习。本专业的《离散数学》是给其他专业课打基础、作知识预备的，教学重点在于应用，所以教学中选用的例题与习题多是与实际问题结合的，并要引导学生将专业课中涉及的内容用离散数学的方法来解决，强调的是加深理解、加强联系，学以致用。在每章学完后会采用讲习题课、讨论答疑、批改作业等多种手段来检查学生学习效果，部分习题解答要求学生编程序实现。
二、课程的内容与学时分配
根据本专业知识的需求及课程设置和学时的安排，《离散数学》从实用角度出发，结合后续课程的应用主要讲授三大部分的内容，即数理逻辑、集合论、图论。
课程的内容与学时分配表 内 容 命题逻辑 一阶逻辑/谓词逻辑 集合的基本概念和运算 二元关系和函数 图的基本概念 一些特殊的图 树
·1·
学 时 10 8 4 10 8 8 6 第一章 命题逻辑
第一节 命题符号化及联结词 第二节 命题公式及分类 第三节 等值演算 第四节 联接词全功能集 第五节 对偶与范式 第六节 推理理论 第七节 题例分析
内容：自然语言命题的符号化，命题公式的判定，主析取/合取范式，推理理论。 重点讲授：逻辑问题符号化成命题公式，等值公式和推理定律，命题演算与推导。 第二章 一阶逻辑/谓词逻辑
第一节 一阶逻辑基本概念 第二节 一阶逻辑合式公式及解释 第三节 一阶逻辑等值式 第四节 一阶逻辑推理理论 第五节 题例分析
内容：个体、谓词、量词的定义，一阶逻辑公式的判定，量词转化及辖域的扩缩，前束范式，一
阶逻辑推理。
重点讲授：一阶逻辑命题的符号化，一阶逻辑公式性质的判定，一阶逻辑推理理论，命题逻辑推
理。
第三章 集合的基本概念和运算
第一节 集合的基本概念 第二节 集合的基本运算 第三节 集合中元素的计数 第四节 题例分析
内容：幂集、笛卡尔积，集合运算基本定律，包含排斥原理。
重点讲授：集合的包含、相等证明，集合元素的计数，包含排斥原理的运用。 第四章 二元关系和函数
第一节 集合的笛卡儿积与二元关系 第二节 关系的运算 第三节 关系的性质 第四节 关系的闭包 第五节 等价关系和偏序关系 第六节 函数的定义和性质 第七节 函数的复合和反函数 第八节 题例分析
内容：关系的性质，关系的基本运算，关系的闭包，复合运算和逆运算，等价关系和偏序关系，
函数的性质，函数的复合，反函数。
重点讲授：关系的闭包与复合运算，等价关系和偏序关系的证明与应用，函数性质的判断，函数
·2·
的复合。
第五章 图的基本概念
第一节 无向图及有向图 第二节 通路、回路、图的连通性 第三节 图的矩阵表示 第四节 最短路径及关键路径 第五节 题例分析
内容：图的基本概念，图的连通性，图的矩阵表示，最短路径和关键路径。
重点讲授：完全图、子图的定义，图的连通性的判别，图的矩阵表示及其用途，用标号法求最短
路径，用PERT图求关键路径。
第六章 一些特殊的图
第一节 二部图 第二节 欧拉图 第三节 哈密尔顿图 第四节 平面图 第五节 题例分析
内容：匹配问题，欧拉通路判别法，哈密尔顿通路判别法，平面图，欧拉公式。
重点讲授：特殊图的判别与生成的方法，工种分配、一笔画问题、货郎担问题、着色问题的运用。 第七章 树
第一节 无向树及生成树 第二节 根树性质及其应用 第三节 题例分析
内容：无向树及生成树，最小生成树，根树性质，正则树，最优二元树求法，根树的行遍方法。 重点讲授：用避圈法求最小生成树，用哈夫曼算法求最优二元树，用中序、前序、后序行遍法遍
历根树。
三、教材与参考书
教材：离散数学（第三版），清华大学出版社，耿素云，屈婉玲，张立昂，2004 参考书：[1] 离散数学导论，清华大学出版社，马振华，2000
[2] Discrete Mathematics. 电子工业出版社，Richard Johnsonbaugh. 王孝喜等译，1999
四、作业和考核方式
每章后面的习题要求全做，考核采取课堂练习、单元小测验、闭卷等多种方式，成绩按比例综合评定。
·3·