第 1章绪论 在生活中，我们从来不需要数学定理，而只是使用数学定理从其他不属于数学的领域中推导出非数学的定理。 Tractatus logico-philosophicus, 6.211 Ludwig Wittgenstein 本章，我们将给出撰写本书的出发点，并且简要说明书中各个章节将会涉及的主题。 计算机科学作为一门系统的、并且需要尽可能自动处理信息的学科，如果没有数学的思维方式和技术作为基础，那么这门学科将不会存在。无论是算法的制定和分析，还是信息和通信技术系统与设备的构造和理解，数学的方法、抽象模型和形式描述始终起着核心的作用。因此，对数学科学中的概念、思维方式和记录方式的介绍是对那些想要成功设计或者管理计算机信息处理系统和计算机网络，或者进行软件开发，或者希望设计和实现面向未来的应用程序的所有人进行培训的基础部分。 本书面向的是所有想要深入了解计算机科学，并因此需要具备扎实的数学知识和技术的读者。除了中学高年级的那些读者，本书也希望适用于具有中等数学背景的那些读者。因此，本书会在第一部分“数学基础知识”中以非正式的、更具叙述性的风格对命题和集合论的基本数学概念进行介绍。这样做是为了让读者可以对抽象的和基本的术语形成一个更直观的认识，而不会对抽象的数学模式和论证感到茫然。事实上，我们希望读者通过本书的学习可以认识到数学思维和记录方式的更深层含义和目的，并且获得并不总是会轻松得到的学习动力。 在第 2章“命题”中，会向读者开启数理逻辑世界的大门，并开始介绍数学的思维模式。首先会从句子开始介绍。这些句子不是“真的”就是“假的”，即所谓的命题。判断句子是真的还是假的本身通常并不是逻辑问题。相反，逻辑与命题判断的结果有关。其中，涉及检查命题联结、建立真值表和处理那些不需要判断各个组成部分的真实性，并且始终为真（重言式）或者为假（矛盾式）的特殊的命题联结。这里的描述形式对于数学科学（对事实的准确描述非常重要）来说虽然是非正式的，但是这种形式可以有效地开启对数学思维模式的介绍。在这个章节的最后，读者还可以学习到存在量词和全称量词，可以使用带有变量的命题（即所谓的命题公式）来构造句子，这些句子可以是真的，也可以是假的。 在第 3章“集合和集合运算”中，将介绍所有有关数学集合的基本概念。使用的还是非正式的描述和论证，这是为了培养直觉，激发对更精确有效表达形式的渴望。也就 计算机数学基础 (第 6版) 是说，为了引出正式的数学记录方式。与集合概念一起介绍的还有集合联结。其中涉及一些重要的知识点，如数字，以及我们世界中的其他对象，例如，使用集合这种抽象的对象，可以进行正确“计算”。这里有固定的规则，各个操作都需要遵守这些规则，并且确定它们之间的互动。这些规则可以自动化，并且由计算机执行或者检查，然后得出我们无法感知到的关系领域中的结论。 在第 4章“数学证明”中，讨论了数学证明的意义和目的。讨论了使用主张和事实来论证数学以及相关领域的特征的方式方法。在所有科学中，数学思维方式的独一无二性体现在了数学证明中。因此，理解这种数学证明方式，并且能够独立进行证明的能力是所有严肃数学教育的首要目标，也是本书的重点。 在第 5章“关系”中，会讨论关系的概念。首先会对关系进行数学定义，并使用大量的示例进行说明。然后给出有关关系重要性质的命题，并且进行数学证明。读者可以通过这些证明过程，掌握如何借助数学证明来证实问题中断言的有效性。随后详细讨论了偏序关系和等价关系，并且重点介绍了等价类形成的概念。第 6章是本书第一部分的最后一章，讨论了数学及其应用的映射和函数的主要概念。这些概念对于在集合和关系的概念世界中的归类尤为重要。 本书的第一部分介绍了数学的基本概念，通过这些概念将所介绍的抽象概念与可靠的直觉相关联，在激发使用简洁的和正式的数学表达和记录方法的动机之后，本书的第二部分将介绍基本的数学技术支持。首先，在第 7章“数学证明方法”中，会对常用证明方法，如直接证明法、换质位法证明、反证法、个案分析证明等进行分类，并且使用大量短小示例进行演示和实践。随后，使用单独的一章（第 8章）专门介绍“完全归纳法”技术，并且还使用了大量的示例来帮助读者对该技术进行消化理解，而这对于计算机科学来说尤其重要。 由于集合元素的具体性质在数学思维中的重要性，有关集合元素的数量、执行某些构造或者进行特殊选择的可能性数量迅速成为了考虑的重点。例如，要确定计算机算法的最坏情况下的复杂度，必须考虑可能的输入情况的数量。因此，第 9章“组合计数”介绍了确定这些数量的组合技术。其中，包括了很多众所周知的有趣的数学公式，前面介绍过的证明技术正好可以用于这些数学公式的证明。随后，在一个单独的章节（第 10章）“离散概率论”中，计数技术会被用于检测一个随机试验中某个特定事件发生的概率。例如，计数技术在计算机科学的密码加密的安全性评估中起到了重要的作用。与随机变量的概念一起给出介绍的还有对随机试验重要参数的描述，例如，期望值和方差。 本书的第三部分介绍了一些重要的“数学结构”。当来自生命或者自然的情况被简化到其本质的核心后，那么就会进行抽象的数学建模和描述。首先，在第 11章中，我们介绍了“布尔代数”的数学结构，即给出了具有特定性质的三个运算（被称为加法、乘法和负运算）的集合的数学结构。这种结构的布尔代数不仅可以在数学逻辑中找到，而且还可以在人脑功能模型的检查或者在电子电路设计中找到。在本章中，在使用一系列示例展现这种结构的广泛性之后，我们会证明布尔代数的有趣性质，使用运算来定义关系， 第 1章绪论 3 并且使用不同的范式来处理布尔代数元素的统一表示。最后，我们可以使用同构定理将顺序这个概念带入到有限布尔代数的世界中。 在第 12章“图和树”中介绍由基本集、结点、基本集上的关系和边组成的结构。实际上，可以使用图来描述来自企业和社会的日常生活中的大量情况。由图论的案例，我们可以更详细地考虑图形中的路径，并且可以借助二次数方案来描述图，即所谓的矩阵，以及关于同构的基本数学原理。 到了第 13章，我们的数学之旅又转了回来，将回到命题逻辑这个主题上，但是着重点会放到抽象的数学层面上。在检查命题演算时，我们利用其与布尔代数的紧密联系，给出逻辑表达式的范式，并且处理对应的核心问题，即如何尽可能有效地测试数学命题的可满足性。为此，我们介绍了霍恩子句的演算，并且给出了归结原理。 在本书的最后一章第 14章“模算术”中，介绍了信息安全和密码系统的数学基础知识。为此，我们首先回顾有关等价关系的概念，并且特别关注余数类算术。之后引出费马小定理，该定理在十七世纪就已经为安全加密方法奠定了基础。最后，我们介绍了如今每个互联网用户（即使没有意识到）都在使用的 RSA加密算法。 读者在阅读完这本书之后，应该具备了可以成功处理有关数学领域中其他问题的能力，以及理解数学文献中通常水平的能力。例如，关于“有限状态机”用于对有限存储器和计算机芯片的切换过程的建模和检查，或者作为用于描述物理学中的对称性的重要结构的“群”。 第一部分数学基础知识 第 2章命题 在本章中，我们会介绍如何从数学的角度对事务进行精确阐述。这种方式是证明事务共性的一个先决条件。首先，我们会讲解一些基本概念，如命题和命题公式，同时给出思考，人们如何将命题与数理逻辑原则联结起来。 2.1定义和举例 命题就是一个陈述句，并且这个陈述句不是真的，就是假的。命题是科学描述世界的基石。在解答有关原始命题真假的过程中，相关学科的任务是使用其所涉及的数理逻辑和其中存在的命题逻辑来确定复杂的复合命题的真实性。事实上，一个复合命题的真值并不取决于其各个组成部分的具体内容，而是由这些组成部分的命题的真值和它们对应的联结类型决定的。需要注意的是，这里我们描述和刻画的是复杂的离散数学结构。为了确保这些命题联结演算的安全性，我们会从数理逻辑最重要的基本概念开始，以一种非正式形式给出我们的介绍。 A定义 2.1一个命题就是一个陈述句，这个陈述句可以是真的，也可以是假的，但是不会同时既是真的又是假的（即非真即假）。真命题具有的真值记作 T，假命题具有的真值记作 F。 示例 2.1 (1) 命题 “11是一个质数”是一个真命题，这个命题的真值为 T。事实上，自然数 11确实只能被 1和 11这两个因子整除，而这个条件满足质数被定义的属性。 √ (2) 命题“ 2是一个有理数”是一个假命题，因此这个命题具有的真值为 F。事实上可以证明，假设 √ 2是一个有理数，而有理数都可以表达为两个整数之比，这样就很容易产生了矛盾。这个已经被希腊数学家欧几里得证明过的定理相传是由毕达哥拉斯的学生希帕索斯发现的。当时希帕索斯所在的毕达哥拉斯学派认为“万物皆（有理）数”，而希帕索斯却发现了“无限不循环小数”，即无理数的存在。这个发现在当时引起了该学派的巨大恐慌，以至于相传希帕索斯被自己的老师毕达哥拉斯判处淹死的极刑。 (3) 哥德巴赫猜想“任何一个大于 2的偶数，都可以表示为两个质数之和”。这句话显然非真即假，也就是说这是一个命题。那么这个命题的真值是什么呢？直到如今仍然是一个未知数。如果对于无限多个自然数中的每个偶数，都可以表示为两个质数 计算机数学基础 (第 6版) 之和，那么这个命题就是真的。如果可以找出一个例外的偶数，这个偶数不能表示为两个质数之和，那么这个命题就是假的。而由于上面提到的两种情况不可能同时出现，那么就说明哥德巴赫猜想是一个命题。 (4) 费马猜想“当正整数 n> 2时，不存在 x,y,z > 0这样的三个自然数，使得不定式方程 xn + yn = zn成立”同样是一个命题。如果确实不存在三个满足条件的自然数使得不定式方程成立，那么这句话就是真的。而如果确实存在三个满足条件的自然数，那么这句话就是假的。事实上，寻找这个由费马在书本不起眼的空白处提出的命题的真值的过程被认为是过去 350年来最令人兴奋的科学猜想。而费马猜想的最后结论是命题的真值为真，这是由英国数学家安德鲁·怀尔斯（ Andrew John Wiles）在 1995年证明的。有关对这个独特数学难题进行解答历史的详细介绍可以参考 Simon Singh出版的畅销书《费马最后定理》。 (5) 还存在一种情况：一个句子既可以是真的，也可以是假的，那么就可以断定这个句子不是一个命题。现在我们来看罗素悖论（ Russell’s paradox）“这句话是假的”。假设，如果这句话原本表述的内容是真的，那么“这句话是假的”就是假的。但是反过来，如果这句话原本表述的内容是假的，那么“这句话是假的”就是真的。顺便说一下，这个悖论最初流传的形式是“一名理发师要为自己村子里所有不为自己刮胡子的人刮胡子（理发师悖论） ”。罗素使用这个悖论非常简洁地驳斥了数学界中的一个根深蒂固的假设：所有的句子都归属于一个真值。而这个悖论在 20世纪初也触发了基础数学的危机。 2.2命题联结词 通过命题联结词的使用，简单的命题可以被联结成高度复杂的命题（复合命题）。有趣的是，通过这种方式联结而成的命题的真值不再依赖于单个命题的具体内容，而是取决于各个命题的真值以及联结词的种类。对于复合命题真值的决定因素的研究是命题逻辑的主要方向，而命题逻辑是数理逻辑中的一个重要分支。 例如，两个命题： “11是一个质数”和“ √ 2是一个有理数”。这两个命题可以组成一个新的句子：“11是一个质数，并且 √ 2是一个有理数”。事实上，这个新组合还是一个命题，因为这个复合命题基于了一个被验证的事实，即 √ 2不是一个有理数，因此这个命题的真值为假。现在，如果我们将命题 “11是一个质数”联结一个任意的假命题，即通过联结词√ “合取”（与）相联结，那么我们总是会得到一个真值为 F的命题。因此，命题的内容 “ 2是一个有理数”对于复合命题的真值是没有意义的，只有这个命题的真值才是最重要的。 √ 我们也可以将两个单独的命题： “11是一个质数”和“ 2是一个有理数”通过一个联结词“析取”（或）联结起来。那么基于 11确实是质数的事实，这个新的复合命题的真 第 2章命题 9 值就是 T。这里，命题的具体内容也是没有意义的，而只依赖于两个参与命题的真值中是否有一个是真的。 从这个意义上来说，在确定复合命题的真值过程中，一贯普遍的做法是：只需要关注通过命题变量表示的各个组成部分。也就是说，只关心各个单独命题的真值。例如，如 √ 果字母 p代表命题 “11是一个质数”，字母 q代表命题 “ 2是一个有理数”。那么上面描述的由两个命题组成的新的复合命题就可以简化表示为： “p与 q”或者 “p或 q”。这时，新命题的真值只用通过 p和 q的真值就可以推断出来。 为了能够精确地得出复合命题的真值和各个单独命题的真值之间的关联，必须将口语化的联结词，如“与”“或”“非”或者“如果 ······ ,则 ······ ”等使用数学命题逻辑的术语联结词来表示。结合前面提到的命题变量就会得出这样的思路：首先查看作为数学运算的单个联结词，然后从逻辑命题的布尔值中“计算”出复合语句的真值。 我们首先来了解口语化的联结词“与”。 A定义 2.2如果 p和 q是两个命题。那么 “p与 q”（表示为 p ∧ q）也是一个命题，即所谓的（逻辑）合取。当 p和 q两个命题同时为真的时候，命题 (p ∧ q)的真值才为真。 命题 p和 q的真值决定了复合命题 (p ∧ q)的真值。这种决定因素可以用真值表的形式清晰地给出。在真值表中，人们首先列出了命题 p和 q所有可能的真值组合。然后将从各种组合中产生的复合命题 (p ∧ q)的真值填写到表格中。这里，在真值表中的命题 p和 q很像初等数学中的变量，因此被称为可以赋予任何内容的命题变量（命题变项）。 p q (p ∧ q) T T T T F F F T F F F F 上面真值表的四行中，每一行都含有一个命题 p的真值（第一列）和一个命题 q的真值（第二列），以及由此产生的复合命题 (p ∧ q)的真值（第三列）。事实上，真值表可以准确地反映出上述定义中所涉及的规范标准。 现在来看一个命题： “15可以被 3整除，并且 26是一个质数”。为了确定该命题的真值，我们首先来考虑通过“合取”联结词联结起来的两个子命题： “15可以被 3整除”和“26是一个质数”。我们可以很容易地看出：第一个子命题是真值为 T的真命题，而第二个子命题是真值为 F的假命题。这时我们可以从真值表中读取命题 (p ∧ q)的逻辑“与”的真值，即命题 p的值为 T，命题 q的值为 F的那行。在这行中，命题 (p ∧ q)的真值为 F，因此这个命题的真值为 F。 接下来，我们来学习口语化联结词“或”。 A定义 2.3如果 p和 q是两个命题。那么 “p或 q”（表示为 p ∨ q）也是一个命题，即所谓的（逻辑）析取。当命题 p和 q中有一个为真，或者两个都为真的时候，命题 (p ∨ q)为真。 计算机数学基础 (第 6版) 这里，口语化联结词“或”不能与口语中的“不是 ······就是 ······ ”相混淆。命题“15可以被 3整除，或者 29是一个质数”是由两个子命题通过联结词“析取”相联结而成的。其中，两个子命题的真值都为 T，因此复合命题的真值也为真。但是，用口语表达的“不是 15可以被 3整除，就是 29是一个质数”的命题却不是一个真命题。也就是说，当两个子命题 p和 q中有一个是真的，那么“不是 p就是 q”这种表达方式也是真的。当两个子命题都是真的，或者都是假的时候，那么命题“不是 p就是 q”就是假的。相反，当两个子命题都是真的情况下，命题 “p或 q”也是真的。 现在我们将上述定义再次以真值表的形式给出。 p q (p ∨ q) T T T T F T F T T F F F 正如前面提到的那样，简单命题（原子命题）可以进行组合得到新的复杂的命题（复合命题）。例如，我们使用三个简单命题： “15可以被 3整除” “16小于 14”和“26是一个质数”来重新组合成两个新的复合命题： “15可以被 3整除，并且 16小于 14” 和 “16小于 14，或者 26是一个质数” 由这两个新的复合命题还可以衍生出一个更加复杂的复合命题： “（15可以被 3整除，并且 16小于 14） 或者 （16小于 14，或者 26是一个质数） ” 为了更加清晰、无歧义地表示上述复合命题被联结的结构，我们将各个子命题设置在了括号中。因为整个复合命题的真值是由各个子命题的真值决定的，所以我们需要首先确定两个由联结词“或者”（析取）联结的子命题是真还是假。为了确定两个子命题的真值，我们再次来观察这些子命题：第一部分是由一个真子命题和一个假子命题通过联结词“并且”（合取）组成的，那么联结后的命题就是一个假命题。第二部分是由两个假子命题通过联结词“或者”（析取）组成的，那么联结后的命题同样是假命题。因此，由联结词“或者”联结的整个命题也是一个假命题。 如果使用命题变量来替代具体的命题内容（毕竟我们只是对各个单独命题的真值感兴趣），那么上面的由三个简单命题组成的复合命题可以表示为： ((p ∧ q) ∨ (q ∨ r))。为