離散数学入門

基本情報

コンセプト

本書は以下のコンセプトをもって書いたものです。

・本書を読み進めていく上で必要なことは、高校1年生が習う数学をよく理解する力をもっていること。

・近年、符号理論、暗号理論、プログラム理論などが注目されるようになってきたのに伴って、それらの基礎となる離散数学が注目されるようになってきました。離散数学は集合論や初等整数論を基礎として、純組合せ論、電気や化学とも関係が深いグラフ理論、実験計画や符号とも関係が深いデザイン論などが主な対象となります。そのような背景から、離散数学は新鮮な気持ちで学ぶことができることを前面に出して執筆しました。

・本書は、いわゆる「読み物」ではなく、初歩から一歩ずつ確実に理解を積み上げていく「教科書」スタイルをとっています。各章の特徴は以下の通りです。

・1章：整数の誕生の歴史から始まって、集合や写像の丁寧な説明を心掛けること。

・2章：最初に、樹形図の発想などを用いて高校数学で学ぶ順列や組合せなどを復習すること。さらに、離散数学の根本は「数えること」であることに注目し、それを「帰納的に考えて数える」、「2通りに数える」、「対称性を利用して数える」の3つに分類し、それぞれの平易な例を紹介すること。

・3章（「帰納的に考えて数える」発想）：数えることに関して重要な包含・排除の公式、グラフ理論の「木」の個数、純組合せ論的な「オモリの問題」などを学び、最後に帰納的に数える発想を本質とする「偶置換・奇置換の一意性」の証明について学ぶこと。

・4章（「2通りに数える」発想）：グラフ理論やデザイン論の重要な基礎的定理の証明は2通りに数える発想を用いていることを説明し、応用例として正多面体の分類、16人麻雀大会のスケジュールなどを取り上げ、最後に2通りに数える発想を本質とする「偶置換・奇置換の一意性」の証明について学ぶこと。

・5章（「対称性を用いて数える」発想）：ダイオキシンの異性体や正多面体の合同変換の個数を求める例から始めて、組合せ構造の自己同型群の位数を求めるときに有効な公式を証明し、代数学のガロア理論の話題、および対称性を用いて数える発想を本質とする「偶置換・奇置換の一意性」の証明について学ぶこと。

・6章（無限集合の濃度）：「1対1の対応」から始め、自然数全体の集合と実数全体の集合の濃度が等しくないことを示す「カントールの対角線論法」、および2つの無限集合の濃度が等しいことを示すときに有効な「ベルンシュタインの定理」について、例も交えた丁寧な証明を心掛けること。