《离散数学及其应用:本科教学版(第6版)》课后习题答案

《离散数学及其应用》一书是介绍离散数学理论和方法的经典教材，已经成为采用率最高的离散数学教材，仅在美国就被600多所高校用作教材，并获得了极大的成功。第6版在前5版的基础上做了大量的改进，使其成为更有效的教学工具。

本书基于该书第6版进行改编，保留了国内离散数学课程涉及的基本内容，更加适合作为国内高校计算机及相关专业本科生的离散数学课程教材。本书的具体改编情况如下：

· 补充了关于范式和标准型的基础内容。

· 删去了在其他课程中讲授的内容，如数论、离散概率、归纳和递归等。

· 对于保留章节，删去了编号为偶数的练习题。

· 删去了相关的历史资料。

目录

• 出版者的话
• 改编者序
• 译者序
• 前言
• 第1章基础:逻辑和证明
• 1.1命题逻辑
• 1.1.1引言
• 1.1.2命题
• 1.1.3条件语句
• 1.1.4复合命题的真值表
• 1.1.5逻辑运算符的优先级
• 1.1.6翻译语句
• 1.1.7系统规范说明
• 1.1.8布尔检索
• 1.1.9逻辑难题
• 1.1.10逻辑运算和位运算
• 练习
• 1.2命题等价
• 1.2.1引言
• 1.2.2逻辑等价
• 1.2.3德摩根律的运用
• 1.2.4构建新的逻辑等价式
• 练习
• 1.3谓词和量词
• 1.3.1引言
• 1.3.2谓词
• 1.3.3量词
• 1.3.4其他量词
• 1.3.5约束论域量词
• 1.3.6量词的优先级
• 1.3.7绑定变量
• 1.3.8涉及量词的逻辑等价
• 1.3.9否定量化表达式
• 1.3.10翻译语句为逻辑表达式
• 1.3.11在系统说明中运用量词
• 1.3.12选自Lewis Carroll的例子
• 1.3.13逻辑程序设计
• 练习
• 1.4嵌套量词
• 1.4.1引言
• 1.4.2量词的顺序
• 1.4.3将数学语句翻译成涉及嵌套量词的语句
• 1.4.4将嵌套量词翻译为汉语
• 1.4.5将汉语语句翻译成逻辑表达式
• 1.4.6否定嵌套量词
• 练习
• 1.5推理规则
• 1.5.1引言
• 1.5.2命题逻辑的有效论证
• 1.5.3命题逻辑的推理规则
• 1.5.4用推理规则建立论证
• 1.5.5消解
• 1.5.6谬误
• 1.5.7带量词命题的推理规则
• 1.5.8命题推理和量化语句推理规则的结合
• 练习
• 1.6证明导论
• 1.6.1引言
• 1.6.2一些专用术语
• 1.6.3定理陈述的理解
• 1.6.4证明定理的方法
• 1.6.5直接证明
• 1.6.6反证法
• 1.6.7归谬证明
• 1.6.8证明中的错误
• 1.6.9仅仅是开始
• 练习
• 1.7证明的方法和策略
• 1.7.1引言
• 1.7.2穷举证明和分情形证明
• 1.7.3存在性证明
• 1.7.4唯一性证明
• 1.7.5证明策略
• 1.7.6寻找反例
• 1.7.7行动证明策略
• 1.7.8填充
• 1.7.9未解决问题的作用
• 1.7.10其他证明方法
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 第2章基本结构：集合、函数、数列与求和
• 2.1集合
• 2.1.1引言
• 2.1.2幂集合
• 2.1.3笛卡儿积
• 2.1.4使用带量词的集合符号
• 2.1.5量词的真值集合
• 练习
• 2.2集合运算
• 2.2.1引言
• 2.2.2集合恒等式
• 2.2.3扩展的并集和交集
• 2.2.4计算机表示集合的方式
• 练习
• 2.3函数
• 2.3.1引言
• 2.3.2一对一函数和映上函数
• 2.3.3反函数和函数组合
• 2.3.4函数的图像
• 2.3.5几个重要的函数
• 练习
• 2.4序列与求和
• 2.4.1引言
• 2.4.2序列
• 2.4.3特殊的整数序列
• 2.4.4求和
• 2.4.5基数
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 第3章计数
• 3.1计数基础
• 3.1.1引言
• 3.1.2基本的计数原则
• 3.1.3比较复杂的计数问题
• 3.1.4容斥原理
• 3.1.5树图
• 练习
• 3.2鸽巢原理
• 3.2.1引言
• 3.2.2广义鸽巢原理
• 3.2.3巧妙使用鸽巢原理
• 练习
• 3.3排列与组合
• 3.3.1引言
• 3.3.2排列
• 3.3.3组合
• 练习
• 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.5.5把物体放入盒子
• 练习
• 3.6生成排列和组合
• 3.6.1引言
• 3.6.2生成排列
• 3.6.3生成组合
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 第4章高级计数技术
• 4.1递推关系基础
• 4.1.1引言
• 4.1.2递推关系
• 4.1.3用递推关系构造模型
• 练习
• 4.2求解线性递推关系
• 4.2.1引言
• 4.2.2求解常系数线性齐次递推关系
• 4.2.3常系数线性非齐次的递推关系
• 练习
• 4.3分治算法和递推关系
• 4.3.1引言
• 4.3.2分治递推关系
• 练习
• 4.4生成函数
• 4.4.1引言
• 4.4.2关于幂级数的有用事实
• 4.4.3计数问题与生成函数
• 4.4.4使用生成函数求解递推关系
• 4.4.5使用生成函数证明恒等式
• 练习
• 4.5容斥
• 4.5.1引言
• 4.5.2容斥原理
• 练习
• 4.6容斥原理的应用
• 4.6.1引言
• 4.6.2容斥原理的另一种形式
• 4.6.3埃拉托色尼筛
• 4.6.4映上函数的个数
• 4.6.5错位排列
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 第5章关系
• 5.1关系及其性质
• 5.1.1引言
• 5.1.2函数作为关系
• 5.1.3集合的关系
• 5.1.4关系的性质
• 5.1.5关系的组合
• 练习
• 5.2n元关系及其应用
• 5.2.1引言
• 5.2.2n元关系
• 5.2.3数据库和关系
• 5.2.4n元关系的运算
• 5.2.5SQL
• 练习
• 5.3关系的表示
• 5.3.1引言
• 5.3.2用矩阵表示关系
• 5.3.3用图表示关系
• 练习
• 5.4关系的闭包
• 5.4.1引言
• 5.4.2闭包
• 5.4.3有向图的路径
• 5.4.4传递闭包
• 5.4.5沃舍尔算法
• 练习
• 5.5等价关系基础
• 5.5.1引言
• 5.5.2等价关系
• 5.5.3等价类
• 5.5.4等价类与划分
• 练习
• 5.6偏序
• 5.6.1引言
• 5.6.2字典顺序
• 5.6.3哈塞图
• 5.6.4极大元素与极小元素
• 5.6.5格
• 5.6.6拓扑排序
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 第6章图
• 6.1图和图模型
• 练习
• 6.2图的术语和几种特殊的图
• 6.2.1引言
• 6.2.2基本术语
• 6.2.3一些特殊的简单图
• 6.2.4偶图
• 6.2.5特殊类型的图的一些应用
• 6.2.6从旧图到新图
• 练习
• 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.4.6计算顶点之间的通路数
• 练习
• 6.5欧拉通路与哈密顿通路
• 6.5.1引言
• 6.5.2欧拉通路与欧拉回路
• 6.5.3哈密顿通路与哈密顿回路
• 练习
• 6.6最短通路问题
• 6.6.1引言
• 6.6.2最短通路算法
• 6.6.3旅行商问题
• 练习
• 6.7可平面图
• 6.7.1引言
• 6.7.2欧拉公式
• 6.7.3库拉图斯基定理
• 练习
• 6.8图着色
• 6.8.1引言
• 6.8.2图着色的应用
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 第7章树
• 7.1概述
• 7.1.1树作为模型
• 7.1.2树的性质
• 练习
• 7.2树的应用
• 7.2.1引言
• 7.2.2二叉搜索树
• 7.2.3决策树
• 7.2.4前缀码
• 7.2.5博弈树
• 练习
• 7.3树的遍历
• 7.3.1引言
• 7.3.2通用地址系统
• 7.3.3遍历算法
• 7.3.4中缀、前缀和后缀记法
• 练习
• 7.4生成树
• 7.4.1引言
• 7.4.2深度优先搜索
• 7.4.3宽度优先搜索
• 7.4.4回溯
• 7.4.5有向图中的深度优先搜索
• 练习
• 7.5最小生成树
• 7.5.1引言
• 7.5.2最小生成树算法
• 练习
• 关键术语和结果
• 复习题
• 补充练习
• 计算机题目
• 计算和研究
• 写作题目
• 练习题答案