布尔代数

维基百科，自由的百科全书

在抽象代数中，-{A|zh-cn:布尔;zh-hk:布林}-代数(又譯-{zh-cn:布林;zh-tw:布尔}-代數)是捕获了集合运算和逻辑运算二者的根本性质的一个代数结构(就是说一组元素和服从定义的公理的在这些元素上运算)。特别是，它处理集合运算交集、并集、补集；和逻辑运算AND、OR、NOT。

例如，逻辑断言陈述 a 和它的否定 ¬a 不能都同时为真，

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

相似于集合论断言子集 A 和它的补集 A^C 有空交集，

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

有时也被称为布尔代数的一个相关主题是布尔逻辑，它可以被定义为是所有布尔代数所公有的东西。它由在布尔代数的元素间永远成立的关系组成，而不管你具体的那个布尔代数。因为真值可以在逻辑电路中表示为二进制数或电平，这种相似性同样扩展到它们，所以布尔代数在电子工程和计算机科学中同在数理逻辑中一样有很多实践应用。

子集的布尔格

布尔代数也叫做-{zh-cn:布尔;zh-tw:布林}-格。关联于格(特殊的偏序集合)是在集合包含 A ⊆ B 和次序 a ≤ b 之间的相似所预示的。考虑 {x,y,z} 的所有子集按照包含排序的格。这个布尔格是偏序集合，在其中 {x} ≤ {x,y}。任何两个格的元素，比如 p = {x,y} 和 q = {y,z}，都有一个最小上界，这里是 {x,y,z}，和一个最大下界，这里是 {y}。这预示了最小上界(并或上确界)被表示为同逻辑 OR 一样的符号 p∨q；而最大下界(交或下确界)被表示为同逻辑 AND 一样的符号 p∧q。

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

布尔代数得名于乔治·布尔，他是 College Cork 大学的英国数学家。布尔所公式化的逻辑的代数系统更加类似于布尔环，而这里的布尔代数根源于英国逻辑学家威廉姆·斯坦利·杰文斯对布尔的最初系统做的重建工作。

[编辑] 形式定义

布尔代数是一个集合 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 的布尔代数。

[编辑] 序理论的性质

子集的布尔格

同任何格一样，布尔代数 (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://zh.wikipedia.org../../../%E5%B8%83/%E5%B0%94/%E4%BB%A3/%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0.html”

页面分类: 布尔代数 | 抽象代数 | 序理论

We provide Linux to the World