离散数学复习.docx

总复习（一）第一章

1. 基本概念

命题、命题常元、命题变元、命题的解释或赋值、原子命题(简单命题)、复合命题、否定联结词、合取、析取、可兼或、不可兼或、条件、双条件、常值命题、命题变量、命题公式、命题公式的解释、真值表、永真公式(重言式)、永假公式(矛盾式，不可满足公式)、可满足公式、公式的等价、对偶（公）式、对偶原理、子句、短语、析取范式、合取范式、主析取

（主合取）范式、极小项、极大项二、基本要求

1、深刻理解五种常用联结词的涵义，并能准确地应用它们将基本命题及复合命题符号化。

2、熟练地写出给定命题公式的真值表

3、牢记基本等价式的名称及它们的内容；

4、熟练地应用基本等价式及置换规则进行等价演算

5、熟练掌握求主析取（主合取）范式的方法

6、理解并牢记9类基本蕴涵关系式和蕴涵的基本性质

7、牢记各条推理规则的内容及名称

8、熟练掌握推理的各种方法（直接法、利用CP规则、反证法）第二章

全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词符号、谓词公式、公式的解释、永真公式(重言式)、永假公式(矛盾式，不可满足公式）、可满足公式、前束范式、母式、前束合取(或析取)范式、Skolem范式、US(全称指定规则)、ES(存在指定规则)、UG(全称推广规则)、EG(存在推广规则)

能准确地将给定命题符号化

深刻理解全称量词、存在量词及量词的辖域、全总个体域的概念能准确理解约束变元(量)和自由变元的概念

掌握约束变元的改名规则和自由变元的代入规则能熟练地运用US、ES、UG、EG规则进行推理第四、五章

关系、n元关系、空关系、二元关系、全关系、关系矩阵；关系的交、并、补、差、复合、幂、逆；自反闭包、对称闭包、传递闭包；等价关系、以m为模的同余关系、等价类、生成元、偏序关系、偏序集、偏序集的哈斯图、最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界、全序关系、良序关系、良序集

1、熟练掌握关系的性质和运算

2、熟练运用Warshall算法计算关系的传递闭包

3、熟练掌握偏序关系的哈斯图的画法以及由哈斯图给出相应的偏序关系

4、熟练掌握求偏序集中子集的最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界的方法

5、熟练掌握利用关系的性质和定义进行证明第六章

一、基本概念

复合函数、单射、满射、双射、置换、单位(恒等)置换、循环、逆函数

二、基本要求

1、熟练掌握判断函数是否为单射、满射、双射的方法

2、熟练掌握置换的复合运算和置换表示成循环的积的方法第十章

无序对、结点、边、阶、无向图、有向图、邻接点、邻接边、环、孤立结点、零图、平凡图、(n，m)图、简单图、基图、广义图（伪图）、多重图、平行边、赋权图、无权图、结点的度数、出度、入度、正则图、k度正则图、子图、真子图、生成子图、平凡子图、删点子图、删边子图、点诱导子图、边诱导子图、完全图、补图、二部图、完全二部图、图的同构

道路、道路的长度、零道路、开道路、闭道路、简单道路、回路、基本道路、圈、道路图、圈图、距离、连通图、非连通图、图的支、点割集、基本割集、割点、边割集、基本边割集、割边、连通度、边连通度、可达的、单向连通图、强连通图、弱连通图、强分图、单向分图、弱分图、邻接矩阵、零矩阵、单位矩阵、可达性矩阵

二、基本要求

1、熟练掌握Euler基本定理及推论

2、熟练掌握邻接矩阵、可达性矩阵的计算方法

3、熟练掌握强分图的计算方法

4、熟练掌握利用邻接矩阵计算图中道路和回路数目的方法

第十一、十二、十三章一、基本概念

树、树叶、枝点、生成树、树枝、树补边、最小生成树、有向树、根树、有序树、子树、二叉树、完全二叉树、最优二叉树、平面图、面、对偶图、欧拉道路、欧拉图、哈密尔顿道路、哈密尔顿圈、哈密尔顿图

二、基本要求

1、熟练掌握树的六个等价命题

2、熟练掌握利用Kruskal算法求最小生成树

3、熟练掌握判定平面图的三个必要条件

4、熟练掌握判定欧拉图和欧拉道路的充分必要条件

5、熟练掌握判定哈密尔顿图和哈密尔顿道路的几个充分和必要条件第十四～十七章

一、基本概念

代数系统、单位元或幺元、零元、幂等元、逆元、半群、含幺半群、群、子半群、群的阶、子群、生成子群、交换群、循环群、生成元、元素的周期、右陪集、左陪集、陪集的性质、子群的指数、不变子群(或正规子群)、环、含零因子环、交换环、含幺环、整环、子环、域、格、代数格、偏序格、子格、分配格、有界格、有补格、有补分配格、布尔格、布尔代数

二、基本要求

1、熟练掌握群、环、域的基本性质和证明方法（按定义证明和反证法）