一階述語論理
一階述語論理（いっかいじゅつごろんり、First-Order Logic）は、現代の数学、計算機科学、哲学において最も広く用いられている人工言語（形式言語）の一つ。
命題全体を一つのカタマリとして扱った「命題論理」とは異なり、一階述語論理では文を「主語（個体）」と「述語（性質や関係）」に分解し、さらに「すべての～」「ある～」といった量化（全称・存在）を扱うことができる。
第1章:なぜ一階述語論理が必要なのか?
[編集]命題論理では、次の推論の正しさを証明できません。
- すべての人間は死ぬ
- ソクラテスは人間である
- ゆえに、ソクラテスは死ぬ
命題論理ではこれらをそれぞれ独立した命題P, Q, Rとしか扱えないため、「人間」や「ソクラテス」といった内部の結びつきを表現できないのである。一階述語論理は、この結びつきを記号化するために生まれた。
第2章:構成要素（文法）
[編集]一階述語論理の言語は、主に以下の記号を使って構成されます。
基礎的な記号
[編集]- 個体定数（Constants）- 固有の対象を表す名前。（例:a=ソクラテス）
- 個体変数（Variables）- 特定しない対象を表す変数。x, y, z...
- 述語記号（Predicates）- 対象の性質や関係を表す。（例:H(x)=「xは人間である」、M(x)=「xは死ぬ」）
- 論理結合子（Connectives）- 命題論理と同じ。否定（¬）、かつ（∧）、または（∨）、ならば（⇒）など。
量化記号（クォンティファイア）
[編集]ここが一階述語論理の核心です。
- 全称記号（∀ - Universal Quantifier）-「すべての」「任意の」を意味する。
- 存在記号（∃ - Existential Quantifier）-「ある～が存在する」「少なくとも論理的に1つは～」を意味する。
「一階（First-Order）」の由来
[編集]変数として動かせる対象が「個体（モノ）」に限られているため。「述語そのもの（性質の性質など）」を全称や存在で縛ることはできない（それをやるのは二階以上の高階述語論理になる）。
第3章:翻訳の例（定式化）
[編集]先ほどの「ソクラテスの三段論法」を、一階述語論理で表現してみよう。
- H(x)：xは人間である
- M(x)：xは死ぬ
- s：ソクラテス
| 日常言語 | 一階述語論理の論理式 | 読み方 |
|---|---|---|
| 全ての人間は死ぬ。 | ∀x(H(x)→M(x)) | 全てのxについて、もしxが人間なら、xは死ぬ。 |
| ソクラテスは人間である。 | H(s) | ソクラテスは人間である。 |
| 結論:ソクラテスは死ぬ。 | M(s) | ソクラテスは死ぬ。 |
この前提から、結論が論理的に導き出せることを一階述語論理の「推論規則」を用いて、厳密に証明することができる。
第4章:意味論（モデル理論）
[編集]論理式が「正しい（真）」か「間違い（偽）」かを決めるには、その記号が何を指しているのかという解釈（モデル）を与える必要がある。一階述語論理の意味論は、タルスキの定義に基づき、以下の3つを設定して考える。
- 議論領域（ドメイン）- 考えている対象の全集合（例:すべての人間、自然数全体など）。
- 定数の割り当て - 個体定数が領域のどの具体的な要素を指すか。
- 述語の割り当て - 述語記号が領域のどんな性質や関係（部分集合）を表すか。
これらが決まって初めて、∀x'P(x)が真か偽かが確定する。
重要な性質
[編集]一階述語論理は、非常に美しい数学的性質を持っています。
- 健全性（Soundness）- 構文的に「証明できる」ならば、それは意味論的に常に「真（妥当）」である。
- 完全性（Completeness）- ゲーデルが証明。意味論的に常に「真」である論理式は、必ず有限ステップで「証明できる」。
- 決定不動性（Undecidability）- チャーチとチューリングが証明。ある論理式が正しいかどうかを、自動で判定する万能なプログラム（アルゴリズム）は作れない。