离散数学教学大纲屈婉玲

离散数学第二版屈婉玲简介《离散数学第二版》是由屈婉玲编写的离散数学教材。

离散数学是计算机科学中的一门基础课程，主要研究离散对象及其结构、性质和相互关系。

这本教材系统地介绍了离散数学的各个方面，具有循序渐进、清晰易懂的特点，适合计算机科学及相关专业本科生使用。

目录•离散数学概论–离散数学的基本概念–命题逻辑–谓词逻辑与推理–集合与命题逻辑的应用•图论基础–图的基本概念–有向图与无向图–图的遍历–最短路径•关系与函数–二元关系–关系的闭包与等价关系–函数与映射关系–函数的复合与反函数•计数原理–基本计数原理–排列与组合–生成函数–容斥原理•离散数学中的数论–整数与整除性–模运算与同余关系–素数与因子分解–公约数与最大公约数•离散结构中的代数系统–代数系统的基本概念–半群与幺半群–群与子群–环与域内容概述离散数学概论第一章介绍了离散数学的基本概念和离散对象的性质。

包括集合论、命题逻辑和谓词逻辑等内容。

后续讲解了命题逻辑的推理规则，以及如何应用集合论和命题逻辑解决实际问题。

图论基础第二章介绍了图论的基本概念和图的表示方法。

包括有向图和无向图的概念、图的遍历算法和最短路径算法。

通过实例讲解了如何使用图论解决实际问题。

关系与函数第三章介绍了关系与函数的概念和性质。

包括二元关系的定义和性质、关系的闭包和等价关系的概念，以及函数与映射关系的概念和性质。

通过实例讲解了如何使用关系和函数解决实际问题。

计数原理第四章介绍了计数原理的基本概念和计数方法。

包括基本计数原理、排列与组合、生成函数和容斥原理等内容。

通过实例讲解了如何使用计数原理解决实际问题。

离散数学中的数论第五章介绍了离散数学中的数论知识。

包括整数与整除性、模运算与同余关系、素数与因子分解、公约数与最大公约数等内容。

通过实例讲解了如何使用数论知识解决实际问题。

离散结构中的代数系统第六章介绍了离散结构中的代数系统。

包括代数系统的基本概念、半群与幺半群、群与子群、环与域等内容。

《离散数学》教学大纲（Discrete Mathematics）适用专业：电子信息类课程类别：学科基础课课程学时：48课程学分：3.0先修课程：高等数学、线性代数等一、课程简介离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是计算机科学与技术的支撑学科。

它在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能与机器人、数据库、网络、计算机图形学、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握离散结构的描述工具和处理方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

二、教学目的与任务离散数学是一门培养学生缜密思维、严格推理，具有综合归纳分析能力的课程。

通过本课程的学习，使学生有一定的严格逻辑推理与抽象思维能力，掌握离散量的处理及运算技能，能够将离散数学应用到解决计算机技术中的实际问题中。

不仅能为学生奠定计算机科学的专业基础，并且能为将后续课程的学习及将来开发软、硬件技术及研究、应用提供有力的工具。

三、课程内容第1章命题逻辑的基本概念1.1命题与联结词1.2命题公式及其赋值第2章命题逻辑等值演算2.1等值式2.2析取范式与合取范式* 2.3联结词的完备集* 2.4可满足性问题与消解法第3章命题逻辑的推理理论3.1推理的形式结构3.2自然推理系统P3.3消解证明法第4章一阶逻辑基本概念4.1一阶逻辑命题符号化4.2一阶逻辑公式及其解释第5章一阶逻辑等值演算与推理5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式* 5.3一阶逻辑的推理理论第6章集合代数6.1集合的基本概念6.2集合的运算6.3有穷集的计数6.4集合恒等式第7章二元关系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系第8章函数8.1函数的定义与性质8.2函数的复合与反函数* 8.3双射函数与集合的基数* 8.4一个电话系统的描述实例第14章图的基本概念14.1图14.2通路与回路14.3图的连通性14.4图的矩阵表示* 14.5图的运算第15章欧拉图与哈密顿图15.1欧拉图15.2哈密顿图15.3最短路问题、中国邮递员问题与货郎担问题第16章树16.1无向树及其性质16.2生成树16.3根树及其应用三、课程学时分配、教学内容与教学基本要求四、教学方法与教学手段说明该课程教学方式主要有：课堂教学、交互学习、课后作业。

《离散数学B》教学大纲一、课程基本信息1．课程代码：212165022．课程中文名称：离散数学B课程英文名称：Discrete Mathematics B3．面向对象：信工学院软件工程、信息工程、地理信息科学大二学生4．开课学院（课部）、系（中心、室）：信工学院软件工程系5．总学时数：56讲课学时数：56 实验学时数：06．学分数：3.57．授课语种：汉语考试语种：汉语8．教材：屈婉玲、耿素云等编著《离散数学》——普通高等教育“十一五”国家级规划教材，高等教育出版社。

