归纳规范：自上而下与自下而上与推理规则？

Question

请耐心听我讲这一点。我首先要描述书中的一个例子，然后在最后提出我的问题。

根据编程语言范式的文本：

归纳规范是指定一组的强大方法 价值观。为了说明这个方法，我们用它来描述某个 自然数 N = {0, 1, 2, . 。 .}.

自上而下的定义：

自然数 n 在 S 中当且仅当

1. n = 0，或
2. n −3 ∈ S。

我们知道0 ∈ S。因此 3 ∈ S，因为 (3 − 3) = 0 且 0 ∈ S。类似地 6 ∈ S，因为 (6−3) = 3 且 3 ∈ S。继续这样，我们 可以得出结论，3的所有倍数都在S中。

那么其他自然数呢？ 1 是 S 吗？我们知道 1 != 0，所以 第一个条件不满足。此外，(1−3) = −2，这不是自然数 数，因此不是 S 的成员。因此第二个条件 不满意。

自下而上的定义：

定义集合S为N中包含的最小集合并且满足 满足以下两个性质：

1. 0 ∈ S，
2. 如果 n ∈ S，则 n +3 ∈ S。

“最小集合”是满足性质 1 和 2 的集合，即 a 满足属性 1 和 2 的任何其他集合的子集。很容易看出 只能有一个这样的集合：如果 S1 和 S2 都满足属性 1 和 2，并且两者都是最小的，则 S1 ⊆ S2 （因为 S1 最小），并且 S2 ⊆ S1 （因为 S2 最小），因此 S1 = S2。我们需要这个额外条件，因为 否则有许多集合满足其余两个条件

推理规则：

_____
0 ∈ S

n ∈ S
---------
(n+3) ∈ S

这只是先前版本定义的简写符号。 每个条目被称为推理规则，或者只是一个规则；水平的 该行被解读为“如果-那么”。线上方的部分称为假设 或先行词；线下方的部分称为结论或结果。 当列出两个或多个假设时，它们通过以下方式连接 隐含的“和”

---

现在问题来了。

• 也许最重要的问题是为什么我需要知道这些归纳定义，以及它们在现实世界中有何用处？
• 为什么 Google 几乎没有返回归纳定义的结果？
• 如果自上而下、自下而上和推理规则本质上显示的是同一件事，为什么我们需要三种方式来编写同一件事呢？
• 为什么我很难找到比书中示例复杂一点的问题的归纳定义，例如下面的例子。

我想找到以下两个问题的自上而下、自下而上和推理定义。你不必给我答案，但我确实想知道如何导出归纳定义。我从哪里开始？是否有一个系统的方法（秘诀）来解决这些类型的问题？

1. {2n+3m +1 | n,m ∈ N}
2. {(n, 2n+1) | n ∈ N}

Answer 1

您在这里问了很多问题，所以希望这个答复能够回答所有问题。如果您想澄清一些事情，请告诉我。

你的第一个问题——为什么我们需要归纳定义？ - 最容易回答。在计算机科学中，大量的结构是通过归纳定义的。例如，您的简单链表具有归纳定义

• 空列表是链表。
• 单个节点后跟链表就是链表

或二叉树：

• 空树就是二叉树。
• 具有两个二叉树子节点的节点是二叉树。

或者正则表达式：

• ∅是正则表达式。
• ε 是正则表达式。
• a 是每个字符 a 的正则表达式
• 如果 R1 和 R2 是正则表达式，则 R1 | R2 是正则表达式。
• 如果R1和R2是正则表达式，则R1 R2是正则表达式。
• 如果 R 是正则表达式，则 R* 也是正则表达式。
• 如果R是正则表达式，则(R)是正则表达式。

这些定义有许多很好的属性。首先，它们适合递归算法。如果要访问二叉树中的每个节点，我们可以使用二叉树的归纳定义来构建一个简单的访问算法：

• 访问空树，不执行任何操作。
• 访问由一个节点和两个子树组成的树：
  • 访问节点
  • 访问左子树
  • 访问右子树

类似地，如果我们想要操作正则表达式的结构 - 例如，可能为其构建匹配自动机 - 那么归纳定义可以让我们构建自动机分段地从正则表达式中取出。

归纳定义也可用于形式化证明结构的属性。例如，下面是 AVL 树的正式定义：

• 单个节点是 0 阶 AVL 树
• 是 1 阶 AVL 树。
• 具有一到两个子级 0 级 AVL 树的节点 是 n - 1 阶 AVL 树，或者其中一个子节点是 n - 1 阶 AVL 树，另一个子节点是 n - 3 阶 AVL 树，是 n 阶 AVL 树。

