格

• 格
  • 定义
    • 偏序格：
      • 设 $\langle S,\preceq \rangle$ 是偏序集，若 $\forall x,y \in S$ 满足 $\{x,y\}$ 都在 $S$ 存在最小上界和最大下界，则 $S$ 是偏序格。
      • 定义保交 $x \lor y$ 为取 $x,y$ 的最小上界，保联 $x \land y$ 为取 $x,y$ 的最大下界。
    • 代数格：
      • 设 $\langle S,\star,\circ \rangle$ 为代数系统，$\star,\circ$ 具有交换律、结合律、吸收律，则 $S$ 是代数格。
      • 可以定义 $S$ 中的偏序关系 $\preceq$：$x \preceq y \iff x \circ y = y$。
      • $\land,\lor$ 满足 $x\land y = x \star y,x\lor y = x \circ y$。
    • 偏序格和代数格的定义是等价的，统称为格。
  • 性质
    • 由定义，对于 $\land$ 有 $a \land b \preceq a,a\land b \preceq b$，对 $\lor$ 有 $a \lor b \succeq a, a\lor b \succeq b$。
    • $\preceq$ 和 $\succeq$、$\lor$ 和 $\land$ 对偶。已知格 $L$，$\forall a,b\in L$，$a\land b \preceq a \iff a \lor b \succeq a$。
    • $\lor,\land$ 具有交换律、结合律、吸收律、幂等律。幂等律可以由吸收律推出。
    • $a \preceq b \iff a \land b = a \iff a \lor b = b$。
    • 若 $a \preceq b,c \preceq d$，则 $a \land c \preceq b \land d$，$a \lor c \preceq b \lor d$，称为保序性。
    • $a \lor (b \land c) \preceq (a \lor b) \land (a \lor c)$，$(a \land b) \lor (a \land c) \preceq a \land (b \lor c)$，即 $\land,\lor$ 不一定有分配律。
    • 已知 $\langle L,\land,\lor \rangle$ 是格，$S \subseteq L$，若 $S$ 关于 $\land,\lor$ 构成格，则 $S$ 是 $L$ 的子格。
• 分配格
  • 定义
    • 已知 $\langle L,\land,\lor \rangle$ 是格，若 $\land,\lor$ 满足分配律，则 $L$ 是分配格。
  • 判定
    • 钻石格和五角格不是分配格。
    • 格不是分配格 $\iff$ 包含与钻石格或五角格同构的子格。
    • 小于 $5$ 元的格、一条链都是分配格。
• 有界格
  • 定义
    • 已知 $L$ 是格
      • 若存在 $a\in L$ 满足 $\forall x \in L,a \preceq x$，则 $a$ 是全下界，记作 $0$。
      • 若存在 $a\in L$ 满足 $\forall x \in L,a \succeq x$，则 $a$ 是全上界，记作 $1$。
  • 性质
    • 若存在全上界或全下界，则其是唯一的。
    • $n$ 元有限格一定是有界格，$a_1 \land a_2 \land \cdots \land a_n = 0$，$a_1 \lor a_2 \lor \cdots \lor a_n = 1$。
    • 无限格可能是有界格。
• 有补格
  • 定义
    • 已知 $L$ 是有界格，$a\in L$，若存在 $b \in L$，满足 $a \land b = 0$ 且 $a \lor b = 1$，则 $a$ 有补，$b$ 是 $a$ 的补元。
    • 若 $\forall a \in L$，$a$ 都有补，则 $L$ 为有补格。
  • 性质
    • $b$ 是 $a$ 的补元 $\iff$ $a$ 是 $b$ 的补元，称为 $a,b$ 互补。
    • $0,1$ 总是互补，其他元素不一定有补，补元也不一定唯一。
    • 对于有界分配格，若存在补元，则补元唯一。
• 布尔代数
  • 定义
    • 定义 1：
      • 若 $L$ 是有补分配格，则 $L$ 是布尔代数。
      • 因为 $\forall a \in L$ 有唯一补元，则可以定义该补元为 $a'$，$'$ 为求补运算。
    • 定义 2：
      • 若 $\langle L,\star,\circ \rangle$ 满足交换律、分配律、同一律、补元律，则 $L$ 为布尔代数。
      • 同一律：$a \star 1=a$，$a\circ 0=a$
      • 补元律：$a\star a'=0$，$a\circ a'=1$
  • 性质
    • 已知 $B$ 是布尔代数：
      • 双重否定律：$\forall a \in B$，$(a')'=a$
      • 德摩根律：$\forall a,b\in B$，$(a \land b)' = a' \lor b'$，$(a \lor b)' = a' \land b'$
    • 定义 $L$ 中的原子 $a$ 满足 $\forall b\in L,0\prec b\preceq a$。对任何有限布尔代数 $B$，$A$ 是其原子的集合，则 $B \cong P(A)$。
      • 任何有限布尔代数 $B$ 满足 $|B|=2^n,n\in \mathrm{\boldsymbol N}$。
      • 任何等势的有限布尔代数都是同构的。