6

Herbrand Universe、Herbrand Base、Herbrand Model of Binary Tree (プロローグ) で尋ねられた質問と回答を読みましたが、確認のような少し異なる質問があり、混乱が解消されることを願っています。

P を、次の事実とルールを持つようなプログラムとします。

q(a, g(b)).
q(b, g(b)).
q(X, g(X)) :- q(X, g(g(g(X)))).

上記プログラムから、エルブラン・ユニバース 

Up = {a, b, g(a), g(b), q(a, g(a)), q(a, g(b)), q(b, g(a)), q(b, g(b)), g(g(a)), g(g(b))...e.t.c}

エルブランドベース:

Bp = {q(s, t) | s, t E Up}
  • さて、私の質問に来てください（私の無知を許してください）、私はq（a、g（a））を私のHerbrand Universeの要素として含めましたが、事実から、q（a、g（b））と述べています。それは q(a, g(a)) がそこにあるとは思わないということですか?
  • また、Herbrand モデルは Herbrand ベースのサブセットであるため、誘導によって最小の Herbrand モデルを決定するにはどうすればよいですか?

注: 私はこれについて多くの調査を行いました。いくつかの部分は私にはよくわかりますが、それでも私はこの疑問を抱いています。それが、コミュニティの意見を求めたい理由です. ありがとうございました。

4

2 に答える 2

7

事実から、モデルにあるq(a,g(b))かどうかを結論付けることはできません。q(a,g(a))最初にモデルを生成する必要があります。

モデルを決定するには、事実から始めて、{q(a,g(b)), q(b,g(b))}ルールを適用してモデルを拡張してみてください。ただし、あなたの場合、ルールの右側q(X,g(X)) :- q(X,g(g(g(X)))).を上記の事実に一致させる方法はありません。したがって、完了です。

ルールを想像してみてください

q(a,g(Y)) :- q(b,Y).

このルールは、セットを拡張するために使用できます。実際、インスタンス

q(a,g(g(b))) :- q(b,g(b)).

が使用されている:q(b,g(b))が存在する場合は、結論を下しq(a,g(g(b)))ます。ここでは右から左のルールを使用していることに注意してください。だから私たちは得る

{q(a,g(b)), q(b,g(b)), q(a,g(g(b)))}

それによって修正点に到達します。

ここで、あなたが提案したルールを別の例として取り上げます

q(X, g(g(g(X)))) :- q(X, g(X)).

1 つのステップで生成することを許可するもの (インスタンス化されたルールは表示しません):

{q(a,g(b)), q(b,g(b)), q(a,g(g(g(b)))), q(b, g(g(g(b))))}

しかし、これで終わりではありません。繰り返しますが、ルールを適用してさらに生産することができるからです。実際、これで無限モデルが完成しました。

{g(a,g n+1 (b)), g(b, g n+1 (b))}

この右から左への読み方は、Prolog の再帰規則を理解しようとするときに非常に役立ちます。特に、トップダウンの読み取り (左から右) は、後戻りと一般的な統一を考慮する必要があるため、非常に難しいことがよくあります。

于 2014-01-27T20:26:52.343 に答える
3

あなたの質問に関して：

「また、Herbrand モデルは Herbrand ベースのサブセットであるため、帰納法によって最小の Herbrand モデルを決定するにはどうすればよいでしょうか?」

ホルン節の集合 P である確定プログラムがある場合、プログラム演算子を定義できます。

T_P(M) := { H S | S is ground substitution, (H :- B) in P and B S in M }

最小のモデルは次のとおりです。

inf(P) := intersect { M | M |= P }

定形プログラムのすべてのモデルがプログラム オペレータの固定点であるとは限らないことに注意してください。たとえば、完全なハーブランド モデルは常にプログラム P のモデルであり、これは明確なプログラムが常に一貫していることを示していますが、必ずしも固定点であるとは限りません。

一方、プログラム演算子の各不動点は、明確なプログラムのモデルです。つまり、T_P(M) = M の場合、M |= P と結論付けることができます。そのため、さらに数学的推論 (*) を行った後、最小の固定点は最小のモデルでもあることがわかります。

lfp(T_P) = inf(P)

しかし、ある種の計算によって最小のモデルを決定できると言えるようにするには、さらにいくつかの考慮事項が必要です。つまり、ホーン節はその本体に forall 量指定子を持っていないので、プログラム演算子が連続している、つまりチェーンの無限結合を保持していることを簡単に観察できます。

union_i T_P(M_i) = T_P(union_i M_i)

そのため、さらに数学的推論 (*) を行った後、反復によって最小の固定点を計算できることがわかり、簡単な帰納法に魔女を使用できます。最小モデルのすべての要素には、有限の深さの単純な導出があります。

union_i T_P^i({}) = lpf(T_P)

さよなら

(*) おそらく、この本で必要とされる正確な数学的推論に関するさらなるヒントを見つけることができますが、残念ながらどのセクションが関連しているか思い出せません:
Foundations of Logic Programming、John Wylie Lloyd、1984
http://www.amazon.de /Foundations-Programming-Computation-Artificial-Intelligence/dp/3642968287

于 2014-02-02T17:55:37.047 に答える