一階述語論理

一階述語論理（いっかいじゅつごろんり、英: first-order predicate logic）とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理（英: second-order predicate logic）と呼び、さらなる一般化を加えた述語論理を高階述語論理（英: higher-order predicate logic）という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細はそれぞれの記事を参照。

概要

命題論理との差異

命題論理では文を構成する最も基本的な命題（原子命題）は命題記号と呼ぶ一つの記号によって表していた。それに対し、一階述語論理においては、最も基本的な命題は原子論理式と呼ぶ記号列によって表す。原子論理式とは述語記号( $P$ )と呼ぶ記号と、項( $t_{1},\,\cdots ,\,t_{n}$ ) と呼ぶものの列、からなる $P(t_{1},\,\cdots ,\,t_{n})$ という形の記号列であり、これは個体の間の関係を表すものである。

命題論理にない一階述語論理のもう一つの特徴は量化 (quantification) である。例えば、定言的命題論理の範囲において、次のような推論の妥当性を扱うことはできない：

すべての人間は死ぬ。

ソクラテスは人間である。

したがってソクラテスは死ぬ。

一階述語論理では、このような「すべての…について」という表現や、また「ある…について」といった表現を扱えるように、全称量化記号 (universal quantifier) と呼ぶ記号 $\forall$; と存在量化記号 (existential quantifier) と呼ぶ記号 $\exists$; を新たに導入する。これらを用いると「すべての $x$ について $\phi$; である」という命題は $\forall x\phi$; 、「ある $x$ に対して $\phi$; である」は $\exists x\phi$; と表される。これらの記号を用いると上の三つの文はそれぞれ、例えば、

$\forall x[P(x)\Rightarrow Q(x)]$

$P(a)$

$Q(a)$

のように記号化することができる。ここで、$P(x)$ と $Q(x)$ はそれぞれ「 $x$ は人間である」「$x$ は死ぬ」を表し、$a$ はソクラテスを表すことを意図している。上の日本語による定言命題推論の妥当性は不決定的だが、仮言命題推論化されるならば、一階述語論理において $Q(a)$ が

$\{\forall x[P(x)\Rightarrow Q(x)]\,,\,P(a)\}$

の論理的帰結 (logical consequence) であるという事実に反映される。一般に、論理式 $\phi$; が論理式の可算集合 $\Sigma$; の論理的帰結であるとは、$\Sigma$; の論理式のすべてをみたす解釈は必ず $\phi$; もみたすこととして定義され、これは、あるいくつかの前提からある結論が論理的に導かれるという概念の数学的な定式化である。

命題論理においては、論理式の解釈は各命題記号に対する真理値 0 , 1 の割り当てが与えられた。これに対して、一階述語論理の論理式の解釈は構造 (structure) と呼ばれ、これは領域 (universe, domain) と呼ぶ空でない集合と、それぞれの非論理記号（述語記号・関数記号・定数記号）の "意味" の割り当てからなる。領域とは「すべての $x$ について」といったときの $x$ が動きうる値の範囲である。一階述語論理の論理式は構造を一つ与えることによって真偽が決定される。

二階述語論理（およびそれ以上の高階述語論理）では、述語および関数に対する量化を導入する。

一階述語論理の表現力

一階述語論理は、数学のほぼ全領域を形式化するのに十分な表現力を持っている。実際、現代の標準的な集合論の公理系 ZFC は一階述語論理を用いて形式化されており、数学の大部分はそのように形式化された ZFC の中で行うことができる。すなわち、数学の命題は一階述語論理の論理式によって記述することができ、そのように論理式で記述された数学の定理には ZFC の公理からの形式的証明 (formal proof) が存在する。このことが一階述語論理が重要視される理由の一つである。この他にペアノ算術のように単独で形式化する理論もある。

一階の言語

一階述語論理の言語（一階の言語）は次のものからなる：

論理記号 (logical symbol)

