数理パズルで楽しく学べる論理学

---------
ある島にはAさんとBさんの二人の住人がいます。
一方が正直者であり，他方は嘘つきです。
ここで，Aさんは次のように言いました。
「Bさんと私の少なくとも一人は嘘つきだ。」
---------
さて，Aさんは正直者ですか，またBさんはどうでしょうか？

次のパズルは，ジョージ・ルーカスが製作総指揮した映画（Labyrinth）で使われた問題です。
---------
ここに左右二つの扉があり，それぞれに門番がついています。
一方は正直者であり，他方は嘘つきです。
左右の扉のうち一つだけが城に通じています。
門番一人に一つの質問をして，どの扉が城に至るのかを聞き出してください。
映画の主人公サラは，一人の門番にある質問を尋ねました。
どのような質問でしょうか？
---------
質問に対する回答を確認後，”前とは違って賢くなったみたい”と話しながら，サラは一つの扉を開けます。

形式的ではない論理的思考のための題材として，スマリヤンの論理学の本にはこのようなパズルが収められています。そこでは，社会学と論理学に興味を持っている人類学者アバクロンビーの冒険が続くことになります。しかしこのような問題を真面目に自然言語で考えていると，目が回りそうになります。私は実際に目がまわってしまいました ^^;　

そう言えば中学生の時に，リンゴやミカンの個数を求める問題で，変数を使って式をたてました。そして，式を計算して解くことで個数を求めました。これと同じ様に式を使って表現して，これらのパズルの答えを求めることはできないでしょうか？

本書で言っている記号化・形式化とは，このような式（論理式）を使って物事を表現することを意味しています。この種のパズルの解法では，大まかには二つの方法が考えられます。

一つは，推論規則を使って答えを導出する方法です（証明論的手法）。もう一つは，真理値と呼ばれる式の値を計算する方法です（意味論的手法）。全く異なるこれら二つの手法の関係を理解することが本書の大きな目標です（ゲーデルの完全性定理）。

さらに，証明も同様に式（ラムダ式）として表現されることを学びます。これによって，証明をプログラムと考えることができて，論理式をプログラムの型（タイプ）と解釈することができます。このような考え方に基づくと，高校で勉強した数学的帰納法の証明から再帰的プログラムが得られることになります。論理とプログラミング言語の親密な関係（カリー・ハワード同型）についても習得することができます。