离散数学及其应用（原书第4版） (2008 年度畅销榜NO.391 )

本书介绍了离散数学的理论和方法，内容涉及数学推理、组合分析、离散结构和算法设计。本书取材极其广泛，除包括定义、定理的严密陈述外，还配备大量的实例和图、表的说明，适合各种需求的练习和题目，以及丰富的历史资料和网站资源。本书的第3版曾被全世界几百所大学选为教材，第4版作了新的改进和补充。本书适合于数学、计算机科学和工程技术专业人员使用。\r\n\r\n\r\n
\r\n

第l章 基础：逻辑. 集合和函数 \r\n\r\n 1. 1 逻辑 \r\n\r\n 1. 1. 1 引言 \r\n\r\n 1. 1. 2 命题 \r\n\r\n 1. 1. 3 翻译语言的句子 \r\n\r\n 1. 1. 4 布尔检索 \r\n\r\n l. 1. 5 逻辑运算和位运算练习 \r\n\r\n 1. 2 命题等价 \r\n\r\n 1. 2. 1 引言 \r\n\r\n 1. 2. 2 逻辑等价练习 \r\n\r\n 1. 3 谓词和量词 \r\n\r\n 1. 3. 1 引言 \r\n\r\n 1. 3. 2 量词 \r\n\r\n 1. 3. 3 翻译语句为逻辑表达式 \r\n\r\n 1. 3. 4 选自Lewis Carroll的例子(选读) \r\n\r\n 1. 3. 5 绑定变量 \r\n\r\n 1. 3. 6 否定练习 \r\n\r\n 1. 4 集合 \r\n\r\n 1. 4. 1 引言 \r\n\r\n 1. 4. 2 幂集合 \r\n\r\n 1. 4. 3 笛卡儿积练习 \r\n\r\n 1. 5 集合运算 \r\n\r\n 1. 5. 1 引言 \r\n\r\n 1. 5. 2 集合相等 \r\n\r\n 1. 5. 3 扩展的并集和交集 \r\n\r\n 1. 5. 4 集合的计算机表示练习 \r\n\r\n 1. 6 函数 \r\n\r\n 1. 6. 1 引言 \r\n\r\n 1. 6. 2 一对一函数和映上函数 \r\n\r\n 1. 6. 3 反函数和函数组合 \r\n\r\n 1. 6. 4 函数的图像 \r\n\r\n 1. 6. 5 几个重要的函数练习 \r\n\r\n 1. 7 序列与求和 \r\n\r\n 1. 7. 1 引言 \r\n\r\n 1. 7. 2 序列 \r\n\r\n 1. 7. 3 特殊的整数序列 \r\n\r\n 1. 7. 4 求和 \r\n\r\n 1. 7. 5 基数(选读)练习 \r\n\r\n 1. 8 函数增长 \r\n\r\n 1. 8. 1 引言 \r\n\r\n 1. 8. 2 大O符号 \r\n\r\n 1. 8. 3 函数组合的增长 \r\n\r\n 1. 8. 4 大Ω和大Ξ符号 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第2章 基础：算法. 整数和矩阵 \r\n\r\n 2. 1 算法 \r\n\r\n 2. 1. 1 引言 \r\n\r\n 2. 1. 2 搜索算法练习 \r\n\r\n 2. 2 算法的复杂性 \r\n\r\n 2. 2. 1 引言练习 \r\n\r\n 2. 3 整数和除法 \r\n\r\n 2. 3. 1 引言 \r\n\r\n 2. 3. 2 除法 \r\n\r\n 2. 3. 3 素数 \r\n\r\n 2. 3. 4 除法算法 \r\n\r\n 2. 3. 5 最大公约数和最小公倍数 \r\n\r\n 2. 3. 6 模运算 \r\n\r\n 2. 3. 7 同余应用 \r\n\r\n 2. 3. 8 密码学练习 \r\n\r\n 2. 4 整数和算法 \r\n\r\n 2. 4. 1 引言 \r\n\r\n 2. 4. 2 欧几里德算法 \r\n\r\n 2. 4. 3 整数表示 \r\n\r\n 2. 4. 4 整数运算算法练习 \r\n\r\n 2. 5 数论应用 \r\n\r\n 2. 5. 1 引言 \r\n\r\n 2. 5. 2 若干有用的结果 \r\n\r\n 2. 5. 3 线性同余 \r\n\r\n 2. 5. 4 中国余数定理 \r\n\r\n 2. 5. 5 大整数的计算机算术运算 \r\n\r\n 2. 5. 6 伪素数 \r\n\r\n 2. 5. 7 公钥密码学 \r\n\r\n 2. 5. 8 RSA加密 \r\n\r\n 2. 5. 9 RSA解密 \r\n\r\n 2. 5. 10 用RSA作公钥系统练习 \r\n\r\n 2. 6 矩阵 \r\n\r\n 2. 6. 1 引言 \r\n\r\n 2. 6. 2 矩阵运算 \r\n\r\n 2. 6. 3 矩阵乘法运算 \r\n\r\n 2. 6. 4 矩阵的转置和幂 \r\n\r\n 2. 6. 5 0-1矩阵练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第3章 数学推理 \r\n\r\n 3. 1 证明方法 \r\n\r\n 3. 1. 1 引言 \r\n\r\n 3. 1. 2　推理规则 \r\n\r\n 3. 1. 3 谬误 \r\n\r\n 3. 1. 4 带量词命题的推理规则 \r\n\r\n 3. 1. 5 证明定理的方法 \r\n\r\n 3. 1. 6 定理与量词 \r\n\r\n 3. 1. 7 停机问题 \r\n\r\n 3. 1. 8 关于证明的一些评注练习 \r\n\r\n 3. 2 数学归纳法 \r\n\r\n 3. 2. 1 引言 \r\n\r\n 3. 2. 2 良序性 \r\n\r\n 3. 2. 3 数学归纳法 \r\n\r\n 3. 2. 4 数学归纳法证明的例子 \r\n\r\n 3. 2. 5 数学归纳法的第二原理练习 \r\n\r\n 3. 3 递归定义 \r\n\r\n 3. 3. 1 引言 \r\n\r\n 3. 3. 2 递归地定义函数 \r\n\r\n 3. 3. 3 递归地定义集合练习 \r\n\r\n 3. 4 递归算法 \r\n\r\n 3. 4. 1 引言 \r\n\r\n 3. 4. 2 递归与迭代练习 \r\n\r\n 3. 5 程序正确性 \r\n\r\n 3. 5. 1 引言 \r\n\r\n 3. 5. 2 程序验证 \r\n\r\n 3. 5. 3 推理规则 \r\n\r\n 3. 5. 4 条件语句 \r\n\r\n 3. 5. 5 循环不变量 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第4章 计数 \r\n\r\n 4. 1 计数的基础 \r\n\r\n 4. 1. 1 引言 \r\n\r\n 4. 1. 2 基本的计数原则 \r\n\r\n 4. 1. 3 容斥原理 \r\n\r\n 4. 1. 4 树图练习 \r\n\r\n 4. 2 鸽巢原理 \r\n\r\n 4. 2. 1 引言 \r\n\r\n 4. 2. 2 推广的鸽巢原理 \r\n\r\n 4. 2. 3 巧妙使用鸽巢原理练习 \r\n\r\n 4. 3 排列与组合 \r\n\r\n 4. 3. 1 引言 \r\n\r\n 4. 3. 2 排列 \r\n\r\n 4. 3. 3 组合 \r\n\r\n 4. 3. 4 二项式系数 \r\n\r\n 4. 3. 5 二项式定理练习 \r\n\r\n 4. 4 离散概率 \r\n\r\n 4. 4. 1 引言 \r\n\r\n 4. 4. 2 有限概率 \r\n\r\n 4. 4. 3 事件组合的概率 \r\n\r\n 4. 4. 4 概率的推理练习 \r\n\r\n 4. 5 概率论 \r\n\r\n 4. 5. 1 引言 \r\n\r\n 4. 5. 2 概率赋值 \r\n\r\n 4. 5. 3 事件的组合 \r\n\r\n 4. 5. 4 条件概率 \r\n\r\n 4. 5. 5 独立性 \r\n\r\n 4. 5. 6 伯努利实验与二项式分布 \r\n\r\n 4. 5. 7 随机变量 \r\n\r\n 4. 5. 8 期望值 \r\n\r\n 4. 5. 9 独立随机变量 \r\n\r\n 4. 5. 10 方差 \r\n\r\n 4. 5. 11 切比雪夫不等式 \r\n\r\n 4. 5. 12 平均状态下的计算复杂性练习 \r\n\r\n 4. 6 一般性的排列和组合 \r\n\r\n 4. 6. 1 引言 \r\n\r\n 4. 6. 2 有重复的排列 \r\n\r\n 4. 6. 3 有重复的组合 \r\n\r\n 4. 6. 4 具有不可区别物体的集合的排列 \r\n\r\n 4. 6. 5 把物体放入盒子练习 \r\n\r\n 4. 7 生成排列和组合 \r\n\r\n 4. 7. 1 引言 \r\n\r\n 4. 7. 2 生成排列 \r\n\r\n 4. 7. 3 生成组合 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第5章 高级计数技术 \r\n\r\n 5. 1 递推关系 \r\n\r\n 5. 1. 1 引言 \r\n\r\n 5. 1. 2 递推关系 \r\n\r\n 5. 1. 3 用递推关系构造模型练习 \r\n\r\n 5. 2　求解递推关系 \r\n\r\n 5. 2. 1 引言 \r\n\r\n 5. 2. 2 求解常系数线性齐次递推关系 \r\n\r\n 5. 2. 3 常系数线性非齐次的递推关系练习 \r\n\r\n 5. 3　分而治之关系 \r\n\r\n 5. 3. 1 引言 \r\n\r\n 5. 3. 2 分而治之关系练习 \r\n\r\n 5. 4 生成函数 \r\n\r\n 5. 4. 1 引言 \r\n\r\n 5. 4. 2 关于幂级数的有用的事实 \r\n\r\n 5. 4. 3 计数问题与生成函数 \r\n\r\n 5. 4. 4 使用生成函数求解递推关系 \r\n\r\n 5. 4. 5 使用生成函数证明恒等式练习 \r\n\r\n 5. 5 容斥 \r\n\r\n 5. 5. 1 引言 \r\n\r\n 5. 5. 2 容斥原理练习 \r\n\r\n 5. 6 容斥原理的应用 \r\n\r\n 5. 6. 1 引言 \r\n\r\n 5. 6. 2 容斥原理的另一种形式 \r\n\r\n 5. 6. 3　伊拉脱森筛 \r\n\r\n 5. 6. 4 映上函数的个数 \r\n\r\n 5. 6. 5 错位排列 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第6章 关系 \r\n\r\n 6. 1 关系及其性质 \r\n\r\n 6. 1. 1 引言 \r\n\r\n 6. 1. 2 函数作为关系 \r\n\r\n 6. 1. 3 集合上的关系 \r\n\r\n 6. 1. 4 关系的性质 \r\n\r\n 6. 1. 5 关系的组合练习 \r\n\r\n 6. 2 n元关系及其应用 \r\n\r\n 6. 2. 1 引言 \r\n\r\n 6. 2. 2 n元关系 \r\n\r\n 6. 2. 3 数据库和关系练习 \r\n\r\n 6. 3 关系的表示 \r\n\r\n 6. 3. 1 引言 \r\n\r\n 6. 3. 2 用矩阵表示关系 \r\n\r\n 6. 3. 3 用图表示关系练习 \r\n\r\n 6. 4 关系的闭包 \r\n\r\n 6. 4. 1 引言 \r\n\r\n 6. 4. 2 闭包 \r\n\r\n 6. 4. 3 有向图的路径 \r\n\r\n 6. 4. 4 传递闭包 \r\n\r\n 6. 4. 5 沃舍尔算法练习 \r\n\r\n 6. 5 等价关系 \r\n\r\n 6. 5. 1 引言 \r\n\r\n 6. 5. 2 等价关系 \r\n\r\n 6. 5. 3 等价类 \r\n\r\n 6. 5. 4 等价类与划分练习 \r\n\r\n 6. 6 偏序 \r\n\r\n 6. 6. 1 引言 \r\n\r\n 6. 6. 2 字典顺序 \r\n\r\n 6. 6. 3 哈斯图 \r\n\r\n 6. 6. 4 极大元素与极小元素 \r\n\r\n 6. 6. 5 格 \r\n\r\n 6. 6. 6 拓扑排序 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第7章 图 \r\n\r\n 7. 1 图的介绍 \r\n\r\n 7. 1. 1 图的种类 \r\n\r\n 7. 1. 2 图模型练习 \r\n\r\n 7. 2 图的术语 \r\n\r\n 7. 2. 1 引言 \r\n\r\n 7. 2. 2 基本术语 \r\n\r\n 7. 2. 3 一些特殊的简单图 \r\n\r\n 7. 2. 4 偶图 \r\n\r\n 7. 2. 5 特殊类型的图的一些应用 \r\n\r\n 7. 2. 6 从旧图到新图练习 \r\n\r\n 7. 3 图的表示和图的同构 \r\n\r\n 7. 3. 1 引言 \r\n\r\n 7. 3. 2 图的表示 \r\n\r\n 7. 3. 3 相邻矩阵 \r\n\r\n 7. 3. 4 关联矩阵 \r\n\r\n 7. 3. 5 图的同构练习 \r\n\r\n 7. 4 连通性 \r\n\r\n 7. 4. 1 引言 \r\n\r\n 7. 4. 2 通路 \r\n\r\n 7. 4. 3 无向图连通性 \r\n\r\n 7. 4. 4 有向图中的连通性 \r\n\r\n 7. 4. 5 通路与同构 \r\n\r\n 7. 4. 6 统计顶点之间的通路练习 \r\n\r\n 7. 5 欧拉通路与哈密顿通路 \r\n\r\n 7. 5. 1 引言 \r\n\r\n 7. 5. 2 欧拉回路和欧拉通路的充要条件 \r\n\r\n 7. 5. 3 哈密顿通路和回路练习 \r\n\r\n 7. 6 最短通路问题 \r\n\r\n 7. 6. 1 引言 \r\n\r\n 7. 6. 2 一个最短通路算法 \r\n\r\n 7. 6. 3 旅行推销员问题练习 \r\n\r\n 7. 7 平面性图 \r\n\r\n 7. 7. 1 引言 \r\n\r\n 7. 7. 2 欧拉公式 \r\n\r\n 7. 7. 3 库拉图斯基定理练习 \r\n\r\n 7. 8 图着色 \r\n\r\n 7. 8. 1 引言 \r\n\r\n 7. 8. 2 图着色的应用 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第8章 树 \r\n\r\n 8. 1 介绍树 \r\n\r\n 8. 1. 1 树作为模型 \r\n\r\n 8. 1. 2 树的性质练习 \r\n\r\n 8. 2 树的应用 \r\n\r\n 8. 2. 1 引言 \r\n\r\n 8. 2. 2 二叉搜索树 \r\n\r\n 8. 2. 3 决策树 \r\n\r\n 8. 2. 4 前缀码练习 \r\n\r\n 8. 3 树的遍历 \r\n\r\n 8. 3. 1 引言 \r\n\r\n 8. 3. 2 通用地址系统 \r\n\r\n 8. 3. 3 遍历算法 \r\n\r\n 8. 3. 4 中缀. 前缀和后缀记法练习 \r\n\r\n 8. 4 树与排序 \r\n\r\n 8. 4. 1 引言 \r\n\r\n 8. 4. 2 排序的复杂性 \r\n\r\n 8. 4. 3 冒泡排序 \r\n\r\n 8. 4. 4 归并排序练习 \r\n\r\n 8. 5 生成树 \r\n\r\n 8. 5. 1 引言 \r\n\r\n 8. 5. 2 一些构造生成树的算法 \r\n\r\n 8. 5. 3 回溯练习 \r\n\r\n 8. 6 最小生成树 \r\n\r\n 8. 6. 1 引言 \r\n\r\n 8. 6. 2 最小生成树算法 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第9章 布尔代数 \r\n\r\n 9. 1 布尔函数 \r\n\r\n 9. 1. 1 引言 \r\n\r\n 9. 1. 2 布尔表达式和布尔函数 \r\n\r\n 9. 1. 3 布尔代数中的恒等式 \r\n\r\n 9. 1. 4 对偶性 \r\n\r\n 9. 1. 5 布尔代数的抽象定义练习 \r\n\r\n 9. 2 布尔函数的表示 \r\n\r\n 9. 2. 1 积之和展开式 \r\n\r\n 9. 2. 2 函数完备性练习 \r\n\r\n 9. 3 逻辑门电路 \r\n\r\n 9. 3. 1 引言 \r\n\r\n 9. 3. 2 门的组合 \r\n\r\n 9. 3. 3 电路的例子 \r\n\r\n 9. 3. 4 加法器练习 \r\n\r\n 9. 4 电路的极小化 \r\n\r\n 9. 4. 1 引言 \r\n\r\n 9. 4. 2 卡诺图 \r\n\r\n 9. 4. 3 无需在意条件 \r\n\r\n 9. 4. 4 奎因-莫可拉斯基方法 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 第10章 计算模型 \r\n\r\n 10. 1 语言和文法 \r\n\r\n 10. 1. 1 引言 \r\n\r\n 10. 1. 2 短语结构文法 \r\n\r\n 10. 1. 3 短语结构文法的类型 \r\n\r\n 10. 1. 4 派生树 \r\n\r\n 10. 1. 5 巴科斯-诺尔范式练习 \r\n\r\n 10. 2 带输出的有限状态机 \r\n\r\n 10. 2. 1 引言 \r\n\r\n 10. 2. 2 带输出的有限状态机练习 \r\n\r\n 10. 3 不带输出的有限状态机 \r\n\r\n 10. 3. 1 引言 \r\n\r\n 10. 3. 2 串的集合 \r\n\r\n 10. 3. 3 有限状态自动机练习 \r\n\r\n 10. 4 语言的识别 \r\n\r\n 10. 4. 1 引言 \r\n\r\n 10. 4. 2 正则集合 \r\n\r\n 10. 4. 3 克莱因定理 \r\n\r\n 10. 4. 4 正则集合和正则文法 \r\n\r\n 10. 4. 5 一个不能由有限状态自动机识别语言 \r\n\r\n 10. 4. 6 一些更强大的机器练习 \r\n\r\n 10. 5 图灵机 \r\n\r\n 10. 5. 1 引言 \r\n\r\n 10. 5. 2 图灵机的定义 \r\n\r\n 10. 5. 3 用图灵机识别集合 \r\n\r\n 10. 5. 4 用图灵机计算函数 \r\n\r\n 10. 5. 5 不同类型的图灵机 \r\n\r\n 10. 5. 6 丘奇-图灵论题 \r\n\r\n 练习 \r\n\r\n 关键术语和结果 \r\n\r\n 复习题 \r\n\r\n 补充练习 \r\n\r\n 计算机题目 \r\n\r\n 计算和研究 \r\n\r\n 写作题目 \r\n\r\n 附录A 指数函数和对数函数 \r\n\r\n 附录B 伪代码 \r\n\r\n 奇数练习题答案 \r\n\r\n 推荐读物 \r\n\r\n 参考文献 \r\n
\r\n

