離散数学Ｉ 第6回 茨城大学工学部 佐々木稔.

Presentation on theme: "離散数学Ｉ 第6回 茨城大学工学部 佐々木稔."— Presentation transcript:

1 離散数学Ｉ 第6回 茨城大学工学部 佐々木稔

2 今回のお話 半順序集合と束

3 集合 X の上限と下限 半順序集合 (S, ≼) の空集合でない集合 X ⊆ S に対して、集合 X の上限 sup X と下限 inf X を以下のように定義する X の上限 　sup X = min{ s∈S: 任意の x∈X に対して x≼s}　 X中のすべての要素の上位に共通するSの最小要素 X の下限 　inf X = max{ t∈S: 任意の x∈X に対して t≼x} X中のすべての要素の下位に共通するSの最大要素

4 束（そく） 任意の二つの要素について上限と下限が存在すれば、そのような半順序集合を束と呼ぶ

5 上限の例 c sup {b, c} = min {e, g} = e sup {a, c} = min {c, e, f, g} = c
sup {c, d} = min {e, g} = e sup {a, d} = min {d, e, g} = d sup {a, g} = min {g} = g g e f d c b a

6 下限の例 c inf {e, f} = max {c, a} = c inf {c, d} = max {a} = a
inf {e, g} = max {a, b, c, d, e} = e inf {d, e} = max {a, b, d} = d g e f d c b a

7 束でない半順序集合 i sup {m, p} = min∅=なし
inf {m, p} = max{k, i, j} = なし （j と k のどちらが大きいか分からない。j と k の間が線で結ばれていれば分かる。） p q n m k j i

8 束の演算 束 (S, ≼) について2つの演算が存在 x ∨ y = sup {x, y} x ∧ y = inf {x, y}

9 束の演算子 交換律 結合律 吸収律 x∨y = y∨x、 x∧y = y∧x
(x∨y)∨z = x∨(y∨z)、 (x∧y)∧z = x∧(y∧z) 吸収律 x∨(x∧y) = x 、 x∧(y∧x) = x

10 例題3.4 S={24の約数} とし、 x ≼ y を x|y と定義すると、 (S, ≼) は束になることを確かめよ。また、ハッセ図をかけ。

11 例題3.4 S={24の約数} とし、 x ≼ y を x|y と定義すると、 (S, ≼) は束になることを確かめよ。また、ハッセ図をかけ。 24 8 12 4 6 2 3 1

12 例題3.4 S={24の約数} とし、 x ≼ y を x|y と定義すると、 (S, ≼) は束になることを確かめよ。また、ハッセ図をかけ。 a ∨ b = sup {a, b} =min{x: a≼𝑥, 𝑏≼𝑥} =min{x: x はaとbの倍数} =a と b の最小公倍数 どの組合せでもSの要素となる。 従って、 (S, ≼) は束である。 24 8 12 4 6 2 3 1

13 例題3.5 束 (S, ≼) には最大元があることを示せ。

14 例題3.5 束 (S, ≼) には最大元があることを示せ。
２つの異なる極大元 p と q があると仮定する。 r = p∨qとおくと、 p ≼ r であるため p = r となる。 同様にして、q ≼ r であるため q = r となる。 これは異なる極大元 p, q ではないため矛盾する。したがって、極大元はひとつで、それが最大元となる。

15 今日の練習問題 31ページ　問題3.17 31ページ　問題3.19 提出用紙に学籍番号、氏名、答案を書いて、できれば提出してください。