《离散数学》课程教学大纲

Discrete Mathematics

课程编号： 适用专业：计算机类科技班

先修课程：高等数学、线性代数 学 分 数：4

总学时数：64学时 实验（上机）学时：

考核方式：院考试

执 笔 者：刘建元 编写日期：2004年6月

一、课程性质和任务

离攻数学是为大学本科计算机科学专业学生开设的专业骨干基础课程。离散数学以研究离散量的结构和它们之间的关系为主要目标，其研究对象一般地是有限个或可数个元素，充分描述了计算机科学的离散性特点。通过本课程的学习，不仅使学生获得工本理论知识，而且培养学生抽象思维和慎密概括的能力，为后续计算机课程的学习做好准备。

二、课程教学内容和要求

第一章 命题逻辑

基本要求：熟练掌握命题及命题公式的概念，掌握命题的符号化；熟练掌握真值表、等价式、重言式及蕴含式的概念和性质；理解命题范式的概念和性质，掌握命题公式化为范式的方法；熟练掌握命题演算的推理理论和推理方法。

重点：熟练掌握命题符号化，主析取范式、主合取范式的求法；熟练掌握推理规则及推理方法。

难点：命题符号化；推理规则及推理方法的掌握。

主要内容：

1．1 命题及其表示

介绍命题的概念及其表示。

1．2 联结词

介绍否定、合取、析取、条件、双条件联结词及性质。

1．3 命题公式与翻译

介绍命题演算的合式公式的概念，重点介绍命题符号化的一般方法。

1．4 真值表与等价公式

介绍真值表与等价公式的概念，重点介绍命题定律及命题等价公式的推证。

1．5 重言式与蕴含式

介绍命题演算的重言式、矛盾式等概念，重点介绍各种常用的蕴含式。

1．6 其他联结词

介绍不可兼析取、条件否定、与非、或非等联结词及其性质，介绍最小联结词组的概念。

1．7 对偶与范式

介绍对偶和范式的概念，重点介绍命题公式等价转化为主析取范式、主合取范式的方法。

1．8 推理理论

介绍命题演算的推理规则及推理方法。

第二章 谓词逻辑

基本要求：熟练掌握谓词的概念及表示方法；熟练掌握谓词函数、量词的概念；掌握谓词公式的概念；熟练掌握自然语言的翻译；理解变元的约束、前束范式等有关概念；熟练掌握谓词演算的等价式与蕴含式；熟练掌握谓词演算的推理理论。

重点：全称量词、存在量词的概念；自然语言的翻译；谓词演算的等价式与蕴含式；谓词演算的推理理论。

难点：自然语言的翻译；谓词演算的推理规则的理解和推理方法的掌握。

2．1 谓词的概念与表示

介绍谓词的概念与表示方法

2．2 命题函数与量词

介绍命题函数、个体域、全总个体域的概念，重点介绍全称量词、存在量词的概念。

2．3 谓词公式与翻译

介绍谓词演算的合式公式的概念，重点介绍命题符号化的一般方法。

2．4 变元的约束

介绍指导变元、作用域、自由出现、约束出现、自由变元、约束变元的概念，介绍约束变元的换名规则及自由变元的代入规则。

2．5 谓词演算的等价式与蕴含式

介绍谓词公式的等价、有效、满足、不可满足的概念；介绍谓词演算的常用等价式和蕴含式以及多个量词的使用方法。

2．6 前束范式

介绍前束范式的概念及其理论。

2．7 谓词演算的推理理论

介绍谓词演算的推理规则及推理方法。

第三章 集合与关系

基本要求：理解集合的概念，熟练掌握集合的运算及其性质；理解序偶与笛卡尔积的概念；掌握关系的概念，熟练掌握关系的性质及运算；掌握集合的覆盖和划分的概念；熟练掌握等价关系和等价类的概念；理解相容关系及有关概念；理解集合的划分与等价关系间、集合的覆盖与相容关系之间的联系；熟练掌握偏序关系及有关概念。

重点：熟练掌握集合的运算及其性质；熟练掌握关系的概念、性质及运算；熟练掌握等价关系、偏序关系及其相关概念。

难点：基本概念的理解和掌握，定理的理解和应用。

主要内容：

3．1 集合的概念和表示法

介绍集合的概念及其表示法，着重介绍有关的基本概念和基本理论，如外延公理、子集、全集、空集、幂集等。

3．2 集合的运算

介绍集合的交、并、差、补、对称差等运算及其性质。

3．3 包含排斥原理

介绍用于有限个元素的计数问题的包含排斥原理。

3．4 序偶与笛卡儿积

介绍序偶、多元组及笛卡儿积的有关概念，重点介绍笛卡儿积的性质。

3．5 关系及其表示

介绍关系及其的有关概念，包括前域、值域、域、恒等关系以及关系的集合运算等，介绍关系的图与矩阵表示，即关系图与关系矩阵。

3．6 关系的性质

介绍关系可能具备的一些性质，包括自反性、反自反性、对称性、反对称性、传递性等，介绍关系的性质在关系图与关系矩阵中的反映。

3．7 复合关系和逆关系

介绍关系的复合运算与逆运算及这些运算的性质，介绍复合关系及逆关系的关系矩阵的求法。

3．8 关系的闭包运算

介绍关系的闭包运算，包括自反闭包、对称闭包、传递闭包的概念、性质及理论，特别是传递闭包矩阵的Warshall算法。

3．9 集合的划分和覆盖

介绍集合的划分和覆盖的概念及理论，包括最小划分、最大划分、交叉划分、划分的加细等。

3．10 等价关系与等价类

介绍等价关系、等价类及商集的概念，介绍等价关系与划分之间联系的有关定理。

3．11 相容关系

