ブール代数

4. ブール代数
五島正裕
DATE
:
束の代数的定義
1. 交換律 (commutative law)
x ・ y = y ・ x
x ＋ y = y ＋ x
4. べき等律 (idempotent law)
（他の3つから導かれる）
x ・ x = x
x ＋ x = 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
ブール束
 ブール束 (B, ＋, ・)
 束の定義
 交換律
 結合律
 吸収律（ブール束の場合，他から導かれる）
 追加：
 分配律 (distributive law) → distributive lattice
 単位元 1，零元 0 の存在
 補元 x' の存在
ブール代数の定義
1.
交換律 (commutative law)
4. 単位元 1，零元 0 の存在
x・y = y・x
x・1 = x
x＋y = y＋x
x＋0 = x
2. 結合律 (associative law)
5. 補元 x' の存在
 x ・ (y ・ z) = (x ・ y) ・ z
 x ・ x' = 0
 x ＋ (y ＋ z) = (x ＋ y) ＋ z
 x ＋ x' = 1
3. 分配律 (distributive law) →
distributive lattice
 x ・ (y ＋ z) = (x ・ y) ＋ (x ・ z)
 x ＋ (y ・ z) = (x ＋ y) ・ (x ＋ z)
ブール代数の例 (1/2)
 二元ブール代数
B
： {0, 1}
 零元
：0
 単位元
：1
＋
：論理和 x ＋ y
・
：論理積 x ・ y
 補元
：0⇔1
1
0
ブール代数の例 (2/2)
 集合演算
{a, b, c}
B
：集合
 零元
：空集合
 単位元
：全集合
＋
：集合和 x ∪ y
・
：集合積 x ∩ y
 補元
：補集合
{a, b}
{a, c}
{b, c}
{a}
{b}
{c}
 例）
 集合 A = {a, b, c} の巾集合 2A
{}
ブール代数ではない例
 因数
元
：最大数の因数
 零元
：1
 単位元
：最大数
＋
： x, y の最小公倍数
・
： x, y の最大公約数
x≦y
：「x は y の因数」
 補元
：単位元 ÷ x？
 例）
 12 の因数？
 6 の因数？
12
4
6
2
3
1
ブール代数の性質
 性質：
1.
双対性
2.
1, 0 の性質
3.
1, 0 は一意
4.
補元は一意
5.
吸収律
6.
べき等律
7.
二重否定
8.
ド・モルガンの法則
1. 双対性 (duality)
 双対
 公理において，・ ⇔ ＋, 1 ⇔ 0 を交換すると，同じ公理
2. 1, 0 の性質
 1, 0 の定義
x ・ 1 = x
x ＋ 0 = x
 1, 0 の性質
x ・ 0 = 0
x ＋ 1 = 1
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 も同様に成り立つ．
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 ＋ 02 = 01
交換律から両者の左辺は等しい
∴ 01 = 0 2
4. 補元は一意
x' がふたつ存在するとして，￢1x, ￢2x とすると
￢ 2x = 1 ・￢ 2x
= (x + ￢1x) ・￢2x
= (x ・￢2x) + (￢1x ・￢2x)
= 0 + (￢1x ・￢2x)
同様に
￢1x = 0 ＋ (￢1x ・￢2x)
∴ ￢ 1x = ￢ 2x
∵ 1 の定義
∵ ￢1 についての仮定 x ＋￢1x = 1
∵ 分配律
∵ ￢2 についての仮定 x ・￢2x = 0
5. 吸収律 (absorptive law)
 吸収律
 x ・ (x ＋ y) = x
 x ＋ (x ・ y) = x
x ∙ (x + y)
=
=
=
=
(x + 0) ∙ (x + y)
x + (0 ∙ y)
x+0
x
∵ 0 の定義 (x + 0 = x)
∵ 分配律
∵ 0 の性質 (0 ∙ y = 0)
∵ 0 の定義 (x + 0 = x)
6. べき等律 (idempotent law)
 べき等律
x ・ x = x
x ＋ x = x
x・x
=
=
=
=
=
(x ・ x) ＋ 0
(x ・ x) ＋ (x ・ x')
x ・ (x ＋ x')
x・1
x
∵ 0 の定義
∵ 補元の定義
∵ 分配律
∵ 補元の定義
7. 二重否定
x'' = x
交換則により，
x' ＋ x = 1
x' ・ x = 0
であり，x は x' の補元になっている．
x'' の一意性から x'' = x
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
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+0 = 0
以下同様．
ブール束
 ブール束 (B, ＋, ・)
束
 交換律
 結合律
 吸収律（ブール束の場合，他から導かれる）
 追加：
 分配律 (distributive law) → distributive lattice
 単位元 1，零元 0 の存在
 補元 x' の存在
含意と半順序
 含意 →
 「ならば」
 x → y ≡ x' ＋ y
∵ 定義
 含意はブール束での半順序
 x → y ⇒ x ・ y = x かつ x ＋ y = y
含意と半順序
 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
・1
∵ x → y ⇒ x′ ＋ y
= x ・ (y ＋ x)
= x
∵ 吸収律
x＋y
= (x ・ y) ＋ y
= y
∵ 吸収律

Download Report