离散数学教案

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