markdown
離散数学の入口md f5fa855
lecture/information/discrete-math/離散数学の入口-講義.n.md
Download as PDF
離散数学の入口
informationdiscrete-mathundergraduatelecture
導入
この講義で最重要なのは、情報工学では連続的な量よりも、有限または可算的な対象をどう整理し、どう論理的に扱うかが基礎になることである。
アルゴリズムやデータ構造を学ぶとき、いきなり実装だけを見ると、「なぜこの場合分けでよいのか」「なぜこの手順がいつか終わるのか」が曖昧になりやすい。その土台になるのが、集合、論理、写像、帰納法である。
用語と定義
集合 とは、対象をひとまとまりとして集めたものである。
命題 とは、真か偽かを判定できる文である。
写像 とは、ある集合の要素を、別の集合の要素へ対応させる規則である。
数学的帰納法 とは、自然数についての主張を順番に確かめる証明の方法である。
方針
まず情報をどう分類するかを集合で見る。つぎに、「もし A ならば B」といった条件を論理で整理する。そのあと、手順が正しいことを帰納法で支える見方へつなげる。
直感的な説明
配列に整数が入っているとして、「偶数だけを集める」「条件を満たすものだけを残す」という操作は、集合を切り分けていると見なせる。また、「すべての要素に対してこの性質が成り立つか」を考えるときには、論理の記号が役に立つ。
厳密な説明
1. 集合
A \subset B
は、集合 A のすべての要素が B に含まれることを意味する。
2. 論理
「A ならば B」は
A \Rightarrow B
と書く。アルゴリズムの条件分岐では、この形を何度も使っている。
3. 帰納法
すべての自然数 n に対して主張 P(n) を示したいとき、まず P(1) を示し、つぎに P(k) を仮定して P(k+1) を示せば、すべての n に対して成り立つ。
見分け方
- 要素の集まりを整理したいなら、まず集合で考える。
- 条件のつながりを追いたいなら、命題と論理で書きなおす。
- 手順の正しさや式の一般形を示したいなら、帰納法を疑う。
最終形
\boxed{A \subset B}
\boxed{A \Rightarrow B}
\boxed{P(1)\ \text{と}\ P(k)\Rightarrow P(k+1)\ \text{で帰納法}}
一言でいうと
- 離散数学は、情報をどう整理し、手順の正しさをどう支えるかを学ぶ土台である。