离散数学笔记（11）——布尔代数

离散数学笔记（11）——布尔代数

代数结构（代数系统）

格的性质

$\langle A,\lor,\land \rangle$ 是 $\langle A,\preccurlyeq \rangle$ 诱导的代数系统，$\forall a,b,c,d \in A$：

1. $a \preccurlyeq a \lor b,b \preccurlyeq a \lor b,a \land b \preccurlyeq a,a \land b \preccurlyeq b$。

2. 若 $a \preccurlyeq b,c \preccurlyeq d$，则 $a \lor c \preccurlyeq b \lor d,a \land c \preccurlyeq b \land d$。

   推论：在一个格中，任何 $a,b,c \in A$，如果 $b \preccurlyeq c$，则 $a \lor b \preccurlyeq a \lor c,a \land b \preccurlyeq a \land c$。

3. 交换律：$a \lor b = b \lor a,a \land b = b \land a$。

4. 幂等律：$a \lor a = a,a \land a = a$。

   

5. 结合律：$(a \lor b) \lor c = a \lor (b \lor c),(a \land b) \land c = a \land (b \land c)$。

   

6. 吸收律：$a \lor (a \land b) = a,a \land (a \lor b) = a$。

   

7. $\langle A,\lor,\land \rangle$ 是代数系统，若 $\lor$ 和 $\land$ 是满足吸收律的二元运算，则 $\lor$ 和 $\land$ 必满足幂等律。

   

8. 不一定满足分配律，但有分配不等式：

   $$a \lor (b \land c) \preccurlyeq (a \lor b) \land (a \lor c) \\(a \land b) \lor (a \land c) \preccurlyeq a \land (b \lor c)$$
   

9. $a \preccurlyeq b \Leftrightarrow a \lor b = b \Leftrightarrow a \land b = a$。
   

定理：设 $\langle A,\lor,\land \rangle$ 中的二元运算满足交换律、结合律、吸收律，则可以定义一个偏序 $\preccurlyeq$ 使得 $\langle A,\preccurlyeq \rangle$ 是格。

格的同态与同构

设 $\langle A_1,\preccurlyeq_1 \rangle$ 和 $\langle A_2,\preccurlyeq_2 \rangle$ 是两个格，由它们诱导的代数系统分别是 $\langle A_1,\lor_1,\land_1 \rangle$ 和 $\langle A_2,\lor_2,\land_2 \rangle$，如果存在映射 $f :A_1 \to A_2$，使得对任何 $a,b \in A_1$，有：

$$f(a \lor_1 b) = f(a) \lor_2 f(b) \\ f(a \land_1 b) = f(a) \land_2 f(b)$$
则称 $f$ 是 $\langle A_1,\lor_1,\land_1 \rangle$ 到 $\langle A_2,\lor_2,\land_2 \rangle$ 的同态映射，也称 $\langle f(A_1),\preccurlyeq_2 \rangle$ 是 $\langle A_1,\preccurlyeq_1 \rangle$ 的同态像。

如果 $f$ 是双射的，就称 $f$ 是 $\langle A_1,\lor_1,\land_1 \rangle$ 到 $\langle A_2,\lor_2,\land_2 \rangle$ 的格同构，也称 $\langle A_1,\preccurlyeq_1 \rangle$ 和 $\langle A_2,\preccurlyeq_2 \rangle$ 同构。

格同态的保序性

设 $f$ 是 $\langle A_1,\preccurlyeq_1 \rangle$ 到 $\langle A_2,\preccurlyeq_2 \rangle$ 的同态映射，则对任何 $a,b \in A_1$，若 $a \preccurlyeq_1 b$，则 $f(a) \preccurlyeq_2 f(b)$。

格同构的保序性

设 $f$ 是 $A_1$ 到 $A_2$ 的双射，则 $f$ 是 $\langle A_1,\preccurlyeq_1 \rangle$ 到 $\langle A_2,\preccurlyeq_2 \rangle$ 的同构映射，当且仅当对任何 $a,b \in A_1$，$a \preccurlyeq_1 b \Leftrightarrow f(a) \preccurlyeq_2 f(b)$。

特殊格

分配格

$\langle A,\lor,\land \rangle$ 是 $\langle A,\preccurlyeq \rangle$ 诱导的代数系统，如果对 $\forall a,b,c \in A$，有：

$$a \lor (b \land c) = (a \lor b) \land (a \lor c) \\a \land (b \lor c) = (a \land b) \lor (a \land c)$$
则称 $\langle A,\preccurlyeq \rangle$ 是分配格。

