本稿では,ブール代数の基礎と基本について記述する.ブール代数はイギリスの数学者ジョージ・ブール(George Boole, 1815-1864)によって考案された代数系で,電子工学や情報工学への応用が知られている.この世にある教科書やインターネットの内容の多くは工学の為のブール代数であることが多いが,本稿では数学の為のブール代数の理論を説明する.但し,本稿では集合と位相の基礎(目安として大学2年次程度の集合と位相の講義)を理解しているものとして話を進める.

モチベーションの為に本稿で扱う内容をざっくり説明する.はじめに,ブール代数は集合代数の一般化とみることができる.即ち,ある集合上の和集合,共通部分,補集合という3つの集合演算を代数系としてみるというものである.目標の定理はStoneの表現定理と呼ばれるもので,どのようなブール代数もある集合代数に同型であるという主張である.つまり,ブール代数の本質は集合代数である.そこで,本稿では,いくらか電子情報工学への応用を見つつ,目標の定理を示すことにする.

1. Boole代数
- Def.1.1
- Lem.1.2
  - proof
- Lem.1.3
  - Proof
- Lem.1.4
  - Proof
- Lem.1.5
  - Proof
- Ex.1.6
- Ex.1.7
- Ex.1.8
- Def.1.9
- Lem.1.10
  - Proof
- Lem.1.11
  - Proof
- Ex.1.12
- Ex.1.13
- Ex.1.14
- 参考文献

1. Boole代数

Def.1.1

集合 $B$ とその元 $0, 1 \in B \ (0 \neq 1)$ について, $B$ 上の2項演算 $+, \ \cdot$ と $B$ 上の1項演算 $\neg$ が次の公理を満たすとき, $B$ をBoole代数(ブール代数)という.

$(x + y) + z = x + (y + z)$ . (結合律)
$x + y = y + x$ . (交換律)
$x + 0 = x$ . (零元の性質)
$x + x = x$ . (冪等律)
$(x \cdot y) \cdot z = x \cdot (y \cdot z)$ . (結合律)
$x \cdot y = y \cdot x$ . (交換律)
$x \cdot 1 = x$ . (単位元の性質)
$x \cdot x = x$ . (冪等律)
$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ . (分配律)
$x + (y \cdot z) = (x + y) \cdot (x + z)$ . (分配律)
$x + \neg x = 1$ . (補元律)
$x \cdot \neg x = 0$ . (補元律)

ここで, $+$ を加法, $\cdot$ を乗法, $\neg$ を否定という. $0$ を $B$ の零元, $1$ を $B$ の単位元という. $x \in B$ に対し, $x + x' = 1, \ x \cdot x' = 0$ を満たす元 $x' \in B$ を $x$ の補元という.また,否定は加法と乗法よりも結合性が強いものとする.

流儀によって,乗法は加法よりも結合性が強いと定義することもあるが,ここでは加法と乗法との間の結合性に強さの順序を設けないことにする.

Def.1.1の12個の公理を見てみると,実はそれぞれ1, 2, 3, 4, 9, 11は5, 6, 7, 8, 10, 12の式において $0$ を $1$ に, $\cdot$ を $+$ に置き換えた式である.つまり, Boole代数の等式 $t = s$ が成り立てば, $0$ を $1$ に, $\cdot$ を $+$ に置き換えた等式 $t' = s'$ も成り立つことがわかる.逆に, $1$ を $0$ に, $+$ を $\cdot$ に置き換えた場合も成り立つ.これをBoole代数の双対原理という.以後,このことに注意して証明を見てみよう.

まず, Boole代数の基本的な性質について見ていく.

Lem.1.2

Boole代数 $B$ の零元 $0$ と単位元 $1$ は存在すれば一意である.

proof

もうひとつの零元 $0'$ と単位元 $1'$ をとる.このとき,零元の性質と交換律から,

$0' = 0' + 0 = 0 + 0' = 0$

である.また,単位元の性質と交換律から,

$1' = 1' \cdot 1 = 1 \cdot 1' = 1$

である. $\square$

Lem.1.3

Boole代数 $B$ の任意の元 $x$ はただ1つの補元 $\neg x$ をもつ.

Proof

公理から明らかに, $\neg x$ は $x$ の補元である.そこで, $a, b$ を $x$ の補元とする.このとき,

$a = a + 0 = a + (x \cdot b) = (a + x) \cdot (a + b) = 1 \cdot (a + b) = a + b$

である.従って, $a = b$ である. $\square$

Lem.1.4

Boole代数 $B$ は次の性質をもつ.

$x + 1 = 1$ .
$x \cdot 0 = 0$ .
$x + (x \cdot y) = x$ . (吸収律)
$x \cdot (x + y) = x$ . (吸収律)
$\neg \neg x = x$ . (二重否定)
$\neg 0 = 1, \ \neg 1 = 0$ .
$x + y = y \leftrightarrow x \cdot y = x$ .

Proof

(1) $x + 1 = x + (x + \neg x) = (x + x) + \neg x = x + \neg x = 1$ .