1. 変数（あるいは個体変数）と呼ぶ記号の集合： $V=\{x_{1},\,x_{2},\,\cdots \}$
2. 結合記号： $\lnot$, $\land$ , $\lor$, $\Rightarrow$, $\Leftrightarrow$
3. 量化記号： $\forall$, $\exists$
4. 括弧： $($ , $)$ , $[$ , $]$ , $\{$ , $\}$
5. 等号： $=$ （含まなくてもよい。）

非論理記号 (nonlogical symbol)

1. 述語記号と呼ぶ記号の集合（有限集合でも無限集合でもよい）。各述語記号にはアリティ（arity）と呼ぶ引数の個数に相当する正の整数が一つ対応しているものとする。
2. 関数記号と呼ぶ記号の集合（有限集合でも無限集合でもよい）。各関数記号もアリティを持っているものとする。
3. 定数記号と呼ぶ記号の集合（有限集合でも無限集合でもよい）。

一階の言語は、それが等号を持つかどうか、非論理記号に何を持っているかを決めることによって定まる。例えば集合論においては、等号を持ち、非論理記号としてはアリティ $2$ の述語記号 $\in$; だけをもつ一階の言語（集合論の言語）が使われる。以下に一階の言語について、いくつかの注意を述べる。

• 等号 $=$ はアリティ $2$ の特別な述語記号として扱われる。どの一階の言語にも等号を含めて少なくとも一つは述語記号が含まれていなければならないものとする。
• アリティ $n$ の述語（関数）記号を、$n$ 変数述語（関数）記号と呼ぶこともある。
• 記号は一つの用途のみに用いる。すなわち、一つの一階の言語において、ある記号が述語記号であると同時に定数記号でもあるということや、論理記号であると同時に関数記号でもあるというようなことがあってはならない。
• いくつかの結合記号や量化記号は言語にもともと含まれている記号ではなく、省略記法として定義によって導入される場合がある。例えば、$\Leftrightarrow$; は言語に含まれず、 $(\phi \Leftrightarrow \psi )$ は $[(\phi \Rightarrow \psi )\land (\psi \Rightarrow \phi )]$ を表すものとして定義される場合もある。上の論理記号すべてを用いて表現される命題は、例えば $\lnot$、$\lor$、$\exists$ や $\lnot$、$\Rightarrow$、$\forall$ だけを用いても十分に表現できることが知られている。
• 文献によっては、$\Rightarrow$ の代わりに $\supset$; を用い、$\forall$ の代わりに $\Pi$; を用いている場合がある。
• 同一性関係を一階述語論理の一部とみなす場合もある。その場合、等号は必ず言語に含まれることになる。常に等号が含まれることを仮定した一階述語論理を等号付き一階述語論理と呼ぶ。
• 定数記号はアリティ 0 の関数記号と呼ぶこともある。
• 上の定義では述語は 1 以上のアリティを持つとされているが、アリティ 0 の述語も考えることができ、それらは「真」や「偽」を意味するものと考えることができる。しかし「真」は $\forall x(x=x)$ などと別の方法で表せるので、アリティ 0 の述語を導入することに大きな意味はない。
• 括弧の使い方の流儀は様々である。ある人は $\forall x$ を $(\forall x)$ と書く。括弧の代わりにコロンや終止符を使う場合もある。もちろんその場合には、言語にコロンや終止符を含めておく必要がある。括弧を全く使わない表記法にポーランド記法(Polish notation)と呼ぶものがある。これは、$\land$; や $\lor$; を先頭に書いて $(\phi \land \psi )$ の代わりに $\land \phi \psi$ のように書く方法である。ポーランド記法はコンパクトで数学的に取り扱いやすいという利点があり、可読性が低いという欠点がある。

項と論理式

項

一階述語論理の項 (term) は次のように帰納的に定義される：

1. 変数と定数記号はすべて項である。
2. $t_{1},\,\cdots ,\,t_{n}$ が項で、$f$ がアリティ n の関数記号ならば、$ft_{1},\,\cdots ,\,t_{n}$ は項である。
3. 上記の 1. と 2. によって項とされるものだけが項である。

項というのは直観的には議論領域に属するある対象を表す"名前"の役割をもった記号列である。

