離散数学とその応用

引用

Rosen, K. H. (2025). Discrete Mathematics and Its Applications (2025 release). McGraw Hill.

章の要約

McGraw Hill は2025年版について、13の章と付録を挙げています。出版社が示す第7版の目次にも同じ13の章のテーマが並んでいます。公開されている目次は章のタイトルだけなので、以下の詳細のうち、出版社による第8版（2019年）の変更点リストや第7版（2012年）の序文に基づくものは、その旨を明記します。

第1–2章：Foundations: Logic and Proofs（論理と証明の基礎）／Basic Structures: Sets, Functions, Sequences, Sums, Matrices（基本構造：集合、関数、数列、和、行列）

第1章は論理から始まり、続いて証明の方法を扱います。出版社の第8版変更点リストには、論理パズルと、n クイーン問題を充足可能性問題としてモデル化する例が挙げられています。第2章は全体で使う基本構造、すなわち集合、関数、数列、和、行列をまとめます。同じリストには、多重集合が演習問題から本文に移されたことも記されています。

第3–4章：Algorithms（アルゴリズム）／Number Theory and Cryptography（整数論と暗号）

第3章はアルゴリズムを扱い、第8版の変更点リストによれば、文字列照合問題とそのブルートフォース・アルゴリズムが含まれています。第4章は整数論と暗号を扱い、同リストには、拡張ユークリッドの互除法、素数についての最近の発見と未解決の予想、準同型暗号が挙げられています。

第5–6章：Induction and Recursion（帰納法と再帰）／Counting（数え上げ）

第5章は帰納法と再帰にあてられ、第8版の変更点には、例題の前に置かれた、数学的帰納法による証明のひな形の拡充が含まれます。第6章は数え上げを導入し、同じリストには、除法原理の扱いの拡充が記録されています。

第7–8章：Discrete Probability（離散確率）／Advanced Counting Techniques（高度な数え上げの技法）

第7章は離散確率を、第8章は基礎を超えた数え上げの技法を扱います。公開されている目次では、どちらもこれ以上詳しくは説明されていません。

第9–11章：Relations（関係）／Graphs（グラフ）／Trees（木）

第9章は関係を扱い、第8版の変更点リストによれば、データマイニングの相関ルールが n 項関係の節で論じられています。第10章のグラフには、同リストによれば、人工知能の意味ネットワークをグラフとしてモデル化する新しい例が含まれます。第11章は木に移ります。

第12–13章：Boolean Algebra（ブール代数）／Modeling Computation（計算のモデル化）

最後の2章はブール代数と計算のモデル化を扱います。第7版の序文は、この2章をいずれも、コンピュータ科学を重視する場合の任意の内容として位置づけています。

付録

第7版の序文は3つの付録を挙げています。実数と正の整数の公理、指数関数と対数関数、そしてアルゴリズムを表現するために使う擬似コードです。第8版の変更点リストによれば、抽象代数（群、環、体）の章が別のオンライン資料として提供されており、カスタム版に追加できます。

主要概念

第1–6章：論理、構造、アルゴリズム、整数論、数え上げ

• 論理と証明：第1章のタイトルに掲げられた基礎で、序文はこれを、その後の証明方法の議論の土台と位置づけています。
• 集合、関数、数列、和、行列：第2章の基本構造。
• アルゴリズム：第3章の主題。序文によれば、アルゴリズムは言葉と擬似コードで記述され、その計算量は初等的なレベルで分析されます。
• 整数論と暗号：第4章の主題。
• 帰納法と再帰：第5章。序文は数学的帰納法を重視していると述べています。

第7–13章：確率、関係、グラフ、木、計算

• 離散確率と高度な数え上げ：第7–8章。
• 関係：第9章。
• グラフと木：第10–11章。
• ブール代数と計算のモデル化：第12–13章。

批判的分析

長所

