布尔代数

概述

布尔代数（Boolean Algebra）是定义在集合 $\{0,1\}$ 上的代数结构，通过三种基本运算（AND、OR、NOT）操作布尔值，是命题逻辑的代数化表述，也是数字电路设计的数学基础。

定义

形式化定义

布尔代数 $(B,\wedge ,\vee ,\neg ,0,1)$ 是一个六元组，其中：

• $B=\{0,1\}$ 是布尔值集合（0 = 假，1 = 真）
• $\wedge$（AND，与）：$a\wedge b=\min (a,b)$
• $\vee$（OR，或）：$a\vee b=\max (a,b)$
• $\neg$（NOT，非）：$\neg a=1-a$
• $0$ 是零元（关于 $\vee$ 的单位元），$1$ 是壹元（关于 $\wedge$ 的单位元）

满足以下公理：

1. 交换律：$a\wedge b=b\wedge a$，$a\vee b=b\vee a$
2. 结合律：$(a\wedge b)\wedge c=a\wedge (b\wedge c)$，$(a\vee b)\vee c=a\vee (b\vee c)$
3. 分配律：$a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$，$a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
4. 恒等律：$a\wedge 1=a$，$a\vee 0=a$
5. 互补律：$a\wedge \neg a=0$，$a\vee \neg a=1$

基本运算真值表

$a$	$b$	$a\wedge b$	$a\vee b$	$\neg a$
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

重要定律

德摩根定律（De Morgan’s Laws）

$\neg (a\wedge b)=\neg a\vee \neg b$ $\neg (a\vee b)=\neg a\wedge \neg b$

德摩根定律是布尔代数中最重要的对偶性定律，将 AND 转化为 OR（反之亦然），同时取反。

吸收律

$a\wedge (a\vee b)=a$ $a\vee (a\wedge b)=a$

其他重要性质

• 幂等律：$a\wedge a=a$，$a\vee a=a$
• 零壹律：$a\wedge 0=0$，$a\vee 1=1$
• 对合律：$\neg (\neg a)=a$
• 对偶原理：将等式中的 $\wedge$ 与 $\vee$ 互换、$0$ 与 $1$ 互换，得到的新等式仍然成立

与命题逻辑的关系

布尔代数与命题逻辑完全等价：

布尔代数	命题逻辑
变量 $a,b$	命题 $P,Q$
$a\wedge b$	$P\wedge Q$（合取）
$a\vee b$	$P\vee Q$（析取）
$\neg a$	$\neg P$（否定）
恒等式	逻辑等价式
重言式	永真式（值为 1）
矛盾式	永假式（值为 0）

应用场景

• 电路设计：逻辑电路直接实现布尔函数，AND/OR/NOT 门对应三种基本运算
• 可满足性问题（SAT）：判定布尔公式是否存在使其为真的赋值，是 NP 完全问题的第一个例子（Cook-Levin 定理）
• 逻辑优化：利用布尔代数定律化简逻辑表达式，减少电路门数
• 程序分析：条件语句、位运算等都基于布尔运算

参见

• 逻辑电路
• 公钥密码学