1. 首页
  2. 文章资讯

【PL理论深化】(3) 数学归纳法：归纳假设 (IH) | 结构归纳法 | 归纳假设的证明

50 阅读 0 评论

  •  写在前面：所有编程语言都是通过归纳法定义的。因此，虽然编程语言本身是有限的，但用该语言编写的程序数量是没有限制的，本章将学习编程语言研究中最基本的归纳法。本章我们继续讲解归纳法，介绍归纳假设和结构性归纳法。

目录

0x00 归纳假设 (IH) 和结构归纳法

0x01 归纳假设的证明

0x00 归纳假设 (IH) 和结构归纳法

归纳法是一种用于证明归纳定义的集合中的元素所具有性质的方法。

假设存在一个通过归纳法定义的集合 S，为证明集合 S 中的所有元素 x 都满足某个性质 P(x)。

需证明以下两点：

① 若 x 是 S 的基本元素，则直接证明 P(x) 。

② 若 x 是利用 S 中的其他元素 y_1, y_2,..., y_n 归纳定义出来的，那么：

P(y_1),P(y_2),...P(y_n)

并假设它们都成立，然后利用这些假设来证明 P(x) 成立。

.

在这种情况下，P(y_1),P(y_2),...P(y_n) 被称为 归纳假设 (induction hypothesis, IH) 。

这种证明方法称为 结构归纳法 (structural induction)。

当集合 S 是自然数集时，这种方法就称为 数学归纳法 (MI)，是结构归纳法的一种特殊情况。

0x01 归纳假设的证明

举个例子，假设集合 S 是通过以下推理规则定义的集合：

让我们用结构归纳法来证明这样定义的集合 S 中的所有元素都能被 3 整除。

首先证明基本元素的情况。如果 x 等于 3，那么显然 x 能被 3 整除。

接下来，我们证明归纳生成的元素的情况，假设元素是按照以下规则生成的：

归纳假设 (induction hypothesis, I.H.) 如下：

x 和 y 能被 3 整除

根据归纳假设，设 x = 3k_1,\, y = 3k_2，需要证明的是：

x + y 能被 3 整除

证明如下：

x+y=3k_1+3k_2   ··· 归纳假设

=3(k_1+k_2)

.

我们再举个例子，将集合 S 定义为通过以下推理规则所定义的集合：

并且当 x\in S 时，设 l(x) 和 r(x) 分别表示 x 中包含的左括号和右括号的数量。

它们如下通过归纳法定义：

现在，我们来证明对于集合 S 的所有元素 x，左括号和有货好的数量是对等的。

我们可以如下表示将要证明的命题：

对于  \forall x\in S，l(x)=r(x)

可以通过 结构归纳法 进行如下证明：

基础元素是 x=0，根据函数 l 和 r 的定义，成立 l(x)=1=r(x)。

归纳生成的情况有以下两种：

.

规则一 的情况下，归纳假设如下：

l(x)=r(x)

需要证明的是 l\big(\, (x)\, \big)=r\big(\, (x)\, \big)，证明如下：

.

规则二 的情况下，归纳假设如下：

l(x)=r(x),\, \, \, \, \, l(y)=r(y)

需要证明的是 l(xy)=r(xy)，证明方式如下：

 [ 笔者 ]   王亦优
 [ 更新 ]   2024.6.23
 [ 勘误 ]   /* 暂无 */
 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！

参考资料 

- R. Neapolitan, Foundations of Algorithms (5th ed.), Jones & Bartlett, 2015.

- T. Cormen《算法导论》（第三版），麻省理工学院出版社，2009年。

- T. Roughgarden, Algorithms Illuminated, Part 1~3, Soundlikeyourself Publishing, 2018.

- J. Kleinberg&E. Tardos, Algorithm Design, Addison Wesley, 2005.

- R. Sedgewick&K. Wayne，《算法》（第四版），Addison-Wesley，2011

- S. Dasgupta，《算法》，McGraw-Hill教育出版社，2006。

- S. Baase&A. Van Gelder, Computer Algorithms: 设计与分析简介》，Addison Wesley，2000。

- E. Horowitz，《C语言中的数据结构基础》，计算机科学出版社，1993

- S. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008.

- A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974.

- M. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997.

- A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003. - A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983.

- E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997.

- R. Sedgewick, Algorithms in C: 第1-4部分（第三版），Addison-Wesley，1998

- R. Sedgewick，《C语言中的算法》。第5部分（第3版），Addison-Wesley，2002

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处： 免费源码网-免费的源码资源网站 » 【PL理论深化】(3) 数学归纳法：归纳假设 (IH) | 结构归纳法 | 归纳假设的证明

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部