DPLLアルゴリズム
論理式 φ = ( 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リテラル規則、純リテラル規則とも適用できず単純化できないため、分割規則を適用する。