4. ブール代数 五島 正裕.

Presentation on theme: "4. ブール代数 五島 正裕."— Presentation transcript:

1 4. ブール代数 五島 正裕

2 束の代数的定義 交換律 (commutative law) べき等律 (idempotent law) （他の3つから導かれる）
x ・ y = y ・ x x ・ x = x x ＋ y = y ＋ x x ＋ x = 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

3 ブール束 ブール束 (B, ＋, ・) 束の定義 交換律 結合律 吸収律（ブール束の場合，他から導かれる） 追加：
分配律 (distributive law) → distributive lattice 単位元 1，零元 0 の存在 補元 x' の存在

4 ブール代数の定義 交換律 (commutative law) 単位元 1，零元 0 の存在 x ・ y = y ・ x x ・ 1 = x
結合律 (associative law) 補元 x' の存在 x ・ (y ・ z) = (x ・ y) ・ z x ・ x' = 0 x ＋ (y ＋ z) = (x ＋ y) ＋ z x ＋ x' = 1 分配律 (distributive law) → distributive lattice x ・ (y ＋ z) = (x ・ y) ＋ (x ・ z) x ＋ (y ・ z) = (x ＋ y) ・ (x ＋ z)

5 ブール代数の例 (1/2) 二元ブール代数 B ： {0, 1} 零元 ： 0 単位元 ： 1 ＋ ： 論理和 x ＋ y
零元 ： 0 単位元 ： 1 ＋　 ： 論理和 x ＋ y ・　 ： 論理積 x ・ y 補元 ： 0 ⇔ 1 1

6 ブール代数の例 (2/2) 集合演算 B ： 集合 零元 ： 空集合 単位元 ： 全集合 ＋ ： 集合和 x ∪ y
零元 ： 空集合 単位元 ： 全集合 ＋　 ： 集合和 x ∪ y ・　 ： 集合積 x ∩ y 補元 ： 補集合 例） 集合 A = {a, b, c} の巾集合 2A {a, b, c} {a, b} {a, c} {b, c} {a} {b} {c} {}

7 ブール代数 ではない 例 12 4 6 2 3 1 因数 元 ： 最大数の因数 零元 ： 1 単位元 ： 最大数
元　 ： 最大数の因数 零元 ： 1 単位元 ： 最大数 ＋　 ： x, y の最小公倍数 ・　 ： x, y の最大公約数 x ≦ y ：「x は y の因数」 補元 ： 単位元 ÷ x？ 例） 12 の因数？ 6 の因数？ 12 4 6 2 3 1

8 ブール代数の性質 性質： 双対性 1, 0 の性質 1, 0 は一意 補元は一意 吸収律 べき等律 二重否定 ド・モルガンの法則

9 1. 双対性 (duality) 双対 公理において，・ ⇔ ＋, 1 ⇔ 0 を交換すると，同じ公理

10 2. 1, 0 の性質 1, 0 の定義 x ・ 1 = x x ＋ 0 = x 1, 0 の性質 x ・ 0 = 0 x ＋ 1 = 1

11 2. 1, 0 の性質 x ・ 0 = (x ・ 0) + 0 ∵ 0 の定義 (x ＋ 0 = x) = (x ・ 0) + (x ・ x') ∵ 補元の定義 (x ・ x' = 0) = x ・ (0 + x') ∵ 分配律 (x ・ (y ＋ z) = (x ・ y) ＋ (x ・ z)) = x ・ x' ∵ 補元の定義 = 0 双対性から，x ＋ 1 = 1 も同様に成り立つ．

12 3. 1, 0 は一意 ∀x∈B，x ＋ 0 = x を満たす 0 が複数あり，それらを (01, 02) とする，すなわ ち， x ＋ 01 = x x ＋ 02 = x 上の式の x に 02, 下の式の x に 01を代入すると 02 ＋ 01 = ＋ 02 = 01 交換律から両者の左辺は等しい ∴ 01 = 02

13 4. 補元は一意 x' がふたつ存在するとして，￢1x, ￢2x とすると ￢2x = 1 ・ ￢2x ∵ 1 の定義 = (x + ￢1x) ・ ￢2x ∵ ￢1 についての仮定 x ＋ ￢1x = 1 = (x ・ ￢2x) + (￢1x ・ ￢2x) ∵ 分配律 = 0 + (￢1x ・ ￢2x) ∵ ￢2 についての仮定 x ・ ￢2x = 0 同様に ￢1x = 0 ＋ (￢1x ・ ￢2x) ∴ ￢1x = ￢2x

14 5. 吸収律 (absorptive law) 吸収律 x ・ (x ＋ y) = x x ＋ (x ・ y) = x
= (x + 0) ∙ (x + y) ∵ 0 の定義 (x + 0 = x) = x + (0 ∙ y) ∵ 分配律 = x + 0 ∵ 0 の性質 (0 ∙ y = 0) = x ∵ 0 の定義 (x + 0 = x)

15 6. べき等律 (idempotent law) べき等律 x ・ x = x x ＋ x = x x ・ x
= (x ・ x) ＋ 0 ∵ 0 の定義 = (x ・ x) ＋ (x ・ x') ∵ 補元の定義 = x ・ (x ＋ x') 　　　　　　 ∵ 分配律 = x ・ 1 ∵ 補元の定義 = x

16 7. 二重否定 x'' = x 交換則により， x' ＋ x = 1 x' ・ x = 0 であり，x は x' の補元になっている． x'' の一意性から x'' = x

17 8. ド・モルガンの法則 (De Morgan's law)
(x ＋ y)' = x' ・ y' (x ・ y)' = x' ＋ y' 補元の定義より (x ＋ y)' = x' ・ y' ⇔ (x ＋ y)・(x' ・ y') = 0 かつ (x ＋ y)・(x' ・ y') = 1

18 8. ド・モルガンの法則 (De Morgan's law)
(x ＋ y)・(x' ・ y') = (x' ・ y')・(x + y) ∵ 交換律 = ((x' ・ y') ・ x) + ((x' ・ y') ・ y) ∵ 分配律 = ((y' ・ x') ・ x) + ((x' ・ y') ・ y) ∵ 交換律 = (y' ・ (x' ・ x)) + (x' ・ (y' ・ y)) ∵ 結合律 = (y' ・ 0) + (x' ・ 0) ∵ 交換律 = = 0 以下同様．

19 ブール束 ブール束 (B, ＋, ・) 束 交換律 結合律 吸収律（ブール束の場合，他から導かれる） 追加：
分配律 (distributive law) → distributive lattice 単位元 1，零元 0 の存在 補元 x' の存在

20 含意 と 半順序 含意 → 「ならば」 x → y ≡ x' ＋ y ∵ 定義 含意はブール束での半順序
x → y ⇒ x ・ y = x かつ x ＋ y = y

21 含意と半順序 x → y ⇒ x ・ y = x かつ x ＋ y = y
x ・ y = (x ・ y) ＋ 0 = (x ・ y) ＋ (x ・ x′) = (x ＋ x) ・ (y ＋ x) ・ (x ＋ x′) ・ (y ＋ x′) = x ・ (y ＋ x) ・ ・ 1 ∵ x → y ⇒ x′ ＋ y = x ・ (y ＋ x) = x ∵ 吸収律 x ＋ y = (x ・ y) ＋ y = y ∵ 吸収律