論理プログラミング

論理プログラミングは、形式論理に基づいたプログラミング、データベース、および知識表現パラダイムです。論理プログラムは、ある問題領域に関する知識を表す論理形式の文の集合です。その知識に論理的推論を適用して計算を実行し、領域内の問題を解決します。主要な論理プログラミング言語ファミリには、Prolog、Answer Set Programming (ASP)、およびDatalogがあります。これらすべての言語では、ルールは節の形式で記述されます。

A :- B1, ..., Bn.

論理形式では陳述文として読まれます。

A if B1 and ... and Bn.

Aはルールのヘッドと呼ばれ、、 ...はボディと呼ばれ、はリテラルまたは条件と呼ばれます。n = 0 の場合、ルールはファクトと呼ばれ、簡略化された形式で記述されます。 B1BnBi

A.

クエリ (または目標) はルール本体と同じ構文を持ち、通常は次の形式で記述されます。

?- B1, ..., Bn.

最も単純なHorn 節(または「明確な」節)の場合、A、B ₁、...、B _{nはすべて p(t 1}、...、t _m )という形式の原子式です。ここで、p は「母性」などの関係を表す述語記号で、t _{i は}オブジェクト (または個人) を表す項です。項には、「charles」などの定数記号と、大文字で始まる X などの変数の両方が含まれます。

たとえば、次のホーン節プログラムを考えてみましょう。

mother_child (エリザベス、 チャールズ)。
father_child (チャールズ、 ウィリアム)。
father_child (チャールズ、 ハリー)。
parent_child ( X 、 Y )  :-  
     mother_child ( X 、 Y )。
parent_child ( X 、Y ) :- father_child ( X 、Y )。grandparent_child ( X 、Y ) :- parent_child ( X 、Z )、parent_child ( Z 、Y )。   
      
   
       
      

クエリが与えられると、プログラムは回答を生成します。例えば、クエリ の場合 ?- parent_child(X, william)、単一の回答は次のようになります。

X  = チャールズ

さまざまなクエリを実行できます。たとえば、祖父母を生成するクエリと孫を生成するクエリの両方を実行できます。孫と祖父母のすべてのペアを生成するために使用することも、単に特定のペアがそのようなペアであるかどうかを確認するために使用することもできます。

祖父母の子供( X 、 ウィリアム). 
X  = エリザベス

?-  grandparent_child (エリザベス、 Y ) 
。Y  = ウィリアム、
Y  = ハリー。

?-  grandparent_child ( X 、 Y ) 
。X =エリザベスY =ウィリアム; X =エリザベス Y =ハリー。 
  
  
  

?-  grandparent_child (ウィリアム、 ハリー)。
いいえ
?-  grandparent_child (エリザベス、 ハリー)。
はい

ホーン節論理プログラムはチューリング完全であるが^{[1] [2]、}ほとんどの実用的なアプリケーションでは、ホーン節プログラムを負の条件を持つ「通常の」論理プログラムに拡張する必要がある。たとえば、兄弟の定義では負の条件が使用され、述語= は節によって定義されます X = X 。

兄弟( X 、 Y )  :- 
     親の子( Z 、 X )、 
     親の子( Z 、 Y )、 
     ( X = Y )ではありません。  

否定条件を含む論理プログラミング言語は、非単調論理の知識表現機能を備えています。

ASP および Datalog では、ロジック プログラムには宣言的な読み取りのみがあり、その実行は、動作がプログラマによって制御されることを意図していない証明手順またはモデル ジェネレーターによって行われます。ただし、Prolog ファミリーの言語では、ロジック プログラムには、目標削減手順としての手続き型解釈もあります。この観点から、節 A :- B ₁ ,...,B _{n は}次のように理解されます。

解決してA、解決して、そして…解決する。B1Bn

節の本体にある否定条件にも手続き的な解釈があり、これは「失敗としての否定 not B」として知られています。つまり、肯定的なリテラルが成立しない場合にのみ、否定的なリテラルが成立 Bすると見なされます。

論理プログラミングの分野における研究の多くは、否定を失敗として論理的な意味論で表現することや、否定の他の意味論や実装を開発することに取り組んできました。これらの開発は、論理ベースのプログラム検証やプログラム変換のための形式手法の開発をサポートする上で重要でした。

コンピュータ プログラムを表現および実行するために数学的論理を使用するのは、1930 年代にアロンゾ チャーチが開発したラムダ計算の特徴でもあります。しかし、コンピュータ プログラムを表現するために節形式の論理を使用する最初の提案は、コーデル グリーンによって行われました。^{[3]これは、} LISPのサブセットの公理化と入出力関係の表現を使用して、LISP でのプログラム実行をシミュレートすることで関係を計算しました。一方、フォスターとエルコックのAbsys は、演算が実行される順序に制約を課さないアサーション プログラミング言語で、方程式とラムダ計算の組み合わせを採用しました。 ^[4]

事実とルールからなる現在の構文を持つ論理プログラミングは、人工知能における知識の宣言的表現と手続き的表現をめぐる1960年代後半から1970年代前半の論争にまで遡ることができる。宣言的表現の支持者は、ジョン・マッカーシー、バートラム・ラファエル、コーデル・グリーンらと連携したスタンフォード大学や、ジョン・アラン・ロビンソン（シラキュース大学からの客員研究者）、パット・ヘイズ、ロバート・コワルスキーらとエディンバラ大学で活動していたことが知られている。手続き的表現の支持者は主に、マービン・ミンスキーとシーモア・パパートの指導の下、MITに集中していた。^[5]

MITのCarl Hewittが開発したPlannerは、論理の証明方法に基づいていたが、この手続き型パラダイム内で登場した最初の言語だった。^[6] Plannerは、ゴール（ゴール削減または後方連鎖）およびアサーション（前方連鎖）からの手続き型プランのパターン指向呼び出しを特徴としていた。 Plannerの最も影響力のある実装は、 Gerry Sussman、Eugene Charniak、Terry Winogradによって実装されたPlannerのサブセットであるMicro-Plannerだった。 Winogradは、画期的な自然言語理解プログラムSHRDLUを実装するためにMicro-Plannerを使用した。^[7]効率性のために、Plannerはバックトラッキング制御構造を使用して、一度に格納できる計算パスは1つだけにした。 Plannerは、プログラミング言語QA4、^[8] Popler、^[9] Conniver、^[10] QLISP、^[11]および並行言語Etherを生み出した。^[12]