(2) $x \cdot 0 = x \cdot (x \cdot \neg x) = (x \cdot x) \cdot \neg x = x \cdot \neg x = 0$ .

(3) $x + (x \cdot y) = (x \cdot 1) + (x \cdot y) = x \cdot (1 + y) = x + 1 = x$ .

(4) $x \cdot (x + y) = (x + 0) \cdot (x + y) = x + (0 \cdot y) = x + 0 = x$ .

(5) 補元律より, $\neg x + \neg \neg x = 1, \ \neg x \cdot \neg \neg x = 0$ なので, $\neg x$ は $\neg \neg x$ の補元である. Lem.1.3より, $\neg \neg x = x$ である.

(6) $0 + 1 = 1, \ 0 \cdot 1 = 0$ より, $\neg 0 = 1, \ \neg 1 = 0$ である.

(7) $x + y = y$ とすると, $x \cdot y = x \cdot (x + y) = (x \cdot x) + (x \cdot y) = x + (x \cdot y) = x$ である.逆に, $x \cdot y = x$ とすると, $x + y = (x \cdot y) + y = (x + y) \cdot (y + y) = (x + y) \cdot y = y$ である. $\square$

Boole代数の有名な性質の1つに, de Morganの法則がある.

Lem.1.5

Boole代数 $B$ は次の性質をもつ.

$\neg (x + y) = \neg x \cdot \neg y$ . (de Morgan律)
$\neg (x \cdot y) = \neg x + \neg y$ . (de Morgan律)

Proof

(1) 右辺が $x + y$ の補元であることを確かめればよい.実際,

$(x + y) + (\neg x \cdot \neg y) = ( (x + y) + \neg x) \cdot ( (x + y) + \neg y) = 1$

かつ

$(x + y) \cdot (\neg x \cdot \neg y) = (x \cdot (\neg x \cdot \neg y) ) + (y \cdot (\neg x \cdot \neg y) ) = 0$

である.

(2) 右辺が $x \cdot y$ の補元であることを確かめればよい.実際,

$(x \cdot y) + (\neg x + \neg y) = (x + (\neg x + \neg y) ) \cdot (y + (\neg x + \neg y) ) = 1$

かつ

$(x \cdot y) \cdot (\neg x + \neg y) = ( (x \cdot y) \cdot \neg x) + ( (x \cdot y) \cdot \neg y) = 0$

である. $\square$

ここまで, Boole代数の基本的な性質について見てきたが,大学で数学を多少学んだことのある人であれば,例えばBoole代数が集合の演算のような働きを見せることがわかるだろう.実際,次のような例が挙げられる.

Ex.1.6

空でない集合 $X$ の冪集合 $\mathcal{P}(X)$ は加法として和集合 $A \cup B$ ,乗法として共通部分 $A \cap B$ ,否定として $X$ における補集合 $X \setminus A = A^c$ ,零元として空集合 $\emptyset$ ,単位元として全体集合 $X$ をもつようなBoole代数である.これを $X$ 上の集合代数(field of sets)という.

最も単純なBoole代数であり,電子情報工学への応用が知られているのは次のものである.

Ex.1.7

$B = 2 = \{ 0, 1 \}$ とおくと,加法として $0 + 0 = 0, \ 1 + 0 = 1, \ 0 + 1 = 1, \ 1 + 1 = 1$ ,乗法として $0 \cdot 0 = 0, \ 1 \cdot 0 = 0, \ 0 \cdot 1 = 0, \ 1 \cdot 1 = 1$ ,否定として $\neg 0 = 1, \ \neg 1 = 0$ ,零元として $0$ ,単位元として $1$ をもつようなBoole代数である.これをスイッチング代数という.

他にも,位相空間の開閉集合全体の族もBoole代数である.この例は後にStoneの表現定理において重要な役割を果たす.

Ex.1.8

空でない位相空間 $X$ の開閉集合全体の族を $\mathrm{clop}(X)$ とおく.このとき, $\mathrm{clop}(X)$ は集合代数と同じ演算によってブール代数である.特に, $X$ が連結ならば, $\mathrm{clop}(X) = \{ \emptyset, X \}$ である.これはスイッチング代数にほかならない.

また, Boole代数に標準的な順序を入れることができる.

Def.1.9

Boole代数 $B$ 上の関係 $\leq$ を次で定める.

$x \leq y :\Longleftrightarrow x + y = y \Longleftrightarrow x \cdot y = x$ .

また,関係 $\lt$ を次で定める.

$x \lt y :\Longleftrightarrow x \leq y \wedge x \neq y$ .

Lem.1.10

Def.1.9で定められるBoole代数 $B$ 上の関係 $\leq$ は順序である.

Proof

(反射律) $x + x = x$ より, $x \leq x$ である.

(反対称律) $x \leq y, \ y \leq x$ とすると, $x + y = y, \ y + x = x$ であるから, $x = y$ である.

