集合論(6) 論理学(3)

こんにちは！マシューの数理理論部屋です。
今回は予告通り真偽表を構成したいと思います。
パズルの枠組みとなる部分で、この真偽表をもとにすれば様々な証明がガチャガチャと手を動かすことで示すことができます。前回紹介した対偶や背理法が正しいことも、真偽表を用いて示すことができます。

真偽表とは
実際の真偽表
1. A\(\Rightarrow \)B
2. 仮定が偽なとき
  1. 具体例
  2. 応用例
A\(\Rightarrow \)Bと真偽が同じ命題
A\(\Rightarrow \)Bの証明方法
まとめ

真偽表とは

真偽表についてまずざっと説明します。
まず、命題を入力されることで命題となるようなものを考えます。(例えば\(A\Rightarrow B\)を考えると、\(A\)や\(B\)自体が命題となるときです)

この大きな命題の真偽は入力した命題(何個でももちろん可能)の真偽によって決まります。例えば、\(A\)と\(B\)がともに真であるとき、\(A\Rightarrow B\)も真となることはわかりやすいと思います。
では、\(A\)が偽であるときや\(B\)が偽であるときは真でしょうか？それとも偽でしょうか？
このようなものを場合ごとにわけてまとめたものが真偽表となります。

実際の真偽表

真偽表は大きな命題の形ごとに作る必要がありますが、今回は最も基本的な3つの命題を紹介します。

A	B	A\(\lor \)B	A\(\land \)B	A\(\Rightarrow \)B
真	真	真	真	真
真	偽	真	偽	偽
偽	真	真	偽	真
偽	偽	偽	偽	真

真偽表(の例)。AとBの真偽の場合について4つの行ができる。

A\(\lor \)BとA\(\land \)Bの詳しい説明は省略したいと思います。
A\(\lor \)Bは片方でも真なら真、A\(\land \)Bは両方が真でないと真にならないということを考えると良いです。

A\(\Rightarrow \)B

では、A\(\Rightarrow \)Bの説明に入ります。

まず、上記のようにAとBが真のとき、A\(\Rightarrow \)Bも真であることは省略します。簡単に言えば、正しいことを仮定して、正しい推論をすれば正しい結果が得られるということです。

またAが真であるのにBが偽であるとき、推論自体が偽であることも詳しい説明は省略します。仮定が正しいのに結論が間違えているとき、それは推論が間違っています。

仮定が偽なとき

残りはAが偽であるときです。真偽表を見てみると、Bの真偽に関係なくA\(\Rightarrow \)Bは真となっています。
以下では仮定が偽であるとき、全体の推論自体は結果に関係なく真であるとはどういうことでしょうか。

これはA\(\Rightarrow \)Bが主張していることを考えることで答えを得ることができます。A\(\Rightarrow \)Bは「Aが真ならばBも真」ということを主張しています。
ですので、Aが偽であるときに関してはなんの主張もしていません。

なので、A\(\Rightarrow \)BだけならAが偽であるとき、Bは真とも偽ともなりうるということです。

具体例

このことに関しては具体例を見てみることで納得しやすいので具体例を見ていきます。

まず、0=1を仮定します(勿論これは偽な命題です)。ここに2種類の手を加えます。

1つ目は両辺を10倍します。両辺に同じ数をかけたので推論としては正しいですが、結果は0=10となり、偽となります。
2つ目は右辺と左辺をかえて足し合わせます。右辺は1+0=1、左辺は0+1=1となるので結果は1=1となり、真となります。ここでも推論自体は同じ数を足したので正しい推論です。

応用例

ではこの”仮定が偽”という状況を考えることはあるのでしょうか？
仮定が偽のとき、結論に限らず正しい推論であるからといって実際に命題は有効なものとなるのでしょうか。
では、応用例のうちの一つを見ていきます。

\(\emptyset \subset X\)・・・(1)

高校数学の時に(詳しい説明はなかったと思いますが)空集合は全ての集合の部分集合であることを聞いたことがある人もいるかもしれません。これは、仮定が偽であることから得られる事実です。
まず、部分集合の定義は以下で書けます。

[\(Y\subset X\)]\(\overset{def}{\Leftrightarrow} [(^{\forall} z \in Y)\Rightarrow (z\in X)]\)

Yが空集合の時、この定義の右辺の(\(^{\forall} z\in Y\))が偽となりますので、右辺全体が正しいことが分かります。
右辺が満たされれば左辺が言えます。ここでXの条件はとくに課してないので空集合は任意の集合の部分集合ということができます。

A\(\Rightarrow \)Bと真偽が同じ命題

最後に、真偽表を使ってA\(\Rightarrow \)Bと真偽が同じ命題を探してみましょう。つまり、Aが偽なときとAとBが真のときは真となり、Aが真でBが偽のときは偽となるような命題です。

答えは\(\lnot A \lor B\)です。

では実際に真偽表で確かめてみましょう。上で記載した真偽表を少しいじります。Aと\(\lnot \)Aは真偽が反対であることを使って下のようになります。

A	B	\(\lnot A\)	A\(\Rightarrow \)B	\(\lnot A \lor B\)
真	真	偽	真	真
真	偽	偽	偽	偽
偽	真	真	真	真
偽	偽	真	真	真

これでA\(\Rightarrow \)Bと\(\lnot A \lor B\)の真偽が一致することが示せました。

A\(\Rightarrow \)Bの証明方法

ここでA\(\Rightarrow \)Bを証明するために何をすればいいかを論じて今回は終わりたいと思います。
まず、Aが偽ならA\(\Rightarrow \)Bは真です。これは推論の方法や結果に関係なく真なので、証明する必要はありません。
次にAが真であるときを考えます。このとき、A\(\Rightarrow \)Bが真となるためにはBも真である必要があるので、Ａが真であると仮定してＢも真であると示せば良いわけです。

逆に反証する必要がある(つまりA\(\Rightarrow \)Bが偽であることを示す)ならば、Aが偽であることを仮定してもA\(\Rightarrow \)Bは常に真なので反証できません。なのでここでもAが真であることを仮定したうえでBは偽となることを示せば良いです。

これは\(\lnot A \lor B\)の証明方法と同じであることが分かるかと思います。基本的にX\(\lor \)Yという命題を証明するには、片方が偽であるとき、もう片方が真となることを示すのですが、ここでXを\(\lnot \)A、ＹをＢして考えます。
するとＸでないことは\(\lnot (\lnot A)\)が真であることを仮定することなり、結局Ａが真であることを仮定してY、つまりBも真となることをしめせばいいです。

まとめ

今回は真偽表について簡単な説明を載せました。
この真偽表から始まって論理学は色々と枝を伸ばすことができます。
今回で論理学はひとまず終わりにして、次回は関数をより広げた概念である写像について紹介したいと思います。
最後までお付き合いいただきありがとうございました。これからもマシューの数理理論部屋をよろしくお願いします。