离散数学既是计算机科学的理论基础, 又是计算机应用必不可少的工具. 《离散数学及其应用》的写作目标就是向读者展示离散数学的实用性：为计算机专业学生提供一切必要的数学基础, 使数学专业学生理解数学概念的重要性以及这些概念为什么对应用而言是重要的. 作者肯尼斯H. 罗森博士具有很深的数学造诣, 有丰富的教学经验. 我们翻译的这一本书是该书的第4版, 其第3版曾在欧美400多所学校使用, 获得了很大的成功. 成功的作品还要修订, 还要出新版, 可见作者对学术的追求和对读者的热爱.

新版并不是简单纠正旧版的错误. 信息时代使作者有可能与广大读者, 包括教师. 学生和自学者, 保持及时的联系. 新版对原版的修正反映的正是来自教和学两种实践的宝贵意见. 新增加的内容既包括离散数学新的研究成果, 也包括网络时代新的应用实例.

本书供1至2个学期使用. 本书使学生学会特定的一些数学事实并知道怎样应用, 更重要的是教会学生做数学思维, 因此本书强调数学推理和用不同的方法解题.

本书有五个重要的主题融为一体：数学推理. 组合分析. 离散结构. 算法思维以及应用和模拟. 一门成功的离散数学课应该使这五部分内容有机地交融和取得平衡.

