布爾代數與布爾環

邏輯合取、集合併與冪等元素的乘法遵循相關的代數規律。布爾代數使這種關係精確化。它不同於普通實數算術：重複一個邏輯命題不會增加第二份，而布爾環的加法表示異或，不是包含性或。

1 格運算與補元

布爾代數是帶有交運算 $a\wedge b$、並運算 $a\vee b$、補元 $\neg a$ 和元素 0、1 的集合 $B$，滿足交換律、結合律、吸收律、各運算對另一運算的分配律、單位律 $a\vee0=a$、$a\wedge1=a$，以及補元律

$$a\vee\neg a=1,\qquad a\wedge\neg a=0.$$

吸收律為 $a\wedge(a\vee b)=a$ 和 $a\vee(a\wedge b)=a$。當 $a\wedge b=a$ 時定義 $a\le b$。這些規律使它成為偏序，且並和交分別是最小上界和最大下界。

對任意集合 $X$，冪集 $\mathcal P(X)$ 在交、並和相對於 $X$ 的補運算下是布爾代數，0 為空集，1 為 $X$。按邏輯等價取類的命題在與、或、非運算下給出另一個例子。二元素代數 $\{0,1\}$ 是真值模型。

補元唯一。若 $b,c$ 都是 $a$ 的補元，則

$$b=b\wedge1=b\wedge(a\vee c)=(b\wedge a)\vee(b\wedge c)=b\wedge c,$$

同理 $c=b\wedge c$，故 $b=c$。

De Morgan 律。 $\neg(a\vee b)=(\neg a)\wedge(\neg b)$，且 $\neg(a\wedge b)=(\neg a)\vee(\neg b)$。

證明。 分配律與補元律表明 $(\neg a)\wedge(\neg b)$ 與 $a\vee b$ 的交為 0、並為 1。例如交展開為含有 $a\wedge\neg a$ 或 $b\wedge\neg b$ 的各項，而並等於 $[(a\vee b)\vee\neg a]\wedge[(a\vee b)\vee\neg b]=1$。補元唯一性證明第一個等式；交換交和並即可得到第二個。$\square$

2 布爾環使用不同的加法

這裏的布爾環指每個元素都冪等（$a^2=a$）的含單位元交換環。它滿足 $2\cdot1=0$：由 $(1+1)^2=1+1$ 得 $4=2$，故 $2=0$。因此非零布爾環的特徵為 2；即使允許零環，每個 $a$ 也滿足 $a+a=0$。

由這樣的環定義

$$a\wedge b=ab,\qquad a\vee b=a+b+ab,\qquad\neg a=1+a.$$

這些運算給出布爾代數。補元等式立即成立：$a(1+a)=a+a^2=0$，$a+(1+a)+a(1+a)=1$。吸收律來自 $a(a+b+ab)=a+ab+ab=a$。展開兩邊並使用 $a^2=a$ 可得交對並的分配律；並的結合律兩種分組都展開為

$$a+b+c+ab+ac+bc+abc.$$

其他格規律可用同樣的環展開或補元得到。因此這個構造不只是表面類比，而是確實滿足公理。

對集合，布爾環的乘法是交，加法是對稱差

$$A\triangle B=(A\setminus B)\cup(B\setminus A).$$

每個點的成員關係將這些運算對應到模 2 的乘法和加法，逐點證明環規律。包含性並則是 $A\triangle B\triangle(A\cap B)$。

3 有限布爾代數中的原子

原子是在 $\le$ 下極小的非零元素。在有限布爾代數中，每個非零元素下方都有原子：從它的非零下界組成的有限非空集合取一個極小元素即可。不同原子的交為零；否則非零交會因極小性迫使它們相等。

每個元素 $a$ 都是它下方原子的並。設這些原子的並為 $s\le a$。若 $s\ne a$，則 $a\wedge\neg s\ne0$；否則 $a=a\wedge(s\vee\neg s)=a\wedge s\le s$。$a\wedge\neg s$ 下方的原子將是 $a$ 下方卻被 $s$ 遺漏的原子，矛盾。因此將 $a$ 映到其下方原子的集合，就把有限布爾代數識別為其原子集合的冪集。特別地，其元素個數對某個 $k$ 為 $2^k$，不是任意有限數。

偏序、兩個方向的環構造與有限表示

