课程名称

（中文）离散数学

（英文）Discrete Mathematics

课程性质

专业基础课程

适用专业及年级

23级人工智能、24级人工智能

开课部门

人工智能与数据科学系

学时学分

学分:3

总学时:54

理论学时:54

实验学时:0

先修课程

高等数学

教学章节

教学内容

（知识点）与教学要求

理论学时

教学方式与方法

第一章

命题逻辑

教学要求:

1. 深刻理解命题的概念，分清简单命题与复合命题。

2. 熟练掌握常用联结词, , , , 的涵义，并能准确地应用它们。

3. 深刻理解命题的赋值、成真赋值、成假赋值、重言式、矛盾式、可满足式等概念。

4. 能熟练地写出给定命题公式的真值表，并根据真值表判断公式的类型、求公式的成真赋值和成假赋值。

5. 深刻理解等值式的定义，牢记基本等值式并能熟练地应用它们进行等值演算。

6. 深刻理解文字、简单析取式、简单合取式、析取范式、合取范式、主析取范式、主合取范式等概念。熟练掌握极小项、极大项的定义、名称以及下角标与成真赋值、成假赋值的关系。

7. 深刻理解主析取范式、主合取范式、真值表三者之间的关系。熟练掌握求主析取范式与主合取范式的方法，会用主析取范式和主合取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值。

8. 理解联结词完备集的定义，掌握联结词和，会将命题公式等值地化成指定联结词完备集上的公式。

9. 会利用命题公式解决一些实际问题。

10. 熟练掌握推理形式结构的两种形式和判断推理是否正确的（真值表法、等值演算法、主析取范式法等）。

11. 牢记推理规则，掌握构造推理的证明以及附加前提证明法、归谬法。

12. 会用推理解决一些实际问题.

教学内容:

1.1命题及命题联结词；

1.2命题公式及类型；

1.3等值演算；

1.4范式；

1.5联结词全功能集；

1.6组合电路；

1.7推理理论；

1.8题例分析。

教学重点:

1. 常用联结词, , , , 的应用。

2.写出给定命题公式的真值表，并判断公式的类型。

3.应用基本等值式进行等值演算。

4.主析取范式和主合取范式求公式的应用。

5.推理的证明。

教学难点:

1.应用等值式进行等值演算。

2.主析取范式和主合取范式的应用。

3. 推理的证明，并用推理解决一些实际问题。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

12

课件讲授，

讨论，

案例教学

第二章

一阶逻辑

教学要求:

1.深刻理解个体词与个体域、谓词、量词等概念，并能准确地运用这些概念将给定命题符号化。

2.深刻理解一阶逻辑公式、指导变元与量词的辖域、个体变项的约束出现与自由出现等概念。

3.深刻理解解释与赋值的概念，会在给定解释和赋值下解释公式。

4.深刻理解永真式、矛盾式、可满足式的概念并能判别一些公式的类型。

5.深刻理解一阶逻辑公式的等值概念，熟练掌握一阶逻辑中的重要等值式和换名规则。

6.能熟练地求出给定公式的前束范式。

教学内容:

2.1一阶逻辑基本概念；

2.2一阶逻辑合式公式及解释；

2.3一阶逻辑等值式与前束范式；

2.4题例分析。

教学重点:

1.一阶逻辑公式、指导变元与量词的辖域、个体变项的约束出现与自由出现等概念；

2.一阶逻辑公式的解释与赋值及其应用；

3.一阶逻辑公式的前束范式。

教学难点:

1.一阶逻辑公式的解释与赋值；

2.给定公式的前束范式。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

6

课件讲授，

讨论，

案例教学

第三章

集合的基本概念和运算

教学要求:

1.深刻理解集合的概念，熟练掌握集合的两种表示法。

2.深刻理解集合之间的相等、包含关系以及子集、空集、全集、幂集等概念。

3.熟练掌握集合的基本运算（并、交、补、对称差等）及其算律，并能运用算律化简集合表达式。

4.掌握证明集合相等和包含关系的方法。

5.掌握利用文氏图和包含排斥原理计数有穷集合方法。

教学内容:

3.1集合的基本概念；

3.2集合的基本运算；

3.2集合的基本运算；

3.4题例分析。

教学重点:

1.集合的表示，集合的幂集；

2.集合的运算；3.集合恒等式的证明。

教学难点:1.集合的运算；

2.集合恒等式的证明。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

3

课件讲授，

讨论，

案例教学

第四章

二元关系和函数

教学要求:

1.深刻理解有序对和笛卡儿积的概念，熟练掌握笛卡儿积的运算性质。

2.熟练掌握二元关系的定义及常用的二元关系，熟练掌握表示关系的3种方法。

