《离散数学》课程教学大纲 课程编号：06082002 适用专业：计算机科学与技术 学时数：60 学分数：4 开课学期：第2学期 先修课程：线性代数、高级语言程序设计(C语言) 执笔者：傅彦、顾小丰、刘启和、王庆先、王丽杰 编写日期：2011.03 审核人（教学副院长）：周世杰 一、课程性质和目标（用小四号黑体字） 授课对象：本科生 课程类别：学科基础课 教学目标（本课程对实现培养目标的作用：学生通过学习该课程后，在思想、知识、能力和素 质等方面应达到的目标)：离散数学是一门理论兼实际应用的综合性学科，即具有严备的理论基础， 又具备应用科学的特点。它是计算机科学和其他应用科学的基础理论课。在课堂教学中，不仅要求 学生掌握离散数学具体内容，更重要的是强调离散数学课程的思想，特别是离散数学中逻辑的概念 可以说是贯穿到整个教学中：通过课后实验，学生不仅能够加深对离散数学知识的进一步理解，而 且还可以从实验中提高自己的实践动手能力和编程能力，最关键的是提高学生学习离散数学的兴趣 和了解离散数学与其他课程之间的关系。通过本课程学习，培养和训练学生的抽象思维能力和严格 的逻辑推理的能力，使学生了解离散数学在计算机学科和日常生活中的作用，为学生今后处理离散 信息以及用计算机处理大量的日常事物和科研项目，从事计算机科学和应用打下坚实基础，特别是 对那些从事计算机科学与理论研究的高层次计算机人员来说，更是一门必不可少的基础理论工具。 二、课程内容安排和要求（用小四号黑体字） (一)教学内容、要求及教学方法（用五号宋体加粗） 第1章集合论2学时 掌握：集合的基本概念（集合的概念及表示、集合与元素的关系、集合与集合的关系、几个特 殊的集合)、集合的运算。 理解：集合的应用。 了解：粗糙集简介（粗糙集合研究现状、知识与知识库、粗糙集的基本概念、成员关系，粗相 等和粗包含)（本部分自学）。 教学方法：问题十实例的讲授式教学方法 第2章计数问题2学时 理解：基本原理（乘法原理、加法原理）、排列与组合（排列问题、组合问题）、容斥原理与鸽 笼原理 了解：递归关系、离散概率简介、计数问题的应用。 教学方法：问题十实例的讲授式教学方法 第3章命题逻辑8学时 掌握：命题与命题联结词、命题公式、解释、真值表、命题公式的分类、命题公式的基本等价 关系、公式的标准型一一范式（析取范式和合取范式、主析取范式和主合取范式）
《离散数学》课程教学大纲 课程编号：06082002 适用专业：计算机科学与技术 学 时 数：60 学 分 数：4 开课学期：第 2 学期 先修课程：线性代数、高级语言程序设计(C 语言) 执 笔 者：傅彦、顾小丰、刘启和、王庆先、王丽杰 编写日期：2011.03 审核人（教学副院长）：周世杰 一、课程性质和目标（用小四号黑体字） 授课对象：本科生 课程类别：学科基础课 教学目标（本课程对实现培养目标的作用；学生通过学习该课程后，在思想、知识、能力和素 质等方面应达到的目标）：离散数学是一门理论兼实际应用的综合性学科，即具有严备的理论基础， 又具备应用科学的特点。它是计算机科学和其他应用科学的基础理论课。在课堂教学中，不仅要求 学生掌握离散数学具体内容，更重要的是强调离散数学课程的思想，特别是离散数学中逻辑的概念 可以说是贯穿到整个教学中；通过课后实验，学生不仅能够加深对离散数学知识的进一步理解，而 且还可以从实验中提高自己的实践动手能力和编程能力，最关键的是提高学生学习离散数学的兴趣 和了解离散数学与其他课程之间的关系。通过本课程学习，培养和训练学生的抽象思维能力和严格 的逻辑推理的能力，使学生了解离散数学在计算机学科和日常生活中的作用，为学生今后处理离散 信息以及用计算机处理大量的日常事物和科研项目，从事计算机科学和应用打下坚实基础，特别是 对那些从事计算机科学与理论研究的高层次计算机人员来说，更是一门必不可少的基础理论工具。 二、课程内容安排和要求（用小四号黑体字） （一）教学内容、要求及教学方法（用五号宋体加粗） 第 1 章 集合论 2 学时 掌握：集合的基本概念（集合的概念及表示、集合与元素的关系、集合与集合的关系、几个特 殊的集合）、集合的运算。 理解：集合的应用。 了解：粗糙集简介（粗糙集合研究现状、知识与知识库、粗糙集的基本概念、成员关系，粗相 等和粗包含）（本部分自学）。 教学方法：问题＋实例的讲授式教学方法 第 2 章 计数问题 2 学时 理解：基本原理（乘法原理、加法原理）、排列与组合（排列问题、组合问题）、容斥原理与鸽 笼原理 了解：递归关系、离散概率简介、计数问题的应用。 教学方法：问题＋实例的讲授式教学方法 第 3 章 命题逻辑 8 学时 掌握：命题与命题联结词、命题公式、解释、真值表、命题公式的分类、命题公式的基本等价 关系、公式的标准型——范式（析取范式和合取范式、主析取范式和主合取范式）
理解：命题联结词的应用、命题公式的应用、命题联结词的个数、联结词的完备集。 了解：范式的应用、全功能联结词的应用 教学方法：讲授为主的引导式教学方法，帮助学生建立命题逻辑的基本概念，通过例题掌握正 确解决问题的方法，并初步学习使用命题逻辑的方法建立符号体系。 第4章谓词逻辑4学时 掌握：谓词逻辑的基本概念与表示（谓词、量词、谓词的语言翻译）、谓词的合式公式、自由 变元与约束变元、谓词合式公式的解释、谓词合式公式的分类、谓词合式公式的基本等价关系。 了解：公式的标准型一一范式（前束范式、SKOLEM标准型)、谓词的应用 教学方法：讲授为主的启发式的教学方法，引导学生通过回顾第三章的学习过程，掌握学习数 理逻辑的基本方法，逐步从以前的被动学习向主动学习转换。以学生课前预习，课堂讨论为主的教 学方法，激发学生的主动性和参与性，进一步扩展学生的主动思维习惯。 第5章推理与证明技术4学时 掌握：命题逻辑的推理理论（推理的基本概念和推理形式、判断有效结论的常用方法）、谓词 逻辑的推理理论（谓词逻辑的推理规则、谓词逻辑推理的常用方法）。 了解：数学归纳法、按定义证明方法。 教学方法：讲授为主的启发式的教学方法，引导学生通过回顾以往数学问题的证明过程，掌握 学习数理逻辑的符号证明体系，特别注重证明过程的正确性。以学生课前预习，课堂讨论为主的教 学方法，激发学生的主动性和参与性，进一步扩展学生的主动思维习惯。 第6章二元关系6学时 掌握：二元关系及其表示法（关系的定义、关系的表示法）、关系的运算（关系的复合运算、 逆运算、幂运算等)、关系的性质（关系性质的定义、关系性质的证明、关系性质的保守性 了解：关系的应用、关系运算的应用、关系性质的应用、关系的闭包运算、关系闭包的应用。 教学方法：讲授为主的启发式的教学方法。 第7章特殊关系4学时 掌握：等价关系与划分（等价关系、等价类与商集、集合的划分、等价关系与划分）、次序关 系（拟序关系、偏序关系、全序关系、良序关系）。 理解：等价关系与划分的应用、次序关系的应用。 教学方法：讲授为主的启发式的教学方法。 第8章函数2学时 掌握：函数函数与性质、函数的运算（复合运算、逆运算）。 了解：置换函数、函数的应用。 教学方法：引导学生采取自我提问方式独立看书预习，仍然以先师生共同课堂讨论，然后老师 总结的主要内容和讨论的重要问题的方法。 第9章图6学时 掌握：图的基本概念（图的定义、图的表示、邻接点与邻接边、图的分类、子图与补图、结点 的度数与握手定理、图的同构、图的操作)、通路、回路与连通性（通路与回路、无向图的连通性、 有向图的连通性)。 了解：图的应用、通路、回路与连通性的应用。 教学方法：讲授为主的启发式的教学方法。 第10章树2学时 掌握：无向树（无向树的定义与性质、生成树、最小生成树）、根树（根树的定义与分类、最 优树与哈夫曼算法)。 理解：无向树的应用、根树的遍历、决策树、博弈树、根树的应用。 教学方法：讲授为主的启发式的教学方法。 第11章特殊图4学时
理解：命题联结词的应用、命题公式的应用、命题联结词的个数、联结词的完备集。 了解：范式的应用、全功能联结词的应用 教学方法：讲授为主的引导式教学方法，帮助学生建立命题逻辑的基本概念，通过例题掌握正 确解决问题的方法，并初步学习使用命题逻辑的方法建立符号体系。 第 4 章 谓词逻辑 4 学时 掌握：谓词逻辑的基本概念与表示（谓词、量词、谓词的语言翻译）、谓词的合式公式、 自由 变元与约束变元、谓词合式公式的解释、谓词合式公式的分类、谓词合式公式的基本等价关系。 了解：公式的标准型——范式（前束范式、SKOLEM 标准型）、谓词的应用 教学方法：讲授为主的启发式的教学方法，引导学生通过回顾第三章的学习过程，掌握学习数 理逻辑的基本方法，逐步从以前的被动学习向主动学习转换。以学生课前预习，课堂讨论为主的教 学方法，激发学生的主动性和参与性，进一步扩展学生的主动思维习惯。 第 5 章 推理与证明技术 4 学时 掌握：命题逻辑的推理理论（推理的基本概念和推理形式、判断有效结论的常用方法）、谓词 逻辑的推理理论（谓词逻辑的推理规则、谓词逻辑推理的常用方法）。 了解：数学归纳法、按定义证明方法。 教学方法：讲授为主的启发式的教学方法，引导学生通过回顾以往数学问题的证明过程，掌握 学习数理逻辑的符号证明体系，特别注重证明过程的正确性。以学生课前预习，课堂讨论为主的教 学方法，激发学生的主动性和参与性，进一步扩展学生的主动思维习惯。 第 6 章 二元关系 6 学时 掌握：二元关系及其表示法（关系的定义、关系的表示法）、关系的运算（关系的复合运算、 逆运算、幂运算等）、关系的性质（关系性质的定义、关系性质的证明、关系性质的保守性 了解：关系的应用、关系运算的应用、关系性质的应用、关系的闭包运算、关系闭包的应用。 教学方法：讲授为主的启发式的教学方法。 第 7 章 特殊关系 4 学时 掌握：等价关系与划分（等价关系、等价类与商集、集合的划分、等价关系与划分）、次序关 系（拟序关系、偏序关系、全序关系、良序关系）。 理解：等价关系与划分的应用、次序关系的应用。 教学方法：讲授为主的启发式的教学方法。 第 8 章 函数 2 学时 掌握：函数函数与性质、函数的运算（复合运算、逆运算）。 了解：置换函数、函数的应用。 教学方法：引导学生采取自我提问方式独立看书预习，仍然以先师生共同课堂讨论，然后老师 总结的主要内容和讨论的重要问题的方法。 第 9 章 图 6 学时 掌握：图的基本概念（图的定义、图的表示、邻接点与邻接边、图的分类、子图与补图、结点 的度数与握手定理、图的同构、图的操作）、通路、回路与连通性（通路与回路、无向图的连通性、 有向图的连通性）。 了解：图的应用、通路、回路与连通性的应用。 教学方法：讲授为主的启发式的教学方法。 第 10 章 树 2 学时 掌握：无向树（无向树的定义与性质、生成树、最小生成树）、根树（根树的定义与分类、最 优树与哈夫曼算法）。 理解：无向树的应用、根树的遍历、决策树、博弈树、根树的应用。 教学方法：讲授为主的启发式的教学方法。 第 11 章 特殊图 4 学时
掌握：欧拉图、哈密顿图、偶图、平面图（定义、判定方法、欧拉公式、库拉托夫斯基定理）。 理解：欧拉图的应用、哈密顿图的应用、偶图的应用、平面图的着色、平面图的应用。 教学方法：讲授为主的启发式的教学方法。 第12章代数系统3学时 掌握：代数系统（代数运算、代数系统、子代数）、代数系统的基本运算和性质（代数运算的 性质：交换律、结合律、分配律、幂等律、吸收律、消去律：代数系统中的特殊元素：单位元、零 元、逆元、幂等元)、同态和同构。 理解：代数系统的应用、代数系统性质的应用、同态与同构的应用。 教学方法：讲授为主的启发式的教学方法。 第13章群7学时 掌握：半群与含幺半群（半群和含幺半群、子半群和子含幺半群、循环半群与循环含么半群的 概念、性质与判断)、群及其性质（群的定义、元素的周期、子群及其判定条件、群同态与同构)、 特殊群（交换群、循环群）、陪集与拉格朗日定理、不变子群与商群 理解：半群的应用、群的应用、特殊群的应用、拉格朗日定理的应用。 了解：置换群、商群、商群的应用。 教学方法：讲授为主的启发式的教学方法。 第15章格与布尔代数6学时 掌握：格（偏序格、代数格、两种格的等价性、格的性质、子格与格同态、分配格与模格、有 界格与有补格)、布尔代数、子布尔代数与布尔同态。 理解：格的应用、布尔表达式、布尔代数的应用。 教学方法：讲授为主的启发式的教学方法，引导学生通过回顾以往偏序关系和代数系统的知识， 掌握格的偏序和代数的两重性，特别注重判断和证明。以学生课前预习，课堂讨论为主的教学方法， 激发学生的主动性和参与性，进一步扩展学生的主动思维习惯。 (二)自学内容和要求（用五号宋体加粗） 第14章环与域自学 了解：环与域的定义、性质和应用。 (三)实践性教学环节和要求（用小四号黑体字） 实验项目名称 实验类型 逻辑学家会议问题 基础型 海底管道问题 基础型 海盗分宝石问题 设计型 分油问题 综合型 穿衣问题 综合型 交通网络问题 综合型 洒水车路线问题 设计型 代数运算的判定 综合型 学生课后完成实验并提交实验报告，需完成两个基础型实验，并自选一个综合性或设计型实验。 三、考核方式 期末(70%)+期中(10%)+平时(10%)+实验(10%) 四、建议教材及参考资料 教材 1.离散数学及其应用(“十一五”规划教材)，傅彦，顾小丰，王庆先，刘启和，高等教 育出版社，“十一五”规划教材，2007年
掌握：欧拉图、哈密顿图、偶图、平面图（定义、判定方法、欧拉公式、库拉托夫斯基定理）。 理解：欧拉图的应用、哈密顿图的应用、偶图的应用、平面图的着色、平面图的应用。 教学方法：讲授为主的启发式的教学方法。 第 12 章 代数系统 3 学时 掌握：代数系统（代数运算、代数系统、子代数）、代数系统的基本运算和性质（代数运算的 性质：交换律、结合律、分配律、幂等律、吸收律、消去律；代数系统中的特殊元素：单位元、零 元、逆元、幂等元）、同态和同构。 理解：代数系统的应用、代数系统性质的应用、同态与同构的应用。 教学方法：讲授为主的启发式的教学方法。 第 13 章 群 7 学时 掌握：半群与含幺半群（半群和含幺半群、子半群和子含幺半群、循环半群与循环含幺半群的 概念、性质与判断）、群及其性质（群的定义、元素的周期、子群及其判定条件、群同态与同构）、 特殊群（交换群、循环群）、陪集与拉格朗日定理、不变子群与商群 理解：半群的应用、群的应用、特殊群的应用、拉格朗日定理的应用。 了解：置换群、商群、商群的应用。 教学方法：讲授为主的启发式的教学方法。 第 15 章 格与布尔代数 6 学时 掌握：格（偏序格、代数格、两种格的等价性、格的性质、子格与格同态、分配格与模格、有 界格与有补格）、布尔代数、子布尔代数与布尔同态。 理解：格的应用、布尔表达式、布尔代数的应用。 教学方法：讲授为主的启发式的教学方法，引导学生通过回顾以往偏序关系和代数系统的知识， 掌握格的偏序和代数的两重性，特别注重判断和证明。以学生课前预习，课堂讨论为主的教学方法， 激发学生的主动性和参与性，进一步扩展学生的主动思维习惯。 （二）自学内容和要求（用五号宋体加粗） 第 14 章 环与域 自学 了解：环与域的定义、性质和应用。 （三）实践性教学环节和要求（用小四号黑体字） 实验项目名称 实验类型 逻辑学家会议问题 基础型 海底管道问题 基础型 海盗分宝石问题 设计型 分油问题 综合型 穿衣问题 综合型 交通网络问题 综合型 洒水车路线问题 设计型 代数运算的判定 综合型 学生课后完成实验并提交实验报告，需完成两个基础型实验，并自选一个综合性或设计型实验。 三、考核方式 期末（70%）+ 期中（10%）+ 平时（10%）+ 实验（10%） 四、建议教材及参考资料 教材 1. 离散数学及其应用（“十一五”规划教材），傅彦，顾小丰，王庆先，刘启和，高等教 育出版社，“十一五”规划教材，2007 年
2.离散数学实验与习题解析(“十一五”规划教材)，傅彦，尚明生，王丽杰，顾小丰， 高等教育出版社，“十一五”规划教材，2007年。 参考资料 1.离散数学(“十五”规划教材)，傅彦，顾小丰，刘启和，机械工业出版社，2005年。 2.离散数学常见题型解析及模拟题，傅彦，顾小丰，刘启和，西北工业大学出版社，2004 年。 3.离散数学结构，[美]B.Kolman,R.C.Busby,S.C.Ros,罗平译，高等教育出版社，2005 年。 4.离散数学结构一一理论与应用，[美]D.S.Ma1ik,邱仲潘译，高等教育出版社，2005 年
2. 离散数学实验与习题解析（“十一五”规划教材），傅彦，尚明生，王丽杰，顾小丰， 高等教育出版社，“十一五”规划教材，2007 年。 参考资料 1. 离散数学（“十五”规划教材），傅彦，顾小丰，刘启和，机械工业出版社， 2005 年。 2. 离散数学常见题型解析及模拟题，傅彦，顾小丰，刘启和，西北工业大学出版社，2004 年。 3. 离散数学结构，[美]B.Kolman，R.C.Busby，S.C.Ros，罗平 译，高等教育出版社，2005 年。 4. 离散数学结构——理论与应用，[美]D.S.Malik，邱仲潘 译，高等教育出版社，2005 年