《离散数学》课程教学大纲Word格式文档下载.docx

1、1、掌握命题逻辑和谓词逻辑基本方法、基本理论和基本应用。2、掌握集合运算、关系以及关系运算，理解集合划分和等价关系的联系。3、掌握代数系统的概念。4、掌握图、树相关理论、方法和应用。三、教学学时分配离散数学课程理论教学学时分配表章次主要内容学时分配教学方法或手段第一章命题逻辑的基本概念4讲授法第二章命题逻辑等值演算6第三章命题逻辑的推理理论第四章一阶逻辑的基本概念第五章一阶逻辑等值演算与推理第六章集合第七章二元关系12第八章函数第九章代数系统第十章图的基本概念第十一章欧拉图与哈密顿图第十二章树合计64理论学时包括讨论、习题课等学时。四、教学内容和教学要求第一章 命题逻辑的基本概念 （4学时）（

2、一）教学要求通过本章内容的学习，了解命题和命题公式的基本概念，理解命题公式赋值的意义，掌握命题的判断、逻辑联结词的定义、命题的符号化以及用真值表法判断命题公式的类型。（二）教学重点与难点教学重点：命题的概念及其符号化，逻辑联结词，命题公式的真值表表示教学难点：命题的符号化、命题公式类型的判断（三）教学内容第一节 命题与逻辑联结词1命题的基本概念2逻辑联结词的定义3命题的符号化第二节 命题公式及其赋值1命题公式的基本概念2命题公式的赋值及其类型判断本章习题要点：命题的判断及其符号化，利用真值表判断公式的类型。第二章 命题逻辑等值演算（6学时）通过本章内容的学习，了解等值式的基本概念和常见的联结词

3、完备集，掌握等值式的判断以及利用等值演算法、真值表法将任给公式化为主析取（主合取）范式并判断公式的类型，了解常见的联结词完备集。等值式，等值演算析取范式和合取范式第一节 等值式1等值式的基本概念及其判断2基本等值式和等值演算第二节 析取范式与合取范式1析取范式和主析取范式2合取范式和主合取范式第三节 联结词的完备集1联结词的完备集等值式的证明，求公式的主析取范式和主合取范式，将公式化为仅含给定的联结词的与之等值的公式。第三章 命题逻辑推理理论 （4学时）通过本章内容的学习，了解自然推理系统P的概念，理解推理的形式结构和有效推理的意义，掌握常用的推理规则以及在自然推理系统中构造有效推理的证明。推

4、理的形式结构，自然推理系统推理规则，自然推理系统第一节 推理的形式结构1推理的形式结构和有效推理2推理定律第二节 自然推理系统P1自然推理系统P和推理规则2附加前提证明法和归谬法推理的符号化，在自然推理系统P中构造推理的证明。第四章 一阶逻辑的基本概念（4学时）通过本章内容的学习，了解个体词、谓词、量词、变元、个体域、量词辖域、谓词公式、代换实例等概念，理解一阶逻辑公式的成真解释或成假解释，掌握一阶逻辑命题的符号化。一阶逻辑命题的符号化一阶逻辑命题的符号化，一阶逻辑公式的解释第一节 一阶逻辑命题符号化1个体词、谓词、量词、变元、个体域的基本概念2一阶逻辑命题的符号化第二节 一阶逻辑公式及其解释

5、1谓词公式、量词辖域的概念2谓词公式的解释一阶逻辑命题的符号化，谓词公式的解释，判断谓词公式的类型。第五章 一阶逻辑等值演算与推理（6学时）通过本章内容的学习，了解一阶逻辑等值式的基本概念，理解基本的逻辑等值式的意义，掌握一阶逻辑等值演算方法、一阶逻辑的推理理论以及在自然推理系统中给出有效推理的证明。基本的逻辑等值式，逻辑等值演算方法，一阶逻辑的推理理论一阶逻辑的推理理论第一节 一阶逻辑等值式与置换规则1一阶逻辑等值式与置换规则2一阶逻辑等值演算第二节 一阶逻辑的推理理论1自然推理系统与推理规则一阶逻辑的等值演算，在自然推理下构造推理的证明。第六章 集合（4学时）通过本章内容的学习，了解集合的

6、基本概念及集合的表示法，理解集合的运算及其性质，掌握集合中常见的恒等式以及集合恒等式的证明。集合的运算，有穷集合的计数，集合恒等式有穷集合的计数，集合恒等式第一节 集合的基本概念及其运算1集合的基本概念及其表示2集合的运算第二节 有穷集的计数与集合恒等式1有穷集的计数2集合恒等式集合的运算，集合的计数，集合恒等式的证明。第七章 二元关系 （12学时）通过本章内容的学习，了解关系的基本概念及其表示方法，理解关系的闭包，掌握关系的运算、性质等价关系和集合的划分以及偏序关系。关系的运算和性质，等价关系和划分关系的性质，等价关系和划分第一节 有序对与笛卡尔积1有序对的基本概念2笛卡尔积的基本概念及其性