阅读. 理解和构造数学证明依赖于数学推理的能力. 逻辑和数学归纳技术是数学推理的基础. 组合分析是一项重要的解题技巧, 它指的是借助枚举而非公式来解决数学问题. 离散结构是抽象的数学结构, 包括集合. 置换. 关系. 图. 树和有限状态机等, 用于表示离散对象及离散对象之间的关系. 借助计算机解题需要给出程序, 程序设计必须从算法规范入手. 算法思维指的是算法设计（给出规范）. 正确性证明和复杂性分析. 离散数学已应用到包括化学. 植物学. 动物学. 语言学. 地理学. 商业以及互联网等众多的领域, 为各个领域建立

数学模型是离散数学应用的基础. 应用模拟是另一项重要的解题技巧.

显然, 以上五个主题互为依存, 它们构成离散数学的整体. 本书既说明了它们独立的作用, 又突出了它们有机的结合.

罗森博士在写作过程中充分考虑了教和学两个方面的需要, 为教师和学生分别编撰了参考资料, 并在书中提供了各章节相关的网站地址. 从这些方面来看, 这是译者见过的最完备. 最成熟的教材.

译者大多有多年的从事计算机专业离散数学课程教学的经验, 他们参与编撰的离散数学教材获得过多种奖励. 希望本译著的出版能为我国离散数学的教与学提供宝贵的参考.

