布尔代数

布尔代数（Boolean Algebra）是以英国数学家乔治·布尔（George Boole, 1815-1864）命名的代数系统。它是数字电路设计的数学基础，也是计算机科学中逻辑运算的理论依据。从简单的逻辑门到复杂的处理器设计，布尔代数无处不在。

布尔代数基础

布尔代数的定义

布尔代数是一个代数结构 $(B, \land, \lor, \neg, 0, 1)$ ，其中：

$B$ 是一个集合，至少包含两个元素 $0$ 和 $1$
$\land$ 是合取运算（AND，与）
$\lor$ 是析取运算（OR，或）
$\neg$ 是否定运算（NOT，非）
$0$ 是最小元（假）
$1$ 是最大元（真）

最简单的布尔代数是二值布尔代数，其中 $B = \{0, 1\}$ 。

布尔运算的真值表

与运算（AND）： $x \land y$ ，当且仅当 $x$ 和 $y$ 都为 1 时结果为 1。

$x$	$y$	$x \land y$
0	0	0
0	1	0
1	0	0
1	1	1

或运算（OR）： $x \lor y$ ，当 $x$ 或 $y$ 至少一个为 1 时结果为 1。

$x$	$y$	$x \lor y$
0	0	0
0	1	1
1	0	1
1	1	1

非运算（NOT）： $\neg x$ ，对输入取反。

$x$	$\neg x$
0	1
1	0

布尔代数的公理

布尔代数满足以下公理（Huntington 公理）：

交换律：

$x \land y = y \land x$

$x \lor y = y \lor x$

分配律：

$x \land (y \lor z) = (x \land y) \lor (x \land z)$

$x \lor (y \land z) = (x \lor y) \land (x \lor z)$

同一律：

$x \land 1 = x$

$x \lor 0 = x$

互补律：

$x \land \neg x = 0$

$x \lor \neg x = 1$

这些公理是完全的，可以推导出布尔代数的所有其他性质。

布尔代数的定理

从公理可以推导出许多重要定理：

幂等律：

$x \land x = x$

$x \lor x = x$

支配律：

$x \land 0 = 0$

$x \lor 1 = 1$

吸收律：

$x \land (x \lor y) = x$

$x \lor (x \land y) = x$

双重否定律：

$\neg \neg x = x$

德摩根律：

$\neg(x \land y) = \neg x \lor \neg y$

$\neg(x \lor y) = \neg x \land \neg y$

德摩根律是布尔代数中最重要的定理之一，它描述了如何将否定运算分配到合取和析取中。

证明德摩根律：

设 $x \land y = a$ ，则：

$a \lor (\neg x \lor \neg y) = (x \land y) \lor \neg x \lor \neg y = (x \lor \neg x \lor \neg y) \land (y \lor \neg x \lor \neg y) = 1 \land 1 = 1$
$a \land (\neg x \lor \neg y) = (x \land y) \land (\neg x \lor \neg y) = (x \land y \land \neg x) \lor (x \land y \land \neg y) = 0 \lor 0 = 0$

由互补律的唯一性， $\neg(x \land y) = \neg x \lor \neg y$ 。

布尔函数

布尔函数的定义

布尔函数是从 $\{0, 1\}^n$ 到 $\{0, 1\}$ 的映射。 $n$ 个变量的布尔函数有 $2^{2^n}$ 种不同的可能。

例子：2 个变量的布尔函数有 $2^{2^2} = 16$ 种，包括：

与函数： $f(x, y) = x \land y$
或函数： $f(x, y) = x \lor y$
异或函数： $f(x, y) = x \oplus y$
等价函数： $f(x, y) = x \leftrightarrow y$

布尔表达式的等价性

两个布尔表达式等价，当且仅当它们对所有输入组合产生相同的输出。可以通过真值表验证等价性。

例子：验证 $x \lor (x \land y) = x$ （吸收律）

$x$	$y$	$x \land y$	$x \lor (x \land y)$
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

可以看到 $x \lor (x \land y)$ 的值与 $x$ 完全相同，验证了吸收律。

