离散数学
课程编码：B2011001Y 英文名称：Discrete Mathematics 课时：56 学分：3.00 课程属性：专业必修课 主讲教师：王鲲鹏等
第一章 命题逻辑的基本概念
本章的教学内容包括命题与联接词、命题公式及其赋值。要求掌握五种常用联接词的涵义并能准确运用它们将命题符号化；掌握命题公式的赋值。教学难点是蕴含联接词和析取联接词，真值表。
第二章 命题逻辑等值演算
本章的教学内容包括等值式，析取范式和合取范式，联接词的完备集。要求掌握等值式的定义，熟练应用等值式及置换规则进行等值演算，掌握极小项、极大项的定义、名称、下角标与成真赋值的关系，掌握求主析取范式和主合取范式的方法。重点和难点是等值式的定义，极大项与极小项。
第三章 命题逻辑的推理理论
教学内容包括推理的形式结构，自然推理系统。要求掌握判断推理是否正确的不同方法，掌握推理系统中各条推理规则的名称和内容，掌握自然推理系统中的常用证明方法。难点是推理的形式结构，推理规则。
第四章 一阶逻辑的基本概念
教学内容包括一阶逻辑命题符号化，一阶逻辑公式及其解释。要求掌握一阶逻辑的命题符号化，理解为此公式与解释。难点是个体、谓词、量词；重点是谓词公式及其解释。
第五章 一阶逻辑等值演算
教学内容包括一阶逻辑等值式与置换规则，一阶逻辑前束范式。要求掌握一阶逻辑基本等值式的使用，掌握一阶逻辑前束公式的求解方法。教学难点是一阶逻辑前束范式。
第六章 集合代数
教学内容包括几何的基本概念，集合的运算，有穷集的计数，集合恒等式等。要求掌握集合的两种表示法，能够判断两个集合之间是否存在包含、相等、真包含等关系，熟练掌握集合的基本运算，掌握有穷集合的计数方法，掌握证明集合等式或者包含关系的基本方法。重点是掌握集合的基本概念和运算；难点是集合中的计数问题。
第七章 二元关系
教学内容包括二重组和笛卡尔积，二元关系，关系的运算，关系的性质，关系的闭包，等价关系与划分，偏序关系。教学要求是理解二重组、二元关系、集合的关系的定义，掌握笛卡尔积的运算和性质，熟练掌握关系表达式、关系矩阵、关系图的表示法，熟练掌握关系的定义域、值域、逆、复合以及幂的计算方法，熟练掌握判断关系五种性质的方法，熟练掌握等价关系和划分的概念和性质，熟练掌握偏序关系、偏序集以及哈斯图。教学难点是二元关系的运算，关系的闭包，等价关系与划分，偏序关系。
第八章 函数
教学内容包括函数的定义与性质，函数的复合与反函数，双射函数与集合的基数。要求掌握函数的基本概念，会判断和证明函数的单射、满射和双射性质，会构造两个给定集合之间的双射，会计算复合函数、双射函数的反函数。难点和重点是函数的复合与反函数，双射函数与集合的基数。
第九章 图的基本概念
教学内容包括图，通路与回路，图的连通性，图的矩阵表示，图的运算等。要求了解无向图与有向图的定义、顶点的度数等概念，理解零图、平凡图、简单图、完全图、正则图、子图、补图、图同构等概念，熟练掌握握手定理及应用，理解通路与回路、简单通路、简单回路、初级通路、初级回路、无向图顶点间的连通、有向图顶点间的可达等概念，理解无向连通图、连通图等概念，掌握n阶有向图的邻接矩阵和可达矩阵的定义，熟练掌握通过邻接矩阵求顶点间长度为k的通路数、回路数以及图中长度为k的通路和回路数的方法。教学重点是图的基本概念；教学难点是图的通路、回路和连通性，图的矩阵表示。
第十章 树
教学内容包括无向树及其性质，生成树、跟树及其应用等。要求掌握树的概念和性质，最小生成树的概念和性质，二叉树的遍历及哈夫曼算法等。教学难点是二叉树的遍历。
第十一章 几种特殊的图
教学内容包括欧拉图，哈密尔顿图，最短路径问题等。要求理解欧拉通路、回路以及欧拉图等概念，熟练掌握判断欧拉图的方法，理解哈密尔顿通路、回路以及哈密尔顿图的概念，会判断某些图是或者不是哈密尔顿图。教学难点是欧拉图的概念、性质以及判断方法，哈密尔顿图的判别。
第十二章 整除和算术基本定理
教学内容包括整除的基本概念和性质，带余除法和辗转相除法，最大公因子，素数和算术基本定理等。要求掌握整除、带余除法、素数等基本概念，掌握算术基本定理的内容。要求熟练掌握最大公因子和辗转相除法的关系，熟练掌握辗转相除法计算最大公因子的方法。教学难点是素数定理的证明。
第十三章 同余
教学内容包括同余的概念，完全剩余系和既约剩余系的概念，费马定理和欧拉定理，一次同余方程的解，同余方程组的解和孙子定理，二次同余方程的解和二次剩余，Legendre符号和二次剩余，Jacobi符号等。要求掌握上述基本概念和基本定理。熟练掌握费马定理、孙子定理的内容，熟练应用费马定理和孙子定理解决相关问题。理解Legendre符号和二次剩余的关系，理解Jacobi符号和一般模数二次剩余的关系。教学难点是同余的概念、既约剩余系的概念，孙子定理的证明等。
第十四章 原根
教学内容包括指数和原根的概念，模奇素数的原根的存在性。要求理解指数和原根的概念。教学难点是模奇素数的原根的存在性的证明。
| 章节/学时分配 | 讲课 | 习题课 | 实验课 | 上机课 | 讨论课 | 其它 |
| 第一章 | 4 | 1 |
|
|
|
|
| 第二章 | 5 | 2 |
|
|
|
|
| 第三章 | 4 | 2 |
|
|
|
|
| 第四章 | 3 | 1 |
|
|
|
|
| 第五章 | 4 | 1 |
|
|
|
|
| 第六章 | 3 | 1 |
|
|
|
|
| 第七章 | 3 | 2 |
|
|
|
|
| 期中考试 |
|
|
|
|
| 2 |
| 第八章 | 4 | 1 |
|
|
|
|
| 第九章 | 4 | 1 |
|
|
|
|
| 第十章 | 4 | 1 |
|
|
|
|
| 第十一章 | 4 | 1 |
|
|
|
|
| 第十二章 | 2 | 1 |
|
|
|
|
| 第十三章 | 6 | 2 |
|
|
|
|
| 第十四章 | 2 | 1 |
|
|
|
|
| 期末考试 |
|
|
|
|
| 2 |