一階述語論理
一階述語論理の言語(一階の言語)は次のものからなる:
論理記号 (logical symbol) 変数(あるいは個体変数)と呼ぶ記号の集合: V = { x 1 , x 2 , ⋯ } {\displaystyle V=\{x_{1},\,x_{2},\,\cdots \}} 結合記号: ¬ {\displaystyle \lnot } , ∧ {\displaystyle \land } , ∨ {\displaystyle \lor } , ⇒ {\displaystyle \Rightarrow } , ⇔ {\displaystyle \Leftrightarrow } 量化記号: ∀ {\displaystyle \forall } , ∃ {\displaystyle \exists } 括弧: ( {\displaystyle (} , ) {\displaystyle )} , [ {\displaystyle [} , ] {\displaystyle ]} , { {\displaystyle \{} , } {\displaystyle \}} 等号: = {\displaystyle =} (含まなくてもよい。)
非論理記号 (nonlogical symbol) 述語記号と呼ぶ記号の集合(有限集合でも無限集合でもよい)。各述語記号にはアリティ(arity)と呼ぶ引数の個数に相当する正の整数が一つ対応しているものとする。
これらを用いると「すべての x {\displaystyle x} について φ {\displaystyle \phi } ; である」という命題は ∀ x φ {\displaystyle \forall x\phi } ; 、「ある x {\displaystyle x} に対して φ {\displaystyle \phi } ; である」は ∃ x φ {\displaystyle \exists x\phi } ; と表される。これらの記号を用いると上の三つの文はそれぞれ、例えば、
∀ x [ P ( x ) ⇒ Q ( x ) ] {\displaystyle \forall x[P(x)\Rightarrow Q(x)]}
P ( a ) {\displaystyle P(a)}
Q ( a ) {\displaystyle Q(a)}
のように記号化することができる。ここで、 P ( x ) {\displaystyle P(x)} と Q ( x ) {\displaystyle Q(x)} はそれぞれ「 x {\displaystyle x} は人間である」「 x {\displaystyle x} は死ぬ」を表し、 a {\displaystyle a} はソクラテスを表すことを意図している。上の日本語による定言命題推論の妥当性は不決定的だが、仮言命題推論化されるならば、一階述語論理において Q ( a ) {\displaystyle Q(a)} が
一階述語論理の項 (term) は次のように帰納的に定義される:
変数と定数記号はすべて項である。
t 1 , ⋯ , t n {\displaystyle t_{1},\,\cdots ,\,t_{n}} が項で、 f {\displaystyle f} がアリティ n の関数記号ならば、 f t 1 , ⋯ , t n {\displaystyle ft_{1},\,\cdots ,\,t_{n}} は項である。
上記の 1. と 2. によって項とされるものだけが項である。
項というのは直観的には議論領域に属するある対象を表す"名前"の役割をもった記号列である。
例. 自然数論の言語は等号を持つ一階の言語で、非論理記号として 、 1 {\displaystyle 1} 変数関数記号 S {\displaystyle S} 、 2 {\displaystyle 2} 変数関数記号 + {\displaystyle +} , ⋅ {\displaystyle \cdot } と定数記号 0 {\displaystyle 0} を持つ。定義より、
関数記号と呼ぶ記号の集合(有限集合でも無限集合でもよい)。各関数記号もアリティを持っているものとする。 定数記号と呼ぶ記号の集合(有限集合でも無限集合でもよい)。
一階の言語は、それが等号を持つかどうか、非論理記号に何を持っているかを決めることによって定まる。例えば集合論においては、等号を持ち、非論理記号としてはアリティ 2 {\displaystyle 2} の述語記号 ∈ {\displaystyle \in } ; だけをもつ一階の言語(集合論の言語)が使われる。以下に一階の言語について、いくつかの注意を述べる。
等号 = {\displaystyle =} はアリティ 2 {\displaystyle 2} の特別な述語記号として扱われる。どの一階の言語にも等号を含めて少なくとも一つは述語記号が含まれていなければならないものとする。
アリティ n {\displaystyle n} の述語(関数)記号を、 n {\displaystyle n} 変数述語(関数)記号と呼ぶこともある。
記号は一つの用途のみに用いる。すなわち、一つの一階の言語において、ある記号が述語記号であると同時に定数記号でもあるということや、論理記号であると同時に関数記号でもあるというようなことがあってはならない。
いくつかの結合記号や量化記号は言語にもともと含まれている記号ではなく、省略記法として定義によって導入される場合がある。
文 φ が文の集合 Σ の論理的帰結であること ( Σ ⊨ φ {\displaystyle \Sigma \vDash \varphi } ) と、φ が Σ の定理であること ( Σ ⊢ φ {\displaystyle \Sigma \vdash \varphi } ) は全く別の仕方で定義されている。
健全性とは、Σ の定理はすべて Σ の論理的帰結であることである。
Σ ⊢ φ ⟹ Σ ⊨ φ {\displaystyle \Sigma \vdash \varphi \Longrightarrow \Sigma \vDash \varphi }
完全性とは、Σ の論理的帰結はすべて Σ の定理であることである。
Σ ⊨ φ ⟹ Σ ⊢ φ {\displaystyle \Sigma \vDash \varphi \Longrightarrow \Sigma \vdash \varphi }
古典一階述語論理は健全かつ完全である。