例． 自然数論の言語は等号を持つ一階の言語で、非論理記号として 、$1$ 変数関数記号 $S$ 、$2$ 変数関数記号 $+$ , $\cdot$ と定数記号 $0$ を持つ。定義より、

$x_{1}$ , 　$x_{5}$ , 　$0$ , 　$Sx_{1}$ , 　$S0$ , 　$SS0$ , 　$+S0S0$ , 　$+0x_{5}$ , 　$\cdot Sx_{1}+0x_{5}$

はすべて項である。 $+S0S0$ や $+0x_{5}$ といった前置記法は読みにくいため、これらの項を表すのに、通常使われている $S(0)+S(0)$ や $0+x_{5}$ のような表現(中置記法)が用いられることもある。したがって $\cdot Sx_{1}+0x_{5}$ は中置記法では $S(x_{1})\cdot (0+x_{5})$ のように表される。

論理式

項が何らかの対象を表す記号列であったのに対して、論理式は何らかの命題を表すものである。論理式は原子論理式と呼ぶ最も基本的な論理式から結合記号と量化記号を繰り返し用いることによって形成される。まず、原子論理式は次のように定義される：

ある正の整数 $n$ に対するアリティ $n$ の述語記号 $P$ と $n$ 個の項 $t_{1},\,\cdots ,\,t_{n}$ を用いて $P(t_{1},\,\cdots ,\,t_{n})$ と表される記号列を原子論理式 (atomic formula) と呼ぶ。

原子論理式を用いて、論理式 (well-formed formula, wff) あるいは式 (formula) は次のように帰納的に定義される：

1. 原子論理式は論理式である。
2. $\phi$ と $\psi$ が論理式ならば、$(\lnot \phi )$ , $(\phi \land \psi )$ , $(\phi \lor \psi )$ , $(\phi \Rightarrow \psi )$ , $(\phi \Leftrightarrow \psi )$ は論理式である。
3. $\phi$ が論理式で $x$ が変数ならば、$(\forall x\phi )$ , $(\exists x\phi )$ は論理式である。
4. 上記の 1. と 2. と 3. によって論理式とされるものだけが論理式である。

例． 再び自然数論の言語を考える。定義から、

$[(S0+S0)=SS0]$ ,　 $[(0+x_{5})=S0]$

はすべて原子論理式（したがって論理式）であり、

$\{\lnot [(S0+S0)=SS0]\}$ , 　$\{[(0+x_{5})=S0]\land [(S0+S0)=SS0]\}$ , 　$\{\forall x_{5}[(0+x_{5})=S0]\}$, 　$\{\exists x_{2}[(0+x_{5})=S0]\}$

自由変数

自然数論の言語における論理式 $(S0+S0)=SS0$ の各記号を通常の意味で解釈すれば「$1+1=2$」となり、これは真である論理式である。$\lnot [(S0+S0)=SS0]$ は「$1+1\neq 2$」となるので通常の解釈で偽なる論理式である。また、変数の動く範囲（議論領域）は自然数全体の集合だとすれば、論理式 $[\forall x_{1}(0=Sx_{1})]$ は「すべての自然数 $n$ について $0=n+1$」という意味になり、これは偽である論理式であることが分かる。一方、論理式 $(0+x_{5})=S0$ の意味を考えてみると、「$0+x_{5}=1$」となるがこれは真であるか偽であるかを判断することができない。なぜなら、$x_{5}$ という変数が何を表しているかが決まっていないからである。このようなとき、$x_{5}$ は論理式 $(0+x_{5})=S0$ における自由変数 (free variable) であると言われる。正式には、各論理式 $\phi$ に対して、"$\phi$ における自由変数全体の集合" $fr(\phi )$ を次のように再帰的に定義する：

1. $\phi$ が原子論理式ならば、$fr(\phi )$ は記号列 φ に現れるすべての変数からなる集合である。
2. $fr[(\lnot \phi )]=fr(\phi )$ 。
3. $fr[(\phi \land \psi )]=fr[(\phi \lor \psi )]=fr[(\phi \Rightarrow \psi )]=fr[(\phi \Leftrightarrow \psi )]=fr(\phi )\cup fr(\psi )$ 。
4. $fr(\forall x\phi )=fr(\exists x\phi )=fr(\phi )-\{x\}$。

