背理法の利用

Last-modified: 2008-01-28 (月) 16:35:58

背理法は証明方法の一つで、ありえないことがありえると仮定して、論理的に導き出された命題が矛盾することを示します。矛盾により仮定がありえないことを証明します。

例をあげて考えて見ます(あまりよい例ではないと思いますが)

真夜中に帰ってきた子供がお酒を飲んでいるか背理法で考えて見ます。
お酒を飲んでいると仮定します。
お酒を飲んでいるとすれば、
  →千鳥足になっている
  →息がお酒臭い
  →顔が赤い
帰ってきた子供は、千鳥足になっていないし、息もお酒臭くない、そして、顔も赤くない。
よって矛盾するので、仮定が誤っている、つまりお酒を飲んでいないと考えられます。

サポートをする際に背理法は消去法に利用できるのではないかと考えられます。

シャーロック・ホームズは以下のように言っています。

 When you have eliminated all which is impossible, then whatever remains,
 however improbable, must be the truth.
 
 すべての不可能な選択を消したときに、残った一つはどのようなものであれ、
 起こりえそうにないものであれ、真実である。

ホームズは推理に消去法を用いて真実に到達しようとしました。しかしどうやって不可能な選択を選び出すのでしょうか。ここで背理法が使えるのではないかと思います。

例えば、2008/1/28に強盗事件が東京で夜中に発生して、A容疑者、B容疑者、C容疑者がいるとします。
背理法では、それぞれの容疑者を犯人と仮定して、犯人であれば起きえないであろう矛盾を探します。

まずA容疑者が犯人と仮定します。A容疑者が犯人とするならば、彼は東京にいることになります。
しかし実際にはA容疑者はその日に大阪に出張をしていたことが分かりました。東京と大阪に同じ時間にいることはできないために、A容疑者が犯人であることは除外されます。

次にB容疑者が犯人と仮定します。しかしB容疑者の場合には特に矛盾が見つかりませんでした。

最後にC容疑者が犯人と仮定します。C容疑者は前日に交通事故にあい、骨折をして病院に入院していました。目撃者の証言では犯人は怪我をしているようには見えなかったそうです。よって目撃証言とC容疑者の状態はm順するためにC容疑者は犯人でないことが分かります。

残ったのはB容疑者だけですので、この場合にはB容疑者が犯人となります。

もちろんこの証明方法にはいくつもの不備があります。

= 他に容疑者がいないのか
= 矛盾を解消できないか(大阪から東京に移動する方法がある、怪我はそれほど重くないなど)

しかし方法論としては絞込みができるということでサポートに向いています。例えば「ファイルが削除できない」現象について考えます。これに対して原因をいくつかあげます。

= ファイルが存在しない
= ファイルにロックがかかっている
= 削除のルーチンを飛ばしている
= 権限が足りない

4つの原因に対してそれぞれ逆を仮定することにより、消去することで原因の特定ができます。