一階述語論理
一階述語論理（いっかいじゅつごろんり、first-order predicate logic）とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理（にかいじゅつごろんり、second-order predicate logic）と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理（こうかいじゅつごろんり、higher-order predicate logic）という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。
命題論理では文を構成する最も基本的な命題（原子命題）は命題記号と呼ぶ一つの記号によって表していた。それに対し、一階述語論理においては、最も基本的な命題は原子論理式と呼ぶ記号列によって表す。原子論理式とは述語記号と呼ぶ記号と、項と呼ぶものの列、からなる "P t" … "t" という形の記号列であり、これは個体の間の関係を表すものである。
命題論理にない一階述語論理のもう一つの特徴は量化 (quantification) である。例えば、定言的命題論理の範囲において、次のような推論の妥当性を扱うことはできない：
一階述語論理では、このような「すべての…について」という表現や、また「ある…について」といった表現を扱えるように、全称量化記号 (universal quantifier) と呼ぶ記号 ∀ と存在量化記号 (existential quantifier) と呼ぶ記号 ∃ を新たに導入する。これらを用いると「すべての "x" について φ である」という命題は ∀"x"φ 、「ある "x" に対して φ である」は ∃"x"φ と表される。これらの記号を用いると上の三つの文はそれぞれ、例えば、
のように記号化することができる。ここで、"Px" と "Qx" はそれぞれ「"x" は人間である」「"x" は死ぬ」を表し、"a" はソクラテスを表すことを意図している。上の日本語による定言命題推論の妥当性は不決定的だが、仮言命題推論化されるならば、一階述語論理において "Qa" が、{ ∀x (Px" → "Qx) , "Pa" } の論理的帰結 (logical consquence) であるという事実に反映される。一般に、論理式 φ が論理式の集合 Σ の論理的帰結であるとは、Σ の論理式のすべてをみたす解釈は必ず φ もみたすこととして定義され、これは、あるいくつかの前提からある結論が論理的に導かれるという概念の数学的な定式化である。
命題論理においては、論理式の解釈は各命題記号に対する真理値 0 , 1 の割り当て与えられた。これに対して、一階述語論理の論理式の解釈は構造 (structure) と呼ばれ、これは領域 (universe, domain) と呼ぶ空でない集合と、それぞれの非論理記号（述語記号・関数記号・定数記号）の "意味" の割り当てからなる。領域とは「すべての "x" について」といったときの "x" が動きうる値の範囲である。一階述語論理の論理式は構造を一つ与えることによって真偽が決定される。
二階述語論理（およびそれ以上の高階述語論理）では、述語および関数に対する量化を導入する。
一階述語論理は、数学のほぼ全領域を形式化するのに十分な表現力を持っている。実際、現代の標準的な集合論の公理系 ZFC は一階述語論理を用いて形式化されており、数学の大部分はそのように形式化された ZFC の中で行うことができる。すなわち、数学の命題は一階述語論理の論理式によって記述することができ、そのように論理式で記述された数学の定理には ZFC の公理からの形式的証明 (formal proof) が存在する。このことが一階述語論理が重要視される理由の一つである。この他にペアノ算術のように単独で形式化する理論もある。
一階述語論理の言語（一階の言語）は次のものからなる：
一階の言語は、それが等号を持つかどうか、非論理記号に何を持っているかを決めることによって定まる。例えば集合論においては、等号を持ち、非論理記号としてはアリティ 2 の述語記号 ∈ だけをもつ一階の言語（集合論の言語）が使われる。以下に一階の言語について、いくつかの注意を述べる。
一階述語論理の項 (term) は次のように帰納的に定義される：
項というのは直観的には議論領域に属するある対象を表す"名前"の役割をもった記号列である。
例． 自然数論の言語は等号を持つ一階の言語で、非論理記号として、2 変数述語記号 < 、1 変数関数記号 S 、2 変数関数記号 + , · と定数記号 0 を持つ。定義より、
はすべて項である。 +S0S0 や +0x" といった前置記法は読みにくいため、これらの項を表すのに、通常使われている S0 + S0 や 0 + "x" のような表現(中置記法)が用いられることもある。したがって · Sx"+ 0x" は中置記法では Sx" · (0 + "x") のように表される。
項が何らかの対象を表す記号列であったのに対して、論理式は何らかの命題を表すものである。論理式は原子論理式と呼ぶ最も基本的な論理式から結合記号と量化記号を繰り返し用いることによって形成される。まず、原子論理式は次のように定義される：
原子論理式を用いて、論理式 (well-formed formula, wff) あるいは式 (formula) は次のように帰納的に定義される：
例． 再び自然数論の言語を考える。定義から、
はすべて原子論理式（したがって論理式）であり、
はすべて論理式である。=+S0S0SS0 , <0Sx" などの論理式は分かりやすさのため、述語記号を項の間に書いた +S0S0 = SS0 , 0 < Sx" のような表現で表すことが多い。上で述べた項に関する略記法も用いれば、+S0S0 = SS0 はさらに S0 + S0 = SS0 と表される。また、(¬ =+S0S0SS0) や (=+0x"S0 ∧ =+S0S0SS0) などの論理式は、最も外側の括弧を省略して、¬ =+S0S0SS0 , =+0x"S0 ∧ =+S0S0SS0 のように表すこともある。
自然数論の言語における論理式 S0 + S0 = SS0 の各記号を通常の意味で解釈すれば「1 + 1 = 2」となり、これは真である論理式である。(¬ S0 + S0 = SS0) は「1 + 1 ≠ 2」となるので通常の解釈で偽なる論理式である。また、変数の動く範囲（議論領域）は自然数全体の集合だとすれば、論理式 ∀"x" 0 < Sx" は「すべての自然数 "n" について 0 < "n" + 1」という意味になり、これは真である論理式であることが分かる。一方、論理式 0 +x" = S0 の意味を考えてみると、「0 + x = 1」となるがこれは真であるか偽であるかを判断することができない。なぜなら、"x" という変数が何を表しているかが決まっていないからである。このようなとき、"x" は論理式 0 +"x" = S0 における自由変数 (free variable) であると言われる。正式には、各論理式 φ に対して、"φ における自由変数全体の集合" fr(φ) を次のように再帰的に定義する：
論理式 φ が自由変数を一切持たないとき、つまり fr(φ) = ∅ のとき、φ は閉論理式 (closed formula) あるいは文 (sentence) と呼ぶ。直観的には、文とは記号に解釈を与えて意味を考えたときに正しいか正しくないかが決まるような論理式である。S0 + S0 = SS0 や ∀"x" 0 < Sx" は文であるが、fr(0 +x" = S0) = { "x" } より 0 +"x" = S0 は文でない。
はじめに述べたように、一階述語論理の論理式の解釈は構造と呼ぶものによって与えられる。構造は変数が動く領域とそれぞれの非論理記号に対する "意味" の割り当てからなる。正式には、構造は次のように定義される。
"M" が一階の言語に対する構造であるとき、"M" の領域 |"M"| の要素を "M" の個体 (individual) と呼ぶ。
上で見たように、自由変数を持たない論理式（すなわち文）は解釈（構造）を一つ与えることで、正しいか正しくないかが定まる。構造 "M" を与えたとき、文 φ が正しい命題になっているならば、φ は解釈 "M" において真 (true) であるといい、正しくない命題である場合、φ は "M" において偽 (false) であるという。以下で、これらの真偽の概念をより正確に定義する。ただし、論理式の真偽の定義にはいくつかの異なる（同値な）方法があり、ここで述べる定義はその内の一つである。
直観的には、項 "t" の値 "t" ("s") とは、各変数 "x" が "M"の個体 "s"("x") を表すとしたとき、"t" が表す "M" の個体のことである。
次に、「構造 "M" が個体の割り当て関数 "s" によって論理式 φ を充足する」と言うことを定義する。"M" が "s" によって φ を充足するとは、各変数 "x" は "s"("x") を表すとし、各非論理記号は "M" によって与えられた意味を表すとしたとき、φ が正しい命題になっているということである。
特に φ が文である場合は、すべての個体の割り当て関数 "s" に対して "M"(φ, "s") = 1 であるか、すべての個体の割り当て関数 "s" に対して "M"(φ, "s") = 0 であるかのいずれかであることが示される。そこで、前者の場合に φ は "M" において真であるといい、後者の場合に φ は "M" において偽であるという。すなわち、構造 "M" と文 φ に対して、
と定義する。φ が "M" において真であるとき、"M" は φ のモデル (model) であるともいう。また、"M" が文の集合 Σ のすべての要素のモデルであるとき、単に "M" は Σ のモデルであるという。
Σ を論理式の集合とし、φ を論理式とする。Σ に属するすべての論理式 ψ に対して "M"(ψ, "s") = 1 であるような任意の構造 "M" と "M" の個体の割り当て関数 "s" が "M"(φ, "s") = 1 をみたすとき、φ は Σ の論理的帰結 (logical consquence) であるといい、formula_1 と書く。論理式 φ と ψ が formula_2 かつ formula_3 をみたすとき、φ と ψ は論理的に同値 (logically equivalent) であるという。また、φ が ∅ の論理的帰結である場合、すなわち任意の構造 "M" と "M" の個体の割り当て関数 "s" に対して "M"(φ, "s") = 1 であるとき、φ は恒真 (valid) であるという。φ と ψ が論理的に同値であることは、(φ ↔ ψ) が恒真であることと同値である。
命題論理においては、論理公理 (logical axiom) と呼ぶ論理式の集合と、ある論理式たちから新たな論理式を導出する規則（推論規則）を導入し、論理公理から推論規則の有限回の適用によって得られる論理式全体とトートロジー全体が一致するようにすることができる（命題論理の健全性と完全性）。一階述語論理においても、適切に論理公理と推論規則を導入することで、論理公理から推論規則を使って導出される論理式全体と恒真論理式全体が一致するようにできる。
形式的証明の定義の仕方はひとつではなく、様々な異なる（等価な）方法がある。ここで述べる定義はヒルベルト流計算の典型例であり、これは異なる公理を多数用意して推論規則を少なくするスタイルをとっている。ゲンツェン流の形式的証明では逆に、公理を少なくして推論規則を多く用いている。ここで述べるものと異なる証明可能性の定義については「自然演繹」「シークエント計算」などを参照。
以下の形の論理式すべてを論理公理とする。ここで、"x", "y" は変数、"t", "t" , ..., "t" は項、φ, ψ は論理式を表す：
量化記号に関する公理 1. における φ [ "t" ] とは、論理式 φ において "束縛されていない" 変数 "x" をすべて項 "t" で置き換えて得られる論理式を表す（正確な定義は後述）。
推論規則とは、あるいくつかの論理式から別の論理式を導出するための規則である。これは正確には、論理式全体の集合の上の関係として定義される。推論規則には様々なものが考えられるが、ここで用いる推論規則はモーダス・ポーネンス (modus ponens) と呼ぶ規則と全称化 (generalization) と呼ぶ規則の二つである。
モーダス・ポーネンスとは、φ と (φ → ψ) から ψ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる：
(φ, φ, φ) ∈ MP であるとき、φ は φ, φ からのモーダス・ポーネンスによる導出であるという。
全称化規則とは、"x" が変数のとき、φ から ∀"x" φ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる：
(φ, φ) ∈ GEN であるとき、φ は φ からの全称化による導出であるという。
論理式 φ が論理式の集合 Σ から証明可能であるとは、Σ に属する論理式と論理公理から推論規則の有限回の適用によって φ が得られることを意味する。そして、Σ に属する論理式と論理公理から φ を導出する仮定を示した論理式の有限列を、Σ からの φ の形式的証明とよぶ。これらの概念は次のように厳密に定義することができる。
φ [ "t" ] は、論理式 φ において "束縛されていない" 変数 "x" をすべて項 "t" で置き換えて得られる論理式を表すと述べた。正確には、φ [ "t" ] は再帰によって次に述べるような仕方で定義される。
次に、論理式 φ において項 "t" が変数 "x" に代入可能であるということを定義する。このことの直観的な意味は、φ が "x" について述べていることと同じことを φ [ "t" ] が "t" について述べているということである。例えば、。これに対して、。
代入可能性の正式な定義は次の通りである。
等号に関する公理の 2. は、
となっている。ここで、項 "u" が項 "t" における "x" のいくつかを "y" で置き換えて得られる項であるということは正確には次のように定義される。
文 φ が文の集合 Σ の論理的帰結であること ( formula_1 ) と、φ が Σ の定理であること ( formula_4 ) は全く別の仕方で定義されている。
健全性とは、Σ の定理はすべて Σ の論理的帰結であることである。
完全性とは、Σ の論理的帰結はすべて Σ の定理であることである。
古典一階述語論理は健全かつ完全である。
以下、健全性定理と完全性定理以外の重要な定理を列挙する。こうした論理の多くは、一階述語論理の何らかの拡張と言える。これらは、一階述語論理の論理演算子と量化子を全て含んでいて、それらの意味も同じである。リンドストレムは、一階述語論理の拡張には、レーヴェンハイム・スコーレムの下降定理とコンパクト性定理の両方を満足するものが存在しないことを示した。この定理の内容を精確に述べるには、論理が満たしていなければならない条件を数ページにわたって列挙する必要がある。例えば、言語の記号を変更しても各文の真偽が基本的に変わらないようになっていなければならない。
一階述語論理のいくぶんエキゾチックな等価物には、次のものがある。順序対構成をもつ一階述語論理は、特別な関係として順序対の射影を持つ関係代数（これはタルスキと Givant によって構築された）と精確に等価である。