布爾代數

布爾代數（Boolean algebra）在抽象代數中是指捕獲了集合運算和邏輯運算二者的根本性質的一個代數結構（就是說一組元素和服從定義的公理的在這些元素上運算）。特別是，它處理集合運算交集、併集、補集；和邏輯運算與、或、非。

<image>

例如，邏輯斷言陳述 $a$ 和它的否定 $\neg a$ 不能都同時為真。

$a\land(\lnot a) = \mbox{FALSE}$。

相似於集合論斷言子集A和它的補集 $A^C$ 有空交集。

$A\cap(A^C) = \varnothing$。

因為真值可以在邏輯電路中表示為二進位數或電平，這種相似性同樣擴展到它們，所以布爾代數在電子工程和電腦科學中同在數理邏輯中一樣有很多實踐應用。在電子工程領域專門化了的布爾代數也叫做邏輯代數，在電腦科學領域專門化了布爾代數也叫做布爾邏輯。

布爾代數也叫做布爾格。關聯于格（特殊的偏序集合）是在集合包含 $A\subseteq B$ 和次序 $a \leq b$ 之間的相似所預示的。考慮 $\{x,y,z\}$ 的所有子集按照包含排序的格。這個布爾格是偏序集合，在其中 $\{x\} \leq \{x,y\}$。任何兩個格的元素，比如 $p= \{x,y\}$ 和 $q= \{y,z\}$，都有一個最小上界，這裡是 $\{x,y,z\}$，和一個最大下界，這裡是 $\{y\}$。這預示了最小上界（並或上確界）被表示為同邏輯OR一樣的符號 $p \lor q$；而最大下界（交或下確界）被表示為同邏輯AND一樣的符號 $p \land q$。

這種格釋義有助於一般化為海廷代數，它是免除要麼一個陳述要麼它的否定必須為真的限制的布爾代數。海廷代數對應於直覺邏輯，而布爾代數對應於經典邏輯。

布爾代數又譯為布爾代數。布爾代數得名於喬治·布爾，他是愛爾蘭科克的皇后學院的英國數學家。布林（boolean）在英文中的意思是「布爾的」，這是為了表彰布爾的貢獻，而「布林」只是一種音譯。

## 歷史

術語「布爾代數」得名於喬治·布爾（1815–1864），他是自學成材的英國數學家。他最初在1847年出版的一個小冊子《邏輯的數學分析》中介入了代數邏輯系統，用來響應在奧古斯都·德·摩根和William Hamilton之間的公開論戰，後來又出現在1854年出版的更充實的書《思維規律》中。布爾的公式化在一些重要方面不同於上述描述。例如，布爾的合取和析取不是一對對偶的運算。布爾代數出現在1860年代威廉姆·斯坦利·傑文斯和查爾斯·皮爾士的論文中。到了1890年Ernst Schröder寫的《Vorlesungen》，我們才有了布爾代數和分配格的首次系統表述。首次用英語寫的對布爾代數的廣泛處置是阿弗烈·諾夫·懷海德在1898年的《泛代數》。在現代公理化意義上的作為公理化代數結構的布爾代數開始於Edward Vermilye Huntington 1904年的論文。布爾代數隨著Marshall Stone在1930年代的工作和Garrett Birkhoff在1940年的《格理論》而進入了嚴肅數學時期。在1960年代，Paul Cohen、Dana Scott和其他人使用布爾代數的分支也就是力迫和布爾值模型，深入發現了數理邏輯和公理化集合論中的新成果。

## 形式定義

布爾代數是一個集合 $A$，其上定義了以下結構：

- 二元運算$\land$：$A \times A \rightarrow A$。
- 二元運算$\lor$：$A \times A \rightarrow A$。
- 一元運算$\lnot$：$A \rightarrow A$。
- 零元運算（常數）0和1。

這些運算滿足以下條件：$\forall a, b, c\in A$。

$a \lor (b \lor c) = (a \lor b) \lor c$｜$a \land (b \land c) = (a \land b) \land c$｜結合律

