5

请多多包涵。我将首先描述书中的一个例子，然后在最后提出我的问题。

根据编程语言范式上的文字：

归纳规范是指定一组值的强大方法。为了说明这种方法，我们用它来描述 自然数 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 的集合，它是满足属性 1 和 2 的任何其他集合的子集。很容易看出只能存在一个这样的集合：如果 S1 和 S2 都满足属性1 和 2，并且都是最小的，则 S1 ⊆ S2（因为 S1 最小），并且 S2 ⊆ S1（因为 S2 最小），因此 S1 = S2。我们需要这个额外的条件，否则会有很多集合满足剩下的两个条件

推理规则：

_____
0 ∈ S

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

这只是先前版本定义的简写符号。每个条目都称为推理规则，或者只是一条规则；水平线读作“if-then”。线以上的部分称为假设 或前件；线以下的部分称为结论或结果。当列出两个或多个假设时，它们通过隐含的“和”连接</p>

现在问题来了。

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

我想找到以下 2 个问题的自上而下、自下而上和推理定义。您不必给我答案，但我确实想知道如何推导归纳定义。我从哪里开始？是否有解决此类问题的系统方法（配方）？

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

3 回答 3

3

你在这里问了很多问题，所以希望这个回复能回答所有问题。如果您有什么想澄清的，请告诉我。

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

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

或者二叉树：

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

或正则表达式：

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

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

  • 参观空树，什么都不做。
  • 访问由一个节点和两个子树组成的树：
    • 访问节点
    • 访问左子树
    • 访问右子树

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

归纳定义也可以用来正式证明结构的性质。例如，下面是 AVL 树的正式定义：

  • 单个节点是一棵 0 阶的 AVL 树
  • 具有一个或两个子节点的节点是 0 阶 AVL 树，即是 1 阶 AVL 树。
  • 具有两个子节点的节点是 n - 1 阶的 AVL 树，或者一个节点是 n - 1 阶的 AVL 树和另一个是 n - 3 阶的 AVL 树的子节点是 n 阶 AVL 树。

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

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

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

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

您的第四个问题-为什么找不到任何示例？- 可以通过花一分钟时间查看您所知道的经典数据结构和算法来轻松解决。你可以归纳定义多少个数据结构？尝试查看链表、二叉树、红黑树、AVL 树等以获得灵感。您将如何定义图表？DAG？同样，尝试查看句法结构。例如，您将如何归纳定义平衡括号的字符串？C中的函数原型怎么样？

您的最后一个问题 - 是否有解决这些问题的系统方法？- 有否定的答案。您可以定义等效于在输入上模拟任意图灵机的递归，并且由于停止问题是不可判定的，因此没有解决此类问题的通用程序。但是，确实存在许多方法。尝试查看 Graham、Knuth 和 Patashnik 的“具体数学”，以获取有关如何通过重复进行工作的灵感。

希望这可以帮助！

于 2012-02-07T04:18:48.023 回答
2

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

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

1. a) 0 ∈ Sb) If n ∈ S, then n+2 ∈ Sc)If n ∈ S, then n+3 ∈ S

2. k=0 and l=1如果 a)或 b) ，则一对自然数 (k,l) 在 S 中(k-1, l-2) ∈ S

2. 一）(0,0) ∈ S二）If (k,l) ∈ S, then (k+1, l+2) ∈ S

于 2012-02-07T04:27:52.567 回答
1

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

归纳定义适用于：

  1. 证明关于集合成员的属性。例如，可以归纳定义lambda 项，然后您可以证明有关这些项的定理。您将使用一种称为Structural Induction的证明技术。
  2. 编写操作集合成员的函数。我们在函数式编程中一直这样做。例如，可以归纳定义列表。然后使用代数数据类型在代码中表示该归纳定义，然后我们可以在列表上编写函数，如length下面的函数。另一个例子是归纳图，请查看这篇论文Inductive Graphs and Functional Graph Algorithms。
type List a
  = Empty
  | Cons a (List a)

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

    Cons _ xs ->
      1 + length xs

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

我不知道，但这本书有一个很好的章节（第 3 章 - 构造技术），其中包含大量示例。

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

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

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

我上面分享的这本书，离散结构、逻辑和可计算性（第 4 版），在第 3 章中有大量示例和练习，供您分别理解和练习。

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

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

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

回答1。

回答2。

有系统的方法吗？

不，解决问题。提出想法并进行测试。阅读Polya 的How to Solve It以培养您解决问题的能力。

于 2019-08-07T14:10:41.807 回答