述語論理と量化子
「すべて」と「存在する」を扱う
入門（高校〜大学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)$ は $x$ の値しだいで真にも偽にもなる。
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$ の平方根が存在する
- $\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$ に依ってよい」のはこの順序のためである。
4. 束縛変数と自由変数
量化子 $\forall x$ や $\exists x$ の作用範囲にある変数 $x$ を束縛変数という。束縛変数の名前は他の使われていない文字に付け替えても式の意味は変わらない（$\forall x\, P(x)$ と $\forall z\, P(z)$ は同じ）。
どの量化子にも束縛されていない変数を自由変数という。自由変数は値を決めないと真偽が定まらない。
束縛変数の付け替えが自由にできること（$\alpha$ 変換）は、証明を機械的に扱う際に重要になる。同じ意味の式を同じものと見なす仕組みは、λ計算 でも中心的な役割を果たす。
まとめ
この章のポイント
- 述語論理：命題の内部に踏み込み、対象（変数）と性質・関係（述語）を分ける
- 量化子：$\forall$（すべての）と $\exists$（存在する）で対象全体にわたる主張を表す
- 量化子の順序は意味を変える（$\forall\exists$ と $\exists\forall$ は別物）
- 束縛変数は名前を付け替え可能、自由変数は値しだいで真偽が決まる
よくある質問
述語論理は命題論理と何が違うのか
命題論理は命題を分解しない原子として扱うが、述語論理は命題の内部に立ち入り、対象（変数）と性質・関係（述語）を区別する。さらに全称 $\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）である。