• 1冊で幅広く。 目次は論理と証明からグラフ、ブール代数、計算のモデルまで及び、出版社は本書が数学、コンピュータ科学、工学の専攻の学生を念頭に書かれたと述べているので、1冊でさまざまな種類の課程に対応できます。
• 明示された教育上のテーマ。 第7版の序文は、本書を貫く5つの柱として、数学的推論、組合せ解析、離散構造、アルゴリズム的思考、応用とモデル化を挙げています。800を超える例題、難易度別に整理された4,000を超える演習（奇数番号には解答または解法の概要つき）、各章末の重要用語リストと復習問題、さらに任意のコンピュータ・プロジェクトとライティング・プロジェクトがあると報告しています（いずれも第7版の数字）。
• 柔軟な課程設計。 同じ序文は、章どうしの依存関係を最小限にしていると述べ、必須の節と任意の節の表を示しているので、1学期の2年次向け課程、2学期の課程、コンピュータ科学寄りの課程のそれぞれが異なる部分を選べます。
• 前提が明示されている。 序文は、明示的な前提条件を大学レベルの代数だけとし、微積分に言及するわずかな箇所には印がついていると述べています。そのため微積分の課程を取っていなくても使えます。

短所

• 公開されている目次の情報が少ない。 出版社が2025年版について示しているのは章のタイトルだけで、第8版からの変更点は列挙されていません。版を選ぶ際は、実際の目次を比べるべきです。
• 証明は目的ではなく手段。 序文は、数学的推論を5つのテーマのひとつとして示しています。証明の書き方をもっと本格的に学びたい学生は、このコース一覧のEppの本のように、証明の書き方を軸にした教科書のほうが向いているかもしれません。
• 読者層が混在している。 本書は数学、コンピュータ科学、工学の読者を対象としているため、第7版の表では、アルゴリズム、ブール代数、計算のモデル化といった章は数学寄りの課程では任意とされています。一方、第5、6、9、10章には、どの課程でも必須とされる節が含まれています。

コースにおける位置づけ

Rosen は、証明の方法、アルゴリズム、整数論、数え上げ、確率、グラフ、計算のモデルを1冊で扱う、幅広いリファレンス型の教科書です。Epp の『Discrete Mathematics with Applications』は似た範囲を扱いますが、推論と証明の書き方を学ぶことを軸に組み立てられているので、論理や証明の書き方でより多くの助けが必要な学生に向いています。Oscar Levin の『Discrete Mathematics: An Open Introduction』は、数え上げ、数列、グラフ理論、論理を中心にした、探究型の無料の入門課程で、László Lovász、József Pelikán、Katalin Vesztergombi の『Discrete Mathematics: Elementary and Beyond』は、問題を軸にした短い入門書です。Graham、Knuth、Patashnik の『Concrete Mathematics』と van Lint、Wilson の『A Course in Combinatorics』は、その後に読むものです。前者はアルゴリズム解析のための和、漸化式、二項係数、母関数を、後者は大学院レベルの組合せ論を扱います。

本書の使い方

Rosen は、1～2学期の離散数学の課程を取る、コンピュータ科学、数学、工学系の1～2年次の学生に向いています。序文が求める前提は大学レベルの代数だけです。課程の教科書として使い、その後はリファレンスとして手元に置くのが最適です。

実際の進め方は次のとおりです。

• 中核： まず第1章と証明方法の節を学び、続いて第2章の基本構造、帰納法と再帰（第5章）、数え上げ（第6章）、グラフ（第10章）へと進みます。第7版の表では、第1、2、4、5、6、9、10章のほとんどの節が必須とされています。
• アルゴリズムと整数論（第3–4章）： 第7版の表は、第3章をコンピュータ科学向けの任意の内容、第4章は冒頭の節だけを必須としています。コンピュータ科学の課程では両方の章を通して学ぶことになるでしょう。
• 確率、高度な数え上げ、関係（第7–9章）： 第7版の表では、それぞれの章で必須とされるのは1～3節だけなので、短い課程ではそれらを、2学期の課程では残りも扱えます。
• 任意（第11–13章）： 第7版の表は、木については冒頭の節だけを必須とし、第12–13章（ブール代数、計算のモデル化）はコンピュータ科学向けの任意の内容としているので、そうした重点をもつ課程に向いています。

演習問題は継続的に使ってください。序文によれば、奇数番号の演習には解答または解法が付いており、章末の復習問題は、簡単な計算ではなく文章で十分に答えることを想定しています。