3

私は公理の解決がプロローグでどのように機能するかを理解しようとしています。

自然数に対して2つの基本的な操作を定義すると仮定しましょう。

  • s（term）（後継者を表す）および

  • add（term、anotherTerm）。

addのセマンティクスは次のように与えられます

  • 追加（0、x1）-> x1

  • 追加（x1、0）-> x1

  • add（s（x1）、y1）-> s（add（x1、y1））

次に、方程式を解きたい

add（x、add（y、z））= s（0）

一つの戦略は

  • 方程式の右辺（RHS）が左辺（LHS）と等しいかどうかをテストします

  • 解決策が見つからない場合は、最も一般的なユニファイアを探してください

  • そうでない場合は、この方程式で使用できる公理を見つけてください。この仕事をするための戦略は次のようになります（公理ごとに）：方程式のRHSが公理のRHSに等しいことを解こうとします。解がある場合は、方程式のLHSが公理のLHSに等しいことを解いてみてください。それが成功した場合、私たちは正しい公理を見つけました。

  • 最終的に、解がなく、方程式のLHSとRHSが同じ操作（つまり、同じシグネチャであるが同じオペランドではない）の場合、各オペランドにアルゴリズムを適用し、各オペランドの解が見つかった場合に解が見つかります。

この（単純な）アルゴリズムはうまくいくと思います。しかし、このような問題を解決した経験のある人がいるかどうか知りたいのですが。より良いアルゴリズムに関するドキュメントがどこにあるか知っている人はいますか？

前もって感謝します

4

3 に答える 3

4

Prolog プログラムは述語の集まりです。

述語は節の集まりです。

句の形式は次のとおりです。

Head :- Body.

Head「が真なら真」という意味Bodyです。

短縮形の節があります

Head.

と同じ意味です

Head :- true.

wheretrueは常に 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.

Prolog には、評価順序 (左から右) と「カット」 (検索ツリーを剪定する) に関するいくつかの特別な規則がありますが、それはこの短いチュートリアルの範囲を超える細かい詳細です。

ここで、anAtomが真かどうかを判断するにはAtom、次の形式のいずれかを使用できます (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)の合計に評価される関数を定義できますが、Prolog では、ヘッドが成功した場合に との合計を表す項と一体化する述語を定義します。XYadd(X, Y, Z)ZXY

以上のことから、次のように 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))).

ここで、「句で複数のヘッドが一致した場合はどうなるか」または「評価パスが失敗した場合はどうなるか」という質問をすることができますが、その答えは「非決定論」、「バックトラッキング」であり、一般に、プロローグの教科書！

お役に立てれば。

于 2010-11-30T23:20:48.963 に答える
2

あなたが探しているものは、ナローイングと呼ばれます。Curryなどの関数型論理言語で実装されていますが、Prolog 自体では実装されていません。

于 2010-12-01T07:30:09.557 に答える
0

Brachmann と Levesque による「知識の表現と推論」は、これらがどのように機能するかについてかなり良い紹介を提供します。

于 2010-11-30T22:01:21.427 に答える