$a \lor b = b \lor a$｜$a \land b = b \land a$｜交換律

$a \lor (a \land b) = a$｜$a \land (a \lor b) = a$｜吸收律

$a \lor (b \land c) = (a \lor b) \land (a \lor c)$｜$a \land (b \lor c) = (a \land b) \lor (a \land c)$｜分配律

$a \lor \lnot a = 1$｜$a \land \lnot a = 0$｜互補律

上面的前三對公理：結合律、交換律和吸收律，意味著 $(A, \land, \lor)$ 是一個格。所以布爾代數也可以定義為一個有補分配格。

從這些公理可以推出元素0、元素1和任何元素 $a$ 的補 $\lnot a$ 都能被唯一確定。

另外，$\forall a, b\in A$，下列恆等式也成立：

$a \lor a = a$｜$a \land a = a$｜冪等律

$a \lor 0 = a$｜$a \land 1 = a$｜有界律

$a \lor 1 = 1$｜$a \land 0 = 0$

$\lnot 0 = 1$｜$\lnot 1 = 0$｜0和1是互補的

$\lnot (a \lor b) = \lnot a \land \lnot b$｜$\lnot (a \land b) = \lnot a \lor \lnot b$｜德·摩根定律

$\lnot \lnot a = a$｜對合律

值得注意的是，如果 $A$ 滿足互補律、交換律、分配律、和第一組有界律這四條公理，那麼所有其他的公理都能從這四條公理中推出。

### 其它運算

在上述基本定義基礎上，布爾代數中常見的還有以下的運算：

- 二元運算 $-$：$A \times A \rightarrow A$，定義為：$a-b = a\land b'$。
- 二元運算 $+$ 或 $\Delta$：$A \times A \rightarrow A$，定義為：$a+b = (a-b)\lor (b-a)$。
- 二元運算→：$A \times A \rightarrow A$，定義為：$a\rightarrow b = (a-b)'$。
- 二元運算↔：$A \times A \rightarrow A$，定義為：$a\leftrightarrow b = (a\rightarrow b)\land (b\rightarrow a)$。
- 二元運算|或↑:$A \times A \rightarrow A$，定義為：$a|b = (a\land b)'$。
- 二元運算⊕或↓: $A \times A \rightarrow A$，定義為：$a\oplus b = a'\land b'$

注意：-和→，+和↔是對偶的。即$a\rightarrow b = (a-b)'$，$a\leftrightarrow b=(a+b)'$。

### 總結

布爾代數的各種運算同時也被應用於集合論和邏輯學，在不同的上下文有不同的名稱。具體的符號和名稱如下：

運算符號｜布爾代數｜集合論｜邏輯學｜邏輯閘｜文氏圖

0或$\bot$｜底｜空集｜偽｜低電位｜

<image>

1或$\top$｜頂｜全集｜真｜高電位｜

<image>

¬或~或'或c｜補集｜非｜反相器｜

<image>

∧或∩｜下確界｜交集｜與｜及閘｜

<image>

∨或∪｜上確界｜聯集｜或｜或閘｜

<image>

$\not\leftarrow$或$\not\subset$｜補｜相對補集｜

<image>

-或$\not\rightarrow$｜減｜差集｜實質非蘊涵｜蘊含非閘｜

<image>

⊕或Δ｜對稱差｜對稱差｜異或｜異或閘｜

<image>

→｜條件｜條件｜蘊含閘｜

<image>

↔｜雙向條件｜雙條件｜同或閘｜

<image>

或↑｜謝費爾豎線｜與非｜反及閘｜

<image>

↓｜皮爾斯箭頭｜或非｜反或閘｜

<image>

## 例子

- 最簡單的布爾代數只有兩個元素0和1，並通過如下規則定義:

- 它應用於邏輯中，解釋0為「偽」，1為「真」，∧為「與」，∨為「或」，¬為「非」。涉及變量和布爾運算的表達式代表了陳述形式，兩個這樣的表達式可以使用上面的公理證實為等價的，若且唯若對應的陳述形式是邏輯等價的。
- 兩元素的布爾代數也是在電子工程中用於電路設計；這裡的0和1代表數字電路中一個位的兩種不同狀態，典型的是高和低電壓。電路通過包含變量的表達式來描述，兩個這種表達式對這些變量的所有的值是等價的，若且唯若對應的電路有相同的輸入-輸出行為。此外，所有可能的輸入-輸出行為都可以使用合適的布爾表達式來建摸。
- 兩元素布爾代數在布爾代數的一般理論中也是重要的，因為涉及多個變量的等式是在所有布爾代數中普遍為真，若且唯若它在兩個元素的布爾代數中為真（這總是可以通過平凡的窮舉法演算法證實）。比如證實下列定律（「合意定理」）在所有布爾代數中是普遍有效的:
- $$(a \lor b) \land (\neg a \lor c) \land (b \lor c) \equiv (a \lor b) \land (\neg a \lor c)$$
- $$(a \land b) \lor (\neg a \land c) \lor (b \land c) \equiv (a \land b) \lor (\neg a \land c)$$
- 任何給定集合 $S$ 的冪集（子集的集合）形成有兩個運算 $\lor:= \cup$（並）和 $\land:= \cap$（交）的布爾代數。最小的元素0是空集而最大元素1是集合 $S$ 自身。
- 有限的或余有限的集合 $S$ 的所有子集的集合是布爾代數。
- 對於任何自然數 $n$，$n$ 的所有正約數的集合形成一個分配格，如果我們對 $a|b$ 寫 $a \leq b$。這個格是布爾代數若且唯若 $n$ 是無平方數因數的數。這個布爾代數的最小的元素0是自然數1；這個布爾代數的最大元素1是自然數n。
- 布爾代數的另一個例子來自拓撲空間：如果 $X$ 是一個拓撲空間，它既是開放的又是閉合的，$X$ 的所有子集的搜集形成有兩個運算$\lor:= \cup$（並）和$\land:= \cap$（交）的布爾代數。
- 如果 $R$ 是一個任意的環，並且我們定義「中心冪等元」（central idempotent）的集合為$A=\{e \in R: e^2=e, ex=xe, \forall x \in R\}$，則集合A成為有兩個運算 $e \lor f:= e + f + ef$ 和 $e \land f := ef$的布爾代數。

## 原型布爾代數

在 $k$ 元素集合 $X$ 上有 $k^{k^n}$個 $n$ 元運算 $f:X^n \rightarrow X$，因此在 $\{0,1\}$ 上有 $2^{2^n}$個 $n$ 元運算。所以得出所有布爾代數，不論大小都兩個常量或「零元」運算，四個一元運算，16個二元運算，256個三元運算，以此類推，它們叫做給定布爾代數的布爾運算。只有一個例外就是一個元素的布爾代數，它叫做退化的或平凡的（被一些早期作者禁用），布爾代數的所有運算可以被證明是獨特的。（在退化情況下，給定元數的所有運算都是同樣的運算因為對所有輸入都返回同樣結果。）

在 $\{0,1\}$ 上的運算可以用真值表展出，選取0和1為真值假和真。它們可以按統一和不依賴應用的方式列出，允許我們命名或至少單獨列出它們。這些名字對布爾運算提供方便的簡寫。$n$ 元運算的名字是 $2^n$ 位的二進位數。有 $2^{2^n}$ 個這種運算，你不能得到更簡明的命名法了!

下面展示元數從0到2的所有運算的這種格局和關聯的名字。

0｜1｜x0｜1f0｜1f1｜1f2｜1f3 0｜0｜1｜0｜1 1｜0｜0｜1｜1

