布尔代数 发表评论(0) 编辑词条

　　Boolean algebra
　　英国数学家G.布尔为了研究思维规律（逻辑学、数理逻辑)于1847和1854年提出的数学模型。此后R.戴德金把它作为一种特殊的格。所谓一个布尔代数，是指一个有序的四元组〈B，∨，∧，*〉，其中B是一个非空的集合，∨与∧是定义在B上的两个二元运算，*是定义在B上的一个一元运算，并且它们满足一定的条件。
　　布尔代数由于缺乏物理背景，所以研究缓慢，到了20世纪30～40年代才有了新的进展，大约在 1935年， M.H.斯通首先指出布尔代数与环之间有明确的联系，他还得到了现在所谓的斯通表示定理：任意一个布尔代数一定同构于某个集上的一个集域；任意一个布尔代数也一定同构于某个拓扑空间的闭开代数等，这使布尔代数在理论上有了一定的发展。布尔代数在代数学（代数结构）、逻辑演算、集合论、拓扑空间理论、测度论、概率论、泛函分析等数学分支中均有应用；1967年后，在数理逻辑的分支之一的公理化集合论以及模型论的理论研究中，也起着一定的作用。近几十年来，布尔代数在自动化技术、电子计算机的逻辑设计等工程技术领域中有重要的应用。
　　1835年，20岁的乔治·布尔开办了一所私人授课学校。为了给学生们开设必要的数学课程，他兴趣浓厚地读起了当时一些介绍数学知识的教科书。不久，他就感到惊讶，这些东西就是数学吗？实在令人难以置信。于是，这位只受过初步数学训练的青年自学了艰深的《天体力学》和很抽象的《分析力学》。由于他对代数关系的对称和美有很强的感觉，在孤独的研究中，他首先发现了不变量，并把这一成果写成论文发表。这篇高质量的论文发表后，布尔仍然留在小学教书,但是他开始和许多第一流的英国数学家交往或通信，其中有数学家、逻辑学家德·摩根。摩根在19世纪前半叶卷入了一场著名的争论，布尔知道摩根是对的，于是在1848年出版了一本薄薄的小册子来为朋友辩护。这本书是他6年后更伟大的东西的预告，它一问世，立即激起了摩根的赞扬，肯定他开辟了新的、棘手的研究科目。布尔此时已经在研究逻辑代数，即布尔代数。他把逻辑简化成极为容易和简单的一种代数。在这种代数中，适当的材料上的“推理 ”，成了公式的初等运算的事情，这些公式比过去在中学代数第二年级课程中所运用的大多数公式要简单得多。这样，就使逻辑本身受数学的支配。为了使自己的研究工作趋于完善，布尔在此后6年的漫长时间里，又付出了不同寻常的努力。1854年，他发表了《思维规律》这部杰作，当时他已39岁，布尔代数问世了，数学史上树起了一座新的里程碑。几乎像所有的新生事物一样，布尔代数发明后没有受到人们的重视。欧洲大陆著名的数学家蔑视地称它为没有数学意义的、哲学上稀奇古怪的东西，他们怀疑英伦岛国的数学家能在数学上做出独特贡献。布尔在他的杰作出版后不久就去世了。20世纪初，罗素在《数学原理》中认为，“纯数学是布尔在一部他称之为《思维规律》的著作中发现的。”此说一出，立刻引起世人对布尔代数的注意。今天，布尔发明的逻辑代数已经发展成为纯数学的一个主要分支。
　　在离散数学中，布尔代数(有时叫布尔格)是有补分配格（可参考格的定义)可以按各种方式去认为元素是什么；最常见的是把它们当作一般化的真值。作为一个简单的例子，假设有三个条件是独立的为真或为假。布尔代数的元素可以接着精确指定那些为真；那么布尔代数自身将是所有八种可能性的一个搜集，和与之在一起的组合它们的方式。
　　有时也被称为布尔代数的一个相关主题是布尔逻辑，它可以被定义为是所有布尔代数所公有的东西。它由在布尔代数的元素间永远成立的关系组成，而不管你具体的那个布尔代数。因为逻辑门和某些电子电路的代数在形式上也是这样的，所以同在数理逻辑中一样，布尔逻辑也在工程和计算机科学中研究。
　　在布尔代数上的运算被称为AND(与)、OR(或)和NOT(非)。代数结构要是布尔代数，这些运算的行为就必须和两元素的布尔代数一样(这两个元素是TRUE(真)和FALSE(假))。

