Naučte se

Monoid

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

Zkrácená definice

Monoid je pologrupa ⟨M, ◦⟩, 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

Příklady monoidů

Řetězec s operací zřetězení

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

 

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

 

Kladná reálná čísla s 0 s operací násobení (ℝ0+,·) jsou (komutativní) monoid.**
Asociativita plyne z asocitivity na ℝ.
(1 ∈ ℝ0+) a (∀a ∈ ℝ0+)(1·a = a·1 = a) => 1 je neutrální prvek
Nemá však inverzní prvek: (∀a ∈ ℝ0+)(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]

 

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).

    • (ℕ,xy), 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

Související