直接参与翻译的共有4人：袁崇义. 屈婉玲. 王捍贫. 刘田.

译者

2001年4月

肯尼斯H. 罗森（Kenneth H.Rosen）是AT＆T荷姆德尔实验室（新泽西州）新概念领域人才部的杰出成员.

罗森博士1972年获密执安大学数学学士学位, 1976年获麻省理工学院数学博士学位, 其博士论文研究的是数论, 导师为H. 斯达克（Harold Stark）. 在1982年加入Bell实验室以前, 他曾在科罗拉多大学（位于Boulder）和俄亥俄州立大学（位于Columbus）工作, 并在缅因大学（位于Orono）担任数学副教授. 在AT＆T实验室工作时, 罗森还在蒙马斯大学计算机科学夜校任教, 教授离散数学. 编码理论和数据安全的课程.

罗森博士已在专业期刊上发表了数论及数学模型领

多年来教授离散数学的经验和兴趣指引我写作本书. 对学生而言, 我的目的是为他们提供准确而可读的教材, 使离散数学的概念和技术得以清晰地介绍和演示. 我的目标是向爱怀疑的学生们展示离散数学的相关领域和实用性. 我希望为学习计算机科学的学生提供一切必需的数学基础. 我希望使学数学的学生理解数学概念的重要性以及这些概念为什么对应用而言是重要的. 而且我希望既能达到这些目标, 又不使教材含太多的水分.

