考试大纲

来源：自考过程考核  2023-09-14 17:28 字体： 放大 正常 缩小 打印
《离散数学》考试大纲
　　
第1章　命题与命题公式

　　一、课程内容
　　1.1 命题与命题联结词
　　1.2 命题公式的等值演算
　　1.3 联结词完备集
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生理解命题、命题联结词、命题公式、真值表等基本概念，掌握联结词的定义及运算次序，掌握重言式、矛盾式和可满足公式的定义并能进行正确识别，掌握命题公式等值和蕴涵的含义，掌握命题公式的等值演算公式。
　　本章的重点是命题及命题联结词、将命题符号化、命题公式的真值表、命题公式的化简及命题的等值演算。
　　本章的难点是命题公式的化简及等值演算及其应用。
　　
　　三、考核内容与考核要求
　　1.命题与命题联结词，要求达到“领会” 层次。
　　1.1 命题与命题的表示 , 能对命题进行符号化。
　　1.2 复合命题与联结词，掌握命题联结词，能够使用联结词熟练构造复合命题。
　　2.命题公式的等值演算，要求达到“简单应用” 层次。
　　2.1 命题公式，掌握命题公式的概念，能够构造命题公式的真值表，能够正确判别重言式、矛盾式和可满足公式。
　　2.2 等值演算与蕴涵式，熟记常用的命题定律和蕴涵式，掌握命题公式的等值关系和蕴含关系，能够进行简单的公式论证。
　　3.联结词完备集，要求达到“领会” 层次。
　　
第2章　命题逻辑的推理理论

　　一、课程内容
　　2.1 范式
　　2.2 主范式
　　2.3 自然推理系统
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生理解范式、小项与大项、主范式等基本概念，要求考生能够熟练进行命题公式的化简与主范式表示；理解推理的概念，掌握推理中的形式证明方法，使用命题逻辑的推理理论及相关规则正确进行命题推理。
　　本章的重点是命题公式的主范式表示及其相互转换，使用P 规则、T 规则及CP规则进行命题推理。
　　本章的难点是命题推理及其应用。
　　
　　三、考核内容与考核要求
　　1.范式，要求达到“领会” 层次。
　　1.1 范式的概念，掌握范式的概念及性质，能够正确计算给定公式的范式。
　　1.2 小项与大项，掌握小项与大项的概念及性质，能够正确计算给定公式的成真赋值、成假赋值及对应的编码。
　　2.主范式，要求达到“简单应用” 层次。
　　2.1 主析取范式，掌握主析取范式的概念及性质，能够正确计算给定公式的主析取范式。
　　2.2 主合取范式，掌握主合取范式的概念及性质，能够正确计算给定公式的主合取范式。
　　3.自然推理系统，要求达到“简单应用” 层次。
　　正确理解有效推理概念，掌握推理理论和推理规则，能够使用真值表法、主范式方法和推理法进行正确的论证。
　　
第3章　谓词逻辑

　　一、课程内容
　　3.1 谓词的概念与表示
　　3.2 量词与合式公式
　　3.3 谓词演算的等价式与蕴涵式
　　3.4 前束范式
　　3.5 谓词演算的推理理论
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生在学习了命题知识的基础上，进一步掌握谓词理论。理解谓词的概念及表示，包括个体词、谓词和量词、个体变元、量词的辖域、谓词公式。掌握谓词演算的等值公式及蕴涵式，理解前束范式概念，熟练掌握谓词运算的推理理论。
　　本章的重点是使用谓词及量词表示相关命题并能确定量词的辖域，能将带量词的公式变换为等价的前束范式，能进行正确的谓词演算推理。
　　本章的难点有两个，一是带量词的公式变换，即将公式变换为等价的前束范式。二是能够进行谓词演算推理。
　　
　　三、考核内容与考核要求
　　1.谓词的概念与表示，要求达到“领会” 层次。
　　理解谓词、个体词、命题函数的概念，能使用谓词表示相关命题。
　　2.量词与合式公式，要求达到“识记” 层次。
　　理解全称量词、存在量词的概念，能够使用谓词与恰当的量词表示命题，理解合式公式并能够正确判别，能指明合式公式中的指导变元、量词的辖域、个体变元的自由出现和约束出现等。能使用约束变元改名规则和自由变元代入规则改写命题公式。
　　3.谓词演算的等价式与蕴涵式，要求达到“领会” 层次。
　　理解对谓词公式赋值的含义，掌握谓词演算的规则，熟记谓词演算的等值式与蕴涵式。
　　4.前束范式，要求达到“简单应用” 层次。
　　理解前束范式概念，能够将所给公式变换为等值的前束范式。
　　5.谓词演算的推理理论，要求达到“简单应用” 层次。
　　掌握谓词演算的推理理论，能够进行正确的构造推理证明。
　　
第4章　集　合

