01 / 読書ガイド
読書ガイド
引用
Levin, O. (2025). Discrete Mathematics: An Open Introduction (4th ed.). Chapman & Hall/CRC. Free official edition: https://discrete.openmathbooks.org/dmoi4.html
章の要約
第0章：序論と予備知識
短い冒頭の章では、握手、数列、数え上げに関する小さなパズルを通じて数学の何が「離散的」なのかを説明し、続いて本書全体で使われる離散構造――集合、関数、数列、関係、グラフ――を非形式的に一巡する。これらの構造はここでは「必要に応じて」導入され、第5章でより形式的に扱われる。
第1章：論理と証明
本書における証明への橋渡しとなる章である。原子命題と複合命題、量化子と述語、逆と対偶を伴う含意、真理値表、論理的同値（量化された命題を含む）、演繹を扱う。続いて直接証明、対偶による証明、背理法を教え、新設の節でこれらの方法を集合、関数、関係、グラフに適用する。章のまとめでは、ゴールドバッハ予想を例に、命題の論理形式が証明の形をどのように示唆するかを示している。
第2章：グラフ理論
ケーニヒスベルクの橋のような問題から始めてグラフを定義し、木（性質、全域木、根付き木）、オイラーの公式とその多面体との関係を含む平面グラフ、ハミルトン路とあわせたオイラー路とオイラー回路、頂点彩色と辺彩色を学ぶ。関係の節では、関係、同値関係、分割をグラフとして見る方法を示し、章の最後では二部グラフのマッチングとホールの結婚定理を扱う。
第3章：数え上げ
この版では規則よりも結果の集合に注目するよう再構成された章で、格子路、ビット列、部分集合を通して見るパスカルの三角形から始まる。続いて和の法則と積の法則、重なりのある結果に対する包除原理、商の法則を伴う組合せと順列、多重集合（ビット列による「星と棒」）、組合せ論的証明を展開する。新設の節では数え上げを条件付き確率を含む確率に応用し、最後の節では多重集合、完全順列（撹乱順列）、関数の数え上げに包除原理を用いる。
第4章：数列
数列を一般項の公式と漸化式、部分和と階差で記述し、短い Python の例を添える。等差数列と等比数列、有限差分で見つける多項式数列、和の求め方（「逆順にして足す」「掛けてずらして引く」）を学び、特性根の方法で線形漸化式を解く。最後に数学的帰納法と強い帰納法を扱い、数列の再帰的な記述と帰納的な推論を結びつける。
第5章：離散構造再訪
自己完結した章で、集合（記法、包含関係、演算、ベン図）と関数（記述の仕方、単射・全射・全単射、像と逆像）をより詳しく扱う。序文によれば、この章は本書の他の部分とは独立に学べる。
第6章：追加の話題
二つの話題で本書を締めくくる。母関数を作り、差分、積、部分和によって操作し、漸化式の解法に用いる。整数論入門では、整除性、剰余類、合同の性質、合同式の解法、一次不定方程式の解法を扱う。
主要概念
第0章：序論と予備知識
- 離散構造：集合、数列、関係、グラフのように、互いに分離した別個の要素からなる数学的対象で、現実の問題のモデル化に使われる。
- 離散構造としての関数：定義域の各要素に終域のちょうど一つの要素を対応させる規則で、多くの場合有限集合の間で考える。
第1章：論理と証明
- 含意：「PならばQ」という命題で、Pが真でQが偽のときだけ偽になる。対偶はこれと論理的に同値だが、逆はそうではない。
- 量化子：「すべての」と「存在する」で、その順序と否定が命題の意味を決める。
- 証明の型：命題の論理形式に応じて選ぶ直接証明、対偶による証明、背理法。
第2章：グラフ理論
- 木：閉路をもたない連結グラフ。n 個の頂点をもつ木には n − 1 本の辺がある。
- オイラーの公式：連結な平面グラフでは、頂点数から辺数を引いて面の数を足すと2になる。
- オイラー路：すべての辺をちょうど一度ずつ通る道で、グラフが連結で奇数次の頂点が0個または2個のときに限って存在する。
- 彩色数：隣接する頂点が異なる色になるために必要な最小の色数。
第3章：数え上げ
- 和の法則と積の法則：互いに排反な選択肢は足し、独立な段階は掛けて数える。
- 包除原理：共通部分の大きさを交互に足し引きして重なりを補正する。
- 組合せ論的証明：両辺が同じ集合を数えていることを示して恒等式を証明する。
- 完全順列：不動点をもたない置換で、包除原理を使って数える。
第4章：数列
- 漸化式と一般項の公式：前の項から項を記述する方法と、添字から直接記述する方法。
- 特性根の方法：フィボナッチの漸化式のような線形漸化式を、付随する多項式の根を用いて解く方法。
- 数学的帰納法：基底と帰納段階によってすべての n について命題を証明する方法。強い帰納法では前のすべての場合を使う。
第5章：離散構造再訪
- 集合演算：和集合、共通部分、差集合、補集合、直積で、ベン図で図示される。
- 全単射：単射かつ全射である関数で、二つの集合の要素を一対一に対応させる。
第6章：追加の話題
- 母関数：数列の項を係数とするべき級数で、漸化式の操作や解法に使われる。
- nを法とする合同：nで割った余りが等しい二つの整数は合同であるという。
- 一次不定方程式：整数解を求める方程式 ax + by = c。
批判的分析
長所
- 探究型の授業のために作られている。 各節は自由回答形式の「Investigate!」の問いと構造化された予習活動で始まり、読解問題で終わり、その後に練習問題と追加演習が続く。序文はこれらの使い方――授業前の予習、グループ活動としての利用など――をいくつか紹介しており、この構成は独習も支えている。
- 大規模で多様な演習。 第4版では300題近い演習が追加されて総数は750題を超え、予習、読解、練習、追加演習に分けられ、各章末には章の復習がある。選ばれた問題のヒントと解答は二つの付録に収められている。
- 対話的なオンライン版。 オンラインでは多くの予習活動と練習問題が即時にフィードバックを返し、一部はランダム化された別バージョンで練習でき、Python のスクラッチパッドも使える。第4章には数列のための短い Python の例がある。
- 結果の集合を通じた数え上げ。 改訂された数え上げの章は公式の暗記よりも結果の集合を見極めることを重視しており、章のまとめの最後の Investigate! では、表面上似た問題を方法ごとに分類させている。
短所
- 話題の選択は特定の授業に合わせたもの。 序文によれば話題はノーザンコロラド大学の学生向けに選ばれており、アルゴリズム解析（漸近記法）、ブール代数、有限状態機械、形式言語は扱われない。計算機科学の授業では補助教材が必要になるかもしれない。
- 一部の分野は深さが限られる。 整数論と母関数は短い「追加の話題」であり、確率は一節だけで、グラフ理論はネットワークフローや最短経路アルゴリズムのような話題の手前で終わる。
- 帰納法の登場が遅い。 帰納法は第1章の他の証明法とともにではなく数列の章の最後に置かれており、教員によってはもっと前に移したいと考えるかもしれない。
- 印刷版とPDFでは対話性が失われる。 フィードバック、ランダム化された練習、隠されたヒントはオンライン版の機能であり、PDFを使う読者は付録と自己管理によって答えを確かめる必要がある。
本書で扱う応用
応用は独立した章ではなく、例と演習に織り込まれている。グラフ理論はケーニヒスベルクの橋、地図の彩色、多面体、マッチングの問題によって動機づけられ、数え上げは条件付き確率を含む確率に応用される。数列は現実の状況の再帰的な記述と結びつけられ、Python で項を計算する。強い帰納法は分割統治の考え方と関連づけられ、整数論は合同式と一次不定方程式の解法で締めくくられる。
コースにおける位置づけ
この離散数学のリストで、Levin の本は、Lovász、Pelikán、Vesztergombi の Discrete Mathematics: Elementary and Beyond（一般に、整数論と組合せ論により重点を置いた問題主導の入門書とされる）と並ぶ。Rosen の Discrete Mathematics and Its Applications と Epp の Discrete Mathematics with Applications は、一般に包括的な教科書とされる。これらはアルゴリズムや計算量など Levin が扱わない話題を含んでおり、Levin を取り組みやすい中核テキストとして使う計算機科学の授業で参考書として役立つ。
Graham、Knuth、Patashnik の Concrete Mathematics と van Lint と Wilson の A Course in Combinatorics はさらに先へ進む本である。Levin の第3・4・6章（数え上げ、数列と漸化式、母関数）は両者へのよい準備となる。これらの章を楽しめた学生は、和や漸近的手法を学ぶなら Concrete Mathematics へ、より深い組合せ論を学ぶなら van Lint と Wilson へ進むとよい。
本書の使い方
本書は数学と計算機科学の1〜2年生を対象とし、将来の学校教員も含む。また証明への橋渡しの授業としても機能する。始めるには中等教育の代数で十分であり、証明の経験は前提としない。
1学期の授業では本書の順に進めることができる。第0章、第1章（論理と証明）、第2章（グラフ理論）、第3章（数え上げ）、第4章（数列と帰納法）を扱い、第5章は参照や復習に、第6章は発展として使う。序文によれば節はかなり独立しているので、教員は順序を入れ替えられる。各節では、読む前に Investigate! の問いと予習活動に取り組み、読んだ後に読解問題に答え、それから練習問題――できればオンラインで即時のフィードバックを受けながら――に取り組み、その後で追加演習と章末の復習に進むとよい。選ばれたヒントと解答は、著者の助言どおり、できるだけ控えめに使うべきである。
版と出典
本ガイドは Discrete Mathematics: An Open Introduction 第4版（© 2013–2025 Oscar Levin、CC BY-NC-SA 4.0、序文の日付は2024年、PDF作成は2025年9月）に基づき、公式の版ページ https://discrete.openmathbooks.org/dmoi4.html からリンクされた無料PDFを読んで作成した。謝辞、序文（目的、探究型の設計、第4版での変更点）、「本書の使い方」、小節レベルまでの目次全体、第0章全体、第1〜4章の章のまとめ、そして全体にわたる節の冒頭と主要な主張（ホールの結婚定理、鳩の巣原理、数列と帰納法の内容を含む）を参照している。