沈阳建筑大学2005级硕士研究生复试《离散数学》考试大纲
一、适用专业:计算机应用技术
二、题目类型：填空、选择、证明、应用
三、参考书目：
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）能画出带有一组权值的最优树，并给出哈夫曼编码 。
一、适用专业:计算机应用技术
二、题目类型：填空、选择、证明、应用
三、参考书目：
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）能画出带有一组权值的最优树，并给出哈夫曼编码 。