ディジタル回路

離散数学
1. 集合
五島 正裕
離散数学
集合
 現代数学すべての基本
 自然数も集合によって定義
離散数学
集合
 集合:
 「明確に定義された対象の集まり」
 要素 (element)
x ∈ A
 表現
 外延的表現 (extensional)

A = {1, 2, 3}
 内包的表現 (intentional)

A = {x | xは1≦x≦3を満たす整数}
離散数学
 空集合 (empty set)
 φ
 包含関係
 A ⊂ B, B ⊃ A
離散数学
集合の演算
 和集合 (union)
 A ∪ B = {x | x ∈ Aまたはx ∈ B}
 積集合 (intersection)
 A ∩ B = {x | x ∈ Aかつx ∈ B}
 差集合 (difference)
 A - B = {x | x ∈ Aかつx \∈ B}
 補集合 (complement)
 ある集合Uの部分集合だけを問題とするとき
 Aの上に横棒 = A^c = U - A
 直積 (direct product, Cartesian product)
 A × B = {(a,b) | a ∈ A, b ∈ B}
離散数学
濃度
 濃度 (potency, power)
 集合の大きさ, 有限集合の場合は要素数
 |A|
離散数学
巾(べき)集合
 巾集合 (power set)
 集合 A の部分集合すべての集合
 2A
 A = {a, b, c} なら

2A = {{}, {a}, {b}, {c}, {a, b}, {b, c}, {c, a}, {a, b, c}}
 2A
 A → {0,1} への写像全体の集合と同一視できる
 | 2A | = 2|A|
離散数学
代表的な無限集合の記法
 自然数:
N
 整
数:
Z
 有理数:
Q
 実
R
数:
離散数学
無限集合の濃度
 無限集合の濃度の比較
 全単射写像が存在すれば |A| = |B|
 AからBへの単射が存在すれば |A| ≦ |B|
 全単射写像の作り方
 システマティックな数え上げの方法
離散数学
無限ホテル by ヒルベルト
 無限の部屋があるホテルがあり,満室だった.
突然の客が来て,どうしても泊めて欲しいと言う.
 1号室の客は2号室へ,2号室の客は3号室へ,… ,と移ってもらうと,
1号室が空く.
離散数学
無限ホテル by ヒルベルト
 無限の部屋があるホテルがあり,満室だった.
突然 無限人の客が来て,どうしても泊めて欲しいと言う.
 1号室の客は2号室へ,2号室の客は4号室へ,… ,n 号室の客は 2n 号室
へと移ってもらうと,無限の部屋が空く.
 自然数の濃度 = 奇数(偶数)の濃度!
離散数学
自然数と整数の濃度
 自然数 ⇔ 整数
0 1 2 3 4 5 ...
0 1 -1 2 -2 3 ...
離散数学
有理数の濃度
 自然数 → 有理数の単射は簡単
 有理数 → 自然数の単射は
1/1 1/2 1/3 1/4 ...
2/1 2/2 2/3 2/4 ...
3/1 3/2 3/3 3/4 ...
...
分子+分母をしだいに大きく
離散数学
実数の濃度
 自然数と実数の濃度は違う
 「対角線論法」
 正の実数全体 → (0,1) の実数
 シグモイド関数(ロジスティック関数)

y = 1/(1 + exp(-x))
離散数学
対角線論法 by カントール
1: α1 = 0. a11 a12 a13 …
2: α2 = 0. a21 a22 a23 …
3: α3 = 0. a31 a32 a33 …
n: αn = 0. an1 an2 an3 … ann …
β = 0. b1 b2 b3 … bn …
bi = 7 (0 ≤ ai ≤ 4)
2 (5 ≤ ai ≤ 9)
離散数学
‫א‬
 一般に |A| < |2A|
 自然数 の濃度:
実

可算無限: ‫א‬0
数 の濃度: 非可算無限: ‫א‬
‫א‬
 アレフ
 ヘブライ語のアルファ
離散数学
どんな仕様のプログラムでも書けるか?
 あらゆるプログラム
 プログラム: 文字の有限長の並び
 文字コードでエンコードすれば有限長のビット列
→ 自然数と同じ濃度
 あらゆる仕様とは? たとえば:
 入力: 自然数
 出力: 0 または 1
というプログラムの仕様 (入出力の関係) は:
 入力: 0 1 2 3 4 5 ...
 出力: 0 1 1 0 1 0 ...
という無限長の0/1列で表現できる.
離散数学
どんな仕様のプログラムでも書けるか?
 プログラムの実行結果の一覧表
0:
01101011...
1:
11011001...
2:
00110110...
...
対角線論法により, ここに出現しない仕様があるはず.
 入力の自然数には上限 (32b とか)があるが?
 入力を「任意長文字列」→「自然数」とすれば同じ
離散数学
Russel のパラドクス
 「集合の集合」も考えられる
 「自分自身を要素として持つような集合」

例: あらゆる集合の集合
 「自分自身を要素として持たない集合すべての集合」S
 S 自身は S の要素か?

Yes → S の定義に違反

No → S の定義から S は S の要素であるべき
離散数学
Russel のパラドクス
 ある村にはただ一人の理髪師がいて,自分で自分のヒゲを剃らない村人
全員のヒゲを剃るとする.この理髪師は,自分のヒゲを剃るか?
 ある図書館の図書目録のうちで,自分自身を載せていないものすべての
目録を作る.この目録自体は,この目録に載せるべき?
 自分の市に住んでいない市長のみを集めて「市長市」を作る.「市長
市」の市長には誰がなるか?
離散数学
素朴集合論の破綻
 素朴集合論 → 公理的集合論