3

我如何进行归纳以建立陈述moll n = doll n，与

moll 0 = 1                               --(m.1)
moll n = moll ( n-1) + n                 --(m.2)

doll n = sol 0 n                         --(d.1)
 where
  sol acc 0 = acc +1                     --(d.2)
  sol acc n = sol ( acc + n) (n-1) -- ?    (d.2)

我试图证明 n = 0 的基本情况

doll 0 = (d.2) = 1 = (m.1) = moll 0 , which is correct.

现在n+1，证明

moll 2n = doll (n + 1)

=> doll (n + 1) = (d.2) = soll (acc + n + 1) n

但是现在呢？我怎样才能进一步简化它？

4

1 回答 1

1

你的n+1步骤有误。我怀疑这是因为您不熟悉 Haskell 及其优先规则。

moll (n+1)不是，正如您所写的那样moll 2n-我假设您的意思是moll (2*n)，因为moll 2n是haskell语法错误。

无论如何，moll (n+1)is in fact moll n + n + 1，或者，为了明确起见，添加了额外的括号：

(moll n) + (n + 1)

也就是说，您申请moll然后n添加n + 1到结果中。

从这里你应该能够应用归纳假设并继续前进。

更明确地说，因为您似乎仍然遇到麻烦：

moll (n+1) == (moll n) + (n + 1)       (by m.2)
           == (doll n) + (n + 1)       (by induction hypot.)
           == (sol 0 n) + (n + 1)      (by d.1)

现在，作为引理：

sol x n == (sol 0 n) + x

这可以通过对 的归纳来证明n。显然n等于 0 是正确的。

对于引理的归纳步骤：

sol x (n+1) == (sol (x + (n+1)) n)       (By d.2, for (n+1) > 0)
            == (sol 0 n) + (x + (n+1))   (By the induction hypot.)
            == (sol 0 n) + (n+1) + x     (This is just math; re-arranging)
            == ((sol 0 n) + (n+1)) + x
            == (sol (n+1) n) + x         (By the induction hypot. again)
            == (sol 0 (n+1)) + x         (By d.2 again)

我第二次使用归纳假设可能看起来有点奇怪，但请记住归纳假设说：

 sol x n == (sol 0 n) + x

对于所有x. 因此，我可以将它应用于添加到 . 的任何内容(sol 0 n)，包括n+1.

现在，回到主要证明，使用我们的引理：

moll (n+1) == (sol 0 n) + (n + 1)      (we had this before)
           == sol (n+1) n              (by our lemma)
           == sol 0 (n+1)              (by d.2)
           == doll (n+1)               (by d.1)
于 2016-01-25T13:58:55.960 回答