論理式 $\phi$ が自由変数を一切持たないとき、つまり $fr(\phi )=\varnothing$ のとき、$\phi$ は閉論理式 (closed formula) あるいは文 (sentence) と呼ぶ。直観的には、文とは記号に解釈を与えて意味を考えたときに正しいか正しくないかが決まるような論理式である。$(S0+S0)=SS0$ や $\forall x_{1}0=Sx_{1}$ は文であるが、$fr[(0+x_{5})=S0]=\{x_{5}\}$ より $(0+x_{5})=S0$ は文でない。

論理式の真偽

構造

はじめに述べたように、一階述語論理の論理式の解釈は構造と呼ぶものによって与えられる。構造は変数が動く領域とそれぞれの非論理記号に対する "意味" の割り当てからなる。正式には、構造は次のように定義される。

一階の言語に対する構造 (structure) とは、空でない集合 $D$ と、非論理記号全体の集合を定義域とする関数 $F$ の組 $M=(D,\,F)$ で次をみたすものをいう：

1. $P$ がアリティ $n$ の述語記号ならば、$F(P)\subseteq D^{n}$ 、すなわち $F(P)$ は $D$ 上の $n$ 項関係である。
2. $f$ がアリティ $n$ の関数記号ならば、$F(f):D^{n}\to D$ 、すなわち $F(f)$ は $D$ 上の $n$ 項演算である。
3. $c$ が定数記号ならば、$F(c)\in D$ 、すなわち $F(c)$ は　$D$ のある要素である。

集合 $D$ を $M$ の領域 (universe, domain) と呼び、通常 $|M|$ で表す。また、$F(P)$ , $F(f)$ , $F(c)$ などは通常 $P^{M}$ , $f^{M}$ , $c^{M}$ と表される。

$M$ が一階の言語に対する構造であるとき、$M$ の領域 $|M|$ の要素を M の個体 (individual) と呼ぶ。

論理式の充足

上で見たように、自由変数を持たない論理式（すなわち文）は解釈（構造）を一つ与えることで、正しいか正しくないかが定まる。構造 M を与えたとき、文 φ が正しい命題になっているならば、φ は解釈 M において真 (true) であるといい、正しくない命題である場合、φ は M において偽 (false) であるという。以下で、これらの真偽の概念をより正確に定義する。ただし、論理式の真偽の定義にはいくつかの異なる（同値な）方法があり、ここで述べる定義はその内の一つである。

M が一階の言語に対する構造であるとき、変数全体の集合 V から M の領域 |M| への関数を、変数に対する M の個体の割り当て関数と呼ぶ。変数に対する M の個体の割り当て関数 s を一つとったとき、それぞれの項 t に対して、t の値 (value) t ^M(s) が次のように再帰的に定義される：

1. 変数 x に対しては、x ^M(s) = s(x) 。
2. 定数記号 c に対しては、c ^M(s) = c ^M 。
3. t₁ , ..., t_n が項で、f がアリティ n の関数記号ならば、(f t₁ … t_n)^M(s) = f ^M (t₁^M(s), ..., t_n^M(s)) 。

直観的には、項 t の値 t ^M(s) とは、各変数 x が Mの個体 s(x) を表すとしたとき、t が表す M の個体のことである。

次に、「構造 M が個体の割り当て関数 s によって論理式 φ を充足する」と言うことを定義する。M が s によって φ を充足するとは、各変数 x は s(x) を表すとし、各非論理記号は M によって与えられた意味を表すとしたとき、φ が正しい命題になっているということである。

M が一階の言語に対する構造であるとき、各論理式 φ と M の個体の割り当て関数 s に対して、M(φ, s) ∈ { 0, 1 } を次のように再帰的に定義する：

