ギルモアのアルゴリズム
一階述語論理式 P が証明可能かどうかを調べたい時、エルブランの定理により、
P が恒真かどうかは、 ¬ P {\displaystyle \lnot P} が充足不能(恒偽)かどうかと同値
¬ P {\displaystyle \lnot P} が充足不能ならば、基礎例(ground instance)の命題論理レベルの充足不能チェックにより有限ステップで証明可
であり、ギルモアのアルゴリズムはこの考え方をもとにしている。
アルゴリズムの入出力は以下のように定義できる。
G i l m o r e ( E ( F ) ) = { h a l t , when F is unsatisfiable u n d e f , when F is not unsatisfiable {\displaystyle Gilmore\left(E\left(F\right)\right)={\begin{cases}halt,&{\mbox{when }}F{\mbox{ is unsatisfiable}}\\undef,&{\mbox{when }}F{\mbox{ is not unsatisfiable}}\end{cases}}}