人的思维方式有两种，形象思维与抽象思维。形象思维是最简单的思维方式，它借助实物形象进行推理，以脑内形成事物的具体表征为特征。抽象思维凭借抽象概念对事物的本质和客观世界发展的深远过程进行反映，使人们通过认识活动获得远远超出靠感觉器官直接感知的知识。抽象是在对事物的本质属性进行分析、综合、比较的基础上，抽取出事物的本质属性。抽象思维深刻地反映着外部世界，使人能在认识客观规律的基础上科学地预见事物和现象的发展趋势。

    在大学生涯中，有一个重要的能力需要培养，就是将具体的问题转为抽象的表示，并采用抽象结构进行推理，求出结果。本书介绍辅助培养这种技能的诸多数学工具，主要内容有如下几部分：

第一部分内容包括第1章～第4章，介绍定性类的工具：

 第1章系统讲述集合的概念，作为后续学习的铺垫。

 第2章介绍关系的基本概念以及分类和排序这两种重要应用，关系在计算机科学中非常重要，既可作为分析工具又可用来表示计算结构。本章介绍关系的基本概念，本章内容是后续学习的基础。

 第3章讲解函数，它广泛存在于数学与计算机科学之中。

 第4章阐述归纳与递归，归纳与递归的基本概念不仅可以应用在数值领域内，而且，可以扩展到结构、进程和各种各样的过程之中。

第二部分内容包括第5章～第9章，介绍定量类的工具：

 第5章讲解组合学的内容，首先介绍两条基本原理：加法原理和乘法原理，然后讲解4种基本选择方法，给出算术公式，并且进行实际应用。最后说明如何计算集合的重排和划分。

 第6章介绍概率。此处只考虑离散情况，也就是有限域，而不考虑无穷域。

 第7章介绍了计算机科学中常见的数据结构--树。   第8章介绍了逻辑的纯结构部分，并阐述命题逻辑。

致 学 生

对于刚刚结束高中生活进入大学的计算机专业学生来说，也许并不喜欢数学，但在第一年的学习中，数学是必不可少的基础课程。本书由此入手，介绍计算机、信息科学中涉及到的基本数学知识。

篇幅所限，本书尚未涵盖大学学习中需要用到的所有数学知识。这方面优秀的书籍还有很多，同学们可以根据需要进行选择。但实践已经证实，不管概括归纳得多么精彩，初学者还是会感到无从下手。本书针对初学者，从基础理论出发，为今后的深入学习奠定基础。

考虑到同学们以前的数学基础和学习兴趣等问题，在本书的学习过程中，重在温习基础知识，培养学习兴趣。

本书介绍的内容多是计算中经常用到的知识，包括以下内容：

 归纳多个元素，在数学术语中称为集合；

 不同元素之间的对比，即关系式；

 将一个元素与其他元素相关联，即函数；

 循环输出作为输入，即归纳与递归；

 计算，数学术语为组合学；

 权衡可能性，这一方法用于处理概率；

 存储数学，学习树图的运用；

 肯定与否定，以“何者为真”为基础的命题逻辑；

 全部与零，即数量逻辑。

坦白地说，如果没有数学基础，对于计算机科学的认识只能停留在茫然的阶段，根本不可能写出有创造性的计算程序。而一旦掌握数学知识，即可发现，在计算机之外的领域，这些知识也大有裨益。

计算机数学前  言数学不像其他学科比如药学、法律那样，有大量的内容需要记忆，数学学习中最重要的是理解和运用。

数学远比想象的微妙。理解与运用相互依存。没有理解的运用是盲目的，将导致可怕的错误，而没有经过运用检验的理解是靠不住的。尤其是，如果没有看到一个定义在特定环境是如何起作用的，就不能说是真正理解了这一定义：正面的实例表明了适用范围，反面的实例揭示了局限性。检验是否真正理解需要一定的时间。