1. M(t₁ = t₂ , s) = 1 　⇔　 t₁^M(s) = t₂^M(s) 。
2. P がアリティ n の非論理述語記号ならば、　M(P t₁ … t_n , s) = 1　 ⇔　 (t₁^M(s), ..., t_n^M(s)) ∈ P ^M 。
3. M((¬ φ), s) = 1 　⇔　 M(φ, s) = 0 。
4. M((φ ∧ ψ), s) = 1 　⇔　 M(φ, s) = 1 かつ M(ψ, s) = 1 。
5. M((φ ∨ ψ), s) = 1 　⇔　 M(φ, s) = 1 または M(ψ, s) = 1 。
6. M((φ → ψ), s) = 1 　⇔　 M(φ, s) = 0 または M(ψ, s) = 1 。
7. M((φ ↔ ψ), s) = 1 　⇔　 M(φ, s) = M(ψ, s) 。
8. M(∀x φ, s) = 1 　⇔　 すべての m ∈ |M| に対して M(φ, s[x|m]) = 1 。
9. M(∃x φ, s) = 1 　⇔　 ある m ∈ |M| に対して M(φ, s[x|m]) = 1 。

ただし、s[x|m] は変数 x には m を割り当て、x 以外の変数に対しては s と同じ個体を割り当てる関数を表す。

M(φ, s) = 1 であるとき M は s によって φ を充足するという。

特に φ が文である場合は、すべての個体の割り当て関数 s に対して M(φ, s) = 1 であるか、すべての個体の割り当て関数 s に対して M(φ, s) = 0 であるかのいずれかであることが示される。そこで、前者の場合に φ は M において真であるといい、後者の場合に φ は M において偽であるという。すなわち、構造 M と文 φ に対して、

φ は M において真 (true) 　⇔　 任意の M の個体の割り当て関数 s に対して、M(φ, s) = 1 。

φ は M において偽 (false) 　⇔　 任意の M の個体の割り当て関数 s に対して、M(φ, s) = 0 。

と定義する。φ が M において真であるとき、M は φ のモデル (model) であるともいう。また、M が文の集合 Σ のすべての要素のモデルであるとき、単に M は Σ のモデルであるという。

論理的帰結

Σ を論理式の集合とし、φ を論理式とする。Σ に属するすべての論理式 ψ に対して M(ψ, s) = 1 であるような任意の構造 M と M の個体の割り当て関数 s が M(φ, s) = 1 をみたすとき、φ は Σ の論理的帰結 (logical consquence) であるといい、$\Sigma \vDash \varphi$ と書く。論理式 φ と ψ が $\{\varphi \}\vDash \psi$ かつ $\{\psi \}\vDash \varphi$ をみたすとき、φ と ψ は論理的に同値 (logically equivalent) であるという。また、φ が ∅ の論理的帰結である場合、すなわち任意の構造 M と M の個体の割り当て関数 s に対して M(φ, s) = 1 であるとき、φ は恒真 (valid) であるという。φ と ψ が論理的に同値であることは、(φ ↔ ψ) が恒真であることと同値である。

形式的証明

命題論理においては、論理公理 (logical axiom) と呼ぶ論理式の集合と、ある論理式たちから新たな論理式を導出する規則（推論規則）を導入し、論理公理から推論規則の有限回の適用によって得られる論理式全体とトートロジー全体が一致するようにすることができる（命題論理の健全性と完全性）。一階述語論理においても、適切に論理公理と推論規則を導入することで、論理公理から推論規則を使って導出される論理式全体と恒真論理式全体が一致するようにできる。

形式的証明の定義の仕方はひとつではなく、様々な異なる（等価な）方法がある。ここで述べる定義はヒルベルト流計算の典型例であり、これは異なる公理を多数用意して推論規則を少なくするスタイルをとっている。ゲンツェン流の形式的証明では逆に、公理を少なくして推論規則を多く用いている。ここで述べるものと異なる証明可能性の定義については「自然演繹」「シークエント計算」などを参照。

論理公理

以下の形の論理式すべてを論理公理とする。ここで、x, y は変数、t, t₁ , ..., t_n は項、φ, ψ は論理式を表す：

