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

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

《《离散数学》课程教学大纲Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《《离散数学》课程教学大纲Word格式文档下载.docx（11页珍藏版）》请在冰点文库上搜索。

1、掌握命题逻辑和谓词逻辑基本方法、基本理论和基本应用。

2、掌握集合运算、关系以及关系运算，理解集合划分和等价关系的联系。

3、掌握代数系统的概念。

4、掌握图、树相关理论、方法和应用。

三、教学学时分配

《离散数学》课程理论教学学时分配表

章次

主要内容

学时分配

教学方法或手段

第一章

命题逻辑的基本概念

4

讲授法

第二章

命题逻辑等值演算

6

第三章

命题逻辑的推理理论

第四章

一阶逻辑的基本概念

第五章

一阶逻辑等值演算与推理

第六章

集合

第七章

二元关系

12

第八章

函数

第九章

代数系统

第十章

图的基本概念

第十一章

欧拉图与哈密顿图

第十二章

树

合计

64

＊理论学时包括讨论、习题课等学时。

四、教学内容和教学要求

第一章命题逻辑的基本概念（4学时）

（一）教学要求

通过本章内容的学习，了解命题和命题公式的基本概念，理解命题公式赋值的意义，掌握命题的判断、逻辑联结词的定义、命题的符号化以及用真值表法判断命题公式的类型。

（二）教学重点与难点

教学重点：

命题的概念及其符号化，逻辑联结词，命题公式的真值表表示

教学难点：

命题的符号化、命题公式类型的判断

（三）教学内容

第一节命题与逻辑联结词

1．命题的基本概念

2．逻辑联结词的定义

3．命题的符号化

第二节命题公式及其赋值

1．命题公式的基本概念

2．命题公式的赋值及其类型判断

本章习题要点：

命题的判断及其符号化，利用真值表判断公式的类型。

第二章命题逻辑等值演算（6学时）

通过本章内容的学习，了解等值式的基本概念和常见的联结词完备集，掌握等值式的判断以及利用等值演算法、真值表法将任给公式化为主析取（主合取）范式并判断公式的类型，了解常见的联结词完备集。

等值式，等值演算

析取范式和合取范式

第一节等值式

1．等值式的基本概念及其判断

2．基本等值式和等值演算

第二节析取范式与合取范式

1．析取范式和主析取范式

2．合取范式和主合取范式

第三节联结词的完备集

1．联结词的完备集

等值式的证明，求公式的主析取范式和主合取范式，将公式化为仅含给定的联结词的与之等值的公式。

第三章命题逻辑推理理论（4学时）

通过本章内容的学习，了解自然推理系统P的概念，理解推理的形式结构和有效推理的意义，掌握常用的推理规则以及在自然推理系统中构造有效推理的证明。

推理的形式结构，自然推理系统

推理规则，自然推理系统

第一节推理的形式结构

1．推理的形式结构和有效推理

2．推理定律

第二节自然推理系统P

1．自然推理系统P和推理规则

2．附加前提证明法和归谬法

推理的符号化，在自然推理系统P中构造推理的证明。

第四章一阶逻辑的基本概念（4学时）

通过本章内容的学习，了解个体词、谓词、量词、变元、个体域、量词辖域、谓词公式、代换实例等概念，理解一阶逻辑公式的成真解释或成假解释，掌握一阶逻辑命题的符号化。

一阶逻辑命题的符号化

一阶逻辑命题的符号化，一阶逻辑公式的解释

第一节一阶逻辑命题符号化

1．个体词、谓词、量词、变元、个体域的基本概念

2．一阶逻辑命题的符号化

第二节一阶逻辑公式及其解释

1．谓词公式、量词辖域的概念

2．谓词公式的解释

一阶逻辑命题的符号化，谓词公式的解释，判断谓词公式的类型。

第五章一阶逻辑等值演算与推理（6学时）

通过本章内容的学习，了解一阶逻辑等值式的基本概念，理解基本的逻辑等值式的意义，掌握一阶逻辑等值演算方法、一阶逻辑的推理理论以及在自然推理系统中给出有效推理的证明。

基本的逻辑等值式，逻辑等值演算方法，一阶逻辑的推理理论

一阶逻辑的推理理论

第一节一阶逻辑等值式与置换规则

1．一阶逻辑等值式与置换规则

2．一阶逻辑等值演算

第二节一阶逻辑的推理理论

1．自然推理系统与推理规则

一阶逻辑的等值演算，在自然推理下构造推理的证明。

第六章集合（4学时）

通过本章内容的学习，了解集合的基本概念及集合的表示法，理解集合的运算及其性质，掌握集合中常见的恒等式以及集合恒等式的证明。

集合的运算，有穷集合的计数，集合恒等式

有穷集合的计数，集合恒等式

第一节集合的基本概念及其运算

1．集合的基本概念及其表示

2．集合的运算

第二节有穷集的计数与集合恒等式

1．有穷集的计数

2．集合恒等式

集合的运算，集合的计数，集合恒等式的证明。

第七章二元关系（12学时）

通过本章内容的学习，了解关系的基本概念及其表示方法，理解关系的闭包，掌握关系的运算、性质等价关系和集合的划分以及偏序关系。

关系的运算和性质，等价关系和划分

关系的性质，等价关系和划分

第一节有序对与笛卡尔积

1．有序对的基本概念

2．笛卡尔积的基本概念及其性质

第二节二元关系

1．二元关系的基本概念及其表示

第三节关系的运算

1．二元关系的运算及其性质

第四节关系的性质

1．关系的性质及其判定

