論理プログラミングの構文と意味論

論理プログラミングの多くの実装では、上記の文法を拡張して:-、次のようにカンマなしで事実を記述できるようにしています。

r ( x )

また、多くのライブラリでは、次のように括弧なしで0項関係を記述することもできます。

p :- q 。

これらは単なる省略形（構文糖衣）であり、プログラムの意味には何の影響もありません。

以下のプログラムは、関係 の推移閉包pathである関係 を計算します。edge

edge ( x , y ). edge ( y , z ). path ( A , B ) :- edge ( A , B ). path ( A , C ) :- path ( A , B ), edge ( B , C ).

ルールは、そのすべての原子（ヘッドとボディ）がグラウンドである場合にグラウンドと呼ばれます。グラウンドルールR _2は、R 1_のすべての変数を定数で置換した結果である場合に_、別のルールR _1のグラウンドインスタンスとなります。

Datalog プログラムのHerbrand 基底とは、プログラムに現れる定数を用いて作成できるすべての基本アトムの集合です。解釈(データベース インスタンスとも呼ばれる) は、Herbrand 基底のサブセットです。基本アトムは、解釈Iの要素である場合に、解釈Iにおいて真となります。ルールは、そのルールの各基本インスタンスについて、本体内のすべてのアトムがIにおいて真であれば、ルールのヘッドも I において真である場合に、解釈 I において真となります。

Datalog プログラムPのHerbrand モデルとは、 Pのすべての基本事実を含み、 Pのすべての規則をIで真にするPの解釈I のことである。モデル理論的意味論では、Datalog プログラムの意味は、その最小 Herbrand モデル (同等に、すべての Herbrand モデルの共通部分) であると述べている。^{[ 4 ]}

例えば、このプログラム：

edge ( x , y ). edge ( y , z ). path ( A , B ) :- edge ( A , B ). path ( A , C ) :- path ( A , B ), edge ( B , C ).

ハーブランドの世界はこうだ: x、y、z

そしてこのハーブランドベース: edge(x, x)、edge(x, y)、 ...、edge(z, z)、path(x, x)、 ...、path(z, z)

そしてこの最小限のハーブランドモデル: edge(x, y), edge(y, z), path(x, y), path(y, z),path(x, z)

DatalogプログラムPの解釈の集合をIとする。すなわち、I = P ( H )であり、HはPのヘルブランド基底、Pは冪集合演算子である。Pの直接帰結演算子は、IからIへの次の写像Tである。Pの各ルールの各基底インスタンスについて、本体のすべての節が入力解釈に含まれている場合、基底インスタンスの先頭を出力解釈に追加する。この写像Tは、 T上の部分集合包含によって与えられる半順序に関して単調である。クナスター・タルスキーの定理により、この写像は最小不動点を持つ。クリーネの不動点定理により、不動点は連鎖の上限である。${\displaystyle T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots }$Mの最小不動点は、プログラムの最小ヘルブランドモデルと一致する。^{[ 5 ]}

不動点意味論は、最小ヘルブランドモデルを計算するためのアルゴリズムを示唆している。プログラム内の基本事実の集合から始め、不動点に到達するまで規則の帰結を繰り返し追加していく。このアルゴリズムは、ナイーブ評価と呼ばれる。

プログラムPが与えられたとき、基底原子Aの証明木は、根にAというラベルが付けられ、葉にはPの事実のヘッドからの基底原子というラベルが付けられ、枝には子を持つ木である。${\displaystyle A_{1},\ldots ,A_{n}}$基底原子Gによってラベル付けされ、基底インスタンスが存在する

G :- A1, ..., An.

Pのルールの。証明論的意味論では、Datalog プログラムの意味は、そのような木から導出できる基底原子の集合であると定義される。この集合は最小の Herbrand モデルと一致する。^{[ 6 ]}

Datalog プログラムの最小 Herbrand モデルに特定の基底原子が現れるかどうかを知りたい場合、モデルの残りの部分についてはあまり気にしなくてもよいかもしれません。上記で説明した証明ツリーを上から下へ読み解くと、そのようなクエリの結果を計算するアルゴリズムが示唆され、この読み解がSLD 解決アルゴリズムに情報を提供し、それがPrologの評価の基礎となります。

Datalog のセマンティクスは、より一般的な半環上の不動点の文脈でも研究されている。^{[ 7 ]}

否定を含む論理プログラムは、各関係を何らかの階層に割り当てることが可能であり、関係Rが関係Sの本体で否定されている場合、RはSよりも低い階層にある、という場合に階層化されている。^{[ 9 ]} Datalog のモデル理論的意味論と固定点意味論は、階層化された否定を扱うように拡張でき、そのような拡張は同等であることが証明できる。

Datalogの多くの実装では、固定小数点セマンティクスにヒントを得たボトムアップ評価モデルが採用されています。このセマンティクスは階層的否定を扱うことができるため、Datalogのいくつかの実装では階層的否定が実装されています。

階層化否定は Datalog の一般的な拡張ですが、階層化できない妥当なプログラムも存在します。次のプログラムは、相手に手番がない場合にプレイヤーが勝利する 2 対 2 のゲームを記述しています。^{[ 10 ]}

move ( a , b ). win ( X ) :- move ( X , Y ), not win ( Y ).

aこのプログラムは階層化されていないが、それが試合に勝つための妥当な選択肢であると考えるのは妥当だろう。

安定モデルの意味論は、プログラムの特定のヘルブランドモデルを安定と呼ぶための条件を定義します。直感的に言えば、安定モデルとは、「（プログラム）が与えられた場合に、合理的なエージェントが持ちうる信念の可能な集合」です。^{[ 11 ]}

否定を含むプログラムには、安定モデルが多数存在する場合もあれば、安定モデルが全く存在しない場合もある。例えば、プログラム

p :- qではない。q :- pではない。

2つの安定モデルがあります${\displaystyle \{p\}}$、${\displaystyle \{q\}}$1つのルールに基づくプログラム

p :- pではありません。

安定したモデルがありません。

すべての安定モデルは最小ヘルブランドモデルです。否定を含まないデータログプログラムには、その最小ヘルブランドモデルと全く同じ安定モデルが1つだけ存在します。安定モデルの意味論では、否定を含む論理プログラムの意味は、安定モデルがちょうど1つ存在する場合に、その安定モデルであると定義されます。しかし、プログラムのすべての（または少なくともいくつかの）安定モデルを調査することは有用な場合があります。これが解答集合プログラミングの目的です。