エディンバラのヘイズとコワルスキーは、知識表現に対する論理ベースの宣言的アプローチとプランナーの手続き型アプローチを調和させようとした。ヘイズ（1973）は、定理証明器の動作を変更することで異なる手順を得ることができる等式言語Goluxを開発した。^[13]

その頃、マルセイユのアラン・コルメローは、論理を使って意味を表現し、解像度を使って質問に応答する自然言語理解の研究をしていた。1971年の夏、コルメローはコワルスキーをマルセイユに招待し、2人は共同で、論理の節形式を使って形式文法を表現できること、解像度定理証明器を使って構文解析できることを発見した。彼らは、ハイパー解像度^[14]のような定理証明器はボトムアップパーサーとして動作し、SL解像度（1971）^[15]のような定理証明器はトップダウンパーサーとして動作することを観察した。

翌1972年の夏、コワルスキーは再びコルメラウアーと共同で、節形式の含意の手続き的解釈を開発した。また、そのような節は定節またはホーン節に限定できること、SL解決はSLD解決に限定（および一般化）できることも明らかになった。コワルスキーの手続き的解釈とSLDは、1974年に出版された1973年のメモで説明されている。^[16]

ColmerauerはPhilippe Rousselとともに、手続き型解釈をPrologの基礎として使い、1972年の夏から秋にかけて実装された。1972年に書かれマルセイユで実装された最初のPrologプログラムは、フランスの質問応答システムだった。実用的なプログラミング言語としてのPrologの使用は、 1977年にエディンバラでDavid HD Warrenがコンパイラを開発したことで大きな弾みがついた。実験により、エディンバラPrologはLispなどの他の記号プログラミング言語の処理速度に匹敵することが実証された。^{[17]エディンバラPrologは}事実上の標準となり、 ISO標準Prologの定義に大きな影響を与えた。

論理プログラミングは、1980年代に日本の 通商産業省が第5世代コンピュータシステム(FGCS) プロジェクトのソフトウェア開発に採用したことにより、国際的な注目を集めました。FGCS プロジェクトは、論理プログラミングを使用して、超並列コンピュータ上で高度な人工知能アプリケーションを開発することを目的としていました。プロジェクトでは当初 Prolog の使用を検討していましたが、後にFGCS コンピュータ アーキテクチャに近い並行論理プログラミングの使用が採用されました。

しかし、並行論理プログラミングのコミット選択機能は、言語の論理的意味論^[18]と知識表現および問題解決アプリケーションへの適合性を妨げました。さらに、プロジェクトで開発された並列コンピュータシステムは、より一般的な汎用コンピュータの開発の進歩と競争できませんでした。これら2つの問題が相まって、FGCSプロジェクトは目標を達成できませんでした。論理プログラミングとAIの両方への関心は世界中で低下しました。^[19]

その一方で、Prologの使用に基づくものを含む、より宣言的な論理プログラミングアプローチは、FGCSプロジェクトとは独立して進歩を続けました。特に、Prologは知識の宣言的表現と手続き的表現を組み合わせるために開発されましたが、論理プログラムの純粋に宣言的な解釈は、演繹データベースの分野での応用の焦点となりました。この分野の研究は、Hervé GallaireとJack Minkerがトゥールーズで論理とデータベースに関するワークショップを開催した1977年頃に顕著になりました。 ^{[20]この分野は最終的に}Datalogに改名されました。

論理プログラムの論理的かつ宣言的な読み取りに焦点を当てたこの考え方は、1980年代の制約論理プログラミングと1990年代の回答セットプログラミングの発展によってさらに推進されました。これは、Prologの最近の応用でも再び重視されています^[21]

論理プログラミング協会（ALP）は、論理プログラミングを促進するために1986年に設立されました。2000年までの公式ジャーナルはThe Journal of Logic Programmingでした。創刊編集長はJ. Alan Robinsonでした。^[22] 2001年に、ジャーナルはThe Journal of Logic and Algebraic Programmingに改名され、ALPの公式ジャーナルはCambridge University Pressから出版されているTheory and Practice of Logic Programmingになりました。

論理プログラムは、プログラミング、データベース、知識表現、問題解決など、幅広い分野で応用されているだけでなく、多様なセマンティクスと問題解決方法を備えています。

論理プログラムの手続き的解釈は、後方推論を使用して目標をサブ目標に減らすものであり、問​​題解決戦略を使用して、宣言的かつ論理的な知識表現の使用を制御し、アルゴリズムの動作を取得する特殊なケースです。より一般的には、同じ論理表現に異なる問題解決戦略を適用して、異なるアルゴリズムを取得できます。または、異なる論理表現を使用することで、特定の問題解決戦略で異なるアルゴリズムを取得することもできます。^[23]

主な問題解決戦略は、後方推論（目標削減）と前方推論の 2 つで、それぞれトップダウン推論とボトムアップ推論とも呼ばれます。

命題ホーン節プログラムとトップレベルのアトミック目標の単純なケースでは、後方推論によってand-or ツリーが決定され、これが目標を解決するための検索空間を構成します。トップレベルの目標はツリーのルートです。ツリー内の任意のノードと、そのノードに一致するヘッドを持つ任意の節が与えられると、節の本体のサブ目標に対応する子ノードのセットが存在します。これらの子ノードは、「and」によってグループ化されます。ノードを解決する代替方法に対応する代替の子のセットは、「or」によってグループ化されます。

この空間を探索するためには、任意の探索戦略を使用することができます。Prologは、一度に1つの選択肢と1つのサブゴールのみを検討する、シーケンシャル、後入れ先出し、バックトラッキング戦略を使用します。たとえば、サブゴールは並列に解決でき、節も並列に試すことができます。最初の戦略は、と並列であり、2番目の戦略はまたは並列。インテリジェントバックトラッキング^[24]や最適解を見つけるためのベストファーストサーチ^[25]も可能である。