因而，在学习过程中，练习必不可少，正如谚语所说“数学王国里没有为国王铺设的大道”。本书中包含了大量的思考题，有些题目书中已经给出了完整的解答范例。值得一提的是：无论一个概念看上去有多么简单和直接，如果不通过练习，根本无法完全掌握。因而，对于书中已经给出答案的练习题目，最好的方法是将答案盖住，自己先做一做。这需要自律和耐心，但必定受益匪浅。

此外，练习题目是从众多题目中选出的，很多题目的结果是后续章节的铺垫，都是整个理论不可或缺的组成部分。

出于同样原因，读书时不要养成省去实例论证的习惯。在数学中，除非已经掌握了为何如此，否则都不算是真正的理解，实例是对理论的一个论证。一些国家所认同的数学抛开论证，通过事实教学并普及的观念将会给近期高中乃至大学教育带来不小的麻烦。

实际上，本书所涉及到的数学工具都不是孤立的。只有将这些工具结合起来，融会贯通，在遇到问题的时候才能迎刃而解。第1章介绍的集合概念将会运用到之后几乎所有的章节中；关系式则同样会出现在图表与树图的章节中；在组合学和概率，尤其是函数中，将包含最常见的加法、乘法等算术运算。

致 教 师

此类书籍不可避免地要寻求二者之间的平衡：数学的固有属性以及直觉。掌握算术的最佳途径是从一般理论开始，顺其自然。教育只在某些前提下起作用，同时也有可能带来麻烦。很多情况下需要逆向思维，比如从一些特例出发，推及更广的范围。

所有问题都没有最完美的解决方法，只能剔除最不适宜的方法。本书采用集合、关系式、函数这样的顺序来编排，遵循了一般理论，但在一些章节中也不得不采用逆向思： 比如，在介绍归纳与递归的时候，由简单的正整数归纳/递归开始，过渡到同一定义域的附加形式，再拓展到定性的结构式形式，最后通过一般性的集合呈现出来；又如在介绍树图的章节中，从依赖直觉的有根树开始，抽象出无根树。

在介绍算法和概率的章节中，需要掌握另外的平衡--传统术语学与前现代符号的平衡，并将其用集合、关系式、函数表述出来。大部分教科书都按照传统理论来阐述所有内容，其中存在着一定的不足：学生难以理解此处同前面所讲的集合、关系式、函数的关系。坦白地说，这种关系并不十分严格和显而易见。本书将帮助读者熟悉两种不同的表述方式，通过集合、函数等语言将其阐述清楚，传统的组合数学和概率可用于术语的沟通。

逻辑在推理数学中非常微妙，本书安排在最后对其进行系统讲解。尽管读者对于逻辑的运用贯穿于整个推理数学，即便是在前3章--集合、关系式、函数这类基本概念中也要用到，但根据作者多年的教学经验，过早地讲解逻辑，效果并不理想。逻辑对于初学者来说难以理解，只能通过实际运用来理解，并且，只有掌握了一定的集合、关系式、函数及树图的知识，才能对逻辑的概念给出清晰的阐述。

因而，本书采取与以往不同的顺序进行编排，在最初的章节中，逻辑只出现在具体实例的讨论中，而且只进行了简单描述。其以“逻辑框”的形式出现，每个逻辑框仅涉及到解决本节问题需要用到的知识。最后两章系统讲解逻辑，读者将更容易理解。

拜刘易斯·卡罗尔所赐，有时会出现“爱丽丝专栏”用以讨论一些难题。有时，这些问题会令学生烦恼，但是他们却不能清楚地表述出来，或者羞于启齿。事实上，数学和逻辑体系的建构是“殊途同归”，有时，不同的途径之间会产生冲突。此类冲突经常出现在定量逻辑中--采用不同的方式理解量词，甚至是采用不同的方式表述“真”与“伪”，其他章节中也有论述。哈特的回答在此处可能有所帮助。

