1. 布尔代数

布尔代数作为一个数学分支，研究的对象是两个真值变量：真、假（True/False），通常表示为 1 与 0. 真值的基本运算有三种：AND, OR, NOT, 他们被称为逻辑运算，其运算规则如下：

x	y	x AND y	x OR y	NOT x
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

我们可以通过这三种运算的组合形成更复杂的运算，例如：蕴含式（->），XOR:

x	y	x -> y	x XOR y
0	0	1	0
0	1	1	1
1	0	0	1
1	1	1	0

易得 x -> y 等价于 (NOT x) OR y, 而 x XOR y 等价于 (x OR y) AND ((NOT x) OR (NOT y)), 事实上任何逻辑运算都可以通过三种基本运算的组合实现。上文展示逻辑运算结果的表被称为逻辑表达式的真值表。

关于 x XOR y 的等价式，可以理解为 (x OR y) 表示 x 与 y 中至少一个为 1, 而 (NOT x) OR (NOT y) 限定两个不能同时为 1, 最终的效果就是 x 与 y 的值不同时，x XOR y 的值才为 1。

上述运算还满足一些基本的运算律，例如：

• 结合律：x AND (y AND z) = (x AND y) AND z, x OR (y OR z) = (x OR y) OR z

• 交换律：x AND y = y AND x, x OR y = y OR x

• 对偶律：NOT (x OR y) = (NOT x) AND (NOT y), NOT (x AND y) = (NOT x) OR (NOT y)

这里我们不对布尔代数做过多讨论，对于有编程背景的同学来说，上述内容应该非常熟悉。

香农在20世纪30年代对继电器开关电路的研究时发现，开关电路的行为与布尔代数的运算有着相似之处，例如开关的状态只有两种，开、关可以分别对应布尔代数中的 True 与 False，两个串联的开关电路对应于 AND 运算，而两个并联的开关电路对应于 OR 运算。当时，电路设计更多地依赖电气工程师的个人经验来完成，而缺乏系统性的研究、分析的手段，也就是说其更像是一门艺术，而非一门科学。香农敏锐地观察到使用布尔代数来分析开关电路的可能性，并在他的硕士论文《继电器与开关电路的符号分析》中对其进行了系统的阐述。该论文被认为是20世纪最重要的硕士论文之一，其为电路分析、设计找到了数学上的理论基础，从此以后，工程师们在设计电路时不必再考虑继电器、开关、晶体管等具体物件，而只需要考虑逻辑符号以及符号之间的逻辑运算，这为后来集成电路以及大规模集成电路的发展起到了至关重要的作用。

布尔代数由英国数学家乔治布尔于19世纪创建，目的是用代数的方式系统性地研究逻辑推演，布尔不曾想到，他所创建的学科如此深刻地刻画了一个世纪之后的信息世界。