• トートロジー（命題論理におけるトートロジーの命題記号を一階の論理式で置き換えて得られる論理式）
• 量化記号に関する公理

1. ∀x φ → φ_x [ t ] 　（ただし、φ において t が x に代入可能（後述）の場合に限る）
2. ∀x (φ → ψ) → (∀x φ → ∀x ψ)
3. ∀x (¬ φ) ↔ (¬ ∃x φ)

• 等号に関する公理（言語が等号を持つ場合に限る）

1. x = x
2. x = y → (P t₁ … t_n → P u₁ … u_n) 　（ただし、P は n 変数述語記号で、u_i は t_i における x のいくつかを y で置き換えて得られる項である）

量化記号に関する公理 1. における φ_x [ t ] とは、論理式 φ において "束縛されていない" 変数 x をすべて項 t で置き換えて得られる論理式を表す（正確な定義は後述）。

推論規則

推論規則とは、あるいくつかの論理式から別の論理式を導出するための規則である。これは正確には、論理式全体の集合の上の関係として定義される。推論規則には様々なものが考えられるが、ここで用いる推論規則はモーダス・ポーネンス (modus ponens) と呼ぶ規則と全称化 (generalization) と呼ぶ規則の二つである。

モーダス・ポーネンス (MP)

モーダス・ポーネンスとは、φ と (φ → ψ) から ψ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる：

MP = { (φ, (φ → ψ), ψ) | φ と ψ は論理式 } 。

(φ₁, φ₂, φ₃) ∈ MP であるとき、φ₃ は φ₁, φ₂ からのモーダス・ポーネンスによる導出であるという。

全称化 (GEN)

全称化規則とは、x が変数のとき、φ から ∀x φ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる：

GEN = { (φ, ∀x φ) | φ は論理式かつ x は変数 } 。

(φ₁, φ₂) ∈ GEN であるとき、φ₂ は φ₁ からの全称化による導出であるという。

証明可能性

論理式 φ が論理式の集合 Σ から証明可能であるとは、Σ に属する論理式と論理公理から推論規則の有限回の適用によって φ が得られることを意味する。そして、Σ に属する論理式と論理公理から φ を導出する仮定を示した論理式の有限列を、Σ からの φ の形式的証明とよぶ。これらの概念は次のように厳密に定義することができる。

φ を論理式、Σ を論理式の集合とする。Σ からの φ の形式的証明 (formal proof) あるいは証明 (proof) とは、論理式の有限列 (φ₀, ..., φ_n) で次をみたすものをいう：

1. φ_n = φ 。
2. n 以下の任意の自然数 k に対して、次のいずれかが成り立つ：

(a) φ_k ∈ Σ 。

(b) φ_k は論理公理である。

(c) ある i, j < k が存在して、φ_k は φ_i , φ_j からのモーダス・ポーネンスによる導出である。

(d) ある i < k が存在して、φ_k は φ_i からの全称化による導出である。

Σ からの φ の証明が存在するとき、φ は Σ から証明可能 (provable) である、あるいは φ は Σ の定理 (theorem) であるといい、$\Sigma \vdash \varphi$ と書く。

代入について

φ_x [ t ] は、論理式 φ において "束縛されていない" 変数 x をすべて項 t で置き換えて得られる論理式を表すと述べた。正確には、φ_x [ t ] は再帰によって次に述べるような仕方で定義される。

まず、それぞれの項 u に対して u_x [ t ] を次のように再帰的に定義する：

1. x_x [ t ] = t 。
2. y が x と異なる変数ならば、y_x [ t ] = y 。
3. c 定数記号ならば、c_x [ t ] = c 。
4. t₁ , ..., t_n が項で、f がアリティ n の関数記号ならば、(f t₁ … t_n)_x [ t ] = f (t₁)_x [ t ] … (t_n)_x [ t ] 。

そして、φ_x [ t ] を次のように再帰的に定義する：

