离散数学复习提纲.ppt

离散数学 复习提纲2012 11 第一章命题逻辑 命题符号化及联结词命题公式及分类等值演算会运用等值式 P9 证明两个公式是否相等 判断公式的类型 P33 34 7 9 对偶与范式求命题公式的 主 析取范式及用途 主 合取范式 P34 12 13 第一章命题逻辑 联结词全功能集复合联结词 N个命题变项可构成的不等价的命题公式数推理理论推理的形式结构 常用推理规则 P23 构造证明法 直接证明法 附加前提证明法 反证法 P35 16 17 本章的应用P11例11 P28例27 P35 15 第二章一阶逻辑 一阶逻辑基本概念 命题符号化一阶逻辑公式 解释及分类公式的解释 代换实例 P54 5 13 一阶逻辑等值式 前束范式量词否定等值式 P46 量词辖域收缩和扩张等值式 P47 量词分配等值式 P47 48 第二章一阶逻辑 一阶逻辑推理理论有关量词的推理规则 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 幂集 文氏图集合的基本运算会运用集合运算算律 P61 62 证明有关集合运算的命题成立与否 进行化简集合中元素的计数 本章应用 包含排斥原理 P64例9 10 P69例15 第四章二元关系与函数 集合的笛卡儿积与二元关系会计算和运用笛卡儿积的性质 P78 证明命题成立与否重要关系 E I L D 关系的运算dom ran fld R 1和合成R S 关系上的幂运算关系的性质 判断 证明 自反性 反自反性 对称性 反对称性 传递性关系运算与性质的关系 P88 关系性质的充要条件关系的闭包对称闭包 自反闭包和传递闭包的定义和构造方法 第四章二元关系与函数 等价关系和偏序关系等价类 商集 划分及其关系哈斯图 偏序集的特定元素及性质函数的定义和性质满射 单射 双射的性质 判断双射函数的构造函数的复合和反函数函数复合运算及性质 反函数的计算本章应用等价类及划分 P117 24 构造双射函数 P112例35 第七章图的基本概念 无向图及有向图握手定理 推论及应用图的同构条件及判断完全图 正则图 生成子图 自补图通路 回路 图的连通性无向图和有向图的连通性 点割集 边割集图的矩阵表示关联矩阵 邻接矩阵及性质会计算图中指定长度的通路和回路的个数 P165 最短路径和关键路径 本章应用 P166例3 P168例4 P175 23 24 第八章一些特殊的图 二部图 完全二部图 匹配 Hall定理及应用 欧拉图 半 欧拉图的定义及判别方法 哈密顿图 半 哈密顿图的定义及存在性的充分条件和必要条件 平面图平面图的面 次数及它们之间的关系极大平面图 极小非平面图欧拉公式及推广 定理8 10 8 11 平面图判定定理 定理8 13 8 14 对偶图的构造和性质本章应用二部图 P177例1 哈密顿回路 P189 13 平面图 第九章树 无向树及生成树无向树 最小 生成树基本回路系统 基本割集系统树的性质及有关定理 定理9 1 9 3 根树及其应用 本章应用 有向树及根树 根树的分类最优树 前缀码与最佳前缀码 P196例9 3 波兰符号法与逆波兰符号法 P198例9 4 第十章组合分析初步 加法法则和乘法法则基本排列组合的计数方法多重集的组合与排列公式 定理10 6 定理10 7 递推方程的求解与应用递推方程的定义和求解过程 P213例13 14 算法的时间复杂度函数満足的递推方程T n aT n b d n n bkT 1 1 第十章组合分析初步 当d n c时 c为某个常数 代入上式得 当d n cn时 c为某个常数 代入上式得 算法的时间复杂度函数満足的递推方程T n aT n b d n n bkT 1 1 离散数学 试题结构 卷面一 选择题 10 二 填空题 15 三 计算题 25 四 证明题 20 五 应用题 30 各章内容比例第一章命题逻辑 15 第二章一阶逻辑 10 第三章集合 10 第四章关系 函数 20 第七章图论 15 第八章特殊图 10 第九章树 10 第十章组合分析 10 离散数学 试题举例 一 选择题 10 1 设S T M为任意集合 则下列命题中 命题真值是真的是 A 若S T S M 则T MB 若S T 则S TC 若 S T E 则S T D 是 的子集二 填空题 15 1 公式 p q r的成真赋值是 离散数学 试题举例 三 运算题 25 1 用等值演算法判断公式q p q 的类型解 q p q q p q q p q p q q p 0 0由最后一步可知 该式为矛盾式 2 计算集合A 的幂集解 P A P 离散数学 试题举例 四 证明题 20 证明A B C D A C B D证 任取 A C x A y C x B y D B D 离散数学 试题举例 五 应用题 30 证明 金属都是导电体 铜是金属 所以铜是导电体 解 令F x x是金属 G x x是导电体 a 铜前提 x F x G x F a 结论 G a 证明 F a 前提引入 x F x G x