最小项与最大项

最小项（Minterm）：包含所有变量的合取式，每个变量以原变量或否定形式出现恰好一次。对于 $n$ 个变量，有 $2^n$ 个最小项。

对于变量 $x, y, z$ ，最小项为：

$m_0 = \neg x \land \neg y \land \neg z$ （对应输入 000）
$m_1 = \neg x \land \neg y \land z$ （对应输入 001）
$m_2 = \neg x \land y \land \neg z$ （对应输入 010）
...

最大项（Maxterm）：包含所有变量的析取式，每个变量以原变量或否定形式出现恰好一次。

对于变量 $x, y, z$ ，最大项为：

$M_0 = x \lor y \lor z$ （对应输入 000，函数值为 0）
$M_1 = x \lor y \lor \neg z$ （对应输入 001，函数值为 0）
...

标准形式

析取范式（DNF）：布尔函数表示为最小项的析取。也称为"积之和"（Sum of Products, SOP）形式。

$f(x, y, z) = \bigvee_{i: f(m_i) = 1} m_i$

例子：真值表

$x$	$y$	$z$	$f$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

DNF： $f = (\neg x \land \neg y \land z) \lor (\neg x \land y \land z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land \neg z) \lor (x \land y \land z)$

合取范式（CNF）：布尔函数表示为最大项的合取。也称为"和之积"（Product of Sums, POS）形式。

$f(x, y, z) = \bigwedge_{i: f(M_i) = 0} M_i$

逻辑门

基本逻辑门

逻辑门是布尔运算的物理实现，是数字电路的基本构建块。

与门（AND Gate）：输出为所有输入的合取。

  A ──┐
      ├── AND ── Y = A ∧ B
  B ──┘

或门（OR Gate）：输出为所有输入的析取。

  A ──┐
      ├── OR ── Y = A ∨ B
  B ──┘

非门（NOT Gate）：输出为输入的否定。

  A ──○── Y = ¬A

复合逻辑门

与非门（NAND Gate）：与门的否定， $\neg(A \land B)$ 。

  A ──┐
      ├── AND ──○── Y = ¬(A ∧ B)
  B ──┘

或非门（NOR Gate）：或门的否定， $\neg(A \lor B)$ 。

  A ──┐
      ├── OR ──○── Y = ¬(A ∨ B)
  B ──┘

异或门（XOR Gate）： $A \oplus B = (A \land \neg B) \lor (\neg A \land B)$ 。

  A ──┐
      ├── XOR ── Y = A ⊕ B
  B ──┘

$A$	$B$	$A \oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

逻辑门的完备性

定理：{NAND} 和 {NOR} 都是功能完备的门集合，即仅用 NAND 门或仅用 NOR 门可以实现任何布尔函数。

证明（NAND 完备性）：

用 NAND 实现 NOT： $\neg A = A \text{ NAND } A$
用 NAND 实现 AND： $A \land B = \neg(A \text{ NAND } B) = (A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B)$
用 NAND 实现 OR： $A \lor B = \neg(\neg A \land \neg B) = (\neg A) \text{ NAND } (\neg B)$

由于 {NOT, AND, OR} 是功能完备的，NAND 也是功能完备的。

def nand_gate(a, b):
    """NAND 门"""
    return not (a and b)

def not_gate(a):
    """用 NAND 实现 NOT"""
    return nand_gate(a, a)

def and_gate(a, b):
    """用 NAND 实现 AND"""
    return not_gate(nand_gate(a, b))

def or_gate(a, b):
    """用 NAND 实现 OR"""
    return nand_gate(not_gate(a), not_gate(b))

# 测试
print(f"NOT(1) = {not_gate(1)}")           # 0
print(f"AND(1, 1) = {and_gate(1, 1)}")     # 1
print(f"OR(0, 1) = {or_gate(0, 1)}")       # 1

布尔表达式化简

代数化简法

使用布尔代数的定理对表达式进行化简。

例子：化简 $x \land y \lor x \land \neg y$

$x \land y \lor x \land \neg y = x \land (y \lor \neg y) = x \land 1 = x$

