交互式定理证明与程序开发 Coq归纳构造演算的艺术【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

交互式定理证明与程序开发 Coq归纳构造演算的艺术PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1概述1

1.1表达式、类型和函数1

1.2命题和证明2

1.3命题和类型3

1.4规范说明和已验证的程序4

1.5一个排序的例子4

1.5.1归纳定义4

1.5.2“包含相同元素”的关系5

1.5.3排序程序的规范说明5

1.5.4一个辅助函数6

1.5.5排序函数主程序6

1.6学习Coq7

1.7本书内容8

1.8词法约定9

2类型和表达式11

2.1第一步11

2.1.1项、表达式和类型11

2.1.2解释辖域12

2.1.3类型检查13

2.2游戏规则15

2.2.1简单类型15

2.2.2标识符、环境、上下文16

2.2.3表达式及其类型17

2.2.4自由和约束变元；α-变换24

2.3声明和定义25

2.3.1全局声明和定义25

2.3.2 Section和局部变量26

2.4计算29

2.4.1替换30

2.4.2归约规则30

2.4.3归约序列32

2.4.4可转换性32

2.5类型、大类和类型空间32

2.5.1 Set大类33

2.5.2类型空间34

2.5.3规范说明的定义和声明35

2.6实现规范说明36

3命题和证明39

3.1最小命题逻辑41

3.1.1命题和证明41

3.1.2目标和证明策略42

3.1.3第一个目标制导的证明42

3.2类型规则和证明策略的联系46

3.2.1命题构造规则46

3.2.2推理规则和证明策略47

3.3一个交互式证明的结构51

3.3.1激活目标处理系统51

3.3.2一个交互式证明的当前阶段52

3.3.3取消操作52

3.3.4证明的正常结束52

3.4证明无关性53

3.4.1 Theorem和Definition的分析比较53

3.4.2证明策略有助于构造程序吗54

3.5 Sections和证明55

3.6证明策略的结合56

3.6.1泛证明策略56

3.6.2证明维护问题59

3.7命题逻辑的完备性61

3.7.1一个完备的证明策略集61

3.7.2不可证命题62

3.8其他证明策略62

3.8.1 cut和assert策略62

3.8.2自动证明策略64

3.9一种新的抽象方式65

4依赖积67

4.1依赖类型的优点67

4.1.1对A→B类型的扩展68

4.1.2关于绑定71

4.1.3一种新的构造72

4.2类型规则和依赖积74

4.2.1函数应用的类型规则74

4.2.2关于抽象的类型规则77

4.2.3类型推导80

4.2.4转换规则83

4.2.5依赖积和可转换性次序83

4.3依赖积的表达能力83

4.3.1积的构造规则84

4.3.2依赖类型84

4.3.3多态86

4.3.4 Coq系统中的相等性90

4.3.5高阶类型91

5常用逻辑95

5.1依赖积的实用方面95

5.1.1 exact和assumption95

5.1.2 intro策略96

5.1.3 apply策略98

5.1.4 unfold策略104

5.2逻辑联结词105

5.2.1引入和消去规则106

5.2.2反证法107

5.2.3否定108

5.2.4合取和析取110

5.2.5关于repeat高阶策略112

5.2.6存在量词112

5.3等价性与重写113

5.3.1证明等式113

5.3.2使用等式：重写证明策略114

5.3.3*pattern策略116

5.3.4*条件重写117

5.3.5搜索用于重写的定理118

5.3.6用于等式的其他证明策略118

5.4策略总结表119

5.5***非直谓定义119

5.5.1警告119

5.5.2True和False119

5.5.3莱布尼兹等价120

5.5.4其他一些联结词和量词122

5.5.5书写非直谓定义的指导原则123

6归纳数据类型125

6.1非递归类型125

6.1.1枚举类型125

6.1.2简单的推理与计算127

6.1.3 elim策略128

6.1.4模式匹配129

6.1.5记录类型132

6.1.6带变体的记录134

6.2分情形推理135

6.2.1 case证明策略135

6.2.2矛盾等式137

6.2.3单射的构造子140

6.2.4归纳类型和等式142

6.2.5 * case的使用准则143

6.3递归类型147

6.3.1一个归纳类型——自然数147

6.3.2在自然数上做归纳证明148

6.3.3递归编程150

6.3.4构造子的形态变化152

6.3.5**具有函数域的类型155

6.3.6在递归函数上完成证明157

6.3.7匿名递归函数（fix）159

6.4多态类型159

6.4.1多态列表160

6.4.2 option类型162

6.4.3二元组类型163

6.4.4不相交和的类型164

6.5*依赖归纳类型165

6.5.1一阶数据做参数165

6.5.2可变依赖归纳类型165

6.6*空类型167

6.6.1非依赖空类型167

6.6.2依赖空类型169

7证明策略和自动化证明171

7.1用于归纳类型的证明策略171

7.1.1分情况讨论和递归171

7.1.2变换172

7.2 auto和eauto证明策略174

7.2.1证明策略库管理命令：Hint174

7.2.2*eauto证明策略177

7.3针对重写的自动证明策略177

7.3.1 autorewrite证明策略177

7.3.2 subst证明策略178

7.4和数相关的证明策略179

7.4.1 ring证明策略179

7.4.2 omega证明策略181

7.4.3 field证明策略182

7.4.4 fourier证明策略182

7.5其他决策过程183

7.6**策略定义语言184

7.6.1策略中的变元184

7.6.2模式匹配185

