四川大学离散数学教学大纲[2011软件].docxVIP

离散数学教学大纲（2011年2月修订）课程名离散数学课号311019040类型必修所属学科软件工程领域方向离散数学学时68+20学分4+1教师冯伟森、栾新成、何坤、林兰先修课程线性代数、高等数学同修课程无基本目的让学生学习并掌握离散数学基本理论知识， 培养学生的数学涵养和抽象思维能力；为学生在进一步学习专业课程或解决实际问题时所需要的离散数学知识奠定坚实的基础，并受惠长远。?学习收获1．掌握命题逻辑和谓词逻辑的体系构造、表达实现和有效推理的方法与技术。 2．掌握二元关系的理论，特别是关系的性质和运算，熟悉典型的二元关系；掌握函数的性质和运算以利于构造其他的数学模型。3．掌握图论的基本知识和解决有关图论问题的基本技能，熟悉各种典型图类性质特征及相关算法的应用技巧、了解应用背景。 4．掌握格和布尔代数的相关知识以及在计算机科学中的应用。5. 掌握形式语言和有限状态自动机的相关知识，为以后学习相关专业课程打下基础。6. 了解代数系统的基本知识。教学方式课堂讲授，每周讲授4学时。教材《离散数学》，冯伟森、栾新成、石兵编（机械工业出版社 2011.2） 参考书目1、《离散数学及其应用》（原书第5版）（Discrete Mathematical and Its Applications），Kenneth.Rosen 著， 袁崇义 屈婉玲 等译 机械工业出版社（2007.6） 2、《离散数学（修订版）》耿素云、屈婉玲高等教育出版社（2004．4）3、《离散数学学习指导与习题解析》耿素云、屈婉玲高等教育出版社 2005．34、《应用离散数学》，方景龙 王毅刚 编著 人民邮电出版社（2005.8）5、《离散数学》——常见题型解析及模拟题，傅彦，西北工业大学出版社 （2004）考试方式笔试成绩评定作业和半期考试、到课情况等综合占30%，期末考试占70%。助教需求每个大班安排1一2名助教负责作业批改和答疑。实验条件需求内容提要第1章? 命题逻辑（12个学时）1．?? 命题、真值、逻辑联结词、合适公式及真值表、重言式、矛盾式、可满足公式。2．?? 命题公式的等价、基本等价式、等价的性质、对偶式、联结词的完备集、命题公式的范式构造。3．?? 命题公式的蕴含、基本蕴含式、蕴含的性质。4．?? 命题逻辑的推理方法、规则、过程、消解原理的应用。第2章?? 一阶谓词逻辑（8个学时）1．个体域、量词、谓词合适公式及其解释。2．谓词公式的等价、基本等价式、前束范式、Skolem范式构造。3．谓词公式的蕴含、基本蕴含式。4．谓词逻辑的推理方法和规则、消解法应用。第3章?? 集合代数集合间的并、交、差、补、对称差等运算，以及幂集、笛卡尔集的构造及相关的证明方法。（该章主要靠学生自学，课堂上只讲述幂集、笛卡尔集的定义，建议放到第4章讲述，因此未单独安排学时）第4章?? 二元关系（4个学时）1.???? 二元关系的定义、以及关系的集合、矩阵和关系图表示。2.???? 二元关系的自反、反自反、对称、反对称、传递等性质。3.???? 关系的并、交、补、复合及逆运算、以及闭包运算。第5章?? 特殊关系（6个学时）1.???? 等价关系、等价类、集合的划分与等价关系。2.???? 偏序关系、偏序集、哈斯图。3. 全序集与良序集、全序关系与拓扑排序。第6章?? 函数（4个学时）1.???? 函数的定义、单射、满射和双射、函数的运算，以及函数的递归定义。2.???? 集合的基数、可数集与不可数集、Cantor定理。第8章基本计数方法（2个学时）1.????容斥原理、鸽巢原理。第10章? 图的基本概念（6个学时）1.???? 无向图与有向图基本概念、图论基本定理、特殊图类、子图和补图、图的同构问题。2.???? 图的道路、回路、连通性问题、连通度定理。3.???? 图的邻接矩阵、关联矩阵、回路矩阵问题。第11章?树及其应用（4个学时）1.???? 树、生成树的概念、最小生成树算法。2.???? 根树、最优树与编码。第12章?平面图及其应用（6个学时）1.???? 平面图、欧拉公式、对偶图问题。2. 平面图的点着色与图的着色第13章? 欧拉图与哈密顿图（6个学时）1.???? 欧拉图及其应用。2.???? 哈密顿图及其应用。第14章? 代数系统（2个学时）1.???? 二元运算及其性质。2.???? 代数系统。第15章 半群与群（2个学时）1. 几个典型代数系统。 2. 同态与同构。第17章格与布尔代数（8个学时）1．?? 格的定义及性质、子格与格同态。2．?? 分配格、有补格、Demorgan律。3．?? 布尔代数。4. 布尔表达式。第18章 应用（10个学时） 1. 串和语