もし任意の宿題を解けたら、成績は \(A\) だ。
3.6 述語論理
目次
3.6.1 量化子
「全ての \(\cdots\) 」を意味する記号 \(\forall\) は本書の冒頭 (第 1.1 節) で初めて登場した。例えば、述語
\[ x^{2} \geq 0 \]
は全ての \(x\) に対して成り立つ。これを言い換えれば、
\[ \forall x \in \mathbb{R}.\ \ x^{2} \geq 0 \]
は真の命題である。一方で、述語
\[ 5x^{2} - 7 = 0 \]
は一部の \(x\) で (具体的には \(x = \pm \sqrt{7/5}\) のとき) 真になる。こういった事実は「 \(\cdots\) が存在する (少なくとも一つのオブジェクトで述語が真になる)」を意味する記号 \(\exists\) を使うと表現できる。つまり命題
\[ \exists x \in \mathbb{R}. \ \ 5x^{2} - 7 = 0 \]
は真であるのに対して、次の命題は偽である:
\[ \forall x \in \mathbb{R}. \ \ 5x^{2} - 7 = 0 \]
文章で「どんなときも正しい」と「一部で正しい」を表現する方法は多くある。そういった表現の例を次に示す。左にあるのは一般的な文章であり、右にあるのが具体的な例である。数学の文章ではこういった表現を何百回も目にすることだろう！
\[ \textbf{どんなときも正しい} \]
\[ \begin{aligned} &\text{全ての \(x \in D\) で \(P(x)\) が真} &&\qquad \text{全ての \(x \in \mathbb{R}\) で \(x^{2} \geq 0\)} \\ &\text{集合 \(D\) の任意の要素 \(x\) で \(P(x)\) が真} &&\qquad \text{任意の \(x \in \mathbb{R}\) で \(x^{2} \geq 0\)} \\ \end{aligned} \]
\[ \textbf{一部で正しい} \]
\[ \begin{aligned} & \text{\(P(x)\) が真となる \(x \in D\) が存在} && \ \text{\(5x^{2}-7=0\) を満たす \(x \in \mathbb{R}\) が存在} \\ & \text{集合 \(D\) のある要素 \(x\) で \(P(x)\) が真} && \ \text{ある \(x \in \mathbb{R}\) で \(5x^{2}-7=0\)} \\ & \text{少なくとも一つの \(x \in D\) で \(P(x)\) が真} && \ \text{少なくとも一つの \(x \in \mathbb{R}\) で \(5x^{2}-7=0\)} \\ \end{aligned} \]
こういった文章で述語は量化 (quantify) されている、と言う。詳しく言うと、述語を全称量化 (universal quantification) すると述語がどんなときでも正しいという表明になり、述語を存在量化 (existential quantification) すると述語が正しくなるオブジェクトが存在するという表明になる。量化を表す記号は量化子 (quantifier) と呼ばれ、\(\forall\) は全称量化子 (universal quantifier)、\(\exists\) は存在量化子 (existential quantifier) と呼ばれる。この二つの量化子と命題論理式を適切に組み合わせた記号列を述語論理式 (predicate formula) と呼ぶ。
普段の文章は量化に関して曖昧な場合がある。例えば次の文章を見てほしい:
\((3.19)\)
この文章に含まれる「任意の」は全称量化とも存在量化とも無理なく解釈できる。つまり「任意の宿題を解けたら」の意味が次の二つのどちらなのかはっきりしない:
宿題を全て解けたら
\((3.20)\)
宿題を少なくとも一つ解けたら
\((3.21)\)
この問題を正確に表現してみよう。宿題全体の集合を \(\operatorname{Probs}\) とする。\(\operatorname{Solves}(x)\) を述語「あなたが宿題 \(x\) を解いた」、\(\text{G}\) を命題「\(A\) の成績を得る」と定める。このとき、文章 \(\text{(3.19)}\) の二つの解釈は次の述語論理式で表せる:
\[ \begin{aligned} \qquad (\forall x \in \operatorname{Probs}. \ \operatorname{Solves}(x)) \ \operatorname{\text{\footnotesize IMPLIES}}\ G &&\quad \href{#eq-3-20}{(3.20)}\ \text{に対応} \\ \qquad (\exists x \in \operatorname{Probs}. \ \operatorname{Solves}(x)) \ \operatorname{\text{\footnotesize IMPLIES}}\ G &&\quad \href{#eq-3-20}{(3.21)}\ \text{に対応} \end{aligned} \]
3.6.2 複数の量化子
数学的命題の多くには複数の量化子が含まれる。例えば、Goldbach の予想 (予想 1.1.6) は次の命題だった:
\(2\) より大きい任意の偶数は二つの素数の和である。
この命題を量化に関して正確に表現すると次のようになる:
\(2\) より任意の偶数 \(n\) に対して、\(n = p + q\) を満たす素数 \(p\), \(q\) が存在する。
\(\text{Evens}\) を \(2\) より大きい偶数全体の集合、\(\text{Primes}\) を素数全体の集合とする。このとき Goldbach の予想は述語論理式を使って次のように表現できる:
\[ \underbrace{\forall n \in \text{Evens},}_{\substack{\footnotesize 2 \text{ より大きい} \\[2pt] \footnotesize \text{任意の偶数 } n \text{ に対して}}} \underbrace{\exists p \in \text{Primes},\ \ \exists q \in \text{Primes}}_{\footnotesize \text{次の条件を満たす素数 } p,\ q \text{ が存在する}}. \ \ n = p + q \]
3.6.3 量化子の順序
異なる種類の量化子 (全称量化子と存在量化子) の順序を入れ替えると、一般に命題の意味は変化する。例として、章の冒頭で示した次の曖昧な文章を考えよう:
アメリカ人はみな夢を持つ。
この文章が曖昧なのは、量化の順序が明確でないためである。\(A\) をアメリカ人全体の集合、\(D\) を夢全体の集合、\(H(a, d)\) を述語「アメリカ人 \(a\) が 夢 \(d\) を持つ」とする。上記の文章の解釈の一つは「全てのアメリカ人は同じ夢を持つ」である。例えば「自分の家を持つ」という夢かもしれない。この解釈は次の述語論理式で表現できる:
\[ \exists d \in D,\ \forall a \in A. \ \ H(a, d) \]
一方で、上記の文章は「全てのアメリカ人はそれぞれが自分の夢を持つ」とも解釈できる。定年退職後の穏やかな暮らしを夢見るアメリカ人もいれば、生きている限り働き続けて技術を磨くことを夢見るアメリカ人も、働く必要がないほどの資産を夢見るアメリカ人もいるのかもしれない。この解釈を表現する述語論理式を次に示す:
\[ \forall x \in A, \ \exists d \in D. \ \ H(a, d) \]
Goldbach の予想で量化子の順序を入れ替えると、「\(2\) より大きい全ての偶数は同じ二素数 \(p\), \(q\) の和である」という明らかに偽の命題が得られる:
\[ \underbrace{\exists p \in \text{Primes},\ \ \exists q \in \text{Primes}}_{\footnotesize \text{次の条件を満たす素数 } p,\ q \text{ が存在する}}, \underbrace{\forall n \in \text{Evens}.}_{\substack{\footnotesize 2 \text{ より大きい} \\[2pt] \footnotesize \text{任意の偶数 } n \text{ に対して}}} \ \ n = p + q \]
3.6.4 量化子の省略
述語論理式に含まれる全ての変数が同じ非空集合 \(D\) の要素なら、\(D\) への言及を省略する慣習がある。例えば \(\forall x \in D,\ \exists y \in D. \ \ Q(x, y)\) は \(\forall x\, \exists y.\ Q(x, y)\) とも書ける。この例で \(x\), \(y\) が属する非空集合 \(D\) を論理式の議論領域 (domain of discourse) と呼ぶ。議論領域は単に領域 (domain) とも呼ばれる。
全ての変数が単一の議論領域に属するように論理式を書き換えることは簡単にできる。例えば Goldbach の予想は議論領域を \(\mathbb{N}\) として次のように書き換えられる:
\[ \forall n. \ n \in \text{Evens} \ \operatorname{\text{\footnotesize IMPLIES}}\ (\exists p\, \exists q.\ p \in \text{Primes} \ \operatorname{\text{\footnotesize AND}} \ q \in \text{Primes} \ \operatorname{\text{\footnotesize AND}} \ n = p + q) \]
3.6.5 量化子の否定
全称量化子と存在量化子の間には単純な関係がある。例えば次の二つの文章は同じことを意味する:
誰もがアイスクリームを好きなわけではない。
アイスクリームが好きでない人がいる。
この事実は、述語論理式に関する次の一般的な同値性の具体例である:
\[ \operatorname{\text{\footnotesize NOT}} (\forall x.\ P(x))\ \ \longleftrightarrow\ \ \exists x.\ \operatorname{\text{\footnotesize NOT}} (P(x)) \tag{3.22}\]
同様に、次の二つの文章も同じことを意味する:
馬鹿にされて喜ぶ人はいない。
誰であっても馬鹿にされれば喜ばない。
この事実を一般化した述語論理式の同値性を次に示す:
\[ \operatorname{\text{\footnotesize NOT}} (\exists x.\ P(x)) \ \ \longleftrightarrow\ \ \forall x.\ \operatorname{\text{\footnotesize NOT}} (P(x)) \tag{3.23}\]
なお、関係 \(\text{(3.23)}\) は関係 \(\text{(3.22)}\) の両辺を否定することでも得られる。
一般的な法則としてまとめれば「\(\operatorname{\text{\footnotesize NOT}}\) を量化子の反対側に移動させると、\(\exists\) は \(\forall\) になり、\(\forall\) は \(\exists\) に変わる」となる。
この二つの関係は量化子に対する De Morgan の法則と呼ばれる。なぜなら、命題論理に対する De Morgan の法則 \(\text{(3.14)}\), \(\text{(3.15)}\) を無限に長い \(\operatorname{\text{\footnotesize AND}}\) および \(\operatorname{\text{\footnotesize OR}}\) に対して適用したものと解釈できるからである。例えば、議論領域を \(\left\{ d_{0}, d_{1}, \ldots, d_{n}, \ldots \right\}\) とするとき、関係 \(\text{(3.22)}\) の右辺 \(\exists x.\ \operatorname{\text{\footnotesize NOT}} (P(x))\) は次の無限に長い \(\operatorname{\text{\footnotesize OR}}\) と同じことを意味する:
\[ \operatorname{\text{\footnotesize NOT}} (P(d_{0})) \ \operatorname{\text{\footnotesize OR}}\ \operatorname{\text{\footnotesize NOT}} (P(d_{1})) \ \operatorname{\text{\footnotesize OR}}\ \cdots \ \operatorname{\text{\footnotesize OR}}\ \operatorname{\text{\footnotesize NOT}} (P(d_{n})) \ \operatorname{\text{\footnotesize OR}}\ \cdots \tag{3.24}\]
De Morgan の法則を適用すれば、これと同値な無限に長い論理式が得られる:
\[ \operatorname{\text{\footnotesize NOT}} (P(d_{0}) \ \operatorname{\text{\footnotesize AND}} \ P(d_{1}) \ \operatorname{\text{\footnotesize AND}} \ \cdots \ \operatorname{\text{\footnotesize AND}} \ P(d_{n}) \ \operatorname{\text{\footnotesize AND}} \ \cdots) \tag{3.25}\]
この無限に長い論理式 \(\text{(3.25)}\) は関係 \(\text{(3.22)}\) の左辺と同じことを意味する:
\[ \operatorname{\text{\footnotesize NOT}} (\forall x.\ P(x)) \]
つまり \(\exists x.\ \operatorname{\text{\footnotesize NOT}} (P(x))\) と \(\operatorname{\text{\footnotesize NOT}} (\forall x.\ P(x))\) は同じ意味を持つ。これで関係 \(\text{(3.22)}\) が成り立つことを確認できた。
3.6.6 述語論理式の恒真性
恒真性の概念は述語論理式にも拡張できる。ただし、述語論理式が恒真となるのは、議論領域がどんな集合であっても、変数が議論領域に属するどんな値を取ったとしても、述語にどんな解釈が与えられたとしても真になるときである。例えば、全称量化子の否定に関する規則を示す関係 \(\text{(3.22)}\) からは、次の述語論理式が恒真だと分かる:
\[ \operatorname{\text{\footnotesize NOT}} (\forall x.\ P(x)) \ \operatorname{\text{\footnotesize IFF}}\ \exists x.\ \operatorname{\text{\footnotesize NOT}} (P(x)) \tag{3.26}\]
有用な恒真述語論理式の例をもう一つ示す:
\[ \exists x\, \forall y.\ P(x, y)\ \ \operatorname{\text{\footnotesize IMPLIES}}\ \ \forall y\, \exists x.\ P(x, y) \tag{3.27}\]
この述語論理式が正しい理由は次の通りである:
\(D\) を変数の議論領域、\(P_{0}\) を \(D\) 上の任意の二項述語1とする。この解釈の下で
\[ \exists x \in D,\ \ \forall y \in D.\ \ P_{0}(x, y) \tag{3.28}\]
が成り立つとき、次の述語論理式が成り立つことを示す:
\[ \forall y \in D,\ \ \exists x \in D.\ \ P_{0}(x, y) \tag{3.29}\]
関係 \(\text{(3.28)}\) が成り立つと仮定する。このとき \(\exists\) の定義から、少なくとも一つの \(d_{0} \in D\) で次が成り立つ:
\[ \forall y \in D.\ P_{0} (d_{0}, y) \]
次は \(\forall\) の定義から、全ての \(d \in D\) で
\[ P_{0} (d_{0}, d) \]
が成り立つ。よって任意の \(d \in D\) に対して、\(P_{0}(x, d)\) が成り立つ \(D\) の要素 \(x = d_{0}\) が存在する。これは述語論理式 \(\text{(3.29)}\) が意味することだから、この解釈の下で \(\text{(3.29)}\) が成り立つことが示せた。
この説明で述語論理式 \(\text{(3.27)}\) の恒真性が納得できたことを願う。ただ、これを「証明」と呼ぶべきではない。 \(\text{(3.27)}\) のような非常に単純な述語論理式であっても、証明で利用できる基礎的な公理が定まっていなければ何も証明できない。上記の説明は述語論理式を普段の言葉に変換し、そこに含まれる「全ての」と「ある要素で」の意味を解釈しただけに過ぎない。
なお、 \(\text{(3.27)}\) に似た次の述語論理式は恒真でない:
\[ \forall y\, \exists x.\ P(x, y)\ \ \operatorname{\text{\footnotesize IMPLIES}}\ \ \exists x\, \forall y.\ P(x, y) \tag{3.30}\]
この事実は \(\forall y\, \exists x.\ P(x, y)\) が真で \(\exists x\, \forall y.\ P(x, y)\) が偽になる解釈を作成すれば証明できる。例えば、議論領域を整数全体の集合、\(P(x, y)\) を \(x > y\) と定める。このとき述語論理式 \(\text{(3.30)}\) の仮定は真になる: \(y\) が整数 \(n\) のとき、\(x\) として \(n + 1\) を取れば \(P(x, y)\) つまり \(n + 1 > n\) が成り立つ。一方で結論は「任意の整数より大きい整数が存在する」と主張しており、明らかに偽である。述語論理式が恒真でないことを示すこういった解釈を反例モデル (counter-model) と呼ぶ。
参考文献
[21]
-
二つの変数の値に依存する述語を二項述語 (binary predicate) と呼ぶ。 ↩︎