デービス・パトナムのアルゴリズム
( t ∨ ¬ t ) {\displaystyle (t\vee \neg t)}
この式はトートロジーのみを含み、充足可能であることが証明できる。さらにクリーンアップ規則を用いれば節が無くなる。
同じ論理式を節集合の形で表現すると以下のようになる。
{ { s , t } , { ¬ s , ¬ t } , { p , u } , { ¬ p , u } } {\displaystyle \{\{s,t\},\{\neg s,\neg t\},\{p,u\},\{\neg p,u\}\}}
(純リテラル規則, u = 真)
{ { s , t } , { ¬ s , ¬ t } } {\displaystyle \{\{s,t\},\{\neg s,\neg t\}\}}
(原子論理式除去規則, s {\displaystyle s} )
{ { t , ¬ t } } {\displaystyle \{\{t,\neg t\}\}}
(クリーンアップ規則, t {\displaystyle t} )
{ } {\displaystyle \left\{\ \right\}}
節集合が空になったので、充足可能であることが証明された。