7、质第二节 二元关系1二元关系的基本概念及其表示第三节 关系的运算1二元关系的运算及其性质第四节 关系的性质1关系的性质及其判定2具有特殊性质的关系经过运算后的性质第五节 关系的闭包1关系的闭包及其性质2关系的闭包的求解第六节 等价关系与划分1等价关系与等价类的概念及性质2等价关系与划分的关系第七节 偏序关系1偏序关系及其哈斯图表示2偏序集中的特殊元素关系的矩阵表示，关系的运算，关系的性质判断，求解关系的闭包，等价关系的判断，偏序关系的判断及哈斯图，寻找偏序关系中的上界、丄确界、下界、下确界、极大元、最大元、极小元、最小元。第八章 函数 （4学时）通过本章内容的学习，掌握函数的基本概念与性质，掌

8、握逆函数和复合函数的基本概念与性质，了解函数作为工具在集合的基数研究中所起的作用。函数的基本概念与性质，逆函数和复合函数的基本概念与性质复合函数的运算第一节 函数的基本概念及其运算1函数的基本概念2函数的复合与反函数第二节 双射函数与集合的基数1双射函数与集合的基数2可数集及其判断判断函数的类型（单射、满射、双射），函数的复合运算，计算集合的基数，判断可数集与不可数集。第九章 代数系统 （4学时）通过本章内容的学习，掌握二元运算的概念和相关性质，掌握代数系统的基本概念和性质，了解代数系统之间的同构关系和同态关系。二元运算，运算律，特异元素代数系统的同态与同构第一节 二元运算及其性质1二元运算2

9、二元运算律及特异元素第二节 代数系统及其同态与同构1代数系统与子代数系统2代数系统的同态与同构判断运算的封闭性，判断运算满足的定律，判断子代数系统，判断代数系统的同态与同构。第十章 图的基本概念 （6学时）通过本章内容的学习，掌握图的基本概念与性质及表示法，了解图中路径、通路和回路的基本概念和应用，掌握图中可达性和连通性的概念和求解方法。图的矩阵表示，图的连通性和可达性图的连通性和可达性判定第一节 图1有向图和无向图的基本概念2子图、生成子图与导出子图3图的同构4图的运算第二节 通路与回路1通路与简单通路2回路与简单回路第三节 图的连通性1无向图的连通性与连通分支2有向图的连通性3二部图及其判

10、断第四节 图的矩阵表示1无向图和有向图的关联矩阵2有向图的邻接矩阵和可达矩阵及应用图的概念及其图形表示，判断正整数列是否可图化，判断图的连通性，求解连通图的边割集和点割集以及边连通度和点连通度，图的矩阵表示及其在寻找通路和回路中的应用，二部图的判断。第十一章 欧拉图与哈密顿图 （4学时）通过本章内容的学习，掌握欧拉图与哈密顿图的基本概念，掌握欧拉图的判定方法。了解哈密顿图的判定方法，掌握哈密顿图的应用。欧拉图的判定，哈密顿图的应用。哈密顿图的判定第一节 欧拉图1欧拉回路和欧拉路径2欧拉图的判断第二节 哈密顿图1哈密顿回路与哈密顿路径2哈密顿的判断寻找欧拉路径和欧拉回路，寻找哈密顿路径和哈密顿回

11、路，欧拉图和哈密顿图的判断。第十二章 树 （6学时）通过本章内容的学习，掌握树的概念及等价定义，了解子树、生成树的概念，掌握根树、二叉树及其应用。树的概念及性质树的等价定义，根树及应用第一节 无向树及其性质1无向树的基本概念2无向树的等价命题第二节 生成树1连通图的生成树2带权图的最小生成树第三节 根树及其应用1根树与最优二叉树2二叉树的周游及应用画出具有给定要求的不同构的树，求连通图的生成树和带权图的最小生成树，求最优二叉树及其周游。五、教学方法或手段教学方法：主要采取讲授法。教学手段：板书，自主学习网站。六、考核方式及评价要求考核方式：课堂考勤、理论课考查、作业、综合测试。1平时成绩占20

12、%，包含课堂考勤、理论课考查和作业；2期末考试占80%，采用综合测试的方式。考核要求：本课程教学应按照大纲要求，注重培养学生系统学习知识的能力，使学生在学习过程中，不仅掌握离散数学基本理论和知识，更注重掌握各章节之间的内在联系，同时加强利用所学知识解决实际问题的能力，从而达到对本课程系统掌握的目的。1掌握数理逻辑,集合论,代数结构和图论的基本概念和原理；2熟练运用数理逻辑、集合论、图论中的理论和方法，分析和解决实际问题；3掌握关系理论、图论中的经典算法及其应用。七、教材及教学主要参考书推荐教材：屈婉玲、耿素云、张立昂主编，离散数学，高等教育出版社，2008年3月第1版，2011年11月第9次印

13、刷。参考书目：1屈婉玲、耿素云、张立昂主编，离散数学题解（修订版），清华大学出版社，2004；2. 左孝凌等主编，离散数学，上海科技文献出版社，2004；3. 夏应龙主编，离散数学同步辅导及习题全解，中国矿业大学出版社，2008；4李盘林等主编，离散数学（第二版），高等教育出版社，2005；5Bernard Kolman, Robert C.Busby, Sharon Cutler Ross. Discrete Mathematical Structures （Fifth Edition）M.Beijing:Higher Education Press,2005。八、说明此部分可做一些补充说明，若无需说明则可省略该项。