本书是根据我多年讲授离散数学的经验和兴趣写成的。对学生而言,我的目的是为他们提供准确而可读的教材,清晰地介绍离散数学的概念和技术。我的目标是向爱怀疑的学生们展示离散数学的实用性,希望为学习计算机科学的学生提供一切必需的数学基础,也希望学数学的学生理解数学概念的重要性,以及这些概念为什么对应用是重要的,还希望本书既能达到这些目标,又不含太多的水分。
对教师(指导者)而言,我的目的是使用成熟的数学教学技术设计一个灵活而全面的教学工具,希望为教师们提供能够以最适合特定学生特点的方式高效地讲授离散数学的教材。希望本书能够达到这些目标。
我为本教材在过去已经取得的巨大成功而分外高兴。根据成功使用本书的600多所学校的大批师生的反馈和建议,此次第6版进行了许多改进。很多内容有所提高,辅助材料更加丰富,配套网站提供的材料更有帮助性,使师生更容易达到他们的目标。
本教材是为1至2个学期的离散数学入门课程而设计的,适用于数学、计算机科学、工程等许多专业的学生。虽然唯一的先修课要求是大学代数,但是要想学习好离散数学还需要掌握更多的数学知识。
离散数学课的目标
离散数学课有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用,更重要的是,这样一门课应教会学生怎样进行数学逻辑思维。为此,本教材特别强调数学推理及用不同的方法解题。本教材有5个重要的主题交织在一起:数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程应该努力使这五部分内容相互融合、平衡。
1数学推理: 学生必须理解数学推理,以便阅读、理解和构造数学证明。本教材以数理逻辑开篇,在后面证明方法的讨论中,数理逻辑是基础。同时,本书描述了构造性证明的方法和技巧。本书还十分强调数学归纳法,不仅用许多证明的实例进行介绍,还详细地解释了数学归纳法为什么是有效的证明方法。
2组合分析:解题的一项重要技巧是计数或枚举对象。本书中,对枚举的讨论从基本的计数方法着手,重点是用组合分析方法来解决计数问题,而不直接使用公式。
3离散结构:离散数学课应该教会学生如何使用离散结构,即学会如何使用表示离散对象及其之间的关系的抽象数学结构。离散结构包括:集合、置换、关系、图、树和有限状态机等。
4算法思维:有些问题是通过详细说明其算法来求解的。算法在描述后就可构造计算机程序来实现。这一过程中用到的数学部分包括:算法描述、正确性证明以及执行算法所需要的计算机内存和时间的分析。这些内容在本书中均有介绍。算法是用英语和一种易于理解的伪码描述的。
5应用与建模:离散数学几乎应用在所有研究领域中。本书既介绍了其在计算机科学和数据网络中的许多应用,也介绍了在其他各种领域中的应用,如化学、植物学、动物学、语言学、地理、商业以及互联网等。这些均是离散数学的实际而重要的应用,而不是编造的。用离散数学来建模是十分重要的问题求解技巧。本书中的一些练习让学生有机会通过自己构造模型来掌握这一技巧。
本书特点
易入门实践证明:此课本对初学者来说易读易懂。它的大部分内容只要求学生学过大学代数,不需要其他的预备知识,少数几个涉及微积分的地方也有明确说明。大部分学生应该很容易理解课本中用于表示算法的伪码,不管他们是否学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易理解的水平开始。本书在仔细研究基本的数学概念之后,就介绍了其他领域中更难的部分和应用。
灵活性课本为灵活使用作了精心设计。各章对其前面内容的依赖都降到最低程度。每一章分成长度大致相等的若干节,每一节又根据内容划分成小节以方便教学。教师可以根据这些分块灵活地安排进度。
写作风格本书的写作风格是直接和实用。使用准确的数学语言,但没有过分的形式化与过分的抽象。在记号和数学命题的词汇间作了精心的平衡。
数学严谨性和准确性本书中所有定义和定理的陈述都十分详细,所以学生可以欣赏其语言的准确以及数学所需的严谨。但证明则是缓慢引入并展开的,每一步都经过了详细论证。本书解释并大量使用了递归定义。
实例本书使用了很多例子来阐述概念、建立不同内容之间的关系或导入应用。在大部分例子中,先提出问题,再适当给出它的解。
应用书中叙述的应用展示了离散数学在解决现实问题中的使用价值,所涉及的范围很广,包括计算机科学、数据网络、心理学、化学、工程、语言学、生物学、商业和互联网。
算法离散数学的结论常常要用算法来表示,因此,本书每一章都介绍了一些关键算法。书中还简要分析了所有算法的计算复杂性。
. 关键术语和结果每一章后面都列出了本章的关键术语和结果,但只列出了学生必须学会的那些最重要的关键术语,而不是在该章中定义的所有术语。
练习书中包含许多练习,代表了大量不同类型的问题。本书不仅提供了足够多的简单问题用于练习基本技巧,还提供了大量的中等难度的练习和许多有挑战性的练习。练习的叙述清晰而无歧义,并按难易程度进行了分级。有些特殊的论题还设计成系列练习。这些练习不仅给出了正文中没有介绍的新概念,还使学生可以通过自己的努力发现新思想。
比平均水平稍难的练习用单个星号作标记,相当有挑战性的问题则用两个星号来标记。必须用微积分来解的练习也作了明确说明。导出正文要用到的结果的练习则用符号“”识别。
复习题每章最后都有一组复习题。设计这些问题的目的是帮助学生重点学习该章最重要的概念和技术。要回答这些复习题,学生必须写出较长的答案,而只做点计算或简答是不够的。
计算机题目每一章后面还有一组计算机题目。这些题目把学生可能已经学到的有关计算和离散数学的内容联系起来。如果从数学角度或程序设计角度来看,其难度超过平均水平的计算机题目用一个星号标记,特别有挑战性的则用两个星号标记。
计算和研究每一章的结论部分都有一组计算和研究性问题。要完成这些练习(大约有100道)需要软件工具的帮助,例如学生或教师自己编写的程序,或数学计算软件包(如Maple或Mathematica)。大部分这样的练习为学生提供了通过计算发现新事实或新思想的机会。
写作题目每一章后面都有一组应该书面完成的题目。要完成这类题目,学生需要参考数学文献。有些题目在过去的历史上是很重要的,学生需要查找原始资料,其他的题目则是通往新内容和新思想的途径。所有此类练习均向学生展示正文中没有深入探讨的思想。这些题目把数学概念和书面写作的过程结合在一起,以帮助学生探索未来的研究领域。
推荐读物在正文的最后,专门有一节用来为各章推荐参考读物,其中有不超过本书水平的书籍,也有较难的书籍;有综述性文章,也有发表离散数学新发现的原始文章。其中一些是许多年前出版的经典读物,而其他一些是在最近几年内出版的。
配套网站
为本书开发了一个内容广泛的配套网站,该网站将不断地维护和改进。可以以多种方式使用该网站进一步学习离散数学,网站地址是:wwwmhhecom/rosen。由此地址进入该网站的主页。该网页有下列链接:
信息中心
学生中心
教师中心
信息中心:该中心包含本书及其辅助资料的基本信息。教师在这个网页中可以利用网页抽取系统“Page Out”,建立自己的课程网页,还能学习定制出版信息。从该信息中心出发,沿着适当的链接,可以看到本书网站的一个概观。
学生中心:该中心包含了可供学生使用的丰富资源,包括下列与课本紧密相关的资源(在课本中用相应的图标加以标记):
网络资源指南:该指南提供了数百个含相关资料的外部网站的链接。可以通过关键词浏览或访问这些链接,它们将把你带到包含下列信息的网站:历史及传记信息、谜题及问题、讨论、Java小程序、程序以及其他类型的资源。
额外的例子:这个网站包含了大量额外的例子。这些例子主要集中在学生经常需要的课外资料的领域。虽然大部分例子只是扩充了基本概念,但还有一部分十分具有挑战性。
额外的步骤:对一些困难的知识点,提供了更深入的解释帮助理解,尤其是一些特殊的证明和例子。
评估:提供对七个关键概念理解程度的评估。每个评估都提供了一个题库,其中的每个试题由两部分构成:先是一段简短的复习,然后是一个多选题。如果你选择的答案不正确,该系统还能提供建议,帮助你理解错在什么地方。这样的评估系统应该能诊断出你学习中的问题,从而把精力集中在寻找纠正办法上。
交互式演示:已经开发了八个交互式演示系统,你可以用它们考查一些重要算法是怎么工作的。这些演示都与课本中的相应材料相对应。
从该学生中心你可以访问网络教学系统“Net Tutor”。它提供了在线教学帮助。当你提问与课本内容相关的问题时,如果是在规定教学时间内,你会收到实时回答;否则稍后才会收到回答。
学生中心还支持能发布消息的公告板系统。使用该系统,你可以提出问题,还可以回答其他学生提出的问题。
除此之外,学生中心还包括下列资源:
证明书写指南
离散数学的常见错误
写作题目的建议
Maple软件
教师中心:除了包含学生中心和信息中心提供的所有链接外,网站中的教师中心还包含下列链接:
教学大纲样本
教学建议
《Applications of Discrete Mathematics》一书中的某些章节
写给学生
什么是离散数学?离散数学是数学中研究离散对象的部分。(这里“离散”的含义是“由不同的或不相连的元素组成”。)离散数学能解决的问题包括:
在计算机系统中,有多少种方式可以选择一个合法口令?
赢彩票的概率是多少?
两台计算机之间在网络上是否有通路?
怎样鉴别Email信息中的垃圾邮件?
怎样加密信息以避免不该收到的人读取该信息?
在某一交通系统下,两个城市之间的最短路径是什么?
怎样把整数序列按递增序排列?
完成上述排序需要多少步骤?
如何证明一个排序方法能正确地排序?
怎样设计两个整数相加的电路?
有多少合法的因特网网址?
你们将学习解决诸如以上问题要用到的离散结构和技术。
更一般地,在对对象进行计数时要用到离散数学,研究两个有限(或可数)集合之间的关系时要用到离散数学,分析只含有限步的进程时也要用到离散数学。离散数学的重要性还在不断增加,一个关键原因就是计算机以离散的方式存储和处理信息。
为什么要学离散数学?有几条重要的理由来说明需要学习离散数学。首先,通过这个课程你们可以发展自己的数学素质,即理解和创造数学证明的能力。没有这些技巧,你们在学习数学时不可能太深入。
其次,离散数学是学习所有更高级数学课程的必经之路。离散数学为学习计算机科学课程提供必要的数学基础,这些课程包括:数据结构、算法、数据库理论、自动机理论、形式语言、编译理论、计算机安全以及操作系统。学生如果没有适当的离散数学基础,在学习上述课程时会感到很困难。有个学生给我发电子邮件说,在她学习的每一门计算机科学的课中都用到了本书的知识。
以离散数学为基础的数学课程包括逻辑、集合论、数论、线性代数、抽象代数、组合论、图论及概率论(其离散部分)。
此外,离散数学还包括了解运筹学(包括许多离散优化技术)、化学、工程及生物学等领域问题的必要的数学背景。从本书中你将学到在上述某些领域中的应用。
许多学生都感到,与他们以前学过的课程相比,离散数学入门课程的挑战性要大得多。这是因为,本课程的一个主要目的是教你进行数学推理和问题求解,而不只是一些分散的技巧。从课本中练习的设计可以看出这个目的。课本中虽然有大量与重点例子类似的练习,但还是有相当比例的练习需要创造性思维。这是有意设计的。虽然课本中的材料提供了解这些问题的工具,但你的任务是创造性地使用这些工具并取得成功。本课程的另一个主要目的是学会处理你以前没有见过的问题。然而,只学会解特殊类型的练习还无法保证能学会足够多的解题技巧,也不能保证在后继课程的学习中或在将来的职业生涯中取得成功。虽然课本讨论了许多主题,但离散数学是一个极为广泛且充满变化的研究领域。作为作者,我的任务之一是帮助你开发学习新知识的能力,在将来的奋斗中你十分需要新的知识。
练习我愿意就如何学好离散数学(或数学的其他学科和计算机科学)给同学们提点有益的建议。积极地做练习能使你最大地获益。我建议你尽可能地多做练习。在做完老师布置的练习后,我鼓励你做更多的练习,包括本书每节后面的练习和每章后面的补充练习。(注意练习前面的分级标记。)
练习标记含义
无标记常规练习
*较难的练习
**富有挑战性的练习
正文中要用到该练习的某个结论
(需要用到微积分)解题时要用到极限或微积分的概念 解题时,最好在查阅答案以前,自己先进行尝试。华章网站(www.hzbook.com)提供了练习的答案。注意,只是答案,而不是完整解答。特别地,答案中省略了解的推导过程。
网络资源我强烈推荐你利用网络提供的新资源,特别是专为本书设计的网站http://www.mhhe.com/rosen中的资源。其中为澄清关键的概念设计了许多额外的例子,自我评测是考查你对关键问题的掌握程度;交互演示小程序帮你探索关键算法和其他概念;网络资源向导包含了广泛的与离散数学有关的外部链接;额外的解释和实践会帮助你掌握关键的概念,增加的书写证明可以避免离散数学中的一般错误;重要应用的深入探索指导应用Maple软件探索离散数学中的计算问题。在文中这些额外的在线资源尽可能在边缘处用特定图标标识。
本书的价值我希望你对本书的投资能得到优质的回报。我们花了多年的努力来开发和优化本书及其配套的辅助读物和网站。对大多数人来说,我很自信本书及其配套资料对掌握离散数学大有帮助。即使你现在的课程可能略去了其中某些章节,但当你学习新课程时会发现,阅读本书中的相关章节对新课程仍然十分有益,许多学生都有这样的感觉。许多人会在将来的研究工作时又找到本书,把它当做一本有用的工具书,特别是那些继续学习计算机科学、数学或工程的人。我设计本书作为你将来研究和探索的入门,我希望你能幸运地开始你的征程。
致谢
我要感谢很多学校中使用本书的大批师生们,他们向我提出了宝贵的反馈和有益的建议。没有他们的反馈和建议,本书不可能有很大的改进。我要特别感谢Jerrold Grossman、John Michaels和Geoge Bergman,感谢他们对第6版的技术审阅,他们敏锐的目光确保了本书的准确性。我也要感谢通过网站提交评论的人们提供的帮助。
我感谢本书第6版及前面5版的许多评阅人,他们对我提出了许多有益的批评和鼓励,我希望本版不辜负他们的期望。
我还要感谢McGrawHill出版社高等教育组的工作人员对本课题强有力的支持。特别要感谢出版人Liz Haefele的支持,感谢Liz Covello 和Senior Sponsoring编辑的提倡和热情,感谢开发编辑Dan Seibert的献身和关注,还要感谢原编辑Wayne Yuhasz,是他的洞察力和技巧保证了本书的成功,以及本书前几版的其他编辑。
我还要对制作本书第6版做出过贡献的职员表示感谢,他们有:项目总经理Peggy Selle、高级设计师Michelle Whitaker、媒体制作负责人Jeff Huettman、高级媒体项目经理Sandy Schnee、补充读物协调人Melissa Leick以及出色的市场经理Kelly Brown。我还很感谢Jerry Grossman,他检查了全部初稿以保证准确性,感谢校对员Rose Kramer 和 Gayle Casel。
Kenneth HRosen