布尔代数介绍

62 阅读 0 评论 41 点赞

我是靠谱客的博主欢呼保温杯，最近开发中收集的这篇文章主要介绍布尔代数介绍，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

布尔代数起源于数学领域，是一个用于集合运算和逻辑运算的公式：〈B，∨，∧，¬ 〉。其中B为一个非空集合，∨，∧为定义在B上的两个二元运算，¬为定义在B上的一个一元运算。
通过布尔代数进行集合运算可以获取到不同集合之间的交集、并集或补集，进行逻辑运算可以对不同集合进行与、或、非。
中文名
布尔代数
外文名
Boolean algebra
发现者
G.布尔
分类
数学专有名词
学科
高数
相关视频
17.5万播放|02:26
为什么说布尔代数是计算机的基本运算方式
6091播放|03:54
布尔代数虽长时间没有实际用处，却吸引了香农的注意｜解码科技史
3万播放|10:59
「Coding Master」第2话二进制算术与布尔代数
发现历史运算理论衍生理论应用领域TA说
发现历史
发现
英国数学家为了研究思维规律（逻辑学、数理逻辑)于1847和1854年提出的数学模型。此后R.戴德金把它作为一种特殊的格。由于缺乏物理背景，所以研究缓慢，到了20世纪30～40年代才有了新的进展，大约在 1935年， M.H.斯通首先指出布尔代数与环之间有明确的联系，这使布尔代数在理论上有了一定的发展。布尔代数在代数学（代数结构）、逻辑演算、集合论、拓扑空间理论、测度论、概率论、泛函分析等数学分支中均有应用；1967年后，在数理逻辑的分支之一的公理化集合论以及模型论的理论研究中，也起着一定的作用。近几十年来，布尔代数在自动化技术、电子计算机的逻辑设计等工程技术领域中有重要的应用。
布尔代数
数学家G.布尔
1835年，20岁的乔治·布尔开办了一所私人授课学校。为了给学生们开设必要的数学课程，他兴趣浓厚地读起了当时一些介绍数学知识的教科书。不久，他就感到惊讶，这些东西就是数学吗？实在令人难以置信。于是，这位只受过初步数学训练的青年自学了艰深的《天体力学》和很抽象的《分析力学》。由于他对代数关系的对称和美有很强的感觉，在孤独的研究中，他首先发现了不变量，并把这一成果写成论文发表。这篇高质量的论文发表后，布尔仍然留在小学教书，但是他开始和许多第一流的英国数学家交往或通信，其中有数学家、逻辑学家德·摩根。摩根在19世纪前半叶卷入了一场著名的争论，布尔知道摩根是对的，于是在1848年出版了一本薄薄的小册子来为朋友辩护。这本书是他6年后更伟大的东西的预告，它一问世，立即激起了摩根的赞扬，肯定他开辟了新的、棘手的研究科目。布尔此时已经在研究逻辑代数，即布尔代数。他把逻辑简化成极为容易和简单的一种代数。在这种代数中，适当的材料上的“推理”，成了公式的初等运算的事情，这些公式比过去在中学代数第二年级课程中所运用的大多数公式要简单得多。这样，就使逻辑本身受数学的支配。为了使自己的研究工作趋于完善，布尔在此后6年的漫长时间里，又付出了不同寻常的努力。1854年，他发表了《思维规律》这部杰作，当时他已39岁，布尔代数问世了，数学史上树起了一座新的里程碑。几乎像所有的新生事物一样，布尔代数发明后没有受到人们的重视。欧洲大陆著名的数学家蔑视地称它为没有数学意义的、哲学上稀奇古怪的东西，他们怀疑英伦岛国的数学家能在数学上做出独特贡献。布尔在他的杰作出版后不久就去世了。20世纪初，罗素在《数学原理》中认为，“纯数学是布尔在一部他称之为《思维规律》的著作中发现的。”此说一出，立刻引起世人对布尔代数的注意。今天，布尔发明的逻辑代数已经发展成为纯数学的一个主要分支。
德·摩根
在离散数学中，布尔代数(有时叫布尔格)是有补分配格（可参考格的定义)可以按各种方式去认为元素是什么；最常见的是把它们当作一般化的真值。作为一个简单的例子，假设有三个条件是独立的为真或为假。布尔代数的元素可以接着精确指定那些为真；那么布尔代数自身将是所有八种可能性的一个搜集，和与之在一起的组合它们的方式。
离散数学
有时也被称为布尔代数的一个相关主题是布尔逻辑，它可以被定义为是所有布尔代数所公有的东西。它由在布尔代数的元素间永远成立的关系组成，而不管你具体的那个布尔代数。因为逻辑门和某些电子电路的代数在形式上也是这样的，所以同在数理逻辑中一样，布尔逻辑也在工程和计算机科学中研究。[1]
运算理论
基本理论
在布尔代数上的运算被称为AND(与)、OR(或)和NOT(非)。代数结构要是布尔代数，这些运算的行为就必须和两元素的布尔代数一样(这两个元素是TRUE(真)和FALSE(假))。亦称逻辑代数.布尔(Boole，G.)为研究思维规律(逻辑学)于1847年提出的数学工具.布尔代数是指代数系统B=〈B，+，·，′〉
它包含集合B连同在其上定义的两个二元运算+，·和一个一元运算′，布尔代数具有下列性质：对B中任意元素a，b，c，有：
1．a+b=b+a， a·b=b·a.
2．a·(b+c)=a·b+a·c，
a+(b·c)=(a+b)·(a+c).
3．a+0=a， a·1=a.
4．a+a′=1， a·a′=0.
布尔代数也可简记为B=〈B，+，·，′〉.在不致混淆的情况下，也将集合B称作布尔代数.布尔代数B的集合B称为布尔集，亦称布尔代数的论域或定义域，它是代数B所研究对象的全体.一般要求布尔集至少有两个不同的元素0和1，而且其元素对三种运算+，·，′ 都封闭，因此并非任何集合都能成为布尔集.在有限集合的情形，布尔集的元素个数只能是2n，n=0，1，2，…二元运算+称为布尔加法，布尔和，布尔并，布尔析取等；二元运算·称为布尔乘法，布尔积，布尔交，布尔合取等；一元运算 ′ 称为布尔补，布尔否定，布尔代数的余运算等.布尔代数的运算符号也有别种记法，如∪，∩，-;∨，∧，?等.由于只含一个元的布尔代数实用价值不大，通常假定0≠1，称0为布尔代数的零元素或最小元，称1为布尔代数的单位元素或最大元.布尔代数通常用亨廷顿公理系统来定义，但也有用比恩公理系统或具有0与1的有补分配格等来定义的。[2]
共2张
布尔代数有关书籍
例子
最简单的布尔代数只有两个元素 0 和 1，并通过如下规则（真值表）定义：
∧
0
1
0
0
0
1
0
1
∨
0
1
0
0
1
1
1
1
¬
0
1

