離散数学

関係 と 関数落合 秀也

前回の復習： 集合• キーワード
集合, 要素, 部分集合, 普遍集合, 空集合, 集合の演算, 双対性, 集合代数の法則, 集合の集合 (=類), べき集合

• 記号{…} ,∈, ⊂, ⊃, =, U, Φ, ∪, ∩, －, ×,[…], 2A2

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射
3

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射
4

2項関係• 集合Aから集合Bへの2項関係 R は、直積A×Bの部分集合
R ⊂ A×B• (x, y) ∈ Rのとき、xとyはR-関係(relation)にあるといい
xRyと表現する• 以下、“関係”とは特に断りが無い限り、2項関係のことを指すものとする
5

例1:• A = {1, 2, 3}, B = {a, b, c}とすると、• A×B = { (1, a), (1, b), (1, c),(2, a), (2, b), (2, c),(3, a), (3, b), (3, c) }である。
ここで、R = { (1, a), (2, b), (3, b), (3, c) }は、AからBへの関係である。
6

例2:• 色の集合A = {赤, 黄}, モノの集合 B = {リンゴ, ミカン} を考察しているものとする。
• いま、目の前に、(1) 赤いリンゴ, (2) 黄色いリンゴ,(3) 黄色いミカン がある。
• それらの色とモノの関係 Rは、
赤Rリンゴ

黄Rリンゴ

黄Rミカンであり、
R = { (赤, リンゴ), (黄,リンゴ), (黄, ミカン)}である。
7

関係の表現方法１：
座標図 (Coordinate Diagram)
A = {1, 2, 3}, B = {a, b, c}, R = { (1, a), (2, b), (3, b), (3, c) }c

(3, c)ba(3, b)(2, b)(1, a)

1238

関係の表現方法2：
関係Rの行列 (Matrix of the Relation)
A = {1, 2, 3}, B = {a, b, c}, R = { (1, a), (2, b), (3, b), (3, c) }abc1100201030119関係の表現方法3：
矢線図 (Arrow Diagram)
A={1, 2, 3}, B={a, b, c}, R={ (1, a), (2, b), (3, b), (3, c) }1a2b3cAR

B

10

練習• 集合A={ 猫, トンボ, ハエトリグサ, 杉, 椅子} から、集合B={ 動物, 植物, 生物 }への関係Rを(常識的に)定義し、矢線図で表現せよ
R={ (猫, 動物), (猫, 生物), (トンボ, 動物), (トンボ, 生物),(ハエトリグサ, 植物), (ハエトリグサ, 生物), (杉, 植物), (杉, 生物) }
動物

猫トンボ

植物

ハエトリグサ杉椅子A生物RB11情報分野での応用:
Domain Name System (DNS)• A: ドメイン名の集合, B: IPアドレスの集合
R = { (www.u-tokyo.ac.jp, 210.152.135.178),(www.t.u-tokyo.ac.jp, 133.11.100.186),(www.i.u-tokyo.ac.jp, 133.11.232.67)}

は、ドメイン名からIPアドレスへの関係を定義する…
www.u-tokyo.ac.jp
www.t.u-tokyo.ac.jp
www.i.u-tokyo.ac.jp…

A…
210.152.135.178
133.11.100.186

R

133.11.232.67
…

B

12

情報分野での応用：
Big Dataの管理・解析• A: 人の集合, B: 地点の集合• スマホからサーバに報告された (人, 地点) の集合 R

ab
…

AR
B
13

考察
• 関係Rは、単一の集合の枠を超えて、異なる世界(異なる考察対象)を結びつけている
A: ドメイン名の集合 (e.g., www.u-tokyo.ac.jp ∈ A)
B: IPアドレス全体の集合 (e.g., 210.152.135.178 ∈ B )www.u-tokyo.ac.jpR210.152.135.178• 任意の集合に対して、何らかの関係を定義可能• R ⊂ A×B
• AかBがΦならば R=Φとする関係を作ればよい• 関係が、意味を生み出す（のではないか？）14意味とは何か：
DNSの例• ユーザが、ブラウザ上に、www.u-tokyo.ac.jpと入力する• しかし、コンピュータは、IPアドレスで通信の宛先を指定しなければサーバとは通信ができない。
• 「www.u-tokyo.ac.jp とは 210.152.135.178である」という解釈が必要• この解釈を行うための(関係)定義が、DNSによって与えられている

A

www.u-tokyo.ac.jp
www.t.u-tokyo.ac.jp
www.i.u-tokyo.ac.jp

R210.152.135.178
133.11.100.186
133.11.232.67「関係の定義 (= 意味づけを与えている)」「関係の利用 (= 意味の解釈を行っている)」

B15

意味とは何か：
オントロジー (Ontology) 哲学• 様々な集合の要素の間に関係を定義していくy,z ∈テレビ

