01 / 読書ガイド
読書ガイド
引用
Epp, S. S. (2020). Discrete Mathematics with Applications (5th ed.). Cengage Learning.
章の要約
本書は12章と付録で構成されています。Cengage による学生用解答集の説明には、一部の演習問題の解答が付録Bにあると記されています。最初の4章で言語、論理、証明技法を築き、第5–8章で帰納法、集合、関数、関係を扱い、第9–12章で数え上げと確率、グラフと木、アルゴリズムの効率、オートマトンを扱います。Cengage の第5版の説明によれば、文字列とグラフは第1章で導入されたうえで全体を通して応用と結びつけて扱われ、握手補題は第12章から第4章に移されました。
第1章：Speaking Mathematically（数学を語る）
冒頭の章は、変数、集合の言語、関係と関数の言語、グラフの言語という4つの節を通して、以降の章で使う語彙を教えます。
第2–3章：The Logic of Compound Statements（複合命題の論理）／The Logic of Quantified Statements（量化された命題の論理）
第2章は論理形式と論理的同値、条件文、妥当な論証と妥当でない論証を扱い、2つの応用、すなわちデジタル論理回路と、数の表現法および加算回路で締めくくります。第3章は量化子について同じ構成を繰り返します。述語と量化された命題（2つの節）、複数の量化子をもつ命題、量化された命題を含む論証です。
第4章：Elementary Number Theory and Methods of Proof（初等整数論と証明の方法）
この章は、本書の証明の扱いの中心です。直接証明と反例についての6つの節では、導入、書き方の助言、有理数、約数と倍数、場合分けと商と余りの定理、床関数と天井関数を扱います。間接的な論証についての2つの節では、背理法と対偶、そして2つの有名な定理を扱い、章は応用、すなわち握手補題とアルゴリズムで終わります。
第5章：Sequences, Mathematical Induction, and Recursion（数列、数学的帰納法、再帰）
第5章は数列から始まり、公式を証明するための帰納法、帰納法の応用、強い帰納法と整列原理の節が続き、アルゴリズムの正当性が扱われます。後半は再帰に移ります。数列の再帰的定義、反復による漸化式の解法、定数係数の2階線形斉次漸化式、一般的な再帰的定義と構造的帰納法です。
第6–8章：Set Theory（集合論）／Properties of Functions（関数の性質）／Properties of Relations（関係の性質）
第6章は要素法による証明、集合の性質、反証と代数的証明を扱い、最後の節ではブール代数、ラッセルのパラドックス、停止問題を取り上げます。第7章は一般の集合上の関数、単射・全射・逆関数、合成、そして計算可能性への応用を含む濃度を扱います。第8章は集合上の関係、反射性・対称性・推移性、同値関係、暗号への応用を含む合同算術、半順序関係を扱います。
第9章：Counting and Probability（数え上げと確率）
第9章は、導入から、可能性の木と乗法の規則、加法の規則、鳩の巣原理、組合せ、重複を許す r 組合せ、パスカルの公式と二項定理、確率の公理と期待値、そして条件付き確率、ベイズの公式、独立事象へと進みます。
第10–12章：Theory of Graphs and Trees（グラフと木の理論）／Analysis of Algorithm Efficiency（アルゴリズムの効率の解析）／Regular Expressions and Finite-State Automata（正規表現と有限状態オートマトン）
第10章は、トレイル、パス、回路、グラフの行列表現、同型、木と根付き木、最短経路アルゴリズムを含む全域木を扱います。第11章は、実数値関数とそのグラフ、O 記法・Ω 記法・Θ 記法、指数関数と対数関数、そしてアルゴリズムの効率を解析する2つの応用を導入します。第12章は形式言語と正規表現、有限状態オートマトン、有限状態オートマトンの簡約を扱います。
主要概念
第1–4章：言語、論理、証明
- 論理形式と論理的同値：第2章で複合命題を分析する基礎。
- 量化された命題：第3章での、述語、複数の量化子、量化子を含む論証の扱い。
- 直接証明、反例、間接的論証：第4章が整数論を使って教える証明方法。
- 商と余りの定理：4.5節で導入される除法の結果。
第5–8章：帰納法、集合、関数、関係
- 数学的帰納法と強い帰納法：5.2–5.4節の証明技法。5.9節には構造的帰納法があります。
- 漸化式：反復による解法（5.7）と、2階線形斉次の場合の一般的な解法（5.8）。
- 要素法による証明：第6章で集合の性質を証明する方法。
- 同値関係と半順序：第8章の関係の種類。
第9–12章：数え上げ、グラフ、アルゴリズム、オートマトン
- 鳩の巣原理、組合せ、二項定理：第9章の数え上げの道具。
- ベイズの公式と期待値：第9章末の確率の話題。
- ビッグオー、オメガ、シータ記法：第11章の記法。
- 有限状態オートマトン：第12章の機械。
批判的分析
長所
- 証明を前提とせず教える。 第1章は数学の言語から、第2–3章は論理から始まり、第4章は直接証明、書き方の助言、間接的な論証を10の節にわたって展開します。Cengage の説明は、本書を「わかりやすく正確なアプローチで知られる」ものとし、数学的な考え方の根底にある推論を重視しています。第5版では、量化子の使い方、証明という概念、証明の書き方の助言、集合論の証明の節が改訂されました。
- 2段階構成の例題。 Cengage の特長リストによれば、本書には問題と解答の形式の例題が500を超えてあり、証明の解答は2段階、すなわち証明にどう取り組むかの議論と、その解答の要約によって展開されます。学生は速いペースかゆっくりしたペースかを選べます。
- 豊富な演習。 出版社は2,500を超える演習を挙げており、応用問題や、オンラインシステムで証明の完成を導く新しい形式の演習も含まれます。
- コンピュータ科学の応用。 Cengage はコンピュータ科学の応用が多数あると述べており、目次もそれを裏づけています。デジタル論理回路と二進数の加算（2.4–2.5）、アルゴリズムの正当性（5.5）、合同算術を使った暗号（8.4）、アルゴリズムの効率の解析（11.3、11.5）、オートマトン（第12章）です。第5版の新しい内容には、二分探索木、暗号学的ハッシュ関数、メッセージ認証があります。
短所
- 数え上げとグラフは後半。 数え上げ、確率、グラフが現れるのは第9–10章になってからで（グラフの言語は第1章で簡単に導入されます）、組合せ論やグラフ理論を中心とする課程では先に飛ばして読む必要があります。出版社は、必須の内容と任意の内容を組み合わせられる構成だと述べています。
- 整数論や暗号の独立した章がない。 整数論は第4章で証明の題材として、暗号は8.4節で合同算術の応用として登場します。より詳しい扱いを求める読者は別の資料が必要です。
- 分量。 アジア版は984ページとされており、最初の課程には多すぎます。教員は章を選ぶ必要があり、構成はそれができるよう意図されています。
コースにおける位置づけ
Epp は、このコース一覧で証明を中心に据えた教科書です。Rosen の『Discrete Mathematics and Its Applications』は、より幅広い話題をリファレンス的な形式で扱い、2冊目として、あるいはすでに無理なく論理的に考えられる学生の代替として適しています。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』は後の学習用です。前者はアルゴリズム解析のための和、漸化式、母関数を、後者は大学院レベルの組合せ論を扱います。
本書の使い方
Epp は、コンピュータ科学で使う離散構造に触れながら、数学的な議論の読み方と書き方を学ぶ必要のある学生向けです。前提は学校レベルの代数と記号に慣れていることで、微積分は不要です。
実際の進め方は次のとおりです。
- 中核（第1–5章）： 順に読みます。証明の習慣が形作られるのは第2–4章で、証明を書く課題の前に4.2節（書き方の助言）を読む価値があります。
- 構造（第6–8章）： 集合、関数、関係。これらは以降のほぼすべての語彙を与えます。
- 数え上げとグラフ（第9–10章）： 本書の組合せ論の中核。
- 任意（第11–12章）： アルゴリズムの解析とオートマトンは、コンピュータ科学の科目に進む学生に向いています。
各節の演習問題に取り組み、自分の証明の構成の手本として例題を使ってください。