30.布尔代数

布尔运算，使得计算机开始有了处理逻辑的能力。

‍‍

‍

莱布尼茨坚信，人类的思想和数字一样可以化繁为简——所有思想都可以分解为数量不多的简单思想。这些简单思想通过一些既定规律，可以组成任意的复杂思想，就像数学运算一样。当两个人发生了争执，他们可以把自己的观点通过数学计算的方式梳理出来，谁对谁错就一目了然了。

为了“计算”思想，莱布尼茨阐述了后来被称为合取（conjunction）、析取（disjunction）、否定（negation）等的逻辑运算规则，成为数理逻辑（mathematical logic）最早的探索者之一。

但逻辑运算在数学上的系统性定义，要等到 19 世纪由英国数学家乔治·布尔（George Boole）首次提出。布尔分别在 1847 年和 1854 年发表了著名的《逻辑的数学分析》和《思维规律的研究》，将数学中的代数方法引入到逻辑学中，被后人称为布尔代数（Boolean algebra），逻辑运算因而也叫布尔运算。

‍

‍

下面通过一个例子介绍简单一下逻辑运算，假设有 X、Y 两个命题：

• X：乔治·布尔发明了二进制。
• Y：乔治·布尔创立了布尔代数。

显然，X 命题是错的，Y 命题是对的。在逻辑学中，我们称：X 命题为假，Y 命题为真。如果用连词将 X、Y 两句话连起来说呢？

比如：乔治·布尔发明了二进制且创立了布尔代数。这句话是错的，即“X 且 Y”的组合命题为假。

再比如：乔治·布尔发明了二进制或创立了布尔代数。这句话是对的，即“X 或 Y”的组合命题为真。

这就是逻辑学中的合取与析取，也称逻辑与和逻辑或。

当然，也有对单个命题的逻辑运算，比如：乔治·布尔没有发明二进制。这句话是对的，即“非 X”为真。

这就是逻辑学中的否定，也称逻辑非。

与、或、非是 3 种最基本、最常用的逻辑运算。将它们组合起来，还可以形成与非、或非、异或、同或等复杂逻辑运算。历史上，布尔和许多其他逻辑学家曾使用过各种层出不穷的符号来表示它们，如今，我们常用下表中的表达形式：

逻辑运算	英文缩写	表达式
与	AND	X · Y
或	OR	X + Y
非	NOT	​
与非	NAND	​
或非	NOR	​
异或	XOR	X Y
同或	XNOR	X Y

​

‍

其中，异或和同或其实意如其名，只是表达式有点抽象，它们的展开式十分容易理解：

X Y = X · + · Y

X Y = X · Y + ·

而逻辑命题的真假像极了二进制中的 1 和 0，布尔代数自然而然选择用 1 表示真、0 表示假。

经过简单的逻辑推演，我们就能得到这些逻辑运算在所有情况下的结果：

X	Y	与	或	非 X	与非	或非	异或	同或
0	0	0	0	1	1	1	0	1
0	1	0	1	1	1	0	1	0
1	0	0	1	0	1	0	1	0
1	1	1	1	0	0	0	0	1

‍

‍

‍

不难发现，逻辑运算和二进制运算有着极高的一致性，除了有点违反直觉的 1+1=1：

逻辑与：

• 0·0=0
• 0·1=0
• 1·1=1

逻辑或：

• 0+0=0
• 0+1=1
• 1+1=1

更巧合的是，逻辑运算和数学运算一样满足交换律、结合律和分配律等各种运算规则，比如：

• X·Y=Y·X
• X+Y=Y+X
• X·(Y·Z)=(X·Y)·Z
• X+(Y+Z)=(X+Y)+Z
• (X+Y)·Z=X·Z+Y·Z

‍