考研

　　离散数学考试大纲

　　1 演算基础

　　1.1 与联结词

　　① ②联结词 ③合式公式 ④的符号化

　　1.2 真假性

　　①解释 ②等价公式 ③联结词的完备集 ④对偶式和内否式。

　　1.3 范式及其应用

　　①范式 ②主范式

　　2 演算的推理理论 1 演算的公理系统

　　①公理系统的组成部分 ②公理系统的推理过程 2 演算的假设推理系统

　　①假设推理系统的组成 ②假设推理系统的推理过程 3 演算的归结推理法

　　①归结证明过程②归结证明方法

　　3 谓词演算基础 1 谓词和个体

　　①个体 ②谓词 ③语句的符号化 2 函数和量词

　　①函数项 ②量词 4 永真性和可满足性

　　①真假性 ②同真假性 ③永真性和可满足性 ④范式

　　4 谓词演算的推理理论 1 谓词演算的永真公理系统

　　①公理系统的组成部分 ②公理系统的推理过程 2 谓词演算的假设推理系统

　　①假设推理系统的组成及证明方法 ②定理的推导过程 3 谓词演算的归结系统

　　①置换 ②归结反演系统 ③霍恩子句逻辑程序

　　5递归函数论 1 数论函数和数论谓词 2 函数的构造

　　6 集合

　　6.1 集合的基本概念

　　①集合;②子集合;③空集合;④集合的相等。

　　6.2 集合的基本运算

　　①集合的运算;②集合的交;③集合的并;④集合的差;⑤集合的对称差;⑥集合的广义交;

　　⑦集合的广义并;⑧幂集合。

　　6.3 全集和集合的补

　　①全集;②集合的补;③德·摩根定律。

　　6.4 自然数与自然数集

　　①自然数;②自然数集;③数学归纳法;④集合的归纳定义。

　　6.5 包含与排斥原理

　　①有限集;②包含与排斥原理。

　　7 关系

　　7.1 集合的笛卡尔积集

　　①有序对;②集合的笛卡尔积集;③有序n(n2)元组;④n重(n2)笛卡尔积集。

　　7.2 二元关系的基本概念

　　①二元关系;②二元关系的表示;③二元关系的图形表示;④二元关系的矩表示;⑤二元关系的运算;⑥二元关系的复合运算;⑦二元关系的逆关系。

　　7.3 二元关系的性质

　　①二元关系的性质;②自反的二元关系;③反自反的二元关系 ;④对称的二元关系;⑤反对称的二元关系;⑥传递的二元关系。

　　7.4 二元关系的闭包运算

　　①二元关系的闭包运算;②自反闭包;③对称闭包;④传递闭包。

　　7.5 等价关系与集合的划分

　　①等价关系;②等价类;③集合的划分;④商集合。

　　7.6 偏序关系和格

　　①偏序关系;②偏序集;③极大元;④极小元;⑤最大元;⑥最小元; ⑦最小上界;⑧最大下界;⑨可比;⑩覆盖;⑾有序集;⑿良序集;⒀格。

　　8 函数与集合的势

　　8.1 函数的基本概念

　　①函数(映射);②定义域;③陪域;④值域;⑤象集;⑥原象集;⑦单射函数;⑧满射函数;⑨双射函数。

　　8.2 函数的复合与可逆函数

　　①函数的复合;②左可逆函数;③右可逆函数;④可逆函数。

　　8.3 无限集

　　①集合的势;②无限集;③集合的势相等;④可数无限集;⑤不可数无限集; ⑥集合势大小的比较。

　　9 图论

　　9.1 图的基本概念

　　①有向图;②无向图;③顶点集;④边集;⑤自环;⑥孤立点;⑦多重边;⑧简单图;⑨完全图;⑩关联;⑾邻接;⑿图的同构;⒀子图;⒁生成子图;⒂补图;⒃图的顶点度数(次数);⒄图的顶点度数和与边数关系。

　　9.2 图中的通路、图的连通性与图的矩阵表示

　　①图中的通路;②简单通路;③初等通路;④回路;⑤简单回路;⑥初等回路(圈);⑦连通图;⑧有向连通图;⑨有向单侧连通图;⑩有向强连通图;⑾ 图的邻接矩阵;⑿图的关联矩阵;⒀图的可达矩阵。

　　9.3 带权图与带权图中最短通路

　　①带权图;②带权图的最短通路;③狄克斯瑞(Dijkstra)算法。

　　9.4 欧拉图

　　①欧拉图;②欧拉通路;③欧拉回路;④欧拉定理。

　　9.5 哈密尔顿图与货郎担问题

　　①哈密尔顿通路;②哈密尔顿回路(圈);③哈密尔顿图;④哈密尔顿图的必要条件;⑤哈密尔顿图的充分条件;⑥货郎担问题;⑦最邻近算法。

　　9.6 二部图

　　①二部图(偶图);②二部图的充要条件;③二部图的匹配;④二部图的极大匹配;⑤二部图的完美匹配。

　　9.7 平面图

　　①平面图;②平面图的欧拉定理;③平面图的必要条件;④平面图的区域着色。

　　10 树

　　10.1 树的基本概念

　　①树;②树中顶点与边关系公式;③树的等价定义。

　　10.2 连通图的生成树与带权图的最小生成树

　　①连通图的生成树;②割集;③割集与生成树的关系;④带权图最小生成树的算法。

　　10.3 有序树

　　①有向树;②根树;③有序树;④有序n (n2)分树;⑤正则有序n (n2) 分树。

　　10.4 前缀码和最优二分树

　　①前缀码;②带权图的最优二分树;③霍夫曼(Huffman)算法。

　　11 群和环

　　11.1 代数运算的基本概念

　　①二元运算;②封闭的二元运算;③可结合的二元运算;④可交换的二元运算;⑤n元运算

　　11.2 代数系统和半群

　　①代数系统;②左么元;③右么元;④么元;⑤半群;⑥含么半群(独异点);⑦半群的同态;⑧子半群;⑨子含么半群。

　　11.3 群的基本概念

　　①左逆元;②右逆元;③逆元;④群;⑤有限群;⑥交换群;⑦群同态;⑧群同构;⑨群中元素的阶。

　　11.4 变换群和置换群

　　①变换含么半群;②变换群;③置换群;④n个文字对称群。

　　11.5 循环群

　　①循环群。

　　11.6 子群、群的子集生成的群

　　①子群。

　　11.7 子群的陪集

　　①子群的陪集;②子群在群中的指数;③群中拉格朗日定理。

　　11.8 正规子群、商群、群同态

　　①正规子群;②商群;③群的同态基本定理。

　　主要参考教材：朱保平,叶有培,张琨.离散数学.北京：北京理工大学出版社，2006