对教师而言, 我的目的是使用成熟的数学教学技术设计一个灵活而全面的教学工具. 我希望为教师们提供一套有效的教材, 使他们能高效地以适合于特定学生特点的方式教授离散数学. 我希望已经达到这些目标.

我为此教材已经取得的巨大成功而分外高兴. 此次第4版的许多改进都是成功使用本书的400多所学校大批师生反馈和建议的结果. 此版有许多提高之处. 原有的辅助材料更加丰富, 还有配套网站提供的辅助材料, 使它更易于被师生使用以达到他们的目标.

本教材为是1至2个学期的入门离散数学课而写的, 适用于包括数学专业. 计算机科学专业和工程专业在内的许多专业的学生. 大学代数是它唯一的预备课程. 离散数学课的目标

一门离散数学课有多个目标. 学生应该学会特定的一些数学事实并知道怎样应用, 更重要的是, 这样一门课应教会学生怎样作数学思维. 为达到这些目标, 本教材强调数学推理及用不同的方法解题. 本教材有5个重要的主题交织在一起：数学推理. 组合分析. 离散结构. 算法思考以及应用和建模. 一门成功的离散数学课应该细心地使这五部分内容交融和取得平衡.

数学推理：学生必须理解数学推理以便阅读. 理解和构造数学证明. 本教材以数理逻辑开篇, 因为数理逻辑是随后讨论的证明方法的基础. 数学归纳技术是通过许多例子来重点介绍的. 通过这些例子还仔细地说明了为什么数学归纳是有效的证明技术.

