デービス・パトナムのアルゴリズム
論理式 φ = ( p ∨ q ∨ ¬ r ) ∧ ( ¬ q ∨ p ) ∧ ( ¬ p ) ∧ ( r ∨ q ) {\displaystyle \phi =(p\vee q\vee \neg r)\wedge (\neg q\vee p)\wedge (\neg p)\wedge (r\vee q)} の充足可能性を考える。
アルゴリズムは以下の動きになる。
( p ∨ q ∨ ¬ r ) ∧ ( ¬ q ∨ p ) ∧ ( ¬ p ) ∧ ( r ∨ q ) {\displaystyle (p\vee q\vee \neg r)\wedge (\neg q\vee p)\wedge (\neg p)\wedge (r\vee q)}
リテラル1つだけの節 ( ¬ p {\displaystyle \neg p} ) に1リテラル規則を適用する。 ¬ p {\displaystyle \neg p} を真と見なせば p {\displaystyle p} は偽である。
( q ∨ ¬ r ) ∧ ( ¬ q ) ∧ ( r ∨ q ) {\displaystyle (q\vee \neg r)\wedge (\neg q)\wedge (r\vee q)}
1リテラル規則はさらに ¬ q {\displaystyle \neg q} にも適用できる。
( ¬ r ) ∧ ( r ) {\displaystyle (\neg r)\wedge (r)}
論理式 φ = ( s ∨ t ) ∧ ( ¬ s ∨ ¬ t ) ∧ ( p ∨ u ) ∧ ( ¬ p ∨ u ) {\displaystyle \phi =(s\vee t)\wedge (\neg s\vee \neg t)\wedge (p\vee u)\wedge (\neg p\vee u)} を考える。
アルゴリズムは以下の動きになる。
( s ∨ t ) ∧ ( ¬ s ∨ ¬ t ) ∧ ( p ∨ u ) ∧ ( ¬ p ∨ u ) {\displaystyle (s\vee t)\wedge (\neg s\vee \neg t)\wedge (p\vee u)\wedge (\neg p\vee u)}
リテラル u {\displaystyle u} は肯定でしか現れないため純リテラルである。純リテラル規則を適用する。(u = 真)
( s ∨ t ) ∧ ( ¬ s ∨ ¬ t ) {\displaystyle (s\vee t)\wedge (\neg s\vee \neg t)}
1リテラル規則、純リテラル規則とも適用できないため、s について原子論理式除去規則を適用する。