離散数学集合落合 秀也

情報の世界を「集合」で考える(1) IPアドレス• インターネットに接続される世界中のコンピュータに付与される住所（Address）• 216.58.220.164 – Google の、とあるコンピュータ• 133.243.3.34 – NICTの、とあるコンピュータ• 157.82.13.244 – 東大工学部の、とあるコンピュータ
IPアドレスはx.y.z.w ( x, y, z, w は 0～255の整数)の値(要素)で、世界中のコンピュータの住所を表す

IPアドレスの集合

0.0.0.0, … ,0.0.0.255,0.0.1.0, … ,0.0.1.255,…
255.255.255.0, … ,255.255.255.255

2

情報の世界を「集合」で考える(2) プログラムの命令• CPUに対する命令(アセンブリ言語)• MOV AX, 10 -- AXレジスタに10を入れる• ADD AX, DX -- AXレジスタとDXレジスタを足し合わせてその結果をAXレジスタに入れる• INC AX -- AXレジスタをインクリメント(+1)する

MOV, …
ADD, SUB, MUX, ..
INC, DEC, …
JMP, JNZ, …

個々の命令(要素)が（CPUの動作と共に）定義されているCPUには、チューリング完全な命令セット(集合)が用意され、これによって、我々は自由自在にプログラムを創造できる。
3

情報の世界を「集合」で考える(3) 色の表現• コンピュータによる色の表現 (R, G, B)• (255,0,0) -- ■赤• (0,255,0) -- ■緑• (0,0,255) -- ■青24ビット RGBカラー表現では、
R(赤), G(緑), B(青)の光の三原色において、各色の強さを 0～ 255 の数値で表す

色全体は「集合」をなす
4

「集合(Set)」とは• 考察対象の集まったもの• 考察対象の取りうる値の領域（空間）• 外延的表現 (extensional)• A={1, 2, 3}• 内延的表現 (intentional)• A={x | xは 1≦x ≦3を満たす整数}

5

集合の要素(element)• x∈A元(member)とも言う• xは集合Aの要素である• 要素xは集合Aに属する• 集合Aの要素xについて考える• 集合Aの要素をxとおく
否定はx∉A
もしくは• AがIPアドレス全体の集合の場合￢x∈Aと表記する
210.152.135.178 ∈ Aのように考えることが可能(*) ブラウザで http://210.152.135.178/ にアクセスしてみよ

6

普遍集合 (Universal Set)
• 考察対象となる要素全体（世界）の集合• IPアドレス全体の集合• CPU命令全体の集合• 色全体の集合

Uと表記することが多い

7

空集合 (Empty Set)
• 要素の存在しない集合• 「無」の空間• 要素の表現に必要な情報量は0ビット∅と表記するΦ や φ とも書く

∀x , x∉ Φ ⇔ ￢ (∃x, x ∈ Φ)
• Φは何個存在するか？
 唯一の存在である∀x: どんな x を取ってきても・・・
すべての x に対して・・・∃x: ・・・という x が存在する
何らかの x によって・・・・
8

部分集合x• A⊂BAB• 集合Aは集合Bに含まれる (contained)• 集合Aは、集合Bの部分集合 (subset)である• 集合Bは、集合Aの上位集合 (superset)である

A ⊂ B ⇔ ∀x ( x ∈ A → x ∈ B )• A=B （集合A と集合Bが等しい）⇔ A ⊂ B かつ A ⊃B

9

部分集合

IPアドレス配布の例• IPアドレス空間Uの切り出し＆配布は階層に行われている
IANA (Internet Assigned Numbers Authority)
U A
↓ U⊃A
APNIC(RIR: 地域インターネットレジストリ)
B↓ A⊃B
JPNIC(NIR: 国別インターネットレジストリ)↓ B⊃C指定事業者(LIR: ローカルインターネットレジストリ)↓ C⊃D
エンドユーザD: 203.178.135.0 ～ 203.178.135.127
参考資料： https://www.nic.ad.jp/ja/basics/terms/allocation-assignment.html

CD

10練習• Φ ⊂ Φ であることを示せ
解１

