情報数学（第9回） 9章　離散関係 7章　剰余演算 12章　順序の数学.

Presentation on theme: "情報数学（第9回） 9章　離散関係 7章　剰余演算 12章　順序の数学."— Presentation transcript:

1 情報数学（第9回） 9章　離散関係 7章　剰余演算 12章　順序の数学

2 集合間の多対多対応 科目の集合 学生の集合 𝐵 𝐴 𝐴から𝐵への 多対多対応
教科書p. 138■2項関係 集合間の多対多対応 科目の集合 𝐵 学生の集合 𝐴 a S b T c U d 𝐴から𝐵への 多対多対応 𝑅={ 𝑥,𝑦 ∣𝑥∈𝐴, 𝑦∈𝐵,学生𝑥が科目𝑦を受講している} = 𝑎,𝑆 , 𝑏,𝑆 , 𝑏,𝑇 , 𝑑,𝑆 , 𝑑,𝑈 ⊆𝐴×𝐵 学生 𝑎 が科目 𝑆 を受講していることを表す

3 2項関係、𝑛項関係 𝑅= 𝑎,𝑆 , 𝑏,𝑆 , 𝑏,𝑇 , 𝑑,𝑆 , 𝑑,𝑈 ⊆𝐴×𝐵 𝐴 と 𝐵 の直積 2項組 （順序対）
教科書p. 138■2項関係 2項関係、𝑛項関係 𝑅= 𝑎,𝑆 , 𝑏,𝑆 , 𝑏,𝑇 , 𝑑,𝑆 , 𝑑,𝑈 ⊆𝐴×𝐵 （𝐴から𝐵への）2項関係（binary relation） 2項組 （順序対） 𝐴 と 𝐵 の直積 3項組 (𝑎,𝑆,85)：学生 𝑎 の科目 𝑆 の得点が85点であることを表す 3項関係：　3項組の集合 （⊆𝐴×𝐵× 𝒩 ） 4項関係：　受講年度を含めた4項組の集合 データベースの数学的基礎 なんてことはおいておいて、以降は2項関係に焦点を絞る

4 𝐴から𝐴への関係 𝐴から𝐴への関係 𝑅⊆𝐴×𝐴= 𝐴 2 を𝐴の中の関係、 𝐴の上の関係、 𝐴における関係といい、
教科書p. 138■2項関係 𝐴から𝐴への関係 　𝐴から𝐴への関係 𝑅⊆𝐴×𝐴= 𝐴 2 を𝐴の中の関係、 𝐴の上の関係、 𝐴における関係といい、 「 𝑎,𝑏 ∈𝑅 」であるとき 「𝑎𝑅𝑏」とも表記する 集合表現 中置記法 ・1桁の奇数の集合 𝑂 1 = 1,3,5,7,9 の中の大小関係「<」 < ={ 1,3 , 1,5 , 1,7 , 1,9 , 3,5 , 3,7 , 3,9 , 5,7 , 5,9 , 7,9 } 　は、 「 1,7 ∈<」よりも「1<7」 　が一般的 ・人の集合の中の関係「友人」、「親子」、etc.

5 関係グラフ 節点，頂点 node vertex 𝐴 有向辺 arc 𝐴 𝐵 𝑎 𝑎 𝑝 𝑏 𝑑 𝑞 𝑏 𝑐 𝑟 𝑐 𝑑 有限集合𝐴の中の関係
教科書p. 139■関係グラフと関係行列 関係グラフ 節点，頂点 node vertex 𝐴 有向辺 arc 𝐴 𝐵 𝑎 𝑎 𝑝 𝑏 𝑑 𝑞 𝑏 𝑐 𝑟 𝑐 𝑑 有限集合𝐴の中の関係 有限集合𝐴から有限集合𝐵への関係

6 有限集合間の関係の行列表現 p q r a b c d 1 0 0 1 1 0 0 0 0 0 0 1 (𝑎, 𝑝) ∈ 𝑅
𝑎, 𝑞 ∉ 𝑅

7 逆関係 𝐴から𝐵への関係に対して、𝐵から𝐴への関係 𝑅 −1 = 𝑅 inv ={ 𝑥,𝑦 ∣𝑦𝑅𝑥}
教科書p139■逆関係 逆関係 　𝐴から𝐵への関係に対して、𝐵から𝐴への関係 𝑅 −1 = 𝑅 inv ={ 𝑥,𝑦 ∣𝑦𝑅𝑥} を𝑅の逆関係（inverse relation）という ・学生の集合から科目の集合への「受講関係」の逆関係は 「受講者関係」 ・人の集合の中の関係「親子関係」の逆関係は「子親関係」 ・𝒩の中の関係「<」の逆関係は「 > 」 クイズ ・𝒩の中の関係「=」の逆関係は?

