2021辽宁石油化工大学离散数学专业研究生考试大纲

一、 考试要求：

1、掌握命题逻辑和谓词逻辑的基本概念及逻辑推理；

2、掌握集合、关系、函数的基本概念，集合与关系的各种运算方法；

3、掌握图与树的基本概念及表示方法；

3、掌握形式语言与自动机的基本概念与基本原理。

二、 考试内容：

1、数理逻辑

（1）命题逻辑：①命题及其表示法；②联结词；③命题公式与翻译；④真值表与等价公式；⑤重言式与蕴含式；⑥对偶与范式；⑦推理理论；⑧数理逻辑应用。　

（2）谓词逻辑：①谓词的概念与表示；②命题函数与量词；③谓词公式与翻译；④变元的约束；⑤谓词演算的等价式与蕴含式；⑥前束范式；⑦谓词演算的推理理论。

2、集合论

（1）集合与关系：①集合的概念和表示法；②集合的运算；③包含排斥原理；　④序偶与笛卡尔积；⑤关系及其表示；⑥关系的性质；⑦复合关系和逆关系；⑧关系的闭包运算；⑨集合的划分和覆盖； 10等价关系与等价类； 11相容关系； 12序关系。

（2）函数：①函数的概念；②逆函数和复合函数；③特征函数与模糊子集；④基数的概念；⑤可数集与不可数集；⑥基数的比较。

3、代数系统

（1）代数结构：①代数系统的引入；②运算及其性质；③半群；④群与子群；⑤阿贝尔群和循环群；⑥置换群与伯恩赛德定理；⑦陪集与拉格朗日定理；⑧同态与同构；⑨环与域。

（2）格和布尔代数：①格的概念；②分配格；③有补格；④布尔代数；⑤布尔表达式。

4、图论

（1）图论：①图的基本概念；②路与回路；③图的矩阵表示；④欧拉图与汉密尔顿图；⑤平面图；⑥对偶图与着色；⑦树与生成树；⑧根树及其应用。

5、计算机科学中的应用

（1）形式语言与自动机：①串和语言；②形式文法；③有限状态自动机；④有限状态机的简化；⑤有限状态机与正则语言。