x0｜x1｜2f0｜2f1｜2f2｜2f3｜2f4｜2f5｜2f6｜2f7｜2f8｜2f9｜2f10｜2f11｜2f12｜2f13｜2f14｜2f15 0｜0｜0｜1｜0｜1｜0｜1｜0｜1｜0｜1｜0｜1｜0｜1｜0｜1 1｜0｜0｜0｜1｜1｜0｜0｜1｜1｜0｜0｜1｜1｜0｜0｜1｜1 0｜1｜0｜0｜0｜0｜1｜1｜1｜1｜0｜0｜0｜0｜1｜1｜1｜1 1｜1｜0｜0｜0｜0｜0｜0｜0｜0｜1｜1｜1｜1｜1｜1｜1｜1

這些表格繼續到更高元數上，對 $n$ 元有 $2^n$ 行，每個行給出 $n$ 個變量$x_0,\cdots,x_{n-1}$的一個求值或綁定，而每列都有表頭 $^n\!f_i$，它們給出第 $i$ 個 $n$ 元運算 $^n\!f_i (x_0,\cdots,x_{n-1})$ 在這個求值下的值。運算包括變量本身，例如 $^1\!f_2$ 是 $x_0$ 而 $^2\!f_{10}$ 是$x_0$（作為它的一元對應者的兩個復件）而 $^2\!f_{12}$ 是$x_1$（沒有一元對應者）。否定或補 $\neg x_0$出現為 $^1\!f_1$ 再次出現為 $^2\!f_5$，連同 $^2\!f_3$ （$\neg x_1$在1元時沒有出現），析取或並 $x_0 \lor x_1$出現為 $^2\!f_{14}$，合取或交 $x_0 \land x_1$出現為 $^2\!f_8$，蘊涵 $x_0 \rightarrow x_1$出現為 $^2\!f_{13}$，異或或對稱差 $x_0 \oplus x_1$ 出現為 $^2\!f_6$，差集 $x_0-x_1$ 出現為 $^2\!f_2$ 等等。對布爾函數的其他命名或表示可參見零階邏輯。

作為關於它的形式而非內容的次要詳情，一個代數的運算傳統上組織為一個列表。我們這裡通過在 $\{0,1\}$ 上有限運算索引了布爾代數的運算，上述真值表表示的排序首先按元數，其次為每個元數運算的列出表格。給定元數的列表次序是如下兩個規則確定的。

(i)表格左半部分的第 $i$ 行是 $i$ 的二進位表示，最低有效位或第0位在最左（「小端」次序，最初由艾倫·圖靈提議，所以可不無合理的叫做圖靈序）。

(ii)表格的右半部分的第 $j$ 列是 $j$ 的二進位表示，還是按小端次序。在效果上運算的下標就是這個運算的真值表。

## 序理論的性質

同任何格一樣，布爾代數$(A,\land,\lor)$可以引出偏序集$(A,\leq)$，通過定義

$a \leq b$ 若且唯若$a = a \land b$（它也等價於$b=a\lor b$）。

事實上你還可以把布爾代數定義為有最小元素0和最大元素1的分配格$(A,\leq)$（考慮為偏序集合），在其中所有的元素 $x$ 都有補 $\neg x$滿足

$x \land \neg x = 0$ 並且 $x \lor \neg x = 1$

這裡的$\land$和$\lor$用來指示兩個元素的下確界（交）和上確界（並）。還有，如果上述意義上的補存在，則它們是可唯一確定的。

代數的和序理論的觀點通常可以交替的使用，並且二者都是有重要用處的，可從泛代數和序理論引入結果和概念。在很多實際例子中次序關係、合取（邏輯與）、析取（邏輯或）和否定（邏輯非）都是自然的可獲得的，所以可直接利用這種聯繫。

### 對偶原理

你還可以把來自序理論的對偶性的普遍認識應用於布爾代數。特別是，所有的布爾代數的次序對偶，或者等價的說通過對換$\land$與$\lor$所獲得的代數，也是布爾代數。一般的說，布爾代數的任何有效的規律都可以變換成另一個有效的對偶規律，通過對換0與1，$\land$與$\lor$，和≤與≥。

## 同態和同構

在布爾代數 $A$ 和 $B$ 之間的同態是一個函數 $f: A\rightarrow B$，對於在 $A$ 中所有的 $a$, $b$ 都有:

$$f(a \lor b) = f(a) \lor f(b)$$

$$f(a \land b)=f(a) \land f(b)$$

$$f(0)=0$$

$$f(1)=1$$

接著對於在 $A$ 中所有的 $a$，$f(\neg a) = \neg f(a)$ 同樣成立。所有布爾代數的類，和與之在一起的態射的概念，形成了一個範疇。從 $A$ 到 $B$ 的同構是雙射的從 $A$ 到 $B$ 的同態。同構的逆也是同構，我們稱兩個布爾代數 $A$ 和 $B$ 為「同構」的。從布爾代數理論的立場上，它們是不能區分的；它們只在它們的元素的符號上有所不同。

### 布爾同態

布爾同態是在布爾代數 $A$ 和 $B$ 之間的函數 $h: A\rightarrow B$ 使得對於所有布爾運算 $^m\!f_i$ 有

$h(^m\!f_i(x_0, \cdots, x_{m-1}))=^m\!f_i(h(x_0),\cdots,h(x_{m-1}))$.

布爾代數的範疇Bool有所有布爾代數作為對象和在它們之間的布爾同態作為態射。

從兩元素布爾代數2到所有布爾代數存在唯一的同態，因為所有態射必須保持兩個常量而它們是2的僅有元素。有這種性質的布爾代數叫做初始布爾代數。可以證明任何兩個初始布爾代數都是同構的，所以在同構的意義下2就是初始布爾代數。

在其他方向上，從布爾代數B到2存在很多同態。任何這種同態都把B 劃分成映射到1的元素和映射到0的元素。由前者組成的B的子集叫做B的超濾子。在B是有限的時候，它的超濾子配對於它的原子；一個原子被映射到1而其他被映射到0。B的每個超濾子因此由B的一個原子和所有其上的元素組成；所以精確的有B的一半元素在這個超濾子中，並且有和原子一樣的多的超濾子。

對於無限布爾代數，超濾子的概念變得相當微妙。大於等於原子的那些元素總是形成超濾子，但是很多其他集合也能形成；例如在整數的有限和余有限集合的布爾代數中，余有限集合形成了超濾子即使它們中沒有原子。類似的整數的冪集有包含給定整數的所有子集的集合作為超濾子之一；有可數多個這種「標準」超濾子，它們可以用整數自身來識別，但是還有不可數多個「非標準」超濾子。這些形成了非標準分析的基礎，它提供了對這種經典不相容對象作為無窮小和delta函數的表述。

## 布爾環、理想和濾子

每個布爾代數$(A,\land,\lor)$都引出一個環（$A$, +, *），通過定義 $a+b=(a \land \neg b)\lor(b \land \neg a)$（這個運算在集合論中叫做「對稱差」在邏輯中叫做XOR（異或））和 $a*b=a\land b$。這個環的零元素符合布爾代數的0；環的乘法單位元素是布爾代數的1。這個環有對於 $A$ 中的所有的 $a$ 保持 $a*a=a$的性質；有這種性質的環叫做布爾環。

反過來，如果給出布爾環 $A$，我們可以把它轉換成布爾代數，通過定義 $x \lor y=x+y+xy$ 和 $x \land y=xy$。因為這兩個運算是互逆的，我們可以說每個布爾環引發一個布爾代數，或反之。此外，映射 $f: A\rightarrow B$ 是布爾代數的同態，若且唯若它是布爾環的同態。布爾環和代數的範疇是等價的。

布爾代數 $A$ 的理想是一個子集 $I$，對於在 $I$ 中的所有 $x$, $y$ 我們有 $x \lor y$ 在 $I$ 中，並且對於在 $A$ 中的所有 $a$ 我們有$a \land x$ 在 $I$ 中。理想的概念符合在布爾環 $A$ 中環理想的概念。$A$ 的理想 $I$ 叫做「素理想」，如果 $I \neq A$；並且如果 $a \land b$ 在 $I$ 中總是蘊涵 $a$ 在 $I$ 中或 $b$ 在 $I$ 中。$A$ 的理想 $I$ 叫做「極大理想」，如果 $I \neq A$ 並且真正包含 $I$ 的唯一的理想是 $A$ 自身。這些概念符合布爾環 $A$ 中的素理想和極大理想的環理論概念。

