デービス・パトナムのアルゴリズム

デービス・パトナムのアルゴリズム（）は、与えられた論理式の充足可能性を調べるアルゴリズムで、連言標準形で表現された命題論理式を対象とする。アメリカ国家安全保障局の支援を受け、一階述語論理での定理自動証明のための方法として（'）とヒラリー・パトナム（'）により1958年に考案され
、一般には1960年に発表された
その後の改良版であるDPLLアルゴリズム（""）
のベースとなるアルゴリズムである。
なお、古い文献ではDPLLアルゴリズムのことをデービス・パトナムのアルゴリズムと呼ぶことがある。それぞれは異なった規則を使用し、正確には異なる。
1960年に提案されたデービス・パトナムのアルゴリズムが導出を使用するのに対し、1962年に提案されたDPLLアルゴリズムはバックトラックを使用する。
概要.
デービス・パトナムのアルゴリズムは、初期の一階述語論理の定理自動証明システムで必要だった命題論理式の充足可能/不能のチェックを効率的に行うために考案されたもので、導出規則を含むいくつかの規則を用いることで充足可能であることが分かっている論理式を効率的に削除し、無駄な判定を省くことができる。
一般に、一階述語論理式 "P" の証明可能性（恒真性）は "¬P" が充足不能（恒偽）かどうかと同値であり、エルブランの定理より "¬P" が充足不能ならば、エルブラン領域の要素を述語論理式に代入した基礎例（"エルブラン基底"）の命題論理レベルの充足不能チェックにより、有限ステップで証明可能であることが分かっている。
しかしこの方法を定理自動証明に使おうとすると、多量の命題論理式の充足不能性をチェックする必要がある。デービス・パトナムのアルゴリズムはこのような処理を高速に行うことができる。
規則.
規則として以下のものがあり、リテラルや充足可能な論理式の削除に用いられる。ここでリテラルとは単一の原子論理式、あるいはその否定を表す。
規則を適用すると論理的な意味は変わるが、充足可能性は変わらない。
さらに以下の規則が追加される場合もある。
1リテラル規則と純リテラル規則は特定のリテラルを真と解釈することによって充足可能となる節を除去する。1リテラル規則の適用によりさらに別のリテラルが削除可能になる場合は繰り返し規則を適用する。
包含規則は冗長な節を除去する。クリーンアップ規則はトートロジーを含む節の除去である。
原子論理式除去規則は命題論理での導出規則であり、1リテラル規則と純リテラル規則を適用したのちに使用する。規則は以下の式で表すことができる。上式は前提となる親節、下式はそれらから導かれる導出節（）を表す。
アルゴリズムは、与えられた節の集合に対しこれらの規則を繰り返し適用し、以下の結果が求まれば停止する。
デービス・パトナムのアルゴリズムについて、以下の定理が成り立つ。
 節の集合が充足可能である必要十分条件は、このアルゴリズムを適用した結果が充足可能になることである。
歴史.
最初、デービス・パトナムのアルゴリズムはエルブランの定理を用いて一階述語論理式の定理を証明するための方法の一部として用いられた。エルブランの定理での証明をそのまま計算機上で実現したギルモアのアルゴリズムよりは効率的で、ギルモアのアルゴリズムがIBM 704上で21分かかっても結果が出なかった問題を容易に手計算で求めることができた。
だが、基礎例を機械的に作り出しその充足不能性を調べるやり方は、多数の無駄な論理式が生成されるため効率が非常に悪く、ギルモアのアルゴリズムと同様、一階述語論理での複雑な論理式の証明はできなかった。
その後、プラウィツ（Dag Prawitz）は、論理式を生成してからチェックするのではなく、論理式への適当な代入（単一化）によって充足不能性を調べる方法を提案し
デービス・パトナムの枠組みにプラウィツのアイデアを組み合わせたロビンソンの導出原理の提案へのとつながっていく。
デービス・パトナムのアルゴリズム自体もより効率のよいDPLLアルゴリズム（""）に発展し、命題論理式の充足可能性問題を解くためのアルゴリズムとして多くの定理証明システムで使用されている。
例.
充足不能な論理式.
論理式 formula_2 の充足可能性を考える。
アルゴリズムは以下の動きになる。
同じ論理式を節集合の形で表現すると以下のようになる。空節を □ で表す。
充足可能な論理式.
論理式 formula_17 を考える。
アルゴリズムは以下の動きになる。
同じ論理式を節集合の形で表現すると以下のようになる。