格和布尔代数

Unknown

• 格：设 ⟨S, ⪯⟩ 是偏序集。如果 ∀x, y ∈ S，{x, y} 都有 最小上界 和 最大下界，则称 S 关于偏序 ⪯ 作成一个格;

  • 把求 {x,y} 的最小上界和最大下界看成 x 与 y 的二元运算∨和∧。
  • 偏序关系: 自反的，反对称的，传递的;
  • 偏序关系的哈斯图。
  • 对偶命题：=,⪯,⪰,∨,∧ -> =,⪰,⪯,∧,∨ 同样成立。
  • 交换律：a ∨ b = b ∨ a, a ∧ b = b ∧ a
  • 结合律：(a∨b)∨c = a∨(b∨c),(a∧b)∧c = a∧(b∧c)
  • 幂等率：a ∨ a = a, a ∧ a = a
  • 吸收律：a∨(a∧b) = a,a∧(a∨b) = a
  • a⪯b⇔a∧b=a⇔a∨b=b
  • 若 a ⪯ b 且 c ⪯ d，则 a ∧ c ⪯ b ∧ d, a ∨ c ⪯ b ∨ d
  • a∨(b∧c) ⪯ (a∨b)∧(a∨c)

• 子格：设⟨L,∧,∨⟩是格，S 是 L 的非空子集。若 S 关于 L 中的运 算∧和∨仍构成格，则称 S 是 L 的子格。

• 分配格：a∧(b∨c) = (a∧b)∨(a∧c) , a∨(b∧c) = (a∨b)∧(a∨c)

  • 判定：设 L 是格。L 是分配格当且仅当 L 不含有与钻石格或五角格同构的子格。（画哈斯图）
  • 小于 5 元的格都是分配格;
  • 任何一条链都是分配格。

• 有界格：设 L 是格，若 L 存在全下界和全上界，则称 L 为有界格， 一般将有界格记为 ⟨L, ∧, ∨, 0, 1⟩。

  • 全上界：若存在 b ∈ L 使得∀x ∈ L 有 x ⪯ b，则称 b 为 L 的全上界;
  • 全下界：若存在 a ∈ L 使得∀x ∈ L 有 a ⪯ x，则称 a 为 L 的全下界;
  • 若格 L 存在全下界或全上界，一定是唯一的;
  • 一般将格的全下界记为 0，全上界记为 1。
  • a ∧ 0 = 0, a ∨ 0 = a, a ∧ 1 = a, a ∨ 1 = 1
  • a1 ∧a2 ∧···∧an 是 L 的全下界，a1 ∨a2 ∨···∨an 是 L 的全上界;
  • 0 是∧运算的零元，∨运算的单位元;
  • 1 是∨运算的零元，∧运算的单位元;
  • 补元：对 $a \in L$, 若存在 $b \in L$, a ∧ b = 0 和 a ∨ b = 1 成立，则称 b 是 a 的补元。
    • 有界分配格下存在补元即为唯一补元
    • 有补格：设 ⟨L, ∧, ∨, 0, 1⟩ 是有界格，若 L 中 所有 的元素都有补元存在，则称 L 为有补格。

• 布尔代数：如果一个格是有补分配格，则称它为布尔格或布尔代数。 布尔代数记为 ⟨B, ∧, ∨,′ , 0, 1⟩，其中 ′ 为求补运算。

  • ∀a ∈ B，(a′)′ = a;
  • ∀a,b ∈ B，(a∧b)′ = a′ ∨b′，(a∨b)′ = a′ ∧b′。
  • (1) 交换律:∀a,b ∈ B，有 a∗b = b∗a，a◦b = b◦a;
  • (2) 分配律:∀a,b,c ∈ B 有 a∗(b◦c) = (a∗b)◦(a∗c)，a◦(b∗c) = (a◦b)∗(a◦c);
  • (3) 同一律: 存在 0,1 ∈ B，使得∀a ∈ B 有 a∗1 = a，a ◦ 0 = a;
  • (4) 补元律:∀a ∈ B，存在 a′ ∈ B 使得 a∗a′ = 0，a◦a′ = 1，则 ⟨B, ∗, ◦⟩ 是一个布尔代数。
  • 原子 a：L 是格，0 ∈ L，若∀b ∈ L 有 0 ≺ b ⪯ a ⇒ b = a, 原子是覆盖最小元的那些元素
  • 有限布尔代数的表示定理: 设 B 是有限布尔代数，A 是 B 的全体原子构成的集合，则 B 同构于 A 的幂集 代数 P(A);

• 集合代数：设 B 为任意集合。B 的幂集格 ⟨P(B), ∩, ∪, ∼, ∅, B⟩ 构成布尔代数，称为集合代数。

• 完全格：格的每个非空子集均有上下确界，则成为完全格。

• 有界格：若格<L, ≤>有最小元 0 和最小元 1(不记得了的话往上翻), 则成为有界格, 记作<L, ≤, 0, 1>, 完全格必然有最小元和最大元。

• 补元：有界格<L, ≤, 0, 1>中, 对任意元素 a∈L, 若存在 b∈L, 并且 a∧b = 0, a∨b = 1, 则称 b 是 a 的补元，补元不一定唯一。

• 有补格：有界格中，每一个元素 都有补元，则称为有补格。

• 布尔代数的一种定义：如果一个格是 有补分配格，那么称为布尔代数。