　　一、课程内容
　　4.1 集合的基本概念
　　4.2 集合的运算
　　4.3 有序对与笛卡儿积
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生理解集合、有序对及笛卡儿积的概念，能判别集合之间的相等、包含等关系，能够采用谓词、图示法表示集合，能正确进行集合之间的求并、交、补、差及集合的幂集的运算，能够运用集合成员及运算恒等式进行相关证明。
　　本章的重点是集合的表示、集合的幂集及集合的运算、集合恒等式的证明。
　　本章的难点是集合的运算及集合恒等式的证明。
　　
　　三、考核内容与考核要求
　　1.集合的基本概念，要求达到“领会” 层次。
　　1.1 集合的概念，了解可数集与不可数集及基数的比较。
　　1.2 集合的表示法，包括列举法、描述法及图示法，了解子集的概念，能判别集合之间的相等、包含等关系。
　　2.集合的运算，要求达到“简单应用” 层次。
　　2.1 集合的基本运算，能正确计算集合的并、交、补及差，能正确求出集合的幂，领会集合运算满足的性质。
　　2.2 集合运算的恒等式，掌握集合运算的相关公式，能运用集合的运算定律进行集合恒等式的证明。
　　3.有序对与笛卡儿积，要求达到“简单应用” 层次。
　　3.1 有序对，掌握有序对、有序n元组的概念，掌握有序对的集合性定义及相关定理。
　　3.2 笛卡儿积，掌握笛卡儿积的定义及性质。
　　
第5章　关系与函数

　　一、课程内容
　　5.1 关系及关系的性质
　　5.2 关系的运算
　　5.3 等价关系与序关系
　　5.4 函数
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生理解集合上的关系及其三种表示方法，掌握关系的常规运算、复合关系及逆关系，掌握等价关系、相容关系、序关系等的性质，能够对所给关系进行判别。
　　同时，本章还要学习函数的概念，理解函数的定义域和值域，领会单射、满射和双射的定义，并能对所给函数进行判别，准确理解反函数和复合函数的定义。
　　本章的重点是集合上的关系及其运算、函数及其运算。
　　本章的难点是对等价关系、相容关系、序关系等的判定与证明。
　　
　　三、考核内容与考核要求
　　1.关系及关系的性质，要求达到“领会” 层次。
　　1.1 关系的定义及表示，掌握关系的定义及三种表示方法，掌握关系的定义域与值域。
　　1.2 关系的性质，理解关系的性质，包括自反性、对称性、传递性、反自反性和反对称性，能进行正确的判别。
　　2.关系的运算，要求达到“领会” 层次。
　　2.1 关系的常规运算，能正确进行关系的运算。
　　2.2 复合运算，理解复合关系概念，能正确进行关系的复合运算。
　　2.3 关系矩阵的布尔运算，理解关系矩阵的定义，熟练进行关系矩阵的计算。
　　2.4 关系的闭包，理解关系的自反、对称和传递闭包，能正确进行计算、表示及判别。
　　3.等价关系与序关系，要求达到“简单应用” 层次。
　　3.1 等价关系，掌握等价关系、等价类、划分等概念，能对给定的关系进行正确判别。
　　3.2 序关系，掌握偏序关系、拟序关系及全序关系，能正确画出表示偏序关系的哈斯图，对给定的关系能正确判别，正确求出偏序关系中的极大（小）元、最大（小）元。
　　4.函数的概念，要求达到“领会” 层次。
　　4.1 函数的概念，掌握函数的概念，能正确判别所给关系是否为函数，是否是单射、满射、双射等。
　　4.2 复合函数，理解复合函数概念，正确计算函数的复合。
　　
第6章　代数系统的一般概念

　　一、课程内容
　　6.1 代数系统
　　6.2 群与半群
　　6.3 环与域
　　
　　二、学习目的与要求
　　本章要求考生了解代数系统的定义、运算及其性质，掌握半群、独异点、群、环和域的概念，掌握子群的概念并能进行正确的判别。
　　本章的重点是能正确判别半群、独异点、群、环等。这些也是本章的难点。
　　
　　三、考核内容与考核要求
　　1.代数系统，要求达到“领会” 层次。
　　正确理解运算及运算的封闭性、运算的结合律、交换律、幂等律、分配律和吸收律等，理解幺元、零元、幂等元及逆元的概念，并能正确计算。
　　2.群与半群，要求达到“领会” 层次。
　　2.1 半群与独异点，正确理解半群和独异点并能进行判别。
　　2.2 群，正确理解群及子群的概念，并能进行判别，掌握子群的判别条件。
　　3.环与域，要求达到“识记” 层次。
　　正确理解环与域的概念并能进行判别。
　　
第7章　格与布尔代数

