一階述語論理
一階述語論理(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)
変数(あるいは個体変数)と呼ぶ記号の集合: V=\{x_1,\,x_2,\,\cdots\}
結合記号: \lnot, \land , \lor, \Rightarrow, \Leftrightarrow
量化記号: \forall, \exists
括弧: ( , ) , [ , ] , \{ , \}
等号: = (含まなくてもよい。)
非論理記号 (nonlogical symbol)
述語記号と呼ぶ記号の集合(有限集合でも無限集合でもよい)。各述語記号にはアリティ(arity)と呼ぶ引数の個数に相当する正の整数が一つ対応しているものとする。
関数記号と呼ぶ記号の集合(有限集合でも無限集合でもよい)。各関数記号もアリティを持っているものとする。
定数記号と呼ぶ記号の集合(有限集合でも無限集合でもよい)。
一階の言語は、それが等号を持つかどうか、非論理記号に何を持っているかを決めることによって定まる。例えば集合論においては、等号を持ち、非論理記号としてはアリティ 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) は次のように帰納的に定義される:
変数と定数記号はすべて項である。
t_1,\,\cdots,\,t_n が項で、f がアリティ n の関数記号ならば、ft_1,\,\cdots,\,t_n は項である。
上記の 1. と 2. によって項とされるものだけが項である。
項というのは直観的には議論領域に属するある対象を表す"名前"の役割をもった記号列である。
例. 自然数論の言語は等号を持つ一階の言語で、非論理記号として 、1 変数関数記号 S 、2 変数関数記号 + , \cdot と定数記号 0 を持つ。定義より、
x_1 ,  x_5 ,  0 ,  Sx_1 ,  S0 ,  SS0 ,  +S0S0 ,  +0 x_5 ,  \cdot Sx_1 + 0 x_5
はすべて項である。 +S0S0 や +0 x_5 といった前置記法は読みにくいため、これらの項を表すのに、通常使われている S(0)+S(0) や 0+x_5 のような表現(中置記法)が用いられることもある。したがって   \cdot Sx_1 + 0 x_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) は次のように帰納的に定義される:
原子論理式は論理式である。
\phi と \psi が論理式ならば、(\lnot\phi) , (\phi\land\psi) , (\phi\lor\psi) , (\phi\Rightarrow\psi) , (\phi\Leftrightarrow\psi) は論理式である。
\phi  が論理式で x  が変数ならば、(\forall x\phi) , (\exists x\phi) は論理式である。
上記の 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) を次のように再帰的に定義する:
\phi が原子論理式ならば、fr(\phi) は記号列 φ に現れるすべての変数からなる集合である。
fr[(\lnot\phi)]= fr(\phi) 。
fr[(\phi\land\psi)] = fr[(\phi\lor\psi)] = fr[(\phi\Rightarrow\psi)] = fr[(\phi\Leftrightarrow\psi)] = fr(\phi) \cup fr(\psi) 。
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) で次をみたすものをいう:
P がアリティ n の述語記号ならば、F(P) \subseteq D^n 、すなわち F(P) は D 上の n 項関係である。
f がアリティ n の関数記号ならば、F(f) : D^n \to D 、すなわち F(f) は D 上の n 項演算である。
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) が次のように再帰的に定義される:
変数 x に対しては、x M(s) = s(x) 。
定数記号 c に対しては、c M(s) = c M 。
t1 , ..., tn が項で、f がアリティ n の関数記号ならば、(f t1 … tn)M(s) = f M (t1M(s), ..., tnM(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 } を次のように再帰的に定義する:
M(t1 = t2 , s) = 1  ⇔  t1M(s) = t2M(s) 。
P がアリティ n の非論理述語記号ならば、 M(P t1 … tn , s) = 1  ⇔  (t1M(s), ..., tnM(s)) ∈ P M 。
M((¬ φ), s) = 1  ⇔  M(φ, s) = 0 。
M((φ ∧ ψ), s) = 1  ⇔  M(φ, s) = 1 かつ M(ψ, s) = 1 。
M((φ ∨ ψ), s) = 1  ⇔  M(φ, s) = 1 または M(ψ, s) = 1 。
M((φ → ψ), s) = 1  ⇔  M(φ, s) = 0 または M(ψ, s) = 1 。
M((φ ↔ ψ), s) = 1  ⇔  M(φ, s) = M(ψ, s) 。
M(∀x φ, s) = 1  ⇔  すべての m ∈ |M| に対して M(φ, s[x|m]) = 1 。
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, t1 , ..., tn は項、φ, ψ は論理式を表す:
トートロジー(命題論理におけるトートロジーの命題記号を一階の論理式で置き換えて得られる論理式)
∀x φ → φx [ t ]  (ただし、φ において t が x に代入可能(後述)の場合に限る)
∀x (φ → ψ) → (∀x φ → ∀x ψ)
∀x (¬ φ) ↔ (¬ ∃x φ)
等号に関する公理(言語が等号を持つ場合に限る)
x = x
x = y → (P t1 … tn → P u1 … un)  (ただし、P は n 変数述語記号で、ui は ti における x のいくつかを y で置き換えて得られる項である)
量化記号に関する公理 1. における φx [ t ] とは、論理式 φ において "束縛されていない" 変数 x をすべて項 t で置き換えて得られる論理式を表す(正確な定義は後述)。
推論規則とは、あるいくつかの論理式から別の論理式を導出するための規則である。これは正確には、論理式全体の集合の上の関係として定義される。推論規則には様々なものが考えられるが、ここで用いる推論規則はモーダス・ポーネンス (modus ponens) と呼ぶ規則と全称化 (generalization) と呼ぶ規則の二つである。
モーダス・ポーネンスとは、φ と (φ → ψ) から ψ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる:
MP = { (φ, (φ → ψ), ψ) | φ と ψ は論理式 } 。
(φ1, φ2, φ3) ∈ MP であるとき、φ3 は φ1, φ2 からのモーダス・ポーネンスによる導出であるという。
全称化規則とは、x が変数のとき、φ から ∀x φ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる:
GEN = { (φ, ∀x φ)  | φ は論理式かつ x は変数 } 。
(φ1, φ2) ∈ GEN であるとき、φ2 は φ1 からの全称化による導出であるという。
論理式 φ が論理式の集合 Σ から証明可能であるとは、Σ に属する論理式と論理公理から推論規則の有限回の適用によって φ が得られることを意味する。そして、Σ に属する論理式と論理公理から φ を導出する仮定を示した論理式の有限列を、Σ からの φ の形式的証明とよぶ。これらの概念は次のように厳密に定義することができる。
φ を論理式、Σ を論理式の集合とする。Σ からの φ の形式的証明 (formal proof) あるいは証明 (proof) とは、論理式の有限列 (φ0, ..., φn) で次をみたすものをいう:
φn = φ 。
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 に対して ux [ t ] を次のように再帰的に定義する:
xx [ t ] = t 。
y が x と異なる変数ならば、yx [ t ] = y 。
c 定数記号ならば、cx [ t ] = c 。
t1 , ..., tn が項で、f がアリティ n の関数記号ならば、(f t1 … tn)x [ t ] = f (t1)x [ t ] … (tn)x [ t ] 。
そして、φx [ t ] を次のように再帰的に定義する:
原子論理式 P t1 … tn に対しては、(P t1 … tn)x [ t ] = P (t1)x [ t ] … (tn)x [ t ] 。
(¬ φ)x [ t ] = (¬ φx [ t ])
(φ ∧ ψ)x [ t ] = (φx [ t ] ∧ ψx [ t ])
(φ ∨ ψ)x [ t ] = (φx [ t ] ∨ ψx [ t ])
(φ → ψ)x [ t ] = (φx [ t ] → ψx [ t ])
(φ ↔ ψ)x [ t ] = (φx [ t ] ↔ ψx [ t ])
(∀x φ)x [ t ] = ∀x φ 、(∃x φ)x [ t ] = ∃x φ 。
y が x と異なる変数ならば、(∀y φ)x [ t ] = ∀y φx [ t ] 、(∃y φ)x [ t ] = ∃y φx [ t ] 。
次に、論理式 φ において項 t が変数 x に代入可能であるということを定義する。このことの直観的な意味は、φ が x について述べていることと同じことを φx [ t ] が t について述べているということである。例えば、。これに対して、。
代入可能性の正式な定義は次の通りである。
論理式 φ において項 t が変数 x に代入可能 (substitutable) であるということを次のように再帰的に定義する:
原子論理式においては、常に t は x に代入可能である。
(¬ φ) において t が x に代入可能  ⇔  φ において t が x に代入可能 。
(φ ∧ ψ) において t が x に代入可能  ⇔  φ と ψ において t が x に代入可能 。
(φ ∨ ψ) において t が x に代入可能  ⇔  φ と ψ において t が x に代入可能 。
(φ → ψ) において t が x に代入可能  ⇔  φ と ψ において t が x に代入可能 。
(φ ↔ ψ) において t が x に代入可能  ⇔  φ と ψ において t が x に代入可能 。
∀y φ において t が x に代入可能  ⇔  x ≠ y または x ∉ fr(φ) または(φ において t が x に代入可能かつ t の中に y が現れない)。
∃y φ において t が x に代入可能  ⇔  x ≠ y または x ∉ fr(φ) または(φ において t が x に代入可能かつ t の中に y が現れない)。
等号に関する公理の 2. は、
x = y → (P t1 … tn → P u1 … un)  (ただし、P は n 変数述語記号で、ui は ti における x のいくつかを y で置き換えて得られる項である)