布尔代数

代数结构

布尔代数(英语:Boolean algebra)在抽象代数中是指捕获了集合运算和逻辑运算二者的根本性质的一个代数结构(就是说一组元素和服从定义的公理的在这些元素上运算)。特别是,它处理集合运算交集并集补集;和逻辑运算

子集的布尔格的哈斯图

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

相似于集合论断言子集A和它的补集AC有空交集,

因为真值可以在逻辑电路中表示为二进制数或电平,这种相似性同样扩展到它们,所以布尔代数在电子工程计算机科学中同在数理逻辑中一样有很多实践应用。在电子工程领域专门化了的布尔代数也叫做逻辑代数,在计算机科学领域专门化了布尔代数也叫做布尔逻辑

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

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

布尔代数又译为布林代数,然而布尔代数得名于乔治·布尔,他是爱尔兰科克的皇后学院的英国数学家。布林(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 CohenDana Scott和其他人使用布尔代数的分支也就是力迫布尔值模型,深入发现了数理逻辑公理化集合论中的新成果。

形式定义

编辑

布尔代数是一个集合A,其上定义了以下结构:

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

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

    结合律
    交换律
    吸收律
    分配律
    互补律

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

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

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

    幂等律
    有界律
   
    0和1是互补的
    德·摩根定律
  对合律

其它运算

编辑

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

  • 二元运算-: 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或  全集 高电位
 
¬或~或'或c 补集 反相器
 
∧或∩ 下确界 交集 及闸
 
∨或∪ 上确界 并集 或闸
 
   相对补集
 
-或  差集 实质非蕴涵 蕴含非闸
 
⊕或Δ 对称差 对称差 异或 异或闸
 
条件 条件 蕴含闸
 
双向条件 双条件 同或闸
 
|或↑ 谢费尔竖线 与非 反及闸
 
皮尔斯箭头 或非 反或闸
 

例子

编辑
  • 最简单的布尔代数只有两个元素0和1,并通过如下规则定义:
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
  • 它应用于逻辑中,解释0为“伪”,1为“真”,∧为“与”,∨为“或”,¬为“非”。涉及变量和布尔运算的表达式代表了陈述形式,两个这样的表达式可以使用上面的公理证实为等价的,当且仅当对应的陈述形式是逻辑等价的。
  • 两元素的布尔代数也是在电子工程中用于电路设计;这里的0和1代表数字电路中一个的两种不同状态,典型的是高和低电压。电路通过包含变量的表达式来描述,两个这种表达式对这些变量的所有的值是等价的,当且仅当对应的电路有相同的输入-输出行为。此外,所有可能的输入-输出行为都可以使用合适的布尔表达式来建摸。
  • 两元素布尔代数在布尔代数的一般理论中也是重要的,因为涉及多个变量的等式是在所有布尔代数中普遍为真,当且仅当它在两个元素的布尔代数中为真(这总是可以通过平凡的穷举法算法证实)。比如证实下列定律(“合意定理”)在所有布尔代数中是普遍有效的:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • 任何给定集合S幂集(子集的集合)形成有两个运算∨ := ∪ (并)和∧ := ∩ (交)的布尔代数。最小的元素0是空集而最大元素1是集合S自身。
  • 有限的或余有限的集合S的所有子集的集合是布尔代数。
  • 对于任何自然数nn的所有正约数的集合形成一个分配格,如果我们对a | bab。这个格是布尔代数当且仅当n无平方数因数的数。这个布尔代数的最小的元素0是自然数1;这个布尔代数的最大元素1是自然数n
  • 布尔代数的另一个例子来自拓扑空间:如果X是一个拓扑空间,它既是开放的又是闭合的,X的所有子集的搜集形成有两个运算∨ := ∪ (并)和∧ := ∩ (交)的布尔代数。
  • 如果R是一个任意的环,并且我们定义“中心幂等元”(central idempotent)的集合为
    A = { eR : e2 = e, ex = xe, ∀xR }
    则集合A成为有两个运算ef := e + f + efef := ef的布尔代数。

原型布尔代数

编辑

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

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

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

直到2元的布尔运算的真值表
常量
0f0 0f1
0 1
一元运算
x0 1f0 1f1 1f2 1f3
0 0 1 0 1
1 0 0 1 1
二元运算
x0 x1 2f0 2f1 2f2 2f3 2f4 2f5 2f6 2f7 2f8 2f9 2f10 2f11 2f12 2f13 2f14 2f15
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

这些表格继续到更高元数上,对n元有2n行,每个行给出n个变量x0,…xn−1的一个求值或绑定,而每列都有表头nfi,它们给出第in元运算nfi(x0,…,xn−1)在这个求值下的值。运算包括变量本身,例如1f2x02f10x0 (作为它的一元对应者的两个复件)而2f12x1 (没有一元对应者)。否定或补¬x0出现为1f1再次出现为2f5,连同2f3x1在1元时没有出现),析取或并x0x1出现为2f14,合取或交x0x1出现为2f8,蕴涵x0x1出现为2f13,异或或对称差x0x1出现为2f6,差集x0x1出现为2f2等等。对布尔函数的其他命名或表示可参见零阶逻辑

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

