《离散数学》课程教学大纲课程类别：专业基础课适用专业：计算机应用技术适用层次：高起专适用教育形式：成人教育考核形式：考试所属学院：计算机科学与技术学院先修课程：无一、课程简介《离散数学》是计算机应用技术专业的一门基础必修课程，主要研究离散量的结构及其相互关系，是现代数学的一个重要分支。
它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时也是计算机专业的许多专业课程必不可少的先行课程。
二、课程学习目标通过本课程的学习，学生具备以下能力（应达到）：1. 理解命题和命题联接词、谓词和量词、命题公式和谓词公式、自由变元和约束变元等概念，记住常见等值式和推理定律，会求命题公式的主范式，能进行命题逻辑和谓词逻辑的符号化、推理和证明。
2. 理解集合、关系、偏序关系、等价关系和划分等概念，能选择合适方法描述集合和关系，能计算集合的幂集和笛卡尔积、二元关系的合成、闭包、偏序关系的特殊元素，会判定二元关系的性质，能绘制哈斯图。
3. 理解图论的基本概念，会判定特殊图的类型；能根据图的矩阵计算得出相应结论，会判别欧拉图、哈密顿图等特殊图的类型。
三、与其他课程的关系本课程是计算机专业许多专业课程，如数据结构、算法分析、数据库原理、编译原理等的先行课程。
四、课程主要内容和基本要求离散数学是研究离散量的结构和相互关系的一门理论学科，主要包括数理逻辑、集合论、代数系统和图论四大部分内容。
集合论是离散数学的基础，主要研究数学中学科分支的关注对象与研究内容的一般性规律，涉及集合的基本概念与运算、关系及性质、函数等内容。
数理逻辑以形式逻辑为研究目标，以形式化推理为其研究内容，包括命题逻辑和谓词逻辑两部分内容。
代数系统以抽象运算为研究目标，以满足某些运算规则组成的系统为研究内容，涉及群、环、域等不同的代数系统，系统之间的同态与同构，格与布尔代数等内容。
图论以离散对象上的二元关系为其研究目标，以抽象世界中事物的结构为其研究内容，涉及图的基本概念及应用等内容。
由于离散数学的内容非常丰富，结合专业发展的要求以及不同层次、不同分类学生的需要，我们从中选择部分内容作为离散数学课程的学习内容。
第一单元命题逻辑『知识点』记住命题联结词真值表（否定、合取、析取、蕴涵、等价）；理解命题、命题公式、（主）范式等概念；命题逻辑符号化；等值式的理解记忆及等值演算；主析取范式与主合取范式求取；主析取范式与主合取范式的转换；命题逻辑的推理与证明。
『基本要求』1. 识记：记住命题联结词真值表（否定、合取、析取、蕴涵、等价）、等值式、和相关推理定律。
2. 领会：理解命题、命题联结词、命题公式、（主）范式等概念。
3. 简单应用：对自然语言进行命题符号化；能运用等值式进行等值演算；会通过恒等变形求取命题公式的主析取范式与主合取范式。
4. 综合应用：运用命题逻辑相关知识进行推理和证明。
『关键知识』1.命题符号化及联结词命题与真值；简单命题与复合命题；常用联结词（否定、合取、析取、蕴含、等价）；命题符号化2.命题公式及分类公式的赋值或解释；真值表；真值表判断公式的类型3.公式的等值演算等值公式的理解和记忆；等值演算证明；等值演算判断公式类型4.范式简单合取式与简单析取式；合取范式与析取范式的概念；极小项与主析取范式求法；极大项与主合取范式求法；主合取范式与主析取范式的命题公式互化5.推理理论推理的形式结构；推理定律和推理规则的理解和证明；推理的构造证明方法。
『重点』命题逻辑符号化；等值式的理解记忆及等值演算；主析取范式与主合取范式的求取；主析取范式与主合取范式的转换；命题逻辑的推理与证明。
『难点』主析取范式与主合取范式的求取；主析取范式与主合取范式的转换；命题逻辑的推理与证明。
第二单元一阶逻辑『知识点』理解一阶逻辑的基本概念；一阶逻辑符号化；理解记忆一阶逻辑等值式；一阶逻辑的等值演算；理解前束范式的概念；理解并记忆量词的消去、引入规则；一阶逻辑推理及证明。
『基本要求』1. 识记：熟练记住一阶逻辑等值式、量词的消去和引入规则。
2. 领会：理解一阶逻辑基本概念、前束范式的概念、一阶逻辑的等值演算、量词的消去和引入规则。
3. 简单应用：自然语言的一阶逻辑符号化；4. 综合应用：能运用一阶逻辑相关知识进行推理和证明。
『关键知识』1.一阶逻辑基本概念个体词与谓词；全称量词与存在量词；全总课题域与特性谓词；一阶逻辑符号化2.一阶逻辑合式公式及解释原子公式与合式公式；量词的辖域；约束变元与自由变元；公式的解释；公式的类型及其判断；换名规则3.一阶逻辑等值式与等值演算等值式的理解与记忆；一阶逻辑的等值演算；前束范式的概念。
『重点』一阶逻辑符号化；一阶逻辑的等值演算、量词的消去、引入规则；一阶逻辑推理及证明。
『难点』一阶逻辑符号化；一阶逻辑的等值演算、量词的消去、引入规则。
第三单元集合与二元关系『知识点』理解集合和二元关系的基本概念和形式化描述；集合和关系的运算；判定关系的性质；等价关系的判定、等价关系与划分相互的诱导关系；偏序关系的判定、哈斯图的绘制，特殊元素的求取。
『基本要求』1. 识记：集合的基本概念与基本运算。
2. 领会：理解集合和二元关系的基本概念和形式化描述；能判定某个关系是否是偏序关系和等价关系。
3. 简单应用：判定关系的性质；会集合基本运算；计算关系的逆运算、合成运算、幂运算和闭包运算；根据集合上等价关系与集合划分的对应关系进行相互转换；绘制偏序关系的哈斯图，求偏序关系的特殊元素。
『关键知识』1.集合的基本概念集合的表示、集合与元素；子集与真子集；空集；幂集与全集。
集合相关的形式化描述。
2.集合的基本运算集合的基本运算；集合运算的运算律。
3.笛卡尔积与二元关系序偶、有序n元组与笛卡尔积的概念；笛卡尔积的性质；二元关系；关系的表示（集合表示法、关系矩阵、关系图）关系的特性4.关系的运算关系的逆运算；关系的的合成；关系的幂运算；关系运算的矩阵表示（补充）。
5.关系的性质自反性、反自反性、对称性、反对称性的判定（包括在关系图和关系矩阵上的体现）。
6.关系的闭包自反闭包、对称闭包、传递闭包7.偏序关系偏序关系；哈斯图；特殊元素。
『重点』集合和二元关系的形式化描述；关系的性质判定；关系的运算；等价关系与划分相互的诱导关系；偏序关系的判定、哈斯图的绘制，特殊元素的求取。
『难点』关系的性质判定；等价关系与划分相互的诱导关系；偏序关系的特殊元素求取。
第四单元图论『知识点』理解图的基本概念；理解通路、回路和图的连通性等概念；判断两个图是否同构；能对图进行矩阵表示；二部图、欧拉图、哈密尔顿图、平面图的判定，能对欧拉图和平面图的简单应用问题建立图模型，并分析解决问题。
『基本要求』1. 识记：图的基本概念2. 领会：理解图的基本概念；理解通路、回路和图的连通性等概念；判断图的连通性；判断两个图是否同构；判断图是否是欧拉图、哈密尔顿图、二部图和平面图。
3. 简单应用：对图进行矩阵表示；根据度数序列进行图的合法性判定和计算。
4. 综合应用：能对简单应用问题（边的遍历问题、着色问题等）建立图模型，并运用相关图论知识（欧拉图、平面图等）分析解决问题。
『关键知识』1.无向图及有向图图的基本概念；无向图和有向图；顶点的度数与握手定理；子图与补图；图的同构2.图的连通性通路与回路；连通与可达；有向图的连通性3.图的矩阵表示无向图的关联矩阵；有向图的关联矩阵；有向图的邻接矩阵；邻接矩阵的性质；有向图的可达矩阵4.欧拉图欧拉图及判定条件；欧拉图的应用；5.哈密尔顿图哈密尔顿图及必要条件；『重点』图的矩阵表示；对欧拉图和平面图的简单应用问题建立图模型，并分析解决问题。
『难点』对欧拉图和平面图的简单应用问题建立图模型，并分析解决问题。
五、课程学习的方法及特点1. 本课程是一门兼具应用性和严密理论性的学科基础课，概念抽象，推理严密，因此教学过程中宜采用理论讲授与例题分析相结合的方法，并引入离散数学在软件工程技术中的应用案例，从实例中让学生了解离散数学知识在软件工程中的具体应用，体会严密推理在软件工程技术中的必要性和重要性。
2. 本课程概念多，理论性强，学生必须通过多做习题来加深对概念的理解和掌握，才能熟悉公式定理的运用，达到消化、掌握课堂内容的目的。
课后应布置一定数量习题，根据教学情况适当安排习题课并进行课程辅导答疑。
3. 在教学中宜根据具体情况引入问题探究式教学方法，拓展学生思维，引导学生积极思考和分析问题，培养学生独立解决问题的能力，注重学生对离散数学在软件工程专业的重要性和整体性理解。
六、课程学习材料1、课程基本教材《离散数学（第五版）》，耿素云、屈婉玲、张立昂，清华大学出版社，2013年7月2、课程主要辅导材料（1）《离散数学题解（第五版）》，屈婉玲、耿素云、张立昂主编，清华大学出版，2013年（2）西南科技大学继续教育网（）的学习平台3、参考资料（1）《离散数学与组合数学（第5版）》，Ralph P.Grimaldi，2007年5月（2）《离散数学（第三版）》，方世昌，西安电子科技大学出版社，2009年1月（3）《离散数学（修订版）》，耿素云、屈婉玲，高等教育出版社，2004年4月（4）《离散数学学习指导与习题解析》，耿素云、屈婉玲，高等教育出版社，2005年3月（5）《离散数学—常见题型解析及模拟题》，傅彦，西北工业大学出版社，2004年8月七、课程结构导航与学习建议八、考核要求、方式与成绩评定考核要求：教材中教学大纲所要求掌握的内容。
考核方式：笔试。
成绩评定：选用百分制模式，平时考查与期末考试相结合。
