搜索
《离散数学》课程教学大纲模板（黑体小三号居中）（以下标题为黑体小四号，行距为18磅，内容为宋体五号）一、课程定位本课程的授课对象、课程的基本描述(课程的性质、任务、与其它课程的关系等)和在人才培养过程中的地位和作用。《离散数学》是计算机科学以及相关专业重要的专业基础课。包括的主要内容有：数理逻辑、集合论、二元关系、函数和图论等。它以研究离散量的结构和相互关系为主要目标，通过该课程的学习，培养学生抽象思维和严密的逻辑推理能力，为进一步学习其它专业课打好基础，并为学生今后处理离散信息，提高专业水平，从事计算机或者相应专业以及实际工作提供必备的数学工具。二、教学目标学生通过学习该课程后，在思维、知识和能力等方面应达到的目标。1.有效地掌握该门课程中的所有概念。通过讲课和布置一定数量的习题使学生能够使用所学的概念对许多问题作出正确的判断。2.通过课程中许多定理的证明过程复习概念，了解证明的思路，学会证明的方法，并使学生掌握定理的内容和结果。3.通过介绍各种做题的方法，启发学生独立思维的能力。创造性的提出自己解决问题的方法，提高学生解决问题的能力。4.通过该门课程的学习使学生掌握逻辑思维和逻辑推理的能力，培养学生正规的逻辑思维方式。课程名称：离散数学/DiscreteMathematics课程编码：20019703总学时数/学分数：专业基础课实验学时：0上机学时：0课程所属部门：信息技术工程学院适用专业：计算机科学与技术、网络工程、软件工程及相关专业课程负责人：制定日期：2017年3月三、课程教学内及要求教学内容及学时教学要求实验（上机）项目及学时第一章数理逻辑（16学时）1.命题2.重言式3.范式4.推理规则和证明方法5.*谓词和量词了解：命题与真值；原子命题、复合命题；命题常元与变元；联结词；真值表；原子公式与命题公式；逻辑等价式；重言式（或永真式）、永假式（或矛盾式）、可满足式；恒等式；永真蕴含式；代入与替换规则；基本积，基本和；极小与极大项；主析取与主合取范式；推理；前提；有效结论；证明；*个体常元与变元；*谓词常元与变元；*论述域；*全总个体域；*量词与辖域；*全称与存在量词；*特性谓词；*原子公式；*谓词公式；*自由与约束变元；*改名规则。理解：命题P的否定式；命题P和Q的合取、析取、蕴含以及等值式；求给定公式的或真或或假的赋值；判断给定公式的类型；熟练求已给公式的极小与极大项、进而求主析取与主合取范式的主要步骤；每个公式都有唯一主合取与主析取范式；推理正确的定义；证明中常用的推理规则；间接证明法；反证法及CP规则法；*特性谓词的加入规则；*命题与谓词之间的相互联系；*量词的量化作用；*正确判断量词的辖域、指明相应的自由与约束变元。掌握：运用五个常用联结词将命题符号化；熟练的构造给定公式的真值表，并用于判断某复合命题的真假；用真值表判断给定公式的类型；牢记并灵活运用重要的恒等式和永真蕴含式；用等值演算法判断二公式是否等价；用定值观察法及等值演算法证明一蕴含式是否为永真蕴含式；运用真值表法或填满变元法熟练地求给定公式的主范式；主析取与主合取范式之间的紧密联系及转化；熟练的掌握判断有效结论的方法：真值表法、*直接证明法、*间接证明法（含反证法及CP规则法）；*用推理规则构造推理的证明；*较熟练的进行不太复杂的自然语言与谓词公式之间的简单翻译；*掌握量词与联结词之间的转化关系。应用：XXXX第二章集合论（4学时）1.集合论的基本概念2.集合上的运算3.集合的笛卡尔乘积了解：集合的并、交、差、补；*对称差集；幂集；序偶；n重组；笛卡尔乘积。理解：两集合相等、全集的相对性；含有集合作为元素的特殊集；常用的集合恒等式；*对称差运算及其性质；用文式图表示集合的运算及之间关系；序偶中元素的次序是重要的；笛卡尔乘积运算的性质。掌握：集合的两种表示法；正确区别“属于”与“包含”之不同；证明集合相等的两类方法；证明集合恒等式；求给定集合的幂集；熟练地求集合的笛卡尔乘积。第三章二元关系（10学时）1.基本概念2.关系的合成3.*关系上的闭包运算4.次序关系5.等价关系与划分了解：关系与二元关系（含A到B的关系及A上的关系）；空关系、全域关系；A上的恒等关系；关系R的定义域与值域；*关系矩阵；关系图；A上的关系的五种特性；关系的合成；关系的幂运算；*逆关系；*关系的闭包；偏序（集合）、拟序（集合）、线序（集合）及良序（集合）；哈斯图；最大、最小、极大、极小元素；上界、下界、最小上界与最大下界；等价关系；等价类；模K等价；*划分；*块；*秩。理解：一个关系的三种描述形式（即序偶、*关系矩阵、关系图表示）；通过关系图确定关系的特性；关系经合成后所得新关系与原关系的联系；*关系经求逆后所得新关系与原关系的联系；偏序与拟序之间的关系；偏序与线序、良序之间的关系；上、下界与最小上界及最大下界；*等价关系与划分之间的一一对应关系。掌握：求给定关系的定义域和值域；判断给定关系的性质；由给定关系求合成关系；*由给定关系求逆关系；*关系的闭包；判断某给定关系R是否为偏序、线序或良序关系；熟练的画出偏序集合的哈斯图，并求出某子集的各种特异元素；判定某给定关系是否为等价关系；*判断集合A的子集构成的集合是否是A上的划分；*搞清并牢记集合A上的等价关系与其上的划分的相互诱导。第四章函数（4学时）1.函数的基本概念2.特殊函数类3.*逆函数了解：函数；恒等函数；合成函数；逆函数单射、满射与双射；集合A的特征函数；*逆函数。理解：函数是满足单值性的特殊关系；正确区别函数的合成与关系的合成在记法上的不同；单、满射与双射的性质，如单（满、双）射和单（满、双）射的合成仍是单（满、双）射；集合A的特征函数的性质；*只有双射才有逆函数。掌握：判断一个关系是否是函数；求两个给定函数的合成函数；判断一函数是否为单射、满射、双射；*判断一个函数是否有逆函数；求出逆函数。第五章图论（14学时）1.图的基本概念2.路径和回路3.几种特殊图4.*树了解：无向图与有向图；邻接；关联；多重边、平行边；路径与回路；图中顶点之间的可达关系；路径与回路的长度；两点间的距离；欧拉路径（回路）及欧拉图；哈密尔顿路径（回路）；二部图，完全二部图；平面图、平面图的面；*无向树、*树叶、*分支点、*森林；*生成树；*树枝与弦；*最小生成树。理解：零图、底图、（ｎ，ｍ）图；多重图、线图与简单图；顶点的次数、有向图中顶点的引入次数和引出次数；图的同构；子图、生成子图；完全图；补图；路径（回路）的分类：简单及基本路径（回路）；无向连通图以及连通分支；三种有向连通图：强、单项及弱连通图；强（单向、弱）分图；赋权图；无向及有向图为欧拉图的充要条件；欧拉公式及其推论；*无向树的几个等价定义；*无向树中边数等于顶点数减一；*任一连通无向图至少有一棵生成树。掌握：灵活运用无向图中关于顶点的次数的重要结论；能判断两个简单的图是否同构；判断无向或有向图中路径及回路的类型；判断一个图是否为欧拉图；*利用定义、定理判断一个图是否为平面图；*利用图的次数定理以及树的有关性质，由已知树中某些顶点的次数求其它顶点的次数（或求具有指定次数的某种顶点数）；*求连通图的生成树；*用Kruskal法求最小生成树。说明：1.实验和上机内容只填写项目名称及学时，具体内容和要求见实验大纲。2.教学要求分章节按“了解”、“理解”、“掌握”三个层次编写教学内容及要求。“了解”是指学生应能辨认的科学事实、概念、原则、术语，知道事物的分类、过程及变化倾向，包括必要的记忆；“理解”是指学生能用自己的语言把学过的知识加以叙述、解释、归纳，并能把某一事实或概念分解为若干部分，指出它们之间的内在联系或与其它事物的相互关系；“掌握”是指学生能根据不同情况对某些概念、定律、原理、方法等在正确理解的基础上结合事例加以运用，包括分析和综合。“应用”指学生运用已获得的知识去解决新的练习性课题或实际问题，要求以语言或实际操作的方式把所学得的知识具体化并应用到社会实践中去。四、教材、参考书和阅读材料(1)教材：《离散数学》（第三版）方世昌西安电子科技大学出版社2009(2)参考书：《离散数学》（第2版）屈婉玲高等教育出版社2015《离散数学》左孝陵上海科学技术文献出版社1982《DiscreteMathematicsandItsApplications》（美）KennethH.Rosen著徐六通等译机械工业出版社2015五、考核方式及评分标准考核方式、以及详细的成绩评定标准（包括课堂参与、出勤、作业情况的各种评分方式、标准以及考核中的重要提示）本课程为考试课。期末笔试占总成绩的70%，平时作业、小测验与考勤提问等环节占总成绩的30％，学期总成绩合格才能获得学分。六、其他情况说明注：带“*”内容为选讲内容，可根据需要及学时而定取舍。