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

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

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

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

今回は、数学の書き方についての話です。主にターゲットとするのは、数学でよく用いられる

ある実数 x_0 が存在して、すべての x \geq x_0 に対して、○○が成り立つ

のような表現です。この「ある『実数』 x_0 が存在して」や「すべての x\geq x_0』 に対して」 のような変数に範囲指定や条件をつける書き方は、数学ではよく用いられるのにも拘らず、教科書で説明されているのを筆者は見たことがないのです。特に後者については、前者の変数を条件に含んでいるところが問題です。これでは、例えば背理法の証明のために否定をとるとき、

ある実数 x_0 が存在して、すべての x \geq x_0 に対して○○が成り立つ

を後述のド・モルガンの法則に従って

すべての実数 x_0 に対して、ある x \geq x_0 が存在して、○○が成り立たない

としてよいものか悩ましいということが起こります。

今回の話では、上のような論理表現を適切に書き換えることによって、上記の問題が解決できることを見ます。

このようなことは教科書でも取り上げられることはなく、おそらくは気にも止められない(ぶっちゃけ面白くもない)ようなことなのですが、筆者としては悩ましいと思った経験があるので、あえてここで取り上げることにしました。後に、情報科学でよく用いられるオーダー記法の定義を与える上で避けては通れないところでもあるので、話の流れ上必要だったという理由もあります。まぁ、つまらない話でしょうが、できれば基礎と思って目を通して頂きたいです。

論理の基礎

最初に論理の基礎的な部分についてざっくり説明します。ここでいう論理とは、「古典一階述語論理」と呼ばれるものです。大雑把に言えば、真と偽の二択だけですべてを割り切る論理を「古典論理」と言います。数学で用いられる論理はほとんどこれで足ります。

命題と述語

「命題」とは、真もしくは偽であることが揺るぎなく定まる文のことです。例えば、(自然数の中で)「2は1より大きい」は真なる命題であり、「2は3より大きい」は偽なる命題です。論理で扱う範囲を広げれば、「他人のものを勝手に取ると泥棒になる」というのも、法律に照らせば真なる命題と考えることができるでしょう。一方で、「嘘つきは泥棒の始まり」というのは、嘘つきでない人間がいきなり他人の物を盗むということがあり得るので、真とも偽ともつかず、従って命題ではありません。ところで、物事の真偽は前提次第で変わるので、何が命題であるかも前提に依存することには注意してください。ただし、これ以後の話では、何が命題であるかという問題は考慮せず、命題と考えられるものだけを扱います。

他方の「述語」とは、命題に変数が入ったもののことです。言い換えると、変数の値を一つ決めれば真偽が確定しますが、変数の値によって真偽が変わり得るというものです。例えば、実数の変数 x に対して、x \geq 0 は述語です。これは、x = 1 のときは真ですが、x = -1 のときは偽です。しかし、変数 x に何の制約もつかない場合は、真とも偽とも言えません。すなわち、述語それ自体は一般に命題ではありません。

命題はその内容に目をつぶれば、真偽のどちらかの値をとる文字と見なすことができます。以下では、命題は A, B, C, \dots のように英字の大文字で表すことにします。ここだけの記法として、命題 A が真であることを A = \mathrm{T} で、偽であることを A = \mathrm{F} で表すことにします。命題の真偽を表す値 \mathrm{T}, \mathrm{F} を「真理値」と言います。

同様に、述語は変数の値によって真偽のどちらかの値をとる関数と見なすことができます。以下では、述語は関数と同様に P(x), Q(x, y), \dots などと表すことにします。ここで、大文字は述語を表し、括弧内の小文字は述語の変数を表します。命題と同様に、真理値を \mathrm{T}, \mathrm{F} で表すことにします。

論理演算子

まずは、論理で用いられる基本的な演算子について説明します。これらは、命題(もしくは述語)を真理値が入る文字(もしくは関数)として見た場合の代数的な演算と見ることもできます。

基本的な演算子

数学の論理で一般的に用いられる演算子は次の4つです。

  • 否定:「~でない」