组合分析：解题的一项重要技巧是计数或枚举对象的能力, 本书中对枚举的讨论就从基本的计数技术着手. 重点是用组合分析来解决计数问题而不使用公式.

离散结构：一门离散数学课应该教学生如何使用离散结构, 离散结构是抽象的数学结构, 用来表示离散对象及离散对象之间的关系. 离散结构包括集合. 置换. 关系. 图. 树和有限状态机.

算法思考：有几类问题是从给出算法说明入手求解的. 描述了算法以后就可构造计算机程序来实现它, 这一过程中的数学部分包括算法说明, 证实它能正确执行, 以及分析执行这一算法所需要的计算机内存和时间. 所有这些内容均在本书中介绍. 算法是用文字陈述和易于理解的一种伪码这样两种方式描述的.

应用与建模：离散数学已被应用到几乎所有研究领域. 本书既有许多计算机科学和数据网络的应用实例, 也有各式各样领域中的应用实例, 包括化学. 植物学. 动物学. 语言学. 地理. 商业以及因特网. 这些实例均是离散数学的自然而重要的应用, 不是编造的. 用离散数学建模是十分重要的解题技巧, 本书的练习使学生有机会通过构造自己的模型来发展这一技巧.

为什么要出第4版

本书第3版在美国的400多所学校, 加拿大的几十所大学, 以及在欧洲. 亚洲和大洋洲的大学使用获得成功. 许多学生和教授均喜欢第3版的形式, 那么为什么还要出第4版？这个问题值得认真回答.

首先, 尽管第3版使用起来十分有效, 许多教师还是要求做某些特定的改进. 许多人希望改动正文, 增加例题或使例题更易于理解, 增加某种类型的练习, 或增加能覆盖新内容的练习等. 在新版中找根据已收到的大量建议对本书作了改进. 根据用户要求做的改动使本版变得更好.

第二, 离散数学是一个活跃的学科, 每年都有许多新发现, 其中有一些可以反映在教科书中. 于是我在本版中收入了自第3版以来的某些新发现（随后的新发现将在本版以后印刷时尽可能收入, 在网站上也会有反映）.

