离散数学教学大纲
- 格式：pdf
- 大小：142.25 KB
- 文档页数：4
离 散 数 学
Discrete Mathematics
课程代码：213103
课程类别：专业基础课
适用专业：计算机科学与技术专业
学时数：（理论学时：72 实验学时： ） 学分数：4
要求先修课程：组合数学，高等数学，计算机程序设计，C 语言
执笔人：叶绿
一、课程性质与地位
《离散数学》是计算机科学与技术专业的一门主要技术基础课程，是必修课，也可作为
电子信息工程专业、自动化专业等相近专业的选修课程。离散数学是计算机科学中基础理论
的核心课程，与数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊
断、机器定理证明等课程联系紧密。该课程的教学任务是使学生掌握由一个或几个判断提出
另一判断的思维形式， 运用集合运算以及图论的基本知识作为工具培养和增强学生的开发创
新能力，独立思维能力， 为今后的学习有关的后续课程和掌握专业知识及新的科学技术打下
一定的基础。
二、课程教学目标
每章每节应配置适当数量的习题，大约共 250 题左右。课外习题应密切结合讲授内容，
保证重点，掌握和主要设计计算方法的训练，题目应由易到难，由简到繁，目的明确，选择
适当。习题类型应多种类型，对学习成绩较好的学生，可补充一些较难的习题，或选择题、
思考题等。习题课的目的在于帮助学生消化和巩固本课程中重要和较繁重的内容，引导学生
分析总结和讨论解题的方法和步骤，指导学生查阅技术资料等。
（1） ．习题课要求
本课程习题讨论课的主要目的在于帮助学生消化和巩固所学的理论知识， 提高学生运用
所学知识独立分析和解决本课各部分实际问题的能力并主要讨论以下几个大题：
1． 掌握命题逻辑的范式、推理理论，将学过的命题逻辑知识应用于日常生活和工程技
术中，尤其在电路设计中应用。
a) 设计一台自动售货机的组合电路（逻辑门电路）的设计图；
b) 设计一个控制盥洗室照明的逻辑门电路图；
c) 设计一个二进制半加器的逻辑门电路图；
d) 设计红绿灯自动控制线路的逻辑门电路图。
2． 掌握谓词逻辑的推理理论，将学过的谓词演算的推理规则（全称指定规则 US、全称
推广规则 UG、存在指定规则 ES、存在推广规则 EG）。
3． 掌握集合原理，将学过的集合知识、包含排斥原理应用于日常生活和工程技术中，
尤其是在有限个元素的计数问题。
4． 掌握关系原理，及集合自反闭包、对称闭包、传递闭包远算。
a) 用 C 或 C++编程语言实现 Warshall在 1962年提出的 R + 的算法。
5． 掌握群的原理，将学过的交换群、置换群和等价类的概念，应用于实际问题。
（2）对学生能力培养的要求
掌握离散数学结构的概念、术语、算法、实现方法。熟悉各种基本离散数据结构的理
论及其算法，初步具有算法分析能力。
三、课程内容、基本要求及学时分配
《离散数学》课程总学时为 68，其中讲课 50 学时，实验 10 学时。
课程内容、基本要求如下：
1. 数理逻辑
(1) 命题逻辑：
理解命题及其表示法、掌握联结词的运用、掌握命题公式与翻译、真值表与等价公
式的方法、了解重言式与蕴含式、其他联结词的概念、熟练掌握对偶与范式、推理理论
的方法、掌握在电路逻辑设计、门电路汇总等方面的应用的解题手段
(2) 谓词逻辑：
理解谓词的概念与表示、掌握命题函数与量词的概述、了解谓词公式与翻译、变元
的约束、谓词演算的等价式与蕴含式、前束范式的概念、掌握谓词演算的推理方法
2. 集合论
理解并掌握集合概述和表示法、 集合的运算方法、 掌握包含排斥原理以及它的应用、
了解序偶与笛卡尔积、关系及其表示、关系的性质和概念、掌握集合的划分和覆盖、等
价关系与等价类的方法和分析手段以及它们的应用问题
3．群论
理解并掌握广群、半群、幺半群、独异点、群、循环群、交换群、置换群的基本概
念，以及幺半群、独异点、群、循环群、交换群的推证的方法。
4. 图论
(1) 图：
理解图的基本概念、路与回路、欧拉图汉密尔顿图、平面图的不同解决方法及其
它的应用、掌握对偶图与着色的方法以及应用、了解图的矩阵表示法和如何程序化
(2) 树：
理解并掌握根树及其应用、掌握树与生成树的解决方法。
5. 计算机科学中的应用
(1) 形式语言与自动机：
了解串和语言、形式文法、有限状态自动机、两类自动机的转换、有限状态机的
简化、有限状态机与正则语言的概念。
(2) 纠错码初步：
了解通讯模型和纠错的基本概念、线性分组码的纠错能力、海明码及查表译码法
的方法。
学时分配如下：
章节 标题 内容要点 重点、难 点 学时
1 数理逻辑概论 数理逻辑基础及其表示法 2
2 命题逻辑 联结词、命题公式与翻译、真值表与等 逻辑推证 8
价公式、 重言式与蕴含式、 对偶与范式、
推理理论、门电路逻辑设计
3 谓词逻辑 函数与量词、谓词公式与翻译、变元的 约束、谓词演算的等价式与蕴含式、前 束范式、谓词演算的推理 谓词公式 6
4 集合论 集合的运算、包含排斥原理以及应用、 序偶与笛卡尔积、关系及其表示、关系 的性质、集合的划分和覆盖、等价关系 与等价类、相蓉关系、序关系 等价关系 12
5 群论 广群、半群、幺半群、独异点、群、循 环群、交换群、置换群 群的推证 10
6 图论 路与回路、 欧拉图汉密尔顿图、 平面图、 对偶图与着色、最小生成图 平面图 15
7 树与根树的应用 根树及其应用、树与生成树、二叉树的 应用、Huffman 树、前缀码 二叉树的 应用 10
8 计算机科学中的 应用 串和语言、形式文法 形式文法 1
9 形式语言与自动 机 有限状态自动机、两类自动机的转换、 有限状态机的简化、有限状态机与正则 语言 图灵机 2
10 纠错码初步 通讯模型和纠错的基本概念、线性分组 码的纠错能力、海明码及查表译码法 海明码 2
合计 68
四、教学环节安排与考核方法
本课程主要是理论教学，周学时为 4，课程的课内外学时比为 1:1.5。
考核方法为闭卷笔试考试。
课外实际应用方面、能力培养方面的要求如下：
1. 能应用于日常生活和工程技术中，特别是在电路设计中应用更广。掌握组合电路逻
辑设计，与命题逻辑联结词相对应的门电路汇总算，用 C 语言、PASCAL语言编写电
路逻辑设计图的模拟程序。
2. 掌握谓词演算的推理理论，能对命题符号化并推证其结论。
3. 熟练掌握集合运算、性质、序偶、关系，能运用包含排斥原理解决具体的应用性问
题。掌握集合关系，如等价关系，划分的具体应用。
4. 熟练掌握路与回路，欧拉图与汉密尔顿图、平面图，了解它的具体应用，掌握对偶
图与着色的具体方法，以及应用。了解游戏难题，迷宫问题，匿门博奕问题，棋盘
上马的行走路线问题， 四色猜想， 环游世界问题的基本解决方法， 用C 语言、 PASCAL
语言编写实现程序。
5. 熟练掌握树的一些基本性质和应用，掌握最优树和前缀码的基本方法，用 C 语言、
PASCAL 语言编写路由算法的实现程序。
6. 了解离散数学在计算机科学中的应用，特别形式语言与自动机，编码这两专题。
五、建议使用教材与教学参考书
1.《离散数学》，左孝凌、李为监、刘永才编著，上海科技出版社，1987年。
2．《离散数学题集》，左孝凌等编著，上海科技出版社，1999 年。
3．《Discrete Mathematical Structures》，Bernard Kolman,Robert C.Busby, Sharon
Ross, PRENTICE-HALL International,Inc.,1997 年。
4．《离散数学》，耿素云等编著，清华大学出版社，1999 年。