定理 1：设 $\langle A,\preccurlyeq \rangle$ 是格，对任意的 $a,b,c \in A$，下列的命题等价：

1. $a \land (b \lor c) = (a \land b) \lor (a \land c)$
2. $a \lor (b \land c) = (a \lor b) \land (a \lor c)$

定理 2：设 $\langle A,\preccurlyeq \rangle$ 是格，则其是分配格的充分必要条件是对 $\forall a,b,c \in A$，$a \land (b \lor c) \preccurlyeq (a \land b) \lor c$。

定理 3：设 $\langle A,\preccurlyeq \rangle$ 是分配格，对 $\forall a,b,c \in A$，如果有 $a \land b = a \land c,a \lor b = a \lor c$ 则必有 $b = c$。

另一个分配格判定条件：一个格是分配格的充分且必要条件是在该格中没有任何子格与上述两个五元素非分配格之一同构。

定理 4：所有链均为分配格。

有界格

格的全上界与全下界：设 $\langle A,\preccurlyeq \rangle$ 是格，如果 $(\exists a)(a \in A \land (\forall x)(x \in A \to x \preccurlyeq a))$ 或 $(\exists a)(a \in A \land (\forall x)(x \in A \to a \preccurlyeq x))$，则称 $a$ 为格的全上（下）界，记为 $1(0)$。

定理：一个格如果有全上（下）界，则是惟一的。

定义：如果一个格存在全上界 $1$ 与全下界 $0$，则称此格为有界格。

结论 1：设 $\langle A,\preccurlyeq \rangle$ 是有界格，则对任何 $a \in A$，因为 $a \preccurlyeq 1$，$\therefore a \land 1 = a,a \lor 1 = 1$；因为 $0 \preccurlyeq a$，$\therefore a \land 0 = 0,a \lor 0 = a$。

结论 2：所有有限个元素的格都是有界格，而无限个元素的格可能是无界格。

有补格

元素的补元：设 $\langle A,\preccurlyeq \rangle$ 是有界格，$a \in A$，如果存在 $b \in A$，使得 $a \lor b = 1,a \land b = 0$，则称 $a$ 与 $b$ 互为补元。

定义：一个有界格中，如果每个元素都有补元，则称之为有补格。

定理：在有界分配格中，如果元素有补元，则补元是唯一的。

布尔格

如果一个格既是分配格又是有补格，则称之为布尔格。

约定：记 $\overline{a}$ 为 $a$ 的补元，称此一元运算为补运算。

布尔代数

由布尔格 $\langle B,\preccurlyeq \rangle$ 诱导的代数系统 $\langle B,\lor,\land \rangle$ 称之为布尔代数。

如果 $B$ 是有限集合，则称它是有限布尔代数。

布尔代数的性质

布尔代数的同构

令 $\langle B_1,\lor_1,\land_1 \rangle$ 和 $\langle B_2,\lor_2,\land_2 \rangle$ 是两个布尔代数，如果存在映射 $f : B_1 \to B_2$，对任何 $a,b \in B_1$ 有：

$$f(a \lor_1 b) = f(a) \lor_2 f(b) \\ f(a \land_1 b) = f(a) \land_2 f(b) \\ f(\overline{a}) = \overline{f(a)}$$
则称 $f$ 是 $\langle B_1,\lor_1,\land_1 \rangle$ 到 $\langle B_2,\lor_2,\land_2 \rangle$ 的同态映射。

若 $f$ 是双射，则称 $f$ 是 $\langle B_1,\lor_1,\land_1 \rangle$ 到 $\langle B_2,\lor_2,\land_2 \rangle$ 的同构映射。

原子

定义 1：设 $\langle B,\lor,\land \rangle$ 是布尔代数，元素 $a \in B,a \not = 0$，对任何元素 $x \in B$，有 $x \land a = a$ 或 $x \land a = 0$，则称 $a$ 是原子。

定义 2：设 $\langle A,\preccurlyeq \rangle$ 是布尔格，在 $\langle A,\preccurlyeq \rangle$ 的 Haskell 图中称盖住全下界 $0$ 的元素为原子。

Stone 定理

设 $\langle B,\lor,\land \rangle$ 是布尔代数，$M$ 是 $B$ 中所有原子构成的集合，则 $\langle B,\lor,\land \rangle$ 与 $\langle P(M),\cup,\cap \rangle$ 同构。

推论 1：任何有限布尔代数的元素个数为 $2^n(n = 1,2,3,\cdots)$。

推论 2：两个有限布尔代数同构的充分且必要条件是元素个数相同。

 离散数学 笔记