偏序結論可從已列公理推導。吸收律給出 $a\wedge a=a$、$a\vee a=a$，從而關係 $\le$ 自反；交換律給出反對稱性。若 $a\wedge b=a$、$b\wedge c=b$，則 $a\wedge c=(a\wedge b)\wedge c=a\wedge(b\wedge c)=a$，故關係傳遞。元素 $a\wedge b$ 在兩個因子下方；任意公共下界 $u$ 滿足 $u\wedge(a\wedge b)=u$，所以它是最大下界。吸收律說明 $a\vee b$ 為上界；若 $a,b\le c$，分配律給出 $(a\vee b)\wedge c=(a\wedge c)\vee(b\wedge c)=a\vee b$，證明它是最小上界。

在由布爾環構造代數的方向，另一條分配律與吸收律可明確寫成

$$(a\vee b)\wedge(a\vee c)=a+bc+abc=a\vee(b\wedge c), \qquad a\vee(a\wedge b)=a+ab+a^2b=a.$$

交的結合律、交換律和單位元 1 來自環乘法；並滿足交換律、單位元為 0，結合律由前述展開式給出。此外 $a\vee a=a$、$a\wedge a=a$。連同兩條補元等式和前面已證的另一條分配律，這就核對了列出的全部布爾代數公理。

反過來，在任意布爾代數中定義

$$a\oplus b=(a\wedge\neg b)\vee(\neg a\wedge b),\qquad a\cdot b=a\wedge b.$$

第一種運算滿足交換律、單位元為 0，且 $a\oplus a=0$。為證明而非假設結合律，用 De Morgan 律展開 $(a\oplus b)\oplus c$ 或 $a\oplus(b\oplus c)$，兩者均為下列四個互不相交項的並：

$$(a\wedge\neg b\wedge\neg c)\vee (\neg a\wedge b\wedge\neg c)\vee (\neg a\wedge\neg b\wedge c)\vee (a\wedge b\wedge c).$$

分別從 $a,\neg a$、$b,\neg b$、$c,\neg c$ 各選一個得到的八項兩兩相交為零，且並為 1；這由展開 $(a\vee\neg a)\wedge(b\vee\neg b)\wedge(c\vee\neg c)$ 得到。因此上述展開無須預先假設集合表示。展開 $a\wedge(b\oplus c)$ 得 $(a\wedge b\wedge\neg c)\vee(a\wedge\neg b\wedge c)$；展開 $(a\wedge b)\oplus(a\wedge c)$ 也得同式，所以乘法對 $\oplus$ 分配。交提供滿足結合律、交換律、含單位元 1 且冪等的乘法。至此所有環公理均已證明。公式 $a\oplus b\oplus(a\wedge b)=a\vee b$ 與 $1\oplus a=\neg a$ 恢復原運算。

最後，有限原子映射確實是同構，而不只是計數。對原子 $t$，每個 $t\wedge a$ 只能為 $0$ 或 $t$。因此 $t\le a\vee b$ 當且僅當 $t\le a$ 或 $t\le b$；$t\le\neg a$ 當且僅當 $t\not\le a$。這證明了並與補元被保持；交的保持是直接的。每個元素都是其原子的並，故映射單射。對有限原子集的任意子集，取其中全部原子的並；互不相交性說明所得元素下方的原子恰為所選子集，從而滿射。若允許退化代數 $0=1$，它沒有原子，所得為無原子集合（空集）的一元素冪集。這裏沒有聲稱每個無限布爾代數都是完整冪集。

4 分級練習

E1 基礎。 設 $X=\{1,2,3\}$、$A=\{1,2\}$、$B=\{2,3\}$，計算交、並、布爾環和以及 $A$ 的補集。

E2 代數。 用布爾環公式驗證 $a\vee a=a$，並與 $a+a$ 比較。

E3 有限結構。 布爾代數能恰有六個元素嗎？16 元布爾代數有多少原子？

E4 邏輯。 化簡 $(p\wedge q)\vee(p\wedge\neg q)$，並解釋為甚麼不涉及概率假設。

5 完整解答

S1. 交為 $\{2\}$，並為 $X$，環和為 $\{1,3\}$，且 $\neg A=\{3\}$。環和不含共有元素 2，而並包含它。

S2. $a\vee a=a+a+a^2=0+a=a$。相反，環加法給出 $a+a=0$。因此不說明約定而用同一加號表示並和環加法會產生歧義。

S3. 不能：有限布爾代數的大小是 2 的冪。由於 $16=2^4$，它有四個原子。

S4. 由分配律得 $p\wedge(q\vee\neg q)=p\wedge1=p$。這是對所有真值賦值都成立的邏輯恆等式，不是獨立性陳述或概率計算。

總結

布爾代數抽象集合與邏輯運算。布爾環以冪等乘法和特徵為二的加法編碼同樣的模式。包含性或與異或是不同運算。有限布爾代數由其原子決定，因此大小是 2 的冪。