2．具有特殊性质的关系经过运算后的性质

第五节关系的闭包

1．关系的闭包及其性质

2．关系的闭包的求解

第六节等价关系与划分

1．等价关系与等价类的概念及性质

2．等价关系与划分的关系

第七节偏序关系

1．偏序关系及其哈斯图表示

2．偏序集中的特殊元素

关系的矩阵表示，关系的运算，关系的性质判断，求解关系的闭包，等价关系的判断，偏序关系的判断及哈斯图，寻找偏序关系中的上界、丄确界、下界、下确界、极大元、最大元、极小元、最小元。

第八章函数（4学时）

通过本章内容的学习，掌握函数的基本概念与性质，掌握逆函数和复合函数的基本概念与性质，了解函数作为工具在集合的基数研究中所起的作用。

函数的基本概念与性质，逆函数和复合函数的基本概念与性质

复合函数的运算

第一节函数的基本概念及其运算

1．函数的基本概念

2．函数的复合与反函数

第二节双射函数与集合的基数

1．双射函数与集合的基数

2．可数集及其判断

判断函数的类型（单射、满射、双射），函数的复合运算，计算集合的基数，判断可数集与不可数集。

第九章代数系统（4学时）

通过本章内容的学习，掌握二元运算的概念和相关性质，掌握代数系统的基本概念和性质，了解代数系统之间的同构关系和同态关系。

二元运算，运算律，特异元素

代数系统的同态与同构

第一节二元运算及其性质

1．二元运算

2．二元运算律及特异元素

第二节代数系统及其同态与同构

1．代数系统与子代数系统

2．代数系统的同态与同构

判断运算的封闭性，判断运算满足的定律，判断子代数系统，判断代数系统的同态与同构。

第十章图的基本概念（6学时）

通过本章内容的学习，掌握图的基本概念与性质及表示法，了解图中路径、通路和回路的基本概念和应用，掌握图中可达性和连通性的概念和求解方法。

图的矩阵表示，图的连通性和可达性

图的连通性和可达性判定

第一节图

1．有向图和无向图的基本概念

2．子图、生成子图与导出子图

3．图的同构

4．图的运算

第二节通路与回路

1．通路与简单通路

2．回路与简单回路

第三节图的连通性

1．无向图的连通性与连通分支

2．有向图的连通性

3．二部图及其判断

第四节图的矩阵表示

1．无向图和有向图的关联矩阵

2．有向图的邻接矩阵和可达矩阵及应用

图的概念及其图形表示，判断正整数列是否可图化，判断图的连通性，求解连通图的边割集和点割集以及边连通度和点连通度，图的矩阵表示及其在寻找通路和回路中的应用，二部图的判断。

第十一章欧拉图与哈密顿图（4学时）

通过本章内容的学习，掌握欧拉图与哈密顿图的基本概念，掌握欧拉图的判定方法。

了解哈密顿图的判定方法，掌握哈密顿图的应用。

欧拉图的判定，哈密顿图的应用。

哈密顿图的判定

第一节欧拉图

1．欧拉回路和欧拉路径

2．欧拉图的判断

第二节哈密顿图

1．哈密顿回路与哈密顿路径

2．哈密顿的判断

寻找欧拉路径和欧拉回路，寻找哈密顿路径和哈密顿回路，欧拉图和哈密顿图的判断。

第十二章树（6学时）

通过本章内容的学习，掌握树的概念及等价定义，了解子树、生成树的概念，掌握根树、二叉树及其应用。

树的概念及性质

树的等价定义，根树及应用

第一节无向树及其性质

1．无向树的基本概念

2．无向树的等价命题

第二节生成树

1．连通图的生成树

2．带权图的最小生成树

第三节根树及其应用

1．根树与最优二叉树

2．二叉树的周游及应用

画出具有给定要求的不同构的树，求连通图的生成树和带权图的最小生成树，求最优二叉树及其周游。

五、教学方法或手段

教学方法：

主要采取讲授法。

教学手段：

板书，自主学习网站。

六、考核方式及评价要求

考核方式：

课堂考勤、理论课考查、作业、综合测试。

1．平时成绩占20%，包含课堂考勤、理论课考查和作业；

2．期末考试占80%，采用综合测试的方式。

考核要求：

本课程教学应按照大纲要求，注重培养学生系统学习知识的能力，使学生在学习过程中，不仅掌握离散数学基本理论和知识，更注重掌握各章节之间的内在联系，同时加强利用所学知识解决实际问题的能力，从而达到对本课程系统掌握的目的。

1．掌握数理逻辑,集合论,代数结构和图论的基本概念和原理；

2．熟练运用数理逻辑、集合论、图论中的理论和方法，分析和解决实际问题；

3．掌握关系理论、图论中的经典算法及其应用。

七、教材及教学主要参考书

推荐教材：

屈婉玲、耿素云、张立昂主编，《离散数学》，高等教育出版社，2008年3月第1版，2011年11月第9次印刷。

参考书目：

1．屈婉玲、耿素云、张立昂主编，《离散数学题解》（修订版），清华大学出版社，2004；

2.左孝凌等主编，《离散数学》，上海科技文献出版社，2004；

3.夏应龙主编，《离散数学同步辅导及习题全解》，中国矿业大学出版社，2008；

4．李盘林等主编，《离散数学》（第二版），高等教育出版社，2005；

5．BernardKolman,RobertC.Busby,SharonCutlerRoss.DiscreteMathematicalStructures（FifthEdition）[M].Beijing:

HigherEducationPress,2005。

八、说明

此部分可做一些补充说明，若无需说明则可省略该项。