東京…∈住所168∈身長x∈人090-xxxx-yyyy∈電話番号w∈性格57.3∈体重日本語, 英語∈言語• 定義を上手に作って、利用できるようにすれば、推論を展開できるのではないか・・・• xは、○○に住んでいて、 ××の料理が好きだから、△△のレストランを、日本語で紹介してあげると喜ぶかもしれない• 「意識」も、このようになっている、と考える人もいる 16→ 参照：NHKスペシャル 超常現象―科学者たちの挑戦意味とは何か：
5V系のデジタル回路• 出力系• 出力信号 = {0, 1}• 出力電位 = {x | 0≦ x ≦5}• 関係 ={ (0,0), (1,5) }100V5出力V5

出力信号“1”なら5Vを出します、という意味

• 入力系

入力

出力電位10• 入力電位 = {x | 0≦ x ≦5}0• 入力信号 = {0, 1}
入力信号
入力電位
• 関係
17= {(x,0), (y,1) | 0≦ x ≦2.5, 2.5 ＜ y ≦5}
入力電位が 2.5V～5Vなら、“1”と捉えます、という意味

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射
18

単一集合上の関係• 集合Aから集合Aへの関係R⊂A×Aを考えるときRは、A上の関係であるという。

•例• A を 整数の集合とする• x ∈ Aから、x+1 というAの要素への関係をRとする• この場合 R = { (x, x+1) | x∈ A} ⊂ A×Aであり、RはA上の関係である、という。

19

単一集合上の関係:
有向グラフ(Directed Graph)での表現
単一集合上の関係は、有向グラフで表現することもある

R={ (1,2), (2,2), (2,4), (3,4), (4,1), (4,3) }の例
123

4
20

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射
21相等性 (equality)=の意味について考える• Aを任意の集合とする。このとき、• A上の相等性の関係{ (a, a) | a ∈ A}
を考えることができる。
• この関係のことを “ = ” で表す123422

全体関係 (universal relation)
空関係 (empty relation)• A上の任意の関係Rは
Φ ⊂ R ⊂ A×Aを満たす• 特に、

R = A×A
を全体関係と呼び、R=Φを空関係と呼ぶ
23

逆関係• AからBへの関係を R とする。
• Rの逆 (inverse) は、
R-1と表記し、次のように定められる

R-1 = { (b, a) | (a, b) ∈ R}
• つまり、bR-1a であるのは、aRbであるとき、かつ、このときに限る。

24

練習• A={1,2,3}, B={a,b,c}, R={ (1,a), (2,b), (3,b), (3,c) }であるとき、R-1={….}を求めよ。また、RおよびR-1を、それぞれ、矢線図で図示せよ。

R-1={ (a,1), (b,2), (b,3), (c,3) }123A

RabcabcB

B-1R

123A

25

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射
26

関係の性質• Rを集合A上の関係とし、以下、a ∈A, b ∈ Aとする。
• aRa• Rは反射的(reflexive)である• aRb  bRa• Rは対称的 (symmetric)である• aRb かつ bRa  a=b• Rは反対称的 (anti-symmetric)である• aRb かつ bRc  aRc• Rは推移的 (transitive)である
27

練習• 集合を要素とする集合(=類)上の、包含関係⊂ の性質(反射的、対称的、反対称的、推移的)について論じよ• 解：• A⊂A であるから、⊂ は反射的である• A⊂Bであっても、B⊂A とは限らないので、⊂は対称的ではない• A⊂BかつB⊂Aであれば、A=Bであるから、⊂は反対称的である• A⊂BかつB⊂Cであれば、A⊂Cであるから、⊂は推移的である
28

練習• 任意の集合上の相等関係 = の性質(反射的、対称的、反対称的、推移的)について論じよ• 解：• a = a であるから = は反射的である• a = b であれば、b = a なので = は対称的である• a = b かつ b = a ならば、a = b なので = は反対称的である• a = b かつ b = c であれば、a = c なので = は推移的である(*) 対称的である関係と反対称的である関係は、互いに背反ではない。
29

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射30同値関係 (Equivalence Relation)• 集合S上の関係Rが、• 反射的である• 対称的である• 推移的である( aRa )
( aRb  bRa )( aRb ∧ bRc  aRc )とき、Rは同値関係である、と呼ばれる。
S の部分集合Ai(ただしAiは互いに素、かつSの各要素はいずれかのAiに属する)とするとき、Sの要素a, bが 同じAi に属するという関係R={(a, b) | a ∈ Ai, b∈Ai}が、同値関係である

SA1A2A331例• あるC言語のプログラムの変数の集合 {a, b, c, d, e, f}
において、“同じ型にある関係R”は、同値関係である• int a = 20;• int b = 213;
• int c=-80;• float d = 21.3;• float e = 31.212;• float f = 19.2;int 型変数の集合 {a, b, c}
float 型変数の集合 {d, e, f}
xRx は成立xRy  yRxは成立
xRy かつ yRz  xRz は成立

32

