离散数学复习提纲

《离散数学复习提纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《离散数学》复习提纲2014.5第一章命题逻辑■命题符号化及联结词■命题公式及分类■等值演算会运用等值式(P9)证明两个公式是否相等、判断公式的类型(P33:7-9)■对偶与范式求命题公式的(主)析取范式及用途、(主)合取范式(P33：12，13)第一章命题逻辑■联结词全功能集复合联结词、N个命题变项可构成的不等价的命题公式数■推理理论推理的形式结构、常用推理规则(P23)构造证明法（直接证明法、附加前提证明法、反证法）(P34-35：18,19)■本章的应用P11例11，P27例28，P34：15第二章一

2、阶逻辑■一阶逻辑基本概念、命题符号化■一阶逻辑公式、解释及分类公式的解释、代换实例(P53-54：5，13)■一阶逻辑等值式、前束范式量词否定等值式（P46）量词辖域收缩和扩张等值式(P47)量词分配等值式(P47)第二章一阶逻辑■一阶逻辑推理理论有关量词的推理规则(EI,EG,UI,UG)及运用■本章应用例：证明:“金属都是导电体,铜是金属，所以铜是导电体。”解：令F(x):x是金属,G(x):x是导电体,a:铜前提：∀x(F(x)→G(x))，F(a)结论：G(a)涉及到证明：①F(a)前提引入➢命题的

3、符号表示②∀x(F(x)→G(x))前提引入➢有关量词的推理规则③F(a)→G(a)②UI➢量词的等值式④G(a)①③假言推理第三章集合的基本概念和运算■集合的基本概念集合之间的关系、∅、E、幂集，文氏图■集合的基本运算会运用集合运算算律(P60-61)证明有关集合运算的命题成立与否、进行化简■集合中元素的计数(本章应用)包含排斥原理（P63例9，10，P65-67例11-13）第四章　二元关系与函数■集合的笛卡儿积与二元关系会计算和运用笛卡儿积的性质(P83)证明命题成立与否重要关系(∅、E、I、L、D、

4、⊆)■关系的运算dom、ran、fld，R-1和合成R∘S、关系上的幂运算■关系的性质(判断、证明)自反性、反自反性、对称性、反对称性、传递性关系运算与性质的关系(P87)、关系性质的充要条件■关系的闭包对称闭包、自反闭包和传递闭包的定义和构造方法第四章　二元关系与函数■等价关系和偏序关系等价类，商集、划分及其关系哈斯图，偏序集的特定元素及性质■函数的定义和性质满射、单射、双射的性质、判断双射函数的构造■函数的复合和反函数函数复合运算及性质，反函数的计算■本章应用等价类及划分,构造双射函数第五章图的基本概念

5、■无向图及有向图握手定理、推论及应用图的同构条件及判断完全图、正则图、生成子图、自补图■通路、回路、图的连通性无向图和有向图的连通性，点割集、边割集■图的矩阵表示关联矩阵、邻接矩阵及性质会计算图中指定长度的通路和回路的个数(P126)■最短路径和关键路径（本章应用）P129例3，P130例4，P138：19，20第六章特殊的图■二部图——完全二部图、匹配、Hall定理及应用。■欧拉图——(半)欧拉图的定义及判别方法。■哈密顿图(半)哈密顿图的定义及存在性的充分条件和必要条件。■平面图平面图的面、次数及它们之

6、间的关系极大平面图、极小非平面图欧拉公式及推广(定理6.10,6.11)平面图判定定理(定理6.13,6.14)对偶图的构造和性质■本章应用二部图(P154:5)，哈密顿回路(P154:15),平面图第七章树■无向树及生成树无向树，（最小）生成树基本回路系统，基本割集系统树的性质及有关定理（定理7.1-7.3）■根树及其应用（本章应用）有向树及根树，根树的分类最优树，前缀码与最佳前缀码（P164例7）第八章组合分析初步■加法法则和乘法法则■基本排列组合的计数方法多重集的组合与排列公式(定理8.6，定理8.7

7、)■递推方程的求解与应用递推方程的定义和求解过程(P181-182例13，14)《离散数学》试题结构卷面各部分分数比例一.选择题（20%）第一部分数理逻辑(30%)二.填空题（20%）第二部分集合论(30%)三.计算题（20%）第三部分图论(30%)四.证明题（20%）第四部分组合分析(10%)五.应用题（20%）《离散数学》试题举例一.选择题（20%）1．设A、B、C为任意集合，则下列命题中，命题真值是真的是。A．若A∪B=A∪C，则B=CB.若A－B=∅，则A=BC．若A∩B=A∩C，则B=CD.∅⊆∅

8、二.填空题：（20%）1、公式(p→q)→r的成真赋值是_____________《离散数学》试题举例三.计算题：（20%）1.用等值演算法判断公式q∧¬(p→q)的类型解:q∧¬(p→q)⇔q∧¬(¬p∨q)⇔q∧(p∧¬q)⇔p∧(q∧¬q)⇔p∧0⇔0由最后一步可知，该式为矛盾式.2.计算集合A={∅，{∅}}的幂集■解：P(A)=P({∅,{∅}})={∅,{∅},{{∅}},{∅,{∅}}}《离散数学》