読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

ちょっと複雑な論理表現・その2

前回は数学で用いられる論理の基礎を説明しただけで終わってしまいました。今回こそは本題に入ります。

条件付き量化子

最初に言ったように、この話で問題にするのは、

ある実数 x_0 が存在して、すべての x \geq x_0 についてx^2 > x が成り立つ。

のような表現です。量化子に範囲指定や条件がついていることが問題です。ちなみに、この命題は真で、例えば x_0 = 2 とすると、x \geq 2 なる x に関して x^2 > x が成り立つことが分かります。上の命題を論理記号を用いて

\exists x_0 \in \mathcal{R}; \forall x \geq x_0; x^2 > x

のように書くこともあります。ここで、\mathcal{R} は実数の全体です。ここでの問題は、このような範囲指定や条件がついた量化子は、普通の量化子や論理記号だけを用いてどのように書けるかということです。

一般に、変数に条件をつけるものは述語です。述語 P(x) に量化子を適用するとき、変数 x について、述語 C(x) を真にすることを条件として課すことを、

\forall x:C(x); P(x)
\exists x:C(x); P(x)

のように表すことにして、これらを「条件付き量化子」と言うことにします。(この話だけの用語です。)例えば、前者は「すべての x で条件 C(x) を満たすものについて、P(x) が成り立つ」と読みます。

条件付き量化子に課される基本的な要請は、変数 x について C(x) が真のとき、P(x) の真理値をそのまま評価して、C(x) が偽のときは P(x) を評価しないということです。これを満たす演算子としては、「かつ」と「ならば」の2つが考えられます。すなわち、「条件 C(x) を満たすものについて、P(x) が成り立つ」を

C(x) \wedge P(x)
C(x) \Rightarrow P(x)

のどちらかにすればよいのです。

条件付き全称量化子

天下り的に言うと、

\forall x:C(x); P(x)

とは

\forall x; C(x) \Rightarrow P(x)

のことです。

どうして「ならば」を取ったのかというと、C(x) を満たさない x については、\forall x を冠しても真偽に影響しないことを要請するためです。このためには、C(x) を満たさない x については \forall x の適用を受ける述語は常に真となる必要があります。もしそこで偽になってしまうと、\forall x を冠したときに、C(x) を満たす範囲の真偽に拘らず、偽になってしまいます。というわけで、要請を満たす述語として C(x) \Rightarrow P(x) が選ばれたのです。

条件付き存在量化

こちらに関しては、

\exists x:C(x); P(x)

とは

\exists x; C(x) \wedge P(x)

のことです。

「かつ」を取った理由は同様で、C(x) を満たさない x については、\exists x を冠しても真偽に影響しないことを要請するためです。今度は C(x) を満たさない x については、\exists x の適用を受ける述語は偽になる必要があるのです。もしそこで真になってしまうと、\exists x を冠したときに、C(x) を満たす範囲の真偽に拘らず、真になってしまいます。というわけで、要請を満たす述語として C(x) \wedge P(x) が選ばれたのです。

ド・モルガンの法則

今回の問題の動機の一つであった、条件付き量化子を含む命題にも、ド・モルガンの法則が成立するかどうかについて見ます。最初に言っておくと、それは成立します。

まず、

\forall x:C(x); P(x)

の否定を考えます。上よりそれは

\neg (\forall x; C(x) \Rightarrow P(x))

となります。ド・モルガンの法則と「ならば」の否定を用いると、これは

\exists x; C(x) \wedge \neg P(x))

と変形できます。これをよく見ると、

\exists x:C(x); \neg P(x)

に等しいことが分かります。

一方、

\exists x:C(x); P(x)

の否定は上を逆にたどって

\forall x:C(x); \neg P(x)

であることが分かります。

以上をまとめると、

\neg (\forall x:C(x); P(x)) \;\Leftrightarrow\; \exists x:C(x); \neg P(x)
\neg (\exists x:C(x); P(x)) \;\Leftrightarrow\; \forall x:C(x); \neg P(x)

が成り立つということになります。結局は、条件については何も考えずに、ド・モルガンの法則を適用すればよかったのです。

複合的な量化子

数学では、一言で済ませているように見えて、その論理的な内容が少々複雑な表現が用いられることがあります。代表的な例が、n を正の整数(自然数)として、命題の列(述語)(A_n)_n を考えるとき、「十分大きい n について A_n が成り立つ」と「無限個の n について A_n が成り立つ」というものです。これらを詳しく見てみましょう。

「十分大きい~について」

まず、前者の

「十分大きい n について A_n が成り立つ」

が意味するところは、何かしらの n_0 を選べば、それ以上の n ではいつでも A_n が成り立つ、ということです。例えば、

「十分大きい n について n^2 > n が成り立つ」

などです。この場合、n = 1 では n^2 > n は成り立たないのですが、仮に n_0 = 2 をとれば、n \geq n_0 では常に n^2 > n が成り立ちます。この解釈を論理的に書き下すと、「十分大きい n について n^2 > n が成り立つ」は、\mathcal{N} を正の整数の集合として

\exists n_0 \in \mathcal{N}; \forall n \geq n_0; n^2 > n

と書けることが分かります。これを一般化すると、

「十分大きい n について A_n が成り立つ」

\exists n_0 \in \mathcal{N}; \forall n \geq n_0; A_n

と書けるということになります。

「無限個の~について」

一方で、後者の

「無限個の n について A_n が成り立つ」

について詳しく見ると、どのような n_0 をとっても、それ以上の nA_n が成り立つものがある、ということになります。よって、論理的に書き下すと

\forall n_0 \in \mathcal{N}; \exists n \geq n_0; A_n

と書けることが分かります。

では、後者の否定がどのようになるかを見てみましょう。

「無限個の n について A_n が成り立つ」

を言葉の上で否定すると、

A_n が成り立つような n は有限個しかない」

となります。つまり、有限の範囲を超えては○○は成り立たないというわけで、

「十分大きい n について A_n が成り立たない」

となるはずです。これを論理的に書き下すと

\neg (\forall n_0 \in \mathcal{N}; \exists n \geq n_0; A_n)
\Leftrightarrow
\exists n_0 \in \mathcal{N}; \forall n \geq n_0; \neg A_n

となります。これは、前述のド・モルガンの法則に従って否定をとった結果と見事に一致しています。逆に言えば、いちいち考えずともド・モルガンの法則を利用すれば否定をとれるということです。

まとめ

このトピックでは、数学でよく用いられる、ちょっと複雑な論理表現について詳しく見てみました。複雑な論理が絡むときは、それを記号的に操作できると便利なことは少なくありません。今回の話で量化子に条件がついていても問題なくド・モルガンの法則が適用できることが判りました。あとは実際の問題でそれを使いこなせるようになれば、数学の論理に関しては十分です。

次回は情報科学で頻繁に用いられる「オーダー記法」について説明します。そこでは今回の最後で扱った「十分大きな~について」という表現が多用されます。先に進んでから今回の話に戻って頂いても問題ありません。それではまた。