使用这个定义，可以正式证明 AVL 树是平衡的。

我们可以类似地使用这些类型的定义来证明编程语言的属性。大多数语言都有某种归纳定义，因此通过证明程序的每个部分都保留了一些信息，我们可以从头开始构建正确性证明。

你的第二个问题 - 为什么谷歌没有提供任何归纳定义的例子？ - 我认为是因为它将其解释为“定义归纳法”，而不是一个术语本身。如果您查找递归定义，那么您会发现大量归纳定义的示例，因为归纳定义和递归定义彼此非常相似。

你的第三个问题——为什么我们需要多种方式来表达同一件事？ - 也很容易。如果你想证明一个系统的某些东西，归纳定义是很好的选择。如果你证明它适用于基本元素，然后证明较大的元素保留该属性，你就可以证明它总是正确的。递归定义有利于编写程序，因为递归函数倾向于向后运行归纳。推理规则与逻辑证明系统相关，并为使用经典逻辑证明系统的属性提供了起点。

你的第四个问题——为什么你找不到任何例子？ - 只需花一分钟时间查看您所知道的经典数据结构和算法即可轻松修复。您可以归纳定义多少种数据结构？尝试查看链表、二叉树、红黑树、AVL 树等来获取灵感。您将如何定义图表？有向无环图？同样，尝试查看句法结构。例如，您将如何归纳定义平衡括号字符串？ C 语言中的函数原型怎么样？

您的最后一个问题 - 是否有系统的方法来解决这些问题？ - 有否定的答案。您可以定义相当于在输入上模拟任意图灵机的递归，并且由于停止问题是不可判定的，因此没有解决此类问题的通用过程。不过，确实存在许多方法。尝试阅读 Graham、Knuth 和 Patashnik 所著的《具体数学》，以获取有关如何处理递归的灵感。

希望这有帮助！

Answer 2

除了“动动脑子”之外，没有什么系统的方法。
但你很幸运，因为这两个示例确实非常接近原始示例：

1。自然数 k 在 S 中，如果 a) k = 1 或 b) k-2 ∈ S 或 c) k-3 ∈ S >

<代码>1。 a) 0 Î S b) 如果 n Î S，则 n+2 Î S c) 如果 n Î S，则 n+3 Î S代码>

<代码>2。一对自然数 (k,l) 在 S 中，如果 a) k=0 和 l=1 或 b) (k-1, l-2) ∈ S

<代码>2。 a) (0,0) Î S b) 如果 (k,l) Î S，则 (k+1, l+2) Î S

Answer 3

为什么我需要了解这些归纳定义，以及它们在现实案例中有何用处？

归纳定义可用于：

1. 证明有关集合成员的属性。例如，lambda 项可以归纳定义，然后您可以证明有关这些项的定理。您可以使用一种名为结构归纳的证明技术。
2. 编写操作集合成员的函数。我们在函数式编程中一直这样做。例如，列表可以归纳定义。然后使用代数数据类型在代码中表示该归纳定义，然后我们可以在上面编写函数列表如下面的 length 函数所示。另一个例子是归纳图，请查看这篇论文 归纳图和函数图算法< /a>.

type List a
  = Empty
  | Cons a (List a)

length : List a -> Int
length list =
  case list of
    Empty ->
      0

    Cons _ xs ->
      1 + length xs

为什么 Google 几乎没有返回归纳定义的结果？

我不知道，但这书有一个很好的章节（第3章 -施工技术）上面有大量的例子。

为什么我们需要 3 种方式来编写同一件事？

不同的观点让你以不同的方式思考同一件事，它们可以帮助你塑造你的直觉。阅读培养你的数学直觉。在这种特殊情况下，自上而下的定义有利于计算对象何时是集合的成员，而自下而上的定义（推理规则只是自下而上的定义的简写）有利于生成集合的成员。

为什么我很难找到比书中示例稍微复杂一点的问题的归纳定义。

我上面分享的书，离散结构、逻辑和可计算性（第四版），第3章有大量的例子和练习，供你分别理解和练习。

我如何导出归纳定义？我从哪里开始？

感受一下集合中的元素。我首先会列出集合中的一些元素，看看它们如何相互关联。我会寻找无法用更简单的元素定义的基本元素，然后从这些基本元素中我会寻找可以写下哪些规则来获取其他元素。

在尝试了几个小时之前不要看。

回答 1。

回答 2。

有系统的方法吗？

不，解决这个问题。提出想法并进行测试。阅读 Polya 的如何解决来培养您解决问题的技能。