A ⊂ B ⇔ ∀x ( x ∈ A → x ∈ B )であるから∀x ( x ∈ Φ → x ∈ Φ ) ・・・ (*)
が言えればよい
定義より、∀x , x∉ Φなので、 どんなxに対しても、x∈Φが成り立つことは無い。よって、
x∈Φ→x∈Φは、どんなxに対しても成立する
つまり、(*)が成立する

解２
A=B ⇔ A ⊂ B かつ A ⊃Bである。また、
Φ=Φが言えるので、
Φ=Φ ⇒ Φ ⊂ Φかつ Φ⊃Φ
ゆえに、
Φ⊂Φ
である

11集合の演算• 和 (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)A∖B と表記されることもある(AマイナスBと読む)• 普遍集合 U について考察しているときの概念• Ac = U − A• 直積 (direct product, Cartesian product)• A × B = {(a, b) | a ∈ A, b ∈ B}
12

練習
• A={1,2,3,4}, B={3,4,5,6}, U={1,2,3, … } (正の整数)とする。このとき、以下を計算せよ
A∪B =A∩B=A−B=
Ac =•解A∪B = {1, 2, 3, 4, 5, 6}
A − B = {1, 2}

A ∩ B = {3, 4}
Ac = {5, 6, 7, …}
13

集合代数における双対性• 双対性, 双対原理 (principle of duality)• ある法則において ∪, ∩, U, Φ を ∩ ,∪, Φ, U に置き換えても成立すること• 例１： 分配の法則 (分配律)A ∪ ( B ∩ C) = ( A ∪ B ) ∩ ( A ∪ C ) は 常に成り立つ⇕ ・・・ 双対性
A ∩ ( B ∪ C) = ( A ∩ B ) ∪ ( A ∩ C ) も同様に常に成り立つ• 例２： 同一の法則 (同一律)A ∪ Φ = A は常に成り立つ⇕ ・・・ 双対性
A ∩ U = A も同様に常に成り立つ

14

集合代数の法則(どんなA, B, C に対しても以下が成立する)• べき等律 (Idempotent Laws)
1a. A∪A = A

1b. A∩A=A• 結合律 (Associative Laws)
2a. (A∪B)∪C= A∪(B∪C)

2b. (A∩B)∩C=A∩(B∩C)• 交換律 (Commutative Laws)
3a. A∪B= B∪A

3b. A∩B= B∩A• 分配律 (Distribution Laws)
4a. A∪(B∩C)=(A∪B)∩(A∪C)

4b. A∩(B∪C)=(A∩B)∪(A∩C)• 同一律 (Identity Laws)
5a. A∪Φ=A
6a. A∪U=U

5b. A∩U=A
6b. A∩Φ=Φ

15

集合代数の法則 ・・・ つづき(どんなA, Bに対しても以下が成立する)• 対合律 (Involution Law)
7. (Ac)c = A• 補元律 (Complement Laws)
8a. A∪Ac = U
9a. Uc = Φ

8b. A ∩ Ac = Φ
9b. Φc = U• ド・モルガンの法則 (DeMorgan’s Law)
10a. (A∪B)c= Ac∩Bc

10b. (A∩B)c= Ac∪Bc
16

集合の集合 ・・・ 類 (Class)• 集合Aの部分集合X, Y, Z, … を考察対象とすることがある• すると X, Y, Z, … を要素とする集合も考えられなくはない• 例: 色全体の集合U={(x,y,z) | 0≦x, y, z≦255 } に対し赤系の色= { (x,0,0) | 192≦x≦ 255 }
緑系の色= { (0,x,0) | 192≦x≦ 255 }青系の色= { (0,0,x) | 192≦x≦ 255 }のような分類が考えられ、
x=255
x=192
[ 赤系の色, 緑系の色, 青系の色 ]という集合(分類 = 類)を考察対象とすることがありえる17

類 (Class) の 他の例(1) 年齢別• 人々の年齢の集合Yを考える• 個人の年齢は21.1123… ∈ YのようにYの要素となる• 統計処理の分野では、年代別の類Y として
Y = [ 0代, 10代, 20代, 30代, 40代, 50代, … ]を考察対象とする（のように分類する）ことがある。
18

