一、课程中英文名称 中文名称：离散数学 英文名称：Discrete Mathematics 二、授课对像与学时 授课对象：软件工程专业 总学时：72每周4课时，由于课时较少，教师在具体执行当中可以根据专业特点，对教学内容进 行适当调整。 三、本课程与其他课程的联系 先修课程：高等数学 后续课程：算法与数据结构 可计算性与计算复杂性理论、程序设计、软件工程、操作系统、编 译理论、逻辑设计、系统结构、人工智能、数据库 四、课程的教学目的 随着计算机科学技术的迅猛发展，作为支撑学科的离散数学正变得越来越重要。离散数学是现 代数学的一个重要分支，是应用数学和计算机科学基础理论的核心课程。离散数学是以研究离散量 的结构和相互之间的关系为主要目花 其研究对象通常是 有限集中的元素，因此 它充分描述了以 计算机科学为代表的现代信息技术等学科离散性的特点。离散数学是一门新兴的发展迅速的基础 具性学科。计算机科学技术的发展所产生的各种理论问题的研究需要采用现代数学中的不同理论和 方法，为了使学生掌握必需的数学工具和培养学生的抽象思维和逻辑推理能力，离散数学课程就成 为了计算机科学技术以及相关专业的核心骨干课程。 离散数学的内容比较广泛，基本内容包括数理逻辑、集合论、代数系统、图论等数学领域中的基 本理论和方法。 通过本课程的学习，要求学生对这四个领域的基本概念和术语、基本定理及初步的 运算证明方法和技巧有较好的理解和掌握，对离散数学与计算机科学之间的关系有初步了解，为后 续相关果程的学习奠定良好的数学基出 五、课程教学的主要内容 第一部分数理逻辑 弟 -章命题逻辑基本概念(4学时) 内容：命题与联结词，命题公式及其赋值 2. 本章教学要求 1)堂合的相肝念 2 掌握连结词的真值表 掌握命题符号化方法并能正确使用连结词 4)掌握合式公式的定义以及公式赋值的概念， 3.重点：命题与联结词，命题公式 4.难点：合式公式，公式赋值 第二章命题逻辑等值演算(4学时) 内容：等值式，析取范式与合取范式，连结词的完备集 2. 本章教学要求 1) 掌握等值式的概念，熟悉基本的等值式： 2)掌握析取范式和合取范式的定义和求法步骤，以及相关的极小项和极大项的概念和性质， 3)了解连结词的完备集的概念 3.重点：等 值式的概念 基本等值式，析取范式与合取范式的定义和求法步骤 4.难点：连结词的完备集的概念 第三章命题逻辑的推理理论(4学时) 1.内容：推理的形式结构，自然推理系统P
一、课程中英文名称 中文名称：离散数学 英文名称：Discrete Mathematics 二、授课对象与学时 授课对象：软件工程专业 总学时：72 每周4课时，由于课时较少，教师在具体执行当中可以根据专业特点，对教学内容进 行适当调整。 三、本课程与其他课程的联系 先修课程：高等数学 后续课程：算法与数据结构、可计算性与计算复杂性理论、程序设计、软件工程、操作系统、编 译理论、逻辑设计、系统结构、人工智能、数据库 四、课程的教学目的 随着计算机科学技术的迅猛发展，作为支撑学科的离散数学正变得越来越重要。离散数学是现 代数学的一个重要分支，是应用数学和计算机科学基础理论的核心课程。离散数学是以研究离散量 的结构和相互之间的关系为主要目标，其研究对象通常是有限集中的元素，因此，它充分描述了以 计算机科学为代表的现代信息技术等学科离散性的特点。离散数学是一门新兴的发展迅速的基础工 具性学科。计算机科学技术的发展所产生的各种理论问题的研究需要采用现代数学中的不同理论和 方法，为了使学生掌握必需的数学工具和培养学生的抽象思维和逻辑推理能力，离散数学课程就成 为了计算机科学技术以及相关专业的核心骨干课程。 离散数学的内容比较广泛，基本内容包括数理逻辑、集合论、代数系统、图论等数学领域中的基 本理论和方法。通过本课程的学习，要求学生对这四个领域的基本概念和术语、基本定理及初步的 运算证明方法和技巧有较好的理解和掌握，对离散数学与计算机科学之间的关系有初步了解，为后 续相关课程的学习奠定良好的数学基础。 五、课程教学的主要内容 第一部分 数理逻辑 第一章 命题逻辑基本概念(4学时) 1． 内容：命题与联结词，命题公式及其赋值 2． 本章教学要求 1） 掌握命题的概念； 2） 掌握连结词的真值表； 3） 掌握命题符号化方法并能正确使用连结词； 4） 掌握合式公式的定义以及公式赋值的概念。 3. 重点：命题与联结词，命题公式 4. 难点：合式公式，公式赋值 第二章 命题逻辑等值演算(4学时) 1． 内容：等值式，析取范式与合取范式，连结词的完备集 2． 本章教学要求 1） 掌握等值式的概念，熟悉基本的等值式； 2） 掌握析取范式和合取范式的定义和求法步骤，以及相关的极小项和极大项的概念和性质； 3） 了解连结词的完备集的概念。 3. 重点：等值式的概念，基本等值式，析取范式与合取范式的定义和求法步骤 4. 难点：连结词的完备集的概念 第三章 命题逻辑的推理理论(4学时) 1． 内容：推理的形式结构，自然推理系统P
2.本章教学要求 1)基本掌握推理的基本概念和形式结构 掌握推理定律和自然推理系统P中的推理规则： 3)能够利用推理规则进行一些简单的推理证明，了解一些常用的证明方法。 3.重点：推理的基本概念和形式结构，自然推理系统P,常用的证明方法 4.难点：推理定律和自然推理系统P 第四音一阶罗娟甚木艇令(4学时 阶逻辑命题符号化， 一阶逻辑公式及解释 2.本章教学要求 )掌握个体词、谓词、全称量词、存在量词的概念，以及在一阶逻辑命题符号化时能正确选择 话当的谓词.量词和车结词 2)基本掌握一阶逻辑合式公式的概念 3) 了解一阶逻辑公式解释的 概念· 3.重点： -阶逻辑命题符号化，一阶逻辑公式解释 4.难点： 一阶罗辑公式解怪 第五章一阶逻辑等值演算与推理(4学时) 1内容： 一阶逻辑等值式与置换规则，一阶逻辑前束范式，一阶逻辑的推理理论 本章教学要求 号，"价透等值式的念，以及基本的等值式.特是有关量词的4个基本等佰式) 2)基本掌握置换规则、换名规则和代替规则侧的概念和使用，了解一阶逻辑命题公式前束范式的 概念，并能够求一些简单公式的前束范式： 3)掌握一阶逻辑自然推理系统F，以及该系统中的推理规则，特别是4个有关量词的推理规 则，能够在推理证明中正确使用这些推理规则 可以进 一些简单的推理证明 3.重点：一阶逻辑基本等值式， 阶逻辑命题公式前束范式的概念，一阶逻辑自然推理系统： 4.难点： 一阶罗辑自然推理系统F 第二部分集合论 第六章集合代数(4学时 内容：集合的基本概念，集合的运算，集合恒等式 2. 本章教学要求 掌程集合的概念和表示去 2)掌握集合的常用基本运算，及其文氏图表示： 3)熟悉常见的集合恒等式及其证明。 3.重点：集合的概念和表示法、基本运算，集合恒等式及其证明 4.难点：集合恒等式及其证明 第七章二元关系(6学时) 1.内容：有序对与笛卡儿积，二元关系，关系的运算，关系的性质，关系的闭包，等价关系 与划分，偏序关系 2 本章教学要求 1) 掌握有序对与笛卡儿积的概念： 2) 掌握二元关系的定义及其矩阵表示： 3)掌握关系的五种常见的性质（自反性、反自反性、对称性、反对称性、传递性）的定义， 堂据关系的白反闭句.时弥闭包.传递闭句的定以和求法： 4)掌握等价关系的定义、等价类及性质，掌握集合划分的定义，以及等价关系与划分之间的 5)掌握偏序关系的定义，以及偏序集的概念和它的Hassel图表示； 6)了解偏序集中的极大元、极小元、最大元、最小元的概念
2． 本章教学要求 1） 基本掌握推理的基本概念和形式结构； 2） 掌握推理定律和自然推理系统P中的推理规则； 3） 能够利用推理规则进行一些简单的推理证明，了解一些常用的证明方法。 3. 重点：推理的基本概念和形式结构，自然推理系统P，常用的证明方法 4. 难点：推理定律和自然推理系统P 第四章 一阶逻辑基本概念(4学时) 1．内容：一阶逻辑命题符号化，一阶逻辑公式及解释 2．本章教学要求 1）掌握个体词、谓词、全称量词、存在量词的概念，以及在一阶逻辑命题符号化时能正确选择 适当的谓词、量词和连结词； 2）基本掌握一阶逻辑合式公式的概念； 3）了解一阶逻辑公式解释的概念。 3. 重点：一阶逻辑命题符号化，一阶逻辑公式解释 4. 难点：一阶逻辑公式解释 第五章 一阶逻辑等值演算与推理(4学时) 1． 内容：一阶逻辑等值式与置换规则，一阶逻辑前束范式，一阶逻辑的推理理论 2．本章教学要求 1）掌握一阶逻辑等值式的概念，以及基本的等值式，特别是有关量词的4个基本等值式； 2）基本掌握置换规则、换名规则和代替规则的概念和使用，了解一阶逻辑命题公式前束范式的 概念，并能够求一些简单公式的前束范式； 3）掌握一阶逻辑自然推理系统F，以及该系统中的推理规则，特别是4个有关量词的推理规 则，能够在推理证明中正确使用这些推理规则，可以进行一些简单的推理证明。 3. 重点：一阶逻辑基本等值式，一阶逻辑命题公式前束范式的概念，一阶逻辑自然推理系统F 4. 难点：一阶逻辑自然推理系统F 第二部分 集合论 第六章 集合代数(4学时) 1． 内容：集合的基本概念，集合的运算，集合恒等式 2． 本章教学要求 1） 掌握集合的概念和表示法； 2） 掌握集合的常用基本运算，及其文氏图表示； 3） 熟悉常见的集合恒等式及其证明。 3. 重点：集合的概念和表示法、基本运算，集合恒等式及其证明 4. 难点：集合恒等式及其证明 第七章 二元关系(6学时) 1． 内容：有序对与笛卡儿积，二元关系，关系的运算，关系的性质，关系的闭包，等价关系 与划分，偏序关系 2． 本章教学要求 1） 掌握有序对与笛卡儿积的概念； 2） 掌握二元关系的定义及其矩阵表示； 3） 掌握关系的五种常见的性质（自反性、反自反性、对称性、反对称性、传递性）的定义， 掌握关系的自反闭包、对称闭包、传递闭包的定义和求法； 4） 掌握等价关系的定义、等价类及性质，掌握集合划分的定义，以及等价关系与划分之间的 关系； 5） 掌握偏序关系的定义，以及偏序集的概念和它的Hasse图表示； 6） 了解偏序集中的极大元、极小元、最大元、最小元的概念
3.重点：二元关系的定义及其矩阵表示，二元关系的常见的性质及闭包的定义和求法，等价关 系、偏序关系的定义，偏序集的概念和它的Hsse图表示，极大元、极小元、最大元、最小元 的概念 4.难点：闭包的定义和求法 第八章函数(4学时) 1.内容：函数的定义与性质，函数的复合与反函数 2. 本章教学要求 1)掌握函数的定义以及满射、单射、双射（一一对应）的概念 了解恒等函数和特征函数的基本概系 3)基本掌握函数的复合、反函数的定义 3.重点：函数的定义与性质，满射、单射、双射（一一对应）的概念 4.难点：函数的复合、反函数 第九章集合的基数(2学时) 内容： 集合的等势与优势，集合的基数 2. 本章教学要求 1) 基本掌握集合的等势概念 2)了解集合的基数概念 3.重点：集合的等势概念 4.难点：集合的基数概念 第三部分代数结构 第十章代数系统(4学时) 1 内容：二元运算及其性质，代数系统 2. 本章教学要求 1)掌根 元运算的定义及性质 掌握 二元运算的结合律、交换律、分配律、吸收律的定义 3)掌握代数结构的定义，以及代数结构中的一些特殊元素（单位元、零元、逆元）的定义 4)了解两个同类型代数结构的定义 3.重点：二元运算的定义及性质，二元运算的结合律、交换律、分配律、吸收律的定义，代数 结构中的 一此特殊麦 4.难点：代数结构中的一些特殊元素，同类型代数结构 第十 一章半群与群(6学时) 1.内容：半群与独异点，群的定义与性质，子群，陪集与拉格朗日定理，正规子群与商群， 群的同态与同构，循环群与置换群 本音数学要求 1) 基本掌握半群 交换半群、独异点的定义 2) 掌握群的定义和 些常儿的群的例子 3)堂程群的基本性质 4)掌握群的价的定义 5 掌握群子群的定义以及子群判定的充要条件 6) 了解子群的陪集的概念和性质， 基本掌握拉格朗日定理，了解正规子群和商群的概念； 基本掌握群的同态和同构的概念； 8)基本掌握循环群和置换群的概念，熟悉一些常见的循环群和置换群。 3.重点：群的定义及基本性质，子群的定义以及子群判定的充要条件，循环群和置换群的概 念，重要的循环群和置换群。 4.难点：子群的陪集的概念和性质，基本掌握拉格朗日定理，正规子群和商群的概念，群的同
3. 重点：二元关系的定义及其矩阵表示，二元关系的常见的性质及闭包的定义和求法，等价关 系、偏序关系的定义，偏序集的概念和它的Hasse图表示，极大元、极小元、最大元、最小元 的概念 4. 难点：闭包的定义和求法 第八章 函数(4学时) 1． 内容：函数的定义与性质，函数的复合与反函数 2． 本章教学要求 1） 掌握函数的定义以及满射、单射、双射（一一对应）的概念 2） 了解恒等函数和特征函数的基本概念 3） 基本掌握函数的复合、反函数的定义 3. 重点：函数的定义与性质，满射、单射、双射（一一对应）的概念 4. 难点：函数的复合、反函数 第九章 集合的基数(2学时) 1． 内容：集合的等势与优势，集合的基数 2． 本章教学要求 1） 基本掌握集合的等势概念 2） 了解集合的基数概念 3. 重点：集合的等势概念 4. 难点：集合的基数概念 第三部分 代数结构 第十章 代数系统(4学时) 1． 内容：二元运算及其性质，代数系统 2． 本章教学要求 1） 掌握二元运算的定义及性质 2） 掌握二元运算的结合律、交换律、分配律、吸收律的定义 3） 掌握代数结构的定义，以及代数结构中的一些特殊元素（单位元、零元、逆元）的定义 4） 了解两个同类型代数结构的定义 3. 重点：二元运算的定义及性质，二元运算的结合律、交换律、分配律、吸收律的定义，代数 结构中的一些特殊元素 4. 难点：代数结构中的一些特殊元素，同类型代数结构 第十一章 半群与群(6学时) 1． 内容：半群与独异点，群的定义与性质，子群，陪集与拉格朗日定理，正规子群与商群， 群的同态与同构，循环群与置换群 2． 本章教学要求 1） 基本掌握半群、交换半群、独异点的定义； 2） 掌握群的定义和一些常见的群的例子； 3） 掌握群的基本性质； 4） 掌握群的阶的定义； 5） 掌握群子群的定义以及子群判定的充要条件； 6） 了解子群的陪集的概念和性质，基本掌握拉格朗日定理，了解正规子群和商群的概念； 7） 基本掌握群的同态和同构的概念； 8） 基本掌握循环群和置换群的概念，熟悉一些常见的循环群和置换群。 3. 重点：群的定义及基本性质，子群的定义以及子群判定的充要条件，循环群和置换群的概 念，重要的循环群和置换群。 4. 难点：子群的陪集的概念和性质，基本掌握拉格朗日定理，正规子群和商群的概念，群的同
态和同构的概念 第十一音环与域(2学时力 内容： 环的定义与性质，整环与域 2 本章教学要求 1) 了解环的定义和几个常见的环的例子： 2)了解域的概念 3重与·环的定义与性后 4.难点：域的概念 第十三章格与布尔代数(4学时) 1. 内容：格的定义与性质，子格与格同态，分配格与有补格，布尔代数 2. 本章教学要求 1)掌握格的定义及基本性质； 2 了解子格的定义与格同态的概念 基本掌握分配格和有补格的定义，以及若干例子； 4)基本掌握布尔代数的概念。 3.重点：格、布尔代数的定义与性质 4.难点：布尔代数的定义与性质 第四部分图论 第十四章图的基本概念(6学时 1. 内容：图，通路与回路，图的连通性，图的矩阵表示，图的运算 2. 本章教学要求 1)掌握图的定义，包括无向图与有向图、赋权图； 2）掌握图的顶点、边的关联与相邻关系，顶点的度数的概念 3) 掌握图的顶点度数与边数的关系： 4) 掌握子图的概念，以及生成子图、导出子图和补图的博念： 5) 了解图的同构的概念； 6) 掌握通路与回路、圈的概念： 71 掌握图的连通性的概念， 了解图的点连通度、边连通度、有向图的连通性 掌握图的矩阵表示（邻接矩阵、关联矩阵），了解可达矩阵的概念； 9)熟悉一些常见的图的运算及性质。 3.重点：无向图与有向图、赋权图的定义，图的顶点度数与边数的关系，图的连通性的概念 图的矩阵表示 4.难点：图的连通性的概念 第十五章Euler图与Hamilton图(4学时 内容：Euler图，Hamilton图，带权图与货郎担问题 2. 本章教学要求 1)掌握Euler图的概念以及Euler图的判定： 21 掌握Ha ton图的概念，以及Hamiton图判定的必要条件和几个常见的充分条件 3) 了解图论 的优化问题， 特别是货郎担问题 3.重点：Euler图、Hamilton图的概念及判定，货郎担问题 4.难点：Hamilton图判定，货郎担问题 第十六章树4学时) 内容：无向树及其性质，生成树，根树及其应用 本章教学要求
态和同构的概念 第十二章 环与域(2学时) 1． 内容：环的定义与性质，整环与域 2． 本章教学要求 1） 了解环的定义和几个常见的环的例子； 2） 了解域的概念 3. 重点：环的定义与性质 4. 难点：域的概念 第十三章 格与布尔代数(4学时) 1． 内容：格的定义与性质，子格与格同态，分配格与有补格，布尔代数 2． 本章教学要求 1） 掌握格的定义及基本性质； 2） 了解子格的定义与格同态的概念； 3） 基本掌握分配格和有补格的定义，以及若干例子； 4） 基本掌握布尔代数的概念。 3. 重点：格、布尔代数的定义与性质 4. 难点：布尔代数的定义与性质 第四部分 图论 第十四章 图的基本概念(6学时) 1． 内容：图，通路与回路，图的连通性，图的矩阵表示，图的运算 2． 本章教学要求 1） 掌握图的定义，包括无向图与有向图、赋权图； 2） 掌握图的顶点、边的关联与相邻关系，顶点的度数的概念； 3） 掌握图的顶点度数与边数的关系； 4） 掌握子图的概念，以及生成子图、导出子图和补图的概念； 5） 了解图的同构的概念； 6） 掌握通路与回路、圈的概念； 7） 掌握图的连通性的概念，了解图的点连通度、边连通度、有向图的连通性； 8） 掌握图的矩阵表示（邻接矩阵、关联矩阵），了解可达矩阵的概念； 9） 熟悉一些常见的图的运算及性质。 3. 重点：无向图与有向图、赋权图的定义，图的顶点度数与边数的关系，图的连通性的概念， 图的矩阵表示 4. 难点：图的连通性的概念 第十五章 Euler图与Hamilton图(4学时) 1． 内容：Euler图，Hamilton图，带权图与货郎担问题 2． 本章教学要求 1） 掌握Euler图的概念以及Euler图的判定； 2） 掌握Hamilton图的概念，以及Hamilton图判定的必要条件和几个常见的充分条件； 3） 了解图论中的优化问题，特别是货郎担问题。 3. 重点：Euler图、Hamilton图的概念及判定，货郎担问题 4. 难点：Hamilton图判定，货郎担问题 第十六章 树(4学时) 1． 内容：无向树及其性质，生成树，根树及其应用 2． 本章教学要求 1） 掌握树的定义及基本性质；
2)掌握树的几个等价定义： 3)掌握生成树的定义，基本掌握最小生成树的概念及求图的最小生成树的算法(Kruskal)； 4)掌握有向树，特别是根树的定义，以及根树的若干重要应用。 3.重点：树的定义及基本性质，最小生成树的概念及求图的最小生成树的算法(Kruskal) 4.难点：根树的应用 第十七章平面图及图的着色(4学时) 1.内容：平面图的基本概念，Euer公式，平面图的判断，平面图的对偶图，图中顶点的着 色，地图的着色与平面图的点着色，边着色 2.本章教学要求 1)掌握平面图的定义，了解平面图的判定定理(Kuratowski定理)； 2)掌握平面图的Euer公式， 3)基本掌握平面图的一些常见性质： 4)了解平面图的对偶图及简单性质； 5)了解图的顶点和边着色的概念，以及相关的色数概念， 6)了解四色问题的提法和现状。 3.重点：平面图的基本概念，Euer公式，平面图的判断，着色 4.难点：着色 第十八章支配集、覆盖集、独立集与匹配(2学时) 1.内容：支配集、点覆盖集与点独立集，边覆盖集与匹配，二部图中的匹配 2.本章教学要求 1)了解图的支配集、点覆盖集、点独立集、边覆盖集和匹配的概念； 2)基本掌握二部图中的匹配(Hal定理)，及与其相关的简单应用问题。 3.重点：匹配的概念，二部图中的匹配(Hal定理) 4.难点：二部图中的匹配(Hal定理) 六、教材及参考书目 教材：《离散数学》，耿素云编，高等教育出版社，2004年 主要参考书目： 1)《离散数学》，李盘林、李丽双等编，高等教育出版社，1999年 2) 《离散数学导论》，徐洁磐编，高等教育出版社，1982年
2） 掌握树的几个等价定义； 3） 掌握生成树的定义，基本掌握最小生成树的概念及求图的最小生成树的算法（Kruskal）； 4） 掌握有向树，特别是根树的定义，以及根树的若干重要应用。 3. 重点：树的定义及基本性质，最小生成树的概念及求图的最小生成树的算法（Kruskal） 4. 难点：根树的应用 第十七章 平面图及图的着色(4学时) 1． 内容：平面图的基本概念，Euler公式，平面图的判断，平面图的对偶图，图中顶点的着 色，地图的着色与平面图的点着色，边着色 2． 本章教学要求 1） 掌握平面图的定义，了解平面图的判定定理（Kuratowski定理）； 2） 掌握平面图的Euler公式； 3） 基本掌握平面图的一些常见性质； 4） 了解平面图的对偶图及简单性质； 5） 了解图的顶点和边着色的概念，以及相关的色数概念； 6） 了解四色问题的提法和现状。 3. 重点：平面图的基本概念，Euler公式，平面图的判断，着色 4. 难点：着色 第十八章 支配集、覆盖集、独立集与匹配(2学时) 1． 内容：支配集、点覆盖集与点独立集，边覆盖集与匹配，二部图中的匹配 2． 本章教学要求 1） 了解图的支配集、点覆盖集、点独立集、边覆盖集和匹配的概念； 2） 基本掌握二部图中的匹配（Hall定理），及与其相关的简单应用问题。 3. 重点：匹配的概念，二部图中的匹配（Hall定理） 4. 难点：二部图中的匹配（Hall定理） 六、教材及参考书目 教材：《离散数学》， 耿素云编，高等教育出版社，2004年 主要参考书目： 1） 《离散数学》，李盘林、李丽双等编，高等教育出版社，1999年 2） 《离散数学导论》，徐洁磐编，高等教育出版社，1982年