一階述語論理
命題論理では文を構成する最も基本的な命題(原子命題)は命題記号と呼ぶ一つの記号によって表していた。それに対し、一階述語論理においては、最も基本的な命題は原子論理式と呼ぶ記号列によって表す。原子論理式とは述語記号( P {\displaystyle P} )と呼ぶ記号と、項( t 1 , ⋯ , t n {\displaystyle t_{1},\,\cdots ,\,t_{n}} ) と呼ぶものの列、からなる P ( t 1 , ⋯ , t n ) {\displaystyle P(t_{1},\,\cdots ,\,t_{n})} という形の記号列であり、これは個体の間の関係を表すものである。
命題論理にない一階述語論理のもう一つの特徴は量化 (quantification) である。例えば、定言的命題論理の範囲において、次のような推論の妥当性を扱うことはできない:
すべての人間は死ぬ。
ソクラテスは人間である。
したがってソクラテスは死ぬ。
一階述語論理では、このような「すべての...について」という表現や、また「ある...について」といった表現を扱えるように、全称量化記号 (universal quantifier) と呼ぶ記号 ∀ {\displaystyle \forall } ; と存在量化記号 (existential quantifier) と呼ぶ記号 ∃ {\displaystyle \exists } ; を新たに導入する。
等号に関する公理の 2. は、
x = y → (P t1 ... tn → P u1 ... un) (ただし、P は n 変数述語記号で、ui は ti における x のいくつかを y で置き換えて得られる項である)
となっている。ここで、項 u が項 t における x のいくつかを y で置き換えて得られる項であるということは正確には次のように定義される。
変数 x と y を固定し、項の間の関係 ≈ を次のように再帰的に定義する: x ≈ u ⇔ u = x または u = y 。 z が x と異なる変数ならば、z ≈ u ⇔ u = z 。 c 定数記号ならば、c ≈ u ⇔ u = c 。 t1 , ..., tn が項で、f がアリティ n の関数記号ならば、f t1 ... tn ≈ u ⇔ t1 ≈ u1 , ..., tn ≈ un であるような u1 , ..., un が存在して u = f u1 ... un 。
t ≈ u であるとき、u は t における x のいくつかを y で置き換えて得られる項であるという。
一階述語論理(英: first-order predicate logic)とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理(英: second-order predicate logic)と呼び、さらなる一般化を加えた述語論理を高階述語論理(英: higher-order predicate logic)という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細はそれぞれの記事を参照。