機率論/集合代數

布林代數

在代數領域，有一種結構叫做域上的代數。為了滿足我們的需求，我們需要對這個概念進行強烈的修改，以獲得布林代數。

定義 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$（注意，透過這種方式，一個集合獲得了唯一的“加法逆元”）。