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

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

数理パズルを通して,身の回りの物事を記号化する力や論理的に説明・表現する力を養う。

ジャンル
発行年月日
2022/03/25
判型
A5
ページ数
200ページ
ISBN
978-4-339-02923-9
数理パズルで楽しく学べる論理学
在庫あり

定価

2,860(本体2,600円+税)

カートに入れる

電子版を購入

電子版を購入

購入案内

  • 内容紹介
  • まえがき
  • 目次
  • レビュー
  • 著者紹介
  • 広告掲載情報

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

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

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

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

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

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

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

数理パズルを楽しみながら論理学を学ぶ。重きを置いたポイントはつぎの2点である。
  1.数理パズルの例を通して,文や対象の記号化(形式化)の大切さを理解する。
  2.記号化された例を通して,論理の構文論的側面(推論規則,証明論)と意味論的側面(真理値,構造,モデル)を理解する。
記号を使って物事を表現することは曖昧さを排除した記述のために大切であり,プログラミングにも必要な能力である。記号化の作業は単純に見えるが記号化される対象の本質をつかむ作業である。文章に限らず物事がいったん記号化されると,元の意図を忘れて記号の世界に持ち込むことができる。そして,計算機を活用して自動処理や高速な計算が可能になる。論理の構文論的側面とは,このような機械的な計算・推論(証明論)を意味している。一方,意味論的側面とは記号の解釈およびその意図や真偽の値(意味論・モデル)に関することである。この二つの側面の違いと関係を理解することが目標である。これら二つの側面は,情報社会では例えば検証の分野,特に数理的・形式的技法で活用されている。それらは,モデル検査技法(様相・時相論理)とアルゴリズムの検証(ホーア論理)の応用例として知られている。

対象読者とそのレベルは,情報系および文系を含む関連分野の学部学生を念頭に置いた。そのために,一つずつ順を追って概念や定義をゆっくりと説明していった。また,証明も可能な限り省略しなかった。

最初に日常的推論で考察可能なパズルを導入した。まず本書のねらいをここで説明した。そして,スマリヤンによる「正直者と嘘つきのパズル」がある。記号を使ってこのパズルを表現し分析していった。重きを置いたことは,記号化が妥当であることの説明である。これは真偽の意味論に基づいて与えられる。

そして,大切な点は,パズルの答えを見つけるためにまったく異なる二つの手法(証明論的手法と意味論的手法)があるということである。最終的にはブーロスの「最強の論理パズル」にも挑戦して論理式を活用した記号化法は興味深いことを見ていく。また,計算機科学や数学でよく登場する概念についても記号を使って述べていった。このように,記号化の題材として多くの数理パズルを引用した。これは普通の教科書と大きく異なる点である。出発点から目的点に行くのに,グーグル検索やダイクストラのアルゴリズムなどを使って最短経路や最適パスを通るのではなく,それとは対極的な戦略である「最長片道切符」流の進み方のように思われる。

そしてつぎに,論理の構文論的側面・意味論的側面の話題につなげる。構文論では形式的体系として,シーケント計算,ヒルベルトの体系,自然演繹の体系,タブロー法などさまざまな体系が知られている。ここでは,日常行う論理的推論を素直に反映したゲンツェンの自然な論理計算(自然演繹法)の考え方に従って,直観主義論理や古典論理における論理的推論の形式化(NJ,NK)を紹介する。その理由は,日常的推論でも十分に活用できるからである。グローバル化された社会における教育でしばしば重要視される点は
  1.コミュニケーション能力
  2.協調性
  3.クリティカルシンキング
である。ここで,自然演繹法の証明をすることは,特に3の訓練につながると考えられる。あることを仮定するとなにが導かれるか。そしてその論理的筋道・説明はいかなるものか。また,別の状況ではなにが可能かなどを理路整然と述べることができる。ここでの証明の過程は証明図と呼ばれる図で表現されるので,仮定から結論に至る推論の流れが読み取りやすい。さらに,この図もラムダ計算の式によって形式化可能となり,証明図の簡約(変形)はラムダ式の計算で扱うことができる。この話題は,カリー・ハワード同型の4.3節で扱う。

