Monoid

Monoid je algebraická struktura, která má neutrální prvek.

Úplná definice

Monoid je matematická struktura ⟨M, ○⟩, pro kterou je binární operace ○ uzavřená na množině M. Operace ○ je asociativní a množina M obsahuje neutrální prvek.

• Asociativita: (∀x,y,z ∈ M) (x◦y)◦z = x◦(y◦z),
• Neutrální prvek: (∃e ∈ M)(∀x ∈ M) x◦e = e◦x = x

Stručná definice

Monoid je pologrupa ⟨M, ◦⟩, která má neutrální prvek.

Příklady monoidů

Řetězec s operací konkenace

("foo" ++ "bar") ++"baz" -- foo­bar­baz

"foo" ++ ("bar"++"baz") -- foo­bar­baz

"" ++ "foo"-- foo

Přirozená čísla

Přirozená čísla s operací sčítání (ℕ,+) jsou (komutativní) monoid.

(2 + 3) + 4 -- 9

2 + (3 + 4) -- 9

0 + 100 -- 100

Přirozená čísla s operací násobení (ℕ,·) jsou (komutativní) monoid.

(2 * 3) * 4 -- 24

2 * (3 * 4) -- 24

1 * 100 -- 100

Reálná čísla

Kladná reálná čísla s 0 s operací násobení (ℝ₀⁺,·) jsou (komutativní) monoid. Asociativita plyne z asocitivity na ℝ.

(1 ∈ ℝ₀⁺) a (∀a ∈ ℝ₀⁺)(1·a = a·1 = a) => 1 je neutrální prvek
Nemá však inverzní prvek: (∀a ∈ ℝ₀⁺)(0·a != 1)

([...],++), seznamy s operací přidání na konec

([1, 2] ++ [3, 4]) ++ [5, 6] -- [1, 2, 3, 4, 5, 6]

[1, 2] ++ ([3, 4] ++ [5, 6]) -- [1, 2, 3, 4, 5, 6]

[] ++ [1, 2, 3] -- [1, 2, 3]

Výroková logika

Boolean s operací nebo

(True or True) or False -- True

True or (True or False) -- True

False or True -- True

Boolean s operací a

(True and True) and False -- False

True and (True and False) -- False

True and False -- False

K zamyšlení

1. Jsou následující struktury monoidy?

• (ℕ,−), přirozená čísla s odčítáním.

• Ne (není asociativní, neexistuje neutrální prvek).

• (ℕ,x^y), přirozená čísla s umocňováním.

  • Ano, (komutativní) monoid.

• ({f|f::a→a},.), funkce typu a -> a se skládáním.

  • Ano, (NEkomutativní) monoid