《离散数学》考试大纲

一、 适用专业 : 计算机应用技术 计算机技术

二、 题目类型：填空、选择、证明、应用

三、 参考书目：

1、 《离散数学》，左孝凌、李为鑑、刘永才编著，上海科学技术文献出版社

2、 《离散数学》，耿素云、屈婉玲等编著，清华大学出版社

四、 基本内容：

理解命题逻辑的基本概念及应用方法；掌握谓词逻辑的基本概念及应用方法；熟练掌握集合、关系函数的基本概念及运算、论证方法；理解代数结构的基本概念及研究方法；掌握图论的概念及应用。

1． 数理逻辑

（1） 命题逻辑

1） 理解下列基本概念：

命题，联结词，合式公式，真值指派和真值表，永真式、永假式和可满足式，等价式与蕴涵式，规范式。

2） 掌握命题符号化的方法；

3） 熟练掌握基本等价式和蕴涵式及其应用；

4） 理解和掌握推理规则（ P 、 T 、 CP 规则），直接证法和间接证法。

（2） 谓词逻辑

1） 理解下列基本概念：谓词，量词，变元的约束，谓词公式；

2） 能用谓词公式表达自然语句表述命题；

3） 熟练掌握基本谓词的演算式和蕴涵式及其应用；

4） 理解和掌握谓词演算的推理理论（推论规则 US 、 ES 、 UG 、 EG ）；

5） 了解前束范式。

2． 集合、关系与函数

（1） 理解下列基本概念：

集合，基数，序偶与笛卡尔集；关系，二元关系，逆关系，复合关系，序关系，关系的性质及闭包，等价关系 ，等价类，覆盖与划分；映射与函数，逆函数，复合函数。

（2） 了解可数无限集与不可数无限集的势的概念；

（3） 掌握集合运算；

（4） 熟练掌握集合相互包含和相等的论证方法；

（5） 掌握关系闭包运算；

（6） 理解等价关系与划分的内在联系；

（7） 能正确区分单（入）射、满射和双射。

3． 代数结构

（1） 理解下列基本概念：

代数系统，幺元，零元，逆元，同态与同构，同余关系，商代数，积代数；半群，独异点，群（包括 Abel 群，循环群，置换群），子群，陪集，正规子群，商群，环和域；偏序及哈斯图，格分配格，有补格，布尔代数。

（2） 理解拉格郎日定理及其推论；

（3） 掌握哈斯图的作法；

（4） 了解代数系统的分类及研究方法。

4． 图论

（1） 理解下列基本概念：

图，结点的度数，路径、回路与连通性，赋权图，欧拉图，哈密尔顿图，平面图，对偶图与着色，树、生成树、根树及最优树。

（2） 掌握图的矩阵表示；

（3） 掌握赋权图的最短路径求法；

（4） 了解和掌握关于平面图的 欧拉公式及其应用；

（5） 能求边赋权图的最小生成树；

（6） 能将 n 元树转换为二叉树来表示；

（7） 能画出带有一组权值的最优树，并给出哈夫曼编码 。