跳到主要内容

代数系统基础

代数系统是离散数学中研究“集合+运算”结构的抽象分支。它为计算机科学中的数据结构（如栈、队列的性质）和信息安全（如 RSA 加密的群论基础）提供了统一的数学语言。

1. 二二元运算及其性质​

1.1 定义​

设 SS 为集合，函数 f:S×S→Sf: S \times S \to S 称为 SS 上的二元运算。

  • 封闭性：二元运算的结果必须仍在 SS 中（定义中已包含）。

1.2 核心性质​

设 ∗* 是 SS 上的运算：

  1. 交换律：x∗y=y∗xx * y = y * x
  2. 结合律：(x∗y)∗z=x∗(y∗z)(x * y) * z = x * (y * z)
  3. 幂等律：x∗x=xx * x = x
  4. 分配律：若有两运算 ∗* 和 ∘\circ，满足 x∗(y∘z)=(x∗y)∘(x∗z)x * (y \circ z) = (x * y) \circ (x * z)。

1.3 特殊元素​

  • 单位元 (Identity)：存在 e∈Se \in S，使 ∀x∈S,x∗e=e∗x=x\forall x \in S, x * e = e * x = x。
  • 零元 (Zero)：存在 θ∈S\theta \in S，使 ∀x∈S,x∗θ=θ∗x=θ\forall x \in S, x * \theta = \theta * x = \theta。
  • 逆元 (Inverse)：若存在单位元 ee，对 x∈Sx \in S，若存在 y∈Sy \in S 使 x∗y=y∗x=ex * y = y * x = e，则 yy 称为 xx 的逆元，记作 x−1x^{-1}。

2. 典型的代数结构​

2.1 半群与独异点​

  • 半群 (Semigroup)：满足结合律的代数系统 ⟨S,∗⟩\langle S, * \rangle。
  • 独异点 (Monoid)：含单位元的半群。

2.2 群 (Group)​

若 ⟨G,∗⟩\langle G, * \rangle 满足：

  1. 结合律；
  2. 存在单位元；
  3. 每个元素都有逆元。 则称 ⟨G,∗⟩\langle G, * \rangle 为群。若还满足交换律，称为 Abel 群。

:::info 例题 证明：群中的单位元是唯一的。 :::

查看证明

假设存在两个单位元 e1,e2e_1, e_2。 根据 e1e_1 是单位元，e1∗e2=e2e_1 * e_2 = e_2。 根据 e2e_2 是单位元，e1∗e2=e1e_1 * e_2 = e_1。 所以 e1=e2e_1 = e_2。单位元唯一。

3. 子系统、同态与同构​

3.1 子代数​

若 V=⟨S,f1,f2,… ⟩V = \langle S, f_1, f_2, \dots \rangle 是代数系统，B⊆SB \subseteq S 且对所有运算封闭，则 ⟨B,f1,f2,… ⟩\langle B, f_1, f_2, \dots \rangle 是 VV 的子代数。

3.2 同态 (Homomorphism)​

设 ⟨A,∗⟩\langle A, * \rangle 和 ⟨B,∘⟩\langle B, \circ \rangle 是两个代数系统。若映射 h:A→Bh: A \to B 满足： h(x∗y)=h(x)∘h(y)h(x * y) = h(x) \circ h(y) 则称 hh 为同态映射。

  • 若 hh 是双射，则称为同构 (Isomorphism)，记作 A≅BA \cong B。

4. 经典练习​

:::info 练习 1 设 S={a,b,c}S = \{a, b, c\}，定义运算 ∗* 如下表：

*abc
aabc
bbbc
cccc
判断该系统是否满足结合律，并找出单位元和零元。
:::
查看解析
  1. 单位元：观察第一行和第一列，a∗x=x∗a=xa * x = x * a = x。故单位元为 aa。
  2. 零元：观察最后一行和最后一列，c∗x=x∗c=cc * x = x * c = c。故零元为 cc。
  3. 结合律：通过遍历可证满足结合律（该运算实际上是 SS 在全序 a<b<ca < b < c 下的求最大值运算 maxmax）。

:::info 练习 2 证明：在任何独异点中，若元素 xx 有逆元，则其逆元是唯一的。 :::

查看解析

设 y,zy, z 都是 xx 的逆元，则 x∗y=y∗x=ex * y = y * x = e 且 x∗z=z∗x=ex * z = z * x = e。 y=y∗e=y∗(x∗z)=(y∗x)∗z=e∗z=zy = y * e = y * (x * z) = (y * x) * z = e * z = z。 故逆元唯一。

本章节由 SolKnow 系统根据代数系统理论构建。