离散数学及其应用

《离散数学及其应用（原书第7版）》是介绍离散数学理论和方法的经典教材，已经成为采用率优选的离散数学教材，被美国众多名校用做教材，获得了极大的成功。本书中文版也已被靠前大学广泛采用为教材。作者罗森参考教师和学生的反馈，并结合自身对教育的洞察，在第7版中做了大量的改进，使其成为更有效的教学工具。本书可作为1～2个学期的离散数学课程教材，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。

罗森编著的《离散数学及其应用（原书第7版）》是经典的离散数学教材，为优选多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法，内容涉及数学推理、组合分析、离散结构、算法思想以及应用与建模。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的实例和图表说明、各种练习和题目以及丰富的历史资料和网站资料。第7版在前六版的基础上做了大量的改进，使其成为更有效的教学工具。
本书可作为高等院校数学、计算机科学和计算机工程等专业的教材或参考书。

Kenneth H.Rosen，作为位于新泽西州蒙茅斯县的AT＆T实验室杰出技术会员已经拥有一段很长的职业生涯。目前他在蒙茅斯大学任访问研究教授，为研究生讲授计算机科学课程。
Rosen博士于1972年获得位于安娜堡的密歇根大学数学学士学位，1976年获得麻省理工学院数学博士学位，在哈罗德·斯塔克（Harold Stark）的指导下他撰写了数论方面的博士论文。1982年加入贝尔实验室之前，他曾就职于科罗拉多大学博尔德分校；哥伦布市的俄亥俄州立大学；在欧洛诺市的缅因大学任数学副教授。在AT&T工作时，他在蒙茅斯大学任教，教授离散数学、编码理论和数据安全方面的课程。他目前教授算法设计以及计算机安全和密码学方面的课程。

