布尔代数 · aiwiki.page

布尔代数是代数的一个分支，研究用于描述合取、析取和否定的运算。最简单的布尔代数只有两个值：0 和 1，分别表示假和真。更一般地说，布尔代数是一种称为有补有界分配格的抽象结构，其元素不必是数或真值。布尔代数通过一套共同的恒等式，将逻辑学、集合论和数字电路设计联系起来。(boole.stanford.edu)

历史发展

布尔代数以乔治·布尔的名字命名。布尔在《逻辑的数学分析》（1847 年）和《思维规律研究》（1854 年）中提出了用于逻辑推理的代数方法。他用符号表示类及逻辑关系，并通过代数运算进行推导。他最初提出的体系在记号和解释上与现代形式有所不同。(georgeboole.com)

克劳德·香农于 1938 年发表的论文《继电器与开关电路的符号分析》，展示了布尔代数的一项重要工程应用。香农说明了如何利用二态变量的代数来分析开关网络，并指导等效电路的构建，从而将符号推理与电气工程中的实际问题联系起来。(tubes.mit.edu)

运算与真值

二元素布尔代数的底集为 $\{0,1\}$ 。它的三种标准运算是与（AND），记作 $a\land b$ ；或（OR），记作 $a\lor b$ ；以及非（NOT），记作 $\neg a$ 。与运算仅在两个输入均为 1 时输出 1。或运算在至少一个输入为 1 时输出 1，也包括两个输入均为 1 的情况。非运算将 0 和 1 互换。真值表明确列出了这些运算的结果：(csg.csail.mit.edu)

$a$	$b$	$a\land b$	$a\lor b$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

工程中常用乘号表示与运算、加号表示或运算，并用上划线表示非运算。这些符号并不表示普通的算术运算：在布尔代数中， $1+1=1$ 。或运算也不同于异或运算；后者恰好在两个输入不同时输出 1。(ocw.mit.edu)

代数结构与定律

形式上，布尔代数由集合 $B$ 、二元运算 $\land$ 和 $\lor$ 、一元补运算 $\neg$ ，以及指定元素 0 和 1 组成。它的公理要求这一结构是一个有界分配格，且每个元素都有补元。两种二元运算均满足交换律和结合律，也满足吸收律，并且彼此满足分配律：(boole.stanford.edu)

a\land(a\lor b)=a,\qquad a\lor(a\land b)=a,

a\land(b\lor c)=(a\land b)\lor(a\land c),

a\lor(b\land c)=(a\lor b)\land(a\lor c).

界元素与补元满足

a\land1=a,\quad a\lor0=a,\quad a\land\neg a=0,\quad a\lor\neg a=1.

由此可推出幂等律 $a\land a=a$ 和 $a\lor a=a$ ，以及双重否定律 $\neg\neg a=a$ 。德摩根定律描述了补运算如何使这两种运算相互转换：

\neg(a\land b)=\neg a\lor\neg b,\qquad \neg(a\lor b)=\neg a\land\neg b.

这些恒等式使表达式能够在保持其值不变的前提下进行系统变换。(csg.csail.mit.edu)

集合与表示

在集合论中，给定集合 $X$ 的幂集 $\mathcal P(X)$ 包含 $X$ 的所有子集，并构成一个布尔代数。与运算对应交集，或运算对应并集，非运算对应相对于 $X$ 的补集。空集是 0， $X$ 本身是 1。一个包含这两个界元素且对三种运算封闭的集合族，也构成布尔代数，即使它只包含 $X$ 的部分子集。(boole.stanford.edu)

与布尔代数相联系的偏序定义为

a\leq b\quad\text{当且仅当}\quad a\land b=a.

对于集合，这就是包含关系。每个有限布尔代数都与其原子集合的幂集同构，其中原子是指极小非零元素。因此，有限布尔代数的元素个数为 $2^n$ ，其中 $n$ 是某个非负整数。斯通表示定理推广了这种集合解释：每个布尔代数都与一个集合代数同构。该定理的拓扑表述将布尔代数与拓扑学中的某些特殊空间联系起来。(math.uwaterloo.ca)

逻辑表达式与范式

在经典命题逻辑中，布尔运算用来解释“且”“或”和“非”这些联结词。一个 $n$ 变量的布尔函数是从 $\{0,1\}^n$ 到 $\{0,1\}$ 的映射。它的真值表包含 $2^n$ 行输入，因此完整真值表的规模随变量数量呈指数增长。不同的表达式可能描述同一个函数。(boole.stanford.edu)

每个布尔函数都可以表示为析取范式，即若干合取项的析取。构造其标准形式时，取真值表中输出为 1 的每一行，用全部变量构成一个合取项；某个变量在该行被赋值为 0 时，就对它取否定。再将这些项用或运算连接起来。与之对偶，合取范式是若干析取子句的合取。标准形式提供了系统的表示方法，但不一定简洁。(ocw.mit.edu)

数字电路实现

在数字系统中，布尔值表示由信号承载的抽象状态。逻辑门实现布尔运算，而相互连接的逻辑门则实现更复杂的函数。与、或、非这三种运算足以表示任何布尔函数。仅用与非（NAND）或仅用或非（NOR）也能做到这一点，因此它们各自都具有函数完备性。(csg.csail.mit.edu)

代数化简可以简化所需的电路结构。例如，

(a\land b)\lor(a\land\neg b) =a\land(b\lor\neg b)=a.

不过，布尔等价性描述的是逻辑行为，而非全部物理性质。等价的实现方式可能在传播延迟和逻辑门布局上有所不同。因此，电路综合需要将代数变换与实现约束相结合，其中包括单个逻辑门可用的输入端数量。(ocw.mit.edu)