論理パズルの算術

次のようなパズルを見たことがあるかもしれない。

常に正しいことを言う正直者と、常に間違ったことを言う嘘つきがいるとする。どちらも「いいえ」と答える質問は?

このようなパズルは一応、試行錯誤によって解くことができる。しかし、つるかめ算のように数式に落とし込んで、よりスマートに解くこともできるのである。今回はその一例を紹介する。

 H: 正直者である,\quad A: 「はい」と答える,\quad S: 質問の内容の真偽
とする。そして、 A,Bの真偽が一致するかの真偽をA=Bで表す。

この時、H=Aが真であることは正直者の「はい」か、嘘つきの「いいえ」を表す。この状況でSは真である。そして、そうでない場合、正直者が「いいえ」と答え、嘘つきが「はい」と答える場合はSは偽である。ゆえに、H=Aの真偽とSの真偽が一致するから、(H=A)=Sである。

これを使って問題を記述すると、 ((H=A)=S)= \neg Aとなる。記述の際には、真となるように記述するのではなく、満たされないときに矛盾が起きるようにしなければならない(でなければ、問題設定が偽である可能性を除外できない)。今回の式では、「いいえ」と答えた時左も真になって矛盾は起きず、「はい」と答えたときは左が偽になって矛盾が起きるようになっている。

実際、=は同値関係であるから、 H=A=S=\neg A。否定同士は打ち消し合って、 H=S=\bot\bot\negにして付けることができ、 S=\neg H。よって、答えの質問は「あなたは嘘つきか?」となる。

この同値関係では代入もできたりする。ただ、特殊な場合でないと簡単には解けない。その点、論理パズルは特殊なものが多い。

参考:
スマリヤンの究極の論理パズル|白揚社 -Hakuyosha-