今、シリーズでオートマトンと言語に関する話を書いている。
初回は以下だ。
さて、前回から必要な知識の補足を書いている。
前回は、集合とは何ぞやというところを解説した。
本当に基礎の部分しか解説していないが、一旦集合が何者かは理解できたと思う。
以下がその記事だ。
さて、今回はまた別の話。
今回は、命題と論理というやつを解説しよう。
前回のラストにも書いた通り、これは証明に深く関わってくる話だ。
…最初、ここをすっ飛ばそうと思ったのだが、やはり解説しておいた方が色々と都合がいい。
随時具体例も混ぜながら説明していくので、落ち着いてついてきて欲しい。
なお、前回に引き続き、以下の本を参考に書いている…が、今回はちょっと順番がめちゃくちゃだったり省略したりもしている。
今回の内容に関しては、各用語を参照する感じで見てもらえればと思う。
命題
早速、本編に入っていこう。
命題とは、誰が見てもそれが正しい(真)か間違っている(偽)かがどちらか一方で一致するような主張のことだ。
幾つか、具体例を見てみよう。
- 1 + 2は3に等しい
- この記事は日本語で書かれている
- \(x^2 – 2x + 1 = 0\)のとき、\(x = 1\)である
これらは、全て真の命題だ。
それに対し、以下の三つは偽の命題になる。
- 2 + 3は4に等しい
- この記事は英語で書かれている
- \(x^2 + 2x + 1 = 0\)のとき、\(x = 1\)である
このように、言っている内容が明らかに間違っていても、命題ではあるので気を付けよう。
命題でないのは、以下のような例だ。
- この宇宙には、地球外生命体が存在する
- 10と11は似ている
一つ目、地球外生命体はいるかどうかは分かっていないので、どちらに決定することもできない。
また、二つ目は似ていることの捉え方が人によって異なるので、これまた正しいかどうかが人によって分かれてしまう。
ただ、もし「差が1未満の二つの数を似ていると定義する」と書かれていれば、この二つ目は偽の命題になる。
とにかく、誰が見ても真か偽かがブレずに決定できれば、それは命題だという認識でいいだろう。
複合命題
さて、命題はただ一つだけではなく、複数組み合わせて使うことが多い。
その全般を複合命題と呼び、これ全体も一つの命題として使うことができる。
ここから、代表的な複合命題を紹介していこう。
なお、大事なのはそういう命題の種類があるという部分で、名前も紹介するがそこまで覚える必要はない。
連言
二つの命題がともに真である場合にのみ全体を真とする複合命題を、連言と呼ぶ。
例えば、「自然数\(a, b\)はともに奇数である」を命題\(A\)としたとき、以下二つの連言と捉えることができる。
- 命題\(A_1\)：自然数\(a\)は奇数である
- 命題\(A_2\)：自然数\(b\)は奇数である
このとき、\(A_1, A_2\)それぞれの真偽と、\(A\)の真偽の関係は以下の表の通りだ。
| \(A_1\) | \(A_2\) | \(A\) |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 偽 |
| 偽 | 偽 | 偽 |
日本語では、「かつ」という文言で結ばれることが多い。
また、数式ではよくコンマで省略されるので、覚えておこう。
選言
今度は、二つの命題のうち最低でもいずれかが真である場合に全体を真とする複合命題で、これを選言と呼ぶ。
上の例の命題\(A_1\)、\(A_2\)の選言を書くと、「自然数\(a, b\)の少なくとも一方は奇数である」となり、真偽の関係は以下の通り。
| \(A_1\) | \(A_2\) | \(A\) |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 真 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 偽 |
こちらは、日本語では「または」に該当し、略されることは基本的にない。
条件付き命題
これは前提となる命題があり、その上で結論について言及する複合命題。
先に日本語の例を出すと、「○○ならば△△である」といった形になる。
この○○の部分が前提や条件、△△が結論だ。
この真偽の関係は少しややこしく、前提が真かつ結論が偽の時に限って全体が偽になり、それ以外のパターンは真となる。
命題\(A\)「命題\(A_1\)ならば命題\(A_2\)である」の真偽の関係は以下の通りだ。
| \(A_1\) | \(A_2\) | \(A\) |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 真 |
これは具体例をちょっと丁寧に見ていこう。
今、命題\(A_1, A_2\)がそれぞれ以下のようになっていたとする。
- 命題\(A_1\)：テストの点数が70点以上である
- 命題\(A_2\)：合格である
このときの命題\(A\)は、「テストの点数が70点以上であれば、合格である」となる。
では、実際のパターンでこれ全体の真偽がどうなっているか確認してみよう。
まず、両方真…例えば、テストが80点で合格したとしよう。
このとき、命題\(A\)の内容に沿っているので真で問題ない。
次に、\(A_1\)が真、\(A_2\)が偽のパターン、テストが80点だったのに不合格の場合。
これは、命題\(A\)が嘘を言っていることになるので、偽だ。
ここまではいいが、問題はここからだ。
テストが60点だったのに合格だった場合、命題\(A_1\)が偽、命題\(A_2\)が真のパターンだ。
これ、注意深く見ると、命題\(A\)は何も嘘は言っていないことが分かるだろうか。
命題\(A\)は、あくまで70点以上なら、という条件で話しているので、70点に届かなかった場合のことは何も言っていないのだ。
よって、この場合の命題\(A\)は真であると言える。
最後、テストが60点で不合格の場合。
これも一つ上と同じく、70点に届かなかった場合なので、命題\(A\)では触れられていない。
よって、命題\(A\)は真で問題ない。
さて、ここまで解説してきたが、この条件付き命題には記号が存在する。
命題\(A_1\)ならば命題\(A_2\)であるというとき、以下のように前提から結論へ、二重線の矢印で結ぶ。
$$A_1 \Rightarrow A_2$$
もちろん、この\(A_1\)、\(A_2\)自体に連言や選言、もしくはこの条件付き命題自身も入ることができるので、覚えておこう。
ちなみに、この命題は書き換えが可能だ。
真偽関係の表を再掲してみよう。
| \(A_1\) | \(A_2\) | \(A\) |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 真 |
さて、命題\(A\)が真となるパターンは、\(A_1\)が偽、あるいは\(A_2\)が真となるとき、というように読み替えることができる。
つまり、後で解説する否定と上で解説した選言を組み合わせて、「\(A_1\)でない、または\(A_2\)である」と書き換えることができるのだ。
上のテストの例でやってみると、「テストの結果が70点未満、または合格である」となる。
これでも、上の4パターンで同じ結果になることを確認してみてほしい。
排他的選言
二つの命題の真偽が異なる時に限り全体が真となる複合命題のことを、排他的選言という。
これは日常の例を出した方が分かりやすい。
カレー屋で、「ライスかナンかを選べる」とき、どちらか一方は必ず頼むが、両方頼めることはない。
このような関係が、排他的選言だ。
日本語だと、「命題\(A_1\)、命題\(A_2\)のどちらか一方のみが成り立つ」といった感じだろうか。
真偽の関係は以下の通り。
| \(A_1\) | \(A_2\) | \(A\) |
|---|---|---|
| 真 | 真 | 偽 |
| 真 | 偽 | 真 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 偽 |
あくまで私の感覚だが、これが出てくることは少ないように思える。
同値関係
排他的選言と比べ、こちらは非常によく出てくる。
二つの命題\(A_1\)、\(A_2\)の真偽が一致しているときに限り、全体を真とするのがこの同値関係だ。
真偽の関係は以下の通り。
| \(A_1\) | \(A_2\) | \(A\) |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 偽 | 偽 |
| 偽 | 真 | 偽 |
| 偽 | 偽 | 真 |
これも具体例を見てみよう。
- 命題\(A_1\)：\(n, m\)はともに奇数である
- 命題\(A_2\)：\(n \times m\)が奇数である
日本語で命題\(A\)を書くと、そのまま「\(n, m\)が奇数であることと、\(n \times m\)が奇数であることは同値である」というような感じ。
この同値関係にも記号が用意されていて、条件付き命題の矢印を両向きにしたものを使う。
$$A_1 \Leftrightarrow A_2$$
また、この同値関係は、「(\(A_1\)ならば\(A_2\)である)かつ(\(A_2\)ならば\(A_1\)である)」と書き直すこともできる。
こう直せる理由は、以下の真偽関係を見てもらえれば分かると思う。
| \(A_1\) | \(A_2\) | \(A_1\)ならば\(A_2\) | \(A_2\)ならば\(A_1\) | \(A_1, A_2\)が同値 |
|---|---|---|---|---|
| 真 | 真 | 真 | 真 | 真 |
| 真 | 偽 | 偽 | 真 | 偽 |
| 偽 | 真 | 真 | 偽 | 偽 |
| 偽 | 偽 | 真 | 真 | 真 |
証明の際には、基本的にこの形に直し、この両方を示すことが多い。
全称命題と存在命題
次に、これらを紹介しよう。
これらは、条件付き命題の一種だ。
全称命題
条件付き命題「\(A_1\)ならば\(A_2\)である」の前提\(A_1\)について、範囲を指定していて、その範囲全てについて言及する内容であるとき、この全体を全称命題と呼ぶ。
例を挙げると、「全ての自然数\(a, b\)について、\(a + b\)は自然数である」という感じ。
ちなみに、この命題は真だ。
この全称命題は、その範囲で一つでも成り立たない例があったときに偽となり、その成り立たない例のことを反例と呼ぶ。
反例が存在する…つまり、偽の全称命題の例を挙げると、「全ての自然数\(a, b\)について、\(a – b\)は自然数である」がそうだ。
この反例は、\(a = 1, b = 2\)など。
存在命題
条件付き命題「\(A_1\)ならば\(A_2\)である」の前提\(A_1\)について、範囲を指定していて、その範囲内に一つ以上\(A_2\)が真となるようなパターンが存在する、という命題を存在命題と呼ぶ。
こちらも例を挙げると、「ある自然数\(a, b\)について、\(a – b\)は自然数である」とか、「\(a- b\)が自然数であるような自然数\(a, b\)が存在する」とか。
これは一つでも結論が成り立つようなパターンが存在すれば真で、今書いた例だと\(a = 2, b = 1\)としてあげれば真であることが分かる。
こちらは、一つも成り立つ例が無ければ、ようやく偽となる。
例えば、「\(\sqrt{n}\)が実数であるような0未満の整数\(n\)が存在する」は偽だ。
ちょっとオマケで、特殊な存在命題についても触れておこう。
通常の存在命題は、一つ以上存在すれば、いくつ存在しようと真になっている。
それに対し、ただ一つだけ存在するときに限り真であるような存在命題もある。
例としては、「\(p\)を素数とすると、\(p\)を割った商が自然数であるような2以上の自然数\(n\)がただ一つ存在する」だろうか。
これは\(p = n\)の時に限り商が1で自然数になるので、真だ。
このパターンは本編にも出てきており、写像であることを示す部分で使っている。
次回詳しく書くが、実際に証明する際の手順としては、存在することと、それがただ一つであることの二つに分けることが多い。
命題の否定
ある命題の真偽を反転させた命題を、元の命題の否定と呼ぶ。
例えば、「1+2と3は等しい」の否定は、「1+2と3は異なる」だ。
また、「「命題の否定」の否定」は、元の命題と一致する。
表裏があるコインを二回ひっくり返すこととやっていることは同じなので、問題ないと思う。
…さて、この否定は複合命題だと色々とややこしいことになるので、丁寧に見ていこう。
連言、選言の否定
連言「\(A_1\)かつ\(A_2\)である」の否定は、「\(A_1\)でない、または\(A_2\)でない」というように、選言になる。
同じく、選言「\(A_1\)または\(A_2\)である」の否定は、「\(A_1\)でない、かつ\(A_2\)でない」で、今度は連言だ。
上の真偽関係の表と見比べてみれば、こうなることは問題ないと思う。
条件付き命題の否定
要注意ポイントの一つ目がここ。
条件付き命題を否定しようとすると、そのままの形だと上手くいかない。
なぜなら、「～ならば」の形にした時点で、4パターンのうち3つが真で確定してしまうからだ。
真偽を入れ替えると、真が1パターン、偽が3パターン欲しいので、そのままでは無理だ。
ということで、書き換えた「\(A_1\)でない、または\(A_2\)である」の方を使う。
これは選言の否定なので、「\(A_1\)、かつ\(A_2\)でない」という連言に書き換えれる。
これが元の否定になっていることは、真偽関係の表で確認してほしい。
全称命題、存在命題の否定
ここも要注意ポイント、上の条件付き命題の否定よりも重要だ。
さきほど、全称命題は反例が存在した時に偽となる、ということを書いたと思う。
で、否定は真偽を入れ替えた命題だとも書いた。
つまり、全称命題の否定は、その反例が存在する、という存在命題になる。
例を挙げると、「全ての自然数\(n, m\)について、\(n – m\)は自然数である」の否定は、「\(n – m\)が自然数でないような自然数\(n, m\)が存在する」だ。
…これまでのパターンから、次にやることはもうなんとなく想像付くと思う。
存在命題の否定は、注目する範囲全てで、結論が成り立たないという全称命題になるのだ。
これも上で出した偽の存在命題の例「\(\sqrt{n}\)が実数であるような0未満の整数\(n\)が存在する」を否定してみよう。
すると、「全ての0未満の整数\(n\)に対し、\(\sqrt{n}\)は実数ではない(=虚数である)」となる。
実際、上の条件で\(\sqrt{n} = \sqrt{-|n|} = i\sqrt{|n|}\)なので成立だ。
この全称命題、存在命題の否定も証明手法によってはよく使うものの一つなので、是非覚えておいて欲しい。
排他的選言、同値の否定
これらは単純で、一方が他方の否定の関係になっている。
真理値表からも明らかだろう。
…とはいえ、メインで解説したい証明ではほとんど使うことはないので、軽い紹介くらいに留めよう。
条件付き命題の逆、裏、対偶
条件付き命題について、証明時にその対偶を示すといった手法を取る場合がある。
で、その対偶を説明するために、逆と裏も必要だ。
ということで、それらを解説していこう。
大元となる命題\(A\)を、「\(A_1\)ならば\(A_2\)である」としておく。
逆
逆は、そのままの意味で前提と結論を入れ替えたような命題だ。
「\(A_2\)ならば\(A_1\)である」というのが、元の命題\(A\)の逆になる。
このときの注意が、元の命題が真であっても、その逆が真であるとは限らないということ。
例えば、「\(a, b\)が自然数なら、\(a + b\)は自然数である」は成り立つが、その逆「\(a + b\)が自然数なら、\(a, b\)は自然数である」は成り立たない。
反例は、\(a = -1, b = 2\)や、\(a = 0.5, b = 1.5\)などなど。
裏
裏は、前提と結論の両方を否定したような命題のこと。
「\(A_1\)でないならば\(A_2\)ではない」が、元の命題\(A\)の裏だ。
これも逆と同じく、元が真だろうと裏も真であるとは限らない。
上と同じ例「\(a, b\)が自然数なら、\(a + b\)は自然数である」を裏にすると、今度は「\(a, b\)の少なくとも一方が自然数でないなら、\(a + b\)は自然数でない」になる。
これは、\(a = -1, b = 2\)とすれば、\(a + b = 1\)で自然数になるので、裏は真ではない。
…と書いてきたが、元の命題の逆と裏は必ず真偽が一致する。
その理由は、次の対偶で説明しよう。
対偶
対偶とは、元の命題の逆の裏、あるいは裏の逆であるような命題のこと。
あるいは、と書いたが、結局どちらも同じ形になる。
「\(A_2\)でないならば\(A_1\)でない」が、対偶の形だ。
これは、元の命題と必ず真偽が一致する。
また同じ具体例「\(a, b\)が自然数なら、\(a + b\)は自然数である」でやってみると、この対偶は「\(a + b\)が自然数でないなら、\(a, b\)の少なくとも一方は自然数でない」となる。
やってみてもらえば分かると思うが、これはどんなパターンでも成り立つので真だ。
ちなみに、ある命題の逆と、同じ命題の裏は真偽が一致すると上で書いた。
その理由は、これらも対偶の関係にあるからだ。
二つを並べて書いてみよう。
- 逆：\(A_2\)ならば\(A_1\)である
- 裏：\(A_1\)でないならば\(A_2\)でない
こうすれば、これらも対偶の関係にあることが分かると思う。
おわりに
今回は、命題と論理に焦点を当てて解説を行った。
…参考書には他にも述語や必要条件、十分条件なども載っているが、今回は証明を解説するための準備であり、これらは直接証明には使わないだろう。
このあたりは興味があれば調べてみて欲しい。
さて、次回は今回の内容を使って、証明を解説していく。
具体的な手法であったり、本編でさらっと使っていた内容も解説するつもりなので、よかったら見てみて欲しい。
2020/12/23追記
次回の証明を投稿した…が、言葉で説明するのに苦労してしまい、結局やり方の流れを説明する感じになってしまった。
大雑把にどんなものかは捉えられると思うので、適宜必要な情報を調べながら読み進めていただきたい。
コメント