《离散数学及其应用》课后习题答案

本书是国家精品课程“离散数学”的主讲教材，也是普通高等教育“十一五”国家级规划教材。本书以教育部计算机科学与技术教学指导委员会最新制订的计算机专业规范为依据编写而成。本书系统介绍了数理逻辑、二元关系、图论、代数系统与布尔代数中有关的概念、定理及其证明方法。既强化基本概念的描述，还特别着重于阐述有关离散数学的证明方法及离散数学应用实例，充分展示了离散数学在计算机中的应用。本书还配有《离散数学实验与习题解析》及电子教案。

本书可作为高等学校计算机专业计算机科学方向、计算机工程方向“离散数学”必修课教材，也可作为其他相关专业“离散数学”课程教材。同时，对于相关专业的科技人员及学生也是一本很好的参考读物。

目录

•  第一篇 预备知识
•    引言
•   第1章 集合论
•    1.0 内容提要
•    1.1 本章学习要求
•    1.2 集合
•     1.2.1 集合的表示
•     1.2.2 集合与元素的关系
•     1.2.3 集合与集合的关系
•     1.2.4 几个特殊的集合
•     1.2.5 集合的运算
•     1.2.6 集合的难点
•    1.3 无限集
•     1.3.1 可数集合和不可数集合
•     1.3.2 无限集的难点
•    1.4 集合的应用
•    1.5 本章总结
•    1.6 习题
•   第2章 计数问题
•    2.0 内容提要
•    2.1 本章学习要求
•    2.2 基本原理
•     2.2.1 乘法原理
•     2.2.2 加法原理
•     2.2.3 基本原理的难点
•    2.3 排列与组合
•     2.3.1 排列问题
•     2.3.2 组合问题
•     2.3.3 排列与组合的难点
•    2.4 容斥原理与鸽笼原理
•     2.4.1 容斥原理
•     2.4.2 鸽笼原理
•     2.4.3 容斥原理与鸽笼原理的难点
•    2.5 离散概率简介
•     2.5.1 基本概念
•     2.5.2 离散概率函数
•     2.5.3 离散概率简介的难点
•    2.6 递归关系
•     2.6.1 递归关系
•     2.6.2 递归关系的难点
•    2.7 计数问题的应用
•    2.8 本章总结
•    2.9 习题
• 第二篇 数理逻辑
•    引言
•   第3章 命题逻辑
•    3.0 内容提要
•    3.1 本章学习要求
•    3.2 命题与命题联结词
•     3.2.1 命题
•     3.2.2 命题联结词
•     3.2.3 联结词理解难点
•     3.2.4 命题联结词的应用
•    3.3 命题公式、解释与真值表
•     3.3.1 命题公式
•     3.3.2 命题公式的解释与真值表
•     3.3.3 命题公式的分类
•     3.3.4 命题公式的基本等价关系
•     3.3.5 命题公式的难点
•     3.3.6 命题公式的应用
•    *3.4 联结词的完备集
•     3.4.1 命题联结词的个数
•     3.4.2 联结词的完备集
•     3.4.3 联结词的完备集的应用
•    3.5 公式的标准型———范式
•     3.5.1 析取范式和合取范式
•     3.5.2 主析取范式和主合取范式
•     3.5.3 范式的难点
•     3.5.4 范式的应用
•    3.6 本章总结
•    3.7 习题
•   第4章 谓词逻辑
•    4.0 内容提要
•    4.1 本章学习要求
•    4.2 谓词逻辑中的基本概念与表示
•     4.2.1 谓词
•     4.2.2 量词
•     4.2.3 谓词的语言翻译
•     4.2.4 谓词翻译难点
•     4.2.5 谓词翻译的应用
•    4.3 谓词合式公式与解释
•     4.3.1 谓词的合式公式
•     4.3.2 自由变元和约束变元
•     4.3.3 谓词合式公式的解释
•     4.3.4 谓词合式公式的分类
•     4.3.5 谓词合式公式的基本等价关系
•     4.3.6 谓词合式公式难点
•     4.3.7 谓词合式公式的应用
•    4.4 公式的标准型———范式
•     4.4.1 前束范式
•     4.4.2 Skolem标准型
•     4.4.3 范式的难点
•    4.5 本章总结
•    4.6 习题
•   第5章 推理与证明技术
•    5.0 内容提要
•    5.1 本章学习要求
•    5.2 命题逻辑的推理理论
•     5.2.1 推理的基本概念和推理形式
•     5.2.2 判断有效结论的常用方法
•     5.2.3 命题逻辑推理的难点
•     5.2.4 命题逻辑推理的应用
•    5.3 谓词逻辑的推理理论
•     5.3.1 谓词演算的演绎与推理
•     5.3.2 谓词演算的综合推理方法
•     5.3.3 谓词逻辑推理的难点
•     5.3.4 谓词逻辑推理的应用
•    5.4 数学归纳法
•     5.4.1 数学归纳法原理
•     5.4.2 数学归纳法应用
•    5.5 按定义证明方法
•     5.5.1 按定义证明方法原理
•     5.5.2 按定义证明方法应用实例
•    5.6 本章总结
•    5.7 习题
• 第三篇 二元关系
•    引言
•   第6章 二元关系
•    6.0 内容提要
•    6.1 本章学习要求
•    6.2 二元关系
•     6.2.1 序偶和笛卡儿积
•     6.2.2 关系的定义
•     6.2.3 关系的表示法
•     6.2.4 二元关系的难点
•     6.2.5 关系的应用
•    6.3 关系的运算
•     6.3.1 关系的复合运算
•     6.3.2 关系的逆运算
•     6.3.3 关系的幂运算
•     6.3.4 关系运算的难点
•     6.3.5 关系运算的应用
•    6.4 关系的性质
•     6.4.1 关系性质的定义
•     6.4.2 关系性质的判定定理
•     6.4.3 关系性质的保守性
•     6.4.4 关系性质的难点
•     6.4.5 关系性质的应用
•    6.5 关系的闭包运算
•     6.5.1 关系的闭包
•     6.5.2 关系闭包的难点
•     6.5.3 关系闭包的应用
•    6.6 本章总结
•    6.7 习题
•   第7章 特殊关系
•    7.0 内容提要
•    7.1 本章学习要求
•    7.2 等价关系
•     7.2.1 等价关系
•     7.2.2 集合的划分
•     7.2.3 等价类与商集
•     7.2.4 等价关系与划分
•     7.2.5 等价关系的难点
•     7.2.6 等价关系的应用
•    7.3 次序关系
•     7.3.1 拟序关系
•     7.3.2 偏序关系
•     7.3.3 全序关系
•     7.3.4 良序关系
•     7.3.5 次序关系的难点
•     7.3.6 次序关系的应用
•    7.4 本章总结
•    7.5 习题
•   第8章 函数
•    8.0 内容提要
•    8.1 本章学习要求
•    8.2 函数
•     8.2.1 函数的定义
•     8.2.2 函数的类型
•     8.2.3 常用函数
•     8.2.4 函数的难点
•     8.2.5 函数的应用
•    8.3 函数的运算
•     8.3.1 函数的复合运算
•     8.3.2 函数的逆运算
•     8.3.3 函数运算的难点
•     8.3.4 函数运算的应用
•    8.4 置换函数
•     8.4.1 基本概念
•     8.4.2 置换函数的难点
•     8.4.3 置换函数的应用
•    8.5 本章总结
•    8.6 习题
• 第四篇 图论
•    引言
•   第9章 图
•    9.0 内容提要
•    9.1 本章学习要求
•    9.2 图的基本概念
•     9.2.1 图的定义
•     9.2.2 图的表示
•     9.2.3 图的操作
•     9.2.4 邻接点与邻接边
•     9.2.5 图的分类
•     9.2.6 子图与补图
•     9.2.7 结点的度数与握手定理
•     9.2.8 图的同构
•     9.2.9 图的难点
•     9.2.10 图的应用
•    9.3 通路、回路与连通性
•     9.3.1 通路与回路
•     9.3.2 无向图的连通性
•     9.3.3 有向图的连通性
•     9.3.4 通路、回路与连通性的难点
•     9.3.5 通路、回路与连通性的应用
•    9.4 本章总结
•    9.5 习题
•   第10章 树
•    10.0 内容提要
•    10.1 本章学习要求
•    10.2 树
•     10.2.1 树的定义与性质
•     10.2.2 生成树
•     10.2.3 最小生成树
•     10.2.4 无向树的难点
•     10.2.5 无向树的应用
•    10.3 根树
•     10.3.1 根树的定义与分类
•     10.3.2 根树的遍历
•     10.3.3 最优树与哈夫曼算法
•     10.3.4 根树的难点
•     10.3.5 根树的应用
•    10.4 本章总结
•    10.5 习题
•   第11章 特殊图
•    11.0 内容提要
•    11.1 本章学习要求
•    11.2 欧拉图
•     11.2.1 欧拉图的引入与定义
•     11.2.2 欧拉图的判定
•     11.2.3 欧拉图的难点
•     11.2.4 欧拉图的应用
•    11.3 哈密顿图
•     11.3.1 哈密顿图的引入与定义
•     11.3.2 哈密顿图的判定
•     11.3.3 哈密顿图的难点
•     11.3.4 哈密顿图的应用
•    11.4 偶图
•     11.4.1 偶图的定义
•     11.4.2 偶图的判定
•     11.4.3 匹配
•     11.4.4 偶图的难点
•     11.4.5 偶图的应用
•    11.5 平面图
•     11.5.1 平面图的定义
•     11.5.2 平面图的简单判定方法———观察法
•     11.5.3 欧拉公式
•     11.5.4 库拉托夫斯基定理
•     11.5.5 对偶图
•     *11.5.6 图的着色
•     11.5.7 平面图的难点
•     11.5.8 平面图的应用
•    11.6 本章总结
•    11.7 习题
• 第五篇 代数系统
•    引言
•   第12章 代数系统
•    12.0 内容提要
•    12.1 本章学习要求
•    12.2 代数系统
•     12.2.1 代数运算
•     12.2.2 代数系统与子代数
•     12.2.3 代数系统中的难点
•     12.2.4 代数系统的应用
•    12.3 代数系统的基本运算和性质
•     12.3.1 二元运算律
•     12.3.2 代数系统的性质
•     12.3.3 代数系统性质的难点
•     12.3.4 代数系统性质的应用
•    12.4 同态与同构
•     12.4.1 同态与同构
•     12.4.2 同态的性质
•     12.4.3 同态与同构的难点
•     12.4.4 同态与同构的应用
•    12.5 本章总结
•    12.6 习题
•   第13章 群
•    13.0 内容提要
•    13.1 本章学习要求
•    13.2 半群与含幺半群
•     13.2.1 半群与含幺半群
•     13.2.2 元素的幂
•     13.2.3 循环半群
•     13.2.4 半群与含幺半群的难点
•     13.2.5 半群的应用
•    13.3 群及其性质
•     13.3.1 群的定义及基本性质
•     13.3.2 元素的周期
•     13.3.3 子群
•     13.3.4 群的同态
•     13.3.5 群及子群的难点
•     13.3.6 群的应用
•    13.4 特殊群
•     13.4.1 交换群（阿贝尔群）
•     13.4.2 循环群
•     *13.4.3 置换群
•     13.4.4 特殊群的难点
•     13.4.5 特殊群的应用
•    13.5 陪集与拉格朗日定理
•     13.5.1 陪集
•     13.5.2 拉格朗日定理
•     13.5.3 陪集与拉格朗日定理的难点
•     *13.5.4 拉格朗日定理的应用
•    13.6 正规子群与商群
•     13.6.1 正规子群（不变子群）
•     *13.6.2 商群
•     13.6.3 正规子群与商群的难点
•     *13.6.4 商群的应用
•    13.7 本章总结
•    13.8 习题
•   *第14章 环与域
•    14.0 内容提要
•    14.1 本章学习要求
•    14.2 环与域
•     14.2.1 环与域的定义
•     14.2.2 环与域的性质
•     14.2.3 环与域的应用
•    14.3 本章总结
•    14.4 习题
•   第15章 格与布尔代数
•    15.0 内容提要
•    15.1 本章学习要求
•    15.2 格
•     15.2.1 偏序格
•     15.2.2 代数格
•     15.2.3 偏序格与代数格的等价性
•     15.2.4 格的性质
•     15.2.5 子格与格同态
•     15.2.6 分配格与模格
•     15.2.7 有界格与有补格
•     15.2.8 格的难点
•     15.2.9 格的应用
•    15.3 布尔代数
•     15.3.1 布尔代数
•     15.3.2 布尔表达式
•     15.3.3 布尔代数的难点
•     15.3.4 布尔代数的应用
•    15.4 本章总结
•    15.5 习题
• 参考文献