Bool 代数

在格论中，Bool 代数是一个广泛使用的代数系统。

定义

称一个有补分配格$(S, \leqslant)$为 Bool 格。在这个系统中，一个元素$a \in S$的补元存在且唯一，记其为$\overline{a}.$这样可以引入一个一元运算——补运算。

引入的补运算还具有以下性质：

1. 双余性：$\overline{(\overline{a})} = a;$
2. De Morgan 定理：$\overline{a \lor b} = \overline{a} \land \overline{b}, \overline{a \land b} = \overline{a} \lor \overline{b}.$

Bool 格连同诱导的并、交、补运算组成一个 Bool 代数$(S, \land, \lor, -).$如果$S$是有限集，就称$(S, \land, \lor, -)$是有限 Bool 代数。

原子

在一个具有下界的格$(S, \leqslant)$中，称恰好覆盖下界$0$的元素为一个原子（有关覆盖的概念参见序关系），显然若$a, b$是$(S, \leqslant)$的原子则有$a \land b = 0.$在具有下界的有限格中，对于一个非下界元素$b \in S$至少有一个原子使得$a \leqslant b.$

在 Bool 代数$(S, \land, \lor, -)$中，原子具有更好的性质，例如

1. 任意一个非下界元素$b \in S$都可以写成所有比它小的原子的并，即$$b = \bigvee_{a_k \leqslant b} a_k.$$且这种表示是唯一的。
2. 对任意的非下界元素$b \in S$以及原子$a \in S$，$a \leqslant b$和$a \leqslant \overline{b}$有一者成立。
3. 设$a_0, a_1, \cdots, a_m$是该代数结构的原子，那么$a_0 \leqslant \bigvee_{k=1}^m a_k$当且仅当$a_0$和$\{ a_k \}_{k=1}^n$中的一个相等。

同构

两个 Bool 代数$(S, \land, \lor, -)$和$(T, \land, \lor, -)$同构，是指存在一个双射$\varphi: S \to T$满足

1. 保持交运算：$\varphi(a \land b) = \varphi(a) \land \varphi(b);$
2. 保持并运算：$\varphi(a \lor b) = \varphi(a) \lor \varphi(b);$
3. 保持补运算：$\varphi(\overline{a}) = \overline{\varphi(a)}.$

Stone 定理

任意一个有限 Bool 代数$(S, \land, \lor, -)$都和集合$A$的幂集$(2^A, \cap, \cup, -)$同构，且$A$的元素个数是 Bool 格$S$的所有原子个数。

因此有限 Bool 代数的元素个数必定为$2^n, n \in \N.$其中$n$是该代数中所有原子的个数。

环结构

定义 Bool 代数$(S, \land, \lor, -)$上的对称差运算 $$\forall a, b \in S, \quad a \Delta b = (a \land \overline{b}) \lor (b \land \overline{a}).$$ 那么可以验证代数系统$(S, \Delta, \land)$是以单位元为上界$1$的 Bool 环。

Bool 代数和 Bool 环可以相互诱导，详见 Bool 环。

参考资料

1. S. Burris, H. P. Sankappanavar, A Course in Universal Algebra, GTM Vol.78, Springer, New York, 2011-10, ISBN 978-1-4613-8132-7.