一階述語論理：構文・意味論・主要定理・応用

基本的な構文と構成要素

一階述語論理の言語は、明確な生成規則によって組み合わされる数種類の記号から構成される。原子的な要素には、定項記号（特定の要素の名前）、変数、関数記号（要素を返すもの）、述語記号（真理値を返すもの）がある。これらから項を作り、さらに述語を項に適用して原子式を作る。形式文法と生成規則の集合は別途提示されることが多い。構文の簡単な案内は構文に関する注記を参照。一階述語論理には、命題論理と共通する通常のブール結合子も含まれる。命題論理と比較できる。

量化子、結合子と例

二つの量化子により、この言語は多数の対象について語ることができる。全称量化子（ここでは∀で表す）は、ある性質が領域のすべての要素について成り立つことを表す。一方、存在量化子∃は、ある要素がその性質をもつと主張する。否定、連言、選言、含意は、命題論理の場合とほぼ同様に量化された式を結合する。量化子の規則についての平易な解説は量化子入門で利用できる。意味論的には、「∀x P(x) → ∃y Q(y)」のような文は、特定の構造において述語記号と関数を解釈することで評価される。意味論的評価の詳細は意味論を参照。

意味論、モデルと解釈

一階述語論理における意味は、構造またはモデル、すなわち談話領域と非論理記号の解釈によって与えられる。ある文は、その解釈のもとで通常の再帰的規則が真を割り当てるとき、その構造において真である。充足可能性、妥当性、論理的帰結といったモデル理論的概念は中心的である。ある文が充足可能であるとは、それを真にするモデルが少なくとも一つ存在することであり、妥当であるとは、すべてのモデルで真となることである。モデル理論の入門的資料としては、モデル理論および例がある。

主要なメタ定理と限界

いくつかの一般的な結果は、一階述語論理の能力と境界を説明する。ゲーデルの完全性定理は、ある式が意味論的に妥当であることと、適切な演繹体系において形式的証明をもつことが正確に同値であると確立する。コンパクト性定理とレーヴェンハイム＝スコーレムの定理は、モデルの大きさ、および有限・無限の文脈間での真理の移行について注目すべき帰結を示す。同時に、チャーチとチューリングは、一階述語論理が一般には決定不能であることを示した。すなわち、すべての文について妥当性を判定するアルゴリズムは存在しない。形式的な記述と証明については、完全性と決定可能性を参照。

歴史、役割と応用

一階述語論理は、数学と論理学の形式化の一環として19世紀後半から20世紀初頭にかけて発展し、現代数学の大部分および集合論などの形式理論の標準的枠組みとなった。たとえば、ツェルメロ＝フレンケル集合論は通常、一階述語論理で定式化される。これはモデル理論、証明論、データベース理論、コンピュータ科学の一部など、多様な分野の基盤となっている。入門的な概説と応用は参考資料にまとめられている。

二階述語論理のような、より表現力の高い体系とは区別される一階述語論理は、一つの均衡を実現している。数学の大部分を形式化できるほど表現力がある一方で、強力な一般メタ定理を備える。しかし、有限性のように、単一の一階文では捉えられない性質もある。このようなトレードオフが、論理学とその基礎における中心的な位置を形づくっている。