　　布尔代数是一个集合 A，提供了两个二元运算 \land (逻辑与)、$\backslash lor\; (逻辑或)，一个一元运算\; \backslash lnot$ / ~ (逻辑非)和两个元素 0(逻辑假)和 1(逻辑真)，此外，对于集合 A 的所有元素 a、b 和 c，下列公理成立:
　　 a \lor (b \lor c) = (a \lor b) \lor c $a\; \backslash land\; (b\; \backslash land\; c)\; =\; (a\; \backslash land\; b)\; \backslash land\; c\; 结合律$
　　 a \lor b = b \lor a $a\; \backslash land\; b\; =\; b\; \backslash land\; a\; 交换律$
　　 a \lor (a \land b) = a $a\; \backslash land\; (a\; \backslash lor\; b)\; =\; a\; 吸收律$
　　 a \lor (b \land c) = (a \lor b) \land (a \lor c) $a\; \backslash land\; (b\; \backslash lor\; c)\; =\; (a\; \backslash land\; b)\; \backslash lor\; (a\; \backslash land\; c)\; 分配律$
　　 a \lor \lnot a = 1 $a\; \backslash land\; \backslash lnot\; a\; =\; 0\; 互补律$
　　上面的前三对公理: 结合律、交换律和吸收律，意味着 (A, \land, $\backslash lor)\; 是一个格。所以布尔代数也可以定义为一个分配的有补格。$
　　从这些公理，你可以展示出最小元素 0、最大元素 1 和任何元素 a 的补 ¬a 都是唯一确定的。对于 A 中的所有的 a 和 b，下列恒等式也成立:
　　 a \lor a = a $a\; \backslash land\; a\; =\; a\; 幂等律$
　　 a \lor 0 = a $a\; \backslash land\; 1\; =\; a\; 有界律$
　　 a \lor 1 = 1 $a\; \backslash land\; 0\; =\; 0$
　　 \lnot 0 = 1 $\backslash lnot\; 1\; =\; 0\; 0\; 和\; 1\; 是互补的$
　　 \lnot (a \lor b) = \lnot a \land \lnot b $\backslash lnot\; (a\; \backslash land\; b)\; =\; \backslash lnot\; a\; \backslash lor\; \backslash 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 : e2 = e, ex = xe, ∀x ∈ R }
　　则集合 A 成为有两个运算 e ∨ f := e + f + ef 和 e ∧ f := ef 的布尔代数。

　　Image:Hasse diagram of powerset of 3.png
　　子集的布尔格同任何格一样，布尔代数 (A, \land, $\backslash lor)\; 可以引出偏序集\; (A,\; \le )，通过定义$
　　a ≤ b 当且仅当 a = a \land b (它也等价于 b = a $\backslash lor\; b)。$
　　事实上你还可以把布尔代数定义为有最小元素 0 和最大元素 1 的分配格 (A, ≤) (考虑为偏序集合)，在其中所有的元素 x 都有补 ¬x 满足
　　x \land ¬x = 0 并且 x $\backslash lor\; \neg x\; =\; 1$
　　这里的 \land 和 $\backslash lor\; 用来指示两个元素的下确界(交)和上确界(并)。还有，如果上述意义上的补存在，则它们是可唯一确定的。$
　　代数的和序理论的观点通常可以交替的使用，并且二者都是有重要用处的，可从泛代数和序理论引入结果和概念。在很多实际例子中次序关系、合取(逻辑与)、析取(逻辑或)和否定(逻辑非)都是自然的可获得的，所以可直接利用这种联系。

　　你还可以把来自序理论的对偶性的普遍认识应用于布尔代数。特别是，所有的布尔代数的次序对偶，或者等价的说通过对换 \land 与 $\backslash lor\; 所获得的代数，也是布尔代数。一般的说，布尔代数的任何有效的规律都可以变换成另一个有效的对偶规律，通过对换\; 0\; 与\; 1，\backslash land$ 与 \lor，和 ≤ 与 ≥。
[编辑本段]其他记号
　　布尔代数的运算符可以用各种方式表示。它们经常简单写成 AND、OR 和 NOT。在描述电路时，还可以使用 NAND (NOT AND)、NOR (NOT OR) 和 XOR (排斥的 OR)。数学家、工程师和程序员经常使用 + 表示 OR 和 · 表示 AND (因为在某些方面这些运算类似于在其他代数结构中的加法和乘法，并且这种运算易于对普通代数熟悉的人得到积之和范式)，和把 NOT 表示为在要否定的表达式顶上画一条横线。
　　这里我们使用另一种常见记号，"交" \land 表示 AND，"并" $\backslash lor\; 表示\; OR，和\; \neg \; 表示\; NOT。(使用只有文本的浏览器的读者将见到\; LaTeX\; 代码而不是他们表示的楔形符号。)$

