半环

带合并运算 ⊕ 与组合运算 ⊗ 的代数结构;定义分配律、吸收律与单位元。

标签 数学 / 半环 / 代数结构 / 动态规划

定义

设 𝑆 是集合,⊕ 与 ⊗ 是 𝑆 上的二元运算,0,1∈𝑆。若满足以下条件,称 (𝑆,⊕,⊗,0,1) 为半环:

  • (𝑆,⊕,0) 是交换 幺半群:⊕ 满足交换律、结合律,0 是单位元;
  • (𝑆,⊗,1) 是幺半群:⊗ 满足结合律,1 是单位元;
  • ⊗ 对 ⊕ 满足左右分配律:

    𝑎⊗(𝑏⊕𝑐)=(𝑎⊗𝑏)⊕(𝑎⊗𝑐),(𝑎⊕𝑏)⊗𝑐=(𝑎⊗𝑐)⊕(𝑏⊗𝑐);
  • 0 是 ⊗ 的吸收元:

    0⊗𝑎=𝑎⊗0=0.

以上等式对所有 𝑎,𝑏,𝑐∈𝑆 成立。有些定义还要求 0≠1;本页不把这条列为必要公理。

幂等半环

若 𝑎⊕𝑎=𝑎 对所有 𝑎∈𝑆 成立,称 ⊕ 幂等,并称该半环为幂等半环。

源码位置