CH9

  • 交换律
  • 结合律
  • 消去律:消去非零元
  • 吸收律:x◦(x∗y) = x 且 x∗(x◦y) = x
  • 分配律:(x∗y)◦z = (x◦z)∗(y◦z) 且 z◦(x∗y) = (z◦x)∗(z◦y)
  • 幂等律:xx=x
  • 幺元:单位元
  • 代数系统:非空集合 S 和 S 上的 k 个一元或二元运算 f1,f2,…,fk 组 成的系统称为代数系统,简称代数,记为 ⟨S, f1, f2, … , fk⟩。
  • 子代数:
    • B ⊆ S,
    • B 对 f1,f2,…,fk 都是封闭的,
    • B 和 S 含有相同的代数常数。
    • 即证明: 运算封闭,代数常数对应。
    • 子代数总是存在;
    • 最大的子代数是 V 本身;
    • 如果 V 中所有的 代数常数 构成的集合 B 对所有的运算 是封闭的,则 B 构成了 V 的最小子代数;
    • 最大和最小子代数称为平凡的子代数;
    • 若 B 是 S 的真子集,则 B 构成的子代数称为 V 的真子代数。
  • 因子代数/积代数:
    • 设 V1 = ⟨A,◦⟩和 V2 = ⟨B,∗⟩是同类型的代数系统,◦和∗ 为二元运算。在集合 A × B 上定义如下的二元运算 • :∀⟨a1, b1⟩, ⟨a2, b2⟩ ∈ A × B, ⟨a1,b1⟩ • ⟨a2,b2⟩ = ⟨a1 ◦ a2,b1 ∗ b2⟩,称 V = ⟨A×B,•⟩为 V1 和 V2 的积代数,记为 V1 ×V2。这 时也称 V1 和 V2 为 V 的因子代数。
      • 即第一个数来自第一个集合,第二个数来自第二个集合,两组集合内的积,分别按照集合定义得运算运算,得到新的积
    • 保持交换律 (结合律,幂等律)
    • 保持零元
    • 保持可逆和逆元
    • 不保持消去律。
  • Isomorphism

CH10

  • 半群:符合二元运算且可结合
    • 设 V = ⟨S, ◦⟩ 是代数系统,◦ 为二元运算,如果 ◦ 是可结合的,则称 V 为半群;
  • 幺半群或独异点:有单位元的半群
    • 设 V = ⟨S,◦⟩是半群,如果 e ∈ S 是关于◦运算的单位元,则称 V 是幺半群或独异点。有时也将独异点记 为 V = ⟨S,◦,e⟩;
  • 群:有单位元,可结合,有逆元
  • 设 G 为有限群,,则 当且仅当 a 为一阶元或二阶元。
  • 设 G 为有限群,则 G 中阶大于 2 的元素有偶数个。
  • 置换群:双射 S -> S
    • 对称群:所有 n 元置换构成的集合 S,有 3! 个
    • 轮换:σ(i1) = i2,σ(i2) = i3,…,σ(ik−1) = ik,σ(ik) = i1 (1 < k < n), k 阶轮换,(i1, i2, … , ik)
    • 对换:k = 2
  • 子群格:设 G 为群,令 S = {H | H 是 G 的子群} 是 G 的所有子群的 集合,在 S 上定义如下关系 R: ∀A, B ∈ S, ARB ⇔ A 是 B 的子群 则 ⟨S, R⟩ 构成偏序集,成为群 G 的子群格。
  • Group
  • Coset
  • Ring

CH11

格和布尔代数

  • 格:设 ⟨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 ∧ 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 的补元,补元不一定唯一。

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

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

Link to original