　　在布尔代数 A 和 B 之间的同态是一个函数 f : A → B，对于在 A 中所有的 a, b 都有:
　　f(a \lor b) = f(a) $\backslash lor\; f(b)$
　　f(a \land b) = f(a) $\backslash land\; f(b)$
　　f(0) = 0
　　f(1) = 1
　　接着对于在 A 中所有的 a，f(¬a) = ¬f(a) 同样成立。所有布尔代数的类，和与之在一起的态射(morphism)的概念，形成了一个范畴。从 A 到 B 的同构是双射的从 A 到 B 的同态。同态的逆也是同态，我们称两个布尔代数 A 和 B 为同态的。从布尔代数理论的立场上，它们是不能区分的；它们只在它们的元素的符号上有所不同。

　　每个布尔代数 (A, \land, $\backslash lor)\; 都引出一个环\; (A,\; +,\; *)，通过定义\; a\; +\; b\; =\; (a\; \backslash land$ ¬b) \lor (b $\backslash land\; \neg a)\; (这个运算在集合论中叫做"对称差"在逻辑中叫做XOR(异或))\; 和\; a\; *\; b\; =\; a\; \backslash land$ b。这个环的零元素符合布尔代数的 0；环的乘法单位元素是布尔代数的 1。这个环有对于 A 中的所有的 a 保持 a * a = a 的性质；有这种性质的环叫做布尔环。
　　反过来，如果给出布尔环 A，我们可以把它转换成布尔代数，通过定义 x \lor y = x + y + xy 和 x $\backslash land\; y\; =\; xy。因为这两个运算是互逆的，我们可以说每个布尔环引发一个布尔代数，或反之。此外，映射\; f\; :\; A\; \to \; B\; 是布尔代数的同态，当且仅当它是布尔环的同态。布尔环和代数的范畴是等价的。$
　　布尔代数 A 的理想是一个子集 I，对于在 I 中的所有 x, y 我们有 x \lor y 在 I 中，并且对于在 A 中的所有 a 我们有 a $\backslash land\; x\; 在\; I\; 中。理想的概念符合在布尔环\; A\; 中环理想的概念。A\; 的理想\; I\; 叫做素理想，如果\; I\; \ne \; A；并且如果\; a\; \backslash 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 $\backslash 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 完成的。

　　代入法则 它可描述为逻辑代数式中的任何变量A，都可用另一个函数Z代替，等式仍然成立。
　　对偶法则 它可描述为对任何一个逻辑表达式F，如果将其中的“+”换成“*”，“*”换成“+”“1”换成“0”，“0”换成“1”，仍保持原来的逻辑优先级，则可得到原函数F的对偶式G，而且F与G互为对偶式。我们可以看出基本公式是成对出现的，二都互为对偶式。
　　反演法则 有原函数求反函数就称为反演（利用摩根定律），
　　我们可以把反演法则这样描述：将原函数F中的“*”换成“+”，“+”换成“*”，“0”换成“1”，“1”换成“0”；原变量换成反变量，反变量换成原变量，长非号即两个或两个以上变量的非号不变，就得到原函数的反函数。
　　布尔代数定律：
　　互补律：
　　第一互补律： 若A=0，则~A=1,若A=1，则~A=0 注：~A =ＮＯＴ　Ａ
　　第二互补律： A*~A=0
　　第三互补律： A+~A=1
　　双重互补律： /<~A>=//A=A
　　交换律：
　　AND交换律： A*B=B*A
　　OR交换律： A+B=B+A
　　结合律：
　　AND结合律： Ａ＜Ｂ*Ｃ＞＝Ｃ*＜Ａ*Ｂ＞
　　ＯＲ结合律：　Ａ＋＜Ｂ＋Ｃ＞＝Ｃ＋＜Ａ＋Ｂ＞
　　分配率：
　　第一分配率：　Ａ*＜Ｂ＋Ｃ＞＝＜Ａ*Ｂ＞＋＜Ａ*Ｃ＞
　　第二分配率：　Ａ＋＜Ｂ*C>=*
　　重言律：
　　第一重言律： A*A=A 若A=1，则A*A=1；若A=0，则A*A=0。因此表达式简化为A
　　第二重言律： A+A=A 若A=1，则1+1=1；若A=0，则0+0=0。因此表达式简化为A
　　带常数的重言律：
　　A+!=A
　　A*1=A
　　A*0=0
　　A+0=A
　　吸收率：
　　第一吸收率： A*=A
　　第二吸收率： A+=A