この再帰プロローグの例を理解するのを手伝ってくれる人はいますか?

StackOverflow https://stackoverflow.com/questions/6322789

  •  27-10-2019
  •  | 
  •  

質問

これが理解できないプラスコードです

plus(0,X,X):-natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).

与えられた間:

natural_number(0).
natural_number(s(X)) :- natural_number(X).

この再帰がわかりません。私が持っているなら plus(s(0),s(s(s(0))),Z) どうすれば答えを得ることができますか 1+3=4?

最初のコードについては説明が必要です。それを試してみます plus(0,X,X) 再帰を停止しますが、やり方が間違っていると思います。

役に立ちましたか？

解決

それでは、始めましょう natural_number(P). 。これを「Pは自然数」として読んでください。与えられた natural_number(0)., 、それは私たちにそれを教えてくれます 0 常に自然数です（つまり、それが事実であるために満たされなければならない条件はありません）。 natural_number(s(X)) :- natural_number(X). それを教えてくれます s(X) 場合は自然数です X 自然数です。これは自然数の通常の帰納的定義ですが、プロログを読むときに「逆」と書かれたq：= p」は「pが真である場合はtrue」として書かれています。

今、私たちは見ることができます plus(P, Q, R). 。これを「plus P Plus qがR "に等しい場合にTRUEです。次に、与えられたケースを調べます。

  1. plus(0,X,X) :- natural_number(X).. 。 xが自然数の場合、xの結果をxに追加すると読み取ります。これは私たちの帰納的ベースケースであり、追加の自然な定義です。
  2. plus(s(X),Y,s(Z)) :- plus(X,Y,Z). 「xの後継者をyの後継者を後継zに追加すると、xがyにyを追加するとz」と読みます。表記を変更すると、x + yの場合は「x + 1 + y = z + 1の場合に代数的に読み取ることができます。 = z "、これは再び非常に自然です。

だから、あなたに直接質問するために「私が持っているなら plus(s(0),s(s(s(0))),z), 、どうすれば1+3 = 4の答えを得ることができますか？」、誘導の各ステップで何かを統合する方法を考えてみましょう

  1. の2番目の定義を適用します plus, 、クエリを統合するのは唯一のものです。 plus(s(0),s(s(s(0))), s(z')) もしそうです plus(0, s(s(s(0))), z') 一部の人には当てはまります z
  2. 次に、Plusの最初の定義を適用します。これは、唯一の統一定義であるためです。 plus(0, s(s(s(0))), z') もしも z' は s(s(s(0))) と s(s(s(0))) 自然数です。
  3. の定義を解き放ちます natural_number 数回 s(s(s(0))) それが真実であることを見るために。
  4. したがって、全体的な声明は真実です s(s(s(0))) 統一されています z' と s(z') 統一されています z.

したがって、インタープリターはtrueを返します z' = s(s(s(0))) と z = s(z'), 、すなわち z = s(s(s(s(0)))). 。そう、 z 4です。

他のヒント

そのコードは、簡単な実装です Peano算術に追加.

Peano算術では、定数を使用して自然数が表されます 0 および統一関数 s. 。そう s(0) 1の表現です、 s(s(s(0))) 3の表現です plus(s(0),s(s(s(0))),Z) あなたに与えます Z = s(s(s(s(0)))), 、4の表現です。

次のような数値用語は得られません。 1+3=4, 、得られるのは用語だけです s/1 これは任意の深さまで埋め込むことができるため、任意の自然数を表すことができます。このような用語を組​​み合わせることができます (使用して plus/3)、それによって合計が達成されます。

の定義に注意してください plus/3 SWI-Prolog の組み込みとは何の関係もありません plus/3 (これは整数では機能しますが、 s/1 条項）：

?- help(plus).
plus(?Int1, ?Int2, ?Int3)
    True if Int3 = Int1 + Int2.
    At least two of the three arguments must be instantiated to integers.
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top