离散数学及其应用（原书第7版）&&&&
作者：（美）Kenneth H.Rosen 著　蒙茅斯大学
ISBN：978-7-111-45382-6
定价：129.00
出版日期：日
译者：徐六通 杨娟 吴斌 译
图书分类： &
原出版社：McGraw-Hill
浏览量：2934
语种：简体中文
原书名：Discrete Mathematics and Its Applications,Seventh Edition
属性分类：教材
所属丛书：
责任编辑：
适用专业：
包含CD：无
本书是介绍离散数学理论和方法的经典教材，在全世界有500多所高校正在使用；目前，国内高校离散数学双语课程的首选教材，但全版内容偏多，本科课程难以全面覆盖，所以根据国内课程体系进行了裁剪。
本书是介绍离散数学理论和方法的经典教材，已经成为采用率最高的离散数学教材，被美国众多名校用做教材，获得了极大的成功。本书中文版也已被国内大学广泛采用为教材。作者参考教师和学生的反馈，并结合自身对教育的洞察，在第7版中做了大量的改进，使其成为更有效的教学工具。 本书可作为1～2个学期的离散数学课程教材，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。本书特点实例：书中有800多个实例，用于阐明概念，联系不同内容，引入各种应用。应用：书中叙述的应用展示了离散数学在解决现实中问题时的使用价值，涉及的应用领域包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网等。算法：离散数学的结论常常要用算法来表示，因此本书每一章都介绍了一些关键算法。历史资料：本书对许多主题的背景做了简要介绍，并以脚注的形式给出了83位对离散数学做出过重要贡献的数学家和计算机科学家的简短传记。关键术语和结论：每一章后面都列出了本章的关键术语和结论。练习、复习题和补充练习：书中有4000多道难度各异的练习，可以满足不同层次学生的学习需求。同时，每章最后都有一组复习题和丰富多样的补充练习。计算机课题：每一章后面还有一组计算机课题，大约有150个这样的题目，把学生已经学到的计算和离散数学的内容结合在一起。计算和探索：每一章的结论部分都有一组计算和探索性问题，为学生提供了通过计算发现新事实或新思想的机会。写作课题：每一章后面都有一组应该书面完成的课题。要完成这类课题，学生需要查阅参考文献，把数学概念和书面写作的过程结合在一起，以帮助学生研究和思考正文中没有深入探讨的思想，便于其未来的学习和研究。前：Kenneth H. Rosen　1972年获密歇根大学数学学士学位，1976年获麻省理工学院数学博士学位，其博士论文研究的是数论，导师是Harold Stark 。Rosen曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学，后加盟贝尔实验室，现为AT&T实验室杰出研究员。他目前还是蒙茅斯大学客座研究教授，教授“离散数学”、“编码理论”和“数据安全”课程。此外，他还是CRC出版社离散数学丛书的编辑顾问。Rosen博士在专业期刊上发表过许多关于数论和数学建模的文章。《初等数论及其应用》和《离散数学及其应用》这两本书均被国际上几百所大学广为采用。
本书是根据我多年讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供准确且可读性很强的教材，清晰地介绍并展示离散数学中的概念和技术。我的目标是向爱怀疑的学生们展示离散数学的相关性和实用性，希望为学习计算机科学的学生提供一切必需的数学基础，也希望学数学的学生理解重要的数学概念，以及为什么这些概念对应用来说很重要，最重要的是希望本书既能达到这些目标，又不含太多的水分。 对教师而言，我的目的是要利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具，希望为教师提供能够以最适合特定学生特点的方式高效地教授离散数学的教材。希望本书能够达到这些目标。 我为本教材在过去所取得的巨大成功而感到非常欣慰。根据北美600多所学校以及全球各地许多大学成功采用了本书的大批师生的反馈和建议，此次第7版进行了许多改进。 本教材是为一至两个学期的离散数学入门课程而设计的，适用于数学、计算机科学和工程等各类专业的学生。虽然唯一的先修课程要求是大学代数，但是要想真正学好离散数学还需要掌握更多的数学知识。离散数学课程的目标 离散数学课程有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用，更重要的是，这样一门课应培养学生的数学逻辑思维。为此，本教材特别强调数学推理以及用不同的方法解题。本书中五个重要主题交织在一起：数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程应该努力使这五个主题相互融合、平衡。1.数学推理：学生必须理解数学推理，以便阅读、领会并构造数学论证。本书以数理逻辑开篇，在后面证明方法的讨论中，数理逻辑是基础。本书描述了构造证明的方法与技巧。本书特别强调数学归纳法，不仅给出了这种证明的许多不同类型的实例，还详细地解释了数学归纳法为什么是有效的证明技术。2.组合分析：一个重要的解题技巧就是计数或枚举对象。本书中，对枚举的讨论从计数的基本技术着手，重点是用组合分析方法来解决计数问题并分析算法，而不是简单地应用公式。3.离散结构：离散数学课程应该教会学生如何处理离散结构，即表示离散对象以及对象之间关系的抽象数学结构。离散结构包括集合、置换、关系、图、树和有限状态机等。4.算法思维：有些问题可以通过详细说明其算法来求解。在清楚地描述算法后，就可以构造一个计算机程序来实现它。这一过程中涉及的数学部分包括算法的详细说明、正确性验证以及执行算法所需要的计算机内存和时间的分析等，这些内容在本书中均有介绍。算法是用英语?　译著中采用汉语。——译者注?和一种易于理解的伪代码来描述的。5.应用与建模：离散数学几乎在每个可以想象到的研究领域中都有应用，本书介绍了其在计算机科学和数据网络中的许多应用，还介绍了在其他各种领域中的应用，如化学、植物学、动物学、语言学、地理学、商业以及因特网等。这些均是离散数学的实际而又重要的应用，而不是编造的。用离散数学来建模是十分重要的问题求解技巧，本书中的一些练习让学生有机会通过自己构造模型掌握这一技巧。第7版中的变更虽然第6版已经是一本非常有效的教材，但许多教师（包括长期使用者）还是提出了使本书更有效的修改要求。我花了大量的时间和精力来满足这些要求，想方设法使这本书做得更好。第7版是一个重大的修订版，其变更基于40多位正式评阅人、学生和教师的反馈以及作者的见解。新版本改善了主题的组织结构，使本书成为一个更加有效的教学工具。逻辑、算法、数论和图论方面的内容有许多实质性的增强，使本书更加灵活和全面。第7版中所做的大量变更能帮助学生更容易地掌握这些内容。增加了额外的解释和例子以便阐述那些学生经常感到有困难的内容。新增了一些常规的和富有挑战性的习题。还增加了一些与因特网、计算机科学以及数学生物学等密切相关的应用。配套网站得易于广泛的开发活动，现在所提供的工具使学生可以用来掌握关键概念并探索离散数学世界，正在开发中的许多新工具也将在本书出版后的来年发布。我希望教师仔细阅读这本新版以发现如何来满足他们的需求。尽管要列出本版所有变更是不切实际的，但基于一些关键变更及其所带来的好处给出一个简要的列表或许是有益的。更灵活的组织结构?命题逻辑的应用分出专门的小节，其中简要介绍了逻辑电路。?递推关系在第2章论述。?扩展了可数性讨论并在第2章中有专门的一节。?用独立的章节论述算法（第3章）以及数论和密码学（第4章），并增加了内容。?采用了更多二级、三级标题以便将章节划分成较小的有紧密联系的部分。便于学习的工具?有些难度的讨论和证明已经在页边用布尔巴基著名的“危险弯道”符号警示。?新的页边注解给出一些链接，增加一些有趣的注解，并为学生提供一些忠告。?在证明以及阐述中引入更多的细节和解释，以帮助学生更容易地阅读本书。?在对许多原有练习做了一些改进的同时，增加了更多新的练习，包括常规练习以及富有挑战性的练习。增强了逻辑、集合和证明所涵盖的内容?可满足性问题有了更深入的阐述，并论述了以可满足性建模的数独（Sudoku）问题。?利用希尔伯特大饭店来解释不可数性。?贯穿全书的证明通过细化步骤及其背后的原因使之更加易于理解。?增加了一个数学归纳法的证明模板。?在数学归纳法证明中显式地注明了应用归纳假设的步骤。算法?本书中使用的伪代码已经做了更新。?算法范型做了显式的扩充，提供了包括蛮力算法、贪婪算法以及动态规划等内容。?增加了对数、幂以及指数函数大O估计的判别规则。数论和密码学?扩展了所涵盖的内容使得教师在课程中可以只选择一小部分或更多的数论内容。?mod函数和同余之间的关系做了更全面的解释。?对埃拉托斯特尼（Eratosthenes）筛法的介绍在本书中有所提前。?线性同余式以及模的逆有了更深入的阐述。?深入讨论了数论应用，包括校验码和散列函数。?新一节的密码学集成了原先的内容，并引入了密码系统的概念。?涵盖了密码协议内容，包括数字签名和密钥共享。图论?增加了结构归纳法在图论中的应用。?更多地关注社交网络的概念。?增加了在生物科学中的应用，还有图同构和平面性方面很有意思的应用。?增加了二分图的匹配问题，包括Hall定理及其证明。?增加了顶点连通性、边连通性以及n连通性，使读者对图的连通性有更深入的理解。充实的内容?对许多传记做了扩充和更新，同时新增了贝尔曼、贝祖·比安内梅、卡尔达诺、卡塔兰、柯克斯、库克、狄拉克、霍尔、希尔伯特、欧尔和陶哲轩的传记。?全书历史资料也有所增加。?大量最新发现也做了相应更新。扩展的媒体?努力为本书开发有价值的网站资源。?在配套网站上为本书主要内容提供了额外的练习。?开发了一些交互式算法，以及一些探索主题并可用于课堂教学的工具。?2012年秋季新上线一个辅助工具——虚拟离散数学导师，可以帮助学生解决学习离散数学中的困难。?2012年秋季新上线的作业提交系统，可用来提供自动化的作业，包括数值型和概念型的练习。?针对关键概念的学生评估模块。?开发了供教师使用的PowerPoint幻灯片。?开发了补充的《探索离散数学》，为配合本书利用MapleTM或MathematicaTM提供广泛的支持。?提供了一组广泛的外部Web链接。本书特色易理解性：本书对于初学者来说已被实践证明是易读易懂的。绝大部分内容不需要读者具备比大学代数更多的数学预备知识。需要额外帮助的学生可以在配套网站找到相应工具将数学水平提升到本书的水准。本书中少数几个需要参考微积分的地方也已显式注明。大多数学生应该很容易理解书中用来表示算法的伪代码，无论他们是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。每章都是从易于理解和领会的水平开始。一旦详细介绍了基本数学概念，就会给出稍难一些的内容以及在其他研究领域中的应用。灵活性：本书为能灵活使用做了精心设计。各章对其前面内容的依赖程度都降到最低。每章分成长度大致相等的若干节，每节又根据内容划分成若干小节以方便教学。教师可以根据这些分块灵活地安排讲课进度。写作风格：本书的写作风格是直接而又实用的。使用准确的数学语言，但没有采用过多的形式化与抽象。在数学命题中的记号和词语表达之间做了精心的平衡。数学严谨性和准确性：本书中所有定义和定理的陈述都十分仔细，这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则先是动机再缓慢展开，每一步都经过了详细论证。证明中用到的公理及其所导出的基本性质在附录中均有显式描述，这呈现给学生一个清晰的概念，即在一个证明中他们能够作何种假设。本书解释并大量使用了递归定义。 实例：超过800多个例子用来阐述概念、建立不同主题之间的关联，并介绍应用。在大部分例子中，首先提出问题，然后再以适量的细节给出其解。 应用：本书中所含的应用展示了离散数学在解决现实世界中的问题时的实用性。本书包含的应用涉及广泛的领域，包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网。算法：离散数学的结论常常要用算法来表述，因此本书每章都介绍一些关键算法。这些算法采用文字叙述，同时也采用一种易于理解的结构化伪代码来描述。伪代码的描述和说明在附录C中给出。简要分析了书中所有算法的计算复杂性。历史资料：本书对许多主题的背景做了简要介绍。83位数学家和计算机科学家的简短传记以脚注的形式给出。这些传记介绍了他们的生活、事业，以及对离散数学做出过重要贡献的科学家的成就，同时配有他们的照片（如果有的话）。此外，脚注还包含了大量历史资料，作为本书正文中历史资料的补充。我们做了大量努力，使得本书能够反映最新的发现。关键术语和结论：每章最后列出关键术语和结论。关键术语只列出学生必须掌握的那些，而非该章中定义的每个术语。练习：书中包含4000多个练习题，涉及大量不同类型的问题。不仅提供了足够多的简单练习用于培养基本技能，还提供了大量的中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义，并按难易程度进行了分级。练习还包含一些特殊的讨论来展开正文中没有涉及的新概念，使得学生能够通过自己的工作来发现新的想法。 那些比平均难度稍难的练习用单个星号*标记，而那些相当有挑战性的练习则用两个星号**标记。需要用微积分来求解的练习也明确指出。而那些其结果要在正文中用到的练习则会明确地用指向右侧的手形符号来标识。本书最后给出了所有奇数编号练习的答案或解题纲要。解答通常包含那些大多数步骤写得很清楚的证明。 复习题：每章最后都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。要回答这些问题，学生必须写出较长的答案，而不是仅做一些计算或一个简答。补充练习：每章后面都有一组丰富而多样的补充练习。这些练习通常比每节后的练习难度更大些。补充练习强化该章中的概念，并把不同主题更有效地综合起来。 计算机课题：每章后面还有一组计算机课题。大约150个计算机课题将学生在计算和离散数学中所学到的内容联系起来。对于那些从数学角度或程序设计角度来看其难度超过平均水平的计算机课题用一个星号*标记，而那些非常具有挑战性的则用两个星号**标记。计算和探索：每章的最后都有一组计算和探索性的问题。完成这些练习（大约有120题）需要借助于现有的软件工具，如学生或教师自己编写的程序，或MapleTM或MathematicaTM这样的数学计算软件包。大部分这些练习为学生提供了通过计算来发现一些新事实或想法的机会（其中的一些练习在配套的在线练习册《探索离散数学》中也有讨论）。 写作课题：每章后面都有一组写作课题。要完成这类课题学生需要参考数学文献。有些课题本质上是关于历史的，需要学生查找原始资料。有些课题则是通往新内容和新思想的途径。所有此类练习是要向学生展示正文中没有深入探讨的想法。这些课题把数学概念和写作过程结合起来，以帮助学生面对未来可能的研究领域（在线版或印刷版的《学生解题指南》中可以找到为这些课题准备的参考文献）。附录：本书有3个附录。附录A介绍实数和正整数的公理，并解释如何利用这些公理直接证明事实。附录B介绍指数函数和对数函数，复习在课程中常用的一些基本内容。附录C则介绍正文中用来描述算法的伪代码。推荐读物：在附录后还提供了一组针对全书及各章的推荐读物。这些推荐读物包括难度不超过本书的书籍、更难些的书籍、阐述性的文章，以及发表离散数学新发现的原始文章。其中一些是多年前出版的经典读物，而另一些是在最近几年内才出版的。怎样使用本书本书经过精心写作和编排，适用于不同层次以及有不同重点的离散数学课程。下表列出了核心章节和可选章节。为大学二年级学生开设一学期的离散数学入门课程可以以本书核心章节为基础，其他章节可由教师取舍。两学期的入门课程可以在核心章节上外加所有可选的数学章节。强调计算机科学的课程则可以涵盖部分或全部可选的计算机科学章节。教师可以在本书网站上的《教师资源手册》中找到广泛的离散数学课程教学大纲样本，以及针对本书章节的教学建议。章核心章节可选的计算机科学章节可选的数学章节11.1~1.8(视需要)22.1~2.4、2.6(视需要)2.533.1~3.3(视需要)44.1~4.4(视需要)4.5、4.655.1~5.35.4、5.566.1~6.36.66.4、6.577.17.47.2、7.388.1、8.58.38.2、8.4、8.699.1、9.3、9.59.29.4、9.6.510.6～10.8、11.311.4、11.5.4.5使用本书的教师可以选用或略去每节最后有挑战性的例题及练习来调整其课程的难度。这里的各章依赖图展示的是强依赖性。星号表示该章的部分相关小节是学习后续章节必需的。弱依赖关系省略了。更多详细信息可以在《教师资源手册》中找到。辅助资料《学生解题指南》：这本可以单独购买的学生手册包含了所有奇数编号练习的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这个方法管用。对于有些练习，还给出了一两种其他可能的解法以说明一个问题可以由多种不同方法来求解。本指南给出了为每章后面的写作课题推荐的参考文献，还包含撰写证明指南、离散数学学习中学生常犯错误的一般性描述，以及为每章提供的考试样例及解答以帮助学生准备考试。 X（ISBN-10∶0-07-）　　　　（ISBN-13∶978-0-07-）《教师资源手册》：本手册在网站上有提供，教师也可以申请印刷版的。手册包含书中所有偶数编号练习的完整解答。给出了如何讲授本书每章内容的建议，包括每节中应强调的重点以及如何组织内容。手册还为每章提供了考试样例以及一个可供选择的包含1500多道考试题目的试题库。对于所有考试样例及试题库中的题目都给出了解答。最后，还给出了针对不同的侧重点以及学生能力水平的课程教学大纲样本。（ISBN-10∶0-07-）　　　　（ISBN-13∶978-0-07-）致谢感谢各类学校中使用本书并向我提供有价值的反馈和有益的建议的许多教师和学生，他们的反馈才有可能使得本书更出色。特别感谢Jerrold Grossman、Jean-Claude Evard和Georgia Mederer，他们作为第7版的技术审阅，以其“鹰眼”般敏锐的目光确保了本书的准确性。我也很感激那些通过网站提交评论的人们所提供的帮助。 感谢第7版以及前六版的评阅人，这些评阅人给予我许多有益的批评和鼓励，希望这一版不会辜负他们的期望。第7版评阅人Philip Barry　美国明尼苏达大学明尼阿波里斯分校Miklos Bona　美国佛罗里达大学Kirby Brown　美国皇后学院John Carter　加拿大多伦多大学Narendra Chaudhari　新加坡南洋理工大学Allan Cochran　美国阿肯色大学Daniel Cunningham　美国布法罗州立学院George Davis　美国佐治亚州立大学Andrzej Derdzinski　美国俄亥俄州立大学Ronald Dotzel　美国密苏里大学圣路易斯分校T.J.Duda　美国哥伦布州立社区学院Bruce Elenbogen　美国密歇根大学迪尔本分校Norma Elias　美国普渡大学卡鲁梅分校（哈蒙德）Herbert Enderton　美国加州大学洛杉矶分校Anthony Evans　美国莱特州立大学Kim Factor　美国马凯特大学Margaret Fleck　美国伊利诺伊大学香槟分校Peter Gillespie　美国费耶特维尔州立大学Johannes Hattingh　美国佐治亚州立大学Ken Holladay　美国新奥尔良大学Jerry Ianni　美国纽约长岛社区学院Ravi Janardan　美国明尼苏达大学明尼阿波里斯分校Norliza Katuk　马来西亚北方大学William Klostermeyer　美国北佛罗里达大学Przemo Kranz　美国密西西比大学Jaromy Kuhl　美国西佛罗里达大学Loredana Lanzani　美国阿肯色大学费耶特维尔分校Steven Leonhardi　美国威诺纳州立大学Xu Liutong　中国北京邮电大学Vladimir Logvinenko　美国迪安萨社区学院Darrell Minor　美国哥伦布州立社区学院Keith Olson　美国犹他谷大学Yongyuth Permpoontanalarp　泰国国王科技大学Galin Piatniskaia　美国密苏里大学圣路易斯分校Stefan Robila　美国蒙特克莱尔州立大学Chris Rodger　美国奥本大学Sukhit Singh　美国得克萨斯州立大学圣马科斯分校David Snyder　美国得克萨斯州立大学圣马科斯分校Wasin So　美国圣何塞州立大学Bogdan Suceava　美国加州州立大学富尔顿分校Christopher Swanson　美国阿什兰大学Bon Sy　美国皇后学院Matthew Walsh　美国印第安那普渡大学韦恩堡分校Gideon Weinstein　美国西部州长办大学David Wilczynski　美国南加州大学我要感谢责任编辑Bill Stenquist的倡导、热情和支持，他对这一版的帮助是不可或缺的。我还要感谢原编辑Wayne Yuhasz，他的洞察力和技能确保了本书的成功。我想要对为这一版做出宝贵贡献的RPK编辑部职员表达我的感谢，包括同时担任开发和产品编辑的Rose Kernan，还有RPK编辑团队的其他成员——Fred Dahl、Martha McMaster、Erin Wagner、Harlan James和Shelly Gerger-Knecthl。感谢PreTeX公司的排版人员Paul Mailhot为这一版做了大量的工作，以及他精湛的LaTex知识。还要感谢Photo Affairs公司的Danny Meldung很巧妙地寻找到新的传记脚注的图片。新版的准确性和高质量要归功于Jerry Grossman和Jean-Claude Evard，他们校对了整个手稿的技术准确性；Georgia Mederer校对了本书最后的答案和《学生解题指南》、《教师资源手册》中题解的准确性。像往常一样，Jerry Grossman编辑了这两册重要的辅助资料，怎么感谢他都不为过。我还要对麦格劳希尔高等教育的科学、工程和数学部（SEM）表达感谢，他们对这一版本以及相关的媒体内容给予了强有力的支持。特别是，感谢麦格劳希尔高等教育SEM总裁Kurt Strand、SEM主编Marty Lange、编辑部主任Michael Lange、全球发行主任Raghothaman Srinivasan、责任编辑Bill Stenquist、市场执行主任Curt Reynolds、项目经理Robin A.Reed、采购员Sandy Ludovissey、内部开发编辑Lorraine Buczek、设计协调人Brenda Rowles、铅照片研究协调人Carrie K.Burger和媒体项目经理Tammy Juran。Kenneth H.Rosen
出版者的话译者序前言配套网站致学生关于作者符号表第1章　基础：逻辑和证明1　1.1　命题逻辑1　　1.1.1　引言1　　1.1.2　命题1　　1.1.3　条件语句4　　1.1.4　复合命题的真值表8　　1.1.5　逻辑运算符的优先级8　　1.1.6　逻辑运算和位运算8　　练习10　1.2　命题逻辑的应用15　　1.2.1　引言15　　1.2.2　语句翻译15　　1.2.3　系统规范说明16　　1.2.4　布尔搜索16　　1.2.5　逻辑谜题17　　1.2.6　逻辑电路18　　练习19　1.3　命题等价式22　　1.3.1　引言22　　1.3.2　逻辑等价式23　　1.3.3　德·摩根律的运用25　　1.3.4　构造新的逻辑等价式25　　1.3.5　命题的可满足性26　　1.3.6　可满足性的应用27　　1.3.7　可满足性问题求解29　　练习30　1.4　谓词和量词32　　1.4.1　引言32　　1.4.2　谓词33　　1.4.3　量词35　　1.4.4　约束论域的量词37　　1.4.5　量词的优先级38　　1.4.6　变量绑定38　　1.4.7　涉及量词的逻辑等价式38　　1.4.8　量化表达式的否定39　　1.4.9　语句到逻辑表达式的翻译40　　1.4.10　系统规范说明中量词的使用42　　1.4.11　选自路易斯·卡罗尔的例子42　　1.4.12　逻辑程序设计43　　练习44　1.5　嵌套量词49　　1.5.1　引言49　　1.5.2　理解涉及嵌套量词的语句49　　1.5.3　量词的顺序50　　1.5.4　数学语句到嵌套量词语句的翻译51　　1.5.5　嵌套量词到自然语言的翻译52　　1.5.6　汉语语句到逻辑表达式的翻译52　　1.5.7　嵌套量词的否定53　　练习54　1.6　推理规则59　　1.6.1　引言59　　1.6.2　命题逻辑的有效论证60　　1.6.3　命题逻辑的推理规则61　　1.6.4　使用推理规则建立论证62　　1.6.5　消解律63　　1.6.6　谬误64　　1.6.7　量化命题的推理规则64　　1.6.8　命题和量化命题推理规则的组合使用66　　练习66　1.7　证明导论69　　1.7.1　引言69　　1.7.2　一些专用术语70　　1.7.3　理解定理是如何陈述的70　　1.7.4　证明定理的方法70　　1.7.5　直接证明法71　　1.7.6　反证法71　　1.7.7　归谬证明法73　　1.7.8　证明中的错误75　　1.7.9　良好的开端76　　练习77　1.8　证明的方法和策略78　　1.8.1　引言78　　1.8.2　穷举证明法和分情形证明法78　　1.8.3　存在性证明81　　1.8.4　唯一性证明84　　1.8.5　证明策略84　　1.8.6　寻找反例86　　1.8.7　证明策略实践86　　1.8.8　拼接87　　1.8.9　开放问题的作用89　　1.8.10　其他证明方法90　　练习90　关键术语和结论92　复习题94　补充练习95　计算机课题97　计算和探索97　写作课题98第2章　基本结构：集合、函数、序列、求和与矩阵99　2.1　集合99　　2.1.1　引言99　　2.1.2　文氏图101　　2.1.3　子集102　　2.1.4　集合的大小103　　2.1.5　幂集103　　2.1.6　笛卡儿积104　　2.1.7　使用带量词的集合符号105　　2.1.8　真值集和量词106　　练习106　2.2　集合运算108　　2.2.1　引言108　　2.2.2　集合恒等式110　　2.2.3　扩展的并集和交集112　　2.2.4　集合的计算机表示114　　练习115　2.3　函数118　　2.3.1　引言118　　2.3.2　一对一函数和映上函数120　　2.3.3　反函数和函数组合122　　2.3.4　函数的图124　　2.3.5　一些重要的函数125　　2.3.6　部分函数127　　练习128　2.4　序列与求和132　　2.4.1　引言132　　2.4.2　序列133　　2.4.3　递推关系134　　2.4.4　特殊的整数序列136　　2.4.5　求和137　　练习141　2.5　集合的基数144　　2.5.1　引言144　　2.5.2　可数集145　　2.5.3　不可数集合147　　练习149　2.6　矩阵151　　2.6.1　引言151　　2.6.2　矩阵算术152　　2.6.3　矩阵的转置和幂153　　2.6.4　0-1矩阵153　　练习155　关键术语和结论158　复习题160　补充练习160　计算机课题162　计算和探索163　写作课题163第3章　算法164　3.1　算法164　　3.1.1　引言164　　3.1.2　搜索算法166　　3.1.3　排序167　　3.1.4　贪婪算法170　　3.1.5　停机问题172　　练习173　3.2　函数的增长176　　3.2.1　引言176　　3.2.2　大O记号176　　3.2.3　一些重要函数的大O估算179　　3.2.4　函数组合的增长182　　3.2.5　大Ω与大Θ记号183　　练习184　3.3　　算法的复杂度187　　3.3.1　引言187　　3.3.2　时间复杂度188　　3.3.3　矩阵乘法的复杂度190　　3.3.4　算法范型191　　3.3.5　理解算法的复杂度192　　练习195　关键术语和结论198　复习题199　补充练习200　计算机课题203　计算和探索203　写作课题203第4章　数论和密码学204　4.1　整除性和模算术204　　4.1.1　引言204　　4.1.2　除法204　　4.1.3　除法算法205　　4.1.4　模算术206　　4.1.5　模m算术208　　练习208　4.2　整数表示和算法210　　4.2.1　引言210　　4.2.2　整数表示210　　4.2.3　整数运算算法213　　4.2.4　模指数运算216　　练习217　4.3　素数和最大公约数219　　4.3.1　引言219　　4.3.2　素数220　　4.3.3　试除法220　　4.3.4　埃拉托斯特尼筛法221　　4.3.5　关于素数的猜想和开放问题224　　4.3.6　最大公约数和最小公倍数225　　4.3.7　欧几里得算法227　　4.3.8　gcd的线性组合表示228　　练习230　4.4　求解同余方程233　　4.4.1　引言233　　4.4.2　线性同余方程233　　4.4.3　中国剩余定理235　　4.4.4　大整数的计算机算术236　　4.4.5　费马小定理237　　4.4.6　伪素数238　　4.4.7　原根和离散对数239　　练习240　4.5　同余应用243　　4.5.1　散列函数243　　4.5.2　伪随机数244　　4.5.3　校验码244　　练习246　4.6　密码学248　　4.6.1　引言248　　4.6.2　古典密码学248　　4.6.3　公钥密码学251　　4.6.4　RSA密码系统251　　4.6.5　RSA加密252　　4.6.6　RSA解密253　　4.6.7　用RSA作为公钥系统254　　4.6.8　密码协议254　　练习255　关键术语和结论257　复习题259　补充练习260　计算机课题262　计算和探索262　写作课题263第5章　归纳与递归264　5.1　数学归纳法264　　5.1.1　引言264　　5.1.2　数学归纳法265　　5.1.3　为什么数学归纳法是有效的266　　5.1.4　数学归纳法的优点与缺点266　　5.1.5　利用数学归纳法证明的例子266　　5.1.6　使用数学归纳法时犯的错误275　　5.1.7　运用数学归纳法证明的原则276　　练习276　5.2　强归纳法与良序性281　　5.2.1　引言281　　5.2.2　强归纳法282　　5.2.3　利用强归纳法证明的例子283　　5.2.4　计算几何学中使用强归纳法285　　5.2.5　利用良序性证明287　　练习288　5.3　递归定义与结构归纳法291　　5.3.1　引言291　　5.3.2　递归地定义函数291　　5.3.3　递归地定义集合与结构294　　5.3.4　结构归纳法298　　5.3.5　广义归纳法300　　练习300　5.4　递归算法305　　5.4.1　引言305　　5.4.2　证明递归算法的正确性307　　5.4.3　递归与迭代308　　5.4.4　归并排序309　　练习312　5.5　程序正确性314　　5.5.1　引言314　　5.5.2　程序验证314　　5.5.3　推理规则315　　5.5.4　条件语句315　　5.5.5　循环不变量316　　练习318　关键术语和结论319　复习题320　补充练习321　计算机课题325　计算和探索325　写作课题326第6章　计数327　6.1　计数的基础327　　6.1.1　引言327　　6.1.2　基本的计数原则327　　6.1.3　比较复杂的计数问题331　　6.1.4　减法法则（两个集合的容斥原理）332　　6.1.5　除法法则333　　6.1.6　树图333　　练习334　6.2　鸽巢原理338　　6.2.1　引言338　　6.2.2　广义鸽巢原理339　　6.2.3　鸽巢原理的几个简单应用341　　练习342　6.3　排列与组合344　　6.3.1　引言344　　6.3.2　排列345　　6.3.3　组合346　　练习348　6.4　二项式系数和恒等式351　　6.4.1　二项式定理351　　6.4.2　帕斯卡恒等式和三角形353　　6.4.3　其他的二项式系数恒等式354　　练习355　6.5　排列与组合的推广358　　6.5.1　引言358　　6.5.2　有重复的排列358　　6.5.3　有重复的组合358　　6.5.4　具有不可区别物体的集合的排列361　　6.5.5　把物体放入盒子362　　练习364　6.6　生成排列和组合367　　6.6.1　引言367　　6.6.2　生成排列368　　6.6.3　生成组合369　　练习370　关键术语和结论371　复习题372　补充练习373　计算机课题376　计算和探索376　写作课题377第7章　离散概率378　7.1　离散概率引论378　　7.1.1　引言378　　7.1.2　有限概率378　　7.1.3　事件组合的概率381　　7.1.4　概率的推理381　　练习382　7.2　概率论384　　7.2.1　引言384　　7.2.2　概率指派384　　7.2.3　事件的组合385　　7.2.4　条件概率386　　7.2.5　独立性387　　7.2.6　伯努利试验与二项分布388　　7.2.7　随机变量389　　7.2.8　生日问题390　　7.2.9　蒙特卡罗算法391　　7.2.10　概率方法392　　练习393　7.3　贝叶斯定理396　　7.3.1　引言396　　7.3.2　贝叶斯定理396　　7.3.3　贝叶斯垃圾邮件过滤器399　　练习401　7.4　期望值和方差403　　7.4.1　引言403　　7.4.2　期望值404　　7.4.3　期望的线性性质405　　7.4.4　平均情形下的计算复杂度407　　7.4.5　几何分布408　　7.4.6　独立随机变量409　　7.4.7　方差410　　7.4.8　切比雪夫不等式413　　练习414　关键术语和结论416　复习题417　补充练习418　计算机课题422　计算和探索422　写作课题422第8章　高级计数技术424　8.1　递推关系的应用424　　8.1.1　引言424　　8.1.2　用递推关系构造模型425　　8.1.3　算法与递推关系429　　练习431　8.2　求解线性递推关系435　　8.2.1　引言435　　8.2.2　求解常系数线性齐次递推关系436　　8.2.3　常系数线性非齐次的递推关系439　　练习441　8.3　分治算法和递推关系444　　8.3.1　引言444　　8.3.2　分治递推关系445　　练习450　8.4　生成函数452　　8.4.1　引言452　　8.4.2　关于幂级数的有用事实452　　8.4.3　计数问题与生成函数455　　8.4.4　使用生成函数求解递推关系458　　8.4.5　使用生成函数证明恒等式459　　练习459　8.5　容斥464　　8.5.1　引言464　　8.5.2　容斥原理464　　练习467　8.6　容斥原理的应用468　　8.6.1　引言468　　8.6.2　容斥原理的另一种形式469　　8.6.3　埃拉托色尼筛469　　8.6.4　映上函数的个数470　　8.6.5　错位排列471　　练习472　关键术语和结论473　复习题474　补充练习475　计算机课题478　计算和探索478　写作课题479第9章　关系480　9.1　关系及其性质480　　9.1.1　引言480　　9.1.2　函数作为关系481　　9.1.3　集合的关系481　　9.1.4　关系的性质482　　9.1.5　关系的组合484　　练习485　9.2　n元关系及其应用489　　9.2.1　引言489　　9.2.2　n元关系489　　9.2.3　数据库和关系490　　9.2.4　n元关系的运算491　　9.2.5　SQL493　　练习493　9.3　关系的表示495　　9.3.1　引言495　　9.3.2　用矩阵表示关系495　　9.3.3　用图表示关系497　　练习498　9.4　关系的闭包500　　9.4.1　引言500　　9.4.2　闭包501　　9.4.3　有向图中的路径501　　9.4.4　传递闭包502　　9.4.5　沃舍尔算法505　　练习507　9.5　等价关系509　　9.5.1　引言509　　9.5.2　等价关系509　　9.5.3　等价类510　　9.5.4　等价类与划分512　　练习514　9.6　偏序518　　9.6.1　引言518　　9.6.2　字典顺序520　　9.6.3　哈塞图521　　9.6.4　极大元与极小元522　　9.6.5　格524　　9.6.6　拓扑排序525　　练习527　关键术语和结论532　复习题533　补充练习534　计算机课题538　计算和探索538　写作课题538第10章　图540　10.1　图和图模型540　　10.1.1　图模型543　　练习546　10.2　图的术语和几种特殊的图549　　10.2.1　引言549　　10.2.2　基本术语549　　10.2.3　一些特殊的简单图551　　10.2.4　二分图552　　10.2.5　二分图和匹配553　　10.2.6　特殊类型图的一些应用556　　10.2.7　从旧图构造新图557　　练习559　10.3　图的表示和图的同构563　　10.3.1　引言563　　10.3.2　图的表示563　　10.3.3　邻接矩阵563　　10.3.4　关联矩阵565　　10.3.5　图的同构566　　10.3.6　判定两个简单图是否同构566　　练习568　10.4　连通性573　　10.4.1　引言573　　10.4.2　通路573　　10.4.3　无向图的连通性575　　10.4.4　图是如何连通的576　　10.4.5　有向图的连通性578　　10.4.6　通路与同构579　　10.4.7　计算顶点之间的通路数580　　练习580　10.5　欧拉通路与哈密顿通路585　　10.5.1　引言585　　10.5.2　欧拉通路与欧拉回路585　　10.5.3　哈密顿通路与哈密顿回路589　　10.5.4　哈密顿回路的应用592　　练习593　10.6　最短通路问题597　　10.6.1　引言597　　10.6.2　最短通路算法599　　10.6.3　旅行商问题603　　练习604　10.7　平面图607　　10.7.1　引言607　　10.7.2　欧拉公式609　　10.7.3　库拉图斯基定理611　　练习612　10.8　图着色614　　10.8.1　引言614　　10.8.2　图着色的应用618　　练习619　关键术语和结论622　复习题625　补充练习626　计算机课题630　计算和探索631　写作课题631第11章　树633　11.1　树的概述633　　11.1.1　有根树634　　11.1.2　树作为模型637　　11.1.3　树的性质638　　练习641　11.2　树的应用643　　11.2.1　引言643　　11.2.2　二叉搜索树643　　11.2.3　决策树646　　11.2.4　前缀码647　　11.2.5　博弈树649　　练习653　11.3　树的遍历656　　11.3.1　引言656　　11.3.2　通用地址系统656　　11.3.3　遍历算法657　　11.3.4　中缀、前缀和后缀记法662　　练习665　11.4　生成树667　　11.4.1　引言667　　11.4.2　深度优先搜索669　　11.4.3　宽度优先搜索671　　11.4.4　回溯的应用672　　11.4.5　有向图中的深度优先搜索674　　练习675　11.5　最小生成树678　　11.5.1　引言678　　11.5.2　最小生成树算法678　　练习681　关键术语和结论683　复习题685　补充练习686　计算机课题688　计算和探索689　写作课题689第12章　布尔代数690　12.1　布尔函数690　　12.1.1　引言690　　12.1.2　布尔表达式和布尔函数691　　12.1.3　布尔代数恒等式692　　12.1.4　对偶性694　　12.1.5　布尔代数的抽象定义694　　练习695　12.2　布尔函数的表示696　　12.2.1　积之和展开式696　　12.2.2　函数完备性698　　练习698　12.3　逻辑门电路699　　12.3.1　引言699　　12.3.2　门的组合699　　12.3.3　电路的例子700　　12.3.4　加法器702　　练习703　12.4　电路的极小化704　　12.4.1　引言704　　12.4.2　卡诺图705　　12.4.3　无需在意的条件710　　12.4.4　奎因莫可拉斯基方法712　　练习715　关键术语和结论716　复习题718　补充练习718　计算机课题720　计算和探索720　写作课题720第13章　计算模型722　13.1　语言和文法722　　13.1.1　引言722　　13.1.2　短语结构文法723　　13.1.3　短语结构文法的类型725　　13.1.4　派生树726　　13.1.5　巴克斯诺尔范式727　　练习728　13.2　带输出的有限状态机732　　13.2.1　引言732　　13.2.2　带输出的有限状态机733　　练习736　13.3　不带输出的有限状态机738　　13.3.1　引言738　　13.3.2　串的集合738　　13.3.3　有限状态自动机738　　13.3.4　有限状态机的语言识别739　　13.3.5　非确定性的有限状态自动机743　　练习746　13.4　语言的识别750　　13.4.1　引言750　　13.4.2　克莱因定理751　　13.4.3　正则集合和正则文法754　　13.4.4　一个不能由有限状态自动机识别的集合756　　13.4.5　一些更强大的机器756　　练习757　13.5　图灵机759　　13.5.1　引言759　　13.5.2　图灵机的定义760　　13.5.3　用图灵机识别集合762　　13.5.4　用图灵机计算函数763　　13.5.5　不同类型的图灵机763　　13.5.6　丘奇图灵论题764　　13.5.7　计算复杂度、可计算性和可判定性764　　练习767　关键术语和结论769　复习题770　补充练习771　计算机课题773　计算和探索773　写作课题773附录A　实数和正整数的公理775附录B　指数与对数函数779附录C　伪代码781推荐读物785参考文献789奇数编号练习答案??　参见华章网站。
离散数学一直被IEEE & ACM确定为计算机专业最核心的课程（最新版CC2005），也是《中国计算机科学与技术学科教程2002》中界定的计算机科学与技术专业的核心基础课程。当你学习离散数学时，你会发现离散数学为许多计算机专业课程提供理论基础，尤其是为大多数计算机算法提供基础。本书清晰地介绍了离散数学中的概念和技术，并向读者展示其相关性和实用性，给计算机科学专业的学生将来的学习提供一切必需的数学基础。本书的优秀之处不仅在于作者对离散数学知识点精心编排，而且其行文流畅、通俗易懂，拥有大量有趣而实用的例子，推荐读物吸引读者广泛的好奇心，丰富的练习帮助读者掌握离散数学的概念和技巧。本书最大的优势在于它的配套网站中给出了一系列丰富的课外资源，既可以辅助教师根据实际情况安排教学活动；又能够帮助学生评估自身学习状况，学习撰写证明并避免常见错误，从各个方面提高学生学习和解决问题的能力，引领学生探索离散数学的新应用。本书的另一个特色是以脚注形式给出的历史资料，让读者了解许多数学知识的来龙去脉以及数学家所做出的贡献，这可以极大提高读者学习离散数学的兴趣，有助于读者了解其发展历程。本书译自Kenneth H. Rosen所著的《Discrete Mathematics and Its Applications, Seventh Edition》。这本书在北美及全球有超过600多所大学采用，在中国也已经被多所大学采纳作为计算机系的离散数学教材。作者一直根据广大教师和学生的反馈意见不断完善这本书，使其能适应计算机科学及应用的发展。自出版以来这本书在北美发行超过350 000册，同时这本书也已经被翻译成法文、希腊文、中文、越南文和韩文等。因此，本书是一本不俗的教科书。如果你有幸读到本书，那恭喜你了。你可以参考作者的建议或按自己的兴趣阅读本书，我相信你一定能从本书中获益匪浅。本书第7版做了重大修订，翻译工作是在第6版译稿的基础上进行的。感谢第6版的译者袁崇义、屈婉玲、张桂芸。第7版翻译分工如下：作者简介、前言、配套网站、致学生，以及第1章至第4章（含奇数编号练习答案）、附录、推荐读物由徐六通（本书英文原版第7版正式评阅人之一）翻译，第5章至第8章（含奇数编号练习答案）由吴斌翻译，第9章至第13章（含奇数编号练习答案）由杨娟翻译。由于译者水平所限，本书难免有不妥的地方，敬请读者不吝赐教。译者2014年10月于北京
计算机\离散数学
离散数学及其应用（英文精编版·第6版）
离散数学及其应用（英文版·第6版）
站内快速链接
　学生用户
　教师用户
　专业读者
　企业用户
　　新书上架
　　华章推荐
　　畅销书榜
　　媒体书评
　　经管类图书
　　计算机图书
　　外语类图书
　　数学类图书
　　机电类图书
　最新动态
　　华章动态
　　行业资讯
　　新书出版
　　活动专题
　专题活动
　　图书区
　　活动区
　　媒体区
　　售前售后服务区
　人才招聘
　关于我们
　　认识华章
　　企业标识
　　组织结构
　　图书获奖
　　联系我们
　　加盟华章
　　版权声明
　　法律条款
版权所有& 2015& 北京华章图文信息有限公司&京ICP备号&京公网安备号通信地址：北京市百万庄南街1号 邮编：100037电话：(010)378998 传真：(010)995260
高校教师服务
无法显示刷新网页