エルブランの定理
エルブラン領域(英: Herbrand universe)とは、述語論理式に現れうる変数を含まない全ての項の集合である。
述語論理式の項は以下の定義から帰納的に表される。
任意の個体定項(定数)は項である。
任意の個体変項(変数)は項である。
任意の n 引数の関数記号 f と複数の項からなる f(t1, .. ,tn) は項である。
論理式を構成する記号として定数及び関数記号が定められているとき、変数を含まない項(閉項、closed term)の全体をエルブラン領域(Herbrand universe)といい、以下の式 H で表すことができる。論理式に定数が含まれない場合は任意の定数 c を付加する。
H = H ∞ {\displaystyle H=\textstyle H_{\infty }} H 0 = { c } {\displaystyle H_{0}={\big \{}c{\big \}}} (cは定数記号) H i + 1 = H i ∪ { f ( t 1 , ... , t n ) | t j ∈ H i } {\displaystyle H_{i+1}=H_{i}\cup {\big \{}f(t_{1},\ldots ,t_{n})|t_{j}\in H_{i}{\big \}}} (f は n 引数の関数記号)
例えば、定数 a と1引数関数 f 及び2引数関数 g が論理式に含まれる場合のエルブラン領域は、a, f(a), f(f(a)), g(a,a), g(a,f(a)), f(g(a,a)), g(a,g(a,a)), .. となる。