《离散数学》考试要点

    以下是偶整理的《离散数学》考查要点，

    希望对大家的复习备考有所帮助。

    参考书：《离散数学》左孝凌等编著，上海科学技术文献出版社出版

    ----------------------------------------------

    数理逻辑

    考查要点：公式推演，谓词演算，符号化推理。

    第一章：命题逻辑

    符号化命题，命题定律；

    重言式、蕴含式及其性质；

    主合取范式、主析取范式，二者的关系（必考题，一般运算较繁，应力求熟练）；

    推理理论，基本蕴含式和等价式（p43）；

    1-9节略过。

    第二章：谓词逻辑

    基本概念；

    用谓词公式符号化命题；

    了解变元的约束；

    谓词演算的等价式与蕴含式，

    熟悉表2-5.1中的等价式和蕴含式，理解p70页的例子；

    了解前束范式；

    谓词演算的推理理论，熟悉基本规则，

    注意存在量词和全称量词的消去顺序，

    关于UG规则的使用，请参考往年试题中方法。

    -----------------------------------------------

    集合论

    考查要点：基本概念；关系及其性质，等价关系与等价类，序关系。

    第三章：集合与关系

    集合运算；

    关系、关系矩阵、关系图；

    关系的性质；

    复合关系、逆关系，复合关系矩阵的构造；

    了解关系的闭包运算，Warshall算法；

    划分与覆盖的概念；

    等价关系、等价类，商集，相关性质；（重点）

    命题：集合A上的等价关系个数，等于A的划分种数；（常用于辅助计算）

    了解相容关系、相容类、最大相容类；

    偏序关系、偏序集，哈斯图；

    链和反链的概念；

    了解全序集合、全序关系；

    了解概念极大元、极小元，最大元、最小元，上确界、下确界；

    了解良序集。

    第四章：函数

    函数概念，函数相等；

    满射（即到上映射）；

    入射（即单射、一对一映射）；

    双射（即一一对应）；

    其它略过。

    -----------------------------------------------

    代数系统

    考查要点：运算及性质，群理论，拉格朗日定理及推论。

    第五章：代数结构

    运算及性质，运算表；

    群，有限群的阶，群中元素的幂；

    群的几个定理；

    子群，交换群，循环群；

    命题：循环群中，若a为生成元，则a的逆元也是生成元；

    生成元阶与有限循环群的阶的关系；

    5-6节略过；

    陪集与拉格朗日定理，定理推论；

    了解同态与同构中的几个概念；

    5-9节略过。

    第六章：格和布尔代数

    格与子格的概念，对偶原理；

    格的基本性质；

    分配格及其性质；

    略过模格；

    有补格一节中的概念；

    布尔代数；

    原子；

    Stone表示定理及推论；

    了解布尔表达式。

    -----------------------------------------------

    图论

    考查要点：图论基本概念，性质。

    第七章：图论

    基本概念；

    完全图的性质，补图，图的同构；

    补充：鸽巢原理；

    路与回路；

    连通分支和连通图；

    点/边割集，连通度；

    有向图的可达性；

    单侧连通、强连通、弱连通；

    强分图、弱分图、单侧分图；

    邻接矩阵、可达性矩阵、完全关联矩阵；

    Warshall算法；

    了解关联矩阵的秩；