述語論理と量化子
「すべて」と「存在する」を扱う
入門（高校〜大学1年レベル）
このページの目標
命題論理では表せなかった「すべての」「ある」を扱う述語論理に進む。述語と変数、量化子 $\forall, \exists$、そして束縛変数と自由変数の違いを理解する。
1. 命題論理の限界
命題論理は命題を分解しない原子として扱う。だが「すべての自然数は $0$ 以上である」という主張は、個々の自然数についての無数の命題をまとめたものであり、命題論理の枠では一つの命題記号 $p$ としてしか扱えない。これでは「$n$ が変わると主張も変わる」という構造を表せない。
そこで命題の内部に踏み込み、対象（変数）と性質・関係（述語）を分けて扱うのが述語論理（一階述語論理）である。
歴史メモ：述語論理は誰が始めたか
現代の述語論理を事実上創始したのは ゴットロープ・フレーゲ（Gottlob Frege）である。著書『概念記法』（Begriffsschrift, 1879）で、命題を述語と引数に分解し、量化子（$\forall, \exists$）と束縛変数を初めて体系的に導入した。
ほぼ同時期、チャールズ・S・パース（と弟子 O. H. ミッチェル、1883–85 年頃）が独立に量化の記法を開発し、量化子の考え方を広めた。現代に近い記号は ジュゼッペ・ペアノが整備している。
本記事が扱う一階述語論理を独立した体系として最初に明確に定式化したのは、ヒルベルトとアッカーマン『理論論理学の基礎』（1928）である。なお遠い先祖として、量化を部分的に扱うアリストテレスの三段論法（項論理）があるが、量化子と束縛変数を備えた本格的な述語論理はフレーゲに始まる。
2. 述語と変数
述語とは、対象（個体）を引数に取り、真理値（真または偽）を返す表現である。$P(x)$ は「$x$ は性質 $P$ を持つ」、$Q(x, y)$ は「$x$ と $y$ は関係 $Q$ にある」を表す。引数の数を述語の項数という。
- $\mathrm{Even}(x)$：「$x$ は偶数である」（$\mathrm{Even}(4)$ は真、$\mathrm{Even}(3)$ は偽）
- $\mathrm{Less}(x, y)$：「$x < y$」（$\mathrm{Less}(2, 5)$ は真）
述語に具体的な対象を入れるまで、真偽は定まらない。$P(x)$ の真偽は、変数へ何を代入するかに依存する。
議論領域（domain of discourse）とは、変数が動く範囲として最初に決めておく集合のことである。$\forall x$ や $\exists x$ の「すべて」「存在する」は、つねにこの領域の中での話であり、領域を決めなければ論理式の真偽は定まらない。
たとえば $\exists x\, (x^2 = 2)$ は、議論領域を実数全体 $\mathbb{R}$ とすれば真だが、有理数全体 $\mathbb{Q}$ でも自然数全体 $\mathbb{N}$ でも偽である。同じ論理式が領域しだいで真偽を変えるのだから、「何についての主張なのか」は式と同じくらい重要である。慣例として、文脈から明らかな場合は領域を書き添えないことが多いが、省略されているだけで消えているわけではない。
3. 量化子：$\forall$ と $\exists$
全称量化 $\forall x\, P(x)$：「すべての $x$ について $P(x)$ が成り立つ」。
存在量化 $\exists x\, P(x)$：「$P(x)$ を満たす $x$ が少なくとも一つ存在する」。
量化子は、述語に対象を一つずつ代入する代わりに、「対象全体にわたって」主張をまとめる。これで命題論理の限界を超え、数学の文をそのまま書けるようになる。
- $\forall n\, (\mathrm{Even}(n) \lor \mathrm{Odd}(n))$：すべての自然数は偶数か奇数である
- $\exists x\, (x^2 = 2)$：$2$ の平方根が存在する（議論領域を実数全体とする場合。$\mathbb{Q}$ や $\mathbb{N}$ では偽）
- $\forall \varepsilon\, \exists \delta\, \dots$：$\varepsilon$-$\delta$ 論法の連続性の定義
量化子の順序は意味を変える。$\forall x\, \exists y\, P(x,y)$（どの $x$ にもそれ用の $y$ がある）と $\exists y\, \forall x\, P(x,y)$（すべての $x$ に共通の $y$ が一つある）は別の主張である。$\varepsilon$-$\delta$ 論法で「$\delta$ は $\varepsilon$ に依ってよい」のはこの順序のためである。
ワンポイント：量化子と否定 否定を量化子の内側へ入れると、$\forall$ と $\exists$ は入れ替わる。 $$\neg \forall x\, P(x) \iff \exists x\, \neg P(x), \qquad \neg \exists x\, P(x) \iff \forall x\, \neg P(x)$$ 「すべてが $P$ ではない」は「$P$ でないものが一つはある」、「$P$ なものは存在しない」は「どれも $P$ ではない」と読み替えられる。命題論理のド・モルガンの法則を、量化子まで広げたものと見てよい。反例を挙げて全称命題を否定する、という日常的な証明の作法はこの同値そのものである。
4. 束縛変数と自由変数
量化子 $\forall x$ や $\exists x$ の作用範囲にある変数 $x$ を束縛変数という。束縛変数の名前は他の使われていない文字に付け替えても式の意味は変わらない（$\forall x\, P(x)$ と $\forall z\, P(z)$ は同じ）。
どの量化子にも束縛されていない変数を自由変数という。自由変数は値を決めないと真偽が定まらない。
束縛変数の付け替えが自由にできること（$\alpha$ 変換）は、証明を機械的に扱う際に重要になる。同じ意味の式を同じものと見なす仕組みは、λ計算 でも中心的な役割を果たす。
本記事が扱うのは「一階」述語論理である：ここまで量化してきた変数 $x$ は、つねに個体（人・数など、議論領域の要素）を指していた。個体だけを量化する体系を一階述語論理と呼ぶ。これに対し、述語や性質そのものを量化して $\forall P\,(P(a) \rightarrow P(b))$（あらゆる性質について、$a$ がそれを持つなら $b$ も持つ）のように書ける体系を高階述語論理という。高階では「すべての性質について」と言えるため数学的帰納法を単一の公理として書けるなど表現力が上がるが、その代わり完全性定理（一階述語論理で成り立つ「意味的に真なら証明できる」という性質）が失われる。詳しくは 単純型理論 = HOL（高階論理の土台） を参照。
まとめ
この章のポイント
- 述語論理：命題の内部に踏み込み、対象（変数）と性質・関係（述語）を分ける
- 量化子：$\forall$（すべての）と $\exists$（存在する）で対象全体にわたる主張を表す
- 量化子の順序は意味を変える（$\forall\exists$ と $\exists\forall$ は別物）
- 束縛変数は名前を付け替え可能、自由変数は値しだいで真偽が決まる
参考文献
- Frege, G. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle: Nebert.（述語・引数への分解と量化子・束縛変数の初出）
- Peirce, C. S. (1885). "On the Algebra of Logic: A Contribution to the Philosophy of Notation". American Journal of Mathematics, 7(2), 180–202.（量化の独立な定式化）
- Hilbert, D., & Ackermann, W. (1928). Grundzüge der theoretischen Logik. Berlin: Springer.（一階述語論理を独立の体系として定式化）
- Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). Academic Press.（議論領域・充足関係の標準的な扱い）
よくある質問
述語論理は命題論理と何が違うのか
命題論理は命題を分解しない原子として扱うが、述語論理は命題の内部に立ち入り、対象（変数）と性質・関係（述語）を区別する。さらに全称 $\forall$ と存在 $\exists$ を導入し、「すべての自然数 $n$ について…」のような数学の主張を表現できる。
束縛変数と自由変数の違いは何か
量化子 $\forall x$ や $\exists x$ の作用範囲にある $x$ を束縛変数といい、名前を付け替えても意味は変わらない。どの量化子にも束縛されていない変数を自由変数といい、値を決めないと真偽が定まらない。$\forall x\, P(x,y)$ では $x$ が束縛変数、$y$ が自由変数である。
$\forall$ と $\exists$ の順序を入れ替えてよいか
一般には入れ替えてはならない。$\forall x\,\exists y\,P(x,y)$ は「どの $x$ にもそれに応じた $y$ がある」だが、$\exists y\,\forall x\,P(x,y)$ は「すべての $x$ に共通の $y$ が一つある」で意味が異なる。量化子の順序は主張の強さを左右する。
述語論理は誰が始めたのか
現代の述語論理を事実上創始したのはゴットロープ・フレーゲで、著書『概念記法』（1879）で命題を述語と引数に分解し、量化子 $\forall, \exists$ と束縛変数を初めて体系的に導入した。ほぼ同時期にチャールズ・S・パースが独立に量化の記法を開発し、記号は後にペアノが整備した。一階述語論理を独立した体系として明確に定式化したのはヒルベルトとアッカーマン（1928）である。