第三, 自第3版发行以来, 因特网变得十分重要, 十分有用. 在本版中将有把离散数学的应用和因特网自身结构联系起来的例题和练习. 与本版配套的还有一个内容广泛的网站, 它能对正文作有益的补充, 为师生提供额外材料. 想更多学习离散数学的人还可以通过本网站提供的路径访问网上有关的网站. 不过, 由于许多人不选用与本课程相连的网站, 所以本书正文中给出了若干Web图标, 指示网站链接, 作为注释本书网站的网上指南.

下面列出的是本版中为使本书更有效所做的主要变动.

1. 新添内容

除大（）记号以外新增加了大 和大 记号.

概率论的新内容包括随机变量的方差和切比雪夫不等式. 此外, 还对Monty大厅三门问题做了讨论.

对停机问题做了处理, 包括其不可解的证明.

讨论了流动推销员问题.

2. 扩充了原有内容

增加了关于数理逻辑和数学推理的附加材料, 用新增例题说明怎样在量化语句和文字陈述之间互译, 强化了推理规则的讨论. 特别是关于量化语句的推理规则, 现在明确地做了讨论, 并且增加了阐明为何使用推理规则的例题.

加强了对底函数和顶函数的讨论.

正文中现在专有一节讨论生成函数, 这是对原书附录内容的扩充. 这一节的中心是生成函数怎样用于解决计数问题, 解决递归关系, 及证明组合恒等式.

常系数非齐次线性递归关系现在在正文中讨论, 而不是放在一组练习题中.

对整数序列进行了更多的介绍, 增加了从初始项识别整数序列可能的通项公式的例题和练习.

增加了传记内容, 包括Peirce（皮尔斯）. Chebyshev（切比雪夫）. Knuth（克努斯）. Hardy（哈弟）. Ramanujan（拉曼扭因）. Tukey（图凯）. Sloane（斯罗尼）和Mersenne莫孙尼）.

3. 跟上时代的新例题

在课文某些关键之处增加了例题, 用以帮助解释学生难于理解的重要概念, 使课本更有趣.

增加了说明离散数学应用于因特网通信协议和网络结构的例题和练习. 其中包括：与因特网地址及因特网协议包有关的计数问题, 因特网搜索引擎使用的布尔搜索问题, 还增加了一个关于怎样在IP组播中使用生成树的例题.

增加了材料以说明离散数学仍有许多未解决的问题, 仍是不断有新发现的活跃领域. 例如增加了莫孙尼素数的内容, 包括1997年和1998年新发现的素数, 还讨论了哥德巴赫猜想已经证明有效的范围, 阐述了汉诺塔难题的变种, 即有四根塔柱的问题.

4. 扩充了练习题

根据使用第3版的教师们的要求, 增加了500多道练习题, 包括常规的和有挑战性的问题, 还包括基于逻辑和数学智力游戏的练习. 新的分块练习题以一系列步骤展开一些关键概念. 新练习能保证所有重要类型的题目既有奇数编号的, 也有偶数编号的. 此外, 还有与以前学过的微积分有关的练习, 不过对这些习题按习惯作了注明, 不想做的话很容易就能避开它们.

5. 网上支持

做为正文的补充, 已建立了一个既适合于学生也适合于教师的网站, 它包含范围广泛的内容（见“配套网站”）, 包括一个注释性的网上指南, 列出因特网上相关的网站. 这一指南对课本正文能提供重要线索, 在本版整个生命期中将不断更新以保证跟上发展.

课文中凡是网上指南有链接指向与所讨论内容相关的网站的地方, 均有Web图标. （指南中不同的链接有200多个. ）网上的这些网站包含有关概念和应用的补充材料. 名人传记. 最新发现. 可下载的源代码. 交互式小应用程序（applet）. 动画的算法以及其他有趣的内容.

特别之处

易入门 实践证明本书对初学者来说易读易懂. 它的大部分内容只要求学生学过大学代数, 不需要其他的预备知识, 少数涉及微积分的地方均有明确的说明. 大部分学生应该很容易理解课文中用于表示算法的伪码, 不管他们是否学过程序设计语言. 本书不要求形式化的计算机科学方面的预备知识.

灵活 本书为灵活使用作了精心设计. 各章对其前面内容的依赖降到最小. 每一章部分成长度大致相等的若干节, 每一节又根据内容的自然分块划分成小节以便教学. 教师可以根据这些分块很容易地安排进度.

写作风格 本书体现的写作风格是直接和实用. 使用了准确的数学语言, 但没有过份的形式化与过份的抽象, 在适当的地方引入并使用记号. 在数学陈述中对记号和文字的平衡作了仔细的考虑.

