逻辑代数

此条目介绍的是数学的子领域。关于相关的代数结构，请见“布尔代数”和“布尔环”。

在数学和数理逻辑中，逻辑代数（有时也称开关代数、布尔代数）是代数的一个分支，其变量的值仅为真和假两种真值（通常记作 1 和 0）。初等代数中变量的值是数字，而且主要的运算是加法、乘法和乘方（以及它们的逆运算），而逻辑代数的主要运算符有合取与，记为∧；析取或，记为∨；否定非，记为¬。因此，它是描述逻辑运算的一种形式主义，就像初等代数描述数字运算一样。

逻辑代数是乔治·布尔（George Boole）在他的第一部著作《逻辑的数学分析》（1847年）中引入，并在他的《思想规律的研究》（1854年）中全面阐述了逻辑代数。^[1] 根据Huntington的说法，“布尔代数”术语最初是由Sheffer于1913年提出。^[2]

逻辑代数一直是数字电路设计的基础，所有现代编程语言都提供支持。它还用于集合论和统计学。 ^[3]

逻辑代数中的几个概念

参与逻辑运算的变量叫逻辑变量，用字母A，B……表示。每个变量的取值非0 即1。 0、1不表示数的大小，而是代表两种不同的逻辑状态。

正、负逻辑规定：

• 正逻辑体制规定：高电平为逻辑1，低电平为逻辑0。
• 负逻辑体制规定：低电平为逻辑1，高电平为逻辑0。

逻辑函数：如果有若干个逻辑变量（如A、B、C、D）按与、或、非三种基本运算组合在一起，得到一个表达式L。对逻辑变量的任意一组取值（如0000、0001、0010）L有唯一的值与之对应，则称L为逻辑函数。逻辑变量A、B、C、D的逻辑函数记为：L=f(A、B、C、D)

逻辑运算

基本运算

逻辑代数的基本运算如下。

• 与（合取），记作 x∧y（有时记作 x AND y 或 Kxy），在 x = y = 1 情况下，满足 x∧y = 1；其他情况下 x∧y = 0。
• 或（析取）, 记作 x∨y（有时记作 x OR y 或 Axy），在 x = y = 0 情况下，满足 x∨y = 0；其他情况下 x∨y = 1。
• 非 （否定）, 记作 ¬x（有时记作 NOT x, Nx 或 !x），在 x = 1 情况下，满足 ¬x = 0；而在 ¬x = 1 情况下，x = 0。

如果把真值0和1解释为整数，这些运算可以表示为普通算数运算：

${\displaystyle {\begin{aligned}x\wedge y&=x\times y\\x\vee y&=x+y-(x\times y)\\\neg x&=1-x\end{aligned}}}$

此外可以用制作真值表来表示 x∧y, x∨y 和 ¬x 的值：

${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\vee y}$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

${\displaystyle x}$ ${\displaystyle \neg x}$ 0 1 1 0

有人可能会认为，只有否定和另外两种运算之一是基本的，因为用下列性质可以用逻辑否和逻辑或来定义逻辑与，反之亦然：

${\displaystyle {\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}}$

衍生运算

上述三个逻辑运算被称为基本的，这意味着其他逻辑运算可以以它们为基础，由他们的复合来建立，即将这些运算组合或结合。下面是由基本运算构成的运算的例子：

${\displaystyle x\rightarrow y=\neg {x}\vee y}$

${\displaystyle x\oplus y=(x\vee y)\wedge \neg {(x\wedge y)}}$

${\displaystyle x\equiv y=\neg {(x\oplus y)}}$

这些定义产生以下真值表，其中给出了对所有四个可能的输入，这些运算的值。

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle x\rightarrow y}$	${\displaystyle x\oplus y}$	${\displaystyle x\equiv y}$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

第一种运算，x → y 或 Cxy，叫做实质蕴涵。如果 x 为真，则 x → y 的值就取自 y 的值。但如果 x 为假，则 y 可以忽略；然而此运算必须返回某种真值，而且只有两种选择，所以返回蕴含较小的值，即真。（相干逻辑通过看作非真非假的假前提的蕴含来处理这件事。）

第二种运算，x ⊕ y 或 Jxy，叫做异或（通常缩写为XOR）与逻辑或的区别在于逻辑或包含其类型。它排除了 x 和 y 同时为真的情形。用算术来定义就是加和之后 mod 2，就如 1 + 1 = 0.

第三种运算，异或的互补运算，是同或或逻辑等价：x ≡ y 或 Exy，当 x 与 y 值相同时为真。因此作为其互补运算，x ⊕ y 可以理解为 x ≠ y，当 x 和 y 不同时为真。它对应的 mod 2 算术为 x + y + 1。

给定两个操作数，每个具有两个可能的值，共有 2² = 4 种可能的输入组合。由于每种输出有两种可能值，一共有 2⁴ = 16种可能的二元逻辑运算（英语：Boolean algebras canonically defined#Truth tables）。

运算律

