デービス・パトナムのアルゴリズム
規則として以下のものがあり、リテラルや充足可能な論理式の削除に用いられる。ここでリテラルとは単一の原子論理式、あるいはその否定を表す。 規則を適用すると論理的な意味は変わるが、充足可能性は変わらない。
1リテラル規則(one literal rule, unit rule)
リテラル L 1つだけの節があれば、L を含む節を除去し,他の節の否定リテラル ¬L を消去する。
純リテラル規則(pure literal rule, affirmative-nagative rule)
節集合の中に否定と肯定の両方が現われないリテラル(純リテラル) L があれば、L を含む節を除去する。
原子論理式除去規則(rule for eliminating atomic formulas)
節集合 F の中に否定と肯定の両方があるリテラル L があれば、そのリテラルを除去する。
さらに以下の規則が追加される場合もある。
包含規則(subsumption rule)
ある節 C の全てのリテラルが他の節 D に含まれていれば、それらの節 C を除去する。
クリーンアップ規則(cleanup rule)