:计算机数学基础

内容简介

本书是作者之一梅内尔教授（(Christoph Meinel）在德国特里尔大学任教为计算机科学专业及经济信息学专业第一学期的学生设计的课程。该课程的主要目的是为学生提供专业的数学知识和技能，以便他们可以获得计算机科学及其相关专业所必需的数学基础。

前言序言

在本书的第 6版中，我们增加了“词汇索引”。同时，该版本还进行了电子书版本的更新。此外，我们对书中存在的错误和不一致的内容进行了进一步的修订。对此，我们对广大热心读者给予的帮助致以诚挚的感谢。 

Christoph Meinel 

Martin Mundhenk 

2015年 5月，波茨坦 /耶拿

第1版前言

本书是作者之一迈内尔教授 (Christoph Meinel)在德国特里尔大学任教时，为计算机科学专业及经济信息学专业第一学期的学生设计的全新课程。该课程的主要目的是为学生提供专业的数学知识和技能，以便他们可以掌握计算机科学及其相关专业所必需的数学基础。在完成本课程后，学生应该具备使用准确严格的数学逻辑方法来有条理地表达自己思维过程所必需的逻辑性，而这种逻辑性是从事计算机科学等信息技术相关工作不可缺少的。与其他数学课程不同的是，在本课程中，读者从开始阶段就会接触到抽象数学的思维逻辑。对于这一点，读者需要谨慎对待，认识到数学的难点有时是从一开始就会出现的。因此，本书的第一部分使用了一种非正式的“叙事”方式来介绍命题逻辑和集合论的相关概念。希望能够帮助读者在开始阶段就形成对精确的数学描述及论证一种形象的理解。该部分也会论述数学定理证明的重要性，并且通过讨论关系和映射等概念进行系统的数学思维的演练。接下来，本书的第二部分将给出计算机科学中会用到的重要数学证明技巧。例如，通过随机理论的一些应用介绍组合学中的完整归纳法、计数法等。最后，本书的第三部分将讨论一些基本的离散结构知识，例如，图论、布尔代数等。本书的最后一章将使用精确的数学思维逻辑的方法来重新阐述那些在前面几章中用非正式方式介绍过的螺旋式术语。那时，读者将已经具备了更为准确的数学直觉，其数据思维也会达到一个更高的境界，有能力在数学的海洋中不断前行。我们由衷希望这本书可以弥补广大学生或其他对计算机科学感兴趣的读者在学习过程中遇到的专用数学教材不足的缺憾，为他们能够更进一步地学习数学减少障碍。在此，我们非常感谢在本书内容教授的过程中，特里尔大学计算机科学系的学生们提出了许多建设性意见。有时候甚至是一些误解促进了我们重新思考教材的内容修订和展示风格。而我们与特里尔大学计算机科学系的同仁们都持有一个共同的观点，那就是扎实的数学基础是计算机科学以及经济信息学的必要条件。最后，我们要感谢 Jochen Bern、Benjamin Boelter、Carsten Damm、Lilo Herbst、Lothar Jost和 Harald Sack在本书插图和校对等工作上给予的大力支持。 

Christoph Meinel 

Martin Mundhenk 

2000年 2月，特里尔

目录

第1章绪论 1

第一部分数学基础知识

第2章命题 7 

21定义和举例 7 

22命题联结词 8 

23重言式和矛盾式  13 

24命题形式化  17 

25命题的量化  18

第3章集合和集合运算 21 

31集合  21 

32集合相等  23 

33补集  25 

34空集  26 

35子集和超集  27 

36幂集和集合族  28 

37集合的交集、并集和补集  30 

38笛卡儿积  34 

39集合运算的其他基本规律  37

第4章数学证明 39

第5章关系  43 

51定义和举例  43 

52关系运算  47 

53关系的重要性质  50 

54等价关系与划分  52 

计算机数学基础 (第6版) 

55等价关系的运算  57 

56偏序关系  61

第6章映射与函数  65 

61定义及第一个例子  65 

62满射、单射和双射  69 

63序列和集合族  74 

64集合的基数  77 

65参考资料  80

第二部分技术支持

第7章数学证明方法  85 

71直接证明法  85 

72换质位法证明  87 

73反证法  88 

74等价证明  89 

75原子命题证明  90 

76个案分析证明  92 

77带量词的命题证明  93 

78组合证明  96

第8章完全归纳法  100 

81完全归纳法的思路  101 

82归纳证明举例  101 

83归纳证明的结构  104 

84广义完全归纳法  106 

85归纳定义  107

第9章组合计数 116 

91基本计数原则  116 

92排列和二项式系数  121 

93计算二项式系数  125

第10章离散概率论  133 

101随机试验和概率  133 

102条件概率  141 

103随机□量  143 

目录 

104二项分布和几何分布  149 

105参考资料  153

第三部分数学结构

第11章布尔代数 157 

111布尔函数及其表达形式  157 

112布尔代数的定义  163 

113布尔代数示例  164 

114布尔代数的性质  170 

115布尔代数中的偏序  174 

116布尔代数的原子  176 

117布尔表达式的规范形式  180 

118□□化布尔表达式  182 

119同构基本定理  184 

1110电路代数  188

第12章图和树  193 

121基本概念  194 

122图中的通路和回路  199 

123图和矩阵  203 

124图同构  210 

125树  212

第13章命题逻辑 218 

131布尔代数和命题逻辑  218 

132范式  223 

133可满足性等价公式  225 

134不可满足的子句集合  229 

135霍恩子句的可满足性  232 

136归结原理  235 

137 2KNF中的子句集  242

第14章模算术  245 

141因数关系  246 

142模的加法和乘法  249 

143模运算  253 

计算机数学基础 (第6版) 

144□□公因数和欧几里得算法  257 

145费马小定理  261 

146使用费马小定理的加密  265 

147 RSA加密算法  270 

148参考资料  272 

作者简介

梅内尔（Christoph Meinel）德国特里尔大学教授，本书是为计算机科学专业及经济信息学专业第一学期的学生设计的课程。