7.6.3在已经定义过的策略中使用归约191

8归纳谓词193

8.1归纳属性193

8.1.1几个例子193

8.1.2归纳谓词和逻辑程序设计195

8.1.3对归纳定义的建议195

8.1.4排序列表196

8.2归纳属性和逻辑连接词198

8.2.1表示真值199

8.2.2表示矛盾式199

8.2.3表示合取199

8.2.4表示析取200

8.2.5表示存在量词200

8.2.6表示等价200

8.2.7***异构等式201

8.2.8一个奇特的归纳原理？205

8.3归纳特性的推理206

8.3.1结构化intros206

8.3.2 constructor策略207

8.3.3*在归纳谓词上做归纳207

8.3.4*对le进行归纳209

8.4*归纳关系和函数213

8.4.1表示阶乘函数213

8.4.2**表示一个语言的语义218

8.4.3**语义属性证明220

8.5 * elim行为的详细阐述223

8.5.1实例化变元223

8.5.2转置225

9*函数及其规范231

9.1用于规范的归纳类型231

9.1.1“子集”类型231

9.1.2嵌套的子集类型233

9.1.3有认证的不相交和234

9.1.4混合不相交和235

9.2强规范235

9.2.1良规函数236

9.2.2将函数构造为证明236

9.2.3偏函数的前置条件237

9.2.4**对前置条件的证明238

9.2.5**增强规范239

9.2.6***最小规范增强240

9.2.7 refine策略243

9.3结构递归的变种形式245

9.3.1多步结构递归245

9.3.2简化步骤249

9.3.3多参数递归函数250

9.4**二进制除法254

9.4.1弱规范的除法254

9.4.2良规的二进制除法259

10*程序抽取和命令式程序设计263

10.1抽取到函数式语言程序263

10.1.1 Extraction命令263

10.1.2抽取机制264

10.1.3 Prop、 Set和抽取272

10.2描述命令式程序274

10.2.1工具Why274

10.2.2 *** Why的内部工作原理277

11*实例分析285

11.1二叉搜索树285

11.1.1数据结构286

11.1.2一个直接的存在判定方法286

11.1.3搜索树的描述287

11.2描述程序289

11.2.1查找289

11.2.2插入一个数289

11.2.3**删除一个数290

11.3辅助引理290

11.4规范说明的实现291

11.4.1查找判定的实现291

11.4.2插入294

11.4.3删除元素298

11.5可能的改进299

11.6另一个实例300

12*模块系统301

12.1签名301

12.2模块303

12.2.1构造一个模块304

12.2.2一个例子：Keys304

12.2.3参数化模块（函子）307

12.3可判定序关系理论310

12.3.1用函子丰富理论311

12.3.2字典序函子313

12.4一个字典模块315

12.4.1丰富了的实现315

12.4.2用函子构造字典316

12.4.3一个简单的实现316

12.4.4一个高效的实现318

12.5结论321

13**无穷对象和证明323

13.1余归纳类型323

13.1.1 CoInductive命令323

13.1.2余归纳类型的特殊性质323

13.1.3无限列表（流）324

13.1.4惰性列表324

13.1.5惰性二叉树325

13.2辅助余归纳类型的技术325

13.2.1构造有限对象325

13.2.2模式匹配326

13.3构造无穷对象327

13.3.1一个失败的尝试327

13.3.2 CoFixpoint命令328

13.3.3余递归函数示例329

13.3.4一些错误的定义331

13.4展开技术332

13.4.1系统性分解333

13.4.2分解引理的使用334

13.4.3化简对余归函数的调用335

13.5余归纳类型上的归纳谓词336

13.6余归纳谓词338

13.6.1无穷序列谓词338

13.6.2构造无限证明338

13.6.3违反Guard约束340

13.6.4消去技术342

13.7互模拟等价343

13.7.1 bisimilar谓词344

13.7.2互模拟等价的使用345

13.8 Park原理346

13.9 LTL347

13.10一个实例：状态迁移系统350

13.11结论351

14**归纳类型基础353

14.1形成规则353

14.1.1归纳类型353

14.1.2构造子355

14.1.3归纳原理的构造358

14.1.4递归子的类型360

14.1.5谓词的归纳原理366

14.1.6 Scheme命令368

14.2***模式匹配和证明上的递归369

14.2.1模式匹配的约束369

14.2.2放宽约束370

14.2.3递归372

14.3互引归纳类型374

14.3.1树和森林374

14.3.2使用互引归纳证明376

14.3.3***树和树列表378

15*一般递归381

15.1有界递归381

15.2**良基递归函数384

15.2.1良基关系384

15.2.2可访问性证明385

15.2.3整合良基关系386

15.2.4良基递归387

15.2.5递归子well_ founded_induction387

15.2.6良基欧氏除法388

15.2.7嵌套递归391

15.3**用迭代法实现通用递归393

15.3.1与递归函数相关的泛函393

15.3.2终止性证明394

15.3.3构造具体函数397

15.3.4证明不动点方程397

15.3.5使用不动点方程399

15.3.6讨论399

15.4***在人为谓词上递归400

15.4.1定义人为谓词400

15.4.2逆转定理401

15.4.3定义函数401

15.4.4证明该函数的特性402

16*自反证明405

16.1引言405

16.2直接的计算证明406

16.3**借助代数计算的证明409

16.3.1基于结合律的证明409

16.3.2把类型和操作符通用化413

16.3.3***交换律：变量排序416

16.4结论419

附录421

插入排序421

参考文献427