-
29-09-2019 - |
質問
私は、Axiomの解像度がPrologでどのように機能するかを理解しようとしています。
自然数に関する2つの基本操作を定義していると仮定しましょう。
s(ターム)(後継者の略)と
追加(用語、別のターム)。
ADDのセマンティックはによって与えられます
追加(0、x1) - > x1
追加(x1、0) - > x1
add(s(x1)、y1) - > s(add(x1、y1))
次に、方程式を解きたいと思います
add(x、add(y、z))= s(0)
私は1つの戦略がそうである可能性があると思います
方程式の右側(RHS)が左側(LHS)に等しいかどうかをテストします
最も一般的なユニファイアを探すことで、ソリューションを見つけることができるかどうかわからない場合
そうでない場合は、この方程式で使用できる公理を見つけてみてください。このジョブを行うための戦略は、(各公理の場合)になる可能性があります。方程式のRHSは、公理のRHSに等しいことです。解がある場合は、方程式のLHSが公理のLHSに等しいことを解決してみてください。それが成功した場合、私たちは正しい公理を見つけました。
最終的には、解がなく、方程式のLHSとRHSが同じ操作(つまり、同じ署名が同じオペランドではない)である場合、各オペランドにアルゴリズムを適用し、各オペランドのソリューションが見つかった場合に解決策が見つかります。
この(単純な)アルゴリズムが機能する可能性があると思います。しかし、誰かがこの種の問題を解決した経験があるかどうかを知りたいですか?より良いアルゴリズムについてのドキュメントをどこで見つけることができるか誰もが知っていますか?
前もって感謝します
他のヒント
Prologプログラムは、述語のコレクションです。
述語は条項のコレクションです。
句にはフォームがあります
Head :- Body.
意味 "Head
もしそうです Body
本当です」。
速記の条項形式があります
Head.
これは同じことを意味します
Head :- true.
どこ true
常に真実である組み込みです。
に戻る Body
条項の一部、 Body
次の形式のいずれかをとることができる目標です(A
, B
, 、 と C
任意の目標を示します):
Atom % This is true if Atom is true (see below).
A, B % This is true if A is true and B is true.
(A ; B) % This is true if A is true or B is true.
\+ A % This is true if A is not true.
(A -> B ; C) % If A is true then B must be true, else C must be true.
評価順序(左から右)と「カット」(検索ツリーを剪定する)に関する特別なルールがいくつかありますが、この短いチュートリアルの範囲を超えた詳細です。
さて、Anかどうかを決定します Atom
本当です、 Atom
次の形式の1つになることができます(X
と Y
任意の用語を示します):
true % or some other builtin with given truth rules.
X = Y % True if X and Y are successfully unified.
p(X, Y, ...) % True if p(X, Y, ...) matches the head of some clause
% and the Body is true.
用語は、本質的に、任意の構文です。
ここで見つける重要なことは、Prologには機能がないことです!機能的な言語では、関数を定義するかもしれません add(X, Y)
の合計に評価します X
と Y
, 、プロログでは、頭がある述語を定義します add(X, Y, Z)
それが成功した場合、統一します Z
合計を示す用語で X
と Y
.
それをすべて考えると、次のようにPrologのルールを定義できます。
add(0, Y, Y). % 0 + Y = Y.
add(Y, 0, Y). % Y + 0 = Y.
add(s(X), Y, s(Z)) :- add(X, Y, Z). % s(X) + Y = s(X + Y).
私が使用している場所 0
ゼロ(!)を示す s(X)
の後継者を示す X
.
評価を検討してください add(s(s(0)), s(0), Z)
:
add(s(s(0)), s(0), Z) % Only the third head for add matches, so...
---> Z = s(Z0), add(s(0), s(0), Z0).
add(s(0), s(0), Z0) % Only the third head for add matches, so...
---> Z0 = s(Z1), add(0, s(0), Z1).
add(0, s(0), Z1) % Only the first head for add matches, so...
---> Z1 = s(0).
これらのすべての統一を置きます Z
一緒に、私たちは持っています Z = s(s(s(0)))
.
ここで、「句で複数のヘッドが一致する場合はどうなりますか」または「評価パスが失敗した場合はどうなりますか?」と尋ねることができます。 Prolog教科書!
お役に立てれば。
BrachmannとLevesqueによる「知識表現と推論」は、これらのことがどのように機能するかについてかなり良い紹介を提供します。