屈婉玲、耿素云等编著《离散数学》（第2版）——21世纪大学本科计算机专业系列教材，清华大学出版社。

二、课程内容简介离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，内容包括数理逻辑、集合论、代数结构（包括群、环、域、格、布尔代数）、图论、初等数论。

三、课程的地位、作用和教学目标离散数学是现代数学的重要分支之一，是计算机科学及相关学科的一门非常重要的专业核心基础课程。

该课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸多领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到分布式系统，无不与离散数学密切相关。

离散数学为数学建模打下知识基础、为算法设计提供具体指导。

离散数学所提供的训练，十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。

教学目标：系统、全面的讲述、分析计算机科学中所用到的研究离散量的各个数学课题，透彻理解并自如运用重要的概念和定理，引导学生进入计算机科学的思维领域，提升学生的数学基本素养、思维底蕴和严谨的逻辑推理能力，从而为计算机专业的学生学习后继课程打下扎实的理论基础，也为他们未来的专业发展提供必要的理论储备。

四、与本课程相联系的其他课程离散数学涉及的数学领域非常广，同时与计算机科学和相关学科关系非常密切，是很多计算机有关课程的基础，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。

精选全文完整版可编辑修改离散数学教学大纲一、教学目标本课程的教学目标是：1．学习和掌握离散型关系结构的构成及分析方法，包括：集合论的主要内容：集合的基本概念、二元关系、函数、自然数和基数等；图论的主要内容：图的基本概念、欧拉图与哈密尔顿图、树、图的矩阵表示、平面图、图的着色、支配集、覆盖集、独立集与匹配、带权图及其应用等；2. 学习和掌握离散型代数结构的构成、性质和分析方法，熟悉半群、群、环、域、格、布尔代数等有着重要应用背景的代数模型；3. 学习和掌握组合配置的存在性证明和计数方法，并用于离散结构的性质分析。

4. 学习和掌握命题逻辑、一阶谓词逻辑的基本概念和推理方法。

5. 能够理论联系实际，用上述离散数学的描述工具和分析方法对实践中的离散系统进行建模和分析。

6. 通过严谨证明及正确逻辑推理的训练，进一步培养学生的抽象思维、计算思维能力和专业素质。

二、教学内容1．集合（教材第一章）●引言●预备知识（命题逻辑）●预备知识（一阶谓词逻辑）●集合的概念和集合之间的关系●集合的运算●基本的集合恒等式2．二元关系（教材第二章）●有序对与卡氏积●二元关系●关系的表示和关系的性质●关系的幂运算和闭包●等价关系和划分●序关系3．函数（教材第三章）●函数的基本概念、性质、合成、反函数4．自然数（教材第四章）●自然数的定义●自然数的性质5．基数（教材第五章）●集合的等势、有穷集合与无穷集合●基数和基数的比较与运算6．图（教材第七章）●图的基本概念●通路与回路●无向图和有向图的连通性●无向图的连通度7．欧拉图与哈密顿图（教材第八章）●欧拉图●哈密顿图8．树（教材第九章）●树9．图的矩阵表示（教材第十章）●图的矩阵表示10．平面图（教材第十一章）●平面图的基本概念●欧拉公式与平面图的判断●平面图的对偶图与外平面图●平面图与哈密顿图11．图的着色（教材第十二章）●点着色和色多项式●平面图着色和边着色12．支配集、覆盖集、独立集与匹配（教材第十三章）●支配集、点覆盖集、点独立集●边覆盖数与匹配●二部图中的匹配13．带权图及其应用（教材第十四章）●中国邮递员问题和货郎问题14. 代数系统（教材第十五章）●二元运算及其性质●代数系统、子代数和积代数●代数系统的同态与同构●同余关系与商代数15. 半群与独异点（教材第十六章）●半群与独异点16 . 群（教材第十七章）●群的定义和性质、子群●循环群、变换群与置换群●群的分解、正规子群与商群、群的同态与同构17. 环与域（教材第十八章）●环与域18. 格与布尔代数（教材第十九章）●格的定义和性质、子格、格同态与直积●模格、分配格、有补格与布尔代数19. 组合存在性定理（教材第二十章）●鸽巢原理和Ramsey定理20. 基本的计数公式（教材第二十一章）●两个计数原则、排列组合●二项式定理与组合恒等式●多项式定理21. 组合计数方法（教材第二十二章）●递推方程的公式解法●递推方程的其他求解方法●生成函数的定义和性质●生成函数、指数生成函数及应用●Catalan数与Stirling数22. 组合计数定理（教材第二十三章）●包含排斥原理与对称筛公式●Burnside引理与Polya定理23. 命题逻辑（教材第二十六章）●引言●命题和联结词●命题形式和真值表●联结词的完全集●推理形式●命题演算自然推理形式系统N●命题演算形式系统P●N与P的等价性●赋值与等值演算●命题范式●可靠性、和谐性与完备性24. 一阶谓词逻辑（教材第二十七章）●一阶谓词演算的符号化●一阶语言●一阶谓词演算形式系统NL●一阶谓词演算形式系统KL●NL与KL的等价性●KL的解释与赋值●KL的可靠性与和谐性●KL的和谐公式集三、教学方式以课堂讲授为主，辅以作业和练习，并配备助教对作业进行批改。

