布爾代數與邏輯函數代數

代數運算不一定是數的加法和乘法。邏輯與、或、非構成布爾代數。另一種表示使用模 2 運算，其中加法成為異或。研究邏輯函數可具體區分這些運算，並給出一個具有原子和商的完整有限模型。

1 布爾運算與序

布爾代數具有交 $a\wedge b$、並 $a\vee b$、補 $\neg a$，以及特殊元素 0 和 1。交與並滿足結合律、交換律、吸收律及相互分配律；0 和 1 滿足 $a\vee0=a$、$a\wedge1=a$；補滿足 $a\wedge\neg a=0$、$a\vee\neg a=1$。

序關係 $a\le b$ 的意思是 $a\wedge b=a$。由於公理蘊含冪等性，它具有自反性。例如，結合 $a\vee0=a$ 與吸收律得到 $a\wedge a=a$。反對稱性來自交換律；傳遞性來自結合律：若 $a\wedge b=a$ 且 $b\wedge c=b$，則 $a\wedge c=(a\wedge b)\wedge c=a\wedge(b\wedge c)=a$。

補是唯一的。若 $b,c$ 均為 $a$ 的補，分配律給出 $b=b\wedge(a\vee c)=b\wedge c$ 及 $c=c\wedge(a\vee b)=b\wedge c$。故 $b=c$。驗證 $\neg a\wedge\neg b$ 是 $a\vee b$ 的補並利用唯一性，可得德摩根律；對偶論證給出另一條。

對集合而言，交是集合交、並是集合併、補是相對於全集的補，0 是空集，1 是全集。對按邏輯等價分類的命題而言，它們分別是合取、析取、否定、假與真。邏輯蘊含對應此序，而不是任意表達式之間普通的數值不等式。

2 有限賦值集上的所有邏輯函數

令 $X=\{0,1\}^n$ 為 $n$ 個變量所有真值賦值的集合，共有 $2^n$ 個賦值。邏輯函數是任意映射 $f:X\to\{0,1\}$，運算逐點進行。選出取值為 1 的賦值，就將函數與 $X$ 的子集對應起來，因此這些函數構成有 $2^{2^n}$ 個元素的布爾代數。

原子是極小的非零元素。這裏原子是恰好一個賦值的指示函數。對變量 $p,q$，四個原子為

$$p\wedge q,\quad p\wedge\neg q,\quad\neg p\wedge q,\quad\neg p\wedge\neg q.$$

每個邏輯函數都是使其為真的賦值原子的並。這就是析取範式。作為選定的原子子集，它是唯一的，儘管寫出的表達式可以有許多代數等價形式。

例。 異或恰在賦值 $(p,q)=(1,0),(0,1)$ 為真，因此

$$p\mathbin{\mathrm{XOR}}q=(p\wedge\neg q)\vee(\neg p\wedge q).$$

包含性或還包括原子 $p\wedge q$，故是不同函數。吸收律將 $p\vee(p\wedge q)$ 化簡為 $p$，但對任意實數輸入，相應的實數恆等式 $p+(pq)=p$ 並不成立。

3 布爾環運算

在同一函數集上，按 $\mathbb F_2$ 逐點定義加法和乘法。乘法是交，加法是異或。由於每個值是 0 或 1，每個函數都滿足 $f^2=f$。這樣的含單位交換環稱為布爾環。

在任意布爾環中，$2\cdot1=0$，因為 $(1+1)^2=1+1$ 給出 $4\cdot1=2\cdot1$。因此 $a+a=0$。非零布爾環的特徵為 2；如果允許零環，它是慣例上的例外。並與補可恢復為

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

對於邏輯函數，可代入四種真值對驗證並的公式。在抽象布爾環中，利用 $a^2=a$ 和 $a+a=0$ 展開，可驗證同樣的格律。例如 $a(a+b+ab)=a+ab+ab=a$，證明吸收律；而 $(a+b+ab)+c+(a+b+ab)c$ 關於三個元素對稱，證明並的結合律。