より一般的な非命題的なケースでは、サブゴールが変数を共有できるため、最もインスタンス化されているサブゴールや、1つの手順のみが適用されるように十分にインスタンス化されているサブゴールを選択するなどの他の戦略を使用できます。^{[26]このような戦略は、たとえば}並行論理プログラミングで使用されます。

ほとんどの場合、クエリまたは目標からの逆推論は、順推論よりも効率的です。ただし、データログと回答セット プログラミングでは、全体としての句のセットから切り離されたクエリが存在しない場合があります。その場合は、句から導き出せるすべての事実を生成することが、問題解決の賢明な戦略となります。次に、 n^番目のフィボナッチ数を ?- fibonacci(n, Result)見つけることを目標とする、より一般的な計算タスクで、順推論が逆推論に勝る別の例を示します。

フィボナッチ( 0 ,  0 )。
フィボナッチ( 1 ,  1 )。

fibonacci ( N 、 結果)  :- 
    N  >  1 、
    N1 は N  -  1 、
    N2 は N  -  2 、
    fibonacci ( N1 、 F1 )、
    fibonacci ( N2 、 F2 )、
    結果は F1 + F2です 。  

ここで、関係 はfibonacci(N, M)関数 を表しfibonacci(N) = M、述語 はN is Expression変数をNの値にインスタンス化する述語の Prolog 表記ですExpression。

のフィボナッチ数を計算するという目標を与えられた場合n、後方推論により、その目標は、n-1 と n-2 のフィボナッチ数を計算するという 2 つのサブ目標に縮小されます。これにより、n-1 のフィボナッチ数を計算するというサブ目標が、n-2 と n-3 のフィボナッチ数を計算するという 2 つのサブ目標に縮小され、n-2 のフィボナッチ数が冗長的に計算されます。1 つのフィボナッチ サブ目標を 2 つのフィボナッチ サブ目標に縮小するこのプロセスは、数 0 と 1 に到達するまで続行されます。その複雑度は 2 ⁿのオーダーです。対照的に、前方推論では、0 と 1 から始めて再計算なしでフィボナッチ数列を生成し、その複雑度は n に関して線形です。

Prologは直接前向き推論を行うことはできません。しかし、テーブル化によって後ろ向き推論のコンテキスト内で前向き推論の効果を達成することができます。サブゴールは、その解決策とともにテーブルに保持されます。サブゴールが再び発生した場合、サブゴールを冗長に再解決するのではなく、テーブルにすでに存在する解決策を使用して直接解決されます。^[27]

論理プログラミングは関数型プログラミングの一般化と見なすことができ、関数は関係の特殊なケースです。^[28]たとえば、関数 mother(X) = Y (すべての X には 1 つの母 Y しかありません) は、関係 mother(X, Y) で表すことができます。この点で、論理プログラムは、関数を関係として表す リレーショナル データベース に似ています。

関係構文と比較すると、関数構文はネストされた関数に対してよりコンパクトです。たとえば、関数構文では、母方の祖母の定義はネストされた形式で記述できます。

母方の祖母( X )  = 母親(母親( X ) )。

リレーショナル表記法での同じ定義は、ネストされていないフラット化された形式で記述する必要があります。

maternal_grandmother ( X ,  Y )  :-  mother ( X ,  Z )、 mother ( Z ,  Y )。

しかし、ネストされた構文は、ネストされていない構文の糖衣構文とみなすことができます。たとえば、 Ciao Prologは、関数型構文をリレーショナル形式に変換し、結果として得られるロジックプログラムを標準のProlog実行戦略を使用して実行します。^[29]さらに、同じ変換を使用して、関数型ではないネストされた関係を実行することもできます。たとえば、

祖父母( X )  := 親(親( X ) )。
親( X )  := 母( X )。
親( X )  := 父( X )。

母(チャールズ)  := エリザベス。
父(チャールズ)  := フィリップ。
母(ハリー)  := ダイアナ。
父(ハリー)  := チャールズ。

?  -祖父母( X 、Y ) 
。X  = ハリー、
Y  = エリザベス。X 
=ハリー 、Y =フィリップ。 
  

リレーショナルプログラミングという用語は、関数を関係の特別なケースとして扱うさまざまなプログラミング言語を指すために使われてきました。miniKanren ^[28] やリレーショナル線形計画法^[30]などの言語は、 この記事の意味での論理プログラミング言語です。

しかし、リレーショナル言語RMLは命令型プログラミング言語 ^[31]であり、その中核構造はリレーショナル式であり、これは一階述語論理の式に似ています。

他のリレーショナルプログラミング言語は、リレーショナル計算^{[32]またはリレーショナル代数[33]}に基づいています。

純粋に論理的な観点から見ると、ホーン節論理プログラムの宣言的意味論には 2 つのアプローチがあります。1 つは、目標の解決を、目標がプログラムのすべてのモデルで真である定理であることを示すことと理解する、元の論理的帰結意味論です。

このアプローチでは、計算は一階述語論理における定理証明であり、SLD 解決のような後方推論と超解決のような前方推論は両方とも正しく完全な定理証明方法です。このような定理証明方法は、論理プログラムに別の証明理論的 (または操作的) 意味論を提供するものと見なされることもあります。しかし、論理的な観点からは、それらは意味論ではなく証明方法です。

ホーン節プログラムの宣言的意味論に対するもう 1 つのアプローチは、充足可能性意味論です。これは、目標の解決を、プログラムの何らかの意図された (または標準的な) モデルで目標が真である (または満たされている) ことを示すことと理解します。ホーン節プログラムの場合、常にこのような標準モデルが存在します。これは、プログラムの 唯一の最小モデルです。

非公式に言えば、最小モデルとは、モデル内で真であるすべての（変数のない）事実の集合として見た場合、プログラムのモデルでもあるより小さな事実の集合を含まないモデルです。

たとえば、次の事実は、この記事の冒頭にある家族関係の例の最小モデルを表しています。その他の変数のない事実はすべて、モデルでは偽です。

