本书是经典的离散数学教材,被全球数百所大学广为采用。本科教学版缩减了篇幅,保留的主要内容包括:逻辑和证明,集合、函数、序列、求和与矩阵,计数,关系,图,树,布尔代数。全书取材广泛,除包括定义、定理的严格陈述外,还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新,成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材,也可作为科技领域从业人员的参考书。
无
本书是根据我多年来讲授离散数学的经验和兴趣写成的。对学生而言,我的目的是为他们提供内容准确且可读性强的教材,清晰地介绍并展示离散数学中的概念和技术。对于那些爱怀疑的学生,我的目标是展示离散数学的相关性和实用性。对于计算机科学专业的学生,我希望为他们将来的学习提供一切必需的数学基础。而对于数学专业的学生,我希望帮助他们理解重要的数学概念,并且意识到为什么这些概念对应用来说很重要。最重要的是,希望本书既能达到这些目标,又不含太多的水分。
对教师而言,我的目的是利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具:只要有本书在手,教师就能迅速地从中筛选内容,以最适合特定学生的方式有效地开展离散数学的教学工作。希望我已经实现了这些目标。
在过去的30年中,本书取得了极大的成功,被世界各地超过100万名学生使用,并被翻译成多种语言,对此我感到非常欣慰。此次第8版所做的许多改进,正是得益于大量读者的反馈和建议。在这些读者中,既有来自北美600多所学校的师生,又有来自全球各地众多高校的读者,他们都曾将本书成功用作教材。由于所收到的这些反馈,以及在不断更新中所投入的大量精力,我才能够在每次升级时显著提高本书的吸引力和有效性。
本教材是为一学期或两学期的离散数学入门课程而设计的,适用于数学、计算机科学、工程等各类专业的学生。大学代数是唯一要求的先修课程,不过,要想真正学好离散数学,还是需要有一定的数学素养。本书的设计目标是满足各种类型离散数学入门课程的需求,内容高度灵活且非常全面。我希望本书不仅是一本成功的教科书,而且成为学生在日后的学习和职业生涯中可以参考的有价值的资源。
离散数学课程的目标
离散数学课程有多个目标。学生应该学会一系列特定的数学知识并知道怎样应用它们,更重要的是,这门课应教会学生怎样运用数学逻辑思维。为了达到这些目标,本教材特别强调数学推理以及问题求解的不同方法。本书中,五个重要主题将交织在一起:数学推理,组合分析,离散结构,算法思维,以及应用与建模。一门成功的离散数学课程应该小心谨慎地融合并平衡所有五个主题。
●数学推理。学生必须理解数学推理以便阅读、领会并构造数学论证。本书开篇即讨论数理逻辑,这为后续讨论证明方法打下了基础。本书描述了构造证明的方法与技巧两个方面。本书特别强调数学归纳法,不仅给出了这种证明技术的许多不同类型的实例,还详细地解释了数学归纳法为什么是一种有效的证明技术。
●组合分析。一个重要的解题技巧就是计数或枚举对象。本书中关于枚举的讨论从计数的基本技术着手。重点是运用组合分析方法来解决计数问题并分析算法,而不是简单地应用公式。
●离散结构。离散数学课程应该教会学生如何处理离散结构,即表示离散对象以及对象之间关系的抽象数学结构。这些离散结构包括集合、置换、关系、图、树和有限状态机等。
●算法思维。有些类型的问题可以通过算法的规范说明来求解。当一个算法被清楚地描述后,就可以编写计算机程序来实现之。该活动涉及的数学部分包括该算法的规范说明、正确性的验证,以及执行算法所需要的计算机内存和时间分析等,这些在本书中均有阐述。算法将采用自然语言
原书采用英语,而中译版则采用汉语。——译者注和一种易于理解的伪代码形式来描述。
●应用与建模。离散数学在几乎每个可以想到的研究领域中都有应用。许多应用涉及本书提到的计算机科学和数据网络,还有一些应用涉及更为广泛的领域,如化学、生物学、语言学、地理学、商业和互联网等。这些是离散数学的自然而又重要的应用,而非人为编造的。用离散数学来建模是一项十分重要的问题求解技巧,学生可通过一些练习来自己构造模型,从而掌握这一技巧。
本书特色
易理解性。实践证明,本书对于初学者来说是易读易懂的。书中绝大部分内容不需要比大学代数更多的数学预备知识,需要额外帮助的学生可以在配套网站找到相应工具,以将数学素养提升到本书要求的水准。书中少数几处需要用到微积分知识的地方都已注明。大多数学生应该很容易理解用于表示算法的伪代码,无论是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易于理解和易于领会的水平开始。一旦详细介绍了基本数学概念,就会给出稍难一些的内容以及在其他研究领域中的应用。
灵活性。为了便于灵活使用,本书做了精心的设计。各章对之前章节的依赖程度都被降到最低。每章分成长度大致相等的若干节,每节又根据内容划分成若干小节以方便教学。教师可以利用章节划分灵活地安排讲课进度。
写作风格。本书的写作风格是直接而又实用的。书中使用准确的数学语言,但没有采用过多的形式化与抽象,在数学命题中的记号和词语表达间做了精心的平衡。
数学严谨性和准确性。书中所有定义和定理的陈述都十分谨慎,这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则是先由动机引入,然后再慢慢展开,并且所有步骤都经过了详细论证。
例题。全书共有超过400道例题,用来阐述概念、建立不同主题之间的关联以及介绍应用。在大部分例题中,首先提出问题,然后再以适量的细节给出解法。
应用。本书中的应用展示了离散数学在解决现实世界中的问题时的实用性。这些应用涉及广泛的领域,包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和互联网。
算法。离散数学的结论常常要用算法来表述,故书中多数章节都介绍了一些关键算法。这些算法采用文字叙述,同时也采用一种易于理解的结构化伪代码来描述。对于本书中的所有算法,都简要分析了其计算复杂度。
关键术语和结论。每章最后列出关键术语和结论。关键术语只列出学生必须学会的那些,而非该章中定义的每个术语。
练习。书中包含2000多道练习题,涵盖大量不同类型的问题。不仅提供了足够多的简单练习用于培养基本技能,还提供了大量中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义,并按难易程度进行了分级。练习中还包含一些特殊的讨论来展开正文中没有涉及的新概念,使得学生能够通过自己的努力来发现新的想法。
那些比平均难度稍难的练习用一个星号(*)标记,而那些更具挑战性的练习则用两个星号(**)来标记。需要用微积分知识求解的练习会明确指出。有些练习的结果要在正文中用到,我们用符号来标识这类题目。本书最后给出了所有奇数编号练习的答案或解题纲要。答案中大部分证明的步骤都十分清晰。
复习题。每章后面都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。要回答这些复习题,学生必须写出较长的答案,而不是仅做一些计算或给出简答。
补充练习。每章后面都有一组丰富多样的补充练习。这些练习通常比每节后面的练习难度更大。补充练习旨在强化该章中的概念,并把不同主题更有效地综合起来。
计算机课题。每章后面还有一组计算机课题。全书共有大约150道计算机课题,用于将学生在计算和离散数学中所学到的内容联系起来。对于那些从数学角度或程序设计角度来看难度超过平均水平的计算机课题,我们用一个星号(*)标记,而那些非常具有挑战性的题目则用两个星号(**)标记。
计算和探索。每章后面都有一组计算和探索性的问题,共有大约120道。完成这些练习需要借助现有的软件工具,诸如学生或教师自己编写的程序,或像Maple或Mathematica这样的数学计算软件包。这些练习大多为学生提供了通过计算来发现一些新事实或想法的机会。(其中一些练习在配套的在线练习册《探索离散数学》(Exploring Discrete Mathematics)中也有讨论。)
写作课题。每章后面都有一组写作课题,要完成这类题目,学生需要参考数学方面的文献。有些题目本质上是关于历史知识的,需要学生查找原始资料;其他题目则将带领学生通往新内容和新思想。这些练习旨在向学生展示正文中没有深入探讨的想法,通过把数学概念和写作过程结合起来,帮助学生面对未来可能的研究领域。(在网络版或印刷版的《学生解题指南》(Student’s Solutions Guide)中可以找到为这些题目准备的参考文献。)
教辅资源
关于本书教辅资源,只有使用本书作为教材的教师才可以申请,需要的教师可向麦格劳·希尔教育出版公司北京代表处申请,电话01057997618/7600,传真01059575582,电子邮件instructorchina@mheducationcom。——编辑注
《学生解题指南》。这本可以单独购买的学生手册包含所有奇数编号练习的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这种方法管用。对于有些问题,还给出了一两种其他可能的解法,以说明一个问题可以用多种不同方法来求解。指南的内容还包括:为每章后面的写作课题推荐的参考文献;关于如何撰写证明的指南;在离散数学学习中学生常犯的各类错误;为每章提供的考试样例及解答,以帮助学生准备考试。
《教师资料手册》。本手册在网站上提供,教师也可以申请印刷版,手册中包含书中所有偶数编号练习的完整解答。手册的内容还包括:关于如何讲授本书每章内容的建议,包括每节中应强调的重点以及如何组织内容;为每章提供的考试样例,以及一个包含1500多道考试题目的可选试题库,对于所有考试样例及试题库中的题目都给出了解答;针对不同的侧重点以及不同学生能力水平的课程教学大纲样本。
致谢
感谢所有将本书用作教材的教师和学生,他们来自不同的学校,并向我提供了很多有价值的反馈和有益的建议。正是有了他们的反馈,才使本书变得更为出色。特别感谢Jerrold Grossman和Dan Jordan,作为第8版的技术评审,他们以“鹰眼”般敏锐的目光确保了本书的准确性。在本书出版过程中的各个阶段,他们两位多次审阅了本书的每个角落,帮助消除了之前勘误表中的错误,并防止出现新的错误。
感谢Dan Jordan为《学生解题指南》和《教师资源手册》做出的贡献。他在更新这些教辅资源方面完成了令人钦佩的工作。感谢Jerrold Grossman,他是本书前7版教辅资源的作者,并为Dan提供了非常有价值的帮助。还要感谢许许多多曾经为本书创建并维护在线资源的人。特别感谢Dan Jordan和Rochus Boerner,他们所做的大量工作解决了配套网站的诸多问题(后面会介绍这个网站)。
感谢第8版以及所有之前版本的审稿人。他们给予我许多有益的批评和鼓励,希望这一版不会辜负他们的期望。自从本书第1版出版以来,已经有超过200位审稿人,其中有许多来自美国以外的国家。近期审稿人列表如下。
近期审稿人
感谢阅读过本书的学生,他们提供了很多建议并报告了一些勘误。在蒙茅斯大学时,曾经上过我的离散数学课程的学生,包括本科生和研究生,从方方面面帮助我改进了书中内容。
还要感谢麦格劳希尔高等教育(本书的出版商)的工作人员,以及Aptara的生产人员。我还想感谢兰登书屋原来的编辑Wayne Yuhasz,以及本书之前的许多编辑,他们的见解和技巧是本书成功的有力保障。
我想对产品经理Nora Devlin表示深深的谢意,她所完成的工作已远远超出了既定的职责。她不仅能力出众,而且责任心强,努力解决了新版本开发过程中出现的各种问题。
还要感谢Peggy Selle,作为内容产品经理,她管理着本书的生产过程。她全程跟踪本书的流程,并帮助解决生产过程中出现的许多问题。感谢Aptara的高级产品经理Sarita Yadav和她的同事,他们的努力工作确保了本书的生产质量。
我还要对麦格劳希尔高等教育的科学、工程和数学(SEM)部门的同仁表示感谢,他们对新版本以及相关的媒体内容给予了大力支持,包括:
●Mike Ryan,高等教育副总裁,负责作品统筹和学习内容管理
●Kathleen McMahon,数学与物理科学部门常务主管
●Caroline Celano,数学部门主管
●Alison Frederick,市场经理
●Robin Reed,首席产品开发师
●Sandy Ludovissey,采购人
●Egzon Shaqiri,设计师
●Tammy Juran,评估内容项目经理
●Cynthia Northrup,数字内容部门主管
●Ruth CzarneckiLichstein,业务产品经理
●Megan Platt,编辑协调人
●Lora Neyens和Jolynn Kilburg,项目经理
●Lorraine Buczek,内容授权专家
Kenneth H. Rosen
计算机\离散数学
本书是介绍离散数学理论和方法的经典教材,被全球数百所高校采用,获得了极大的成功。第8版做了与时俱进的修改,同时更新了配套教辅资源,成为更加实用的教学工具。本科教学版缩减了篇幅,适用于数学、计算机科学、计算机工程、信息技术等专业的学生。
本书特色
·章节:保留了逻辑和证明、基本结构、计数和高级计数、关系、图、数和布尔代数等内容,删除了算法、数论和密码学、归纳与递归、离散概率、计算模型等内容。
·例题:共400多道例题,用于阐明概念、建立不同主题之间的关联以及介绍实际应用。
·应用:涉及的领域包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网等,展示了离散数学的实用性。
·算法:每一章都介绍了一些关键算法,提供伪代码,并简要分析其计算复杂度。
·练习、复习题和补充练习:共有2000多道难度各异的练习题,可以满足不同层次学生的需求。此外,还有一些研究性题目,帮助学生通过计算来探索新知识和新想法。
[美]肯尼思·H. 罗森(Kenneth H. Rosen) 著:肯尼思·H. 罗森(Kenneth H. Rosen) 于1972年获密歇根大学安娜堡分校数学学士学位,1976年获麻省理工学院数学博士学位。Rosen曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学和蒙茅斯大学,教授离散数学、算法设计和计算机安全方面的课程;他还曾加盟贝尔实验室,并且是AT&T贝尔实验室的杰出技术人员。他的著作《初等数论及其应用》和《离散数学及其应用》均被翻译成多种语言,在全球数百所大学中广为采用。
徐六通 杨娟 吴斌 译 陈琼 改编:暂无简介
从在路边小摊贩处扫码完成支付到为黑洞拍摄第一张照片,再到各类世纪工程的竣工,这一切进步与奇迹的背后都离不开计算机科学与技术的飞速发展。
如果你也想为将来的奇迹做出自己的贡献,就必须先了解计算是什么、计算机的工作原理是什么、计算机是如何解题的等问题。你需要学习的第一门基础课就是离散数学。什么是离散数学?离散数学是致力于研究离散对象的数学分支。说得更通俗一点,就是利用计算机进行问题求解时,一切问题背后的原理性东西均属于离散数学的范畴,或者说离散数学就是计算机科学的数学语言。
离散数学一直被IEEECS和ACM认定为计算机专业最核心的课程,也是我国计算机科学与技术专业的核心基础课程。当你学习这门课程的时候,会发现离散数学为许多计算机专业课程提供了理论基础,尤其是为课程中大量的算法提供了基础。
本书英文版自出版以来在北美发行超过450000册,目前已经被翻译成西班牙文、法文、葡萄牙文、希腊文、中文、越南文和韩文等,在世界各地发行数十万册。
第8版对许多内容进行了完善、更新、补充和润色,所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。本书清晰地介绍并展示了离散数学中的概念和技术,行文流畅,通俗易懂。书中包含大量有趣而实用的例子,吸引读者广泛好奇心的推荐读物,以及帮助读者掌握离散数学的概念和技巧的丰富练习题,为计算机科学学生将来的学习提供了一切必需的数学基础。此外,本书还提供了一个非常有价值的网站资源——在线学习中心(OLC),帮助学生评估自身学习状况,学习撰写证明并避免常见错误,从各个方面提高学生学习和实际解决问题的能力,引领学生探索离散数学的新应用。
在本次翻译工作中,徐六通翻译全书(完整版)前言、第1章至第4章、附录及推荐读物,吴斌翻译第5章至第8章,杨娟翻译第9章至第13章。由于译者水平所限,尽管已经修正了之前版本中的一些错误,但是难免还会有不妥的地方,敬请读者不吝赐教。
译者
2019年8月于北京
出版者的话
改编者序
译者序
前言
在线资源
致学生
作者简介
符号表
第1章基础:逻辑和证明1
11命题逻辑1
111引言1
112命题1
113条件语句4
114复合命题的真值表6
115逻辑运算符的优先级7
116逻辑运算和比特运算7
奇数编号练习8
12命题逻辑的应用11
121引言11
122语句翻译11
123系统规范说明12
124布尔搜索12
125逻辑谜题13
126逻辑电路14
奇数编号练习15
13命题等价式17
131引言17
132逻辑等价式17
133德·摩根律的运用20
134构造新的逻辑等价式20
135可满足性21
136可满足性的应用21
137可满足性问题求解24
奇数编号练习24
14谓词和量词26
141引言26
142谓词26
143量词27
144有限域上的量词30
145受限域的量词30
146量词的优先级31
147变量绑定31
148涉及量词的逻辑等价式31
149量化表达式的否定32
1410语句到逻辑表达式的翻译33
1411系统规范说明中量词的使用34
1412选自路易斯·卡罗尔的例子35
1413逻辑程序设计35
奇数编号练习36
15嵌套量词39
151引言39
152理解涉及嵌套量词的语句39
153量词的顺序40
154数学语句到嵌套量词语句的翻译41
155嵌套量词到自然语言的翻译42
156汉语语句到逻辑表达式的翻译43
157嵌套量词的否定43
奇数编号练习44
16推理规则47
161引言47
162命题逻辑的有效论证47
163命题逻辑的推理规则48
164使用推理规则建立论证50
165消解律51
166谬误51
167量化命题的推理规则52
168命题和量化命题推理规则的组合使用53
奇数编号练习54
17证明导论56
171引言56
172一些专用术语56
173理解定理是如何陈述的56
174证明定理的方法56
175直接证明法57
176反证法58
177归谬证明法60
178证明中的错误62
179良好的开端63
奇数编号练习63
18证明的方法和策略64
181引言64
182穷举证明法和分情形证明法64
183存在性证明67
184唯一性证明69
185证明策略69
186寻找反例71
187证明策略实践71
188拼接72
189开放问题的作用74
1810其他证明方法74
奇数编号练习75
章末资料(在线)
标注“在线”的章节,请访问华章网站(wwwhzbookcom)下载。——编辑注
第2章基本结构:集合、函数、序列、求和与矩阵77
21集合77
211引言77
212文氏图79
213子集79
214集合的大小80
215幂集81
216笛卡儿积81
217使用带量词的集合符号83
218真值集和量词83
奇数编号练习83
22集合运算84
221引言84
222集合恒等式87
223扩展的并集和交集89
224集合的计算机表示90
225多重集91
奇数编号练习92
23函数94
231引言94
232一对一函数和映上函数96
233反函数和函数合成98
234函数的图101
235一些重要的函数101
236部分函数103
奇数编号练习104
24序列与求和106
241引言106
242序列106
243递推关系107
244特殊的整数序列109
245求和111
奇数编号练习114
25集合的基数116
251引言116
252可数集合117
253不可数集合119
奇数编号练习121
26矩阵122
261引言122
262矩阵算术123
263矩阵的转置和幂124
26401矩阵125
奇数编号练习126
章末资料(在线)
第3章计数128
31计数的基础128
311引言128
312基本的计数原则128
313比较复杂的计数问题132
314减法法则(两个集合的容斥原理)133
315除法法则135
316树图135
奇数编号练习136
32鸽巢原理138
321引言138
322广义鸽巢原理139
323鸽巢原理的几个简单应用141
奇数编号练习142
33排列与组合143
331引言143
332排列143
333组合145
奇数编号练习147
34二项式系数和恒等式149
341二项式定理149
342帕斯卡恒等式和三角形151
343其他的二项式系数恒等式152
奇数编号练习153
35排列与组合的推广155
351引言155
352有重复的排列155
353有重复的组合155
354具有不可区别物体的集合的排列158
355把物体放入盒子159
奇数编号练习161
36生成排列和组合163
361引言163
362生成排列163
363生成组合165
奇数编号练习166
章末资料(在线)
第4章高级计数技术167
41递推关系的应用167
411引言167
412用递推关系构造模型168
413算法与递推关系172
奇数编号练习174
42求解线性递推关系176
421引言176
422求解常系数线性齐次递推关系176
423求解常系数线性非齐次递推关系180
奇数编号练习182
43分治算法和递推关系184
431引言184
432分治递推关系184
奇数编号练习189
44生成函数191
441引言191
442关于幂级数的有用事实191
443计数问题与生成函数194
444使用生成函数求解递推关系197
445使用生成函数证明恒等式198
奇数编号练习199
45容斥201
451引言201
452容斥原理202
奇数编号练习205
46容斥原理的应用205
461引言205
462容斥原理的另一种形式206
463埃拉托斯特尼筛法206
464映上函数的个数207
465错位排列208
奇数编号练习209
章末资料(在线)
第5章关系211
51关系及其性质211
511引言211
512函数作为关系212
513集合的关系212
514关系的性质213
515关系的组合215
奇数编号练习217
52n元关系及其应用219
521引言219
522n元关系220
523数据库和关系220
524n元关系的运算221
525SQL223
526数据挖掘中的关联规则224
奇数编号练习226
53关系的表示227
531引言227
532用矩阵表示关系227
533用图表示关系229
奇数编号练习231
54关系的闭包232
541引言232
542不同类型的闭包232
543有向图中的路径233
544传递闭包234
545沃舍尔算法236
奇数编号练习239
55等价关系239
551引言239
552等价关系240
553等价类241
554等价类与划分243
奇数编号练习245
56偏序247
561引言247
562字典顺序249
563哈塞图250
564极大元与极小元251
565格253
566拓扑排序254
奇数编号练习256
章末资料(在线)
第6章图259
61图和图模型259
611图模型261
奇数编号练习266
62图的术语和几种特殊的图268
621引言268
622基本术语268
623一些特殊的简单图270
624二分图271
625二分图和匹配273
626特殊类型图的一些应用276
627从旧图构造新图277
奇数编号练习279
63图的表示和图的同构281
631引言281
632图的表示281
633邻接矩阵282
634关联矩阵283
635图的同构284
636判定两个简单图是否同构284
奇数编号练习287
64连通性290
641引言290
642通路290
643无向图的连通性292
644图是如何连通的293
645有向图的连通性295
646通路与同构296
647计算顶点之间的通路数297
奇数编号练习298
65欧拉通路与哈密顿通路300
651引言300
652欧拉通路与欧拉回路300
653哈密顿通路与哈密顿回路304
654哈密顿回路的应用306
奇数编号练习307
66最短通路问题309
661引言309
662最短通路算法311
663旅行商问题315
奇数编号练习316
67平面图318
671引言318
672欧拉公式319
673库拉图斯基定理321
奇数编号练习323
68图着色324
681引言324
682图着色的应用327
奇数编号练习328
章末资料(在线)
第7章树331
71树的概述331
711有根树332
712树作为模型335
713树的性质336
奇数编号练习338
72树的应用340
721引言340
722二叉搜索树340
723决策树342
724前缀码344
725博弈树346
奇数编号练习349
73树的遍历351
731引言351
732通用地址系统352
733遍历算法352
734中缀、前缀和后缀记法358
奇数编号练习360
74生成树362
741引言362
742深度优先搜索363
743宽度优先搜索365
744回溯的应用367
745有向图中的深度优先搜索369
奇数编号练习370
75最小生成树371
751引言371
752最小生成树算法372
奇数编号练习375
章末资料(在线)
第8章布尔代数377
81布尔函数377
811引言377
812布尔表达式和布尔函数378
813布尔代数恒等式379
814对偶性380
815布尔代数的抽象定义381
奇数编号练习382
82布尔函数的表示382
821积之和展开式383
822函数完备性384
奇数编号练习384
83逻辑门电路385
831引言385
832门的组合385
833电路的例子386
834加法器388
奇数编号练习389
84电路的极小化390
841引言390
842卡诺图391
843无须在意的条件396
844奎因莫可拉斯基方法396
奇数编号练习399
章末资料(在线)
推荐读物(在线)
参考文献(在线)
奇数编号练习答案(在线)
请访问华章网站www.hzbook.com下载。