《离散数学》教学大纲

1、离散数学教学大纲一、课程概述1. 课程研究对象和研究内容离散数学是计算机各专业的主干课之一，本课程的目的是使学生懂得怎样在一个通用的层面上， 利用离散结构去描述和理解计算机科学的基本问题和一般的求解方法。训练学生在符号处理层面上基于离散性思维的构造性思想。在计算机科学中不仅要证明解的唯一性，而更重要的是将解构造出来和证明构造的有效性。构造性是计算机科学的最基本的思维，构造的根据是一类问题的离散结构。通过本课程的学习，使学生能了解和掌握构造性思维方法；在开发和利用计算机系统过程中，在最通用层面上利用离散结构去塑造和设计计算机系统；对计算机系统中出现的问题能在符号层面上认识和寻找解决的办法；并能使

2、用有效的数学工具和逻辑工具。离散数学的整个教学就是围绕着 “能满足构造性思维的离散结构是什么？”通过本门课程的学习， 使学生从两个方面牢固认识、理解和掌握离散结构：一种是由事物和事物的性质和关系 （用谓词公式表示） 来确定的离散结构， 并能用形式符号的方法和等价的图形方法来描述；另一种是以关于事物的生成操作（在符号层面用代数运算表示）来确定的离散结构。2. 课程在整个课程体系中的地位离散数学是计算机专业的必修课。离散数学的先行课是线性代数。二、课程目标1知道离散数学这门学科的性质、地位和独立价值。知道这门学科的研究范围、基本框架、研究方法、学科进展。2理解各种离散结构的基本思想、构造方法、主要

3、概念和性质。3熟练掌握各种基本公式（如等值公式）、基本方法（如推理方法）和计算、证明过程及抽象方法，培养对数学模型问题的分析能力以及对数学方法的应用能力。4了解离散数学在计算机中各分支的一些应用。三、课程内容和要求这门学科的知识与技能要求分为知道、理解、掌握、 学会四个层次。这四个层次的一般涵义表述如下：知道是指对这门学科和教学现象的认知。理解是指对这门学科涉及到的概念、 原理、策略与技术的说明和解释， 能提示所涉及到的教学现象演变过程的特征、形成原因以及教学要素之间的相互关系。掌握是指运用已理解的教学概念和原理说明、解释、类推同类教学事件和现象。学会是指能模仿或在教师指导下独立地完成某些教学

4、知识和技能的操作任务， 或能识别操作中的一般差错。教学内容和要求表中的“”号表示教学知识和技能的教学要求层次。本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。教学内容及教学要求表教学内容知道理解掌握学会1 命题逻辑1.1命题及符号化1.2命题公式与等值运算1.3公式的主范式、对偶式1.4公式的蕴含与推理理论2 谓词逻辑2.1命题的谓词表示2.2谓词公式与解释2.3变元的约束2.4等价式与蕴含式2.5前束范式2.6推理理论3 集合论3.1集合及运算3.2二元关系及性质3.3二元关系的闭包运算3.4关系的复合与逆关系教学内容知道理解掌握学会3.5次序关系与等价关系3.6

5、函数4 图论4.1图的基本理论4.2图的连通性4.3特殊图4.4树5 代数系统5.1运算的概念及性质5.2半群5.3群与子群5.4阿贝尔群与循环群5.5置换群、变换群5.6同态与同构5.7环与域 .四、课程实施离散数学是各专业的基础课，每周安排4 课时，共72 课时 ,其中讲授72 学时 ,实验 0 学时。函授为课时课时安排及教学方法表教学内容课时建议教与学的方法建议72 课时35 课时命题逻辑理论讲授、习题讲解、学生加强演算和谓词逻辑推理练习。集合论2210理论讲授，学生加强理解。图论1410理论讲授，学生理解的记忆。代数系统165理论讲授 , 记住概念，掌握证明方法。合计学时学时四、教材和

6、参考书目1. 耿素云、屈婉玲 等编离散数学 ，高等教育出版社， 1997.2.陈 莉、刘晓霞编离散数学 ， 高等教育出版社， 2002.3.王朝阳 等编离散数学 ， 中国矿业大学出版社， 2001.五、课程评价1这门学科的评价依据是本课程标准规定的课程目标、教学内容和要求。2考试时间：120 分钟。3考核方式、分制与分数解释理论课采用闭卷、笔试的方式，以百分制评分，60 分为及格，满分为100 分。有可能的话，把形成性评价与终结性评价结合起来。4理论考试题型参考比例单选题 20%；填空题20%；判断题5%； 证明题 25%；计算及综合题30%。5样题与目标定位示例A 单选题：（着重考查学生对知

7、识的识别程度）例：设 A=1 ， 2， 3 ，以下 _是 A 上的偏序关系。A. R=(1,1),(1,2),(2,3),(2,1),(2,2),(3,3)B. R=(1,2),(1,1),(2,2),(3,3),(1,3)C. R=(1,1),(2,1),(2,2),(2,3)D. R=(1,2),(2,3),(1,1),(2,1),(2,2),(3,3)B填空题： （着重考查学生对知识的理解程度）例：设 A 为集合，在 (A) 上运算的单位元是_ ,零元是 _。C判断题： （着重考查学生对知识的理解程度）例：一个有 5 个结点， 4 条边的连通图是树。（）D计算题：（着重考查学生对知识的掌握与学会程度）例：1一棵树具有3 个 2 度结点， 2 个 4 度结点， 2 个 5 度结点，其余为叶。试求其共有多少个结点？多少片叶？2求命题公式( pqr )(p(qr ) 的主析取范式， 并判断公式的类型。F