例子：化简 $x \lor (x \land y)$

$x \lor (x \land y) = x$ （吸收律）

例子：化简 $\neg(x \land \neg y) \land (\neg x \lor y)$

$\neg(x \land \neg y) \land (\neg x \lor y) = (\neg x \lor y) \land (\neg x \lor y) = \neg x \lor y$

卡诺图

卡诺图是一种图形化简布尔表达式的方法，特别适用于 2 到 4 个变量的情况。

2 变量卡诺图：

        y=0   y=1
x=0  |  m0  |  m1  |
x=1  |  m2  |  m3  |

3 变量卡诺图（注意格雷码排列）：

         yz=00  yz=01  yz=11  yz=10
x=0  |   m0  |  m1  |  m3  |  m2  |
x=1  |   m4  |  m5  |  m7  |  m6  |

化简规则：

将函数值为 1 的方格填入卡诺图
将相邻的 1 方格圈成 2 的幂次大小的组（1、2、4、8...）
每个圈对应一个简化项
圈要尽可能大，数量要尽可能少

例子：化简 $f(x, y) = \neg x \land y \lor x \land \neg y \lor x \land y$

真值表：

$x$	$y$	$f$
0	0	0
0	1	1
1	0	1
1	1	1

卡诺图：

        y=0   y=1
x=0  |   0  |   1  |
x=1  |   1  |   1  |

将右下角的两个 1 圈在一起： $x$ 将右边一列的两个 1 圈在一起： $y$

结果： $f = x \lor y$

Python 实现：

def karnaugh_map_2var(truth_table):
    """
    2变量卡诺图化简
    truth_table: [f(0,0), f(0,1), f(1,0), f(1,1)]
    """
    # 填充卡诺图
    kmap = [[truth_table[0], truth_table[1]],
            [truth_table[2], truth_table[3]]]
    
    terms = []
    
    # 检查整行
    if kmap[1] == [1, 1]:  # x=1 行
        terms.append('x')
    if kmap[0] == [1, 1]:  # x=0 行
        terms.append('¬x')
    
    # 检查整列
    if kmap[0][1] == 1 and kmap[1][1] == 1:  # y=1 列
        terms.append('y')
    if kmap[0][0] == 1 and kmap[1][0] == 1:  # y=0 列
        terms.append('¬y')
    
    # 检查单个方格
    if truth_table[0] == 1 and '¬x' not in terms and '¬y' not in terms:
        terms.append('¬x∧¬y')
    if truth_table[1] == 1 and '¬x' not in terms and 'y' not in terms:
        terms.append('¬x∧y')
    if truth_table[2] == 1 and 'x' not in terms and '¬y' not in terms:
        terms.append('x∧¬y')
    if truth_table[3] == 1 and 'x' not in terms and 'y' not in terms:
        terms.append('x∧y')
    
    return ' ∨ '.join(terms) if terms else '0'

# 测试
print(karnaugh_map_2var([0, 1, 1, 1]))  # x ∨ y

Quine-McCluskey 算法

对于变量较多的情况，可以使用 Quine-McCluskey 算法，这是一种系统化的化简方法。

基本步骤：

将所有最小项转换为二进制表示
按含 1 的个数分组
比较相邻组的项，找出只有一个变量不同的项对，合并
重复直到无法合并
找出必要质蕴涵项

这种方法可以编程实现，适合自动化处理。

布尔代数的应用

数字电路设计

布尔代数是数字电路设计的理论基础。组合逻辑电路直接实现布尔函数，时序逻辑电路在布尔代数的基础上引入了时间概念。

半加器：实现 1 位二进制加法。

输入： $A$ , $B$
输出： $S$ （和）, $C$ （进位）

$S = A \oplus B$

$C = A \land B$

def half_adder(a, b):
    """半加器"""
    s = a ^ b  # 异或
    c = a and b  # 与
    return s, c

print(half_adder(0, 0))  # (0, 0)
print(half_adder(0, 1))  # (1, 0)
print(half_adder(1, 1))  # (0, 1)