(i)表格左半部分的第i行是i的二进制表示,最低有效位或第0位在最左(“小端”次序,最初由艾伦·图灵提议,所以可不无合理的叫做图灵序)。
(ii)表格的右半部分的第j列是j的二进制表示,还是按小端次序。在效果上运算的下标就是这个运算的真值表。

序理论的性质

编辑

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

ab 当且仅当a = a   b (它也等价于b = a   b)。

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

x   ¬x = 0并且x   ¬x = 1

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

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

对偶原理

编辑

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

同态和同构

编辑

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

f(a   b) = fa  fb
f(a   b) = fa  fb
f(0)= 0
f(1)= 1

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

布尔同态

编辑

布尔同态是在布尔代数AB之间的函数h: AB使得对于所有布尔运算mfi

h(mfi(x0,…,xm−1)) = mfi(h(x0),…,h(xm−1)).

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

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

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

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

布尔环、理想和滤子

编辑

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

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

布尔代数A理想是一个子集I,对于在I中的所有x, y我们有x   yI中,并且对于在A中的所有a我们有a   xI中。理想的概念符合在布尔环A环理想的概念。A的理想I叫做“素理想”,如果IA;并且如果a   bI中总是蕴涵aI中或bI中。A的理想I叫做“极大理想”,如果IA并且真正包含I的唯一的理想是A自身。这些概念符合布尔环A中的素理想极大理想的环理论概念。

“理想”的对偶是滤子。布尔代数A的“滤子”是子集p,对于在p中的所有x, y我们有x   yp中,并且对于在A中的所有a,如果a   x = aap中。

表示布尔代数

编辑

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

广义布尔代数

编辑

从布尔代数的公理中去掉存在最大元1的要求产生了“广义布尔代数”。形式的说,分配格B是广义布尔代数,如果它有最小元0并且对于任何B中的元素ab使得ab,存在一个元素x使得 并且 。定义 为唯一的x使得 并且 ,我们可以称结构 是“广义布尔代数”,而 是“广义布尔半格”。

广义布尔格完全就是布尔格的理想

公理化布尔代数

编辑

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

  1. 交换律: x + y = y + x
  2. 结合律: (x + y) + z = x + (y + z)。
  3. Huntington等式:  

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

Robbins代数的公理化:

  1. 交换律: x + y = y + x
  2. 结合律: (x + y) + z = x + (y + z)。
  3. Robbins等式:  

这个问题自从1930年代一直是公开的,并成为阿尔弗雷德·塔斯基和他的学生最喜好的问题。

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

其它记号

编辑

布尔代数的运算包含下列几种,基本包含“与”(AND)、“或”(OR)、“非”(NOT),其中由这三种又可组合成NAND(与非)、NOR(或非)、XOR(异或)与XNOR(异或非)。

常见使用记号:“ ”表示AND,“+”表示OR(如CNFDNF中)或者XOR(如ANF中);A中A上面的一横表示NOT;⊕表示XOR;⊙表示XNOR。

参见

编辑

参考资料

编辑
  • 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 .
  • Stoll, R. R., Set Theory and Logic, W. H. Freeman, 1963, 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. ISBN 978-0-521-33779-3. 
  • 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. 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.
  • 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. ISBN 978-0-387-04469-9. 
  • 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. 

外部链接

编辑

A monograph available free online: