070101118《离散数学》教学大纲

课程编号：070101118《离散数学》课程教学大纲（DiscreteMathematics）一、课程简介1、课程性质：专业基础必修课．2、开课学期：第三学期3、学时学分：总学时：68学分：34、适用专业：计算机科学5、课程修读条件：在修完高等数学与线性代数课程之后开设。6、课程教学目的：离散数学是计算机科学中基础理论的核心课程。通过本课程的学习，培养学生的抽象思维和严密的逻辑推理能力，应用自如的解题技巧，以及训练有素的演算能力，使学生能处理各种离散结构事物的描述工具与方法，为进一步学习专业课打好基础，并为学生今后处理离散信息，提高专业理论水平，从事计算机的实际工作提供必备的数学工具。二、教学基本要求或建议：1、掌握一些现代数学语言2、理解有关基本概念3、掌握有关基本理论知识4、熟练掌握一些重要方法三、内容纲目及标准：第一章命题逻辑[教学目的]正确理解命题、命题联结词、真值表、命题公式的递归定义等概念，掌握命题符号化方法，命题公式真值表的求法，命题演算的基本方法、命题公式范式的判定及求法及应用命题演算基本公式和推理规则进行正确的推理和应用，为学习下一章谓词（一阶）逻辑打下扎实基础。[教学重点与难点]（1）命题公式与符号化；真值表与等价公式（2）重言式与蕴含式；其他联结词（3）对偶与范式（4）推理理论（难点）[教学内容纲目]第一节命题逻辑辑基本概念一、命题与联结词概念二、真值表三、命题公式与赋值第二节命题逻辑等值演算一、等值式二、析取范式与合取范式三、联结词完备集第三节命题逻辑的推理理论一、推理的形式结构二、自然推理系统第二章谓词逻辑[教学目的]正确理解谓词，量词，永真公式，前束范式等基本概念，理解命题演算和谓词演算的相互关系，了解公理化理论的基本思想及公理化理论在计算机科学中的地位和作用。[教学重点与难点]（1）量词与变元（2）等值公式演算（3）前束范式（4）谓词演算推理（难点）[教学内容纲目]第一节谓词（一阶）逻辑基本概念一、一阶逻辑命题符号化（一）个体变项与常项（二）谓词与量词（三）谓词公式二、一阶逻辑公式及解释（一）变元（二）解释（三）等值公式三、公式分类第二节一阶逻辑公式等值演算与推理一、一阶逻辑等值式与置换规则二、一阶逻辑前束范式三、一阶逻辑的推理理论（一）一阶逻辑的公理化理论（二）谓词演算与逻辑程序设计语言第三章集合论[教学目的]（1）正确理解集合、关系、映射的基本概念，理解多元运算的概念，能正确判定单射、满射、双射。（2）熟练掌握集合、关系、映射的运算极其性质。（3）理解和掌握偏序关系、相容关系、等价关系的概念和作用。（4）正确认识无限集合的本质特征，理解集合基数的实质，掌握比较集合基数大小的方法。[教学重点与难点]集合的运算与性质，关系的概念与表示，关系的运算，关系的性质与闭包（难点），次序关系（难点），等价关系（难点），映射，无限集的特征，集合的基数（难点）。[教学内容纲目]第一节集合的概念与运算一、集合的基本概念（一）元素与集合（二）集合的相等（三）子集和幂集二、集合的运算（一）集合的交、并、差（补）运算（二）集合的运算律（三）有序对与笛卡儿积三、集合恒等式第二节二元关系一、关系的概念极其表示（一）关系（二）图表示（三）矩阵表示二、关系的运算（一）交、并、差（补）（二）复合三、关系的性质与闭包（一）自反性，非自反性（二）对称性，非对称性（三）传递性（四）关系的闭包四、等价关系与划分（一）等价关系与等价类（二）商集（三）集合的划分五、次序关系（一）拟序，偏序，线性序（二）极大（小）元，最大（小）元，上（下）界，上（下）确界第三节函数一、函数的定义与性质（一）单射（二）满射（三）1-1映射二、函数的复合与反函数（一）函数的复合（二）逆涵数三、无限集（一）无限集的特征（二）集合的基数第四章代数系统[教学目的]（1）理解和掌握代数系统的概念和性质（2）熟悉半群的概念和特性（3）正确理解群、子群、正规子群、商群、群同态与群同构的概念，熟悉它们的性质，掌握它们的判定方法。（4）理解变换群、置换群的概念和作用，理解置换的计算。（5）掌握循环群的特性和结构。（6）理解Lagrange定理和同态基本定理，并能正确应用。（7）理解格和Boole代数的概念和性质。（8）了解代数系统在计算机科学研究中的地位与作用。[教学重点与难点]半群，群与子群，同态与同构（难点），格，布尔代数（难点），布尔表达式（难点）。[教学内容纲目]第一节代数系统的基本概念一、二元运算及性质（一）单位元（二）逆元（三）同态与同构二、代数系统第二节半群与群一、半群与独异点二、群的定义与性质三、子群四、陪集与Lagrange定理五、正规子群与商群六、群同态与同构基本定理七、循环群与置换群第三节格与Boole代数一、格的定义与性质二、子格与格同态三、分配格与有补格四、Boole代数第五章图论[教学目的]（1）正确理解图论中的基本概念，理解图的连通性。（2）理解Euler图和Hamilton图的特性，并能正确判定。（3）熟悉掌握图的矩阵表示（4）熟悉平面图的概念，判断和有关着色。[教学重点与难点]路与回路的概念，图的矩阵表示，欧拉图与汉密尔顿图，平面图，对偶图与图的着色（难点）。[教学内容纲目]第一节图论基本概念一、图、通路与回路二、图的连通性三、图的矩阵表示第二节Euler图和Hamilton图一、Euler图二、Hamilton图三、带权图与货郎担问题第三节平面图及图的着色一、平面图的基本概念二、平面图的判断与Kuratowski定理三、平面图的点着色与边着色（二）实践部分无实验四、课程学时分配：序号章节标题学时其中讲授讨论实验上机习题其他第一章命题逻辑14122第二章谓词逻辑12102第三章集合论1091第四章代数系统16142第五章图论16133合计685810五、分专业、层次的不同要求的有关说明：对计算机科学与技术，网络工程本科专业（64学时），必须根据实际情况完成主要教学内容。对专科学生，相应降低要求。在教学目标、教学内容及要求、教学方法、教学手段、考试、参考书目等方面差异不大。六、课程作业与考核评价：课程作业训练每周2次，每次2-4个题目，具体作业类型参见教材，课堂讨论课考查学生课堂表现及学习理解能力，期中期末考试形式为闭卷考试，课程试卷试题结构为判断题，填空题，计算题，证明题及综合应用题。考试内容主要考查学生对基础知识的掌握程度，同时又考查学生对所学知识的理解与应用。课程作业、课堂考核及课堂讨论课情况为平时成绩主要依据，闭卷考试成绩和平时成绩按一定比例（不举行期中考试：6：4，举行期中考试则期末考试成绩、期中考试成绩、平时成绩的比为：4.5：1.5：4）构成课程总评成绩。七、教材及主要参考书教材：《离散数学》耿素云等编高等教育出版社(2004.1)参考书：1、《离散数学》左孝凌等编著上海科技文献出版社(1982.)2、《离散数学理论分析题解》左孝凌等编著上海科学技术文献出版社（1988.）3、《离散数学》方世昌编西安电子科技大学出版社(1990.5)4、BernardKolman，RobertC.Busby，SharonCutlerRoss.DiscreteMathematicalStructures(FourthEdition)[M].Beijing:HigherEducationPress,2001.5、《离散数学导论》徐洁磐高等教育出版社（1991.）6、J．P．特伦布菜R．马诺哈著，罗远诠、李盘林等译7、《离散数学结构及其在计算机科学中的应用》上海科学技术出版社（1982.）8、《离散数学及其应用》傅彦等电子工业出版社（1997.6）9、《离散数学》王遇科北京工业学院出版社（1986.）课程教学标准批准：审核人：制定：