请多多包涵。我将首先描述书中的一个例子,然后在最后提出我的问题。
根据编程语言范式上的文字:
归纳规范是指定一组值的强大方法。为了说明这种方法,我们用它来描述 自然数 N = {0, 1, 2, . . .} .
自上而下的定义:
一个自然数 n 在 S 中当且仅当
- n = 0,或
- 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 中包含的最小集合并满足以下两个性质:
- 0 ∈ S,并且
- 如果 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}