目录：  

第I部分　数学证明

引言3

0.1　参考文献4

第1章　什么是证明5

1.1　命题5

1.2  谓词8

1.3  公理化方法8

1.4　我们的公理9

1.4.1　逻辑推理9

1.4.2　证明的模式10

1.5　证明蕴涵10

1.5.1　方法#111

1.5.2　方法#2：证明逆反命题12

1.6  证明“当且仅当”13

1.6.1  方法#1：证明两个语句相互蕴涵13

1.6.2  方法#2：构建iff链13

1.7　案例证明法14

1.8  反证法15

1.9  数学证明的优秀实践16

1.10  参考文献18

1.1节习题18

1.5节习题21

1.7节习题21

1.8节习题23

第2章　良序原理26

2.1　良序证明26

2.2  良序证明模板27

2.2.1  整数求和27

2.3　质因数分解29

2.4　良序集合29

2.4.1　不一样的良序集合（选学）30

2.2节习题31

2.4节习题38

第3章  逻辑公式40

3.1  命题的命题41

3.1.1  NOT，AND和OR41

3.1.2  当且仅当42

3.1.3  IMPLIES42

3.2  计算机程序的命题逻辑44

3.2.1  真值表计算45

3.2.2  符号表示46

3.3  等价性和有效性47

3.3.1  蕴涵和逆否47

3.3.2  永真性和可满足性48

3.4  命题代数49

3.4.1  命题范式49

3.4.2  等价性证明50

3.5  SAT问题53

3.6  谓词公式54

3.6.1  量词54

3.6.2  混合量词55

3.6.3  量词的顺序56

3.6.4  变量与域56

3.6.5  否定量词57

3.6.6  谓词公式的永真性57

3.7  参考文献58

3.1节习题59

3.2节习题61

3.3节习题65

3.4节习题68

3.5节习题69

3.6节习题71

第4章  数学数据类型79

4.1  集合79

4.1.1  常用集合80

4.1.2  集合的比较和组合80

4.1.3  幂集81

4.1.4  集合构造器标记82

4.1.5  证明集合相等82

4.2  序列83

4.3  函数84

4.3.1  域和像84

4.3.2  函数复合86

4.4  二元关系86

4.4.1  关系图87

4.4.2  关系的像89

4.5  有限基数90

4.5.1  有限集有多少个子集91

4.1节习题92

4.2节习题96

4.4节习题97

4.5节习题105

第5章  归纳法107

5.1  一般归纳法107

5.1.1  一般归纳法的规则108

5.1.2  举例说明108

5.1.3  归纳法证明的模板109

5.1.4  一般归纳法的简洁写法110

5.1.5  更复杂的例子111

5.1.6  错误的归纳证明113

5.2  强归纳法115

5.2.1  强归纳法的规则115

5.2.2  斐波那契数列116

5.2.3  质数的乘积117

5.2.4  找零问题118

5.2.5  堆盒子游戏119

5.3  强归纳法、一般归纳法和良序法的比较120

5.1节习题121

5.2节习题131

第6章　状态机136

6.1  状态和转移136

6.2  不变性原理137

6.2.1  沿对角线移动的机器人137

6.2.2  不变性原理的定义139

6.2.3  示例：《虎胆龙威》141

6.3  偏序正确性和终止性143

6.3.1  快速求幂143

6.3.2  派生变量145

6.3.3  基于良序集合的终止性（选学）146

6.3.4  东南方向跳跃的机器人（选学）146

6.4  稳定的婚姻147

6.4.1  配对仪式148

6.4.2  我们结婚吧150

6.4.3  他们从此幸福地生活在一起150

6.4.4  竟然是男性……151

6.4.5  应用152

6.3节习题153

6.4节习题165

第7章  递归数据类型172

7.1  递归定义和结构归纳法172

7.1.1  结构归纳法174

7.2  匹配带括号的字符串175

7.3  非负整数上的递归函数179

7.3.1  N上的一些标准递归函数179

7.3.2  不规范的函数定义179

7.4  算术表达式181

7.4.1  Aexp的替换和求值181

7.5  计算机科学中的归纳185

7.1节习题185

7.2节习题193

7.3节习题201

7.4节习题202

第8章  无限集206

8.1  无限基数集206

8.1.1  不同之处209

8.1.2  可数集209

8.1.3  幂集的势严格大于原集合211

8.1.4  对角线证明213

8.2  停止问题214

8.3  集合逻辑217

8.3.1  罗素悖论217

8.3.2  集合的ZFC公理系统218

8.3.3  避免罗素悖论220

8.4  这些真的有效吗220

8.4.1  计算机科学中的无穷大221

8.1节习题221

8.2节习题228

8.3节习题233

8.4节习题236

第Ⅱ部分　结构

引言241

第9章　数论242

9.1  整除242

9.1.1  整除的性质243

9.1.2  不可整除问题244

9.1.3  虎胆龙威245

9.2  *大公约数247

9.2.1  欧几里得算法247

9.2.2  粉碎机249

9.2.3  水壶问题的通解251

9.2.4  *大公约数的性质252

9.3  质数的奥秘253

9.4  算术基本定理255

9.4.1  **分解定理的证明256

9.5  阿兰·图灵257

9.5.1  图灵编码（1.0版）258

9.5.2  破解图灵编码（1.0版）260

9.6  模运算260

9.7  余运算262

9.7.1  环Z_n264

9.8  图灵编码（2.0版）265

9.9  倒数与约去266

9.9.1  互质267

9.9.2  约去268

9.9.3  解密（2.0版）268

9.9.4  破解图灵编码（2.0版）269

9.9.5  图灵后记269

9.10  欧拉定理271

9.10.1  计算欧拉?函数273

9.11  RSA公钥加密274

9.12  SAT与RSA有什么关系276

9.13　参考文献277

9.1节习题277

9.2节习题278

9.3节习题285

9.4节习题285

9.6节习题287

9.7节习题288

9.8节习题293

9.9节习题293

9.10节习题295

9.11节习题303

第10章  有向图和偏序309

10.1  顶点的度311

10.2  路和通路311

10.2.1  查找通路313

10.3  邻接矩阵314

10.3.1  *短路径315

10.4  路关系316

10.4.1  复合关系316

10.5  有向无环图&调度317

10.5.1  调度318

10.5.2  并行任务调度320

10.5.3  Dilworth引理322

10.6  偏序323

10.6.1  DAG中路关系的性质323

10.6.2  严格偏序324

10.6.3  弱偏序325

10.7  用集合包含表示偏序326

10.8  线性序327

10.9  乘积序327

10.10  等价关系328

10.10.1  等价类328

10.11  关系性质的总结329

10.1节习题330

10.2节习题331

10.3节习题334

10.4节习题335

10.5节习题338

10.6节习题