【PL理论】(1) 语法与语义：归纳的定义 | 推理规则 | 推导树

【PL理论】(1) 语法与语义：归纳的定义 | 推理规则 | 推导树 | 数学归纳法证明 (MI)

💭 写在前面：在学习编程的过程中，我们经常会听到 "语法" 和 "语义" 这两个词，这对于理解和编写高质量的代码至关重要。在本博客中，我们将深入探讨这两个概念，从而帮助读者更好地理解编程语言的本质和运作方式。

0x00 归纳的定义（Inductive Definition）

0x01 推理规则（Inference Rule）

0x02 推导树（Derivation Tree）

0x03 数学归纳法证明（Mathematical Induction）

0x00 归纳的定义（Inductive Definition）

让我们定义 $\mathbb{S},\, \mathbb{S}\in \mathbb{Z}$ ，它是一些整数的集合， $\mathbb S$ 是满足以下两个条件的最小集 (smallest set) ：

$0\in \mathbb{S}$
$n \in \mathbb{S}\Rightarrow n + 3 \in \mathbb{S}$ (若 n ∈ 𝑺, 则 n + 3 ∈ 𝑺)

直觉上，我们知道 $\mathbb{S}=\left \{ 0,3,6,9... \right \}$ ，那么如果我们没有 "最小集" 这个条件呢？

那么可能有许多集合满足这两个条件，例如 $\left \{ 0,1,2,3,4,5,6,... \right \}$ 也满足 $\mathbb{S}$ 。

现在，如果我们没有 $0\in\mathbb{S}$ 这个条件呢？那么 $\mathbb{S}$ 就变成了空集。

因此注重基线条件 (basecase) 是至关重要的。

0x01 推理规则（Inference Rule）

PL (Programming Languages) 可以理解为是概括“程序设计语言自理论体系到其实现系统”的一个总称。

在 PL 中，归纳定义通常使用推理规则来呈现，推理规则的一般形式如下：

意味着 "如果 $A_1\, \, A_2\, \, A_3\, \, ...\, \, A_n$ 都为真，则 $B$ 为真：

$A_1...A_n$ 是前提 (premise)
$B$ 是结论 (conclusion)

先前的归纳定义示例可以重写为推理规则的形式：

请注意，对于基本情况 $0\in \mathbb{S}$ ，没有前提 (without premise) 。

$\mathbb{S}$ 被定义为可以从这些推理规则推导出的元素的集合：

例如对于 𝑥 = 0, 3, 6, 9 …，我们可以推导出 𝑥 ∈ 𝑆
例如对于 𝑥 = 1, 2, 4, 5 …，我们无法推导出 𝑥 ∈ 𝑆

根据规则，理所当然地强制了 $\mathbb{S}$ 是在规则下的最小集。

0x02 推导树（Derivation Tree）

在先前的例子中，对于 $x\in \mathbb S$ ，我们可以构造一个推导树，显示规则的应用。

例如，我们可以如下推导（证明） $9\in \mathbb S$ 。
由于规则简单，它看起来并不像树形结构。

💭 更多例子：

① 自然数 $\mathbb N$ ：

② 整数列表 $L$ ：

[ ] 表示空列表， $\mathbb Z$ 表示整数集合
$x::y$ 表示将元素 $x$ 添加到列表 $y$ 的前面（连接）
$1::2::3::[\, ]$ 等价于 Python 风格中的 $[1,2,3]$

0x03 数学归纳法证明（Mathematical Induction）

数学归纳法 (Mathematical Induction)，简称 MI，是一种证明数学命题的常用方法，特别适用于证明关于自然数的性质。它基于两个关键步骤：

基础步骤（Base Case）：首先证明当自变量取得最小值时，命题成立。通常这是通过直接验证特定的情况来完成的。
归纳步骤（Inductive Step）：接着假设当自变量取得某个值时，命题成立，然后证明当自变量取得下一个值时，命题仍然成立。这个步骤通常包括以下两个部分：
- 假设命题对于一个特定的值成立（归纳假设）。
- 证明基于这个假设，命题对于下一个值也成立。

通过结合基础步骤和归纳步骤，可以推导出命题对于所有符合条件的自变量都成立。

下面我们来看如何使用 MI 证明。

证明：对于归纳定义的集合 $\mathbb S$ ，我们如何证明命题 $P(x)$ 对于所有 $x\in \mathbb S$ 都成立？

基本情形 (Base case) $x$ ：直接证明 𝑷(𝒙) 成立
归纳情形 (Inductive case) $x$ ：在假设所有构成 𝒙 的子组件 𝒙𝒊 都满足 𝑷(𝒙𝒊) 的前提下，证明 𝑷(𝒙) 成立

例如：对于 $P(x)=x$ 是 3 的倍数，在先前的例子中证明 $P(x)$ 对于 $\mathbb S$ 成立。

基本情形 (Base case) ：0 是 3 的倍数
归纳情形 (Inductive case)：如果 $n$ 是 3 的倍数，我们可以令 $n=3k$
- 然后， $n + 3 = 3k + 3 = 3(k + 1)$ 也是 3 的倍数。

上面的归纳的一般形式被称为 结构归纳 (structural induction) 。

当归纳定义的集合是 $\mathbb N$ （自然数集合）时，这通常被称为 数学归纳 (mathematical induction) 。可以将其视为结构归纳的一种特定形式。

$P(1)$ 成立。
如果 $P(N)$ 成立，则 $P(n+1)$ 也成立。

这种归纳是你必须熟悉的一种形式。

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

📜 参考资料

C++reference[EB/OL]. []. http://www.cplusplus.com/reference/.

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/490042.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！