1. 原子論理式 P t₁ … t_n に対しては、(P t₁ … t_n)_x [ t ] = P (t₁)_x [ t ] … (t_n)_x [ t ] 。
2. (¬ φ)_x [ t ] = (¬ φ_x [ t ])
3. (φ ∧ ψ)_x [ t ] = (φ_x [ t ] ∧ ψ_x [ t ])
4. (φ ∨ ψ)_x [ t ] = (φ_x [ t ] ∨ ψ_x [ t ])
5. (φ → ψ)_x [ t ] = (φ_x [ t ] → ψ_x [ t ])
6. (φ ↔ ψ)_x [ t ] = (φ_x [ t ] ↔ ψ_x [ t ])
7. (∀x φ)_x [ t ] = ∀x φ 、(∃x φ)_x [ t ] = ∃x φ 。
8. y が x と異なる変数ならば、(∀y φ)_x [ t ] = ∀y φ_x [ t ] 、(∃y φ)_x [ t ] = ∃y φ_x [ t ] 。

次に、論理式 φ において項 t が変数 x に代入可能であるということを定義する。このことの直観的な意味は、φ が x について述べていることと同じことを φ_x [ t ] が t について述べているということである。例えば、。これに対して、。 代入可能性の正式な定義は次の通りである。

論理式 φ において項 t が変数 x に代入可能 (substitutable) であるということを次のように再帰的に定義する：

1. 原子論理式においては、常に t は x に代入可能である。
2. (¬ φ) において t が x に代入可能 　⇔　 φ において t が x に代入可能 。
3. (φ ∧ ψ) において t が x に代入可能 　⇔　 φ と ψ において t が x に代入可能 。
4. (φ ∨ ψ) において t が x に代入可能 　⇔　 φ と ψ において t が x に代入可能 。
5. (φ → ψ) において t が x に代入可能 　⇔　 φ と ψ において t が x に代入可能 。
6. (φ ↔ ψ) において t が x に代入可能 　⇔　 φ と ψ において t が x に代入可能 。
7. ∀y φ において t が x に代入可能 　⇔　 x ≠ y または x ∉ fr(φ) または（φ において t が x に代入可能かつ t の中に y が現れない）。
8. ∃y φ において t が x に代入可能 　⇔　 x ≠ y または x ∉ fr(φ) または（φ において t が x に代入可能かつ t の中に y が現れない）。

等号に関する公理について

等号に関する公理の 2. は、

x = y → (P t₁ … t_n → P u₁ … u_n) 　（ただし、P は n 変数述語記号で、u_i は t_i における x のいくつかを y で置き換えて得られる項である）

となっている。ここで、項 u が項 t における x のいくつかを y で置き換えて得られる項であるということは正確には次のように定義される。

変数 x と y を固定し、項の間の関係 ≈ を次のように再帰的に定義する：

1. x ≈ u 　⇔　 u = x または u = y 。
2. z が x と異なる変数ならば、z ≈ u 　⇔　 u = z 。
3. c 定数記号ならば、c ≈ u 　⇔　 u = c 。
4. t₁ , ..., t_n が項で、f がアリティ n の関数記号ならば、f t₁ … t_n ≈ u 　⇔　 t₁ ≈ u₁ , ..., t_n ≈ u_n であるような u₁ , ..., u_n が存在して u = f u₁ … u_n 。

t ≈ u であるとき、u は t における x のいくつかを y で置き換えて得られる項であるという。

健全性と完全性

文 φ が文の集合 Σ の論理的帰結であること ( $\Sigma \vDash \varphi$ ) と、φ が Σ の定理であること ( $\Sigma \vdash \varphi$ ) は全く別の仕方で定義されている。

健全性とは、Σ の定理はすべて Σ の論理的帰結であることである。

$\Sigma \vdash \varphi \Longrightarrow \Sigma \vDash \varphi$

完全性とは、Σ の論理的帰結はすべて Σ の定理であることである。

$\Sigma \vDash \varphi \Longrightarrow \Sigma \vdash \varphi$

古典一階述語論理は健全かつ完全である。

一階述語論理に関する定理

