ブール代数 - 而して

Def. Boolean algebra とは, poset $(B, \leq)$ と, その二つの要素 $0, 1 \in B$ の組である. また, $B$ 上の二項演算 join: $a \lor b$ , meet: $a \land b$ , および単項演算 complementation: $\lnot b$ が定義されており, これらは以下の要請を満たす：

$a, b, c \in B$ とするとき,

① $0 \leq a$

② $a \leq 1$

③ $a \leq c$ and $b \leq c$ $\Longleftrightarrow$ $a \lor b \leq c$

④ $c \leq a$ and $c \leq b$ $\Longleftrightarrow$ $c \leq a \land b$

⑤ $a \leq \lnot b$ $\Longleftrightarrow$ $a \land b = 0$

⑥ $\lnot \lnot a = a$ .

Remark. poset $(B, \leq)$ とは, 集合 $B$ と, $B$ 上の半順序 $\leq$ の組である. $B$ 上の半順序 $\leq$ とは, $B$ 上の二項関係, つまり直積の部分集合 $\leq\,\subseteq B \times B$ であって, $a, b, c \in B$ として, 以下の要請：

（反射律） $a \leq a$

（推移律） $a \leq b$ and $b \leq c$ $\Longrightarrow$ $a \leq c$

（反対称律） $a \leq b$ and $b \leq a$ $\Longrightarrow$ $a= b$

を満たすものである.

ブール代数と聞くと集合 $\{0,1\}$ , もしくは $\{ \text{true}, \text{false} \}$ 上の演算を思い浮かべてしまうのだが, 順序を含めて拡張してもこれだけの公理でうまく定義できているので驚いた。ここから諸定理を示すのはそこまで難しくないが, ファインマンの三角関数よろしく, 一通りまとめてみようと思う。

Lem. （ $\lor$ , $\land$ の基本公式） $a \leq a \lor b$ , $b \leq a \lor b$ および $a \land b \leq a$ , $a \land b \leq b$ .

proof. $\leq$ の反射律から $a \lor b \leq a \lor b$ だから, ③より $a \leq a \lor b$ and $b \leq a \lor b$ . 後者は④から従う. 終

Lem. （ $\lor$ , $\land$ の可換則） $a \lor b = b \lor a$ および $a \land b = b \land a$ .

proof. 基本公式より $b \leq a \lor b$ and $a \leq a \lor b$ が成り立つので, ③から $b \lor a \leq a \lor b$ . 同様にして（ $a, b$ を入れ替えると考えてもよい）, $a \lor b \leq b \lor a$ . $\leq$ の反対称律から $a \lor b = b \lor a$ . 後者は④から従う. 終

Lem. （ $\lnot$ と $\leq$ の関係） $a \leq b$ $\Longleftrightarrow$ $\lnot b \leq \lnot a$ .

proof. ⑤⑥から $a \leq b$ $\Longleftrightarrow$ $a \leq \lnot \lnot b$ $\Longleftrightarrow$ $a \land \lnot b = 0$ . $\land$ の可換則からこれらは $\lnot b \land a = 0$ と同値で, ⑤から $\lnot b \leq \lnot a$ と同値. 終

Lem. （De Morganの法則） $\lnot (a \lor b) = \lnot a \land \lnot b$ および $\lnot (a \land b) = \lnot a \lor \lnot b$ .

proof. 基本公式から $a \leq a \lor b$ より, 両辺で $\lnot$ をとり $\lnot (a \lor b) \leq \lnot a$ . $a, b$ を入れ替え, 可換則から $\lnot (a \lor b) \leq \lnot b$ . ④から $\lnot (a \lor b) \leq \lnot a \land \lnot b$ .

一方, 基本公式から $\lnot a \land \lnot b \leq \lnot a$ で, 両辺で $\lnot$ をとり⑥から $a = \lnot \lnot a \leq \lnot (\lnot a \land \lnot b)$ . 同様に $b \leq \lnot (\lnot a \land \lnot b)$ . ③から $a \lor b \leq \lnot (\lnot a \land \lnot b)$ . 再び両辺で $\lnot$ をとって $\lnot a \land \lnot b \leq \lnot (a \lor b)$ . よって $\leq$ の反対称律から結論の前者が従う. 後者は, 前者の $a, b$ が任意であることから, $a$ を $\lnot a$ に, $b$ を $\lnot b$ に置き換え $\lnot (\lnot a \lor \lnot b) = \lnot \lnot a \land \lnot \lnot b$ が得られるので, 両辺で $\lnot$ をとって⑥により（「二重否定」を除去することで）従う. 終