類 (Class) の 他の例(2) 地域• 緯度経度で表現される地点の集合 L を考える

• ある地点は、(35.21341… , 139.21312 … ) ∈ LのようにLの要素となる• 地点の集合を地域で分類し、
L = [ 文京区, 台東区, 豊島区, 千代田区, … ]を考察対象とすることがある
19

類 (Class) の 他の例(3) コンピュータでの数値表現（データ型）• 実数全体の集合 R を考える
• ある値は2118.5 ∈ RのようにRの要素となる• Rは無限に大きく、コンピュータではすべてを表現できない。
• そのため、Rの一部を表現する、データ型T の概念を作り出している
T = [ int, unsinged int, long, unsinged long, float, double ]それぞれのデータ型は、Rの部分集合を表現可能。
T はRの部分集合の類と言える 例) 2118.5 ∈ float ⊂ R20

類 (Class) の 他の例(4) ドメイン名• ドメイン名全体の集合 Dを考える• 各ドメインは、www.u-tokyo.ac.jp ∈ DのようにDの要素となる• ドメインの分類として、
D = [ *.ac.jp, *.co.jp, *.ne.jp, *.go.jp, *.or.jp, … ]を考察対象とすることがある。
ここで、* は任意の意味。つまり、*.ac.jp はDの部分集合となる
21

類 (Class) の 他の例(5) IPアドレスのクラス• IPアドレス全体の集合を考える• この場合、
2.*.*.* = {2.x.y.z | 0≦ x, y, z ≦ 255}
はIPアドレス全体の部分集合となる。
• IPの世界では、以下で定義されるクラスA, クラスB, クラスC
A = [ 0.*.*.*, 1.*.*.*, 2.*.*.*, … , 255.*.*.*]
B = [ 0.0.*.*, 0.1.*.*, 0.2.*.*, … , 255.255.*.* ]C = [ 0.0.0.*, 0.0.1.*, 0.0.2.*, … , 255.255.255.* ]を考察対象とすることがある。
(*) 昔は、この方法でIPアドレスを分割し、各組織に配布していた
22

練習• 以下のファイルの集合があるものとする。
{ tennis.doc, soccer.doc, baseball.doc,tennis_shot.jpg, soccer_shoot.jpg, baseball_hit.jpg }この集合の類( = この場合、ディレクトリに相当するもの)を作ってみよ解1:
tennis = {tennis.doc, tennis_shot.jpg }, soccer = {soccer.doc, soccer_shoot.jpg },baseball = { baseball.doc, baseball_hit.jpg }という部分集合を作り sport = [ tennis, soccer, baseball ] という類とする
解2:
doc = { tennis.doc, soccer.doc, baseball.doc }jpg = {tennis_shot.jpg, soccer_shoot.jpg, baseball_hit.jpg }という部分集合を作り type = [ doc, jpg ] という類とする
23べき集合 (Power Set)
• 与えられた集合Aに対して、Aのすべての部分集合からなる類を、べき集合と呼び、P (A)と表す• 要素数は 2 の n(A)乗、つまり、n(P (A)) = 2n(A) (*) ここで n(A)はAの要素数を表すである。
• そのため、Aのべき集合のことを 2A と表すこともある24

練習• A = {1, 2, 3} の、べき集合 P (A) を外延的に表現
してみよ
• 解：
P (A) = [ {} , {1}, {2}, {3},{1, 2}, {1, 3}, {2, 3}, {1, 2, 3} ]注: Φ = {} は、 Aの部分集合である： i.e., Φ ⊂ A
また、要素数は、確かに 23 となっている
25

次回(4月15日)： 関係 と 関数y,z ∈テレビ

東京…∈住所意味論(Ontology)

168∈身長x∈人

090-xxxx-yyyy∈電話番号w∈性格
57.3∈体重

日本語, 英語∈言語
重要なデータ

復元されたデータ

a b c

a b c

エンコード
a  a’

デコード[a’]  aa’c’[ a’ ][ b’ ]

揺らぎ[ a’ ][ c’ ]b’

送信するデータ[ c’ ][ b’ ]

外乱

受信したデータ

前方誤り訂正(FEC: Forward Error Correction)
26