广泛的课堂实践 本书已在400多所学校使用过, 其中325所以上使用了不止一次. 来自许多学校师生的反馈使第4版成为比前几版更成功的教学工具.

数学上的严密性和准确性 本书所有的定义和定理均是分外细心陈述的. 所以学生可以欣赏其语言的准确以及数学上的严密性. 证明则是缓慢引入并展开的, 每一步都经细心论证, 递归定义均有周密的解释并大量使用.

图和表 本书有550多幅图, 用于阐明关键的概念和证明步骤. 图上带有细心选用的颜色用以解释重点. 只要可能, 就用表格来小结关键内容或说明量化关系.

实例 本书用650多个实例阐明概念, 表示不同内容的关系, 以及引入应用. 在例题中, 首先提出一个问题, 再按适度的细节给出它的解.

应用 本书包含的应用展示了离散数学在解决现实世界问题中的使用价值. 本书所含的应用涉及的范围很广, 包括计算机科学. 数据网络. 心理学. 化学. 工程. 语言学. 生物学. 商业和因特网.

算法 离散数学的结果常能用算法表示, 因此本书每一章均介绍了关键算法. 这些算法一方面用文字描述给出, 另一方面又用一种易于理解的结构化伪码的形式给出. 附录2中对伪码作了描述和说明. 书中对算法的计算复杂性也有初步的分析.

历史资料 本书对许多题材的背景作了简要的介绍. 书中以脚注的形式给出了55位以上的数学家和计算机科学家的传记. 传记中介绍了对离散数学作出巨大贡献的这些科学家们的生活. 事业及成就. 此外, 作为对正文中历史资料的补充, 还有大量史实的脚注.

关键术语和结果每一章后面都列出了本章的关键术语和结果. 关键术语只包括学生必须学会的那些最重要的而不是该章中定义的所有术语.

练习 正文中有3000多道练习, 提出了大量不同类型的问题. 有足够多的简单直接的问题用于开发基本技巧, 还有大量的中等程度的练习和许多有挑战性的练习. 练习的叙述是明白而无二义性的, 全部按难易程度分级. 分组给出的练习包含专门的讨论, 提出正文中没有涉及的新概念, 使学生可以通过自己的努力发现新思想.

比平均水平稍难的练习部用一个星号作了标记, 相当有挑战性的问题则用两个星号标记. 必须用微积分来解的练习均有明确说明. 能导出正文中用到的结果的练习则用手指符号指明, 在正文最后给出了所有奇数号的练习的答案或解题概略, 其中包括清楚给出的大多数证明步骤.

复习题 每章最后都有一组复习题. 这些问题的设计目的是帮助学生集中学习该章最重要的概念和技术. 学生必须写出长长的答案才能回答这些问题, 而不能只作计算或简短的应答.

补充练习 每章后面都有一组丰富而多变的补充练习. 这些练习一般来说都比每一节后面的练习难度大. 补充练习使一章的概念得以加强, 并把不同内容更好地融为一体.

计算机题目 每一章后面还有一组计算机题目. 这大约150个计算机题目可以把学生已经学到的计算和离散数学的内容联系起来. 从数学角度或程序设计角度看来难度超过平均水平的计算机题目用一个星号标记, 特别难的则用两个星号标记.

计算和研究每一章的结尾都有一级计算和探索性问题. 这些练习（大约共100个）的完成需要用现有的软件工具, 例如学生或教师自己编写的程序, 或数学计算软件包, 如MAPLE或Mathematica. 不少这种练习为学生提供了通过计算发现新事实或新思想的机会. （有些这类练习在本书的姊妹篇《用MAPLE研究离散数学及其应用》中作了讨论. ）

写作题目 每一章后面都有一组应书面完成的题目. 学生需要参考数学文献才能做这类题目. 有些这类题目涉及历史, 可能需要查找原始资料. 其他的题目起着联系新题材和新思想的作用. 所有此类练习均向学生展示了正文中没有深入探讨的思想. 这些题目把数学概念和书面写作过程结合在一起, 以帮助学生探索可供未来研究的领域. （为这些题目准备的推荐文献可以在《学生解题指南》中找到. ）

附录 正文有两个附录. 第一个介绍指数函数和对数函数, 以回顾课程中反复使用的某些基本内容, 第二个介绍正文中用以描述算法的伪码.

推荐读物 在正文最后专门有一节为每一章提供推荐读物, 其中包括不超过本书水平的书籍. 较难的书籍. 综述性文章以及发表离散数学新发现的原始文章.