3.熟练掌握关系的定义域、值域、逆、合成、限制、像、幂的计算方法。

4.熟练掌握判断和证明关系的自反性、反自反性、对称性、反对称性、传递性的方法，了解并、交、补、逆、合成等运算对这些性质的影响。

5.能熟练地计算关系的自反闭包、对称闭包和传递闭包.。

6.深刻理解等价关系、等价类、商集、划分等概念，熟练掌握等价关系与划分的对应关系。

7.熟练掌握偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念。

8.熟练掌握函数的概念以及单射、满射、双射等性质。

9.熟练掌握函数的复合、反函数及相关性质。

教学内容:

4.1集合的笛卡儿积与二元关系；

4.2关系的运算；

4.3关系的性质；

4.4关系的闭包；

4.5等价关系和偏序关系；

4.6函数的定义和性质；

4.7函数的复合和反函数；

4.8题例分析。

教学重点:

1.关系的运算、性质和闭包；

2.等价关系和偏序关系的判定与证明；

3.函数及其运算。

教学难点:

1.关系的性质和闭包的判定与证明；

2.等价关系和偏序关系的判定与证明。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

12

课件讲授，

讨论，

案例教学

第五章

图的基本概念

教学要求:

1.深刻理解无向图、有向图及相关的诸多概念，以及它们之间的相互关系。

2.深刻理解握手定理及其推论，并能熟练地应用它们。

3.深刻理解图的同构、简单图、完全图、正则图、子图、导出子图、补图等概念及它们的性质和相互关系，并能熟练地应用这些性质和关系。

4.理解通路与回路及相关概念，掌握图关于连通性的分类以及点割集、边割集、割点、割边等。

5.掌握图的矩阵表示和用有向图的邻接矩阵求图中通路数与回路数，求有向图的可达矩阵。

6.掌握最短路径问题的Dijkstra算法。

教学内容:

5.1无向图及有向图；

5.2通路、回路和图的连通性；

5.3图的矩阵表示；

5.4最短路径、关键路径和着色（选讲）；

5.5题例分析。

教学重点:

1.图的基本概念；2.图的矩阵表示；

3.最短路径问题的Dijkstra算法。

教学难点:

1.握手定理及其推论；2.图的矩阵表示；

2.最短路径问题的Dijkstra算法。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

9

课件讲授，

讨论，

案例教学

第六章

特殊的图

教学要求:

1.熟练掌握二部图的概念及其判别定理。

2.掌握图和二部图的匹配及相关概念，掌握二部图具有完备匹配的充分必要条件（Hall定理）和充分条件（t条件），会利用匹配解决一些实际问题。

3.深刻理解欧拉回路与欧拉通路的定义，熟练掌握欧拉图与半欧拉图的判别定理。

4.深刻理解哈密顿回路和哈密顿通路的定义，了解所给的存在哈密顿回路和通路的必要条件和充分条件。

5.深刻理解平面图及有关概念，掌握极大平面图的判别定理、欧拉公式和它的推广形式及相关的定理。

6.会用库拉图斯基定理证明某些非平面。

7.知道图的着色问题，能用着色问题解决一些的实际问题。

教学内容:

6.1二部图；

6.2欧拉图；

6.3哈密顿图；

6.4平面图；

6.5题例分析。

教学重点:

1.欧拉图和哈密顿图的判别；

2.平面图的判别。

教学难点:

1.欧拉图和哈密顿图的判别；

2.平面图的判别。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

6

课件讲授，

讨论，

案例教学

第七章

树

教学要求:

1.深刻理解无向树的定义，熟练掌握无向树的性质。

2.深刻理解生成树和基本回路、基本割集的概念，会求对应给定生成树的基本回路系统和基本割集系统。

3.熟练掌握地求最小生成树的避圈法。

4.了解有向树、根树及相关概念，了解有序树及其分类。

5.了解Huffman算法和用它求最佳前缀码。

6.了解行遍有序树的方法，了解前缀符号法与后缀符号法。

教学内容:

7.1无向树及生成树；

7.2根树及其应用（选讲）；

7.3题例分析。

教学重点:

1.树的基本概念，有序树及其分类；

2.Huffman算法和用它求最佳前缀码。

教学难点:

1.求对应给定生成树的基本回路系统和基本割集系统；

2.Huffman算法和用它求最佳前缀码。

学生自主学习任务:

作业及小测、预习及课外拓展阅读等。

6

课件讲授，

讨论，

案例教学

合 计

54

考核方式

考核要求

比重（%）

对应的课程目标

平时成绩

出勤、课堂互动、课堂讨论

16

LO1、LO2、LO3、LO4

平时成绩

平时作业、章节测验

24

LO1、LO2、LO3、LO4

期末考试

完成闭卷考试

60

LO1、LO2