半環 | Notion

半環の例

$(\mathbb{N}, \min, +)$, $(\mathbb{N}, \max, +)$ (min plus, max plus)
- a + min(b, c) = min(a + b, a + c)
- min-plus, max-plus 代数
$(\mathbb{N}, \gcd, \times)$, $(\mathbb{N}, \operatorname{lcm}, \times)$
- a × gcd(b, c) = gcd(a × b, a × c)
- 素因数分解で得られる指数の列で min/max や足し算をしたものだと思える
- lcm の方は、lcm も mul も単位元が1なのに注意？（これは半環になる？）
$(\mathbb{Z}\cup\{+\infty, -\infty\}, \min, \max)$
- min, max で分配法則が成り立つ: 不等号とmin,max
- min と max を入れ替えてももちろん半環？
($[2^{64}]$, or, and), ($[2^{64}]$, and, or)
- 環ではない半環
($[2^{64}]$, xor, and), ($[2^{64}]$, xnor, or)
- 環である。
- これは $(\mathbb{Z}/2\mathbb{Z})^{64}$ と同型 (bit ごとに考える)
- cf: 論理演算