1 基礎概念
離散数学は、連続量ではなく、有限個または可算個の対象を中心に扱う数学分野である。対象は抽象的だが、計算や情報の扱いと相性がよく、現代の理論計算機科学に深く結びついている。
1.1 離散数学の対象
主な対象には、整数、集合、命題、関係、関数、グラフ、列、部分構造などがある。いずれも「個々の要素を区別できる」点に特徴があり、量の変化を滑らかに追う解析学とは異なる見方を与える。
1.2 離散量と連続量の違い
離散量は飛び飛びの値をとり、途中の値を基本的に含まない。これに対して連続量は区間全体を埋めるように変化する。たとえば、個数は離散的であり、長さや温度は連続的に扱われることが多い。
1.3 離散数学の役割
この分野は、計算の手順、情報の表現、構造の比較を明確にするための基盤を提供する。証明の形式化や数え上げの技法は、アルゴリズム、暗号、データ構造、ネットワーク解析などの理解に直結する。
2 論理と証明
論理は、命題の真偽を扱い、推論の妥当性を検査するための道具である。証明は、結論が前提から正しく導かれることを示す過程であり、離散数学全体の言語として機能する。
2.1 命題論理
命題論理では、真または偽のどちらかをとる文を基本単位とする。命題同士を論理結合子で結び、複合的な主張の意味や真偽を調べる。
2.1.1 論理結合子
代表的な結合子には、「かつ」「または」「ならば」「でない」がある。これらを用いることで、複雑な条件を簡潔に表現できる。推論規則の多くは、結合子の性質に依存する。
2.1.2 真理値表
真理値表は、命題変数に対する各組合せについて式の真偽を一覧化した表である。式の同値性や恒真性、矛盾性を確認するのに有効で、論理式の整理にも役立つ。
2.2 述語論理
述語論理は、対象とその性質、対象間の関係をより細かく表現する。命題論理より表現力が高く、数学的定義や証明の記述に広く使われる。
2.2.1 量化記号
量化記号には、すべての対象について成り立つことを表すものと、ある対象が存在することを表すものがある。これにより、一般性の高い主張と存在主張を明確に区別できる。
2.2.2 述語と変数
述語は、変数に値を与えたときに真偽が定まる性質や関係を表す。変数は対象を代表し、代入によって具体的な命題へと変わる。
2.3 証明技法
証明技法は、主張を成立させるための典型的な論理手順である。問題の構造に応じて使い分けることで、証明は簡潔かつ見通しよくなる。
2.3.1 直接証明
直接証明は、仮定から出発して論理を順に進め、結論に到達する方法である。定義や既知の命題をそのまま使えるため、最も基本的な形式といえる。
2.3.2 対偶証明
対偶証明では、ある命題の対偶が真であることを示す。元の命題と対偶は論理的に同値なので、直接扱いにくい場合でも有効な場合が多い。
2.3.3 背理法
背理法は、結論が偽であると仮定して矛盾を導く手法である。仮定の不整合を示すことで、結論の正しさを確定する。
2.3.4 数学的帰納法
数学的帰納法は、自然数について成り立つ主張を証明する代表的手法である。最初の段階を示し、次にある段階が成り立つなら次も成り立つことを証明して、全体へ拡張する。
3 集合と関係
集合は、対象をひとまとめにした基本概念であり、関係は要素どうしの結びつきを表す。関数は、その関係の中でも特に対応が一意に決まる重要な場合である。
3.1 集合の基本
集合は、要素の集まりを厳密に扱うための枠組みである。集合論の考え方は、離散数学のほぼすべての領域に現れる。
3.1.1 集合の表し方
集合は、要素を列挙して示す方法と、条件を述べて定義する方法がある。前者は具体的で、後者は一般的な性質を表すのに向いている。
3.1.2 部分集合と冪集合
部分集合は、ある集合の要素だけからなる集まりである。冪集合は、その集合のすべての部分集合を集めたもので、組合せ的な構造を持つ。
3.2 関係
関係は、2つの対象の間に成立する対応や比較を記述する。順序付けや分類、同一視の考え方を整理するうえで重要である。
3.2.1 二項関係
二項関係は、2つの要素の組に対して成り立つ性質として定義される。たとえば、「等しい」「小さい」「隣接する」といった概念がこれにあたる。
3.2.2 同値関係
同値関係は、反射性、対称性、推移性を満たす関係である。対象を同じ種類としてまとめる際に用いられ、剰余類や分類の基礎となる。
3.2.3 順序関係
順序関係は、要素の大小や先後を表す。全ての要素が比較可能な場合もあれば、比較できない組がある場合もあり、構造の階層を示すのに適している。
3.3 関数
関数は、各入力に対してただ1つの出力を対応させる写像である。数学だけでなく、計算やアルゴリズムの記述にも不可欠である。
3.3.1 単射・全射・全単射
単射は異なる入力が異なる出力に写る性質、全射はすべての出力先が少なくとも1つの入力を持つ性質、全単射はその両方を満たす性質である。全単射は対応の1対1性を保証する。
3.3.2 合成関数
合成関数は、ある関数の出力を別の関数の入力として用いる操作である。処理の連続や手順の積み重ねを表現でき、関数の構造を理解するうえで基本的である。
4 組合せ論
組合せ論は、対象の選び方や並べ方、分配の仕方を数える学問である。離散的な配置の総数を求めることで、確率やアルゴリズム解析にも接続する。
4.1 数え上げの基本原理
数え上げでは、問題を小さな部分に分けて総数を求める。基本原理を使うと、複雑な場合でも体系的に計算できる。
4.1.1 和の法則
和の法則は、互いに排反な選択肢が複数あるとき、それぞれの数を足して全体を求める方法である。場合分けを整理する際の出発点となる。
4.1.2 積の法則
積の法則は、ある段階の選択が次の段階に独立して続くとき、各段階の通り数を掛け合わせる考え方である。順序のある選択に特に有効である。
4.2 順列と組合せ
順列は並べ方、組合せは選び方を意味する。順序を区別するかどうかで数え方が変わるため、区別の有無が重要になる。
4.2.1 重複を許す場合
同じ要素を複数回選べると、通り数は条件に応じて増える。並べ方や選び方の制約を正確に確認する必要がある。
4.2.2 重複を許さない場合
重複を認めない場合、各要素は一度しか使えない。典型的な順列・組合せの公式は、この設定で導かれることが多い。
4.3 包除原理
包除原理は、複数の条件が重なって数えられる重複分を補正する手法である。単純な加算では過大評価になる場合に、正確な総数を与える。
4.4 生成関数
生成関数は、数列を形式的なべき級数として表す道具である。数え上げ問題を代数的に扱えるため、再帰関係や組合せ構造の解析に役立つ。
5 グラフ理論
グラフ理論は、点とそれらを結ぶ線で構成される構造を研究する分野である。関係の可視化に優れ、ネットワークや経路の分析に広く利用される。
5.1 グラフの基本概念
グラフは、要素間の結びつきを抽象化したモデルである。構造を単純な図式に落とし込むことで、複雑な関係を扱いやすくする。
5.1.1 頂点と辺
頂点は対象そのものを表し、辺は頂点同士の関係を示す。これらの組み合わせによって、さまざまな構造が表現される。
5.1.2 有向グラフと無向グラフ
有向グラフでは辺に向きがあり、関係の方向を示す。無向グラフでは向きがなく、対等な結びつきを表す。
5.2 代表的なグラフの性質
グラフの性質は、構造の強さや移動のしやすさを表す。これらを調べることで、図形的な見方から論理的な分析へ進める。
5.2.1 連結性
連結性は、任意の2点の間に道筋が存在するかどうかを表す。分断の有無を判断する基本概念である。
5.2.2 距離と最短路
距離は、2点間を結ぶ経路の長さを測る尺度である。最短路は、その中で最も短い経路を指し、効率的な移動や通信の評価に用いられる。
5.2.3 木
木は、閉路を持たない連結グラフである。構造が単純で、階層的な表現や探索の基礎として重要である。
5.3 グラフの応用
グラフは、現実の関係を抽象化する共通言語として働く。問題を頂点と辺の形式に置き換えることで、解析や計算が容易になる。
5.3.1 ネットワーク表現
ネットワーク表現では、地点、接続、流れなどをグラフとして記述する。通信網、交通網、依存関係のモデル化に向く。
5.3.2 経路探索
経路探索は、ある点から別の点へ到達する道を見つける問題である。最短経路や到達可能性の判定は、実用上きわめて重要である。
6 整数論
整数論は、整数の性質を研究する分野であり、離散数学の中核をなす。割り切れ方や合同関係を通じて、数の構造を深く理解する。
6.1 約数と倍数
約数はある整数を割り切る数、倍数はある整数の整数倍で得られる数である。これらの関係は、因数分解や整除性の議論の基盤となる。
6.2 素数
素数は、1と自分自身以外に正の約数を持たない整数である。整数の基本構成要素として重要で、分解の理論において中心的な位置を占める。
6.3 合同式
合同式は、2つの整数がある数で割った余りが等しいことを表す。周期性や繰り返し構造を扱いやすくし、計算の簡略化にも使われる。
6.4 ユークリッドの互除法
ユークリッドの互除法は、2つの整数の最大公約数を効率よく求める手続きである。割り算を繰り返す単純な方法でありながら、高い実用性を持つ。
7 再帰と漸化式
再帰は、対象を同種のより小さな部分として定義する考え方である。漸化式は、数列の各項を前の項から表す式で、離散的な成長や変化を記述する。
7.1 再帰的定義
再帰的定義では、初期の場合を与えたうえで、後続の対象を前の対象から定める。構造が自己相似的なときに特に自然な表現となる。
7.2 漸化式の作成
漸化式を作るには、問題の状態を段階的に分け、現在の値を過去の値で表す。数え上げやアルゴリズムの解析で頻繁に現れる方法である。
7.3 漸化式の解法
漸化式の解法には、式の形に応じた複数の手段がある。代表的な手法を使い分けることで、一般項や挙動を求めやすくなる。
7.3.1 特性方程式
特性方程式は、線形漸化式を代数的に扱うための補助手段である。解の候補を方程式として整理することで、一般解を導く。
7.3.2 母関数
母関数は、数列を形式的級数として表し、その代数操作から情報を引き出す方法である。漸化式の解や係数の構造を調べるのに有効である。
8 論理回路と計算機科学への応用
離散数学は、論理回路や計算理論の基礎として直接応用される。命題の真偽、状態の遷移、計算の効率などを形式的に扱える点が大きい。
8.1 ブール代数
ブール代数は、真偽値に対する代数体系であり、論理演算を計算規則として扱う。回路設計や論理式の簡約に広く用いられる。
8.2 論理回路の設計
論理回路は、入力に応じて出力を決める電気回路である。ブール代数を用いて機能を記述し、必要な構成を整理することで、効率的な設計が可能になる。
8.3 オートマトンとの関係
オートマトンは、有限個の状態を持つ計算モデルである。離散的な状態遷移を通して言語や入力列を処理し、形式言語理論の基礎を成す。
8.4 計算量の基礎
計算量は、問題を解くために必要な時間や記憶の大きさを評価する概念である。離散数学の道具は、アルゴリズムの効率や限界を見極める際に欠かせない。