南京理工大学离散数学2011年考研大纲
离散数学考试大纲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
页:
[1]