离散数学复习提纲.pdf

离散数学复习提纲 2014.5第一章 命题逻辑 命题符号化及联结词 命题公式及分类 等值演算会运用等值式(P9)证明两个公式是否相等、判断公式的类型(P33:7-9)对偶与范式求命题公式的(主)析取范式及用途、(主)合取范式(P33：12，13)第一章 命题逻辑 联结词全功能集复合联结词、N个命题变项可构成的不等价的命题公式数 推理理论推理的形式结构、常用推理规则(P23)构造证明法（直接证明法、附加前提证明法、反证法）(P34-35：18,19)本章的应用P11例11，P27例28，P34：15第二章 一阶逻辑一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类公式的解释、代换实例(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)前提引入 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、)关系的运算dom、ran、fld，R-1和合成RS、关系上的幂运算 关系的性质(判断、证明)自反性、反自反性、对称性、反对称性、传递性 关系运算与性质的关系(P87)、关系性质的充要条件 关系的闭包对称闭包、自反闭包和传递闭包的定义和构造方法第四章二元关系与函数等价关系和偏序关系等价类，商集、划分及其关系 哈斯图，偏序集的特定元素及性质 函数的定义和性质满射、单射、双射的性质、判断 双射函数的构造 函数的复合和反函数函数复合运算及性质，反函数的计算 本章应用等价类及划分,构造双射函数第五章 图的基本概念无向图及有向图握手定理、推论及应用 图的同构条件及判断 完全图、正则图、生成子图、自补图 通路、回路、图的连通性无向图和有向图的连通性，点割集、边割集 图的矩阵表示关联矩阵、邻接矩阵及性质 会计算图中指定长度的通路和回路的个数(P126)最短路径和关键路径（本章应用）P129例3，P130例4，P138：19，20第六章 特殊的图 二部图完全二部图、匹配、Hall定理及应用。欧拉图(半)欧拉图的定义及判别方法。哈密顿图(半)哈密顿图的定义及存在性的充分条件和必要条件。平面图 平面图的面、次数及它们之间的关系 极大平面图、极小非平面图 欧拉公式及推广(定理6.10,6.11)平面图判定定理(定理6.13,6.14)对偶图的构造和性质 本章应用 二部图(P154:5)，哈密顿回路(P154:15),平面图第七章 树无向树及生成树无向树，（最小）生成树 基本回路系统，基本割集系统 树的性质及有关定理（定理7.1-7.3）根树及其应用（本章应用）有向树及根树，根树的分类 最优树，前缀码与最佳前缀码（P164例7）第八章 组合分析初步加法法则和乘法法则基本排列组合的计数方法多重集的组合与排列公式(定理8.6，定理8.7)递推方程的求解与应用递推方程的定义和求解过程(P181-182例13，14)离散数学试题结构卷面一.选择题（20%）二.填空题（20%）三.计算题（20%）四.证明题（20%）五.应用题（20%）各部分分数比例 第一部分 数理逻辑 (30%)第二部分 集合论 (30%)第三部分 图论 (30%)第四部分 组合分析 (10%)离散数学试题举例一.选择题（20%）1设A、B、C为任意集合，则下列命题中，命题真值是真的是 。A若AB=AC，则B=C B.若 AB=，则A=B C若AB=AC，则B=C D.二.填空题：（20%）1、公式(pq)r 的成真赋值是_离散数学试题举例三.计算题：（20%）1.用等值演算法判断公式q(pq)的类型 解:q(pq)q(pq)q(pq)p(qq)p0 0 由最后一步可知，该式为矛盾式.2.计算集合A=，的幂集 解：P(A)=P(,)=,离散数学试题举例四.证明题（20%）证明 A=B C=D AC=BD 证：任取 AC xA yC xB yD BD 离散数学试题举例五.应用题：（20%）证明:“金属都是导电体,铜是金属，所以铜是导电体。”解：令 F(x):x是金属,G(x):x是导电体,a:铜 前提：x(F(x)G(x)，F(a)结论：G(a)证明：F(a)前提引入 x(F(x)G(x)前提引入 F(a)G(a)UI G(a)假言推理