离散数学教学大纲.docx
《离散数学教学大纲.docx》由会员分享，可在线阅读，更多相关《离散数学教学大纲.docx（25页珍藏版）》请在冰点文库上搜索。
离散数学教学大纲
《离散数学》教学大纲（54学时）
一、课程基本信息
1、课程代码：
BCim125
2、课程名称：
离散数学
3、英文名称：
DiscreteMathematics
4、课程类型：
专业必修课
5、课程适用层次：
本科
6、课程适用对象：
计算机科学与技术专业
7、总学时：
54周学时：
3
8、学分：
3
二、课程概述：
本课程是现代数学的一个重要分支，是计算机科学基础理论的核心课程，它所研究的对象是离散的数量关系和离散结构的数学模型，为培养我国社会主义现代化建设所需要的计算机专业技术人才服务。
“DiscreteMathematics”isanimportantbranchofmodernmathematicsandacorecourseofcomputersciencebasictheory.Inthiscoursediscretevolumerelationsanddiscretemathematicalmodelareresearchedandthiscourseistobetrainingthecomputerprofessionaltechnologypersonsforthesocialistmodernizationconstructionofourcountry.
三、学时分配计划
三、课程性质与教学目的
离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是计算机科学与技术专业必修的一门专业基础课。
通过本课程的学习，培养学生的抽象思维和严密的逻辑推理能力，为进一步学习专业课打好基础，并为学生今后处理离散信息，提高专业理论水平，从事计算机的实际工作提供必备的数学工具。
教学目的是使学生掌握高级科研人员或高级技术人员必须具备的离散数学基本理论和基本方法，为学习后继专业课程、从事科学研究或工程技术工作打下一定的基础，同时，结合本课程的特点，培养学生辩证唯物论观点和观察、分析、解决问题的能力，特别应着力培养学生的创新能力和实践能力。
四、教学内容及要求
（第一部分数理逻辑）
第一章命题逻辑基本概念
（一）目的与要求
1．理解命题和逻辑联结词的基本概念；
2．掌握公式分类和真值表构造。
（二）教学内容
第一节命题与联结词
1．主要内容
命题；逻辑联结词。
2．基本概念和知识点
命题的概念；逻辑联结词。
3．问题与应用（能力要求）
理解命题概念；掌握几种重要的逻辑联结词。
第二节命题公式及其赋值
1．主要内容
命题公式；真值表。
2．基本概念和知识点
公式的真值赋值；真值表。
3．问题与应用（能力要求）
理解五个逻辑联结词概念；掌握由它们构成的公式及真值表；熟练掌握求给定公式真值表的方法。
（三）课后练习
Page15：
1—6；8—21。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第二章命题逻辑等值演算
（一）目的与要求
1．理解命题等值关系式；
2．掌握公式的析取范式和合取范式；
3．了解联结词的完备集。
（二）教学内容
第一节等值式
1．主要内容
基本等值式；真值表法和等值演算法；公式等值变换。
2．基本概念和知识点
用真值表法和等值演算法判别公式类型和公式等值变换。
3．问题与应用（能力要求）
记住基本等值式；掌握用真值表法和等值演算法判别公式类型和公式等值变换的方法。
第二节析取范式和合取范式
1．主要内容
析取范式；合取范式；主析取范式；主合取范式。
2．基本概念和知识点
极小项；极大项；析取范式；合取范式。
3．问题与应用（能力要求）
会用等值演算法求公式的析取范式和合取范式；会列真值表求公式的主析取范式和主合取范式。
*第三节联结词的完备集
1．主要内容
联结词的完备集。
2．基本概念和知识点
真值函数的概念；联结词的完备集概念。
3．问题与应用（能力要求）
了解一些常用的联结词的完备集。
（三）课后练习
Page39：
1—13；15—20。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第三章命题逻辑的推理理论
（一）目的与要求
1．掌握重要的重言蕴涵式；
2．理解推理的形式结构和自然推理系统
。
（二）教学内容
第一节推理的形式结构
1．主要内容
重言蕴涵式；推理的形式结构。
2．基本概念和知识点
重言蕴涵式。
3．问题与应用（能力要求）
掌握重要的重言蕴涵式；理解推理的形式结构。
第二节自然推理系统
1．主要内容
自然推理系统
。
2．基本概念和知识点
推理的方法：
演绎法和附加前提法。
3．问题与应用（能力要求）
要求学生通过所掌握重言蕴涵式构造推理证明；掌握演绎法和附加前提法。
（三）课后练习
Page54：
6—18。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第四章一阶逻辑基本概念
（一）目的与要求
1．掌握一阶逻辑的命题符号化；
2．理解谓词公式与解释。
（二）教学内容
第一节一阶逻辑命题符号化
1．主要内容
一阶逻辑的基本概念。
2．基本概念和知识点
谓词；量词；个体词。
3．问题与应用（能力要求）
掌握一阶逻辑命题符号化。
第二节一阶逻辑公式及解释
1．主要内容
一阶逻辑公式。
2．基本概念和知识点
一阶逻辑公式；自由变元；约束变元；解释。
3．问题与应用（能力要求）
要求学生掌握一阶逻辑公式在给定解释下的真值。
（三）课后练习
Page69：
2—10。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第五章一阶逻辑等值演算与推理
（一）目的与要求
1．掌握一阶逻辑的等值关系式；
2．理解谓词公式的前束范式；
3．掌握一阶逻辑的推理理论。
（二）教学内容
第一节一阶逻辑等值式与置换规则
1．主要内容
一阶逻辑等值式。
2．基本概念和知识点
一阶逻辑等值式；置换规则。
3．问题与应用（能力要求）
掌握一阶逻辑等值式；会判断谓词公式在给定解释下的真值。
第二节一阶逻辑前束范式
1．主要内容
前束范式。
2．基本概念和知识点
换名规则；前束范式。
3．问题与应用（能力要求）
会用一阶逻辑等值演算法求公式的前束范式。
第三节一阶逻辑的推理理论
1．主要内容
一阶逻辑的推理理论。
2．基本概念和知识点
一阶逻辑的各推理规则；自然推理系统
。
3．问题与应用（能力要求）
掌握一阶逻辑推理过程。
（三）课后练习
Page85：
2—8；12—25。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
（第二部分集合论）
第六章集合代数
（一）目的与要求
1．了解集合的基本概念；
2．理解集合的运算和性质；
3．掌握集合定律、集合恒等式。
（二）教学内容
第一节集合的基本概念
1．主要内容
集合的基本概念。
2．基本概念和知识点
子集；幂集。
3．问题与应用（能力要求）
了解常用的集合；会求子集和幂集。
第二节集合的运算
1．主要内容
集合的运算和性质。
2．基本概念和知识点
交集；并集；差集；文氏图。
3．问题与应用（能力要求）
掌握集合的运算和性质；理解集合的计数问题。
第三节集合恒等式
1．主要内容
集合恒等式。
2．基本概念和知识点
集合恒等式。
3．问题与应用（能力要求）
掌握并会灵活运用集合恒等式。
（三）课后练习
Page103：
2—10；13—19；25—40。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第七章二元关系
（一）目的与要求
1．理解二元关系的概念；
2．掌握二元关系的运算和性质；
3．了解关系的闭包；
4．掌握等价关系和划分；
5．了解偏序关系。
（二）教学内容
第一节有序对与笛卡尔积
1．主要内容
有序对与笛卡尔积。
2．基本概念和知识点
有序对；笛卡尔积。
3．问题与应用（能力要求）
理解两集合的笛卡尔积。
第二节二元关系
1．主要内容
二元关系。
2．基本概念和知识点
二元关系；关系图；关系矩阵。
3．问题与应用（能力要求）
理解二元关系的概念；掌握三种特殊的关系；会求关系矩阵和关系图。
第三节关系的运算
1．主要内容
关系的运算。
2．基本概念和知识点
关系的逆运算；合成运算。
3．问题与应用（能力要求）
掌握关系的逆运算和合成运算。
第四节关系的性质
1．主要内容
关系的性质。
2．基本概念和知识点
关系的自反性；对称性；反对称性；传递性。
3．问题与应用（能力要求）
掌握关系所满足的性质。
*第五节关系的闭包
1．主要内容
关系的闭包。
2．基本概念和知识点
关系的闭包运算。
3．问题与应用（能力要求）
了解关系的闭包运算。
第六节等价关系和划分
1．主要内容
等价关系和划分。
2．基本概念和知识点
等价关系；等价类；划分。
3．问题与应用（能力要求）
掌握等价关系的证明；会求等价类和划分。
第七节偏序关系
1．主要内容
偏序关系。
2．基本概念和知识点
偏序集；偏序关系；哈斯图。
3．问题与应用（能力要求）
了解偏序关系和其对应的哈斯图。
（三）课后练习
Page140：
6—9；12—16；20—36；38—48。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
*第八章函数
（一）目的与要求
1、了解函数和函数合成的基本概念；
2、理解反函数；
3、了解特征函数的性质。
（二）教学内容
第一节函数的定义与性质
1．主要内容
函数的定义与性质。
2．基本概念和知识点
函数（映射）；函数的象与原象；单射；满射和双射。
3．问题与应用（能力要求）
理解函数（映射），函数相等，象与原象、单射、满射和双射等概念，掌握其判别方法。
第二节函数的复合和反函数
1．主要内容
复合函数和反函数；
2．基本概念和知识点
复合函数和反函数；
3．问题与应用（能力要求）
理解复合函数和反函数概念。
（三）课后练习
Page164：
1；3—6；10—11；17—21。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
（第三部分代数系统）
第十章代数系统
（一）目的与要求
1．了解二元运算及其性质；
2．了解代数系统的概念。
（二）教学内容
第一节二元运算及其性质
1．主要内容
二元运算及其性质。
2．基本概念和知识点
二元运算；运算的性质；单位元；零元；幂等元。
3．问题与应用（能力要求）
了解二元运算及其性质。
第二节代数系统
1．主要内容
代数系统。
2．基本概念和知识点
代数系统的概念；
3．问题与应用（能力要求）
了解代数系统的概念。
（三）课后练习
Page191：
1；3—4；7—11。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第十一章半群与群
（一）目的与要求
1．了解半群的概念；
2．理解群的定义与性质；
3．了解子群的概念和判别方法；
4．理解循环群和置换群。
（二）教学内容
*第一节半群与独异点
1．主要内容
半群与独异点。
2．基本概念和知识点
半群；独异点。
3．问题与应用（能力要求）
了解半群的概念。
第二节群的定义与性质
1．主要内容
群的定义与性质。
2．基本概念和知识点
群；平凡群；交换群；群的性质。
3．问题与应用（能力要求）
掌握群的性质和证明方法。
第三节子群
1．主要内容
子群的概念。
2．基本概念和知识点
子群。
3．问题与应用（能力要求）
了解子群的概念和判别方法。
*第四节陪集与拉格朗日定理
1．主要内容
陪集与拉格朗日定理。
2．基本概念和知识点
陪集；拉格朗日定理。
3．问题与应用（能力要求）
了解陪集的概念；了解拉格朗日定理的应用。
*第五节正规子群与商群
1．主要内容
正规子群与商群。
2．基本概念和知识点
正规子群；商群。
3．问题与应用（能力要求）
了解正规子群与商群的概念。
*第六节群的同态与同构
1．主要内容
群的同态与同构。
2．基本概念和知识点
群的同态；群的同构。
3．问题与应用（能力要求）
了解群的同态与同构的概念。
第七节循环群与置换群
1．主要内容
循环群与置换群。
2．基本概念和知识点
循环群；生成元；置换；置换群。
3．问题与应用（能力要求）
理解循环群与置换群的概念；掌握有限循环群的性质；会求有限循环群和三阶置换群的子群。
（三）课后练习
Page229：
9—11；16—20；35—36。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
*第十二章环与域
（一）目的与要求
1．了解环的定义与性质；
2．了解整环与域。
（二）教学内容
第一节环的定义与性质
1．主要内容
环的定义与性质。
2．基本概念和知识点
环。
3．问题与应用（能力要求）
了解环的定义与性质。
第二节整环与域
1．主要内容
整环与域。
2．基本概念和知识点
整环；域；
3．问题与应用（能力要求）
了解整环与域的概念。
（三）课后练习
Page240：
1—2；4。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
*第十三章格与布尔代数
（一）目的与要求
1．了解格和布尔代数的基本概念；
2．理解格的定义和性质；
3．掌握分配格、有补格、布尔代数性质。
（二）教学内容
第一节格的定义与性质
1．主要内容
格的定义与性质。
2．基本概念和知识点
格。
3．问题与应用（能力要求）
了解格的定义与性质。
第二节子格与格同态
1．主要内容
子格与格同态。
2．基本概念和知识点
子格；格同态。
3．问题与应用（能力要求）
了解子格与格同态的概念。
第三节分配格与有补格
1．主要内容
分配格与有补格。
2．基本概念和知识点
分配格；有补格。
3．问题与应用（能力要求）
了解分配格与有补格的概念和判别方法。
第四节布尔代数
1．主要内容
布尔代数。
2．基本概念和知识点
布尔代数。
3．问题与应用（能力要求）
了解布尔代数的概念及其运算。
（三）课后练习
Page262：
1—2。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
（第四部分图论）
第十四章图的基本概念
（一）目的与要求
1．理解图的基本概念；
2．理解图的连通性、矩阵表示和运算。
（二）教学内容
第一节图
1．主要内容
图的基本概念：
结点、边、度数、自环和平行边等。
2．基本概念和知识点
有向图；无向图；握手原理；特殊图。
3．问题与应用（能力要求）
理解图的基本概念；掌握图的握手原理。
第二节通路与回路
1．主要内容
通路与回路。
2．基本概念和知识点
通路（简单通路、初级通路和复杂通路），回路（简单回路、初级回
路和复杂回路）
3．问题与应用（能力要求）
了解有向图和无向图的通路与回路的概念。
第三节图的连通性
1．主要内容
图的连通性。
2．基本概念和知识点
有向图的连通性；无向图的连通分支数。
3．问题与应用（能力要求）
了解有向图的连通性和无向图连通分支数。
第四节图的矩阵表示
1．主要内容
图的矩阵表示。
2．基本概念和知识点
关联矩阵；邻接矩阵。
3．问题与应用（能力要求）
了解图的矩阵表示方法。
第五节图的运算
1．主要内容
图的运算。
2．基本概念和知识点
图的交、并、差运算。
3．问题与应用（能力要求）
了解图的交、并、差运算。
（三）课后练习
Page191：
1—2；5—10；19—22；29—30。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
第十五章欧拉图与哈密顿图
（一）目的与要求
1．理解欧拉图的概念；
2．理解哈密顿图的概念。
（二）教学内容
第一节欧拉图
1．主要内容
欧拉图。
2．基本概念和知识点
欧拉通路与回路；欧拉图。
3．问题与应用（能力要求）
掌握欧拉图的判别方法。
第二节哈密顿图
1．主要内容
哈密顿图。
2．基本概念和知识点
哈密顿圈；哈密顿图。
3．问题与应用（能力要求）
掌握哈密顿图的判别方法。
（三）课后练习
Page303：
1—4；8—9；12。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
*第十六章树
（一）目的与要求
1．了解无向树和生成树的概念与性质；
2．了解根树的概念及其应用。
（二）教学内容
第一节无向树及其性质
1．主要内容
无向树的概念及其性质。
2．基本概念和知识点
无向树；树叶；分支点；森林；平凡树。
3．问题与应用（能力要求）
了解无向树的概念与性质。
第二节生成树
1．主要内容
生成树。
2．基本概念和知识点
生成树；最小生成树。
3．问题与应用（能力要求）
了解生成树的概念与性质。
第三节根树及其应用
1．主要内容
根树及其应用。
2．基本概念和知识点
根树；树根；子树；有序树；最优二元树；带权二叉树；最优二叉树；最优二叉树的哈夫曼算法。
3．问题与应用（能力要求）
了解根树及其应用，会用哈夫曼算法求最优二叉树。
（三）课后练习
Page319：
1—13；23—27。
（四）教学方法与手段
本章以课堂教学为主，并结合课堂练习与讨论，课后练习及答疑等手段使学生较好的掌握本章的重点和难点。
五、各教学环节学时分配
教学环节
教学时数
课程内容
讲课
习题课
讨论课
实验
其他教
学环节
小计
第一章
4
4
第二章
5
1
6
第三章
4
1
1
6
第四章
4
4
第五章
6
1
1
8
第六章
2
2
第七章
7
1
8
第十章
2
2
第十一章
5
1
6
第十四章
4
4
第十五章
4
4
合计
47
5
2
54
六、推荐教材和教学参考资源
选用教材：
耿素云、屈婉玲，离散数学（修订版），高等教育出版社，2004年1月。
教学参考资料：
1．左孝凌、李为监、刘永才编著，离散数学理论分析题解，上海科学技术文献出版社，1986年。
2．刘爱民，离散数学，北京邮电大学出版社，2004年5月。
3．MathematicalStructures（FourthEdition）BernardKolman,RobertC.Busby,SharonCutlerRoss.DiscreteBeijing:
HigherEducationPress2001.
七、其他说明
1．修订大纲的指导思想：
根据专业特点，使学生掌握必备的离散数学基本理论和基本方法，为学习后继专业课程、从事科学研究或工程技术打下一定的基础。
2．本课程与先修课程和后续课程的联系与分工：
先修课程解决该课程所必须的数学基础问题；本课程着重研究离散结构和相互关系；后续课程着重处理离散结构信息。
升级会员 