离散数学复习提纲.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和合成R S 关系上的幂运算 关系的性质 判断 证明 自反性 反自反性 对称性 反对称性 传递性 关系运算与性质的关系 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 若A B A C 则B C B 若 A B 则A B C 若A B A C 则B C D 二 填空题 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 离散数学 试题举例 四 证明题 20 证明 A B C D A C B D 证 任取 A C x A y C x B y D B D 离散数学 试题举例 五 应用题 20 证明 金属都是导电体 铜是金属