このように形式化は大切であるが,対象が込み入ってくると記号化が容易とは限らない。しかし,この困難さを逆手にとると,物事の内容を整理して深く理解する(本質をつかむ)ための方法として記号化が使えるということである。

これは,一長一短である。論理式,プログラミング言語,定理証明システムなどの形式言語を使って教科書などに書かれている内容,物事の性質,振る舞いを記述することはまさに検証技術の一つの利用法である。このような記号化に重点を置いたが,記号化のためにはなにが重要であろうか?自然言語で物事の性質,振る舞いをキチンと説明・記述することである。それなくしては,形式化も考えられない。いったん記号化されると,元の意図を忘れても正しく推論可能な体系はすでに準備されているので,中身のよく知らないことが簡単に記号化できてしまっては虫がよすぎる。この作業の過程で,定義の曖昧さや場合分けの欠如などが発見されることもある。記号化の先には先人たちの叡智に満ちた論理の世界が広がっている。さらに,記号化は形式論理に限らずほかの分野の領域にも転用可能な基本スキルである。そこでは,形式化の妥当性を確認する必要がある。

本書では,論理の構文論的側面と意味論的側面を明確に区別する立場で,記号化・論理の学習から出発した。その流れは,ゲーデルの完全性定理にて合流する。それは,恒真性(トートロジーである性質)と形式的体系の証明可能性との関係であり,つぎの二つの性質がポイントになる。
  •性質1:推論規則によって恒真性は保存されている。
  •性質2:推論規則の逆操作(分解)によっても恒真性は保存されている。
性質1から,恒真な式から証明できる式は恒真な式だけであることがわかる。
性質2から,恒真ではない性質は推論規則によって伝播することがわかる。これは,恒真ではない式に対する反例の生成につながる。

本書で扱っているトピックスはつぎの五つに分類される。階段を一段ずつ登るように話を進めたので,それぞれ独立に読むこともできる。ただし,数理パズルと記号化については,真理値表の定義と基本的な推論規則の使い方を仮定している。もし必要ならば,命題論理(2.4節)と述語論理(3.3節)における定義を先読みしてもよい。
  •数理パズルと記号化について
  2.1節→2.2節→3.1節
  •ブール代数とブール関数について
  2.5節→2.6節
  •命題論理について
  2.1節→2.3節→2.4節→2.5節→2.6節→2.7節→2.8節→2.2節
  •述語論理について
  2.1節→3.2節→3.3節→3.4節→3.1節
  •カリー・ハワード同型について
  2.7節→3.3節→4.1節→4.2節→4.3節
1章は準備運動の章であり,基本的な言葉を説明した。3.1節でも復習するが,必要なときに復習すればよい。2.1節では本書の二つのポイントを日常的な推論の例で説明した。また,可能な限り図などを使った説明や証明などを加えた。証明は定義の言い換えや論理式・証明の構成(長さ)に関する帰納法を使うことが多いので,場合分けを丁寧に調べれば確認できる。

本書のつぎのステップの重要なテーマとしては,記号化の限界に関して,不完全性定理,記号化による表現能力などさまざまな話題がある。

本書の執筆・出版のためコロナ社の皆様にお世話になった。心より感謝申し上げる。

2022年1月
藤田憲悦

1. 準備
言葉づかいについて:集合,順序と同値関係,写像と関数

2. 命題論理
2.1 日常的推論と記号化
2.2 数理パズルと記号化
 2.2.1 スマリヤン流のパズル
 2.2.2 不思議の国のパズル
 2.2.3 スマリヤン流パズル再考
 2.2.4 パズルランドのアリス
 2.2.5 同値式の代数的性質
 2.2.6 映画Labyrinthのパズル
 2.2.7 ジョージ・ブーロスの最強のパズル
2.3 命題論理の言語:論理式
2.4 命題論理の意味論
 2.4.1 論理式の値:真理値
 2.4.2 恒真(トートロジー),充足可能,充足不可能
 2.4.3 意味論的同値関係
 2.4.4 意味論的帰結Γ|=A
2.5 ブール代数
2.6 ブール関数
2.7 命題論理の形式的体系
 2.7.1 自然演繹の体系NJとNK
 2.7.2 古典論理と直観主義論理:埋め込み
2.8 形式的体系の健全性と完全性
 2.8.1 NKの健全性
 2.8.2 NKの完全性

