本文主要是介绍【PL理论深化】(3) MI 归纳法：归纳假设 (IH) | 结构归纳法 | 归纳假设的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 💬 写在前面：所有编程语言都是通过归纳法定义的。因此，虽然编程语言本身是有限的，但用该语言编写的程序数量是没有限制的，本章将学习编程语言研究中最基本的归纳法。本章我们继续讲解归纳法，介绍归纳假设和结构性归纳法。
目录
0x00 归纳假设 (IH) 和结构归纳法
0x01 归纳假设的证明
0x00 归纳假设 (IH) 和结构归纳法
归纳法是一种用于证明归纳定义的集合中的元素所具有性质的方法。
假设存在一个通过归纳法定义的集合 ，为证明集合
中的所有元素
都满足某个性质
。
需证明以下两点：
① 若 是
的基本元素，则直接证明
。
② 若 是利用
中的其他元素
归纳定义出来的，那么：
并假设它们都成立，然后利用这些假设来证明 成立。
.
在这种情况下， 被称为 归纳假设 (induction hypothesis, IH) 。
这种证明方法称为 结构归纳法 (structural induction)。
当集合 是自然数集时，这种方法就称为 数学归纳法 (MI)，是结构归纳法的一种特殊情况。
0x01 归纳假设的证明
举个例子，假设集合 是通过以下推理规则定义的集合：
让我们用结构归纳法来证明这样定义的集合 中的所有元素都能被 3 整除。
首先证明基本元素的情况。如果 等于 3，那么显然
能被 3 整除。
接下来，我们证明归纳生成的元素的情况，假设元素是按照以下规则生成的：
归纳假设 (induction hypothesis, I.H.) 如下：
x 和 y 能被 3 整除
根据归纳假设，设 ，需要证明的是：
x + y 能被 3 整除
证明如下：
··· 归纳假设
.
我们再举个例子，将集合 定义为通过以下推理规则所定义的集合：
并且当 时，设
和
分别表示
中包含的左括号和右括号的数量。
它们如下通过归纳法定义：
现在，我们来证明对于集合 的所有元素
，左括号和有货好的数量是对等的。
我们可以如下表示将要证明的命题：
对于 ，
可以通过 结构归纳法 进行如下证明：
基础元素是 ，根据函数
和
的定义，成立
。
归纳生成的情况有以下两种：
.
规则一 的情况下，归纳假设如下：
需要证明的是 ，证明如下：
.
规则二 的情况下，归纳假设如下：
需要证明的是 ，证明方式如下：
📌 [ 笔者 ] 王亦优
📃 [ 更新 ] 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) MI 归纳法：归纳假设 (IH) | 结构归纳法 | 归纳假设的证明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
