エルブランの定理
エルブランの定理は、以下のように表現できる。
F {\displaystyle F} を節の有限集合とするとき、以下の2つは同値である。 F {\displaystyle F} が充足不能 F {\displaystyle F} から得られる基礎例(エルブラン基底)の有限集合で充足不能なものが存在
つまり、一階述語論理式の充足不能性の判定は、エルブラン基底上の有限回の命題論理レベルでの判定で行うことができる。
エルブランの定理はこれ以外にも様々な形式で表現することができる。
一般に、論理式の真偽値は対象となる領域 D とその解釈 I の組(モデル)により異なる。例えば、 ∀ x ∃ y ( x > y ) {\displaystyle \forall x\exists y(x>y)} は、自然数を領域とするか実数を領域とするかで真偽値が変わる。モデルにより以下の3通りが考えられる。
恒真(valid)・・・全てのモデルで真
充足可能(satisfiable)・・・少なくとも1つのモデルで真
充足不能(unsatisfiable)・・どんなモデルでも偽(=恒偽)
以下では、例として ∀ x ∀ y P ( x , y ) {\displaystyle \forall x\forall yP(x,y)} のような全称論理式(あるいは論理式の集合) F {\displaystyle F} を考える。 P {\displaystyle P} は述語、 a 1 , a 2 , . . . , a n , . . .