《离散数学》授课计划2013-2014第2学期.doc

2013 /2014 学年第 2 学期 授 课 计 划 课程名称： 《离散数学》 课程代码： 授课对象： 学 时 数： 其中讲课： 64 实 验： 0 执行的教学大纲（名称、制定日期）： 教材（名称、编著者、出版日期）： 主要参考书目： 主讲教师： 辅导教师： 课程组组长（签字）: 2014年 2 月 22 日 订 学期授课计划 周别 授课顺序 授课章节及内容摘要 需要时间 作业数量 作业估计时间 一 二 三 四 五 六 七 八 九 十 十 一 十 二 十 三 十 四 十 五 十 六 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 第0部分 课程简介 有关课程内容及学习、考核方式的介绍 命题逻辑 1、命题符号化及联结词 内容摘要：命题与真值、简单命题与复合命题、常用联结词、命题符号化 2、命题公式及分类 内容摘要：公式的赋值或解释、真值表、 公式的类型及判断、基本等价式、公式的等价演算 3、联结词全功能集 内容摘要：公式在多个联结词全功能集中的互化 4、对偶与范式 内容摘要：合取范式与析取范式概念、 极小项与主析取范式求法、极大项与主合取范式求法、主合取范式与主析取范式的命题公式互化 5、推理理论 内容摘要：推理的形式结构、推理证明的2种方法 6、例题讲解 谓词逻辑 1、谓词逻辑基本概念 内容摘要：个体与谓词、量词、命题符号化 2、谓词逻辑公式及解释 内容摘要：谓词逻辑公式、量词的辖域、 约束变元与自由变元、公式的解释、公式的类型及其判断 3、谓词逻辑等价式 内容摘要：等价式及应用、前束范式 4、一阶逻辑推理理论 内容摘要： UI、UG、EI、EG规则、带量词推理的构造证明方法 5、例题讲解 6、数理逻辑部分内容总结 第三部分 集合的基本概念和运算 1、集合的基本概念 内容摘要：集合与元素、集合与集合、空集、幂集与全集 2、集合的基本运算 内容摘要：集合的基本运算、集合运算的运算律、运算的应用 3、有穷集合的计数问题 内容摘要：元素的计数基本概念、文氏图的使用、包含排斥原理 4、例题讲解 第四部分 二元关系和函数 1、基本概念 内容摘要：关系、二元关系、关系矩阵和关系图、关系的特性 2、关系的合成 内容摘要：关系的的合成、关系的幂运算、合成关系的矩阵表示 3、关系上的闭包运算 内容摘要：逆关系、关系的闭包运算 4、次序关系 内容摘要：偏序关系、拟序关系、线序关系 5、等价关系和划分 内容摘要：等价关系、划分 6、本章小结 7、函数的定义和性质 8、函数的合成与反函数 9、例题讲解 第五部分 图论 图的基本概念 内容摘要：无向图和有向图、顶点的度数与握手定理、子图与补图、图的同构 图的连通性 内容摘要：通路与回路、无向图的连通性与连通度、有向图的连通性及其分类 图的矩阵表示 内容摘要：无向图的关联矩阵、有向图的关联矩阵、无向图的邻接矩阵、有向图的可达矩阵 几种特殊的图 内容摘要：欧拉图及判定、应用、哈密尔顿图及判定、应用、二部图及应用、平面图、平面图着色 5、无向树 内容摘要：无向树的定义及性质、生成树及最小生成树 6、根树及其应用 内容摘要： 根树的定义和性质、最优树、 哈夫曼算法、最佳前缀码、根树的应用 7、本章小结 课程复习、总结 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2