1、1滁州学院计算机与信息工程学院课程教案课程名称： 离散数学 授课教师： 赵欢欢 授课对象： 11 级网络工程 专业 3、4 班 授课时间： 2012 年 9 月-2012 年 12 月 滁州学院计算机科学与信息工程学院2012 年 8 月2离散数学教学大纲（Discrete Mathematic）课程代码： 学时：48 学分：3一、课程简介本大纲根据 2009 版应用型人才培养方案制订。 （一）教学对象：网络工程、计算机科学与技术专业本科学生（二）开课学期：第三学期（三）课程类别：专业基础课（四）考核方式：考试（五）参考教材：离散数学第 2 版 邓辉文 清华大学出版社 2010.主要参考书目：
2、1邵学才,叶秀明 . 离散数学M.北京电子工业出版社， 2009.2邵志清,虞慧群 . 离散数学M.北京电子工业出版社， 2003.3屈婉玲. 离散数学 习题解析M.北京大学出版社， 2008.本课程的先修课程是高等数学、线性代数，后 续课程包含数据结构、数据 库原理及应用、操作系统、数字逻辑、人工智能、算法分析与设计等。二、教学基本要求与内容安排（一）教学目的与要求离散数学是研究离散量的结构及其相互关系的学科,它在各学科领域特别在计算机科学领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程必不可少的先行课程。本课程的教学目的旨在通过对离散数学的教学，让学生不但可以掌握处理如集合、代
3、数结构和图等离散 结构的描述工具和方法，为后续课程的学习创造条件，而且为学生今后提高专业理论水平，从事计算机行业的实际工作提供必备的抽象思维和严格的逻辑推理能力， 为将来参与创新性的研究和开发工作打下坚实的基础。（二）教学内容安排3学时分配教学内容 教学要求 教学方法 重点() 难点()讲课 实验 上机 其他备注第一部分 数理逻辑 讲授 15.51 命题逻辑的基本概念 21.1 命题与联接词 B 11.2 命题公式及其赋值 A 12 命题逻辑等值演算 3.52.1 等值式 B 12.2 析取范式与合取范式 A 12.3 联接词的完备集 C 0.52.4 可满足性与消解法 B 13 命题逻辑的推
4、理理论 2 3.1 推理的形式结构 A 13.2 自然推理系统 P B 14 一阶逻辑基本概念 24.1 一阶逻辑命题符号化 A 14.2 一阶逻辑公式及解释 A 15 一阶逻辑等值演算与推理 35.1 一阶逻辑等值式与置换规则 A 15.2 一阶逻辑前束范式 A 15.3 一阶逻辑的推理理论 A 16 数理逻辑在计算机中的应用 3第二部分 集合论 讲授 131 集合代数 21.1 集合的基本概念 B 0.51.2 集合的运算 A 0.51.3 有穷集的计数 C 0.51.4 集合恒等式 A 0.52 二元关系 62.1 有序对与笛卡尔积 A 12.2 二元关系 A 12.3 关系的运算 A
5、12.4 关系的性质 A 12.5 关系的闭包 A 12.6 等价关系与划分 A 13 函数 33.1 函数的定义与性质 A 0.53.2 函数的复合与反函数 A 0.543.3 双射函数与集合的基数 C 13.4 一个电话系统的描述实例 C 14 集合论在计算机中的应用 2第三部分 代数结构 讲授 6 1.51 代数系统 31.1 二元运算及其性质 A 11.2 代数系统 A 11.3 代数系统的同态 与同构 B 12 群与环 32.1 群的定义及其性质 A 12.2 循环群与置换群 A 2第四部分 图论 讲授 121 图的基本概念 2.51.1 图 A 0.51.2 连通与回路 A 0.5
6、1.3 图的连通性 A 0.51.4 图的矩阵表示 A 0.51.5 图的运算 A 0.52 欧拉图与哈密顿图 22.1 欧拉图 A 0.52.2 哈密顿图 A 0.52.3 最短路问题与货郎担问题 C 13 树 1.53.1 无向树及其性质 A 0.53.2 生成树 A 0.53.3 根树及其应用 B 0.54 平面图 34.1 平面图的基本概念 B 0.54.2 欧拉公式 B 0.54.3 平面图的判断 B 14.4 平面图的对偶图 C 15 图论在计算机中的应用 3（教学要求：A熟练掌握；B掌握；C了解）三、实验内容本课程无实验5制订人（签字）： 审核人（签字）： 教 学 进 度 表 2
7、0122013 学年第 1 学期授课教师姓名 赵欢欢 职称 助教 授课专业 网络工程 班级 2011 级 课程名称 离散数学 教材名称 离散数学 出版社 清华大学出版社 其中周次日期周学时讲课实验课习题课课堂讨论其他环节教 学 内 容 摘 要（章节名称、讲述的内容提要、实验的名称、课堂讨论的题目等）第一周9 月 3 日至 9 月 9日4 4第一讲 集合、映射与运算（一）1.1 集合的基本概念 理论：集合、子集、幂集、n 元组、笛卡 尔积第二讲 集合、映射与运算（二）1.2 映射的有关概念 理论：映射的定义、映射的性质 、逆映射、复合映射第二周9 月 10 日至 9 月 16日2 2第三讲 集合
8、、映射与运算（三）1.3 运算的定义和性质 理论：运算的定义、运算的性质第三周9 月 17 日至 9 月 23日4 4第四讲 集合、映射与运算（四）1.4 集合的运算 1.5 集合的划分 1.6 集合的对等理论：集合的并、交、差、补、对 称差等基本运算，集合的划分与覆盖、集合对等、可数集合、不可数集合第五讲 关系（一）2.1 关系的概念理论：n 元关系的定义、2 元关系、关系的定义域和值域、关系的表示、函数的关系定义第四周9 月 24 日至 9 月 30日2 2第六讲 关系（二）2.1 关系的运算 理论：关系的集合运算、逆运算、复合运算、关系的其他运算第五周10 月 1 日至 10 月 7日
9、4 4国庆放假第七讲 关系（三）2.3 关系的性质 2.4 关系的闭包理论：关系的性质：自反性、反自反性、对称性、反 对称性、传递性；自反闭包 r(R)、对 称闭包 s(R)、传递闭包 t(R)第六周10 月 8 日至 10 月14 日2 2第八讲 关系（四）2.5 等价关系 2.6 相容关系 2.7 偏序关系理论：等价关系的定义、等价类 ；相容关系的定义；偏序关系的定义、哈斯图的、偏序集中的特殊元素第七周10 月 15日至 10月 21 日4 4第九讲 命题逻辑（一）3.1 命题的有关概念 3.2 逻辑联接词理论：命题的定义与真值、原子命 题和复合命题、各种 逻辑连接词的含义，真假的判断第十
10、讲 命题逻辑（二）3.3 命题公式及其真值表理论：命题公式的定义、命题的符号化、命题公式的真值表、命题公式的类型周 数 16 周 计划学时 48 学时讲 课 48 学时 课堂讨论 0 学时实验课 0 学时 习题课 0 学时 其他环节 0 学时6第八周10 月 22日至 10月 28 日2 2第十一讲 命题逻辑（三）3.4 逻辑等值的命题公式理论：逻辑等值的定义、基本等 值式、等 值演算法、对偶原理第九周10 月 29日至 11月 4 日 4 4第十二讲 命题逻辑（四）3.5 命题公式的范式理论：命题公式的析取范式和合取范式的定义域求法命题公式的主析取范式及主合取范式的定义和求法第十三讲 命题逻
11、辑（五）3.7 命题逻辑中的推理理论：推理形式有效性的定义；基本推理规则；命题逻辑的自然推理系统第十周11 月 5 日至 11 月11 日2 2第十四讲 谓词逻辑（一）4.1 个体、谓词、量词和函词理论：谓词逻辑概念，谓词的概念与表示，量词的概念与表示，个体域，辖域，约束变元和自由变元的含义第十一周11 月 12日至 11月 18 日4 4第十五讲 谓词逻辑（二）4.2 谓词公式及命题的符号化 4.3 谓词公式的解释及类型理论：谓词公式的定义，将命题 用用符号（个体，量 词，谓词）来表示，消去量词的逻辑等值式，永真式，科满足式，永假式及中性式的概念第十六讲 谓词逻辑（三）4.4 逻辑等值的谓词
12、公式 4.5 谓词公式的前束范式 理论：谓词公式等值的定义，基本等 值式，前束范式第十二周11 月 19日至 11月 25 日2 2第十七讲 图论（一）6.1 图的基本概念 6.2 节点的度数 6.3 子图， 图的运算和图同构理论：图的定 义，邻接，关联，简单图， 节点的度数，子图第十三周11 月 26日至 12月 2 日4 4第十八讲 图论（二）6.4 路与回路 6.5 图的连通性理论内容：路，回路，无向图的连通性，无向连通图的点连通度与边连通度，有向图的连通性第十九讲 图论（三）6.6 图的矩阵表示 6.7 赋权图及最短路径理论内容：图的邻接矩阵，可达矩 阵，关 联矩阵，赋权图，最短路径第
13、十四周12 月 3 日至 12 月 9日2 2第二十讲 图论（四）7.1 欧拉图理论内容：欧拉图的有关概念，欧拉定理，中国邮递员问题、Hamilton 图第十五周12 月 8 日至 12 月16 日4 4第二十一讲 图论（五）7.2 无向树 7.3 有向树理论内容：树的基本概念，最小生成 树，二叉 树的遍历与表达式的计算第二十二讲 代数结构（一）5.1 代数结构简介理论内容：代数结构的定义，半群及独异点，子代数，代数结构的同态与同构第十六周12 月 17日至 12月 23 日2 2第二十三讲 代数结构（二）5.2 群的定义及性质理论内容：群的有关概念，子群，群的同态第十七周12 月 24日至
14、12月 30 日2 2 第二十四讲 总复习系主任签名： 院长签名： 年 月 日 年 月 日7说明：1本教学进度表由主讲教师负责填写，于每学期开学第一周内送交教师所在系，经领导审定、签字后备查。2此表一式三份，其中，任课教师一份，教师所在系一份，教务处一份。第一讲：集合、映射和运算（一）一、教学目标1. 掌握集合的概念与表示2. 理解子集、幂集、 n 元组与笛卡儿积的概念3.掌握子集，幂集，笛卡尔积的求法 二、重点与难点分析1.重点：集合的概念，子集，幂集，笛卡尔积的概念及求法2.难点：幂集三、 教学内容与教学过程1.进行自我介绍（5 分钟）姓名，联系方式，专业方向。建议学生用电子邮件方式联系。
15、2.进行课程简介（10 分钟）离散数学是研究离散量的结构及相互之间关系的学科是一门专业基础课，是数据结构、操作系统、计算机组成原理、数据库原理等课程的数学基础。特点：知识点集中，概念，定理多；方法性强；学数学就要做数学成绩评定：平时成绩(到课情况，书面作业，平时测验)占 30%,期末考试占70%3.进入主题，开始第一讲(1) 集合的有关概念 (20 分钟)集合 定义：集合是具有某种特定性质的对象汇集成的一个整体，通常用大写字母 A,B,C,D 表示。例如：滁州学院全体学生计算机与信息工程学院所有女生常见的数的集合：N,N +,Z,Q,R,C元素集合中的每一个对象称为该集合的元素，通常用小写字母
16、 a,b,c,d,x,等表示例如：滁州学院的每个学生计算机与信息工程学院的每个女生N：0、1、2、38集合的表示方法列举法：Z=,-2,-1,0,1,2,描述法：x|x 是自然数且 x 小于 10递归法文氏图： 特殊集合：全集 U,空集 元素与集合xA 或 x|A|表示集合 A 中的元素个数注意：集合中的元素可以是集合，如 A=a,a,b,b,c,|A|=4,a,bA注：集合中的元素无顺序；集合中无重复元素例：指出下列哪些是集合，哪些不是集合？中国人的集合； 百货商店里好看的花布的集合；1000 以内的素数的集合；26 个英文字母组成的集合；这个班里高个子学生的集合；直线 y2x-5 上的点的
17、集合。(2)集合之间的关系子集（15 分钟）定义：若 A 中的任意元素都属于 B，则 A 是 B 的子集，称 A 包含于 B 或 B包含 A， ，包括的两层含义：包含与真包含（AB） ， ，A 是 B 的真子B集注意：属于（元素与集合的关系）与包含于（集合与集合的关系）的区别例：A=1,2,3,4，B=2,4或 A定理 1-1： A定理 1-2： （自反性）(1);则 A=B2,B则 （传递性） (3)ACA用定义进行证明定理 1-3：A=B 的充要条件是 ,B9注：该定理是证明两个集合相等的基本方法该定理与定理 1-2 中的(2)的区别 例 1-2注：A 中有一个元素不属于 C，则 ，反证法
18、是一种很好的方法A幂集（15 分钟）定义：由 X 的所有子集组成的集合， ()|PX例：x=1,2，(),12,PY=a,b,c,abcacbc例 1-3注：若|X|=n,P(x)的元素有： ；由一个元素构成的子集；由两个元素构成的子集；由 n 个元素构成的子集计数的基本原理：加法原理：图示乘法原理：图示定理 1-4：若|X|=n,|P(X)|=2 n证明：加法原理：二项式定理： 0()nrnrxyCxy121.()2nnC乘法原理：注：每个元素的参与与否构成不同的子集n 元组（5 分钟）定义：论域 U 中选取的 n 个元素按照一定的顺序排列，得到 n 元有序组，称n 元组，记为：(x1,x2
19、,x3,xn)或例：平面直角坐标系中点的坐标是 2 元组；空间直角坐标系中点的坐标是 3元组；n 元组在数据结构中是一个表有序对，序偶：2 元组注：(x,y )(y,x)笛卡尔积（10 分钟）定义：设 是集合，称 为1,2.An,(1,2.)|12,.iixnxAnA1,A2,An 的笛卡尔积（直积，叉积） ，记为： .例：A=a,b,B=1,2，例 1-4注： 一般来说， AB定理 1-5：若|A|=m,|B|=n,则| |=mn.:,nA104. 教学小结（5 分钟）本讲首先介绍了集合的概念与表示方法，接着介绍了集合之间的关系子集与幂集，n 元组，笛卡尔积的概念及相关定理。 四、 作业与实验（5 分钟）1. 书面作业：习题 1.1 1、2、3、7、102. 上机作业：无
