布林代數

此條目介紹的是一種代數結構。關於相關的數學分支，請見「邏輯代數」。

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

子集的布林格的哈斯圖

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

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

相似於集合論斷言子集A和它的補集 ${\displaystyle A^{C}}$ 有空交集，

${\displaystyle A\cap (A^{C})=\varnothing }$。

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

布林代數也叫做布林格。關聯於格（特殊的偏序集合）是在集合包含 ${\displaystyle A\subseteq B}$ 和次序 ${\displaystyle a\leq b}$ 之間的相似所預示的。考慮 ${\displaystyle \{x,y,z\}}$ 的所有子集按照包含排序的格。這個布林格是偏序集合，在其中 ${\displaystyle \{x\}\leq \{x,y\}}$。任何兩個格的元素，比如 ${\displaystyle p=\{x,y\}}$ 和 ${\displaystyle q=\{y,z\}}$，都有一個最小上界，這裡是 ${\displaystyle \{x,y,z\}}$，和一個最大下界，這裡是 ${\displaystyle \{y\}}$。這預示了最小上界（並或上確界）被表示為同邏輯OR一樣的符號 ${\displaystyle p\lor q}$；而最大下界（交或下確界）被表示為同邏輯AND一樣的符號 ${\displaystyle 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和其他人使用布林代數的分支也就是力迫和布林值模型，深入發現了數理邏輯和公理化集合論中的新成果。

形式定義

布林代數是一個集合 ${\displaystyle A}$，其上定義了以下結構：

• 二元運算∧：${\displaystyle A\times A\rightarrow A}$。
• 二元運算∨：${\displaystyle A\times A\rightarrow A}$。
• 一元運算 '：${\displaystyle A\rightarrow A}$。
• 零元素運算（常數）0和1。

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

${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c}$	${\displaystyle a\land (b\land c)=(a\land b)\land c}$	結合律
${\displaystyle a\lor b=b\lor a}$	${\displaystyle a\land b=b\land a}$	交換律
${\displaystyle a\lor (a\land b)=a}$	${\displaystyle a\land (a\lor b)=a}$	吸收律
${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$	${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$	分配律
${\displaystyle a\lor \lnot a=1}$	${\displaystyle a\land \lnot a=0}$	互補律

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

從這些公理，你可以展示出最小元素0、最大元素1和任何元素a的補a'都是唯一確定的。

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

${\displaystyle a\lor a=a}$	${\displaystyle a\land a=a}$	冪等律
${\displaystyle a\lor 0=a}$	${\displaystyle a\land 1=a}$	有界律
${\displaystyle a\lor 1=1}$	${\displaystyle a\land 0=0}$
${\displaystyle \lnot 0=1}$	${\displaystyle \lnot 1=0}$	0和1是互補的
${\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b}$	${\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b}$	德·摩根定律
${\displaystyle \lnot \lnot a=a}$		對合律

其它運算

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

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

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

總結

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

運算符號	布林代數	集合論	邏輯學	邏輯閘	溫氏圖
0或${\displaystyle \bot }$	底	空集	偽	低電位
1或${\displaystyle \top }$	頂	全集	真	高電位
¬或~或'或c		補集	非	反相器
∧或∩	下確界	交集	與	及閘
∨或∪	上確界	聯集	或	或閘
${\displaystyle \not \leftarrow }$或${\displaystyle \not \subset }$	補	相對補集
-或${\displaystyle \not \rightarrow }$	減	差集	實質非蘊涵	蘊含非閘
⊕或Δ	對稱差	對稱差	互斥或	互斥或閘
→	條件		條件	蘊含閘
↔	雙向條件		雙條件	同或閘
|或↑	謝費爾豎線		與非	反及閘
↓	皮爾斯箭頭		或非	反或閘

例子

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

∧ 0 1 0 0 0 1 0 1

∨ 0 1 0 0 1 1 1 1

a 0 1 ¬a 1 0

• 它應用於邏輯中，解釋0為「偽」，1為「真」，∧為「與」，∨為「或」，¬為「非」。涉及變數和布林運算的表達式代表了陳述形式，兩個這樣的表達式可以使用上面的公理證實為等價的，若且唯若對應的陳述形式是邏輯等價的。

• 兩元素的布林代數也是在電子工程中用於電路設計；這裡的0和1代表數字電路中一個位的兩種不同狀態，典型的是高和低電壓。電路通過包含變數的表達式來描述，兩個這種表達式對這些變數的所有的值是等價的，若且唯若對應的電路有相同的輸入-輸出行為。此外，所有可能的輸入-輸出行為都可以使用合適的布林表達式來建摸。

• 兩元素布林代數在布林代數的一般理論中也是重要的，因為涉及多個變數的等式是在所有布林代數中普遍為真，若且唯若它在兩個元素的布林代數中為真（這總是可以通過平凡的窮舉法演算法證實）。比如證實下列定律（「合意定理」）在所有布林代數中是普遍有效的:
  • ${\displaystyle (a\lor b)\land (\neg a\lor c)\land (b\lor c)\equiv (a\lor b)\land (\neg a\lor c)}$
  • ${\displaystyle (a\land b)\lor (\neg a\land c)\lor (b\land c)\equiv (a\land b)\lor (\neg a\land c)}$

• 任何給定集合 ${\displaystyle S}$ 的冪集（子集的集合）形成有兩個運算 ${\displaystyle \lor :=\cup }$（並）和 ${\displaystyle \land :=\cap }$（交）的布林代數。最小的元素0是空集而最大元素1是集合 ${\displaystyle S}$ 自身。
• 有限的或餘有限的集合 ${\displaystyle S}$ 的所有子集的集合是布林代數。
• 對於任何自然數 ${\displaystyle n}$，${\displaystyle n}$ 的所有正因數的集合形成一個分配格，如果我們對 ${\displaystyle a|b}$ 寫 ${\displaystyle a\leq b}$。這個格是布林代數若且唯若 ${\displaystyle n}$ 是無平方數因數的數。這個布林代數的最小的元素0是自然數1；這個布林代數的最大元素1是自然數n。
• 布林代數的另一個例子來自拓撲空間：如果 ${\displaystyle X}$ 是一個拓撲空間，它既是開放的又是閉合的，${\displaystyle X}$ 的所有子集的搜集形成有兩個運算${\displaystyle \lor :=\cup }$（並）和${\displaystyle \land :=\cap }$（交）的布林代數。
• 如果 ${\displaystyle R}$ 是一個任意的環，並且我們定義「中心冪等元」（central idempotent）的集合為${\displaystyle A=\{e\in R:e^{2}=e,ex=xe,\forall x\in R\}}$，則集合A成為有兩個運算 ${\displaystyle e\lor f:=e+f+ef}$ 和 ${\displaystyle e\land f:=ef}$的布林代數。

原型布林代數

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

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

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

直到2元的布林運算的真值表

常數 0f0 0f1 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

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

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

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

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

序理論的性質

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

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

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

${\displaystyle x\land \neg x=0}$ 並且 ${\displaystyle x\lor \neg x=1}$

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

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

對偶原理

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

同態和同構

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

${\displaystyle f(a\lor b)=f(a)\lor f(b)}$

${\displaystyle f(a\land b)=f(a)\land f(b)}$

${\displaystyle f(0)=0}$

${\displaystyle f(1)=1}$

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

布林同態

布林同態是在布林代數 ${\displaystyle A}$ 和 ${\displaystyle B}$ 之間的函數 ${\displaystyle h:A\rightarrow B}$ 使得對於所有布林運算 ${\displaystyle ^{m}\!f_{i}}$ 有

${\displaystyle 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函數的表述。

布林環、理想和濾子

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

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

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

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

表示布林代數

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

廣義布林代數

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

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

公理化布林代數

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

1. 交換律：${\displaystyle x+y=y+x}$。
2. 結合律：${\displaystyle (x+y)+z=x+(y+z)}$。
3. Huntington等式：${\displaystyle {\overline {{\overline {x}}+y}}+{\overline {{\overline {x}}+{\overline {y}}}}=x}$。

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

Robbins代數的公理化：

1. 交換律：${\displaystyle x+y=y+x}$。
2. 結合律：${\displaystyle (x+y)+z=x+(y+z)}$。
3. Robbins等式：${\displaystyle {\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（互斥或非）。

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

參見

• 布林代數主題列表
• 布林運算
• 邏輯代數
• 代數邏輯

參考資料

• Brown, Stephen; Vranesic, Zvonko, Fundamentals of Digital Logic with VHDL Design 2nd, McGraw–Hill, 2002, ISBN 978-0-07-249938-4. See Section 2.5.

• Cori, Rene; Lascar, Daniel, Mathematical Logic: A Course with Exercises, Oxford University Press, 2000, ISBN 978-0-19-850048-3. See Chapter 2.

• Dahn, B. I., Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem, Journal of Algebra, 1998, 208: 526–532, ISSN 0021-8693.

• Halmos, Paul, Lectures on Boolean Algebras, Van Nostrand, 1963, ISBN 978-0-387-90094-0.

• Halmos, Paul; Givant, Steven, Logic as Algebra, Dolciani Mathematical Expositions, no. 21, Mathematical Association of America, 1998, ISBN 978-0-88385-327-6.

• Huntington, E. V., New sets of independent postulates for the algebra of logic, Transactions of the American Mathematical Society, 1933, 35: 274–304, ISSN 0002-9947.

• Huntington, E. V., Boolean algebra: A correction, Transactions of the American Mathematical Society, 1933, 35: 557–558, ISSN 0002-9947.

• Mendelson, Elliott, Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw–Hill, 1970, ISBN 978-0-07-041460-0.

• Monk, J. Donald; Bonnet, R. (編), Handbook of Boolean Algebras, North-Holland, 1989, ISBN 978-0-444-87291-3. In 3 volumes. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN 978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)

• Stoll, R. R., Set Theory and Logic, W. H. Freeman, 1963, ISBN 978-0-486-63829-4. Reprinted by Dover Publications, 1979.
• Birkhoff, Garrett. On the structure of abstract algebras. Proc. Camb. Phil. Soc. 1935, 31: 433–454. ISSN 0008-1981.
• Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9.
• Dwinger, Philip. Introduction to Boolean algebras. Würzburg: Physica Verlag. 1971.
• Gaifman, Haim. Infinite Boolean Polynomials, I. Fundamenta Mathematicae. 1964, 54: 229–250. ISSN 0016-2736.
• Grau, A.A. Ternary Boolean algebra. Bull: Am. Math. Soc. 1947, 33: 567–572.
• Hales, Alfred W. On the Non-Existence of Free Complete Boolean Algebras. Fundamenta Mathematicae. 1964, 54: 45–66. ISSN 0016-2736.
• --------, and Givant, Steven (1998) Logic as Algebra. Dolciani Mathematical Exposition, No. 21. Mathematical Association of America.
• Johnstone, Peter T. Stone Spaces. Cambridge, UK: Cambridge University Press. 1982. ISBN 978-0-521-33779-3.
• Ketonen, Jussi. The structure of countable Boolean algebras. Annals of Mathematics. 1978, 108: 41–89.
• Koppelberg, Sabine (1989) "General Theory of Boolean Algebras" in Monk, J. Donald, and Bonnet, Robert, eds., Handbook of Boolean Algebras, Vol. 1. North Holland. ISBN 978-0-444-70261-6.
• Peirce, C. S.（1989）Writings of Charles S. Peirce: A Chronological Edition: 1879–1884. Kloesel, C. J. W., ed. Indianapolis: Indiana University Press. ISBN 978-0-253-37204-8.
• Lawvere, F. William. Functorial semantics of algebraic theories. Proceedings of the National Academy of Sciences. 1963, 50 (5): 869–873.
• Schröder, Ernst. Vorlesungen über die Algebra der Logik (exakte Logik), I–III. Leipzig: B.G. Teubner. 1890–1910.
• Sikorski, Roman. Boolean Algebras 3rd. ed. Berlin: Springer-Verlag. 1969. ISBN 978-0-387-04469-9. 引文格式1維護：冗餘文字 (link)
• Stone, Marshall. The Theory of Representations for Boolean Algebras. Transactions of the American Mathematical Society. 1936, 40: 37–111. ISSN 0002-9947.
• Tarski, Alfred（1983）. Logic, Semantics, Metamathematics, Corcoran, J., ed. Hackett. 1956 1st edition edited and translated by J. H. Woodger, Oxford Uni. Press. Includes English translations of the following two articles:
  • Tarski, Alfred. Sur les classes closes par rapport à certaines opérations élémentaires. Fundamenta Mathematicae. 1929, 16: 195–97. ISSN 0016-2736.
  • Tarski, Alfred. Zur Grundlegung der Booleschen Algebra, I. Fundamenta Mathematicae. 1935, 24: 177–98. ISSN 0016-2736.
• Vladimirov, D.A. булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974). Nauka (German translation Akademie-Verlag). 1969.

外部連結

• 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.