布尔代数

维库，知识与思想的自由文库

布尔代数(有时叫布尔格，又譯布林代數)在数学中是一个代数结构(就是说，叫做元素的对象的一个集合，和与之在一起的在这些元素上的运算，它们接受一个或两个元素并返回另一个元素)。可以按各种方式去认为元素是什么；最常见的是把它们当作一般化的真值。作为一个简单的例子，假设有三个条件是独立的为真或为假。布尔代数的元素可以接着精确指定那些为真；那么布尔代数自身将是所有八种可能性的一个搜集，和与之在一起的组合它们的方式。

有时也被称为布尔代数的一个相关主题是布尔逻辑，它可以被定义为是所有布尔代数所公有的东西。它由在布尔代数的元素间永远成立的关系组成，而不管你具体的那个布尔代数。因为逻辑门和某些电子电路的代数在形式上也是这样的，所以同在数理逻辑中一样，布尔逻辑也在工程和计算机科学中研究。

在布尔代数上的运算被称为AND(与)、OR(或)和NOT(非)。代数结构要是布尔代数，这些运算的行为就必须和两元素的布尔代数一样(这两个元素是TRUE(真)和FALSE(假))。

布尔代数得名于乔治·布尔，他是College Cork 大学的英国数学家。Boole 所公式化的逻辑的代数系统与本文所描述的代数结构在一些小但重要的方面是有不同之处的。

[编辑] 形式定义

布尔代数是一个集合 A，提供了两个二元运算 $\land$ (逻辑与)、 $\lor$ (逻辑或)，一个一元运算 $\lnot$ / ~ (逻辑非)和两个元素 0(逻辑假)和 1(逻辑真)，此外，对于集合 A 的所有元素 a、b 和 c，下列公理成立:

$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 的补 ¬a 都是唯一确定的。对于 A 中的所有的 a 和 b，下列恒等式也成立:

$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$	de Morgan 定律
$\lnot \lnot a = a$		对合律

[编辑] 例子

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

∧	0	1
0	0	0
1	0	1

∨	0	1
0	0	1
1	1	1

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

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

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

任何给定集合 S 的幂集(子集的集合)形成有两个运算 ∨ := ∪ (并)和 ∧ := ∩ (交)的布尔代数。最小的元素 0 是空集而最大元素 1 是集合 S 自身。

有限的或者 cofinite 的集合 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 的布尔代数。

[编辑] 次序论的性质

Image:Hasse diagram of powerset of 3.png

子集的格

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

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

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

x $\land$ ¬x = 0 并且 x $\lor$ ¬x = 1

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

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

[编辑] 对偶原理

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

[编辑] 其他记号

布尔代数的运算符可以用各种方式表示。它们经常简单写成 AND、OR 和 NOT。在描述电路时，还可以使用 NAND (NOT AND)、NOR (NOT OR) 和 XOR (排斥的 OR)。数学家、工程师和程序员经常使用 + 表示 OR 和 · 表示 AND (因为在某些方面这些运算类似于在其他代数结构中的加法和乘法，并且这种运算易于对普通代数熟悉的人得到积之和范式)，和把 NOT 表示为在要否定的表达式顶上画一条横线。

这里我们使用另一种常见记号，"交" $\land$ 表示 AND，"并" $\lor$ 表示 OR，和 ¬ 表示 NOT。(使用只有文本的浏览器的读者将见到 LaTeX 代码而不是他们表示的楔形符号。)

[编辑] 同态和同构

在布尔代数 A 和 B 之间的同态是一个函数 f : A → 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(¬a) = ¬f(a) 同样成立。所有布尔代数的类，和与之在一起的态射(morphism)的概念，形成了一个范畴。从 A 到 B 的同构是双射的从 A 到 B 的同态。同态的逆也是同态，我们称两个布尔代数 A 和 B 为同态的。从布尔代数理论的立场上，它们是不能区分的；它们只在它们的元素的符号上有所不同。

[编辑] 布尔的环、理想和过滤

每个布尔代数 (A, $\land$ , $\lor$ ) 都引出一个环 (A, +, *)，通过定义 a + b = (a $\land$ ¬b) $\lor$ (b $\land$ ¬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 → B 是布尔代数的同态，当且仅当它是布尔环的同态。布尔环和代数的范畴是等价的。

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

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

[编辑] 表示布尔代数

可以证实所有的有限的布尔代数都同构于这个有限集合的所有子集的布尔代数。此外，所有的有限的布尔代数的元素数目都是二的幂。

Stone 的著名的布尔代数的表示定理陈述了所有的布尔代数 A 都在某个(紧凑的完全不连通的 Hausdorff)拓扑空间中同构于所有闭开集的布尔代数。

[编辑] 公理化布尔代数

在 1933 年，美国数学家 Edward Vermilye Huntington (1874-1952) 展示了对布尔代数的如下公理化:

交换律: x + y = y + x。
结合律: (x + y) + z = x + (y + z)。
Huntington 等式: n(n(x) + y) + n(n(x) + n(y)) = x。

一元函数符号 n 可以读做'补'。

Herbert Robbins 接着摆出下列问题: Huntington 等式能否缩短为下述的等式，并且这个新等式与结合律和交换律一起成为布尔代数的基础? 通过一组叫做 Robbins 代数的公理，问题就变成了: 是否所有的 Robbins 代数都是布尔代数?

Robbins 代数的公理化:

交换律: x + y = y + x。
结合律: (x + y) + z = x + (y + z)。
Robbins 等式: n(n(x + y') + n(x + n(y))) = x。

这个问题自从 1930 年代一直是公开的，并成为 Alfred Tarski 和他的学生最喜好的问题。

在 1996 年，William McCune 在 Argonne 国家实验室，建造在 Larry Wos、Steve Winker 和 Bob Veroff 的工作之上，肯定的回答了这个长期存在的问题: 所有的 Robbins 代数都是布尔代数。这项工作是使用 McCune 的自动推理程序 EQP 完成的。

[编辑] 参见

[编辑] 外部链接

Article on The Mathematics of Boolean Algebra at the Stanford Encyclopedia of Philosophy

来自“http://www.wikilib.com/wiki/%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0”

个人工具