命題 A に対して、命題「A でない」は A の真偽を逆転させたものです。論理記号による表現は

\neg A

です。古典論理では否定の否定は元に戻ります。論理式で書くと

\neg(\neg A) = A

となります。ここでもこの先でも古典論理以外を扱うことはないと思われるので、原則としてこの置き換えは常に可能であるとします。

命題 A と命題 B に対して、命題 「A かつ B」 は、AB の両方が真であるときに真となり、それ以外では偽となる命題です。論理記号による表現は

A \wedge B

です。

命題 A と命題 B に対して、命題 「A かつ B」 は、AB の少なくとも一方が真であるときに真となり、それ以外では偽となる命題です。注意すべきは、日常的に用いられる「または」とは違って、一方のみを選択する意味はないということです。論理記号による表現は

A \vee B

です。

  • 含意:「~ならば…」

命題 A と命題 B に対して、命題 「A ならば B」 は、A が真のとき、B の真偽をそのまま真理値として持つ命題です。一方、A が偽のときは、B の真偽に拘らず真となります。論理記号による表現は

A \Rightarrow B

です。

注意すべきは、A が偽のときは常に真となるという、一見すると奇妙に思われるルールです。これは実は、ここで扱っているような二値(古典)論理において最も重要なポイントです。ただ直感的には理解しにくいと思われるので、後で真理値表を出して検証します。とにもかくにも、「A が偽ならば A \Rightarrow B は真」ということを頭にとどめておいてください。

真理値表

以上の演算子を並べると

否定:「A でない」=\neg A
論理積:「A かつ B」=A \wedge B
論理和:「A または B」=A \vee B
含意:「A ならば B」=A \Rightarrow B

です。演算子の結合順序は、上から順に強いとします。例えば、

A \Rightarrow B \vee C \wedge \neg D

A \Rightarrow (B \vee (C \wedge (\neg D)))

と同値です。

以上の演算子に対して、命題 A および B を真理値の変数と見なして、演算の結果の真理値を表にしたものを「真理値表」と言います。一般の論理関数(真理値をとって真理値を返す関数)については、変数の真理値の組に対する関数の値を並べたものを真理値表と言います。以上の4つの演算に対する真理値表は次のようになります。

f:id:azapen6:20130127090518j:plain

ド・モルガンの法則

上の3つの演算に成り立つ関係として、「ド・モルガンの法則」というものがあります。これは、複雑な論理式の否定を記号的に計算するときによく用いられます。「A または B」は、AB の両方が偽のときに限って偽となります。そこで、否定をとって真偽を逆転させると、同値関係

\neg (A \vee B) \;\Leftrightarrow\; \neg A \wedge \neg B

が成り立ちます。ここで、さらに全体の否定をとって

\neg( \neg A \wedge \neg B) \;\Leftrightarrow\; A \vee B

として、A \to \neg AB \to \neg B と置き換えると、

\neg (A \wedge B) \;\Leftrightarrow\; \neg A \vee \neg B

が得られます。これら2つの同値関係

\neg (A \vee B) \;\Leftrightarrow\; \neg A \wedge \neg B
\neg (A \wedge B) \;\Leftrightarrow\; \neg A \vee \neg B

をド・モルガンの法則と言います。

必要なのは3つだけ

少し考えると、「~でない」「かつ」「ならば」の3つだけを用いた論理式ですべての論理関数を表現できることが分かります。まず、関数の真理値表で真の部分を抜き出します。次に、そのときの命題のうちの A が真ならば A、偽ならば \neg A と置いて、すべての変数についてそれらを \wedge で結んだものを一つの項とします。そのようにして作られた項をすべて \vee で結べば、その関数と同値な論理式が得られます。もしくは、真偽を逆転させて同値な論理式を作り、それの否定をとるという方法もあります。このようにして作られる論理式は多くの場合冗長になりますが、ともかく3つだけですべてを表せることは分かりました。*1

例として4つ目の A \Rightarrow B をとると、これは A = \mathrm{T} かつ B = \mathrm{F} のときだけ偽となるので、最初に否定をとると

