algorithm)は、与えられた論理式の充足可能性を調べるアルゴリズムで、連言標準形で表現された命題論理式を対象とする。[3]のベースとなるアルゴリズムである。古い文献ではDPLLアルゴリズムのことをデービス・パトナムのアルゴリズムと呼ぶことがある。それぞれは異なった規則を使用し[3]、正確には異なる。1960年に提案されたデービス・パトナムのアルゴリズムが導出を使用するのに対し、1962年に提案されたDPLLアルゴリズムはバックトラックを使用する[4]。概要[編集]デービス・パトナムのアルゴリズムは、初期の一階述語論理の定理自動証明システムで必要だった命題論理式の充足可能/不能のチェックを効率的に行うために考案されたもので、導出規則を含むいくつかの規則を用いることで充足可能であることが分かっている論理式を効率的に削除し、無駄な判定を省くことができる。充足不能ならば、エルブラン領域の要素を述語論理式に代入した基礎例(エルブラン基底)の命題論理レベルの充足不能チェックにより、有限ステップで証明可能であることが分かっている。この方法を定理自動証明に使おうとすると、多量の命題論理式の充足不能性をチェックする必要がある。デービス・パトナムのアルゴリズムはこのような処理を高速に行うことができる。規則[編集]規則として以下のものがあり、リテラルや充足可能な論理式の削除に用いられる。ここでリテラルとは単一の原子論理式、あるいはその否定を表す。規則を適用すると論理的な意味は変わるが、充足可能性は変わらない。あれば、そのリテラルを除去する。以下の規則が追加される場合もある。含む節を全て除去する。1リテラル規則と純リテラル規則は特定のリテラルを真と解釈することによって充足可能となる節を除去する。1リテラル規則の適用によりさらに別のリテラルが削除可能になる場合は繰り返し規則を適用する。包含規則は冗長な節を除去する。命題論理での導出規則であり、1リテラル規則と純リテラル規則を適用したのちに使用する。規則は以下の式で表すことができる。上式は前提となる親節、下式はそれらから導かれる導出節(resolvent)を表す。Q}}}アルゴリズムは、与えられた節の集合に対しこれらの規則を繰り返し適用し、以下の結果が求まれば停止する。空節(リテラルを含まない節)が生じれば、結果は充足不能デービス・パトナムのアルゴリズムについて、以下の定理が成り立つ[2]。節の集合が充足可能である必要十分条件は、このアルゴリズムを適用した結果が充足可能になることである。歴史[編集]最初、デービス・パトナムのアルゴリズムはエルブランの定理を用いて一階述語論理式の定理を証明するための方法の一部として用いられた。704上で21分かかっても結果が出なかった問題を容易に手計算で求めることができた[2]。複雑な論理式の証明はできなかった[1]。デービス・パトナムの枠組みにプラウィツのアイデアを組み合わせたロビンソンの導出原理の提案へのとつながっていく。algorithm)に発展し、命題論理式の充足可能性問題を解くためのアルゴリズムとして多くの定理証明システムで使用されている。q)}の充足可能性を考える。アルゴリズムは以下の動きになる。1リテラル規則を適用する。