TV「たけしのコマネチ大学数学科」に出てきた「トロピカルな和と積」は面白い話題でした。
トロピカル演算(マックス・プラス代数)
- トロピカルな和を、 "2 + 5" = 5 のように、max関数(最大値)として定義: "a + b" = max(a, b)
- トロピカルな積を、 "2 × 5" = 7 のように、和として定義: "a × b" = a + b
- このときでも、通常の和と積のように、「結合法則」「交換法則」「分配法則」が成り立つ。
結合法則: a × (b × c) = (a × b) × c
トロピカルな記法 |
HLSL的な記法 |
""2 + 5" + 3" = 5 |
max(2, max(5, 3)) = 5 |
"2 + "5 + 3"" = 5 |
max(max(2, 5), 3) = 5 |
交換法則: a × b = b × a
トロピカルな記法 |
HLSL的な記法 |
"2 × 5" = 7 |
2 + 5 = 7 |
"5 × 2" = 7 |
5 + 2 = 7 |
分配法則: a × (b + c) = a × b + a × c
トロピカルな記法 |
HLSL的な記法 |
"2 × "5 + 3"" = 7 |
2 + max(5, 3) = 7 |
""2 × 5" + "2 × 3"" = 7 |
max(2 + 5, 2 + 3) = 7 |
様々な記法
"a + b" = a ⊕ b = a ∨ b := max(a, b)
a ∧ b := min(a, b)
"a × b" = a ⊗ b := a + b
|
|
HLSL的な記法 |
トロピカルな加法のべき等(idempotent) |
a ⊕ a = a |
max(a, a) = a |
以上を踏まえて考えてみた(HLSL的な記法)
※乗算を含む場合は符号を制限する必要あり。
min(min(a, b), c) = min(a, min(a + c)) |
max(max(a, b), c) = max(a, max(a + c)) |
min(a, b) = min(b, a) |
max(a, b) = max(b, a) |
a + min(b, c) = min(a + b, a + c) |
a + max(b, c) = max(a + b, a + c) |
a * min(b, c) = min(a * b, a * c) |
a * max(b, c) = max(a * b, a * c) |
min(a, b | c) = min(a, b) | min(a, c) |
max(a, b | c) = max(a, b) | max(a, c) |
min(a, b & c) = min(a, b) & min(a, c) |
max(a, b & c) = max(a, b) & max(a, c) |
a | min(b, c) = min(a | b, a | c) |
a | max(b, c) = max(a | b, a | c) |
a & min(b, c) = min(a & b, a & c) |
a & max(b, c) = max(a & b, a & c) |
a + b = (a | b) + (a & b) |
a + b = min(a, b) + max(a, b) |
(a | b) - min(a, b) = max(a, b) - (a & b) |