茶年 · 中文维基百科

布尔代数

Wikipedia · 2026-03-08 维基百科 👁 1 阅读

布尔代数（）在抽象代数中是指捕获了集合运算和逻辑运算二者的根本性质的一个代数结构（就是说一组元素和服从定义的公理的在这些元素上运算）。特别是，它处理集合运算交集、并集、补集；和逻辑运算与、或、非。

]]
例如，逻辑断言陈述 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。

这种格释义有助于一般化为海廷代数，它是免除要么一个陈述要么它的否定必须为真的限制的布尔代数。海廷代数对应于直觉逻辑，而布尔代数对应于经典逻辑。

布尔代数又譯為-{zh-hans:布林代数; zh-hant:布爾代數;}-。布尔代数得名于乔治·布尔，他是爱尔兰科克的皇后学院的英国数学家。布-{}-林（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, \land, \lor) 是一个格。所以布尔代数也可以定义为一个有补分配格。

从这些公理可以推出元素0、元素1和任何元素 a 的补 \lnot a 都能被唯一确定。

另外，\forall a, b\in 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和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的所有运算的这种格局和关联的名字。

|

|-
| colspan="5" |

|}

这些表格继续到更高元数上，对 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。

参见

  • 布尔代数主题列表
  • 布尔逻辑
  • 逻辑代数
  • 代数逻辑

参考资料
*. See Section 2.5.

*. See Chapter 2.

*.

*.

*.

*

*.

*.

*.

*. 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)

*. Reprinted by Dover Publications, 1979.
*
*
*
*
*
*
--------, and Givant, Steven (1998) Logic as Algebra*. Dolciani Mathematical Exposition, No. 21. Mathematical Association of America.
*
*

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

外部链接

A monograph available free online:

#代数结构 #布尔代数 #格理论 #序理论 #代数逻辑

评论 (0)

  • 还没有评论，来抢沙发吧。