本屋にいくと『証明の読み方・考え方』という本が目に入った。数学の証明の本だ。手にとって眺めると面白そうなので買ってみた。中学や高校の数学でも証明問題は苦手だった。苦手というよりちゃんと証明の仕方を教わったり、勉強した覚えがない。『証明の読み方・考え方』で紹介されている前進後退法という考え方を知ることで証明の苦手意識が薄くなった。
後ろから前から
この本で紹介されている証明方法の基礎となるのが前進後退法だ。聞いたこともない方法だったが、難しい話ではない。
証明したい対象から考える後退過程と、仮定など既知の情報から結論に向かって考える前進過程という２つの過程を組み合わせて証明の道筋を探していく方法だ。
まず後退過程で、証明したい命題というゴールに到達するためはどういう命題が真であればいいのかを考える。さらにその命題が真であるには……と、証明したい命題から逆順に論理を遡っていく。
続いて前進過程だ。前進過程は仮定などの既知の情報からスタートして、別の命題を作っていく。このときに後進過程に接続できるように論理を進んでいく。
後退過程と前進過程が接続すると、仮定から証明したい命題への論理的な道筋が出来上がる。
最初の一歩が後進過程で、何が言えればいいのか？を考えることと、仮定から直接結論を目指すのではなく、後進過程に接続できるところを目指すというところが特に個人的に面白いと思った。
本の中では図形の簡単な証明の例でわかりやすく説明されているので、専門的な知識は不要だ。この章だけでも面白いのでおすすめだ。
迷路の探索
『証明の読み方・考え方』の表紙は迷路が描かれているが、証明の道筋を考えるのは迷路の入り口から出口を見つける探索のようだ。
迷路の探索といえば、グラフの探索アルゴリズム。証明もある種の探索問題なのか、という考えが頭に浮かぶ。
それにしても前進後退法で、スタートとゴールからそれぞれ探索を始めるというのは奇妙な方法だ。双方向探索アルゴリズムというものもあるらしいが、あまり聞かない。
証明問題が構成するグラフというのが、双方向から探索するのが効率的な特性を持っているのだろうか。
本の構成
前進後退法は全15章のうちの第2章で、全体は以下のような構成になっている。
- 第1章 数学的に真理であるとはどういうことか
- 第2章 前進後退法
- 第3章 定義と数学用語について
- 第4章 量化詞1：構成法
- 第5章 量化詞2：抽出法
- 第6章 量化詞3：特殊化
- 第7章 量化詞4：入れ子の量化詞
- 第8章 主張の否定をどう書くか
- 第9章 背理法
- 第10章 対偶法
- 第11章 一意性の証明法
- 第12章 帰納法
- 第13章 二者択一法
- 第14章 最大最小の証明法
- 第15章 まとめ
前進後退法が具体的な証明方法の最初の基礎で、その後に含まれるキーワードから各種の証明パターンを見極めていくという流れだ。量化詞というのは∀や∃などの記号のことだ。
数学の教科書で「数学的帰納法」という言葉は載っていたけど、この本のようにまず前進後退法の考え方を教えておいてくれよと思った。
感想
この本を手に取ったときの期待通り、数学の証明の考え方の基礎を知ることができてよかった。証明に対する苦手意識も薄くなったと思う。
大人になってから数学の証明を読んだり考えたりする必要に迫られることはないけど、何が正しくて何が正しくないのかを論理的に考える機会は少なくない。例えばソフトウェアのバグの原因を考えたり、障害の原因を考えるときにも論理的な思考が必要だ。前進後退法のように目的から後ろ向きに考えることと、既知の情報から前向きに考えることを組み合わせるという考え方は応用できそうだ。そういう意味でも読んでよかった。