Lem. （無矛盾律と排中律） $a \land \lnot a = 0$ および $a \lor \lnot a = \lnot 0$ .

proof. ⑤で $b = \lnot a$ とすると, ⑥から $a \leq \lnot \lnot a = a$ は $\leq$ の反射律から成立つので, $a \land \lnot a = 0$ . De Morganの法則と $\lor$ の可換則, および⑥から $\lnot (a \land \lnot a) = \lnot a \lor \lnot \lnot a = a \lor \lnot a = \lnot 0$ . 終

ex1. $0 \neq 1$ として $\mathbf{2} = \{0,1\}$ . おなじみの二値集合である.

ここで $\leq$ の指定がないのは, もろもろの条件によって自然に定まるからである. すなわち, この集合がboolean algebraとなり得るように $\mathbf{2}$ 上の半順序 $\leq\,\subseteq \mathbf{2} \times \mathbf{2}$ を定義する場合, $\leq$ が半順序であることから, 反射律より $(0,0), (1,1) \in\,\leq$ . また公理の要請①②から $(0,1) \in\,\leq$ . ここで $(1,0) \in\,\leq$ とすると $0 \leq 1$ かつ $1 \leq 0$ と反対称律から $0 = 1$ となって仮定に反するので $(1,0) \notin\,\leq$ でなければならない. したがって, $\leq\,= \{(0,0),(0,1),(1,1)\}$ と一意に定まり, 逆にこの $\leq$ は半順序である.

また, 実は $\lnot 0 = 1$ かつ $\lnot 1 = 0$ であるしかない：⑤と $\land$ の可換則から $a \leq \lnot b$ $\Longleftrightarrow$ $a \land b = 0$ $\Longleftrightarrow$ $b \land a = 0$ $\Longleftrightarrow$ $b \leq \lnot a$ だから, もし $\lnot c = c$ なる $c$ が存在すれば, 任意の $a$ について $a \leq \lnot a$ となり, $a$ を $\lnot a$ で置き換え⑥を使えば $\lnot a \leq \lnot \lnot a = a$ ゆえ, 任意の $a$ について $\lnot a = a$ が従う. しかるに, これにより先の同値は $a \leq b$ $\Longleftrightarrow$ $b \leq a$ とかけるので, 反対称律から任意の $a, b$ につき $a=b$ となり, これは $0 \neq 1$ に反する. 従って, 任意の $c$ につき $\lnot c \neq c$ でなければならない.

つまり「 $0 \neq 1$ として $\mathbf{2} = \{0,1\}$ 」という言明だけで, 他の言及がなくとも, 半順序と単項演算 $\lnot$ は自然に定まっているのである. 特に, 以上の流れから分かるように, $0 \neq 1$ という点が本質的である.

いわゆる「真理値表」を作ってみよう. $\lnot$ は先に見たとおり.

$\land$ については⑤より $0 \land 0 = 0$ , $0 \land 1 = 1 \land 0 = 0$ . また $1 \leq 1$ より, ④から $1 \leq 1 \land 1$ . 逆に②から $1 \land 1 \leq 1$ ゆえ $1 \land 1 = 1$ .

$\lor$ についてはDe Morganの法則から, それぞれ $1 \lor 1 = 1$ , $1 \lor 0 = 0 \lor 1 = 1$ , $0 \lor 0 = 0$ が従う.

ex2. 集合 $X$ の冪集合 $2 ^ {X}$ . $\leq\,=\,\subseteq$ , $0 = \emptyset$ , $1 = X$ , $\lor = \cup$ , $\land = \cap$ , $\lnot A = A ^ {c} = X \backslash A$ とすれば, $2 ^ X$ はboolean algebraとなる. 特に, $\mathbf{2}$ は $\mathbf{1} = \{\ast\}$ （一元集合）の冪集合とみなせる： $\mathbf{2} \cong 2 ^ {\mathbf{1}}$ .

Reference. Awodey, S. (2010) Category Theory, Oxford: Oxford University Press, 2nd ed. 2011.