归纳证明两个函数定义相等

Question

如何进行归纳以建立语句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

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

Answer 1

您的 n+1 步骤有误。我怀疑这是因为您是 Haskell 及其优先级规则的新手。

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

在任何情况下，moll (n+1) 实际上是 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)

归纳证明两个函数定义相等

To prove equality of two function definitions inductively

haskell

induction

equational-reasoning