总地来说，本书的编排内容符合标准，用于课堂教学时可以省略第5章至第9章，或者第4章的后半部分至第9章，但第1章至第3章则需完整地讲授。有些教师可能希望能够增加一些更深入的内容，受篇幅所限本书未涉及的内容，教师可根据自己的经验进行补充。

本书没有专门讲述图表的章节，有以下几方面的原因。尽管树是图的一种特殊形式，但在不阐述总体理论的前提下并不影响对树的全面讲述。而且，如果安排一章或长度相当的内容介绍图表，在课堂教学中至少需要两周的讲授时间；图表所包含的内容十分复杂，还要涉及到所选的范围（含有循环的图表、不含循环的图表、多边图表及直接图表与间接图表的划分），涉及到的定义、定理过多。根据作者的经验，这些定义、定理对学生的帮助不大，极有可能演变成为了应付考试而机械记忆，而后迅速遗忘。

对于是否介绍特殊运算法则本书也进行了充分的考虑，采用何种方式介绍：英语、虚拟符号或者实在的程序语言？总地来说，本书尽可能地采用开放方式。原则上计算机专业一年级的课程内容应该包括编程的基本规则及特定的程序语言，而程序语言的选择应视情况而定。本书在遵从一般运算法则的前提下尽量采用严密的语言。部分练习题采用了虚拟符号，比如讲述树图的章节。有些教师倾向于系统地运用虚拟符号，或者将内容与特定的程序语言相结合，均可自行安排。

致  谢

在此感谢Anatoli Degtyarev、Franz Dietrich、Valentin Goranko及George Kourousias在本书写作过程中给予的大力协助，特别感谢George为本书图表所做的工作。同时也感谢伦敦经济学校，尤其是校领导Colin Howson和Richard Bradley为本书编写过程中提供的良好工作环境。

第1章 集合1

  1.1 集合的直观概念1

  1.2 集合的基本关系2

1.2.1 包含关系2

1.2.2 相等关系3

1.2.3 真包含4

1.2.4 欧拉图4

1.2.5 维恩图5

1.2.6 集合的定义6

  1.3 空集8

1.3.1 空集的概念8

1.3.2 不相交集9

  1.4 集合上的布尔运算10

1.4.1 交集10

1.4.2 并集11

1.4.3 差集与补集14

  1.5 广义并集与广义交集16

  1.6 幂集18

  1.7 部分重要的数字集合20

第2章 关系23

  2.1 序偶、笛卡尔积和关系23

2.1.1 序偶23

2.1.2 笛卡尔积25目  录     2.1.3 关系27

  2.2 关系表和关系图29

2.2.1 关系表29

2.2.2 关系图30

  2.3 关系运算31

2.3.1 逆运算31

2.3.2 关系并运算32

2.3.3 关系的合运算33

2.3.4 象/象集36

  2.4 自反性与传递性37

2.4.1 自反性37

2.4.2 传递性38

  2.5 等价关系与划分39

2.5.1 对称39

2.5.2 等价关系40

2.5.3 划分41

2.5.4 划分与等价关系之间的对应43

  2.6 顺序相关关系44

2.6.1 偏序44

2.6.2 线性有序45

2.6.3 严格有序46

  2.7 关系的闭合48

2.7.1 关系传递闭包48

2.7.2 关系条件下集合闭包49

第3章 函数53

  3.1 何为函数53

  3.2 函数运算55

3.2.1 定义域与值域55

3.2.2 象、限制与闭包56

3.2.3 合成58

3.2.4 逆59

  3.3 单射、满射与双射60

3.3.1 单射60

3.3.2 满射61

3.3.3 双射函数62

  3.4 应用函数比较大小63

3.4.1 等量原理63

3.4.2 比较原理64

3.4.3 归档原理65

  3.5 常用函数67

3.5.1 恒等函数67

3.5.2 常（值）函数67