(推移律) $x \leq y, \ y \leq z$ とすると, $x + y = y, \ y + z = z$ であるから, $x + z = x + (y + z) = (x + y) + z = y + z = z$ である.よって, $x \leq z$ である. $\square$

以後, $\leq$ はDef.1.9の関係を指すものとする.この順序は次の性質をもつ.

Lem.1.11

Boole代数 $B$ において,次が成り立つ.

$\max B = 1, \ \min B = 0$ .
$x, y \leq x + y, \ x \cdot y \leq x, y$ .
$x, y \leq z \rightarrow x + y \leq z$ .
$z \leq x, y \rightarrow z \leq x \cdot y$ .
$\sup \{ x, y \} = x + y, \ \inf \{ x, y \} = x \cdot y$ .
$x \leq y \rightarrow x + z \leq y + z, \ x \cdot z \leq y \cdot z$ .
$x + y = 1 \leftrightarrow \neg y \leq x$ .
$x \cdot y = 0 \leftrightarrow x \leq \neg y$ .
$x \leq y \leftrightarrow \neg y \leq \neg x$ .

Proof

(1) Lem.1.4(1), (2)より示される.

(2) $x + (x + y) = x + y$ より, $x \leq x + y$ である.また, $(x \cdot y) \cdot x = x \cdot y$ より, $x \cdot y \leq x$ である.

(3) $x, y \leq z$ とすると, $x + z = z, \ y + z = z$ である.よって, $(x + y) + z = (x + y) + (z + z) = (x + z) + (y + z) = z + z = z$ である.故に, $x + y \leq z$ である.

(4) $z \leq x, y$ とすると, $z \cdot x = z, \ z \cdot y = z$ である.よって, $z \cdot (x \cdot y) = (z \cdot z) \cdot (x \cdot y) = (z \cdot x) \cdot (z \cdot y) = z \cdot z = z$ である.故に, $z \leq x \cdot y$ である.

(5) (2)~(4)より示される.

(6) $x \leq y$ とすると, $x + y = y, \ x \cdot y = x$ である.よって, $(x + z) + (y + z) = (x + y) + z = y + z, \ (x \cdot z) \cdot (y \cdot z) = (x \cdot y) \cdot z = x \cdot z$ である.故に, $x + z \leq y + z, \ x \cdot z \leq y \cdot z$ である.

(7) $x + y = 1$ とすると, $y + (\neg y \cdot x) = (y + \neg y) \cdot (y + x) = 1 + 1 = 1$ かつ $y \cdot (\neg y \cdot x) = 0$ なので, $\neg y \cdot x = \neg y$ である.よって, [tex; \neg \leq x]である.逆に, $\neg y \leq x$ とすると, $\neg y + x = x$ である.よって, $x + y = (\neg y + x) + y = 1 + x = 1$ である.

(8) $x \cdot y = 0$ とすると, $y + (x + \neg y) = 1 + x = 1$ かつ $y \cdot (x + \neg y) = (y \cdot x) + (y \cdot \neg y) = 0 + 0 = 0$ なので, $x + \neg y = \neg y$ である.故に, $x \leq \neg y$ である.逆に, $x \leq \neg y$ とすると, $x \cdot \neg y = x$ である.よって, $x \cdot y = (x \cdot \neg y) \cdot y = 0$ である.

(9) $x \leq y$ とすると, $x + y = y$ であるから, de Morgan律から, $\neg x \cdot \neg y = \neg y$ である.よって, $\neg y \leq \neg x$ である.逆に, $\neg y \leq \neg x$ とすると, $\neg x \cdot \neg y = \neg y$ である. de Morgan律から, $\neg (x + y) = \neg y$ なので, $x + y = y$ である.よって, $x \leq y$ である. $\square$

最後に, Boole代数の順序の具体例を見て終わる.

Ex.1.12

空でない集合 $X$ の集合代数 $\mathcal{P}(X)$ の順序は包含関係 $\subset$ である.実際, $A \leq B$ とすると, $A \cap B = A$ であるから, $A \subset B$ が従う.逆に, $A \subset B$ とすると, $A \cap B = A$ なので $A \leq B$ が従う.

Ex.1.13

スイッチング代数 $2$ の順序は明らかに $0 \lt 1$ である.

Ex.1.14

空でない位相空間 $X$ の開閉集合 $\mathrm{clop}(X)$ の順序は集合代数と同様に包含関係 $\subset$ である.

次回はBoole代数におけるイデアルとフィルターについて説明する.

ヒナコフスキーの表現定理

ソフィア=ヒナコフスカヤによる気まぐれ日記帳です

ブール代数入門(1)-ブール代数の定義

1. Boole代数

Def.1.1

Lem.1.2

proof

Lem.1.3

Proof

Lem.1.4

Proof

Lem.1.5

Proof

Ex.1.6

Ex.1.7

Ex.1.8

Def.1.9

Lem.1.10

Proof

Lem.1.11

Proof

Ex.1.12

Ex.1.13

Ex.1.14

参考文献