3. 述語論理
3.1 数理パズルと述語論理による記号化
 3.1.1 だれがヒゲを剃るか?
 3.1.2 スマリヤン流パズル述語論理版
 3.1.3 Tiffany Duneau:Solving logical puzzles in DisCoCircにおけるスマリヤン流パズル
 3.1.4 関数の連続性の定義
 3.1.5 言葉づかいについての復習
3.2 述語論理の言語
3.3 述語論理の形式的体系
 3.3.1 自然演繹の体系NKとNJ
 3.3.2 述語論理におけるグリベンコの定理:埋め込み
3.4 述語論理の意味論
 3.4.1 構造と解釈
 3.4.2 NKの健全性
 3.4.3 NKの完全性:シーケントの分解と反例の構成

4. 証明の形式化とラムダ計算
4.1 証明図の簡約
4.2 証明の記号化・形式化
 4.2.1 ラムダ記法:関数と値の区別
 4.2.2 ラムダ項(ラムダ式)
 4.2.3 ベータ変換
 4.2.4 チャーチ・ロッサーの定理
 4.2.5 型付きラムダ計算:型推論
 4.2.6 型付きラムダ項とベータ変換
4.3 カリー・ハワード同型
 4.3.1 論理式と型
 4.3.2 証明図の簡約とベータ変換,CPS変換と埋め込み
 4.3.3 古典論理の証明項:ラムダ・ミュー計算

引用・参考文献
索引

読者モニターレビュー【 やまけー 様(ご専門:数学)】

本書はタイトルにあるように数理パズルを題材に論理学を学習するための書籍である。
準備としては、大学低学年で扱う集合と写像の知識があればよく、意欲的な高校生であれば高校で集合を勉強していると第1章でからしっかり読み込むことで対応可能である。
論理学という性質上、数式も多く記載されているが行間が少なく筆者の説明も丁寧に感じた。
全体的に数理パズルを題材にしているため全体的に楽しく読めるかなと感じた。
また、自分も含め論理学を苦手としている方が多いが最初の1冊として読むのには適していると感じた。

読者モニターレビュー【あめ色玉ねぎ 様(ご専門:システム工学)】

本書は、大学に入学したての理系学生や、日常で数学を使うことの少ない文系学生をはじめとした、初学者でも読みやすい入門書である。
導入は簡潔な用語の定義から始まり、読み進める途中で用語がわからなくなっても、すぐに読み返して確認できるようになっているのが大変ありがたい。序盤は高校数学の知識があれば理解できるような簡単な数理パズルを用いて記号化に慣れ親しむところから始まり、徐々に複雑な内容へと移行していくため段階的に理解することができる。全編を通して、数式ばかりでなく言葉での解説も丁寧であるため、数学に馴染みがなくとも読みやすい。また、図や表による補足の説明も随所にあるため、視覚的に理解が深まる。
論理学の考え方は慣れるのに苦労することが多く、学び始めに良き入門書と出会うことがその後の理解のスピードを左右すると言っても過言でない。かく言う自分自身も、大学入学してすぐの春に論理学の授業で頭を悩ませていた。本書は、そんな当時の自分に送りたいと思える一冊であった。

藤田 憲悦(フジタ ケンエツ)

大学院で最初に研究したテーマは,電子工学の分野で,周期表のII族とVI族の化合物半導体(ZnSe)に関する研究でした(GaN:窒化ガリウムでもなくInGaN:窒化インジウムガリウムでもありません).この当時は,青色発光ダイオードのための材料を調べていました.その材料で作ったダイオードが青く光っていた写真は今でも持っています.その後は,論理学とラムダ計算との深淵な関係に興味を持って修行に励んでいます.エドムント・フッサールの「真の方法とは,探求されるべき事柄の性質に従うべきものであって,われわれの先入見や成心に従うべきものではない.」(厳密な学としての哲学:小池稔訳)は,研究対象と研究方法の本質的な関係を表現していると思われます.

掲載日:2022/05/07

読売新聞広告掲載(2022年5月7日)

掲載日:2022/04/18

情報処理学会誌「情報処理」2022年5月号広告

掲載日:2022/03/14

「数学セミナー」2022年4月号広告

掲載日:2022/03/02

「電子情報通信学会誌」2022年3月号広告