3.5.3 投影函数68

3.5.4 特征函数68

3.5.5 集合族68

3.5.6 序列69

第4章 归纳与递归73

  4.1 归纳与递归73

  4.2 应用正整数的简单归纳进行证明74

4.2.1 实例74

4.2.2 隐藏在实例后的原理75

  4.3 应用自然数的简单递归进行定义78

  4.4 预测递归定义的函数80

  4.5 累积归纳和递归81

4.5.1 返回多单元的递归式定义81

4.5.2 应用累积归纳进行证明83

4.5.3 同时归纳与递归84

  4.6 结构递归与归纳86

4.6.1 结构递归法定义集合86

4.6.2 应用结构归纳法进行证明89

4.6.3 应用结构递归法在定义域上定义函数90

4.6.4 结构递归法进行函数定义的条件91

4.6.5 何时唯一分解条件失效93

  4.7 良基集上的归纳与递归94

4.7.1 良基集94

4.7.2 应用良基归纳法进行证明时的定理95

4.7.3 应用良基递归法在定义域上定义函数97

  4.8 递归程序98

第5章 组合学102

  5.1 两条基本原理: 加法和乘法102

  5.2 两条基本原理的联合运用105

  5.3 从n个对象中选出k个项目的4种方法106

  5.4 排列与组合的计算公式110

5.4.1 排列的计算公式(O＋R-)111

5.4.2 组合的计算公式(O-R-)112

  5.5 有重排列与有重组合的计算公式116

5.5.1 有重排列计算公式(O＋R＋)116

5.5.2 有重组合计算公式(O-R＋)117

  5.6 重排及划分119

5.6.1 重排119

5.6.2 给定数字格局下的划分计算121

第6章 概率126

  6.1 有限概率空间126

6.1.1 基本定义126

6.1.2 概率函数的性质128

  6.2 基本哲学原理及应用130

  6.3 一些简单问题132

  6.4 条件概率135

  6.5 插曲之辛普森悖论141

  6.6 独立性142

  6.7 贝叶斯定理145

  6.8 随机变量与期望值147

6.8.1 随机变量148

6.8.2 期望值148

6.8.3 诱导概率分布150

6.8.4 采用诱导概率函数表示期望值151

第7章 存储数学： 树156

  7.1 第一棵树156

  7.2 有根树158

  7.3 标记树164

  7.4 插曲: 无括号表示法167

  7.5 二叉查找树168

  7.6 无根树173

7.6.1 无根树的定义173

7.6.2 无根树的性质174

7.6.3 寻找生成树177

第8章 命题逻辑180

  8.1 何为逻辑180

  8.2 结果的结构特征181

  8.3 真值函数连接词185

  8.4 同义反复188

8.4.1 命题逻辑语言189

8.4.2 赋值（分配）与赋值函数189

8.4.3 永真蕴含（重复蕴含）190

8.4.4 重复等价（同义反复等价）192

8.4.5 永真式与永假式（矛盾）195

  8.5 标准型（范式）、最小字母集与最大模块性198

8.5.1 析取范式198

8.5.2 合取范式201

8.5.3 去除冗余字母（文字）202

8.5.4 最大模表示204

  8.6 语义分解树206

  8.7 自然演绎210

8.7.1 约束210

8.7.2 二级（亦称间接）推理212

第9章 量化逻辑221

  9.1 量词语言221

9.1.1 实例221

9.1.2 语言的系统表述223

9.1.3 自由与约束227

  9.2 基本的逻辑等价228

  9.3 量化逻辑的语义学230

9.3.1 解释231

9.3.2 在解释下评价条件231

9.3.3 在解释下评价公式的初始条件232

9.3.4 在解释下评价公式的递归步骤232

9.3.5 量词的x-变体解释232

9.3.6 量词的替代解释235

  9.4 逻辑结论237

  9.5 带有量词的自然演绎/推理243