出版者的话
译者序
前言
配套网站
致学生
关于作者
符号表
第1章基础：逻辑和证明
1.1命题逻辑
1.1.1引言
1.1.2命题
1.1.3条件语句
1.1.4复合命题的真值表
1.1.5逻辑运算符的优先级
1.1.6逻辑运算和位运算
练习
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.3.3德·摩根律的运用
1.3.4构造新的逻辑等价式
1.3.5命题的可满足性
1.3.6可满足性的应用
1.3.7可满足性问题求解
练习
1.4谓词和量词
1.4.1引言
1.4.2谓词
1.4.3量词
1.4.4约束论域的量词
1.4.5量词的优先级
1.4.6变量绑定
1.4.7涉及量词的逻辑等价式
1.4.8量化表达式的否定
1.4.9语句到逻辑表达式的翻译
1.4.10系统规范说明中量词的使用
1.4.11选自路易斯·卡罗尔的例子
1.4.12逻辑程序设计
练习
1.5嵌套量词
1.5.1引言
1.5.2理解涉及嵌套量词的语句
1.5.3量词的顺序
1.5.4数学语句到嵌套量词语句的翻译
1.5.5嵌套量词到自然语言的翻译
1.5.6汉语语句到逻辑表达式的翻译
1.5.7嵌套量词的否定
练习
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.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.8证明的方法和策略
1.8.1引言
1.8.2穷举证明法和分情形证明法
1.8.3存在性证明
1.8.4专享性证明
1.8.5证明策略
1.8.6寻找反例
1.8.7证明策略实践
1.8.8拼接
1.8.9开放问题的作用
1.8.10其他证明方法
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第2章基本结构：集合、函数、序列、求和与矩阵
2.1集合
2.1.1引言
2.1.2文氏图
2.1.3子集
2.1.4集合的大小
2.1.5幂集
2.1.6笛卡儿积
2.1.7使用带量词的集合符号
2.1.8真值集和量词
练习
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.3.6部分函数
练习
2.4序列与求和
2.4.1引言
2.4.2序列
2.4.3递推关系
2.4.4特殊的整数序列
2.4.5求和
练习
2.5集合的基数
2.5.1引言
2.5.2可数集
2.5.3不可数集合
练习
2.6矩阵
2.6.1引言
2.6.2矩阵算术
2.6.3矩阵的转置和幂
2.6.40—1矩阵
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第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大O记号
3.2.3一些重要函数的大O估算
3.2.4函数组合的增长
3.2.5大Ω与大Θ记号
练习
3.3算法的复杂度
3.3.1引言
3.3.2时间复杂度
3.3.3矩阵乘法的复杂度
3.3.4算法范型
3.3.5理解算法的复杂度
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第4章数论和密码学
4.1整除性和模算术
4.1.1引言
4.1.2除法
4.1.3除法算法
4.1.4模算术
4.1.5模m算术
练习
4.2整数表示和算法
4.2.1引言
4.2.2整数表示
4.2.3整数运算算法
4.2.4模指数运算
练习
4.3素数和优选公约数
4.3.1引言
4.3.2素数
4.3.3试除法
4.3.4埃拉托斯特尼筛法
4.3.5关于素数的猜想和开放问题
4.3.6优选公约数和最小公倍数
4.3.7欧几里得算法
4.3.8gcd的线性组合表示
练习
4.4求解同余方程
4.4.1引言
4.4.2线性同余方程
4.4.3中国剩余定理
4.4.4大整数的计算机算术
4.4.5费马小定理
4.4.6伪素数
4.4.7原根和离散对数
练习
4.5同余应用
4.5.1散列函数
4.5.2伪随机数
4.5.3校验码
练习
4.6密码学
4.6.1引言
4.6.2古典密码学
4.6.3公钥密码学
4.6.4RSA密码系统
4.6.5RSA加密
4.6.6RSA解密
4.6.7用RSA作为公钥系统
4.6.8密码协议
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第5章归纳与递归
5.1数学归纳法
5.1.1引言
5.1.2数学归纳法
5.1.3为什么数学归纳法是有效的
5.1.4数学归纳法的优点与缺点
5.1.5利用数学归纳法证明的例子
5.1.6使用数学归纳法时犯的错误
5.1.7运用数学归纳法证明的原则
练习
5.2强归纳法与良序性
5.2.1引言
5.2.2强归纳法
5.2.3利用强归纳法证明的例子
5.2.4计算几何学中使用强归纳法
5.2.5利用良序性证明
练习
5.3递归定义与结构归纳法
5.3.1引言
5.3.2递归地定义函数
5.3.3递归地定义集合与结构
5.3.4结构归纳法
5.3.5广义归纳法
练习
5.4递归算法
5.4.1引言
5.4.2证明递归算法的正确性
5.4.3递归与迭代
5.4.4归并排序
练习
5.5程序正确性
5.5.1引言
5.5.2程序验证
5.5.3推理规则
5.5.4条件语句
5.5.5循环不变量
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第6章计数
6.1计数的基础
6.1.1引言
6.1.2基本的计数原则
6.1.3比较复杂的计数问题
6.1.4减法法则（两个集合的容斥原理）
6.1.5除法法则
6.1.6树图
练习
6.2鸽巢原理
6.2.1引言
6.2.2广义鸽巢原理
6.2.3鸽巢原理的几个简单应用
练习
6.3排列与组合
6.3.1引言
6.3.2排列
6.3.3组合
练习
6.4二项式系数和恒等式
6.4.1二项式定理
6.4.2帕斯卡恒等式和三角形
6.4.3其他的二项式系数恒等式
练习
6.5排列与组合的推广
6.5.1引言
6.5.2有重复的排列
6.5.3有重复的组合
6.5.4具有不可区别物体的集合的排列
6.5.5把物体放入盒子
练习
6.6生成排列和组合
6.6.1引言
6.6.2生成排列
6.6.3生成组合
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第7章离散概率
……
第8章高级计数技术
第9章关系
第10章图
第11章树
第12章布尔代数
第13章计算模型
附录A实数和正整数的公理
附录B指数与对数函数
附录C伪代码
推荐读物
参考文献
奇数编号练习答案

    《计算机科学丛书：离散数学及其应用（原书第7版）》是根据我多年讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供准确且可读性很强的教材，清晰地介绍并展示离散数学中的概念和技术。我的目标是向爱怀疑的学生们展示离散数学的相关性和实用性，希望为学习计算机科学的学生提供一切必需的数学基础，也希望学数学的学生理解重要的数学概念，以及为什么这些概念对应用来说很重要，很重要的是希望本书既能达到这些目标，又不含太多的水分。
     对教师而言，我的目的是要利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具，希望为教师提供能够以很适合特定学生特点的方式高效地教授离散数学的教材。希望本书能够达到这些目标。
     我为本教材在过去所取得的巨大成功而感到很好欣慰。根据北美600多所学校以及优选各地许多大学成功采用了本书的大批师生的反馈和建议，此次第7版进行了许多改进。
     本教材是为一至两个学期的离散数学入门课程而设计的，适用于数学、计算机科学和工程等各类专业的学生。虽然专享的先修课程要求是大学代数，但是要想真正学好离散数学还需要掌握更多的数学知识。离散数学课程的目标
     离散数学课程有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用，更重要的是，这样一门课应培养学生的数学逻辑思维。为此，本教材特別强调数学推理以及用不同的方法解题。本书中五个重要主题交织在一起：数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程应该努力使这五个主题相互融合．、平衡。
     1．数学推理：学生必须理解数学推理，以便阅读、领会并构造数学论证。本书以数理逻辑开篇，在后面证明方法的讨论中，数理逻辑是基础。本书描述了构造证明的方法与技巧。本书特別强调数学归纳法，不仅给出了这种证明的许多不同类型的实例，还详细地解释了数学归纳法为什么是有效的证明技术。
     2．组合分析：一个重要的解题技巧就是计数或枚举对象。本书中，对枚举的讨论从计数的基本技术着手，重点是用组合分析方法来解决计数问题并分析算法，而不是简单地应用公式。
     3．离散结构：离散数学课程应该教会学生如何处理离散结构，即表示离散对象以及对象之间关系的抽象数学结构。离散结构包括集合、置换、关系、图、树和有限状态机等。
     4．算法思维：有些问题可以通过详细说明其算法来求解。在清楚地描述算法后，就可以构造一个计算机程序来实现它。这一过程中涉及的数学部分包括算法的详细说明、正确性验证以及执行算法所需要的计算机内存和时间的分析等，这些内容在本书中均有介绍。算法是用英语和一种易于理解的伪代码来描述的。
     5．应用与建模：离散数学几乎在每个可以想象到的研究领域中都有应用，本书介绍了其在计算机科学和数据网络中的许多应用，还介绍了在其他各种领域中的应用，如化学、植物学、动物学、语言学、地理学、商业以及因特网等。这些均是离散数学的实际而又重要的应用，而不是编造的。
     ……