概率论/集合代数

布尔代数

在代数领域，有一种结构叫做域上的代数。为了满足我们的需求，我们需要对这个概念进行强烈的修改，以获得布尔代数。

定义 1.1 (布尔代数):

一个布尔代数是一个集合$A$，它有两个二元运算 $\vee$ 和 $\wedge$，一个一元运算 $\neg$ 和 $0,1\in A$，使得以下公理对于所有 $a,b,c\in A$ 成立

1. $\vee$ 和 $\wedge$ 的结合律: $a\Box (b\Box c)=(a\Box b)\Box c$，$\Box \in \{\vee ,\wedge \}$
2. $\vee$ 和 $\wedge$ 的交换律: $a\Box b=b\Box a$，$\Box \in \{\vee ,\wedge \}$
3. 吸收律: $a\Box (a\triangledown b)=a$，$\{\Box ,\triangledown \}=\{\vee ,\wedge \}$
4. 分配律: $a\Box (b\triangledown c)=(a\Box b)\triangledown (a\Box c)$, $\{\Box ,\triangledown \}=\{\vee ,\wedge \}$
5. 中性元素: $a\vee 0=a$, $a\wedge 1=a$
6. 补律: $a\vee \neg a=1$, $a\wedge \neg a=0$

基本示例 1.2 (逻辑):

如果我们取 $A=\{\bot ,\top \}$ 并且 $\vee ,\wedge ,\neg$ 是来自逻辑的通常运算，我们就得到了一个布尔代数。

基本示例和定理 1.3:

设 $S$ 是一个任意集合，并且设 ${\mathcal {A}}\subset 2^{S}$ 使得

1. $S,\emptyset \in {\mathcal {A}}$
2. $A,B\in S\Rightarrow A\cup B\in S,A\cap B\in S$
3. $A\in S\Rightarrow {\overline {A}}\in S$，其中 ${\overline {A}}$ 表示 $A$ 的补集。

我们设定

• $1:=S$,
• $0:=\emptyset$,
• $\vee :=\cup$,
• $\wedge :=\cap$，以及
• $\neg A:={\overline {A}}$ 对所有 $A\subseteq S$.

那么 $({\mathcal {A}},0,1,\vee ,\wedge ,\neg )$ 是一个布尔代数，称为 **$S$ 的子集代数**.

证明: 由 1. - 3. 可知运算封闭性。我们需要验证定义 1.1 中的 1. - 6.

1.

${\begin{aligned}A\cup (B\cup C)&=\{x\in S:x\in A\vee (x\in B\cup C)\}\\&=\{x\in S:x\in A\vee (x\in B\vee x\in C)\}\\&=\{x\in S:(x\in A\vee x\in B)\vee x\in C)\}\\&=\{x\in S:(x\in A\cup B)\vee x\in C\}\\&=(A\cup B)\cup C\end{aligned}}$

${\begin{aligned}A\cap (B\cap C)&=\{x\in S:x\in A\wedge (x\in B\cap C)\}\\&=\{x\in S:x\in A\wedge (x\in B\wedge x\in C)\}\\&=\{x\in S:(x\in A\wedge x\in B)\wedge x\in C)\}\\&=\{x\in S:(x\in A\cap B)\wedge x\in C\}\\&=(A\cap B)\cap C\end{aligned}}$

2.

$A\cup B=\{x\in S:x\in A\vee x\in B\}=\{x\in S:x\in B\vee x\in A\}=B\cup A$

$A\cap B=\{x\in S:x\in A\wedge x\in B\}=\{x\in S:x\in B\wedge x\in A\}=B\cap A$

3.

${\begin{aligned}A\cup (A\cap B)&=\{x\in S:x\in A\vee x\in (A\cap B)\}\\&=\{x\in S:x\in A\vee (x\in A\wedge x\in B)\}\\&=\{x\in S:(x\in A\vee x\in A)\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:x\in A\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:x\in A\}=A\end{aligned}}$

${\begin{aligned}A\cap (A\cup B)&=\{x\in S:x\in A\wedge x\in (A\cup B)\}\\&=\{x\in S:x\in A\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:(x\in A\vee x\in A)\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:x\in A\vee (x\in A\wedge x\in B)\}\\&=\{x\in S:x\in A\}=A\end{aligned}}$${\begin{aligned}A\cup (B\cap C)&=\{x\in S|x\in A\vee x\in (B\cap C)\}\\&=\{x\in S|x\in A\vee (x\in B\wedge x\in C)\}\\&=\{x\in S|(x\in A\vee x\in B)\wedge (x\in A\vee x\in C)\}\\&=\{x\in S|(x\in A\cap B)\wedge (x\in A\cap C)\}\\&=(A\cap B)\cup (A\cap C)\end{aligned}}$

${\begin{aligned}A\cap (B\cup C)&=\{x\in S|x\in A\wedge x\in (B\cup C)\}\\&=\{x\in S|x\in A\wedge (x\in B\vee x\in C)\}\\&=\{x\in S|(x\in A\wedge x\in B)\vee (x\in A\wedge x\in C)\}\\&=\{x\in S|(x\in A\cup B)\vee (x\in A\cup C)\}\\&=(A\cup B)\cap (A\cup C)\end{aligned}}$

5.

$A\cap S=\{x\in S|x\in A\wedge x\in S\}=\{x\in S|x\in A\wedge \top \}=\{x\in S|x\in A\}=A$

$A\cup \emptyset =\{x\in S|x\in A\vee x\in \emptyset \}=\{x\in S|x\in A\vee \bot \}=\{x\in S|x\in A\}=A$

6.

${\begin{aligned}A\cup {\overline {A}}&=\{x\in S|x\in A\vee (x\in {\overline {A}})\}\\&=\{x\in S|x\in A\vee (x\notin A)\}\\&=\{x\in S|\top \}\\&=S\end{aligned}}$

${\begin{aligned}A\cap {\overline {A}}&=\{x\in S|x\in A\wedge (x\in {\overline {A}})\}\\&=\{x\in S|x\in A\wedge (x\notin A)\}\\&=\{x\in S|\bot \}\\&=S\end{aligned}}$

因此，我们可以看到布尔代数的定律从逻辑的布尔代数“提升”到了集合的布尔代数。

练习

• 练习 1.1.1：设 $A$ 是一个布尔代数， $a\in A$。证明 $a\wedge a=a$ 以及 $a\vee a=a$.

符号

在本手册的剩余部分，我们将遵循以下符号约定（由Felix Hausdorff提出）。

1. 如果集合 $A_{1},\ldots ,A_{n}$ 是成对不交的，我们将使用 $\sum _{j=1}^{n}A_{j}$ 来表示 $\bigcup _{j=1}^{n}A_{j}$；通过这种符号，我们已经表明 $A_{j}$ 是成对不交的。也就是说，如果我们遇到类似 $\sum _{j=1}^{n}A_{j}$ 的表达式，而 $A_{j}$ 是集合，那么我们假定 $A_{j}$ 是成对不交的。
2. 如果 $A,B$ 是集合，且 $A\subseteq B$，我们将用 $B-A$ 来代替 $B\setminus A$。这意味着：在本书中，无论何时遇到 $B-A$ 的符号，它都表示 $B\setminus A$，且 $A\subseteq B$（注意，通过这种方式，一个集合获得了唯一的“加法逆元”）。