　　一、课程内容
　　7.1 格的基本概念
　　7.2 分配格与有补格
　　7.3 布尔代数
　　
　　二、学习目的与要求
　　本章在已了解偏序集的基础上，要求考生掌握格与布尔代数的概念，更深入地领会偏序集的最大元素、最小元素的确切含义，及偏序集中两个元素的子集是否存在最小上界和最大下界的概念及判别方法，能正确判别并计算这些元素。掌握分配格、有补格的概念及性质，理解布尔代数的概念。
　　本章的重点是格、分配格、有补格的概念及性质。这些内容也是本章的难点。
　　
　　三、考核内容与考核要求
　　1.格的基本概念，要求达到“领会” 层次。
　　1.1 格的定义，掌握格的概念，正确理解偏序集中任意两个元素的最大下界、最小上界的概念并能正确判别这些元素是否存在。
　　1.2 格的性质，领会格的性质，掌握格的两种不同的定义方法及它们之间的联系，能正确判别所给偏序集是否是一个格。
　　2.分配格与有补格，要求达到“领会” 层次。
　　2.1 分配格，领会分配格的定义并能正确判别。
　　2.2 有补格，领会有补格的定义并能正确判别。
　　3.布尔代数，要求达到“识记” 层次。
　　了解布尔代数的概念。
　　
第8章　图

　　一、课程内容
　　8.1 图的基本概念
　　8.2 图的连通性
　　8.3 图的表示
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生熟悉图的定义、表示方法、有关术语和基本概念，领会图、完全图、连通图、子图、通路等概念，掌握图的邻接矩阵表示方法。
　　本章的重点是图的定义、相关的性质以及判别方法，图的邻接矩阵表示法。
　　本章的难点是路径矩阵。
　　
　　三、考核内容与考核要求
　　1.图的基本概念，要求达到“识记” 层次。
　　了解有向图、简单图、完全图、零图、图的阶、子图、生成子图、无向图、关联、邻接、顶点的度、自补图等基本概念，熟记图的相关性质。
　　2.图的连通性，要求达到“领会”层次。
　　了解通路、回路、简单通路、简单回路、初级通路和初级回路的定义并能进行识别，了解图的连通性质。
　　3.图的表示，要求达到“ 简单应用” 层次。
　　能使用邻接矩阵表示图，能根据邻接矩阵找出图的相关元素，了解邻接矩阵幂的含义。
　　
第9章　图的应用

　　一、课程内容
　　9.1 欧拉图与哈密顿图
　　9.2 平面图
　　9.3 树及其遍历
　　
　　二、学习目的与要求
　　本章的学习目的是要求考生领会欧拉图和哈密顿图的概念并能够进行判别，领会平面图的概念并能进行判别，理解并熟记树、二叉树、生成树和最小生成树的概念，掌握二叉树的三种遍历方法，能够证明或计算树中关于结点及边的一些数量关系，可以利用所学知识解决树的综合应用问题。
　　本章的重点是欧拉图和哈密顿图的判别、平面图的判别及二叉树的相关性质及遍历方法。
　　本章的难点是欧拉图和哈密顿图的判别、平面图的判别。
　　
　　三、考核内容与考核要求
　　1.欧拉图与哈密顿图，要求达到“简单应用” 层次。
　　1.1 欧拉图，了解欧拉回路、欧拉图的定义，领会欧拉定理，能够判别图是否是欧拉图。
　　1.2 哈密顿图，了解哈密顿图的定义及关于哈密顿路的相关定理，能够判别图是否是哈密顿图，并能够使用相关性质解决一些简单应用问题。
　　2.平面图，要求达到“简单应用” 层次。
　　了解平面图的定义，能够判别图是否是平面图。
　　3.树及其遍历，要求达到“综合应用” 层次。
　　3.1 树的基本概念，掌握树的基本概念及相关性质，能够进行树中相关的计算问题。
　　3.2 二叉树的基本概念，掌握二叉树的基本概念及相关性质。
　　3.3 二叉树与树的遍历，掌握二叉树的三种遍历方法。