离散数学复习提纲

离散数学离散数学 期末复习大纲 完整版 期末复习大纲 完整版 含例题和考试说明 含例题和考试说明 一 一 命题逻辑命题逻辑 复习知识点 1 命题与联结词 否定 析取 合取 蕴涵 等价 复合命题 2 命题公式与赋值 成真 成假 真值表 公式类型 重言 矛盾 可满足 公式的基本等值式 3 范式 析取范式 合取范式 极大 小 项 主析取范式 主合取范式 4 公式类型的判别方法 真值表法 等值演算法 主析取 合取范式法 5 命题逻辑的推理理论 本章重点内容 命题与联结词 公式与解释 主 析取范式与 主 合取范式 公式类型的判定 命题逻辑的推理 复习要求 1 理解命题的概念 了解命题联结词的概念 理解用联结词产生复合命题的方法 2 理解公式与赋值的概念 掌握求给定公式真值表的方法 用基本等值式化简其它公式 公式在解释下 的真值 3 了解析取 合取 范式的概念 理解极大 小 项的概念和主析取 合取 范式的概念 掌握用基本 等值式或真值表将公式化为主析取 合取 范式的方法 4 掌握利用真值表 等值演算法和主析取 合取范式的唯一性判别公式类型和公式等价方法 5 掌握命题逻辑的推理理论 疑难解析 1 公式类型的判定 判定公式的类型 包括判定公式是重言的 矛盾的或是可满足的 具体方法有两种 一是真值表法 二 是等值演算法 2 范式 求范式 包括求析取范式 合取范式 主析取范式和主合取范式 关键有两点 一是准确理解掌握定义 另一是巧妙使用基本等值式中的分配律 同一律和互补律 排中律 矛盾律 结果的前一步适当使用幂 等律 使相同的短语 或子句 只保留一个 3 逻辑推理 掌握逻辑推理时 要理解并掌握 12 个 除第 10 11 推理规则和 3 种证明法 直接证明法 附加前提 证明法和归谬法 例 1 试求下列公式的主析取范式 QQ374289236 1 2 PQQPP RQQPP 1PQQPQPPPQQPP 原式解 QPPPQPPQP QPPQQP QPQPQP 2RQQPPRQQPP 解 RQPRQPRQPRQPRQP RQPRQPRQP 2 用真值表判断下列公式是恒真 恒假 可满足 1 P P Q 2 P Q Q 3 P Q Q R P R 解 1 真值表 P Q P P P P P Q 0 01 0 1 0 11 0 0 1 00 0 1 1 10 0 0 因此公式 1 为可满足 2 真值表 P QP Q P Q P Q Q 0 01 0 0 0 11 0 0 1 00 1 0 1 11 0 0 因此公式 2 为恒假 3 真值表 P Q RP Q Q R P R P Q Q R P R 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 QQ374289236 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 因此公式 3 为恒真 3 Q P Q 蕴涵 P 法 1 真值表法 2 若 Q P Q 为真 则 Q P Q 为真 所以 Q 为假 P 为假 所以 P 为真 法 3 若 P 为假 则 P 为真 再分二种情况 若 Q 为真 则 Q P Q 为假 若 Q 为假 则 P Q 为假 则 Q P Q 为假 根据 所以 Q P Q 蕴涵 P 4 利用基本等价式证明下列命题公式为恒真公式 P Q Q R P R P Q P Q R P Q P R 1 证明 P Q Q R P R P Q Q R P R P Q Q R P R P Q Q R P R P Q P Q R R 1 Q P Q R 1 Q P Q R Q Q P R 1 P R 1 P Q P Q R P Q P R P Q P Q R P Q R P Q Q R P Q R P Q R P Q R 1 5 用形式演绎法证明 蕴涵SRRQQP SP 证明 1 规则 P QP 2 规则 Q 1 QP 3 规则 P RQ 4 规则 Q 3 RQ QQ374289236 5 规则 Q 2 4 RP 6 R S 规则 P 7 P S 规则 Q 5 6 6 用形式演绎法证明 蕴涵 AEFDDCBA E 证明 改 FDFDBABA 为为 1 A 规则 D 2 A B 规则 Q 1 3 规则 P DCBA 4 规则 Q 2 3 DC 5 D 规则 Q 4 6 规则 Q 5 FD 7 规则 P EFD 8 E 规则 Q 6 7 9 规则 Q 1 8 EA 7 P Q Q R R 蕴涵 P 1 Q R 2 R 3 Q 4 P Q 5 P Q 6 P 8 某案涉及甲 乙 丙 丁四个 根据已有线索 已知 1 若甲 乙均未作案 则丙 丁也均未作案 2 若丙 丁均未作案 则甲 乙也均未作案 3 若甲与乙同时作案 则丙与丁有一人且只有一人作案 4 若乙与丙同时作案 则甲与丁同时作案或同未作案 办案人员由此得出结论 甲是作案者 这个结论是否正确 为什么 解 对问题中的四个简单命题用 P1 P2 P3 P4 分别表示甲 乙 丙 丁作案 则办案人员的推理如下 前提 1 P1 P2 P3 P4 2 P3 P4 P1 P2 3 P1 P2 P3 P4 P3 P4 4 P3 P4 P1 P2 P1 P2 结论 P1 P1 P2 P3 P4 P3 P4 P1 P2 P1 P2 P3 P4 P3 P4 P3 P4 P1 P2 P1 P2 P1 不是永真式 比如 P1 取假 P2 取真 P3 取假 P4 取真时 上式为假 QQ374289236 所以 P1 不是前提的有效结论 所以甲是作案者的结论是错误的 二 二 谓词逻辑谓词逻辑 复习知识点 1 谓词 量词 个体词 一阶逻辑 3 要素 个体域 变元 约束出现与自由出现 2 谓词公式与解释 谓词公式的类型 永真 永假 可满足 3 谓词公式的等值式 代换实例 消去量词 量词否定和量词辖域收与扩 和置换规则 置换规则 换 名规则和代替规则 本章重点内容 谓词与量词 公式与解释 复习要求 1 理解谓词 量词 个体词 个体域 变元的概念 理解用谓词 量词 逻辑联结词描述一个简单命题 了解命题符号化 2 理解公式与解释的概念 掌握在有限个体域下消去公式量词 求公式在给定解释下真值的方法 了解 谓词公式的类型 疑难解析 1 谓词与量词 理解谓词与量词引入的意义 概念的含义及在谓词与量词作用下变量的自由性 约束性与改名规则 即换名规则和代替规则 2 公式与解释 能将一阶逻辑公式表达式中的量词消除 写成与之等价的公式 然后将解释中的数值代入公式 求出 真值 三 三 集集 合合 复习知识点 1 集合 元素 集合的表示方法 子集 空集 全集 集合的包含 相等 幂集 2 集合的交 并 差 补以及对称差等运算及其运算律 交换律 结合律 分配律 吸收律 德摩根律 等 文氏 Venn 图 本章重点内容 集合的概念 集合的运算性质 集合恒等式的证明 复习要求 1 理解集合 元素 子集 空集 全集 集合的包含 相等 幂集等基本概念 QQ374289236 2 掌握集合的表示法和集合的交 并 差 补 对称差等基本运算 3 掌握集合运算基本规律 证明集合等式的方法 疑难解析 1 集合的概念 重点对幂集加以掌握 一是掌握幂集的构成 一是掌握幂集元数为 2n 2 集合恒等式的证明 对集合恒等式证明的练习 加深对集合性质的理解与掌握 四 四 二元关系二元关系 复习知识点 1 序偶 迪卡尔积 迪卡尔积的运算 2 关系表达式 关系矩阵与关系图 3 复合关系 右复合 与逆关系 3 关系的性质 自反性 反自反性 对称性 反对称性 传递性 4 关系的闭包 自反闭包 对称闭包 传递闭包 5 等价关系与等价类 6 偏序关系与哈斯图 极大 小元 最大 小元 7 函数及其性质 单射 满射 双射 8 复合函数与反函数 本章重点内容 二元关系的概念 关系的性质 关系的闭包 等价关系 偏序关系和映射的概念 复习要求 1 了解序偶与迪卡尔积的概念 掌握迪卡尔积的运算 2 理解关系的概念 二元关系 空关系 全域关系 恒等关系 掌握关系的集合表示 关系矩阵和关系 图 关系的运算 3 掌握求复合关系与逆关系的方法 4 理解关系的性质 自反性 反自反性 对称性 反对称性 传递性 掌握其判别方法 定义 图 4 掌握求关系的闭包 自反闭包 对称闭包 传递闭包 的方法 5 理解等价关系和偏序关系的概念 掌握等价类的求法和偏序关系做哈斯图的方法 极大 小元 最大 小 元的求法 6 理解函数概念 函数 函数相等 A 到 B 的函数 复合函数和反函数 QQ374289236 7 理解单射 满射 双射等概念 掌握其判别方法 疑难解析 1 关系的概念 熟练掌握二元关系的概念及关系矩阵 关系图表示 2 关系的性质及其判定 关系的性质既是对关系概念的加深理解与掌握 又是关系的闭包 等价关系 偏序关系的基础 对于五 种性质的判定 可以依据教材上总结的规律 这其中对传递性的判定 难度稍大一点 这里要提及两点 一是不破坏传递性定义 可认为具有传递性 如空关系具有传递性 同时空关系具有对称性与反对称性 但是不具有自反性 3 关系的闭包 在理解掌握关系闭包概念的基础上 主要掌握闭包的求法 关键是熟记定理 7 10 和 7 11 4 偏序关系及偏序集中特殊元素的确定 理解与掌握偏序关系与偏序集概念的关键是哈斯图 哈斯图画法掌握了 对于确定任一子集的最大 小 元 极大 小 元也就容易了 这里要注意 最大 小 元与极大 小 元只能在子集内确定 5 映射的概念与映射种类的判定 映射的种类主要指单射 满射 双射与非单非满射 判定的方法除定义外 可借助于关系图 而实数集 的子集上的映射也可以利用直角坐标系表示进行 尤其是对各种初等函数 五 五 图论图论 复习知识点 1 图的基本概念 无向图与有向图 顶点与边的关联关系 顶点 边 与顶点 边 之间邻接关系 简 单图与多重图 顶点度数 度 与握手定理 图的同构 完全图 子 补 图 2 通路与回路 简单通 回 路与初级通 回 路 连通图与非连通图 连通分支 强连通图 单向连 通图与弱连通图 二部图 点割集 边割集 点 边 连通度 3 图的矩阵表示 邻接矩阵 关联矩阵 可达矩阵 4 欧拉通 回 路 半 欧拉图 哈密尔顿通 回 路 半 哈密尔顿图 5 无向树 生成树 带权树 最小生成树 基本回路 基本回路系统 基本割集 基本割集系统 避圈 法 Kruskal 算法 6 有向树 树根 有序树 二叉树 前缀码 最佳前缀码 霍夫曼 Huffman 算法 带权图的最优二 分树 二叉树的周游 QQ374289236 本章重点内容 握手定理 点 边 割集 特殊图 欧拉图与哈密顿图 无 有 向树 复习要求 1 理解图的有关概念 图 完全图 子图 母图 生成子图 图的同构等 2 深刻理解握手定理及其推论的内容 并能熟练地应用它们 3 理解图的矩阵表示 关联矩阵 相邻矩阵 和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中 通路与回路数的方法 4 深刻理解欧拉图 哈密顿图的定义及判别定理 对于给定的图 应用各定理准确判断 会用破坏哈密 顿图应满足的某些必要条件的方法判断某些图不是哈密顿图 会用满足哈密顿的充分条件的方法判断某些 图是哈密顿图 5 深刻理解无向树的定义 熟练掌握无向树的主要性质 并能灵活应用它们 6 深刻理解生成树的有关概念与性质 理解基本回路 基本回路系统 基本割集 基本割集系统 用 Kruskal 算法求权图中最小生成树的方法 7 深刻理解有向树 根树 二叉树和前缀码的有关概念 掌握用霍夫曼 Huffman 算法求带权图的最优 二分树 掌握求最佳前缀码方法 二叉树的中序和前序行遍法 考试说明考试说明 考核方式 1 期末笔试为 120 分钟的闭卷考试 占总评成绩的 70 2 平时成绩根据作业完成情况 半期考成绩 出勤情况和课堂表现确定 占总评成绩 30 各章比例 数理逻辑 30 分 集合 30 分 图论 40 分 考题类型 单项选择题 16 分 填空题 18 分 证明题 12