介绍相容关系、相容类、最大相容类完全覆盖的概念，介绍相容关系的最大相容类的求法，以及相容关系与覆盖之间、相容关系与完全覆盖之间联系的有关定理。

3．12 序关系

介绍偏序关系与偏序集、盖住、哈斯图、链与反链、全序关系与全序集、良序集、极大元、极小元、最大元、最小元、最小上界、最大下界等概念及相关理论。

第四章 函数

基本要求：掌握函数的概念及其基本性质；熟练掌握逆函数，复合函数的概念；熟练掌握基数以及可数集合与不可数集合的概念，理解基数的比较方法。

重 点：函数的概念及性质；可数集、不可数集、基数的概念及有关理论。

难 点：基数概念的理解；基数的比较。

主要内容：

4．1 函数的概念

介绍函数及有关概念，介绍几类特殊的函数，包括满射、入射、双射及它们之间的联系。

4．2 逆函数和复合函数

介绍函数的逆、函数的复合、常函数及恒等函数等概念和有关理论。

4．3 特征函数与模糊子集

此部分略去不讲。

4．4 基数的概念

介绍自然数的集合表示（G. Peano公理）；介绍等势、有限集、基数等概念及有关理论。

4．5 可数集与不可数集

介绍可数集与不可数集的概念及有关理论。

4．6 基数的比较

介绍了基数比较的概念、三歧性定理及基数的其他有关理论。

第五章 代数结构

基本要求：1．了解代数系统的定义，掌握集合上的二元运算及其性质。

2．理解半群、群、子群的概念，掌握其性质。

3．掌握阿贝尔群、循环群的概念及性质。

4．掌握陪集的概念和拉格朗日定理。

5．理解同态与同构的定义。

6．理解环与域的概念。

重点：

难点：

主要内容：

5．1 代数系统的引入

介绍运算及代数系统的概念。

5．2 运算及性质

介绍运算的有关性质，包括封闭性、可交换性、可结合性、可分配性、吸收性、等幂性等；介绍了左幺元、右幺元、幺元、左零元、右零元、零元、左逆元、右逆元、逆元的概念和有关理论。

5．3 半群

介绍广群、半群、子半群、独异点的概念及有关理论。

5．4 群与子群

介绍群、子群的有关概念和理论。

5．5 阿贝尔群和循环群

介绍循环群、循环群的有关概念

5．6 置换群与伯恩塞德定理

此部分略去不讲

5．7 陪集与拉格朗日定理

介绍陪集的概念，以及拉格朗日定理及其推论

5．8 同态与同构

介绍同态、同构及有关概念和理论；介绍同余的概念以及同态与同余关系的理论。

5．9 环与域

介绍具有两个运算的代数系统，主要是环与域的有关概念及理论。

第六章 格与布尔代数

基本要求：理解格的概念和性质；理解布尔代数和布尔表达式的概念。

重点：有补格和分配格的概念；Stone表示定理。

难点：分配格的判断；Stone表示定理的证明。

主要内容：

6．1 格的概念

介绍格的有关概念、性质以及格的同态与同构。

6．2 分配格

介绍模格、分配格的有关概念及性质。

6．3 有补格

介绍有补格的有关概念及性质。

6．4 布尔代数

介绍布尔格、布尔代数的有关概念及性质，给出Stone表示定理的证明。

6．5 布尔表达式

介绍布尔表达式的有关概念及性质。

第七章 图论

基本要求：掌握图的基本概念及性质；掌握路、通路、连通性、可达性的概念和理论；掌握图的矩阵表示；理解欧拉图和汉密尔顿图，能初步应用欧拉图和汉密尔顿图的知识解决一些实际问题；熟练掌握平面图的概念和性质；了解对偶图与着色；掌握解树的概念，熟练掌握树、根树的概念及性质。

重点：图的基本概念；无向图的连通性、有向图的可达性；邻接矩阵、可达性矩阵；平面图的概念及性质；根树及其应用。

难点：汉密尔顿图的应用；平面图的有关理论和应用。

主要内容：

7．1 图的基本概念

介绍图的基本概念。

7．2 路与回路

介绍路、回路、通路、连通性、点割集、边割集、单侧连通、强连通、弱连通等概念和理论。

7．3 图的矩阵表示

介绍图的邻接矩阵、可达性矩阵、完全关联矩阵。

7．4 欧拉图与汉密尔顿图

介绍欧拉图与汉密尔顿图的概念及理论。

7．5 平面图

介绍平面图的概念及理论。

7．6 对偶图与着色

介绍对偶图与图的着色理论。

7．7 树与生成树

介绍树、生成树、最小生成树的概念，介绍构造最小生成树的Kruskal算法。

7．8 根树及其应用

介绍根树、二叉树的概念和理论，介绍二叉树的应用。

三、各教学环节的学时分配

项目 章节	主要内容	学时分配
		讲课	习题课	实验	上机	合计
第一章	命题逻辑	10				10
第二章	谓词逻辑	8				8
第三章	集合与关系	13				13
第四章	函数	7				7
第五章	代数结构	10				10
第六章	格与布尔代数	6				6
第七章	图论	10				10
合计		64				64

四、本课程与其它课程的联系

本课程先修课程为高等数学、线性代数，后续课程为数据结构、操作系统、编译原理、算法分析、计算机逻辑设计、系统结构等。离散数学是计算机科学基础理论课程，基本内容包括数理逻辑、集合论、代数结构、图论四个方面，与计算机科学中的数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构容错诊断、机器定理证明等课程紧密联系。

五、建议教材及参考资料

建议教材：<<离散数学>>，左孝凌等，上海科学技术出版社，1996。

参考资料：<<离散数学>>，耿素云编，清华大学出版社，1995。