两个主要的二元运算的符号定义为 ${\displaystyle \land }$ (逻辑与)和 ${\displaystyle \lor }$ (逻辑或)，把单一的一元运算的符号定义为 ${\displaystyle \lnot }$ (逻辑非)。我们还使用值 0 (逻辑假)和 1 (逻辑真)。逻辑代数有下列性质:

${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c}$	${\displaystyle a\land (b\land c)=(a\land b)\land c}$	结合律
${\displaystyle a\lor b=b\lor a}$	${\displaystyle a\land b=b\land a}$	交换律
${\displaystyle a\lor (a\land b)=a}$	${\displaystyle a\land (a\lor b)=a}$	吸收律
${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$	${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$	分配律
${\displaystyle a\lor \lnot a=1}$	${\displaystyle a\land \lnot a=0}$	互补律
${\displaystyle a\lor a=a}$	${\displaystyle a\land a=a}$	幂等律
${\displaystyle a\lor 0=a}$	${\displaystyle a\land 1=a}$	有界律
${\displaystyle a\lor 1=1}$	${\displaystyle a\land 0=0}$
${\displaystyle \lnot 0=1}$	${\displaystyle \lnot 1=0}$	0 和 1 是互补的
${\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b}$	${\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b}$	对偶律
${\displaystyle \lnot \lnot a=a}$		对合律

布尔运算的各种表示

逻辑代数的基本规则

代入规则

任何一个含有变量 X 的等式，如果将所有出现 X 的位置，都代之以一个逻辑函数 F，此等式仍然成立。

对偶规则

设 F 是一个逻辑函数式，如果将 F 中的所有的 * 变成 +，+ 变成 *，0 变成 1，1 变成 0，而变量保持不变。那么就的得到了一个逻辑函数式 F'，这个 F' 就称为 F 的对偶式。如果两个逻辑函数 F 和 G 相等，则它们各自的对偶式 F' 和 G' 也相等。

反演规则

当已知一个逻辑函数 F，要求 ¬F 时，只要把 F 中的所有 * 变成 +，+ 变成 *，0 变成 1，1 变成 0，原变量变成反变量，反变量变成原变量，即得 ¬F。 使用反演规则时要注意保持原函数中逻辑运算的优先顺序。

逻辑函数的标准形式

逻辑变量的逻辑与运算叫做与项，与项的逻辑或运算构成了逻辑函数的与或式，也叫做积之和式(SP form)。

逻辑变量的逻辑或运算叫做或项，或项的逻辑与运算构成了逻辑函数的或与式，也叫做和之积式(PS form)。

最小项

对于 n 个变量的逻辑函数而言，它的与项如果包含全部 n 个变量，即每个变量以原变量或反变量的形式出现一次且只出现一次，那么这个与项就称为该逻辑函数的最小项。

最大项

对于 n 个变量的逻辑函数而言，它的或项如果包含 全部n 个变量，即每个变量以原变量或反变量的形式出现一次且只出现一次，那么这个或项就称为该逻辑函数的最大项。

逻辑函数的化简

运用逻辑代数的基本公式及规则可以对逻辑函数进行变换，从而得到表达式的最简形式。这里所谓的最简形式是指最简与或式或者是最简或与式，它们的判别标准有两条：(1)项数最少；(2)在项数最少的条件下，项内的文字最少。

卡诺图是遵循一定规律构成的。由于这些规律，使逻辑代数的许多特性在图形上得到形象而直观的体现，从而使它成为公式证明、函数化简的有力工具。

应用

计算机

20世纪早期，一些电子工程师领悟到逻辑代数很像某种电子电路的行为。香农在它1937年的论文中证明了这种行为与逻辑代数等价。

几乎所有现代通用计算机都用二值布尔逻辑做运算；也就是说它们的电路是二值布尔逻辑的物理表示。几种表示方式：导线上电压的高低，磁性存储设备中磁畴的方向，打孔卡或纸带上的洞，等等（但有些早期的计算机用了十进制电路或者机械，而不是二值逻辑电路）

当然，也可能在任意介质中编码进2个以上的符号。比如在导线上用0，1，2，3伏特去编码一种有4个符号的字符集，或者利用打孔卡的洞的不同大小。但实践上，在一个很小的、高速的、低功耗的电路中噪声是个关键因素。它使分辨多个可能出现的符号变得困难。所以电路设计者们选择了高、低2种电压而不是4种。

由于上面的原因计算机使用二值逻辑电路。最常见的计算机架构使用32或64个叫做比特的布尔值序列，比如011010001101001010101001010111100000010101001011。当使用机器语言、汇编语言和某些高级语言时，程序员可以操作寄存器的数字结构。在寄存器中0电压表示逻辑0，参考电压（通常是+5伏或+3.3伏^[4]）表示逻辑1。这些语言同时支持数值操作和逻辑操作。这里的“数值操作”指计算机把比特序列当作二进制数字进行加减乘除等运算。“逻辑操作”指2个比特序列之间的与或非运算，序列中每一位都与另一序列中对应位进行运算。这两种操作之间的关键不同是前者有进位而后者没有。

参见

• 数字逻辑(数位逻辑)
• 逻辑函数(交换函数)
• 规范形式 (布尔代数)
• 逻辑门
• 卡诺图