失敗による否定

失敗による否定（しっぱいによるひてい、英: Negation as failure, NAF）は、論理プログラミングで使われる非単調論理的推論規則であり、${\displaystyle p}$ を導出することに失敗したとき ${\displaystyle {\mathit {not}}~p}$ を自動的に導出することである。Planner や Prolog の初期から論理プログラミングの重要な機能となっている。Prolog では、論理構成要素の範囲外として実装されることが多い。

Prolog

純粋な Prolog では、${\displaystyle {\mathit {not}}~p}$ という形式で表される NAF リテラルは節本体に現れ、他の NAF リテラルを導出するのに使われる。例えば、次のような4つの節があるとする。

${\displaystyle p\leftarrow q\land {\mathit {not}}~r}$

${\displaystyle q\leftarrow s}$

${\displaystyle q\leftarrow t}$

${\displaystyle t\leftarrow }$

NAF によれば、${\displaystyle {\mathit {not}}~s}$、${\displaystyle {\mathit {not}}~r}$、${\displaystyle p}$ が導出される。

完全性意味論

NAF の意味論は未解決の問題だったが、Keith Clark (1978) によって論理プログラムの完全性 (completion) の観点で正しいことが示された。大まかに言えば ${\displaystyle \leftarrow }$ は同値すなわち "${\displaystyle \equiv }$" と解釈される。

例えば、上記の4つの節の完全性は次のように表される。

${\displaystyle p\equiv q\land {\mathit {not}}~r}$

${\displaystyle q\equiv s\lor t}$

${\displaystyle t\equiv {\mathit {true}}}$

${\displaystyle r\equiv {\mathit {false}}}$

${\displaystyle s\equiv {\mathit {false}}}$

推論規則としての NAF は完全性による明示的な推論をシミュレートする。ここで等式の両辺が否定され、右辺の否定が原子論理式にまで分配される。例えば、${\displaystyle {\mathit {not}}~p}$ であることを示すには、NAF は上記等式群に関する次の推論をシミュレートする。

${\displaystyle {\mathit {not}}~p\equiv {\mathit {not}}~q\lor r}$

${\displaystyle {\mathit {not}}~q\equiv {\mathit {not}}~s\land {\mathit {not}}~t}$

${\displaystyle {\mathit {not}}~t\equiv {\mathit {false}}}$

${\displaystyle {\mathit {not}}~r\equiv {\mathit {true}}}$

${\displaystyle {\mathit {not}}~s\equiv {\mathit {true}}}$

命題論理的でない場合、別の名を持つ個体項は別の項であるという前提を形式化するため、完全性は等価性公理にまで敷衍される必要がある。NAF ではこれをユニフィケーションの失敗でシミュレートする。例えば、次の2つの節だけがあるとする。

${\displaystyle p(a)\leftarrow }$
${\displaystyle p(b)\leftarrow }$

NAF によれば、ここから ${\displaystyle {\mathit {not}}~p(c)}$ が導出される。

プログラムの完全性は次のようになる。

${\displaystyle p(X)\equiv X=a\lor X=b}$

ここでは、単一名公理と領域閉包公理によって敷衍されている。

完全性意味論はサーカムスクリプションと閉世界仮説に密接に関連している。

自己認識意味論

完全性意味論は、NAF 推論の結果 ${\displaystyle {\mathit {not}}~p}$ を古典的な ${\displaystyle p}$ の否定 ${\displaystyle \neg p}$ として解釈する。しかし、Michael Gelford (1987) では、${\displaystyle {\mathit {not}}~p}$ を自己認識論理において「${\displaystyle p}$ を示すことができない」、あるいは「${\displaystyle p}$ は未知である」、あるいは「${\displaystyle p}$ は信じられていない」と解釈することも可能であるとした。自己認識的解釈は、さらに Gelford と Lifschitz (1988) で研究が進み、解集合プログラミングの基盤となった。

NAF リテラルを含む純粋 Prolog のプログラム P の自己認識意味論は、基底（変数を伴わない）NAF リテラルの集合 Δ を使った P の「展開; expanssion」で得られ、これは安定モデル意味論で次のような意味を持つ。

Δ = {${\displaystyle {\mathit {not}}~p}$ | ${\displaystyle p}$ は P ∪ Δ に含まれない}

言い換えれば、何が示せないかに関する前提の集合 Δ が安定であることは、Δによって展開されたプログラム P から真であることを示せない全ての文の集合が Δ であることと同値である。ここで、純粋 Prolog プログラムの文法は単純であるため、「含意」は単にモーダスポネンスと普遍例化のみで導出されるものと解釈される。

プログラムはゼロか1つ以上の安定な展開を持つことができる。例えば、

${\displaystyle p\leftarrow {\mathit {not}}~p}$

は安定な展開を持たない。

${\displaystyle p\leftarrow {\mathit {not}}~q}$

は、1つの安定な展開 Δ = {${\displaystyle {\mathit {not}}~q}$} を持つ。

${\displaystyle p\leftarrow {\mathit {not}}~q}$

${\displaystyle q\leftarrow {\mathit {not}}~p}$

は、2つの安定な展開 Δ₁ = {${\displaystyle {\mathit {not}}~p}$} と Δ₂ = {${\displaystyle {\mathit {not}}~q}$} を持つ。

NAF の自己認識的解釈は古典的な否定と結合でき、論理プログラミングや解集合プログラミングでそのような拡張がなされている。そのような結合をすると、次のような表現が可能となる。

${\displaystyle \neg p\leftarrow {\mathit {not}}~p}$ （閉世界仮説）

${\displaystyle p\leftarrow {\mathit {not}}~\neg p}$ （${\displaystyle p}$ はデフォルトで成り立つ）

参考文献

• K. Clark [1978, 1987]. Negation as failure. Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers, pages 311 - 325.
• M. Gelfond [1987] On Stratified Autoepistemic Theories Proc. AAAI, pages 207-211.
• M. Gelfond and V. Lifschitz [1988] The Stable Model Semantics for Logic Programming Proc. 5th International Conference and Symposium on Logic Programming (R. Kowalski and K. Bowen, eds), MIT Press, pages 1070-1080.

外部リンク

• Report from the W3C Workshop on Rule Languages for Interoperability NAF と SNAF (Scoped NAF) に関する記述あり