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。

いずれにせよ、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。n0 に等しい場合は明らかに真です。

補題の誘導ステップの場合:

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)

帰納仮説を 2 回目に使用したのは少し奇妙に思えるかもしれませんが、帰納仮説が次のように述べていることを思い出してください。

 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 に答える