布尔代数：基本定律

1. 概述

在本文中，我们将学习布尔代数中的基本定律。

我们会从布尔代数在构建更复杂的逻辑系统中的作用开始，了解它是如何成为形式逻辑的基础。接着，我们会学习布尔代数中的基本和次要逻辑运算，并掌握如何解释真值表以及使用它们来证明定理。

最后，我们将重点介绍布尔代数的基本定律，并通过真值表来演示这些定律。我们还会将这些定律应用于简单的等价表达式练习中。

本文结束时，你将熟悉布尔代数的基础知识，并能够使用布尔运算和真值表来证明其基本定律。

2. 布尔代数与逻辑的关系

在我们之前关于命题逻辑和一阶逻辑的文章中，我们讨论了命题和谓词之间的逻辑运算。这些运算之所以可能，是因为在布尔项之间存在底层的代数运算规则。因此，本文将研究布尔代数的基础规则，这些规则构成了更复杂的逻辑系统的基石。

关于本文使用的符号，我们遵循计算机科学文章的惯例，使用二进制符号 1 和 0 分别表示 真 和 假。除非另有说明，这些数字在本文中不作为自然数使用，因此像加法“+”这样的算术运算也会被重新定义。

我们在之前的文章中提到，一阶逻辑是命题逻辑的泛化。这意味着一阶逻辑包含了命题逻辑。而布尔代数是命题逻辑和一阶逻辑的前提，因此我们可以认为后者两者都包含了前者：

更正式地说，布尔代数的定律在命题逻辑和一阶逻辑中都是有效的。

3. 术语与运算

3.1. 布尔术语

布尔术语是布尔代数公式中的变量。与我们在命题逻辑和一阶逻辑中使用的术语不同，布尔变量只能取二进制域中的两个值之一。它们没有其他限制条件，比如与现实世界相关的事实（如命题逻辑），或与关系相关（如一阶逻辑）。

我们可以用拉丁字母的斜体字母表示布尔变量，例如 p, q, x, 和 y。布尔代数及其定律的构建不依赖于变量的具体值，因此我们使用真值表来证明定理。

一个真值表显示了一组布尔变量的所有可能值组合。如果集合 S = {s₁, s₂, ..., sₙ} 包含 n 个布尔变量，那么该集合的真值表将有 2ⁿ 行，对应于这些变量的所有可能组合。

例如，集合 S = {p, q} 的真值表如下：

p	q
0	0
0	1
1	0
1	1

你可以逐行阅读这张表。第一行表示 “p 和 q 都为假”，第二行则表示 “p 为假，q 为真”，以此类推。

如果两个表达式在真值表中所有行的值都相同，则它们是等价的。

3.2. 基本布尔运算

布尔代数中有三种基本运算，对应三种逻辑运算符：

• 一元运算符 ¬p，表示 非 p
• 二元运算符 p ∧ q，表示 p 与 q
• 二元运算符 p ∨ q，表示 p 或 q

以下是这些运算的真值表：

p	q	¬p	p ∧ q	p ∨ q
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

这些运算被称为“基本”是因为所有其他运算都可以通过 非、与 和 或 的组合来实现。

3.3. 次要运算

我们还可以定义一些次要布尔运算，它们可以归约为基本运算的组合。最常见的有：

• 条件运算符 p → q，表示 如果 p 则 q
• 等价运算符 p ≡ q，表示 p 等价于 q 或 p 当且仅当 q
• 异或运算符 p ⊕ q，表示 p 或 q，但不同时为真

这些运算可以表示为基本运算的组合：

• p → q = ¬p ∨ q
• p ≡ q = (p ∧ q) ∨ (¬p ∧ ¬q)
• p ⊕ q = (p ∨ q) ∧ (¬p ∨ ¬q)

以下是这些运算的真值表验证：

p → q = ¬p ∨ q

p	q	p → q	¬p	¬p ∨ q
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	1	0	1

p ≡ q = (p ∧ q) ∨ (¬p ∧ ¬q)

p	q	p ≡ q	p ∧ q	¬p	¬q	¬p ∧ ¬q	(p ∧ q) ∨ (¬p ∧ ¬q)
0	0	1	0	1	1	1	1
0	1	0	0	1	0	0	0
1	0	0	0	0	1	0	0
1	1	1	1	0	0	0	1

p ⊕ q = (p ∨ q) ∧ (¬p ∨ ¬q)

p	q	p ⊕ q	p ∨ q	¬p	¬q	¬p ∨ ¬q	(p ∨ q) ∧ (¬p ∨ ¬q)
0	0	0	0	1	1	1	0
0	1	1	1	1	0	1	1
1	0	1	1	0	1	1	1
1	1	0	1	0	0	0	0

通过比较真值表列，我们可以验证这些等价关系。

4. 布尔代数的基本定律

4.1. 恒等律、零化律、幂等律与双重否定律

布尔代数的定律可以表示为两个布尔表达式之间的恒等式，这些表达式包含变量、常量和布尔运算符。

恒等律

• p ∧ 1 = p
• p ∨ 0 = p

零化律

• p ∧ 0 = 0
• p ∨ 1 = 1

幂等律

• p ∧ p = p
• p ∨ p = p

双重否定律

• ¬(¬p) = p

4.2. 交换律与吸收律

交换律

• p ∧ q = q ∧ p
• p ∨ q = q ∨ p

吸收律

• p ∧ (p ∨ q) = p
• p ∨ (p ∧ q) = p

4.3. 结合律与分配律

结合律

• (p ∧ q) ∧ r = p ∧ (q ∧ r)
• (p ∨ q) ∨ r = p ∨ (q ∨ r)

分配律

• p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)
• p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)

4.4. 德摩根定律

德摩根定律是布尔代数中的推理规则，它们指出：

• ¬(p ∧ q) = ¬p ∨ ¬q
• ¬(p ∨ q) = ¬p ∧ ¬q

5. 布尔代数定律的应用

5.1. 何时使用这些定律

布尔代数定律可以简化复杂的公式，使其更易处理。这在诸如信息检索、查询优化、简化嵌套的 if 语句、规则引擎以及简化逻辑电路等领域非常重要。

5.2. 使用分配律进行练习

我们从这个表达式开始：

F: (¬p ∧ q) ∨ (p ∧ q)

根据分配律，我们可以重写为：

F: q ∧ (¬p ∨ p)

由于 ¬p ∨ p = 1，我们可以进一步简化为：

F: q ∨ 0

最终简化为：

F': q

5.3. 使用德摩根定律进行练习

我们从这个表达式开始：

F: ¬(p ∧ ¬(q ∨ r))

应用德摩根定律：

F: ¬(p ∧ (¬q ∧ ¬r))

继续应用德摩根定律：

F: ¬p ∨ ¬(¬q ∧ ¬r)

再次应用德摩根定律：

F': ¬p ∨ q ∨ r

这样我们得到了一个更简化的表达式。

6. 结论

在本文中，我们学习了布尔代数的基本定律，并展示了如何应用它们来简化布尔表达式。

我们首先讨论了布尔运算符的真值表，并观察了次要运算符如何用基本运算符表示。

接着，我们研究了布尔代数的基本定律及其对应的真值表，并学习了如何证明这些定律对所有变量值都有效。

最后，我们学习了如何使用布尔代数的基本定律来简化复杂的布尔表达式。特别是，我们看到了如何应用分配律和德摩根定律来解决练习题。

这些方法可以算法化，比如使用卡诺图和奎因-麦克拉斯基算法，它们基于布尔代数规则，自动简化布尔函数，从而从复杂表达式中提取简单公式。