布尔代数
序理论
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> 用来指示两个元素的
下确界
(交)和
上确界
(并)。还有，如果上述意义上的补存在，则它们是可唯一确定的。
代数的和
序理论
的观点通常可以交替的使用，并且二者都是有重要用处的，可从泛代数和序理论引入结果和概念。在很多实际例子中次序关系、
合取
(逻辑与)、
析取
(逻辑或)和否定(逻辑非)都是自然的可获得的，所以可直接利用这种联系。
布尔代数
其他记号
布尔代数的运算符可以用各种方式表示。它们经常简单写成 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 中。
布尔代数
公理化
在 1933 年，
美国
数学家 Edward Vermilye Huntington (1874-1952) 展示了对布尔代数的如下公理化：
结合律
： (x + y) + z = x + (y + z)。
Huntington
等式
： n(n(x) + y) + n(n(x) + n(y)) = x。
Herbert Robbins 接着摆出下列问题： Huntington
等式
能否缩短为下述的等式，并且这个新等式与
结合律
和
交换律
一起成为布尔代数的基础? 通过一组叫做 Robbins 代数的公理，问题就变成了： 是否所有的 Robbins 代数都是布尔代数?
结合律
： (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 =NOT A
第二互补律：A*~A=0
第三互补律：A+~A=1
双重互补律：/<~A>=//A=A
交换律：
AND交换律：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
子集的布尔格的哈斯图
在{0,1}上的运算可以用
真值表
展出，选取0和1为真值
假
和
真
。它们可以按统一和不依赖应用的方式列出，允许我们命名或至少单独列出它们。这些名字对布尔运算提供方便的简写。
n
元运算的名字是2位的二进制数。有2个这种运算，你不能得到更简明的命名法了!
下面展示元数从0到2的所有运算的这种格局和关联的名字。
直到2元的布尔运算的真值表
常量
一元运算
|
x
0
|
|
f
0
|
f
1
|
f
2
|
f
3
|
|
0
|
|
0
|
1
|
0
|
1
|
|
1
|
|
0
|
0
|
1
|
1
|
二元运算
|
x
0
|
x
1
|
|
f
0
|
f
1
|
f
2
|
f
3
|
f
4
|
f
5
|
f
6
|
f
7
|
f
8
|
f
9
|
f
10
|
f
11
|
f
12
|
f
13
|
f
14
|
f
15
|
|
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
元有2行，每个行给出
n
个变量
x
0,…
xn
−1的一个求值或绑定，而每列都有表头
fi
，它们给出第
i
个
n
元运算
fi
(
x
0,…,
xn
−1)在这个求值下的值。运算包括变量本身，例如
f
2是
x
0而
f
10是
x
0 (作为它的一元对应者的两个复件)而
f
12是
x
1 (没有一元对应者)。否定或补¬
x
0出现为
f
1再次出现为
f
5，连同
f
3 (¬
x
1在1元时没有出现)，析取或并
x
0∨
x
1出现为
f
14，合取或交
x
0∧
x
1出现为
f
8，蕴涵
x
0→
x
1出现为
f
13，异或或对称差
x
0⊕
x
1出现为
f
6，差集
x
0−
x
1出现为
f
2等等。对布尔函数的其他命名或表示可参见零阶逻辑。
作为关于它的形式而非内容的次要详情，一个代数的运算传统上组织为一个列表。我们这里通过在{0,1}上有限运算索引了布尔代数的运算，上述真值表表示的排序首先按元数，其次为每个元数运算的列出表格。给定元数的列表次序是如下两个规则确定的。