分割 と 同値類 ・・・ そして商集合• 分割 (Partition)• 空でない集合Sの分割とは、以下を満たす類 { Ai } である。
• { Ai } の各集合は互いに素である• Sの各要素aは一つのAiに属する• 同値類 (Equivalent Class)• Rを、集合S上の同値関係とする• s ∈ Sに対して、sと同値関係にある要素の集合をSの同値類と呼び、[s] と書く[ s ] = { x | (s, x) ∈ R }• 商集合(Quotient Set)
• Sの同値類の集合• SのRによる商• S/R で表す
S/R = { [s] | s∈S }33

分割 (Partition)• 空でない集合Sの分割とは、以下を満たす類 { Ai }である。
• { Ai } の各集合は互いに素である• Sの各要素aは一つのAiに属する

S

A1A3A2A5A6A4Sの分割例： {A1, A2, A3, A4, A5, A6}34同値類 (Equivalent Class)• Rを、集合S上の同値関係とする• s ∈ Sに対して、sと同値関係Rにある要素の集合をSの同値類と呼び、[s] と書く[ s ] = { x | (s, x) ∈ R }Ss[ s ] : s と同値関係 R にある要素の集合 35

商集合 (Quotient Set)
• Sの同値類の集合• SのRによる商• S/R で表す
S/R = { [s] | s∈S }Rの観点で見たときに、この中は「同じモノ」である
Rは境界線を持ち、その境界線でSを分割できるS

SのRによる商: S/R

36

応用: 前方誤り訂正 (1/3)(FEC: Forward Error Correction)• 情報(ここでは、ビット列を考える)は、伝搬する間、保管されている間、解読時に、失われることがある
ロス / ビットエラー

配送＆時間の経過• 一部が失われても、元のビット列を復元することを可能にする、前方誤り訂正という技術がある。
37

応用: 前方誤り訂正 (2/3)
誤り(揺らぎ)について考える“a”というデータを送ったのに、あるビットの0と1が反転して、”b”になってしまうことがある。

送信したデータ
ab

電磁波

宇宙線

受信されたデータ
ac

熱

外乱

bc

揺らぎ

38

応用: 前方誤り訂正 (3/3)
揺らぎが同値類に収まっていれば、復元可能
重要なデータ

復元されたデータ

a b c

a b c

エンコードa  a’

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

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

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

外乱

受信したデータ39半順序関係 (Partial Ordering)• 集合S上の関係Rが、• 反射的である• 反対称的である• 推移的である( aRa )
( aRb ∧ bRa  a=b )( aRb ∧ bRc  aRc )とき、Rは半順序関係である、と呼ばれる。
• 例: ≦• 詳細は来週の講義で40

今日のテーマ: 関係 と 関数
• 関係 (2項関係)• 単一集合上の関係• 相等性, 全体関係, 空関係, 逆関係• 関係の性質• 同値関係，分割，商集合• 半順序関係• 関数• 単射, 全射, 全単射
41

関数• 集合Aの各要素に対し、集合Bの唯一の要素を割り当てる。
• そのような割当て全体のことを、AからBへの関数(function)と呼ぶ。(写像、変換と呼ぶ場合もある。)• A: 定義域 (domain)• B: 値域 (co-domain)

f: A → B“fはAをBにうつす”と読む
a∈Aに対する、fのもとでのBの唯一の要素を、aの像(image) または aの値 (value) と呼び、 f(a)と書く

42

練習• (a), (b), (c)の各図が、A={1, 2, 3}からB={a, b, c}への関数を定義するか、論じよ。

123abc(a)123abc(b)123abc(c)解(a) 関数ではない: (理由) 2の像がない(b) 関数ではない: (理由) 3がB上の2つの要素に関係づけされている
43(c) 関数である

1対1の関数, 上への関数, 逆関数• 1対1の関数• 定義域の異なる要素が、異なる像を持つ場合
f(a) = f(a’) → a=a’AB

• 上への関数• Bの各要素がAのある要素の像となっている
f(A) = B

• 逆関数

AB

• 逆関係 f -1 がBからAへの関数であるとき(*) 一般に、逆関係が、関数であるとは限らない• この場合、fは可逆である、という。

AB• fが可逆であるのは、fが1対1で上への関数であるとき(1対1対応(one to one correspondence)と呼ぶ)に限る44

単射、全射、全単射• 単射• 1対1のとき

AB• 全射• 上への関数のとき
AB

• 全単射
• 1対1かつ上への関数 = 1対1対応のとき
AB

45

練習
• (a)～(d)について、1対1の関数、上への関数、可逆な関数を答えよ。

123abcd1234(a)解・ 1対1の関数: (a), (d)・ 上への関数: (b), (d)・ 可逆な関数: (d)abc(b)

123abc(c)123abc(d)46次回(4月22日)：順序集合 と 束
2315748束(Lattice)

6910

順序集合
47

引用： http://www.homedepot.ca/product/4-feet-x-8-feet-western-red-cedar-lattice/935813