若布爾環是整環，則僅含 0 和 1：$a(a-1)=0$ 迫使 $a=0$ 或 $a=1$。因此唯一的非零布爾域是 $\mathbb F_2$。四元素域不是布爾域，儘管其特徵也是 2。特徵為 2 本身並不蘊含每個元素冪等。

4 有限原子與商的例子

在任意有限布爾代數中，每個非零元素之下都有原子：取極小的非零下界即可。不同原子的交為零。每個元素等於其下所有原子的並：若它們的並 $s$ 嚴格小於 $a$，則 $a\wedge\neg s$ 非零，並包含另一個原子，與 $s$ 的定義矛盾。因此每個有限布爾代數都是其原子的冪集代數；若有 $k$ 個原子，便有 $2^k$ 個元素。

作為具體環商，取逐坐標運算的 $R=\mathbb F_2^3$ 與理想 $I=\{(a,0,0):a\in\mathbb F_2\}$。投影 $(a,b,c)\mapsto(b,c)$ 是核為 $I$ 的滿環同態，給出 $R/I\cong\mathbb F_2^2$。忘掉一個坐標移除一個原子，使布爾代數從八個元素減至四個。商乘法有效是因為 $I$ 是理想，而不只是因為底層集合有限。

在完整構造前，先用本章符號證明兩條補元等式及第一條分配律。由 $a^2=a$ 和 $a+a=0$，有 $a(1+a)=a+a^2=0$，且 $a+(1+a)+a(1+a)=1$。又有 $a(b\vee c)=ab+ac+abc=(ab)\vee(ac)$，最後一步使用 $a^2=a$。因此這些規律已在此處證明，無須借用其他章節。

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

偏序結論可從已列公理推導。吸收律給出 $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$，它沒有原子，所得為無原子集合（空集）的一元素冪集。這裏沒有聲稱每個無限布爾代數都是完整冪集。

5 分級練習

E1 基礎。 三個變量有多少個賦值、原子和邏輯函數？

E2 化簡。 化簡 $(p\wedge q)\vee(p\wedge\neg q)$。用布爾環記號寫出異或，並與並比較。

E3 結構。 有限布爾代數能有 12 個元素嗎？若有 32 個元素，它有多少原子？

E4 環。 證明 $\mathbb Z/4\mathbb Z$ 不是布爾環，並解釋四元素域也不是布爾環。

E5 商。 在 $\mathbb F_2^4$ 中投影到第 1 和第 4 坐標。求核、商的大小以及商布爾代數的原子個數。

6 詳解

S1. 有 $2^3=8$ 個賦值及八個賦值原子。邏輯函數在每個賦值處獨立選擇 0 或 1，因此有 $2^8=256$ 個函數。混淆變量與賦值會錯誤地只得到八個函數。

S2. 分配律給出 $p\wedge(q\vee\neg q)=p$。在布爾環中異或為 $p+q$，而並為 $p+q+pq$。當兩個輸入均為 1，異或為 0、並為 1，故不能混淆兩種運算。

S3. 不能，因為 12 不是 2 的冪。32 元素布爾代數有五個原子，其元素是這五個原子的所有子集。

S4. 模 4 有 $[2]^2=[0]\ne[2]$，違反冪等性。布爾整環至多有 0 和 1 兩個元素，因此四元素域不能是布爾環。等價地，其滿足 $\alpha^2=\alpha+1$ 的元素 $\alpha$ 不冪等。

S5. 核為 $\{(0,a,b,0):a,b\in\mathbb F_2\}$。像為 $\mathbb F_2^2$，故商有四個元素和兩個原子。第一同構定理給出商的對應。

小結

布爾代數組織邏輯與集合運算，其有限結構由原子控制。邏輯函數提供完整的具體模型。布爾環加法是異或而不是包含性或，僅有特徵為 2 並不足夠。理想與商映射將邏輯代數直接聯繫到環結構。