mother_child (エリザベス、 チャールズ) 
。father_child (チャールズ、ウィリアム) 。father_child (チャールズ、ハリー) 。parent_child (エリザベス、チャールズ) 。parent_child (チャールズ、ウィリアム) 。parent_child (チャールズ、ハリー) 。grandparent_child  (エリザベス、ウィリアム) 。grandparent_child (エリザベス、ハリー) 。
 
 
 
 
 
 

充足可能性セマンティクスには、プログラム内のルールを使用して 1 ステップの推論で既存の事実から新しい事実を導き出す関数の 最小固定点として、より数学的な別の特徴付けもあります。

注目すべきことに、もともと論理的帰結意味論のために開発された前向き推論と後ろ向き推論という同じ問題解決方法が、充足可能性意味論にも同様に当てはまる。前向き推論は、新たな事実を既存の事実から導き出し、新たな事実が生成されなくなるまで、ホーン節プログラムの最小モデルを生成する。後ろ向き推論は、すべてのサブゴールが事実によって解決されるまで、目標をサブゴールに縮小することで成功し、モデルを明示的に生成することなく、目標が最小モデルで真であることを保証する。^[34]

2 つの宣言的意味論の違いは、自然数をという形式の項の列として表す後続算術における加算と乗算の定義で確認できます。一般に、項は の後続、つまりを表します。関数表記法における加算と乗算の標準的な定義は次のとおりです。 0, 1, 2, ...0, s(0), s(s(0)), ...s(X)X,X + 1.

     X + 0 = X.
     X + s(Y) = s(X + Y) です。
つまり、X + (Y + 1) = (X + Y) + 1

     X × 0 = 0です。
     X × s(Y) = X + (X × Y) です。
つまり、X × (Y + 1) = X + (X × Y) となります。

add(X, Y, Z)以下は、を表すために を使用しX + Y = Z,、multiply(X, Y, Z)を表すために を使用した、論理プログラムと同じ定義ですX × Y = Z。

( X 、 0 、 X )を追加します。
( X 、s ( Y )、s ( Z ) )を追加します:- ( X 、Y 、Z )を追加します。      

( X ,  0 ,  0 )を掛けます。
( X , s ( Y ), W )を掛けます:- ( X , Y , Z )を掛け、( X , Z , W )を加算します。         

2 つの宣言的意味論はどちらも、加算と乗算の目標の同じ存在量化された連言に対して同じ答えを返します。たとえば、 には2 × 2 = X解 がありX = 4、 にはX × X = X + X2 つの解X = 0と がありますX = 2。

