布尔代数

术语“布尔代数”得名于乔治·布尔（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，其上定义了以下结构：

• 二元运算∧:A×A→A。
• 二元运算∨:A×A→A。
• 一元运算 ':A→A。
• 零元运算（常数）0和1。

这些运算满足以下条件：∀a，b，c∈A，

上面的前三对公理：结合律、交换律和吸收律，意味着 (A,∧,∨)是一个格。所以布尔代数也可以定义为一个有补分配格。

从这些公理，你可以展示出最小元素0、最大元素1和任何元素a的补a'都是唯一确定的。

另外，∀a,b∈A，下列恒等式也成立：

其它运算

在上述基本定义基础上，布尔代数中常见的还有以下的运算：

• 二元运算-: A×A→A，定义为：a-b = a∧b'；
• 二元运算+或Δ: A×A→A，定义为：a+b = (a-b)∨(b-a)；
• 二元运算→: A×A→A，定义为：a→b = (a-b)'；
• 二元运算↔: A×A→A，定义为：a↔b = (a→b)∧(b→a)；
• 二元运算|或↑: A×A→A，定义为：a|b = (a∧b)'。
• 二元运算⊕或↓: A×A→A，定义为：a⊕b = a'∧b'

注意：-和→，+和↔是对偶的。即a→b = (a-b)'，a↔b=(a+b)'。

总结

布尔代数的各种运算同时也被应用于集合论和逻辑学，在不同的上下文有不同的名称。具体的符号和名称如下：

• 最简单的布尔代数只有两个元素0和1，并通过如下规则定义:

• 它应用于逻辑中，解释0为“伪”，1为“真”，∧为“与”，∨为“或”，¬为“非”。涉及变量和布尔运算的表达式代表了陈述形式，两个这样的表达式可以使用上面的公理证实为等价的，当且仅当对应的陈述形式是逻辑等价的。

• 两元素的布尔代数也是在电子工程中用于电路设计；这里的0和1代表数字电路中一个位的两种不同状态，典型的是高和低电压。电路通过包含变量的表达式来描述，两个这种表达式对这些变量的所有的值是等价的，当且仅当对应的电路有相同的输入-输出行为。此外，所有可能的输入-输出行为都可以使用合适的布尔表达式来建摸。

