離散数学

離散数学
3. 束
五島 正裕
離散数学
代数系 (algebraic system)
 集合 S といくつかの演算を合わせたものを
S を台集合とする代数系(代数構造 (algebraic structure))という
 抽象代数学 (abstract algebra)
 個別の集合や演算ではなく,代数系としての性質についてのみ着目
離散数学
演算一つ
 半群 (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

例)整数上の加法
離散数学
演算二つ (加法と乗法)
 環 (ring)
 加法について可換群
 乗法について半群
 可換環 (commutative ring)

乗法についても可換
 非可換環 (non-commutative group)

乗法について非可換
 体 (field)
 可換環 + 分配律
 分配率: x ∙ (y + z) = x ∙ y + x ∙ z

例)実数体,複素数体
離散数学
内演算と外演算
 集合 S と他の集合 Σ に対し
 写像 α : S × S → S
S 上の内演算 (internal operation)
 写像 β : Σ × S → S
S 上の外演算 (external operation)
 群,環
 内演算
 有限オートマトン
 外演算ひとつ

Σ:状態の集合

S:入出力シンボルの集合
離散数学
束 (lattice)
離散数学
束の半順序集合による定義
 束 L = (S, +, ・)
 半順序集合 S の任意の 2要素 x, y に対し,
{x, y} の上限,下限が共に存在する
 結びと交わり
 x + y :{x, y} の上限:結び (join)
 x ・ y :{x, y} の下限:交わり (meet)
離散数学
束の代数的定義
1.
交換律 (commutative law)
x・y=y・x
x+y=y+x
2.
結合律 (associative law)
 x ・ (y ・ z) = (x ・ y) ・ z
 x + (y + z) = (x + y) + z
3.
吸収律 (absorptive law)
 x ・ (x + y) = x
 x + (x ・ y) = x
4.
べき等律 (idempotent law)
x・x=x
x+x=x
離散数学
吸収律 → べき等律
 吸収律が成り立つなら,べき等律も成り立つ
吸収律 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
離散数学
束の例 (1/2)
 ブール代数(ブール束)
元
:0,1
A+B
:論理和
A・B
:論理積
A≦B
:0 ≦ 1
1
0
離散数学
束の例 (2/4)
 含意 (implication)
元
:述語
A+B
:論理和
A・B
:論理積
A≦B
:含意,「A ならば B」
離散数学
束の例 (3/4)
{a, b, c}
 集合演算
元
:集合
A+B
:集合和
A・B
:集合積
A≦B
:A ⊂ B
 例)
{a, b}
{a, c}
{b, c}
{a}
{b}
{c}
 集合 A = {a, b, c} の巾集合 2A
{}
離散数学
束の例 (4/4)
12
 因数
元
:自然数
A+B
:A, B の最小公倍数
A・B
:A, B の最大公約数
A≦B
:「A は B の因数」
4
6
2
3
 例)
 12 の因数
1
離散数学
束にならない半順序集合
T
 {a, b} の下限はない
 {c, d} の上限はない
a
b
c
d
 a・b ?
 c+d ?
⊥
離散数学
束と半順序
 束 L = (S, +, ・) の S の元 x,y について
x ・ y = x かつ x + y = y ⇔ x ≤ y と定義すれば,
S は ≤ についての半順序集合
離散数学
順序関係 (order relation)
1.
反射的
x≤x
2.
反対称的
x ≤ y and y ≤ x ⇒ x = y
3.
推移的
x ≤ y and y ≤ z ⇒ x ≤ z
離散数学
証明 (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.
離散数学
証明 (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.