全加器：考虑进位输入的加法器。

输入： $A$ , $B$ , $C_{in}$
输出： $S$ , $C_{out}$

$S = A \oplus B \oplus C_{in}$

$C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B))$

def full_adder(a, b, cin):
    """全加器"""
    s = a ^ b ^ cin
    cout = (a and b) or (cin and (a ^ b))
    return s, cout

# 多位加法器
def ripple_carry_adder(a_bits, b_bits):
    """行波进位加法器"""
    result = []
    carry = 0
    for a, b in zip(reversed(a_bits), reversed(b_bits)):
        s, carry = full_adder(a, b, carry)
        result.append(s)
    result.append(carry)
    return list(reversed(result))

# 测试：5 + 3 = 8
print(ripple_carry_adder([0, 1, 0, 1], [0, 0, 1, 1]))  # [0, 1, 0, 0, 0] = 8

数据库查询

SQL 查询中的 WHERE 子句使用布尔表达式进行条件过滤。

SELECT * FROM products
WHERE (price > 100 AND stock > 0) OR discount > 0.5

这个查询条件可以表示为布尔函数： $f = (price > 100 \land stock > 0) \lor (discount > 0.5)$

程序设计

程序中的条件判断本质上就是布尔表达式的求值。

# 条件判断
if (age >= 18 and has_license) or is_learner_permit:
    print("可以驾驶")

理解布尔代数有助于写出简洁、正确的条件表达式。

# 使用德摩根律简化条件
# 原始：not (a < 0 or b < 0)
# 简化：a >= 0 and b >= 0

def check_positive(a, b):
    # 使用简化后的形式更清晰
    return a >= 0 and b >= 0

布尔代数与命题逻辑

布尔代数与命题逻辑有着密切的关系。事实上，二值布尔代数就是命题逻辑的代数化形式：

命题逻辑	布尔代数
真（True）	1
假（False）	0
合取（ $\land$ ）	与运算
析取（ $\lor$ ）	或运算
否定（ $\neg$ ）	非运算
命题公式	布尔函数
逻辑等价	布尔等式

布尔代数为命题逻辑提供了一个计算模型，使得逻辑推理可以机械化进行。这也是电子计算机能够进行逻辑运算的理论基础。

小结

本章介绍了布尔代数的基础知识：

布尔代数基础：定义、公理、定理
布尔函数：最小项、最大项、标准形式
逻辑门：基本逻辑门、复合逻辑门、完备性
布尔表达式化简：代数化简法、卡诺图
应用：数字电路设计、数据库查询、程序设计
与命题逻辑的关系：代数化视角

布尔代数是数字时代的数学基础。从逻辑门到计算机处理器，从数据库查询到程序设计，布尔代数的应用无处不在。理解布尔代数，是理解计算机工作原理的关键。

练习

证明布尔代数的吸收律： $x \lor (x \land y) = x$ 。
使用德摩根律化简： $\neg(\neg x \lor y) \land \neg(x \land \neg y)$ 。
将布尔函数 $f(x, y, z) = \neg x \land y \lor x \land z$ 转换为析取范式。
设计一个 2 选 1 多路选择器的逻辑电路：
- 输入： $A$ , $B$ , $S$ （选择信号）
- 输出： $Y = A$ （当 $S = 0$ ）或 $Y = B$ （当 $S = 1$ ）
证明 NAND 门是功能完备的。
使用卡诺图化简： $f(x, y, z) = \Sigma m(1, 2, 5, 6)$ 。

布尔代数基础​

布尔代数的定义​

布尔运算的真值表​

布尔代数的公理​

布尔代数的定理​

布尔函数​

布尔函数的定义​

布尔表达式的等价性​

最小项与最大项​

标准形式​

逻辑门​

基本逻辑门​

复合逻辑门​

逻辑门的完备性​

布尔表达式化简​

代数化简法​

卡诺图​

Quine-McCluskey 算法​

布尔代数的应用​

数字电路设计​

数据库查询​

程序设计​

布尔代数与命题逻辑​

小结​

练习​