《离散数学》教学大纲一、教学目的离散数学是计算机科学与技术整个一级学科的重要专业基础课，其主要目的在于向学生讲授集合论基础、经典数理逻辑、图论与网络、格与布尔代数、近世代数等离散数学内容。

为学生进一步学习数据结构、编译原理、电路设计等专业课打好数学基础。

离散数学在教给学生离散问题建模、数学理论、计算机求解方法和技术知识的同时,培养学生的数学抽象能力与严密的逻辑推理能力。

离散数学既是一门基础理论课程，又是一门与实际问题紧密相连的课程。

通过本课程学习，将增强学生使用离散数学知识分析问题与解决实际问题的能力。

二、教学要求掌握集合论、数理逻辑、图论、整数、群、环、域、格、布尔代数等离散数学的基本概念和基本原理，为学习计算机专业各后续课程做好必要的知识准备。

并通过这些知识的学习进一步提高学生的抽象思维和逻辑推理能力，为从事计算机相关的理论研究与应用提供必要的描述工具和理论基础。

三、预备知识或先修课程要求高等数学、线性代数四、教学方式多媒体教学，课堂讲解，结合练习或课堂讨论。

五、教学内容及学时分配第一章集合论基础（理论教学20学时）知识点：集合的概念，集合相等和包含关系的定义和性质，常用的集合表示方法，集合的基本运算，关系的相关概念以及关系的性质，关系的乘积，关系的闭包运算，等价关系相关的基本概念，等价关系和划分的内在联系，部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、小确界的定义，有限部分序集的Hasse图，映射、映像、1-1映射等概念，映射的乘积，可数集合的概念及可数集合的判定方法。

1.1 集合的基本概念（6学时）1.2 关系（9学时）1.2.1 关系的基本概念及其性质1.2.2 等价关系1.2.3 偏序关系1.3 映射（5学时）1.3.1 集合的基数1.3.2 可数集合1.3.3 不可数集合第二章计数（理论教学6学时）知识点：加法原理和乘法原理，集合排列数和组合数，多重集合的排列数和组合数，二项式定理及推广，容斥原理及应用，鸽巢原理的简单形式和加强形式及其应用。

《离散数学》课程教学大纲【课程名称】离散数学（Discrete Mathematics)）【课程代码】08012007【适应专业】数学与应用数学【授课对象】普通本科【课程简介】离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。

以研究离散量的结构和相互间的关系为主要目标。

离散数学课程主要介绍命题逻辑等值演算、命题逻辑的推理理论、一阶逻辑的基本概念、一阶逻辑等值演算与推理、集合代数、二元关系、函数、图的基本概念、欧拉图与哈密顿图等内容。

教学原则是注重理论、方法和实例的有机结合，努力使学生对于离散数学课程逐渐形成较为完整的知识体系，对于一些概念、性质、方法有更加深刻的理解，建立正确的形式逻辑和辩证逻辑，提高分析问题、解决问题的能力。

【教学目标】通过离散数学的学习，能够掌握集合的概念、运算及应用，集合内元素间的关系以及集合之间的关系，掌握图论学科的基本理论知识和相关应用，不仅能为学生的专业课学习及将来从事的软、硬件开发打下坚实的基础，同时也能培养他们抽象思维和严格逻辑推理能力。

【参考学时】72学时【参考书目】1．屈婉玲，耿素云编著：《离散数学》，北京，高等教育出版社，2008年2．左孝凌等编著：《离散数学》，上海，上海科技文献出版社，2003年3．蔡英编著：《离散数学》，西安，西安电子科技大学出版社，2007年4．王元元编著：《离散数学导论》，北京，科学出版社，2005年【教学内容】●第一单元命题逻辑的基本概念●§1 命题与联结词§2 命题公式及其赋值●基本要求：1．深刻理解5种常用联结词的涵义，并能准确地应用它们将基本复合命题及复合命题符号化；2．分清“相容或”与“排斥或”；3．深刻理解命题公式的赋值、成真赋值、成假赋值，从而准确地判断出公式的类型。

●重点、难点：蕴涵联结词与析取联结词；真值表。

●教学方法提示：讲授法●参考学时：4学时●第二单元命题逻辑的等值演算●§1 等值式§2 析取范式与合取范式§3 联结词的完备集●基本要求：1．深刻理解等值式的定义；2．熟练应用基本等值式及置换规则进行等值演算；3．深刻理解极小项、极大项的定义，名称、下角标与成真赋值的关系，会求主析取范式与主合取范式。