以下、健全性定理と完全性定理以外の重要な定理を列挙する。

1. コンパクト性定理 ： 文の集合 Σ のすべての有限部分集合がモデルを持つならば、Σ 自身もモデルを持つ。
2. レーヴェンハイム・スコーレムの定理 ： κ を無限基数とする。論理式全体の集合の濃度が κ であるような一階の言語における文の集合がモデルを持つなら、それは濃度 κ 以下のモデルも持つ。
3. 恒真論理式全体の集合は（言語にアリティ 2 以上の述語が一つでも含まれていると）決定可能でない。つまり、任意に論理式が与えられたとき、それが恒真であるか否かを判定するアルゴリズムは存在しない（「チューリングマシンの停止問題」を参照）。この結果はアロンゾ・チャーチとアラン・チューリングがそれぞれ独立に導き出した。正確には、恒真論理式のゲーデル数全体の集合は帰納的でないということである。
4. それでも、与えられた論理式が恒真であるとき、かつそのときにのみ 1 (yes) を出力して停止するアルゴリズムは存在する。ただし、恒真でない論理式を入力した場合はこのアルゴリズムは停止しないかもしれない。これを、恒真論理式全体の集合は準決定可能であるという。これは正確に述べれば、恒真論理式のゲーデル数全体の集合が帰納的可算であるということである。
5. 1 変数述語記号だけを非論理記号に持つ言語の恒真論理式全体の集合は決定可能である。

他の論理との比較

• 型つき一階述語論理は変項や項に型または種を導入したものである。型の個数が有限個であれば普通の一階述語論理と大きな違いはなく、有限個の単項述語で型を記述し、いくつかの公理を追加すればよい。真理値として Ω という特殊な型を持つ場合があるが、その場合の論理式は Ω 型の項となる。
• 弱二階述語論理は有限個の部分集合の量化を許すものである。
• 単項二階述語論理は部分集合、すなわち単項述語の量化のみを許すものである。
• 二階述語論理は部分集合および関係、すなわち全ての述語の量化を許すものである。
• 高階述語論理は述語を引数とする述語など、さらに一般化したものの量化を許す。
• 直観主義的一階述語論理は古典命題計算ではなく直観主義を導入するものである。例えば、¬¬φ は必ずしも φ と等しいとは限らない。
• 様相論理は様相演算子を追加したものである。これは、直観的に説明すれば、「～は必然的である」および「～は可能である」を意味する演算子である。
• 無限論理は無限に長い文を許す。例えば無限個の論理式の連言や選言が許されたり、無限個の変項を量化できたりする。
• 新たな量化子を加えた一階述語論理は、例えば「……であるような多くの x が存在する」といった意味の新たな量化子 Qx, ..., を持つ。

こうした論理の多くは、一階述語論理の何らかの拡張と言える。これらは、一階述語論理の論理演算子と量化子を全て含んでいて、それらの意味も同じである。リンドストレムは、一階述語論理の拡張には、レーヴェンハイム・スコーレムの下降定理とコンパクト性定理の両方を満足するものが存在しないことを示した。この定理の内容を精確に述べるには、論理が満たしていなければならない条件を数ページにわたって列挙する必要がある。例えば、言語の記号を変更しても各文の真偽が基本的に変わらないようになっていなければならない。

一階述語論理のいくぶんエキゾチックな等価物には、次のものがある。順序対構成をもつ一階述語論理は、特別な関係として順序対の射影を持つ関係代数（これはタルスキと Givant によって構築された）と精確に等価である。

関連項目

• 数理論理学
• ロビンソン算術
• コンパクト性定理
• ゲーデルの完全性定理
• ゲーデルの不完全性定理
• エルブラン化
• 論理記号の一覧
• 冠頭標準形
• 分析論前書
• Prolog
• 関係代数 (関係モデル)
• 関係モデル
• スコーレム標準形
• 真理値表

参考文献

• D.ヒルベルト、W.アッケルマン 著、伊藤誠（訳） 編『記号論理学の基礎（第３版 ）』大阪教育図書社、1954年。