8 中の関係の合成 𝑅: 集合 𝐴 の中の関係として ・ 𝑅 0 = 𝑥,𝑥 𝑥∈𝐴 =𝐼 恒等関係
教科書p.141■中の関係の合成 中の関係の合成 𝑅: 集合 𝐴 の中の関係として ・ 𝑅 0 = 𝑥,𝑥 𝑥∈𝐴 =𝐼 恒等関係 ・ 𝑅 2 =𝑅 ∙𝑅={ 𝑥,𝑧 ∣∃𝑦∈𝐴 𝑥𝑅𝑦∧𝑦𝑅𝑧 } 𝑅の2次の合成 ・ 𝑅 𝑛 = 𝑅 𝑛−1 ∙𝑅=𝑅∙ 𝑅 𝑛−1 ={ 𝑥,𝑧 ∣∃𝑦∈𝐴 𝑥𝑅𝑦∧𝑦 𝑅 𝑛−1 𝑧 } 𝑅の𝑛次の合成 ・人の集合の中の「親子関係」の 2次の合成は「祖父母・孫関係」 𝑛次の合成は「𝑛代祖先子孫関係」 ・𝒩の中の関係「≤」の2次の合成は「 ≤ 」 ・𝒩の中の関係「<」の2次の合成は「2以上小さい関係」

9 反射的関係（reflexive relation）
教科書p.142■中の関係の性質 反射的関係（reflexive relation） 反射律:　任意の 𝑥 に対して、　　　　𝑥𝑅𝑥 反射的関係： 反射律を満たす関係 関係行列では 関係グラフでは 1 ・𝒩の中の関係「=」、「≤」は反射的関係 ・𝒩の中の関係「<」は反射的でない

10 対称的関係（symmetric relation）
教科書p.142■中の関係の性質 対称的関係（symmetric relation） 対称律:　任意の𝑥，𝑦に対して、　𝑥𝑅𝑦 ならば 𝑦𝑅𝑥 対称的関係： 対称律を満たす関係 関係行列では 関係グラフでは ・𝒩の中の関係「≠」は対称的関係 ・人の集合の中の「友人関係」が対称的なら円満なのだが．．．

11 推移的関係（transitive relation）
教科書p.142■中の関係の性質 推移的関係（transitive relation） 推移律:　任意の𝑥,𝑦, 𝑧に対して、　𝑥𝑅𝑦 かつ 𝑦𝑅𝑧 ならば 𝑥𝑅𝑧 推移的関係： 推移律を満たす関係 関係グラフでは 間接的な関係があれば 直接の関係も存在する 𝑅 2 ⊆𝑅 ・𝒩の中の関係「≤」、「<」は推移的関係 ・人の集合の中の「祖先子孫関係」は推移的関係

12 反対称的関係（asymmetric relation）
教科書p.143■中の関係の性質 反対称的関係（asymmetric relation） 反対称律:　任意の𝑥，𝑦に対して、𝑥𝑅𝑦 かつ 𝑦𝑅𝑥 ならば 𝑥=𝑦 反対称的関係：　反対称律を満たす関係 関係行列では 関係グラフでは ・𝒩の中の関係「<」、「≤」は反対称的関係 ・人の集合の中の「親子関係」、「祖先子孫関係」は反対称的

13 教科書p.143■同値関係 同値関係 𝐴 の中の関係 𝑅 が反射律、対称律、推移律を満たすとき、𝑅 は 𝐴 における同値関係(equivalence relation)であるという 同値関係は「等号」で表すのが適当であり、=と区別できる ≅,≈,≡ などが用いられる

14 𝑛を法として合同 自然数 𝑛 で整数 𝑚 1 と 𝑚 2 を割った剰余が同じであるとき 𝑚 1 ≡ 𝑚 2 mod 𝑛 あるいは
教科書p.105■合同 𝑛を法として合同 自然数 𝑛 で整数 𝑚 1 と 𝑚 2 を割った剰余が同じであるとき 𝑚 1 ≡ 𝑚 2 mod 𝑛 あるいは 𝑚 1 ≡ 𝑛 𝑚 2 と書き、 𝑚 1 と 𝑚 2 は 𝑛 を法として合同（congruent modulo 𝑛）であるという ≡ 𝑛 は𝒵（整数の集合）における同値関係 反射律： 任意の 𝑥∈𝒵 に対して　𝑥 ≡ 𝑛 𝑥 対称律： 任意の 𝑥,𝑦∈𝒵 に対して　𝑥 ≡ 𝑛 𝑦 ならば 𝑦 ≡ 𝑛 𝑥 推移律： 任意の 𝑥,𝑦,𝑧∈𝒵 に対して　 𝑥 ≡ 𝑛 𝑦 かつ 𝑦 ≡ 𝑛 𝑧ならば 𝑥≡ 𝑛 𝑧

15 教科書p.186■順序関係 順序関係 𝐴 の中の関係 𝑅 が反射律、反対称律、推移律を満たすとき、𝑅 は 𝐴 における順序関係（order relation）であるという 全順序関係 半順序関係 𝒩(あるいは𝒵）の中の大小関係「≤」は、順序関係 順序関係は「等号つき不等号」で表すのが適当であり ≤,⊆,≼ などあるいは、その逆向きの記号が用いられる