pptxファイル

中の関係の性質
集合𝐴中の関係𝑅において
あらゆる𝑥, 𝑦, 𝑧 ∈ 𝐴に対して
𝑥𝑅𝑥
𝑥𝑅𝑦 ⇒ 𝑦𝑅𝑥
(𝑥𝑅𝑦 ∧ 𝑦𝑅𝑧) ⇒ 𝑥𝑅𝑧
𝑥𝑅𝑦 ∧ 𝑦𝑅𝑥 ⇒ 𝑥 = 𝑦
反射律を満たす
対称律を満たす
推移律を満たす
反対称律を満たす
同値関係；反射律、対称律、推移律を満たす関係
同値関係の関係グラフと同値類、商集合
ℎ
[𝑎]𝑅
[𝑏]
[ℎ]𝑅
[𝑎]𝑅
𝑎
𝑏
𝑖
𝑐
𝑗
𝑑
[𝑖]𝑅
𝐴/𝑅
[𝑑]𝑅
[ℎ]𝑅
[𝑖]𝑅
𝑘
𝑒
[𝑑]𝑅
𝑙
[𝑔]𝑅
𝑚
[𝑔]𝑅
[𝑙]𝑅
𝑔
𝑛
𝑜
[𝑙]𝑅
反対称律
任意の 𝑥, 𝑦 ∊ 𝐴 に対して
𝑥 ≤ 𝑦 かつ 𝑦 ≤ 𝑥 ⇒ 𝑥 = 𝑦
対偶
任意の 𝑥, 𝑦 ∊ 𝐴 に対して
𝑥 ≠ 𝑦 ⇒ 𝑥 ≤ 𝑦 かつ 𝑦 ≤ 𝑥 でない
関係グラフにおいて
相異なる要素間には高々一方向にしか辺がない
トーナメント戦における強弱関係
𝐶
𝐶
𝐴
𝐹
𝐶
𝐹
𝐺
𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐺 𝐻
規則
1. 𝑥が𝑦に勝った
⇒ 𝑥は𝑦より強い
反対称律
2. 𝑥が𝑦に勝ったかつ
𝑦が𝑧に勝った
⇒ 𝑥はzより強い
推移律
結論
・𝐶が一番強い
・2番目に強いのは
𝐹か𝐴か𝐷（比較不能）
関係グラフとハッセ図
a
・反射的関係のループを除く
f
b
e
c
d
関係グラフ
・推移的に得られる
有向辺を除く
xRz zRy なる
z があれば
xRyの有向辺を除く
・上位の要素を上に配置し
辺の向きをなくす
関係グラフとハッセ図
a
・反射的関係のループを除く
f
b
e
c
d
関係グラフ
・推移的に得られる
有向辺を除く
xRz zRy なる
z があれば
xRyの有向辺を除く
・上位の要素を上に配置し
辺の向きをなくす
約数関係
12
8
6
2
3
1
集合の包含関係
{𝑎, 𝑏, 𝑐}
{𝑎, 𝑏}
{𝑏, 𝑐}
{𝑎, 𝑐}
{𝑎}
{𝑏}
{𝑐}
∅
派生語関係（p.198 解1）
affect
affectation
affected
affecting
affectedness
affectedly
affection
affective
affectionate
affectingly
affectionately
辞書式順序
able, all, angry, arrive, bad, beautiful, best, big, black, blue, busy,
buy, careful, catch, clean, cold, collect, come, cook, cool, dance,
dark, do, drink, early, easy, eat, enjoy, every, famous, fast,
favorite, fine, free, friendly, full, funny, get, give, glad, go, good,
green, happy, have, help, high, home, honest, hot, hungry, ill,
interesting, junior, kind, know, large, later, learn, leave, light, like,
little, live, long, look, low, make, many, meet, move, much, need,
new, next, nice, no, noisy, old, open, play, poor, popular, put,
quiet, read, red, rich, ride, right, run, sad, sell, send, shy, short,
sick, sing, slow, smart, small, some, sorry, speak, stand, stay,
stop, strong, study, swim, tall, true, try, up, use, visit, wait, walk,
want, wash, warm, well, white, work, write, yesterday, young
上限と下限
順序集合(𝑋; ≦) において
 極大元:自分より大きい（上位の）要素を持たない元
有限集合中に1個以上存在
 最大元：唯一の極大元（もしあれば）
max(𝑋)
極小元、最小元( min(𝑋) )も同様に定義する
順序集合(𝑋; ≦)と、その部分集合𝐴において
 𝐴の上界
𝑈𝑝𝑝𝑒𝑟(𝐴) = {𝑥 | 𝑥 ∈ 𝑋, すべての𝑎 ∈ 𝐴に対し𝑎 ≦ 𝑥}
 𝐴の上限（最小上界）
sup(𝐴) = min(𝑈𝑝𝑝𝑒𝑟(𝐴))
下界(𝐿𝑜𝑤𝑒𝑟 𝐴 )、下限( inf(𝐴) )も同様に定義する
極大元
最大元max(𝑋)
例
a
c
b
e
d
f
g
極小元
h
最小元なし
例1
𝐴の最小上界
（上限）
sup(𝐴)
𝐴の上界𝑈𝑝𝑝𝑒𝑟(𝐴)
a
c
b
𝐴
e
d
f
𝐴の下界
𝐿𝑜𝑤𝑒𝑟(𝐴)
h
g
𝐴の下限
inf(𝐴)
例2
𝑈𝑝𝑝𝑒𝑟(𝐵)
sup(𝐵)
a
𝐵
c
b
inf(𝐵)
e
d
𝐿𝑜𝑤𝑒𝑟(𝐵)
f
g
h

Download Report