1
0
它应用于逻辑中，解释 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 的布尔代数。
特性和示例
要使用布尔代数，必须了解布尔代数的特性：
元素是一个集合的成员。例如：A1，用A1 ∈ B表示。如果A1不是这个集合的元素，用A1 B表示。
全集是集合X，包含集合X内的所有元素。
空集是集合内不包含任何元素。
子集是包含部分元素的集合，例如A，包含集合X中的元素A1，A2，用A∈B表示。
一元运算是对单个集合（例如A）进行运算，目的是求全集内除集合A以外的元素，用¬A表示。
二元运算是对两个集合（例如A1、A2）进行运算，目的是：求两个集合的共有元素，用A1∧A2表示；求两个集合的所有元素，用A1∨A2表示。
了解了布尔代数的抽象化特性后，我们通过实例来介绍如何使用布尔代数进行集合运算。设置集合B中包含元素{1，2，3，4，5，6，7，8，9，10}，子集A1中包含元素{1，2，3，4，5}，子集A2中包含元素{3，4，5，7，10}。那么对应的运算结果为：
¬B=¬1=0，表示空集。
¬A1={6，7，8，9，10}。
A1∧A2={1，2，3，4，5}∧{3，4，5，7，10}={3，4，5}。
A1∨A2={1，2，3，4，5}∨{3，4，5，7，10}={1，2，3，4，5，7，10}。
序理论
Image:Hasse diagram of powerset of 3.png
子集的布尔格同任何格一样，布尔代数 (A,<math>land</math>,<math>lor</math>) 可以引出偏序集(A,≤)，通过定义
a ≤ b当且仅当a = a <math>land</math> b (它也等价于 b = a <math>lor</math> b)。
事实上你还可以把布尔代数定义为有最小元素 0 和最大元素 1 的分配格 (A,≤) (考虑为偏序集合)，在其中所有的元素 x 都有补 ¬x 满足
x <math>land</math> ¬x = 0 并且 x <math>lor</math> ¬x = 1
这里的 <math>land</math> 和 <math>lor</math> 用来指示两个元素的下确界(交)和上确界(并)。还有，如果上述意义上的补存在，则它们是可唯一确定的。
代数的和序理论的观点通常可以交替的使用，并且二者都是有重要用处的，可从泛代数和序理论引入结果和概念。在很多实际例子中次序关系、合取(逻辑与)、析取(逻辑或)和否定(逻辑非)都是自然的可获得的，所以可直接利用这种联系。
对偶原理
你还可以把来自序理论的对偶性的普遍认识应用于布尔代数。特别是，所有的布尔代数的次序对偶，或者等价的说通过对换 <math>land</math> 与 <math>lor</math> 所获得的代数，也是布尔代数。一般的说，布尔代数的任何有效的规律都可以变换成另一个有效的对偶规律，通过对换 0 与 1，<math>land</math> 与 <math>lor</math>，和 ≤ 与 ≥。
其他记号
布尔代数的运算符可以用各种方式表示。它们经常简单写成 AND、OR 和 NOT。在描述电路时，还可以使用 NAND (NOT AND)、NOR (NOT OR) 和 XOR (排斥的 OR)。数学家、工程师和程序员经常使用 + 表示 OR 和 · 表示 AND (因为在某些方面这些运算类似于在其他代数结构中的加法和乘法，并且这种运算易于对普通代数熟悉的人得到积之和范式)，和把 NOT 表示为在要否定的表达式顶上画一条横线。
这里我们使用另一种常见记号，"交" <math>land</math> 表示 AND，"并" <math>lor</math> 表示 OR，和 ¬ 表示 NOT。(使用只有文本的浏览器的读者将见到 LaTeX 代码而不是他们表示的楔形符号。)
同态和同构
在布尔代数 A 和 B 之间的同态是一个函数 f : A → B，对于在 A 中所有的 a,b 都有：
f(a <math>lor</math> b) = f(a) <math>lor</math> f(b)
f(a <math>land</math> b) = f(a) <math>land</math> f(b)
f(0) = 0
f(1) = 1
接着对于在 A 中所有的 a，f(¬a) = ¬f(a) 同样成立。所有布尔代数的类，和与之在一起的态射(morphism)的概念，形成了一个范畴。从 A 到 B 的同构是双射的从 A 到 B 的同态。同态的逆也是同态，我们称两个布尔代数 A 和 B 为同态的。从布尔代数理论的立场上，它们是不能区分的；它们只在它们的元素的符号上有所不同。
衍生理论
布尔环
每个布尔代数 (A,<math>land</math>,<math>lor</math>) 都引出一个环 (A,+,*)，通过定义 a + b = (a <math>land</math> ¬b) <math>lor</math> (b <math>land</math> ¬a) (这个运算在集合论中叫做"对称差"在逻辑中叫做XOR(异或)) 和 a * b = a <math>land</math> b。这个环的零元素符合布尔代数的 0；环的乘法单位元素是布尔代数的 1。这个环有对于 A 中的所有的 a 保持 a * a = a 的性质；有这种性质的环叫做布尔环。
反过来，如果给出布尔环A，我们可以把它转换成布尔代数，通过定义 x <math>lor</math> y = x + y + xy 和 x <math>land</math> y = xy。因为这两个运算是互逆的，我们可以说每个布尔环引发一个布尔代数，或反之。此外，映射 f : A → B 是布尔代数的同态，当且仅当它是布尔环的同态。布尔环和代数的范畴是等价的。
布尔代数 A 的理想是一个子集 I，对于在 I 中的所有 x,y 我们有 x <math>lor</math> y 在 I 中，并且对于在 A 中的所有 a 我们有 a <math>land</math> x 在 I 中。理想的概念符合在布尔环 A中环理想的概念。A 的理想 I 叫做素理想，如果 I ≠ A；并且如果 a <math>land</math> b 在 I 中总是蕴涵 a 在 I 中或 b 在 I 中。A 的理想 I 叫做极大理想，如果 I ≠ A 并且真正包含 I 的唯一的理想是 A 自身。这些概念符合布尔环A 中的素理想和极大理想的环理论概念。
理想的对偶是滤子。布尔代数 A 的滤子是子集 p，对于在 p 中的所有 x,y 我们有 x <math>land</math> y 在 p 中，并且对于在 A 中的所有 a，如果 a <math>lor</math> 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 完成的。[3]
规则
代入法则它可描述为逻辑代数式中的任何变量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 =NOT A
第二互补律：A*~A=0
第三互补律：A+~A=1
双重互补律：/<~A>=//A=A
交换律：
AND交换律：A*B=B*A
OR交换律： A+B=B+A
结合律：
AND结合律：A<B*C>=C*<A*B>
OR结合律： A+<B+C>=C+<A+B>
分配律：
第一分配律： A*<B+C>=<A*B>+<A*C>
第二分配律： A+<B*C>=<A+B>*<A+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+1=1
A*1=A
A*0=0
A+0=A
吸收律：
第一吸收律： A*<A+B>=A
第二吸收律： A+<A*B>=A
原型
在k元素集合X上有k个n元运算f: X→X，因此在{0,1}上有2个n元运算。所以得出所有布尔代数，不论大小都两个常量或“零元”运算，四个一元运算，16个二元运算，256个三元运算，以此类推，它们叫做给定布尔代数的布尔运算。只有一个例外就是一个元素的布尔代数，它叫做退化的或平凡的（被一些早期作者禁用），布尔代数的所有运算可以被证明是独特的。（在退化情况下，给定元数的所有运算都是同样的运算因为对所有输入都返回同样结果。）
在{0,1}上的运算可以用真值表展出，选取0和1为真值假和真。它们可以按统一和不依赖应用的方式列出，允许我们命名或至少单独列出它们。这些名字对布尔运算提供方便的简写。n元运算的名字是2位的二进制数。有2个这种运算，你不能得到更简明的命名法了!
子集的布尔格的哈斯图
下面展示元数从0到2的所有运算的这种格局和关联的名字。
直到2元的布尔运算的真值表
常量
f0
f1
0
1
一元运算
x0

