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

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

仮定が偽なら結論は何でもあり

前回の補遺として、演算子「ならば」のところで述べた、A \Rightarrow BA が偽のときには B の真偽に拘らず真となる、という真理値割り当てを検証します。これは二値(古典)論理において重要なポイントなのですが、どうにも直感では理解が難しい部分でもあると思われます。そこで今回の話は、「ならば」の真理値割り当てを、基本的な論法から真理値表を用いて導出を試みます。

「ならば」の真理値を考えるためには、まず「ならば」の意味を考える必要があります。「AならばB」とはどういう意味でしょうか?あまりに基本的なことなのでむしろ答えるのが難しいかもしれません。少し冗長な言い方をすれば、「Aが正しいとき、必ずBも正しい」ということですね。もしAが正しくないとすると、Bについて何も言えません。ところが、「AならばB」という命題は、Aが正しくないときは必ず真である、というわけです。ここに混乱が生じると命題の真偽が直感に反するということが起こります。

一つの問題は、「ならば」が単なる命題の演算子であるという以上に、推論の方向を指示する接続詞として解釈できるということがあります。命題「AならばB」は、推論として「Aが正しいことを仮定すると、Bが正しいことが導かれる」とも解釈できるわけです。後者の場合、Aが正しくない場合は仮定に当てはまらないので扱いません。しかし、「AならばB」は命題なので、Aが正しくない場合でもちゃんと真偽が定まらないといけないのです。

ここで推論を命題の言葉に置き換えるために、「推論『Aが正しいことを仮定すると、Bが正しいことが導かれる』とは、どんな真理値の割り当てに対しても命題『AならばB』が真となることに等しい」という同一視を行うことにします。推論の意味では、もし「Aが正しい」ことが解っているとすれば、「Bが正しい」が結論されるはずです。例えば、「この部屋に酸素があるならば、私は息ができる」と「この部屋に酸素がある」の両方が正しいならば、「私は息ができる」わけです。このような推論は「ならば」の意味を考えれば妥当でしょう。これを論理学では modus ponens(モードゥス・ポーネンス)といい、「ならば」の意味そのものと言っていいほど基本的な推論規則です。

上の同一視をもとに命題「AならばB」の真理値を見るために、modus ponens を対応する命題に置き換えましょう。推論を言葉で書くと、「「「Aが正しい、ならば、Bが正しい」かつ「Aが正しい」」、ならば、Bが正しい」となります。これを命題に置き換えて記号で書くと

((A \Rightarrow B) \wedge A) \Rightarrow B

です。上の推論規則を認めるということは、すなわち、どのようなAとBへの真理値の割り当てに対しても、この命題は真でなければなりません。すなわち、真理値表は

f:id:azapen6:20150512184023j:plain

となるはずです。ここで、A \Rightarrow BA = \mathrm{T} のときだけ真理値が決まっていますが、(A \Rightarrow B) \wedge AA = \mathrm{F} のとき必ず偽となるので、真理値がすべて確定しています。

さて、真理値表をよく見ると、仮定が偽のときの値が既に確定していることがお分かりでしょうか?

X:= (A \Rightarrow B) \wedge A

と置いて X と B の組に対する X \Rightarrow B の真理値を見ると、

f:id:azapen6:20170121143251j:plain

となっています。すなわち、F \Rightarrow TF \Rightarrow F も真であることが分かります。X を改めてA と置くと、A \Rightarrow B の真理値表は

f:id:azapen6:20170121143302j:plain

となります。つまり、仮定が偽ならば結論は何でもありというわけです。

極端な例としては、常に偽である特殊な命題 \bot に関して、どんな命題 B を持ってきても \bot \Rightarrow B が真である、というものがあります。証明の意味では、\bot は矛盾に対応する記号です。つまり、「矛盾からは何でも導出できる」ということです。この規則は Principle of explosion といい、古典論理を特徴づけるものです。以下に示すように対偶法や背理法が正当性を持つのは、本質的にはこの規則の帰結です。

対偶法と背理法

上の真理値表より同値関係

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

が直ちに出ます。

これを用いて、対偶の同値関係は

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

と計算できます。

他には背理法(帰謬法)、すなわち「Aが成り立たないことを仮定して誤りが導かれるならば、Aが成り立つ」という論法の正当性を計算で示すことができます。背理法に相当する命題は (\neg A \Rightarrow \bot) \Rightarrow A と書けます。これを同値関係によって変形すると、

((\neg A \Rightarrow \bot) \Rightarrow A) \Leftrightarrow (\neg ( A \vee \bot) \vee A) \Leftrightarrow (\neg A \vee A)

となり、最後の命題は常に真であることから、最初の命題も常に真です。すなわち、二値論理のもとで背理法は正当な論法となります。

以上のことから、二値論理は本質的に対偶法と背理法を含んでいると言えます。この辺の話は深い内容がありますが、これ以上は突っ込みません。