pptxファイル

2項組 (𝑎, 𝑏)：学生𝑎が科目𝑏を受講している
𝑎, 𝑏 ∈ 𝐴 × 𝐵
3項組 (𝑎, 𝑏, 𝑐)：学生𝑎の科目𝑏の成績は𝑐点
𝑎, 𝑏, 𝑐 ∈ 𝐴 × 𝐵 ×N
学生の集合𝐴 = 𝑎, 𝑏, 𝑐, 𝑑 から科目の集合𝐵 = 𝑆, 𝑇, 𝑈
への関係
𝑅 = 𝑥, 𝑦 | 𝑥 ∈ 𝐴, 𝑦 ∈ 𝐵, 𝑥さんは𝑦を受講している
= 𝑎, 𝑆 , 𝑏, 𝑆 , 𝑏, 𝑇 , 𝑑, 𝑆 , 𝑑, 𝑈
𝑆
𝑇
𝑈
𝑎
𝑏
𝑐
𝑑
𝑎
{𝑆}
𝑏
{𝑆, 𝑇}
𝑐
∅
𝑑
{𝑆, 𝑈}
𝐴
有向辺
arc
𝐵
節点，頂点
node
vertex
𝑎
𝑎
𝑝
𝑏
𝑞
𝑑
𝑏
𝑐
𝑟
𝑐
𝑑
𝐴の中の関係
𝐴から𝐵への関係
a
p
q
1
0
(𝑎, 𝑝) ∈ 𝑅
r
0
𝑎, 𝑞 ∉ 𝑅
b
1
1
0
c
0
0
0
d
0
0
1
𝐴 = {𝑎, 𝑏, 𝑐}, 𝐵 = {𝑝, 𝑞, 𝑟, 𝑠}, 𝐶 = {1, 2}
𝑃=
0111
1001
1010
𝑅 = 𝑃・𝑄 =
𝑥=𝑏
𝑧=1
の場合
𝑄=
00
11
01
10
𝑥, 𝑧 ∃𝑦 ∈ 𝐵. (𝑥, 𝑦) ∈ 𝑃, (𝑦, 𝑧) ∈ 𝑄 ｝
(𝑏, 𝑝) ∈ 𝑃
𝑏, 𝑞 ∈ 𝑃
𝑏, 𝑟 ∈ 𝑃
(𝑏, 𝑠) ∈ 𝑃
かつ (𝑝, 1) ∈ 𝑄 または
かつ 𝑞, 1 ∈ 𝑄 または
かつ 𝑟, 1 ∈ 𝑄 または
かつ (𝑠, 1) ∈ 𝑄
行列のブール積そのもの
反射律: 任意の 𝑥 に対して、
𝑥𝑅𝑥
反射的関係：
反射律を満たす関係
関係行列では
1
1
1
1
1
1
関係グラフでは
対称律: 任意の𝑥，𝑦に対して、 𝑥𝑅𝑦 ならば 𝑦𝑅𝑥
関係行列では
100100
001101
011000
110111
000100
010100
関係グラフでは
推移律: 任意の𝑥, 𝑦, 𝑧に対して、
𝑥𝑅𝑦 かつ 𝑦𝑅𝑧 ならば
𝑥𝑅𝑧
関係グラフでは
間接的な関係があれば
直接の関係も存在する
𝑅2 ⊆ 𝑅
反対称律: 任意の𝑥，𝑦に対して、
𝑥𝑅𝑦 かつ 𝑦𝑅𝑥 ならば 𝑥＝𝑦
関係行列では
100100
001101
001000
000111
100000
001000
関係グラフでは
𝐴 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 の中の同値関係𝑅が次のように
定義されている。
𝑅 = { 𝑎, 𝑎 , 𝑎, 𝑐 , 𝑎, 𝑒 , 𝑏, 𝑏 , 𝑐, 𝑎 , 𝑐, 𝑐 ,
𝑐, 𝑒 , 𝑑, 𝑑 , 𝑒, 𝑎 , 𝑒, 𝑐 , 𝑒, 𝑒 }
(1) 𝑅を関係グラフで表せ
(2) 𝑅を関係行列で表せ
(3) 𝑅による同値類をすべて求めよ
(1)
a
b
c
(2)
d
e
(3)
10101
01000
10101
00010
10101
[𝑎]𝑅 = 𝑎, 𝑐, 𝑒 = [𝑐]𝑅 = [𝑒]𝑅
[𝑏]𝑅 = 𝑏
[𝑑]𝑅 = {𝑑}

Download Report