「理想」的對偶是濾子。布爾代數 $A$ 的「濾子」是子集 $p$，對於在 $p$ 中的所有 $x$, $y$ 我們有 $x \land y$ 在 $p$ 中，並且對於在 $A$ 中的所有 $a$，如果 $a\lor x=a$ 則 $a$ 在 $p$ 中。

## 表示布爾代數

可以證實所有的「有限」的布爾代數都同構於一個有限集合的所有子集的布爾代數。此外，所有的有限的布爾代數的元素數目都是二的冪。Stone的著名的布爾代數表示定理陳述了「所有的」布爾代數 $A$ 都同構於在某個（完全不連通緊緻豪斯多夫空間）拓撲空間中所有閉開集合的布爾代數。

## 廣義布爾代數

從布爾代數的公理中去掉存在最大元1的要求產生了「廣義布爾代數」。形式的說，分配格 $B$ 是廣義布爾代數，如果它有最小元0並且對於任何 $B$ 中的元素 $a$ 和 $b$ 使得 $a\leq b$，存在一個元素 $x$ 使得$a\land x=0$並且$a\lor x=b$。定義$a - b \,$為唯一的 $x$ 使得$(a\land b)\lor x=a$並且$(a\land b)\land x=0$，我們可以稱結構$(B,\land,\lor,-,0)$是「廣義布爾代數」，而$(B,\lor,0)$是「廣義布爾半格」。

廣義布爾格完全就是布爾格的理想。

## 公理化布爾代數

在1933年，美國數學家Edward Vermilye Huntington（1874-1952）展示了對布爾代數的如下公理化：

- 交換律：$x + y = y + x$。
- 結合律：$(x + y) + z = x + (y + z)$。
- Huntington等式：$\overline{ \overline{x}+y} + \overline{\overline{x}+\overline{y}} = x$。

Herbert Robbins接著擺出下列問題: Huntington等式能否替代為它的對偶等式，並且這個新等式與結合律和交換律一起成為布爾代數的基礎?通過一組叫做「Robbins代數」的公理，問題就變成了：是否所有的Robbins代數都是布爾代數?

Robbins代數的公理化：

- 交換律：$x + y = y + x$。
- 結合律：$(x + y) + z = x + (y + z)$。
- Robbins等式：$\overline{\overline{x + y}+ \overline{x +\overline{y}}} = x$。

這個問題自從1930年代一直是公開的，並成為阿爾弗雷德·塔斯基和他的學生最喜好的問題。

在1996年，William McCune在阿貢國家實驗室，建造在Larry Wos、Steve Winker和Bob Veroff的工作之上，肯定的回答了這個長期存在的問題：所有的Robbins代數都是布爾代數。這項工作是使用McCune的自動推理程序EQP完成的。

## 其它記號

布林代數的運算包含下列幾種，基本包含「與」(AND)、「或」(OR)、「非」(NOT)，其中由這三種又可組合成NAND（與非）、NOR（或非）、XOR（異或）與XNOR（異或非）。

常見使用記號：「$\cdot$」表示AND，「＋」表示OR（如CNF和DNF中）或者XOR（如ANF中）；A中A上面的一橫表示NOT；⊕表示XOR；⊙表示XNOR。

## 外部連結

- Boolean Algebra from AllAboutCircuits
- Stanford Encyclopedia of Philosophy: " The Mathematics of Boolean Algebra, " by J. Donald Monk.
- McCune W., 1997. Robbins Algebras Are Boolean JAR 19(3), 263–276
- "Boolean Algebra" by Eric W. Weisstein、The Wolfram Demonstrations Project, 2007.

A monograph available free online:

- Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 978-3-540-90578-3.