\neg (A \Rightarrow B) \;\Leftrightarrow\; A \wedge \neg B

となります。(この同値関係自体も重要です!)これの否定をとれば、

A \Rightarrow B \;\Leftrightarrow\; \neg (A \wedge \neg B) \;\Leftrightarrow\; \neg A \vee B

となります。最後の同値関係はド・モルガンの法則を用いました。

以上の論理演算子は、そのまま述語に対しても用いることができます。述語に論理演算を適用したものは再び述語になります。

量化子

述語が入る論理で用いられるものに、「量化子(quantifier)」というものがあります。述語は変数の値によって真偽が変わるので、それらの真偽を確定するためには、変数の全体を見て、何らかのルールに従って真偽を決めてやる必要があります。そのルールを指定するのが量化子です。

基本的な量化子

数学で一般的に用いられる量化子は次の2つです。

  • 全称:「すべての~について…」

述語 P(x) に対して、変数 x が可能な範囲を動くとき、「すべての x について P(x) が成り立つ」とは、すべての x の値に対して P(x) が真のときに真となり、それ以外では偽となる命題です。論理記号による表現は、

\forall x \; P(x)

です。

  • 存在:「ある~が存在して…」

述語 P(x) に対して、変数 x が可能な範囲を動くとき、「ある x が存在して P(x) が成り立つ」とは、少なくとも一つの x の値に対して P(x) が真のときに真となり、それ以外では偽となる命題です。論理記号による表現は、

\exists x \; P(x)

です。

2変数以上の場合は、複数の量化子を組み合わせることが可能です。例えば、

\forall x \; \forall y \; P(x, y)
\forall x \; \exists y \; P(x, y)

などです。同じ量化子同士の順序は交換できます。

一方で、異なる量化子の順序は一般に交換できません。例えば、あるクラスの人々について、「○○さんは××さんに嫌われている」という述語を考えるます。すると、「すべての人(○○さん)について、ある人(××さん)が存在して、○○さんは××さんに嫌われている」とした場合、これは「どの人も必ず誰か一人以上からは嫌われている」ということです。一方で、「ある人(○○さん)が存在して、すべての人(××さん)について、○○さんは××さんに嫌われている」とした場合、これは「クラス全員から嫌われている人が存在する」ということです。前者の場合、全員が概ね別の人に嫌われていて、全員から嫌われている人はいないということがあるので、後者とは論理的に関係ありません。同様に、後者の場合、一人だけが全員から嫌われていて、他の人の間は特に険悪ではないという場合があり得ます。

演算子との関係

量化子は命題論理における関係演算子に相当するものです。例えば、

1 \geq 00 \geq 0-1 \geq 0

という3つの命題に対して、

[1 \geq 0] \;\wedge\; [0 \geq 0] \;\wedge\; [-1 \geq 0]

という命題や、

[1 \geq 0] \;\vee\; [0 \geq 0] \;\vee\; [-1 \geq 0]

という命題を作ることができます。真偽は明らかに前者が偽で後者が真です。ここで、共通の部分を取り出して x \geq 0 と書き、変数 x の範囲を -1,0,1 とすると、前者は

\forall x \;[ x \geq 0 ]

と書けることが判ります。また、後者は

\exists x \; [ x \geq 0 ]

と書けます。このように、変数が有限個の値しか取らない場合は、量化子「すべての」は演算子「かつ」に、量化子「ある」は演算子「または」に一致します。

ド・モルガンの法則

ここで、再びド・モルガンの法則が登場します。上の例と以前のド・モルガンの法則を組み合わせれば

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

が成り立つことが解るでしょう。これを一般に拡張して、変数が有限個の値をとる場合に限らず上の2つの同値関係が成り立つとしたものが、述語論理におけるド・モルガンの法則です。

今回はここまで

論理の基礎を説明してたら分量が多くなってしまいました。本題は次に回します。次回は以上の話を踏まえて、最初の問題を解決します。また、数学でよく使われる論理的に複雑な表現についても紹介します。

*1:ここでは扱いませんでしたが、演算子によっては、1つだけですべての論理関数を表現することも可能です。