• 两元素布尔代数在布尔代数的一般理论中也是重要的，因为涉及多个变量的等式是在所有布尔代数中普遍为真，当且仅当它在两个元素的布尔代数中为真（这总是可以通过平凡的穷举法算法证实）。比如证实下列定律（“合意定理”）在所有布尔代数中是普遍有效的:
  • (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
  • (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

• 任何给定集合S的幂集（子集的集合）形成有两个运算∨ := ∪ (并)和∧ := ∩ (交)的布尔代数。最小的元素0是空集而最大元素1是集合S自身。
• 有限的或余有限的集合S的所有子集的集合是布尔代数。
• 对于任何自然数n，n的所有正约数的集合形成一个分配格，如果我们对a | b写a ≤ b。这个格是布尔代数当且仅当n是无平方数因数的数。这个布尔代数的最小的元素0是自然数1；这个布尔代数的最大元素1是自然数n。
• 布尔代数的另一个例子来自拓扑空间:如果X是一个拓扑空间，它既是开放的又是闭合的，X的所有子集的搜集形成有两个运算∨ := ∪ (并)和∧ := ∩ (交)的布尔代数。
• 如果R是一个任意的环，并且我们定义“中心幂等元”（central idempotent）的集合为
  A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R }
  则集合A成为有两个运算e ∨ f := e + f + ef和e ∧ f := ef的布尔代数。

在k元素集合X上有k^kn个n元运算f: Xⁿ→X，因此在{0,1}上有2²ⁿ个n元运算。所以得出所有布尔代数，不论大小都两个常量或“零元”运算，四个一元运算，16个二元运算，256个三元运算，以此类推，它们叫做给定布尔代数的布尔运算。只有一个例外就是一个元素的布尔代数，它叫做退化的或平凡的（被一些早期作者禁用），布尔代数的所有运算可以被证明是独特的。（在退化情况下，给定元数的所有运算都是同样的运算因为对所有输入都返回同样结果。）

在{0,1}上的运算可以用真值表展出，选取0和1为真值假和真。它们可以按统一和不依赖应用的方式列出，允许我们命名或至少单独列出它们。这些名字对布尔运算提供方便的简写。n元运算的名字是2ⁿ位的二进制数。有2²ⁿ个这种运算，你不能得到更简明的命名法了!

下面展示元数从0到2的所有运算的这种格局和关联的名字。

这些表格继续到更高元数上，对n元有2ⁿ行，每个行给出n个变量x₀,…x_n−1的一个求值或绑定，而每列都有表头ⁿf_i，它们给出第i个n元运算ⁿf_i(x₀,…,x_n−1)在这个求值下的值。运算包括变量本身，例如¹f₂是x₀而²f₁₀是x₀ (作为它的一元对应者的两个复件)而²f₁₂是x₁ (没有一元对应者)。否定或补¬x₀出现为¹f₁再次出现为²f₅，连同²f₃ (¬x₁在1元时没有出现)，析取或并x₀∨x₁出现为²f₁₄，合取或交x₀∧x₁出现为²f₈，蕴涵x₀→x₁出现为²f₁₃，异或或对称差x₀⊕x₁出现为²f₆，差集x₀−x₁出现为²f₂等等。对布尔函数的其他命名或表示可参见零阶逻辑。

作为关于它的形式而非内容的次要详情，一个代数的运算传统上组织为一个列表。我们这里通过在{0,1}上有限运算索引了布尔代数的运算，上述真值表表示的排序首先按元数，其次为每个元数运算的列出表格。给定元数的列表次序是如下两个规则确定的。

(i)表格左半部分的第i行是i的二进制表示，最低有效位或第0位在最左（“小端”次序，最初由艾伦·图灵提议，所以可不无合理的叫做图灵序）。

(ii)表格的右半部分的第j列是j的二进制表示，还是按小端次序。在效果上运算的下标就是这个运算的真值表。

同任何格一样，布尔代数 (A, ${\displaystyle \land }$ , ${\displaystyle \lor }$ )可以引出偏序集（A, ≤），通过定义

a ≤ b 当且仅当a = a ${\displaystyle \land }$  b (它也等价于b = a ${\displaystyle \lor }$  b)。

事实上你还可以把布尔代数定义为有最小元素0和最大元素1的分配格 (A, ≤) (考虑为偏序集合)，在其中所有的元素x都有补¬x满足

x ${\displaystyle \land }$  ¬x = 0并且x ${\displaystyle \lor }$  ¬x = 1

这里的${\displaystyle \land }$ 和${\displaystyle \lor }$ 用来指示两个元素的下确界（交）和上确界（并）。还有，如果上述意义上的补存在，则它们是可唯一确定的。

代数的和序理论的观点通常可以交替的使用，并且二者都是有重要用处的，可从泛代数和序理论引入结果和概念。在很多实际例子中次序关系、合取（逻辑与）、析取（逻辑或）和否定（逻辑非）都是自然的可获得的，所以可直接利用这种联系。

对偶原理

你还可以把来自序理论的对偶性的普遍认识应用于布尔代数。特别是，所有的布尔代数的次序对偶，或者等价的说通过对换${\displaystyle \land }$ 与${\displaystyle \lor }$ 所获得的代数，也是布尔代数。一般的说，布尔代数的任何有效的规律都可以变换成另一个有效的对偶规律，通过对换0与1，${\displaystyle \land }$ 与${\displaystyle \lor }$ ，和≤与≥。

在布尔代数A和B之间的同态是一个函数f : A → B，对于在A中所有的a, b都有:

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

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

f（0）= 0

f（1）= 1

接着对于在A中所有的a，f(¬a) = ¬f（a）同样成立。所有布尔代数的类，和与之在一起的态射的概念，形成了一个范畴。从A到B的同构是双射的从A到B的同态。同构的逆也是同构，我们称两个布尔代数A和B为“同构”的。从布尔代数理论的立场上，它们是不能区分的；它们只在它们的元素的符号上有所不同。

布尔同态

布尔同态是在布尔代数A和B之间的函数h: A→B使得对于所有布尔运算^mf_i有

h(^mf_i(x₀,…,x_m−1)) = ^mf_i(h(x₀),…,h(x_m−1)).

布尔代数的范畴Bool有所有布尔代数作为对象和在它们之间的布尔同态作为态射。

从两元素布尔代数2到所有布尔代数存在唯一的同态，因为所有态射必须保持两个常量而它们是2的仅有元素。有这种性质的布尔代数叫做初始布尔代数。可以证明任何两个初始布尔代数都是同构的，所以在同构的意义下2就是初始布尔代数。

在其他方向上，从布尔代数B到2存在很多同态。任何这种同态都把B 划分成映射到1的元素和映射到0的元素。由前者组成的B的子集叫做B的超滤子。在B是有限的时候，它的超滤子配对于它的原子；一个原子被映射到1而其他被映射到0。B的每个超滤子因此由B的一个原子和所有其上的元素组成；所以精确的有B的一半元素在这个超滤子中，并且有和原子一样的多的超滤子。

对于无限布尔代数，超滤子的概念变得相当微妙。大于等于原子的那些元素总是形成超滤子，但是很多其他集合也能形成；例如在整数的有限和余有限集合的布尔代数中，余有限集合形成了超滤子即使它们中没有原子。类似的整数的幂集有包含给定整数的所有子集的集合作为超滤子之一；有可数多个这种“标准”超滤子，它们可以用整数自身来识别，但是还有不可数多个“非标准”超滤子。这些形成了非标准分析的基础，它提供了对这种经典不兼容对象作为无穷小和delta函数的表述。

每个布尔代数 (A, ${\displaystyle \land }$ , ${\displaystyle \lor }$ )都引出一个环（A, +, *），通过定义a + b = (a ${\displaystyle \land }$  ¬b) ${\displaystyle \lor }$  (b ${\displaystyle \land }$  ¬a) (这个运算在集合论中叫做“对称差”在逻辑中叫做XOR（异或）)和a * b = a ${\displaystyle \land }$  b。这个环的零元符合布尔代数的0；环的乘法单位元素是布尔代数的1。这个环有对于A中的所有的a保持a * a = a的性质；有这种性质的环叫做布尔环。

反过来，如果给出布尔环A，我们可以把它转换成布尔代数，通过定义x ${\displaystyle \lor }$  y = x + y + xy和x ${\displaystyle \land }$  y = xy。因为这两个运算是互逆的，我们可以说每个布尔环引发一个布尔代数，或反之。此外，映射f : A → B是布尔代数的同态，当且仅当它是布尔环的同态。布尔环和代数的范畴是等价的。

布尔代数A的理想是一个子集I，对于在I中的所有x, y我们有x ${\displaystyle \lor }$  y在I中，并且对于在A中的所有a我们有a ${\displaystyle \land }$  x在I中。理想的概念符合在布尔环A中环理想的概念。A的理想I叫做“素理想”，如果I ≠ A；并且如果a ${\displaystyle \land }$  b在I中总是蕴涵a在I中或b在I中。A的理想I叫做“极大理想”，如果I ≠ A并且真正包含I的唯一的理想是A自身。这些概念符合布尔环A中的素理想和极大理想的环理论概念。

“理想”的对偶是滤子。布尔代数A的“滤子”是子集p，对于在p中的所有x, y我们有x ${\displaystyle \land }$  y在p中，并且对于在A中的所有a，如果a ${\displaystyle \lor }$  x = a则a在p中。

可以证实所有的“有限”的布尔代数都同构于一个有限集合的所有子集的布尔代数。此外，所有的有限的布尔代数的元素数目都是二的幂。Stone的著名的布尔代数表示定理陈述了“所有的”布尔代数A都同构于在某个（完全不连通紧致豪斯多夫空间）拓扑空间中所有闭开集合的布尔代数。

从布尔代数的公理中去掉存在最大元1的要求产生了“广义布尔代数”。形式的说，分配格B是广义布尔代数，如果它有最小元0并且对于任何B中的元素a和b使得a ≤ b，存在一个元素x使得${\displaystyle a\land x=0}$ 并且${\displaystyle a\lor x=b}$ 。定义${\displaystyle a-b\,}$ 为唯一的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. 交换律: x + y = y + x。
2. 结合律: (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. 交换律: x + y = y + x。
2. 结合律: (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-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.  
• 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. Peirce, C. S.（1989）Writings of Charles S. Peirce: A Chronological Edition: 1879–1884. Kloesel, C. J. W., ed. Indianapolis: Indiana University Press. 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.   引文格式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.