?-  ( s ( s ( 0 )), s ( s ( 0 )), Xを掛けます。X = s ( s ( s ( s ( 0 ))))。  
  

?-  ( X 、X 、Y )を掛け、( X 、X 、Y )を加算します。X = 0 、Y = 0。X = s ( s ( 0 ))、Y = s ( s ( s ( s ( 0 ) )))。     
     
     

add(s(s(0)), s(s(0)), s(s(s(s(s(0)))))),ただし、論理的帰結意味論では、たとえばieが真であるようなプログラムの非標準モデルが存在します2 + 2 = 5。しかし、充足可能性意味論では、 が偽である算術の標準モデルという 1 つのモデルのみ存在します2 + 2 = 5。

どちらのセマンティクスでも、目標は失敗します。充足可能性セマンティクスでは、目標の失敗は目標の真理値が偽であることを意味します。しかし、論理的帰結セマンティクスでは、失敗は目標の真理値が不明であることを意味します。 ?- add(s(s(0)), s(s(0)), s(s(s(s(s(0))))))

否定の失敗not p(NAF) は、肯定条件が成立しないことを示すことによって否定条件が成立すると結論付ける方法として、初期の Prolog システムの機能としてすでに存在していました。結果として生じるSLD 解決pの拡張はSLDNFと呼ばれます。同様の構造である「thnot」は、 Micro-Plannerにも存在していました。

NAFの論理的意味論は、キース・クラーク^[35]が、ある自然条件下では、NAFは一階述語論理における論理プログラムの 完成を用いた論理的帰結意味論による効率的で正しい（そして時には完全な）推論方法であることを示すまで未解決であった。

完了とは、大まかに言うと、ヘッドに同じ述語を持つすべてのプログラム節の集合を考慮することです。

A :- Body1.

...

A :- Bodyk.

述語の定義として:

A iff (Body1 or ... or Bodyk)

ここで、 はiff「 の場合のみ 」を意味します。この補完には、統一に対応する等式公理も含まれます。クラークは、SLDNF によって生成された証明は、プログラムの補完による自然演繹スタイルの推論によって生成された証明と構造的に類似していることを示しました。

たとえば、次のプログラムを考えてみましょう。

should_receive_sanction ( X 、 罰)  :-  
    is_a_thief ( X ) であり、
    should_receive_sanction ( X 、更生)ではありません 。 
    
should_receive_sanction ( X 、 rehabilitation )  :- 
    is_a_thief ( X )、
    is_a_minor ( X )、
    is_violent ( X )ではありません 。
    
泥棒です(トム)。

トムが制裁を受けるべきかどうかを判断するという目標を考えると、最初のルールはトムが罰せられるべきであることを示すことに成功しています。

?-  should_receive_sanction ( tom 、 Sanction )。
Sanction  = 罰則。

これは、トムが泥棒であり、トムが更生すべきであると証明できないためです。トムが未成年であることを証明できないため、トムが更生すべきであると証明することはできません。

しかし、トムが実際に未成年であるという新しい情報を受け取った場合、トムは処罰されるべきであるという以前の結論は、トムは更生されるべきであるという新しい結論に置き換えられます。

マイナー（トム）。

?-  should_receive_sanction ( tom 、 Sanction ) 。
Sanction  =  rehabilitation 。

新しい情報が追加されたときに結論を撤回するこの特性は非単調性と呼ばれ、論理プログラミングを非単調論理にします。

しかし、もし今トムが暴力的だと言われると、トムは罰せられるべきだという結論が復活するでしょう。

暴力的（トム）。

?-  should_receive_sanction ( tom 、 Sanction )。
Sanction  = 罰則。

このプログラムの完了は次のとおりです。

should_receive_sanction ( X 、 Sanction ) の場合のみ、 
    Sanction  =  punishment 、 is_a_thief ( X ) であり、 
    should_receive_sanction ( X 、 rehabilitation ) ではない 、またはSanction =  rehabilitation 、
 is_a_thief  (  X  ) 、 is_a_minor ( X ) であり、is_violent 
    ( X )ではない 。
    
is_a_thief ( X ) の場合、 X  =  tomです。is_a_minor 
( X )の場合、X = tomです。is_violent ( X )の場合、X = tomです。    
    

完了の概念は、ジョン・マッカーシーの デフォルト推論のための限定意味論^[36]やレイ・ライターの 閉世界仮定^[37]と密接に関連している。

否定の完了セマンティクスは論理的帰結セマンティクスであり、SLDNF はこれに対して証明理論的実装を提供します。しかし、1980 年代には、否定を含む論理プログラムでは充足可能性セマンティクスが一般的になりました。充足可能性セマンティクスでは、否定は論理プログラムの意図されたモデルまたは標準モデルにおける真理の古典的な定義に従って解釈されます。

否定条件を伴う論理プログラムの場合、充足可能性意味論には主に2つのバリエーションがある。well -founded semanticsでは、論理プログラムの意図されたモデルは常に存在する唯一の3値極小モデルである。well-founded semanticsは、数理論理学における帰納的定義の概念を一般化したものである。 ^[38] XSB Prolog ^[39]は、SLG解決を使用してwell-founded semanticsを実装している。^[40]

代替の安定したモデル セマンティクスでは、対象モデルがまったく存在しないか、または対象モデルが複数存在し、そのすべてが最小かつ 2 値である可能性があります。安定したモデル セマンティクスは、回答セット プログラミング(ASP) の基盤となります。

妥当なモデルと安定したモデルの両方のセマンティクスは、否定を含む任意の論理プログラムに適用されます。ただし、両方のセマンティクスは、階層化された論理プログラムでは一致します。たとえば、泥棒を処罰するプログラムは (ローカルに) 階層化されており、プログラムの 3 つのセマンティクスはすべて、同じ意図されたモデルを決定します。

制裁を受けるべき(トム、 罰)。
泥棒である(トム)。
未成年者である(トム)。
暴力的である(トム)。

論理プログラミングにおける否定を理解しようとする試みは、抽象的な議論の枠組みの開発にも貢献してきました。^[41]否定の議論の解釈では、トムは泥棒なので罰せられるべきであるという最初の議論は、彼は未成年なので更生されるべきであるという議論によって攻撃されます。しかし、トムが暴力的であるという事実は、トムは更生されるべきであるという議論を弱め、トムは罰せられるべきであるという議論を復活させます。

プログラムをデータとして扱うメタプログラミングは、初期のProlog実装にすでに備わっていた機能である。 ^{[42] [43]}たとえば、エジンバラDEC10のProlog実装には「Prolog自体で書かれたインタープリタとコンパイラ」が含まれていた。^[43]最も単純なメタプログラムは、いわゆる「バニラ」メタインタープリタである。

    解決します( true )。
    解決します(( B 、C )):- 解決します( B )、解決します( C )。
    解決します( A ):- 句( A 、B )、解決します( B )。

ここで、true は空の論理積を表し、(B,C) は B と C の論理積を表す合成項です。述語節 (A,B) は、形式 A :- B の節があることを意味します。

メタプログラミングは、メタロジックまたはメタ言語のより一般的な使用法の応用であり、オブジェクト言語 と呼ばれる別の言語を記述および推論します。

メタロジックプログラミングでは、自然言語と同様に、オブジェクトレベルとメタレベルの表現を組み合わせることができます。たとえば、次のプログラムでは、原子式はattends(Person, Meeting)オブジェクトレベルの式としてだけでなく、メタ述語prohibitedとapproved.

禁止( (人、会議)に出席する) :-承認( (人、会議)に出席する)ではありません。   
     

should_receive_sanction (人、 叱責)  :- 出席(人、 会議)、 
    高尚(人)、 禁止(出席(人、 会議))。
should_receive_sanction (人、 追放)  :- 出席(人、 会議)、 
    卑しい(人)、 禁止(出席(人、 会議))。

承認されました( ( alice 、tea_party )に出席します)。 ( mad_hatter 、tea_party )に出席します。 ( dormouse 、tea_party )に出席します。 
 
 

高尚な（mad_hatter ）。
卑しい（dormouse ）。

?-  should_receive_sanction ( X 、Y )。
人物 =  mad_hatter 、
制裁 =  scolding 。
人物 =  dormouse 、
制裁 =  banishment 。

ポール・サガードは、彼の有名な著書「認知科学入門」^[44] の中で、人間の思考をモデル化する代替アプローチとして、論理とルールを挙げている。彼は、 IF条件THENアクションという形式のルールは論理条件文に「非常に似ている」が、より単純で、心理学的な妥当性が高いと主張している（51ページ）。論理とルールのその他の違いとして、彼は、論理は演繹を使用するが、ルールは検索を使用する（45ページ）こと、および前向きにも後ろ向きにも推論できる（47ページ）ことなどを挙げている。論理における文は「普遍的に真であると解釈されなければならない」が、ルールは例外を認めるデフォルトになり得る（44ページ）。

彼は、「論理とは異なり、ルールベースのシステムは、何をすべきかという戦略的な情報も簡単に表現できる」と述べています (45 ページ)。たとえば、「週末に家に帰りたい場合、バス代があれば、バスに乗ることができます」。彼は、目標をサブ目標に減らすという同じ戦略が、論理プログラミングのように、論理条件に逆推論を適用することとして解釈できることに気づいていません。

can_go (あなた、 家)  :-  have (あなた、 バス運賃)、 catch (あなた、 バス)。

ルールベース システムのこれらすべての特性 (検索、前方および後方推論、デフォルト推論、目標削減) は、論理プログラミングの定義特性でもあります。これは、Thagard の結論 (56 ページ) を示唆しています。

人間の知識の多くは自然にルールに基づいて記述され、計画などの多くの種類の思考はルールベースのシステムによってモデル化できます。

論理プログラミングにも適用されます。

論理プログラミングが人間の思考の側面をモデル化するためにどのように使用できるかを示す他の議論は、キース・ステニングとミヒール・ファン・ランバルゲンの著書「人間の推論と認知科学」で紹介されています。^[45]彼らは、論理プログラムの非単調な特性が、さまざまな心理的タスクにおける人間のパフォーマンスを説明するためにどのように使用できるかを示しています。彼らはまた、「論理プログラミングの外観を持つ閉世界推論は、古典的な論理とは異なり、魅力的なニューラル実装を持っている」ことも示しています（237ページ）。

『イベントの適切な扱い』^[46]では、 ミヒール・ファン・ランバルゲンとフリッツ・ハムが制約論理プログラミングを使用して「人間が時間を構築する方法に注目して、自然言語で時間の概念をコード化する」ことを調査しています。

手続き的知識と戦略的な情報を表すためにロジックを使用することは、論理プログラミングの初期の開発に貢献した主な目標の 1 つでした。さらに、これは今日でも Prolog ファミリーの論理プログラミング言語の重要な機能であり続けています。ただし、Prolog アプリケーションを含む論理プログラミングの多くのアプリケーションでは、純粋に宣言的な知識を表すためにロジックを使用することにますます重点が置かれています。これらのアプリケーションには、一般的な常識的な知識の表現とドメイン固有の専門知識の表現の両方が含まれます。

常識には、原因と結果についての知識が含まれており、これは、たとえば、状況計算、イベント計算、アクション言語で形式化されています。以下は、このような形式主義の主な特徴を示す単純化された例です。最初の節は、イベントが事実を開始（または原因）した直後に事実が成立することを述べています。2 番目の節はフレーム公理であり、ある時点で成立する事実は、その時点で発生するイベントによって終了されない限り、次の時点でも成立し続けます。この定式化により、複数のイベントが同時に発生することが許可されます。

(事実、 時間2 ) を保持:-  
    (イベント、時間1 )が発生し、時間2 は時間1 + 1になり、(イベント、事実)を開始します。 
        
     
     
( Fact 、 Time2 ) が成立します:-  
	( Event 、Time1 )が発生し、 Time2 はTime1 + 1であり、( Fact 、Time1 )が成立し、 ( ( Fact 、Time1 )が終了しません) 。 
        
     
     

終了(事実、 時間)  :-
   発生(イベント、 時間)、
   終了(イベント、 事実)。

これは上記holdsに似たメタ述語ですsolve。ただし、 にはsolve一般節に適用される引数が 1 つしかないのに対し、 の最初の引数はholds事実であり、2 番目の引数は時間 (または状態) です。原子式は、が で成り立つholds(Fact, Time)ことを表します。このような時間によって変化する事実は、フルーエントとも呼ばれます。原子式は、イベントが で発生することを表します。 FactTimehappens(Event, Time)Time

次の例は、これらの節を使用して、おもちゃのブロックの世界における因果関係について推論する方法を示しています。ここでは、時間 0 の初期状態では、緑のブロックがテーブルの上にあり、赤いブロックが緑のブロックの上に積み重ねられています (信号機のように)。時間 0 では、赤いブロックがテーブルに移動されます。時間 1 では、緑のブロックが赤いブロックの上に移動されます。オブジェクトを場所に移動すると、オブジェクトが任意の場所にあるという事実は終了し、オブジェクトが移動先の場所にあるという事実が開始されます。

( ( green_block , table )に対して) 0を保持します。( ( red_block , green_block )に対して) 0 を保持します。  
  

発生します( move ( red_block ,  table ),  0 )。
発生します( move ( green_block ,  red_block ),  1 )。

( ( Object , Place )上のmove ( Object , Place )を開始します。 ( ( Object , Place2 )上のmove ( Object , Place1 )を終了します。)   
   

?- は 成り立ちます(事実、 時間)。

ファクト =  on ( green_block 、table )、
時間 =  0。
ファクト =  on ( red_block 、green_block )、
時間 =  0。
ファクト =  on ( green_block 、table )、
時間 =  1。
ファクト =  on ( red_block 、table )、
時間 =  1。
ファクト =  on ( green_block 、red_block )、
時間 =  2。
ファクト =  on ( red_block 、table )、
時間 =  2。

前向き推論と後ろ向き推論は目標に対して同じ答えを生成しますholds(Fact, Time)。しかし、前向き推論は時間順に漸進的に流暢性を生成し、後ろ向き推論は状況計算における回帰のドメイン固有の使用のように退行的に流暢性を生成します。^[47]

論理プログラミングは、エキスパートシステムでドメイン固有の専門知識を表現するのにも役立つことが証明されています。^[48]しかし、人間の専門知識は、汎用的な常識と同様に、ほとんどが暗黙的かつ暗黙的であり、そのような暗黙の知識を明示的なルールで表現することは難しいことがよくあります。ただし、論理プログラムを使用してビジネス組織や法的機関の既存の明示的なルールを表現する場合は、この困難は発生しません。

たとえば、以下は英国国籍法の最初の文の簡略版の表現です。この文では、英国で生まれた人は、出生時に親が英国国民である場合、出生時に英国国民になると規定されています。

( birth ( Person )、 citizen ( Person 、 uk ) )を開始します:- 
    time_of ( birth ( Person )、 Time )、
    place_of ( birth ( Person )、 uk )、
    parent_child ( Another_Person 、 Person )、
    holdings ( civil ( Another_Person 、 uk )、 Time )。

歴史的には、1980年代に英国国籍法の大部分を論理プログラムとして表現したことは^[49]、「立法の計算表現の開発に大きな影響を与え、論理プログラミングによって、自動推論を生成するために直接展開できる直感的に魅力的な表現が可能になることを示しました」^{[50] 。}

最近では、2009年に開始され、日本の民法と最高裁判所の判例の約2500の規則と例外から構成されるPROLEGシステム^[51]が、おそらく世界最大の法的ルールベースとなっています。^[52]

SLD 解決推論規則は、節の本体のサブゴールを解決のために選択できる順序については中立です。効率性のため、Prolog はこの順序をサブゴールが記述されている順序に制限します。SLD は、SLD 証明の空間を検索する戦略についても中立です。Prolog はこの空間をトップダウン、深さ優先で検索し、節が記述されている順序で同じ (サブ) ゴールを解決するためにさまざまな節を試します。

この検索戦略の利点は、ツリーの現在のブランチをスタックによって効率的に表現できることです。スタックの最上部にある目標節が新しい目標節に縮小されると、新しい目標節がスタックの最上部にプッシュされます。スタックの最上部にある目標節内の選択されたサブゴールを解決できない場合、検索戦略はバックトラックし、スタックの最上部から目標節を削除し、選択されたサブゴールに一致する次の節を使用して、前の目標節内の選択されたサブゴールの解決を再試行します。

バックトラックは、常に成功するがバックトラックできない、 cutと呼ばれるサブゴール ( ! と記述) を使用することで制限できます。cut は効率性を向上させるために使用できますが、節の論理的な意味を妨げることもあります。多くの場合、cut の使用は、失敗としての否定に置き換えることができます。実際、失敗としての否定は、Prolog で cut と、no 節のヘッドと統合する failなどの任意のリテラルを使用することで定義できます。

( P )では ありません:-  P 、 !、 失敗。
( P )ではありません。

Prolog は、cut に加えて、論理的な解釈を持たない他の機能も提供します。これには、プログラム実行中にプログラムの状態を破壊的に更新するための組み込み述語assertとretract が含まれます。

たとえば、上記のおもちゃのブロックの世界の例は、破壊的な状態の変化を使用してフレーム公理なしで実装できます。

( green_block 、 table )
の場合。 ( red_block 、green_block )の場合。 

move ( Object 、 Place2 )  :-  
	retract ( on ( Object 、 Place1 ))、 
	assert ( on ( Object 、 Place2 )。

移動イベントのシーケンスとブロックの結果の位置は、次のクエリを実行することによって計算できます。

?-  ( red_block 、table )を移動し、( green_block 、red_block )を移動し、 ( Object 、Place )に移動します。     

オブジェクト =  red_block 、
場所 =  table 。
オブジェクト =  green_block 、
場所 =  red_block 。

このような破壊的な状態変化のための論理フレームワークを提供するために、論理プログラミングのさまざまな拡張が開発されてきました。^{[53] [54] [55]}

Prologの単独および他の言語との組み合わせでの幅広い応用は、2022年のProlog生誕50周年を記念した 「Year of Prolog Book ^{」[21]で強調されています。}

Prolog は、ALF 、 Fril、Gödel、Mercury、Oz、Ciao、Visual Prolog、XSB、λPrologなど、他のプログラミング言語の開発にも貢献しています。

制約論理プログラミング(CLP) は、ホーン節論理プログラミングと制約解決を組み合わせたものです。制約述語として宣言された一部の述語を節の本体でリテラルとして出現できるようにすることで、ホーン節を拡張します。制約述語は、プログラム内の事実やルールによって定義されるのではなく、ドメイン固有のモデル理論構造または理論によって事前に定義されます。

手続き的には、述語がプログラムによって定義されているサブゴールは、通常の論理プログラミングと同様にゴール削減によって解決されますが、制約は、制約述語のセマンティクスを実装するドメイン固有の制約ソルバーによって簡略化され、充足可能性がチェックされます。初期問題は、制約の充足可能な結合に削減することによって解決されます。

興味深いことに、Prologの最初のバージョンには、フィリップ・ルーセルの1972年の博士論文からの制約述語dif(term1, term2)がすでに含まれていました。これは、両方の引数が異なる項である場合に成功しますが、いずれかの項に変数が含まれている場合は遅延します。^[52]

john's次の制約ロジック プログラムは、教師としての歴史 のおもちゃの時間データベースを表します。

教える(ジョン、 ハードウェア、 T )  :-  1990  ≤  T 、 T  <  1999。
教える(ジョン、 ソフトウェア、 T )  :-  1999  ≤  T 、 T  <  2005。
教える(ジョン、 ロジック、 T )  :-  2005  ≤  T 、 T  ≤  2012。
ランク(ジョン、 インストラクター、 T )  :-  1990  ≤  T 、 T  <  2010。
ランク(ジョン、 教授、 T )  :-  2010  ≤  T 、 T  <  2014。

ここで≤、 と は、<通常の意図された意味を持つ制約述語です。次の目標節は、データベースを照会して、と がjohnいつ教えられlogicたかを調べますprofessor。

?- 教える(ジョン、 論理、 T )、 ランク(ジョン、 教授、 T )。

解決策は 2010 ≤ T, T ≤ 2012 制約を単純化することで得られる 2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.

制約論理プログラミングは、土木工学、機械工学、デジタル回路検証、自動時刻表作成、航空管制、金融などの分野で問題を解決するために使用されてきました。これは、アブダクション論理プログラミングと密接に関連しています。

Datalog は、リレーショナル データベースのようなデータのリレーショナル ビューと、論理プログラミングのような論理ビューを組み合わせたデータベース定義言語です。

リレーショナル データベースは、リレーショナル計算またはリレーショナル代数を使用し、和集合、積集合、差集合、直積などのリレーショナル演算を使用して、データベースにアクセスするクエリを指定します。Datalog は、ルールの本体でor、not などの論理接続子を使用して、関係をデータベース自体の一部として定義します 。

リレーショナルデータベースの開発の初期段階では、再帰クエリはリレーショナル代数でもリレーショナル計算でも表現できないこと、そしてこの欠点は最小固定点演算子を導入することで改善できることが認識されていました。^{[56] [57]}対照的に、再帰関係は、新しい論理接続子や演算子を必要とせずに、論理プログラムのルールによって自然に定義できます。

Datalog は、項として定数と変数のみを使用する点で、より一般的なロジック プログラミングとは異なります。さらに、すべてのファクトは変数フリーであり、ルールは制限されているため、ボトムアップで実行される場合、派生したファクトも変数フリーになります。

たとえば、家族データベースを考えてみましょう。

mother_child (エリザベス、 チャールズ)。
father_child (チャールズ、 ウィリアム)。
father_child (チャールズ、 ハリー)。
parent_child ( X 、 Y )  :-  
     mother_child ( X 、 Y )。
parent_child ( X 、 Y )  :-  
     father_child ( X 、 Y )。
ancestor_descendant ( X 、 Y )  :-  
     parent_child ( X 、 X )。
ancestor_descendant ( X 、 Y )  :-  
     ancestor_descendant ( X 、 Z )、 
     ancestor_descendant ( Z 、 Y )。

ボトムアップ実行では、次の一連の追加事実が導出され、終了します。

親の子(エリザベス、 チャールズ)。
親の子(チャールズ、 ウィリアム)。
親の子(チャールズ、 ハリー)。

祖先の子孫(エリザベス、 チャールズ)。
祖先の子孫(チャールズ、 ウィリアム)。
祖先の子孫(チャールズ、 ハリー)。

祖先の子孫(エリザベス、 ウィリアム)。
祖先の子孫(エリザベス、 ハリー)。

トップダウン実行では、クエリに対して同じ回答が導出されます。

?- 祖先_子孫( X 、 Y )。

しかし、その後、無限ループに入ります。ただし、テーブルを使用したトップダウン実行では、同じ答えが得られ、ループせずに終了します。

Datalog と同様に、Answer Set Programming (ASP) はチューリング完全ではありません。さらに、目標 (またはクエリ) を目標の解決に使用するプログラムから分離するのではなく、ASP はプログラム全体を目標として扱い、目標を真にする安定したモデルを生成することで目標を解決します。この目的のために、安定したモデル セマンティクスを使用します。これによれば、ロジック プログラムは 0、1、または複数の意図されたモデルを持つことができます。たとえば、次のプログラムは、2 つの国を赤または緑に色付けする地図の色付け問題の退化したバリエーションを表しています。

国( oz )。
国( iz )。
隣接( oz 、 iz )。
色( C 、 赤)  :- 国( C ) であり、 ( 色 ( C 、緑 ) ) ではありません。色( C 、 緑) 
: -国(  C ) で あり、(色 ( C 、赤) ) ではありません。

この問題には、4 つの安定したモデルによって表される 4 つの解があります。

国( oz )。 国( iz )。 隣接( oz 、 iz )。 色( oz 、 red )。   色( iz 、 red )。

国( oz )。 国( iz )。 隣接( oz 、 iz )。 色( oz 、 緑)。 色( iz 、 緑)。

国( oz )。 国( iz )。 隣接( oz 、 iz )。 色( oz 、 赤)。   色( iz 、 緑)。

国( oz )。 国( iz )。 隣接( oz 、 iz )。 色( oz 、 緑)。 色( iz 、 赤)。

地図の色付け問題の標準バージョンを表現するには、隣接する 2 つの国を同じ色にできないという制約を追加する必要があります。ASP では、この制約は次の形式の節として記述できます。

:- 国( C1 )、 国( C2 )、 隣接( C1 、 C2 )、 色( C1 、 X )、 色( C2 、 X )。

この制約を追加すると、問題には 2 つの解決策しかなくなります。

国( oz )。 国( iz )。 隣接( oz 、 iz )。 色( oz 、 赤)。   色( iz 、 緑)。

国( oz )。 国( iz )。 隣接( oz 、 iz )。 色( oz 、 緑)。 色( iz 、 赤)。

フォームの制約を追加すると、が真:- Body.であるモデルが削除されますBody。

紛らわしいことに、ASP の制約はCLP の制約とは異なります。 CLP の制約は、クエリに対する回答 (および目標のソリューション) を限定する述語です。 ASP の制約は、目標を満たすモデルを排除する句です。 ASP の制約は、データベースの整合性制約に似ています。

通常の論理プログラミング節と制約節の組み合わせは、ASPにおける問題解決の生成とテストの方法論を示しています。通常の節は可能な解決策の検索空間を定義し、制約は不要な解決策を除外します。^[58]

ASPの実装のほとんどは2つのステップで進みます。まず、プログラムをあらゆる方法でインスタンス化し、命題論理プログラム（グラウンディングと呼ばれる）に還元します。次に、 DPLLアルゴリズムやブールSATソルバーなどの命題論理問題ソルバーを適用します。ただし、s(CASP) ^[59]などの一部の実装では、グラウンディングなしで、目標指向、トップダウン、SLD解決のような手順を使用します。

アブダクティブ論理プログラミング^[60]（ALP）は、CLPと同様に、節の本体に、節によって述語が定義されていないリテラルを含めることができるようにすることで、通常の論理プログラミングを拡張します。ALPでは、これらの述語は、アブダクション可能（または仮定可能）と宣言され、アブダクション推論で観察を説明するために使用されるか、より一般的には、目標を達成するためにプログラムに新しい事実（仮定として）を追加するために使用されます。

たとえば、時刻 0 に赤いブロックがテーブル上の緑のブロックの上にある初期状態が与えられたとします。

( ( green_block , table )に対して) 0を保持します。( ( red_block , green_block )に対して) 0 を保持します。  
  

次のような目標も与えられているとします。

?-  ( ( green_block 、red_block )で、 3 )を保持し、( ( red_block 、table )で、 3 )を保持します。   

目標は観察を表すことができ、その場合、解決策はその観察の説明となる。あるいは目標は望ましい将来の状態を表すことができ、その場合、解決策はその目標を達成するための計画となる。^[61]

happens述語を帰納的として 扱うことで、先に示した原因と結果のルールを使用して目標を達成できます。

(事実、 時間2 ) を保持:-  
    (イベント、時間1 )が発生し、時間2 は時間1 + 1になり、(イベント、事実)を開始します。 
        
     
     
( Fact 、 Time2 ) が成立します:-  
	( Event 、Time1 )が発生し、 Time2 はTime1 + 1であり、( Fact 、Time1 )が成立し、 ( ( Fact 、Time1 )が終了しません) 。 
        
     
     
    
終了(事実、 時間)  :-
   発生(イベント、 時間)、
   終了(イベント、 事実)。

( ( Object , Place )上のmove ( Object , Place )を開始します。 ( ( Object , Place2 )上のmove ( Object , Place1 )を終了します。)