3. 束 五島 正裕.

Presentation on theme: "3. 束 五島 正裕."— Presentation transcript:

1 3. 束 五島 正裕

2 代数系 (algebraic system)
S を台集合とする代数系（代数構造 (algebraic structure)）という 抽象代数学 (abstract algebra) 個別の集合や演算ではなく，代数系としての性質についてのみ着目

3 演算一つ 半群 (semigroup) 結合律： (a ∙ b) ∙ c = a ∙ (b ∙ c)
単位半群 (unitary semigroup, monoid) 半群 ＋ 単位元 単位元： a ∙ e = e ∙ a = a なる e 例）文字列の連接，単位元は空文字列 群 (group) 単位半群 ＋ 逆元 逆元： x −1 ∙ x = x ∙ x −1 = e なる x −1 可換群 (commutative group)，アーベル群 (Abelian group) 交換律 x ∙ y = y ∙ x 例）整数上の加法

4 演算二つ (加法と乗法) 環 (ring) 加法について可換群 乗法について半群 可換環 (commutative ring)
乗法についても可換 非可換環 (non-commutative group) 乗法について非可換 体 (field) 可換環 ＋ 分配律 分配率： x ∙ (y + z) = x ∙ y + x ∙ z 例）実数体，複素数体

5 内演算と外演算 集合 S と他の集合 Σ に対し 写像 α : S × S → S S 上の内演算 (internal operation)
写像 β : Σ × S → S S 上の外演算 (external operation) 群，環 内演算 有限オートマトン 外演算ひとつ Σ：状態の集合 S：入出力シンボルの集合

6 束 (lattice)

7 束の半順序集合による定義 束 L = (S, ＋, ・) 半順序集合 S の任意の 2要素 x, y に対し，
結びと交わり x ＋ y ：{x, y} の上限：結び (join) x ・ y ：{x, y} の下限：交わり (meet)

8 束の代数的定義 交換律 (commutative law) x ・ y = y ・ x x ＋ y = y ＋ x
結合律 (associative law) x ・ (y ・ z) = (x ・ y) ・ z x ＋ (y ＋ z) = (x ＋ y) ＋ z 吸収律 (absorptive law) x ・ (x ＋ y) = x x ＋ (x ・ y) = x べき等律 (idempotent law) x ・ x = x x ＋ x = x

9 吸収律 → べき等律 吸収律が成り立つなら，べき等律も成り立つ
吸収律 x = x ・ (x ＋ y) において，y = (x ・ x) とおくと x = x ・ (x ＋ (x ・ x)) ... ① ここで，吸収律 x ＋ (x ・ y) = x は，y = x としても成り立つので， x ＋ (x ・ x) = x ... ② したがって，①，② より x = x ・ (x ＋ (x ・ x)) = x ・ x

10 束の例 (1/2) ブール代数（ブール束） 元 ：0，1 A ＋ B ：論理和 A ・ B ：論理積 A ≦ B ：0 ≦ 1 1

11 束の例 (2/4) 含意 (implication) 元 ：述語 A ＋ B ：論理和 A ・ B ：論理積
元 ：述語 A ＋ B ：論理和 A ・ B ：論理積 A ≦ B ：含意，「A ならば B」

12 束の例 (3/4) 集合演算 元 ：集合 A ＋ B ：集合和 A ・ B ：集合積 A ≦ B ：A ⊂ B 例）
元 ：集合 A ＋ B ：集合和 A ・ B ：集合積 A ≦ B ：A ⊂ B 例） 集合 A = {a, b, c} の巾集合 2A {a, b, c} {a, b} {a, c} {b, c} {a} {b} {c} {}

13 束の例 (4/4) 12 4 6 2 3 因数 元 ：自然数 A ＋ B ：A, B の最小公倍数 A ・ B ：A, B の最大公約数
元 ：自然数 A ＋ B ：A, B の最小公倍数 A ・ B ：A, B の最大公約数 A ≦ B ：「A は B の因数」 例） 12 の因数 12 4 6 2 3 1

14 束にならない半順序集合 {a, b} の下限はない {c, d} の上限はない a・b ？ c＋d ？ T a b c d ⊥

15 束と半順序 束 L = (S, ＋, ・) の S の元 x，y について
x ・ y = x かつ x ＋ y = y ⇔ x ≤ y と定義すれば， S は ≤ についての半順序集合

16 順序関係 (order relation) 反射的 x ≤ x 反対称的 x ≤ y and y ≤ x ⇒ x = y
推移的 x ≤ y and y ≤ z ⇒ x ≤ z

17 証明 (1/2) 反射律： x ≤ x x ・ x = x かつ x ＋ x = x (べき等)
推移律： x ≤ y かつ y ≤ z ならば x ≤ z 前提条件は定義から x ・ y = x, x＋y = y, y ・ z = y, y＋z = z． これから x ・ z = x, x ＋ z = z を導ければ良い． x ・ z = (x ・ y) ・ z = x ・ (y ・ z) = x ・ y = x． x ＋ z = x ＋ (y ＋ z) = (x ＋ y) ＋z = y ＋ z = z．

18 証明 (2/2) 反対称律：x ≤ y かつ y ≤ x ならば x = y 前提条件は，定義から
x ・ y = x, x ＋ y = y, y ・ x = y, y ＋ x = x． これから x = y を導ければ良い． x = x ・ y = y ・ x = y．