本书是经典的离散数学教材，被全球数百所大学广为采用。书中全面而系统地介绍了离散数学的理论和方法，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。
经典教材全面升级，全球数百万学生阅读，新版包含超过800道例题和4200道习题
本书是根据我多年来讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供内容准确且可读性强的教材，清晰地介绍并展示离散数学中的概念和技术。对于那些爱怀疑的学生，我的目标是展示离散数学的相关性和实用性。对于计算机科学专业的学生，我希望为他们将来的学习提供一切必需的数学基础。而对于数学专业的学生，我希望帮助他们理解重要的数学概念，并且意识到为什么这些概念对应用来说很重要。最重要的是，希望本书既能达到这些目标，又不含太多的水分。
对教师而言，我的目的是利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具：只要有本书在手，教师就能迅速地从中筛选内容，以最适合特定学生的方式有效地开展离散数学的教学工作。希望我已经实现了这些目标。
在过去的30年中，本书取得了极大的成功，被世界各地超过100万名学生使用，并被翻译成多种语言，对此我感到非常欣慰。此次第8版所做的许多改进，正是得益于大量读者的反馈和建议。在这些读者中，既有来自北美600多所学校的师生，又有来自全球各地众多高校的读者，他们都曾将本书成功用作教材。由于所收到的这些反馈，以及在不断更新中所投入的大量精力，我才能够在每次升级时显著提高本书的吸引力和有效性。
本教材是为一学期或两学期的离散数学入门课程而设计的，适用于数学、计算机科学、工程等各类专业的学生。大学代数是唯一要求的先修课程，不过，要想真正学好离散数学，还是需要有一定的数学素养。本书的设计目标是满足各种类型离散数学入门课程的需求，内容高度灵活且非常全面。我希望本书不仅是一本成功的教科书，而且成为学生在日后的学习和职业生涯中可以参考的有价值的资源。
离散数学课程的目标
离散数学课程有多个目标。学生应该学会一系列特定的数学知识并知道怎样应用它们，更重要的是，这门课应教会学生怎样运用数学逻辑思维。为了达到这些目标，本教材特别强调数学推理以及问题求解的不同方法。本书中，五个重要主题将交织在一起：数学推理，组合分析，离散结构，算法思维，以及应用与建模。一门成功的离散数学课程应该小心谨慎地融合并平衡所有五个主题。
●数学推理。学生必须理解数学推理以便阅读、领会并构造数学论证。本书开篇即讨论数理逻辑，这为后续讨论证明方法打下了基础。本书描述了构造证明的方法与技巧两个方面。本书特别强调数学归纳法，不仅给出了这种证明技术的许多不同类型的实例，还详细地解释了数学归纳法为什么是一种有效的证明技术。
●组合分析。一个重要的解题技巧就是计数或枚举对象。本书中关于枚举的讨论从计数的基本技术着手。重点是运用组合分析方法来解决计数问题并分析算法，而不是简单地应用公式。
●离散结构。离散数学课程应该教会学生如何处理离散结构，即表示离散对象以及对象之间关系的抽象数学结构。这些离散结构包括集合、置换、关系、图、树和有限状态机等。
●算法思维。有些类型的问题可以通过算法的规范说明来求解。当一个算法被清楚地描述后，就可以编写计算机程序来实现之。该活动涉及的数学部分包括该算法的规范说明、正确性的验证，以及执行算法所需要的计算机内存和时间分析等，这些在本书中均有阐述。算法将采用自然语言 原书采用英语，而中译版则采用汉语。——译者注和一种易于理解的伪代码形式来描述。
●应用与建模。离散数学在几乎每个可以想到的研究领域中都有应用。许多应用涉及本书提到的计算机科学和数据网络，还有一些应用涉及更为广泛的领域，如化学、生物学、语言学、地理学、商业和互联网等。这些是离散数学的自然而又重要的应用，而非人为编造的。用离散数学来建模是一项十分重要的问题求解技巧，学生可通过一些练习来自己构造模型，从而掌握这一技巧。
第8版中的变化
虽然第7版已经是一本极具影响力的教材，但许多教师还是提出了一些修改请求，以使本书更适于教学。我花了大量的时间和精力来满足这些请求，努力以自己的方式改进本书并使之紧跟最新发展。
第8版的修改基于20多位正式审稿人的意见、学生和教师的反馈以及我自己的见解，希望新版本能成为一个更加有效的教学工具。第8版中所做的大量更新是为了帮助学生更好地学习这些内容。我增加了额外的解释和例子以便阐述那些学生经常感到困难的内容，增加了知识性的和富有挑战性的新练习，还增加了一些与Internet、计算机科学以及数学生物学等密切相关的应用。在开发人员的努力下，本书配套网站现在提供了很多工具，可以帮助学生掌握关键概念并探索离散数学世界。此外，还提供了有效和全面的学习和评估工具，以作为教科书的补充。
我希望教师能仔细阅读新版，以了解如何满足自己的教学需求。要列出所有更新是不切实际的，不过，我将给出概要性的描述，包括一些关键更新及其所带来的好处，这对读者来说或许是有益的。
本书新版对许多内容进行了完善、更新、补充和润色，所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。之前使用过本教材的教师会发现这次更新遍及全书，其中最值得注意的修订如下。
全书范围的更新
●对内容编排的完善贯穿全书，重点是使之更清晰，以便帮助学生阅读和理解概念。
●通过增加细节和解释来改进证明，同时提醒读者注意所采用的证明方法。
●新增例题，用于满足审稿人提出的需求，或是对新内容进行解释。有些例题可以在书中找到，有些例题则只在配套网站上提供。
●新增练习，有知识性的也有富有挑战性的，用于满足教师提出的需求或配合新内容。同时，还有些练习是为了完善或拓宽已有的练习。
●引入了更多的小标题以便将章节划分成更小的部分。
●极大地扩展了在线资源，以为教师和学生提供广泛的支持。后面会给出关于这些资源的详细描述。
主题方面的更新
●逻辑。引入了若干逻辑谜题。一道新例题解释了如何将n皇后问题建模为可满足性问题，这是一个简明易懂的例子。
●集合论。在正文中引入了多重集的概念（之前是在练习中引入的）。
●算法。新版讨论了字符串匹配算法，这是一个应用很广的重要算法，可用于拼写检查、关键字搜索、字符串匹配以及计算生物学。此外，还给出了求解字符串匹配练习的蛮力算法。
●数论。新版包含有关素数及其猜想的最新数值发现和理论发现。在正文中论述了扩展欧几里得算法和一遍（one-pass）算法（之前是在练习中介绍的）。
●密码学。由于在云计算中的重要性，新版涵盖了同态加密的概念。
●数学归纳法。扩展了数学归纳法证明的模板，并将其放在数学归纳法证明的例题之前。
●计数方法。扩充了用于计数的除法法则的讨论。
●数据挖掘。在n元关系一节讨论了数据挖掘中的一个关键概念——关联规则。另外，在练习中还引入了雅卡尔指数，可用于计算两个集合之间的距离。
●图论应用。添加了一道新例题，解释语义网络是如何工作的。这是人工智能中的一个重要结构，可以用图来建模。
●人物传记。新的人物传记包括怀尔斯、婆什迦罗、瓦列·普金、阿达马、张益唐和金特里。原有的传记也做了一些扩展和更新。这次更新是多方面的，包括具有历史意义的东方数学家、19世纪和20世纪的主要研究人员，以及目前活跃的21世纪的数学家和计算机科学家。
本书特色
易理解性。实践证明，本书对于初学者来说是易读易懂的。书中绝大部分内容不需要比大学代数更多的数学预备知识，需要额外帮助的学生可以在配套网站找到相应工具，以将数学素养提升到本书要求的水准。书中少数几处需要用到微积分知识的地方都已注明。大多数学生应该很容易理解用于表示算法的伪代码，无论是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易于理解和易于领会的水平开始。一旦详细介绍了基本数学概念，就会给出稍难一些的内容以及在其他研究领域中的应用。
灵活性。为了便于灵活使用，本书做了精心的设计。各章对之前章节的依赖程度都被降到最低。每章分成长度大致相等的若干节，每节又根据内容划分成若干小节以方便教学。教师可以利用章节划分灵活地安排讲课进度。
写作风格。本书的写作风格是直接而又实用的。书中使用准确的数学语言，但没有采用过多的形式化与抽象，在数学命题中的记号和词语表达间做了精心的平衡。
数学严谨性和准确性。书中所有定义和定理的陈述都十分谨慎，这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则是先由动机引入，然后再慢慢展开，并且所有步骤都经过了详细论证。证明中用到的公理及其所导出的基本性质在附录中均有描述，这呈现给学生一个清晰的概念，即在证明中他们能够做出何种假设。本书解释并大量使用了递归定义。
例题。全书共有超过800道例题，用来阐述概念、建立不同主题之间的关联以及介绍应用。在大部分例题中，首先提出问题，然后再以适量的细节给出解法。
应用。本书中的应用展示了离散数学在解决现实世界中的问题时的实用性。这些应用涉及广泛的领域，包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和互联网。
算法。离散数学的结论常常要用算法来表述，故书中多数章节都介绍了一些关键算法。这些算法采用文字叙述，同时也采用一种易于理解的结构化伪代码来描述。关于伪代码的描述和说明在附录C中给出。对于本书中的所有算法，都简要分析了其计算复杂度。
历史资料。书中对许多主题的背景做了简要介绍，并给出了89位数学家和计算机科学家的简短传记。这些科学家为离散数学做出过重要贡献，传记中介绍了他们的生活、事业和成就，同时配有照片（如果有的话）。
此外，我们还提供了一些历史资料，作为对正文中历史资料的补充。我们做了大量努力以使得本书能够反映新的发现。
关键术语和结论。每章最后列出关键术语和结论。关键术语只列出学生必须学会的那些，而非该章中定义的每个术语。
练习。书中包含4200多道练习题，涵盖大量不同类型的问题。不仅提供了足够多的简单练习用于培养基本技能，还提供了大量中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义，并按难易程度进行了分级。练习中还包含一些特殊的讨论来展开正文中没有涉及的新概念，使得学生能够通过自己的努力来发现新的想法。
那些比平均难度稍难的练习用一个星号（*）标记，而那些更具挑战性的练习则用两个星号（**）来标记。需要用微积分知识求解的练习会明确指出。有些练习的结果要在正文中用到，我们用符号来标识这类题目。本书最后给出了所有奇数编号练习的答案或解题纲要。答案中大部分证明的步骤都十分清晰。
复习题。每章后面都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。要回答这些复习题，学生必须写出较长的答案，而不是仅做一些计算或给出简答。
补充练习。每章后面都有一组丰富多样的补充练习。这些练习通常比每节后面的练习难度更大。补充练习旨在强化该章中的概念，并把不同主题更有效地综合起来。
计算机课题。每章后面还有一组计算机课题。全书共有大约150道计算机课题，用于将学生在计算和离散数学中所学到的内容联系起来。对于那些从数学角度或程序设计角度来看难度超过平均水平的计算机课题，我们用一个星号（*）标记，而那些非常具有挑战性的题目则用两个星号（**）标记。
计算和探索。每章后面都有一组计算和探索性的问题，共有大约120道。完成这些练习需要借助现有的软件工具，诸如学生或教师自己编写的程序，或像Maple或Mathematica这样的数学计算软件包。这些练习大多为学生提供了通过计算来发现一些新事实或想法的机会。（其中一些练习在配套的在线练习册《探索离散数学》（Exploring Discrete Mathematics）中也有讨论。）
写作课题。每章后面都有一组写作课题，要完成这类题目，学生需要参考数学方面的文献。有些题目本质上是关于历史知识的，需要学生查找原始资料；其他题目则将带领学生通往新内容和新思想。这些练习旨在向学生展示正文中没有深入探讨的想法，通过把数学概念和写作过程结合起来，帮助学生面对未来可能的研究领域。（在网络版或印刷版的《学生解题指南》（Student’s Solutions Guide）中可以找到为这些题目准备的参考文献。）
附录。本书有三个附录。附录A介绍实数和正整数的公理，并解释如何利用这些公理直接证明事实。附录B介绍指数函数和对数函数，复习课程中常用的一些基本内容。附录C则介绍正文中用来描述算法的伪代码。
推荐读物。在附录后还提供了一份针对全书及各章的推荐读物。这些推荐读物包括难度不超过本书的书籍、更难些的书籍、阐述性的文章以及发表离散数学新发现的原始文章。其中一些是多年前出版的经典读物，而另一些是在最近几年才出版的。本书的网站中包含许多有价值资源的链接，可以作为对这些推荐读物的补充。
怎样使用本书
本书经过了精心写作和编排，以支持不同层次以及侧重点不同的离散数学课程。下表列出了核心章节和可选章节。为大学二年级学生开设一学期的离散数学入门课程可以以本书核心章节为基础，其他章节可由教师取舍。两学期的入门课程可以在核心章节上外加所有可选的数学章节。强调计算机科学的课程则可以涵盖部分或全部计算机科学章节。教师可以在本书网站上的《教师资源手册》（Instructor’s Resource Guide）中找到离散数学课程教学大纲样本，以及针对本书章节的教学建议。
章节 核心章节 计算机科学可选章节 数学可选章节
1 1.1～1.8(视需要)
2 2.1～2.4,2.6(视需要) 2.5
3 3.1～3.3(视需要)
4 4.1～4.4(视需要) 4.5,4.6
（续）
章节 核心章节 计算机科学可选章节 数学可选章节
5 5.1～5.3 5.4,5.5
6 6.1～6.3 6.6 6.4,6.5
7 7.1 7.4 7.2,7.3
8 8.1,8.5 8.3 8.2,8.4,8.6
9 9.1,9.3,9.5 9.2 9.4,9.6
10 10.1～10.5 10.6～10.8
11 11.1 11.2,11.3 11.4,11.5
12 12.1～12.4
13 13.1～13.5
使用本书的教师可以选用或略去每节最后有挑战性的例题及练习来调整课程的难度。右侧的各章依赖图展示的是强依赖性。星号表示该章只有部分相关小节是学习后续章节所必需的。弱依赖关系不再列出。更多详细信息可以在《教师资源手册》中找到。
教辅资源
关于本书教辅资源，只有使用本书作为教材的教师才可以申请，需要的教师可向麦格劳·希尔教育出版公司北京代表处申请，电话010-57997618/7600，传真010-59575582，电子邮件instructorchina@mheducation.com。——编辑注
《学生解题指南》。这本可以单独购买的学生手册包含所有奇数编号练习的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这种方法管用。对于有些问题，还给出了一两种其他可能的解法，以说明一个问题可以用多种不同方法来求解。指南的内容还包括：为每章后面的写作课题推荐的参考文献；关于如何撰写证明的指南；在离散数学学习中学生常犯的各类错误；为每章提供的考试样例及解答，以帮助学生准备考试。
《教师资料手册》。本手册在网站上提供，教师也可以申请印刷版，手册中包含书中所有偶数编号练习的完整解答。手册的内容还包括：关于如何讲授本书每章内容的建议，包括每节中应强调的重点以及如何组织内容；为每章提供的考试样例，以及一个包含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 Czarnecki-Lichstein，业务产品经理
●Megan Platt，编辑协调人
●Lora Neyens和Jolynn Kilburg，项目经理
●Lorraine Buczek，内容授权专家
Kenneth H. Rosen
计算机\离散数学
本书是介绍离散数学理论和方法的经典教材，被全球数百所高校采用，获得了极大的成功。第8版做了与时俱进的更新，添加了多重集、字符串匹配算法、同态加密、数据挖掘中的关联规则、语义网络等内容，同时更新了配套教辅资源，成为更加实用的教学工具。本书可作为1～2个学期的离散数学课程教材，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。
本书特色
·例题：共800多道例题，用于阐明概念、建立不同主题之间的关联以及介绍实际应用。
·应用：涉及的领域包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网等，展示了离散数学的实用性。
·算法：每一章都介绍了一些关键算法，提供伪代码，并简要分析其计算复杂度。
·历史资料：给出了89位数学家和计算机科学家的简短传记，帮助读者了解不同技术的历史背景和发展轨迹。
·练习、复习题和补充练习：共有4200多道难度各异的练习题，可以满足不同层次学生的需求。此外，还有一些研究性题目，帮助学生通过计算来探索新知识和新想法。
[美]肯尼思·H. 罗森（Kenneth H. Rosen）著：
徐六通 杨娟 吴斌 译：暂无简介
从在路边小摊贩处扫码完成支付到为黑洞拍摄第一张照片，再到各类世纪工程的竣工，这一切进步与奇迹的背后都离不开计算机科学与技术的飞速发展。
如果你也想为将来的奇迹做出自己的贡献，就必须先了解计算是什么、计算机的工作原理是什么、计算机是如何解题的等问题。你需要学习的第一门基础课就是离散数学。什么是离散数学？离散数学是致力于研究离散对象的数学分支。说得更通俗一点，就是利用计算机进行问题求解时，一切问题背后的原理性东西均属于离散数学的范畴，或者说离散数学就是计算机科学的数学语言。
离散数学一直被IEEE-CS和ACM认定为计算机专业最核心的课程，也是我国计算机科学与技术专业的核心基础课程。当你学习这门课程的时候，会发现离散数学为许多计算机专业课程提供了理论基础，尤其是为课程中大量的算法提供了基础。顺便提一下，大家都知道计算机领域的最高奖是图灵奖，但你知道在一个约会场景中寻找稳定匹配的算法是诺奖级的算法吗？有兴趣的读者可以阅读本书3.1节练习65前导文中介绍的延迟接受算法。
本书英文版自出版以来在北美发行超过450 000册，目前已经被翻译成西班牙文、法文、葡萄牙文、希腊文、中文、越南文和韩文等，在世界各地发行数十万册。
第8版对许多内容进行了完善、更新、补充和润色，所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。本书清晰地介绍并展示了离散数学中的概念和技术，行文流畅，通俗易懂。书中包含大量有趣而实用的例子，吸引读者广泛好奇心的推荐读物，以及帮助读者掌握离散数学的概念和技巧的丰富练习题，为计算机科学学生将来的学习提供了一切必需的数学基础。此外，本书还提供了一个非常有价值的网站资源——在线学习中心（OLC），帮助学生评估自身学习状况，学习撰写证明并避免常见错误，从各个方面提高学生学习和实际解决问题的能力，引领学生探索离散数学的新应用。
本书的另一个特色是给出了89位数学家和计算机科学家的简短传记，介绍他们的生活、事业以及对离散数学做出的重要贡献。让读者了解数学知识的来龙去脉，可以极大地提高读者学习离散数学的兴趣并使读者理解其发展历程。这一版新增的传记包括在孪生素数猜想研究中做出重要贡献的华裔数学家张益唐。
本次更新还包括离散数学领域的新发展，比如在密码学一节专门介绍了利用同态加密技术实现数据在加密状态下的直接运算，使得对加密数据所做运算的结果和解密数据做运算后再加密的结果是一样的。将该技术用于云计算场景时，可以保证数据始终处于加密状态。
在本次翻译工作中，徐六通翻译全书前言、第1章至第4章、附录及推荐读物，吴斌翻译第5章至第8章，杨娟翻译第9章至第13章。由于译者水平所限，尽管已经修正了之前版本中的一些错误，但是难免还会有不妥的地方，敬请读者不吝赐教。
译者
2019年8月于北京
出版者的话
译者序
前言
在线资源
致学生
作者简介
符号表
第1章 基础：逻辑和证明1
1.1 命题逻辑1
1.1.1 引言1
1.1.2 命题1
1.1.3 条件语句4
1.1.4 复合命题的真值表7
1.1.5 逻辑运算符的优先级8
1.1.6 逻辑运算和比特运算8
练习9
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
练习20
1.3 命题等价式23
1.3.1 引言23
1.3.2 逻辑等价式23
1.3.3 德·摩根律的运用25
1.3.4 构造新的逻辑等价式26
1.3.5 可满足性28
1.3.6 可满足性的应用28
1.3.7 可满足性问题求解30
练习31
1.4 谓词和量词34
1.4.1 引言34
1.4.2 谓词34
1.4.3 量词37
1.4.4 有限域上的量词39
1.4.5 受限域的量词39
1.4.6 量词的优先级40
1.4.7 变量绑定40
1.4.8 涉及量词的逻辑等价式40
1.4.9 量化表达式的否定41
1.4.10 语句到逻辑表达式的翻译42
1.4.11 系统规范说明中量词的使用43
1.4.12 选自路易斯·卡罗尔的例子44
1.4.13 逻辑程序设计45
练习46
1.5 嵌套量词51
1.5.1 引言51
1.5.2 理解涉及嵌套量词的语句51
1.5.3 量词的顺序52
1.5.4 数学语句到嵌套量词语句的翻译53
1.5.5 嵌套量词到自然语言的翻译54
1.5.6 汉语语句到逻辑表达式的翻译54
1.5.7 嵌套量词的否定55
练习56
1.6 推理规则62
1.6.1 引言62
1.6.2 命题逻辑的有效论证62
1.6.3 命题逻辑的推理规则63
1.6.4 使用推理规则建立论证65
1.6.5 消解律66
1.6.6 谬误66
1.6.7 量化命题的推理规则67
1.6.8 命题和量化命题推理规则的组合使用68
练习69
1.7 证明导论72
1.7.1 引言72
1.7.2 一些专用术语72
1.7.3 理解定理是如何陈述的73
1.7.4 证明定理的方法73
1.7.5 直接证明法73
1.7.6 反证法74
1.7.7 归谬证明法76
1.7.8 证明中的错误78
1.7.9 良好的开端79
练习80
1.8 证明的方法和策略81
1.8.1 引言81
1.8.2 穷举证明法和分情形证明法81
1.8.3 存在性证明84
1.8.4 唯一性证明86
1.8.5 证明策略87
1.8.6 寻找反例89
1.8.7 证明策略实践90
1.8.8 拼接90
1.8.9 开放问题的作用92
1.8.10 其他证明方法93
练习94
关键术语和结论96
复习题97
补充练习98
计算机课题100
计算和探索101
写作课题101
第2章 基本结构：集合、函数、序列、求和与矩阵102
2.1 集合102
2.1.1 引言102
2.1.2 文氏图104
2.1.3 子集105
2.1.4 集合的大小106
2.1.5 幂集107
2.1.6 笛卡儿积107
2.1.7 使用带量词的集合符号109
2.1.8 真值集和量词109
练习109
2.2 集合运算112
2.2.1 引言112
2.2.2 集合恒等式114
2.2.3 扩展的并集和交集116
2.2.4 集合的计算机表示117
2.2.5 多重集118
练习119
2.3 函数123
2.3.1 引言123
2.3.2 一对一函数和映上函数125
2.3.3 反函数和函数合成128
2.3.4 函数的图130
2.3.5 一些重要的函数130
2.3.6 部分函数133
练习133
2.4 序列与求和138
2.4.1 引言138
2.4.2 序列138
2.4.3 递推关系139
2.4.4 特殊的整数序列141
2.4.5 求和144
练习147
2.5 集合的基数150
2.5.1 引言150
2.5.2 可数集合151
2.5.3 不可数集合153
练习155
2.6 矩阵157
2.6.1 引言157
2.6.2 矩阵算术158
2.6.3 矩阵的转置和幂159
2.6.4 0-1矩阵160
练习161
关键术语和结论164
复习题166
补充练习166
计算机课题168
计算和探索169
写作课题169
第3章 算法170
3.1 算法170
3.1.1 引言170
3.1.2 搜索算法172
3.1.3 排序174
3.1.4 字符串匹配176
3.1.5 贪婪算法177
3.1.6 停机问题179
练习180
3.2 函数的增长183
3.2.1 引言183
3.2.2 大O记号184
3.2.3 一些重要函数的大O估算187
3.2.4 函数组合的增长190
3.2.5 大Ω与大Θ记号191
练习192
3.3 算法的复杂度196
3.3.1 引言196
3.3.2 时间复杂度196
3.3.3 矩阵乘法的复杂度198
3.3.4 算法范型199
3.3.5 理解算法的复杂度201
练习203
关键术语和结论207
复习题208
补充练习209
计算机课题211
计算和探索211
写作课题212
第4章 数论和密码学213
4.1 整除性和模算术213
4.1.1 引言213
4.1.2 除法213
4.1.3 除法算法214
4.1.4 模算术215
4.1.5 模m算术217
练习218
4.2 整数表示和算法220
4.2.1 引言220
4.2.2 整数表示220
4.2.3 整数运算算法223
4.2.4 模指数运算225
练习226
4.3 素数和最大公约数229
4.3.1 引言229
4.3.2 素数229
4.3.3 试除法230
4.3.4 埃拉托斯特尼筛法231
4.3.5 关于素数的猜想和开放问题235
4.3.6 最大公约数和最小公倍数236
4.3.7 欧几里得算法238
4.3.8 gcd的线性组合表示239
练习242
4.4 求解同余方程245
4.4.1 引言245
4.4.2 线性同余方程245
4.4.3 中国剩余定理247
4.4.4 大整数的计算机算术248
4.4.5 费马小定理249
4.4.6 伪素数250
4.4.7 原根和离散对数251
练习252
4.5 同余的应用255
4.5.1 散列函数255
4.5.2 伪随机数256
4.5.3 校验码257
练习259
4.6 密码学260
4.6.1 引言260
4.6.2 古典密码学261
4.6.3 公钥密码学263
4.6.4 RSA密码系统265
4.6.5 RSA加密265
4.6.6 RSA解密266
4.6.7 用RSA作为公钥系统266
4.6.8 密码协议267
4.6.9 同态加密268
练习269
关键术语和结论271
复习题273
补充练习273
计算机课题275
计算和探索276
写作课题276
第5章 归纳与递归278
5.1 数学归纳法278
5.1.1 引言278
5.1.2 数学归纳法279
5.1.3 为什么数学归纳法是有效的280
5.1.4 选择正确的基础步骤280
5.1.5 运用数学归纳法进行证明的原则281
5.1.6 数学归纳法的优点与缺点281
5.1.7 利用数学归纳法证明的例子281
5.1.8 使用数学归纳法时犯的错误290
练习291
5.2 强归纳法与良序性296
5.2.1 引言296
5.2.2 强归纳法296
5.2.3 利用强归纳法证明的例子298
5.2.4 计算几何学中使用强归纳法300
5.2.5 利用良序性证明302
练习302
5.3 递归定义与结构归纳法306
5.3.1 引言306
5.3.2 递归地定义函数307
5.3.3 递归地定义集合与结构309
5.3.4 结构归纳法312
5.3.5 广义归纳法315
练习315
5.4 递归算法320
5.4.1 引言320
5.4.2 证明递归算法的正确性322
5.4.3 递归与迭代323
5.4.4 归并排序324
练习327
5.5 程序正确性329
5.5.1 引言329
5.5.2 程序验证329
5.5.3 推理规则330
5.5.4 条件语句330
5.5.5 循环不变量332
练习333
关键术语和结论334
复习题335
补充练习336
计算机课题340
计算和探索341
写作课题341
第6章 计数342
6.1 计数的基础342
6.1.1 引言342
6.1.2 基本的计数原则342
6.1.3 比较复杂的计数问题346
6.1.4 减法法则（两个集合的容斥原理）347
6.1.5 除法法则349
6.1.6 树图349
练习350
6.2 鸽巢原理354
6.2.1 引言354
6.2.2 广义鸽巢原理355
6.2.3 鸽巢原理的几个简单应用357
练习359
6.3 排列与组合361
6.3.1 引言361
6.3.2 排列361
6.3.3 组合362
练习365
6.4 二项式系数和恒等式367
6.4.1 二项式定理368
6.4.2 帕斯卡恒等式和三角形370
6.4.3 其他的二项式系数
恒等式371
练习372
6.5 排列与组合的推广375
6.5.1 引言375
6.5.2 有重复的排列375
6.5.3 有重复的组合375
6.5.4 具有不可区别物体的集合的排列378
6.5.5 把物体放入盒子379
练习382
6.6 生成排列和组合385
6.6.1 引言385
6.6.2 生成排列385
6.6.3 生成组合386
练习387
关键术语和结论388
复习题389
补充练习390
计算机课题393
计算和探索394
写作课题394
第7章 离散概率395
7.1 离散概率引论395
7.1.1 引言395
7.1.2 有限概率395
7.1.3 事件组合的概率398
7.1.4 概率的推理399
练习399
7.2 概率论402
7.2.1 引言402
7.2.2 概率指派402
7.2.3 事件的组合403
7.2.4 条件概率404
7.2.5 独立性405
7.2.6 伯努利试验与二项分布406
7.2.7 随机变量407
7.2.8 生日问题408
7.2.9 蒙特卡罗算法409
7.2.10 概率方法411
练习412
7.3 贝叶斯定理414
7.3.1 引言414
7.3.2 贝叶斯定理415
7.3.3 贝叶斯垃圾邮件过滤器417
练习420
7.4 期望值和方差422
7.4.1 引言422
7.4.2 期望值422
7.4.3 期望的线性性质424
7.4.4 平均情形下的计算复杂度425
7.4.5 几何分布427
7.4.6 独立随机变量428
7.4.7 方差429
7.4.8 切比雪夫不等式431
练习433
关键术语和结论435
复习题436
补充练习437
计算机课题440
计算和探索441
写作课题441
第8章 高级计数技术442
8.1 递推关系的应用442
8.1.1 引言442
8.1.2 用递推关系构造模型443
8.1.3 算法与递推关系447
练习450
8.2 求解线性递推关系453
8.2.1 引言453
8.2.2 求解常系数线性齐次递推关系454
8.2.3 求解常系数线性非齐次递推关系458
练习460
8.3 分治算法和递推关系463
8.3.1 引言463
8.3.2 分治递推关系463
练习469
8.4 生成函数471
8.4.1 引言471
8.4.2 关于幂级数的有用事实471
8.4.3 计数问题与生成函数474
8.4.4 使用生成函数求解递推关系477
8.4.5 使用生成函数证明恒等式478
练习479
8.5 容斥484
8.5.1 引言484
8.5.2 容斥原理484
练习487
8.6 容斥原理的应用488
8.6.1 引言488
8.6.2 容斥原理的另一种形式488
8.6.3 埃拉托色尼筛489
8.6.4 映上函数的个数490
8.6.5 错位排列490
练习492
关键术语和结论493
复习题494
补充练习495
计算机课题497
计算和探索498
写作课题498
第9章 关系500 9.1
关系及其性质500
9.1.1 引言500
9.1.2 函数作为关系501
9.1.3 集合的关系501
9.1.4 关系的性质502
9.1.5 关系的组合504
练习506
9.2 n元关系及其应用510
9.2.1 引言510
9.2.2 n元关系510
9.2.3 数据库和关系511
9.2.4 n元关系的运算512
9.2.5 SQL514
9.2.6 数据挖掘中的关联规则514
练习516
9.3 关系的表示518
9.3.1 引言518
9.3.2 用矩阵表示关系518
9.3.3 用图表示关系521
练习522
9.4 关系的闭包524
9.4.1 引言524
9.4.2 不同类型的闭包524
9.4.3 有向图中的路径525
9.4.4 传递闭包526
9.4.5 沃舍尔算法529
练习531
9.5 等价关系533
9.5.1 引言533
9.5.2 等价关系533
9.5.3 等价类534
9.5.4 等价类与划分536
练习538
9.6 偏序542
9.6.1 引言542
9.6.2 字典顺序544
9.6.3 哈塞图545
9.6.4 极大元与极小元546
9.6.5 格548
9.6.6 拓扑排序550
练习551
关键术语和结论556
复习题557
补充练习558
计算机课题561
计算和探索562
写作课题562
第10章 图563
10.1 图和图模型563
10.1.1 图模型565
练习570
10.2 图的术语和几种特殊的图573
10.2.1 引言573
10.2.2 基本术语573
10.2.3 一些特殊的简单图575
10.2.4 二分图576
10.2.5 二分图和匹配577
10.2.6 特殊类型图的一些应用580
10.2.7 从旧图构造新图582
练习584
10.3 图的表示和图的同构587
10.3.1 引言587
10.3.2 图的表示588
10.3.3 邻接矩阵588
10.3.4 关联矩阵590
10.3.5 图的同构590
10.3.6 判定两个简单图是否同构591
练习593
10.4 连通性598
10.4.1 引言598
10.4.2 通路598
10.4.3 无向图的连通性600
10.4.4 图是如何连通的601
10.4.5 有向图的连通性603
10.4.6 通路与同构604
10.4.7 计算顶点之间的通路数605
练习606
10.5 欧拉通路与哈密顿通路611
10.5.1 引言611
10.5.2 欧拉通路与欧拉回路611
10.5.3 哈密顿通路与哈密顿回路615
10.5.4 哈密顿回路的应用618
练习619
10.6 最短通路问题623
10.6.1 引言623
10.6.2 最短通路算法625
10.6.3 旅行商问题629
练习630
10.7 平面图633
10.7.1 引言633
10.7.2 欧拉公式634
10.7.3 库拉图斯基定理637
练习638
10.8 图着色640
10.8.1 引言640
10.8.2 图着色的应用644
练习645
关键术语和结论648
复习题650
补充练习651
计算机课题656
计算和探索656
写作课题657
第11章 树658
11.1 树的概述658
11.1.1 有根树659
11.1.2 树作为模型662
11.1.3 树的性质663
练习666
11.2 树的应用668
11.2.1 引言668
11.2.2 二叉搜索树668
11.2.3 决策树671
11.2.4 前缀码672
11.2.5 博弈树674
练习678
11.3 树的遍历681
11.3.1 引言681
11.3.2 通用地址系统681
11.3.3 遍历算法682
11.3.4 中缀、前缀和后缀记法688
练习690
11.4 生成树693
11.4.1 引言693
11.4.2 深度优先搜索694
11.4.3 宽度优先搜索696
11.4.4 回溯的应用698
11.4.5 有向图中的深度优先搜索700
练习701
11.5 最小生成树704
11.5.1 引言704
11.5.2 最小生成树算法704
练习707
关键术语和结论709
复习题710
补充练习711
计算机课题714
计算和探索714
写作课题715
第12章 布尔代数716
12.1 布尔函数716
12.1.1 引言716
12.1.2 布尔表达式和布尔函数717
12.1.3 布尔代数恒等式718
12.1.4 对偶性720
12.1.5 布尔代数的抽象定义720
练习721
12.2 布尔函数的表示722
12.2.1 积之和展开式723
12.2.2 函数完备性724
练习724
12.3 逻辑门电路725
12.3.1 引言725
12.3.2 门的组合726
12.3.3 电路的例子726
12.3.4 加法器728
练习729
12.4 电路的极小化731
12.4.1 引言731
12.4.2 卡诺图732
12.4.3 无须在意的条件737
12.4.4 奎因-莫可拉斯基方法737
练习741
关键术语和结论743
复习题744
补充练习744
计算机课题746
计算和探索746
写作课题747
第13章 计算模型748
13.1 语言和文法748
13.1.1 引言748
13.1.2 短语结构文法749
13.1.3 短语结构文法的类型751
13.1.4 派生树752
13.1.5 巴克斯-诺尔范式754
练习755
13.2 带输出的有限状态机758
13.2.1 引言758
13.2.2 带输出的有限状态机759
练习762
13.3 不带输出的有限状态机764
13.3.1 引言764
13.3.2 串的集合764
13.3.3 有限状态自动机765
13.3.4 有限状态机的语言识别766
13.3.5 非确定性的有限状态自动机771
练习773
13.4 语言的识别777
13.4.1 引言777
13.4.2 克莱因定理778
13.4.3 正则集合和正则文法781
13.4.4 一个不能由有限状态自动机识别的集合783
13.4.5 一些更强大的机器783
练习784
13.5 图灵机786
13.5.1 引言786
13.5.2 图灵机的定义787
13.5.3 用图灵机识别集合789
13.5.4 用图灵机计算函数790
13.5.5 不同类型的图灵机790
13.5.6 丘奇-图灵论题791
13.5.7 计算复杂度、可计算性和可判定性791
练习794
关键术语和结论796
复习题797
补充练习798
计算机课题800
计算和探索800
写作课题800
附录A 实数和正整数的公理802
附录B 指数与对数函数807
附录C 伪代码809
推荐读物813
参考文献817
奇数编号练习答案
请访问华章网站www.hzbook.com下载。