f0
f1
f2
f3
0

0
1
0
1
1

0
0
1
1
二元运算
x0
x1

f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
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
展开全部
这些表格继续到更高元数上，对n元有2行，每个行给出n个变量x0,…xn−1的一个求值或绑定，而每列都有表头fi，它们给出第i个n元运算fi(x0,…,xn−1)在这个求值下的值。运算包括变量本身，例如f2是x0而f10是x0 (作为它的一元对应者的两个复件)而f12是x1 (没有一元对应者)。否定或补¬x0出现为f1再次出现为f5，连同f3 (¬x1在1元时没有出现)，析取或并x0∨x1出现为f14，合取或交x0∧x1出现为f8，蕴涵x0→x1出现为f13，异或或对称差x0⊕x1出现为f6，差集x0−x1出现为f2等等。对布尔函数的其他命名或表示可参见零阶逻辑。
作为关于它的形式而非内容的次要详情，一个代数的运算传统上组织为一个列表。我们这里通过在{0,1}上有限运算索引了布尔代数的运算，上述真值表表示的排序首先按元数，其次为每个元数运算的列出表格。给定元数的列表次序是如下两个规则确定的。
(i)表格左半部分的第i行是i的二进制表示，最低有效位或第0位在最左（“小端”次序，最初由艾伦·图灵提议，所以可不无合理的叫做图灵序）。
(ii)表格的右半部分的第j列是j的二进制表示，还是按小端次序。在效果上运算的下标就是这个运算的真值表。[1]
应用领域
应用
布尔代数不仅可以在数学领域内实现集合运算，更广泛应用于电子学、计算机硬件、计算机软件等领域的逻辑运算：当集合内只包含两个元素（1和0）时，分别对应{真}和{假}，可以用于实现对逻辑的判断。
常见的应用包括：
数字电路设计，0和1与数字电路中某个位的状态对应，例如：高电平、低电平。
计算机的网络设置，利用计算机的二进制特性，将子网掩码与本机IP地址进行逻辑与运算，可以得到计算机的网络地址和主机地址。
数据库应用，通过SQL语句查询数据库时需要进行逻辑运算，确定具体的查询目标。