离散数学

格

定义

  1. 二元确界
    1. 二元上确界 $x\lor y$ := 比 $x,y$ 都大の最小
    2. 二元下确界 $x\land y$ := 比 $x,y$ 都小の最大
  2. 格 := 任意二元素存在二元上下确界
  3. 分配格 := 满足 $\land,\lor$ 互相分配
  4. 补元 := $b$ 是 $a$ 补元 $\Leftrightarrow$ $a\lor b=\boldsymbol{1}$ 且 $a\land b=\boldsymbol{0}$
  5. 有补格 := 每个元素都有补元
  6. 布尔代数 := 分配格 $\land$ 有补格 $\land$ 有界(有最元)
Warning

  1. 格の任意而元素存在上下确界，包括自己与自己！
  2. 这要求格的运算是偏序，要求自反
  3. 所有 $(\mathbb{Z},<)$ 不构成格，而 $(\mathbb{Z},\leq)$ 构成格
格基集 格基调 下确界 上确界
$\mathbb{R}$, $\mathbb{Z}$ $\leq$ $\mathrm{min}(a,b)$ $\mathrm{max}(a,b)$
$P(A)$ $\subset$ $\cap$ $\cup$
$\mathbb{N}{+}$, $\mathrm{Factor}{n}$ 整除 $\mathrm{gcd}(a,b)$ $\mathrm{lcm}(a,b)$

性质

  1. 【代数构造格】若 $(S,,\circ)$ 中 $,\circ$ 满足交换律+结合律+吸收律 $\implies$ $S$ 可以是格
    1. 吸收律 $\implies$ 幂等律 $aa=a(a\circ(a*a))=a$
  2. 【夹】$a\land b \preceq a,b \preceq a\lor b$
  3. 【确】
    1. $c\preceq a \land c \preceq b \implies c\preceq a \land b$
    2. $a \preceq c \land b \preceq c \implies a \lor b \preceq c$
  4. 【递】$a\preceq c \land b \preceq d \implies ((a\lor b)\preceq(c\lor d)) \land ((a\land b)\preceq(c\land d))$
  5. $a \preceq b \Leftrightarrow a \land b=a \Leftrightarrow a \lor b = b$
  6. 【确界运算律】都有，只列出 $\lor$
    1. 交换律
    2. 结合律 $(a\lor b)\lor c=a\lor(b\lor c)$
    3. 幂等律 $a\lor a=a$
    4. 吸收律 $a\lor(a\land b)=a$
  7. 【分配格性质】
    1. 【可消】$a\land b=a\land c$ 且 $a\lor b=a\lor c$ $\implies$ $b=c$
  8. 【分配格判定】
    1. 【无钻石格】钻石格 := {(1,2), (1, 3), (1, 5), (2, 30), (3, 30), (5, 30)}
    2. 【无五边格】五边格 := {(1,2), (2, 4), (1, 3), (2, 12), (3,12)}