ギルモアのアルゴリズム

ギルモアのアルゴリズム（）は、エルブランの定理にもとづき一階述語論理式が充足不能（'）かどうかを調べる半アルゴリズム（'）である。ギルモアのアルゴリズムは1960年に発表された。
概要.
一階述語論理式 "P" が証明可能かどうかを調べたい時、エルブランの定理により、
であり、ギルモアのアルゴリズムはこの考え方をもとにしている。
アルゴリズムの入出力は以下のように定義できる。
ここで formula_4 はエルブラン領域の要素を述語論理式に代入した基礎例（エルブラン基底）の集合で、アルゴリズムの入力である。
対象となる述語論理式は冠頭標準形にした選言標準形の式で表現される。
実際の手続きは以下のようになる:
この手続きは半決定可能で、証明したい論理式が充足不能でない場合、手続きは停止しない。一般に、述語論理式が証明可能かどうかは決定可能でないことが知られている。
展開.
ギルモアのアルゴリズムはIBM 704上でプログラムされ、適度に複雑な論理式の証明を2分以内で行った。
だが、基礎例を機械的に作り出しその充足不能性を調べるやり方は、多数の無駄な論理式が生成されるため効率が非常に悪く、単純な証明のみが可能だった。
しかし、ギルモアのアルゴリズムは定理自動証明の初期の試みの1つとしてその後の研究の大きな刺激となり、導出原理などを生み出す原動力になった。