Zoran Skoda
monoid

Polugrupa (engl. semigroup) je skup s jednom asocijativnom binarnom operacijom koja je svuda definirana. Drugim riječima, polugrupa je asocijativna binarna algebarska struktura (asocijativna magma).

Dakle, polugrupa (M,)(M,\cdot) je skup MM zajedno s funkcijom :M×MM\cdot : M\times M\to M koju zovemo operacija polugrupe i koja je asocijativna, tj.

a(bc)=(ab)c,a,b,cM. a\cdot (b\cdot c) = (a\cdot b)\cdot c,\,\,\,\,\,\,\,\forall a,b,c\in M.

Jednostavni primjer polugrupe je polugrupa riječi (W(A),)(W(A), \cdot) gdje je AA neki skup simbola, koji zovemo alfabet, a W(A)W(A) je skup svih nepraznih riječi tj. slogova (= konačnih nizova) simbola koje se mogu sastaviti iz alfabeta. Operacija je spajanje (konkatenacija) riječi. Npr. za alfabet možemo uzeti skup slova abecede pa će npr. KNJI \cdot GA = KNJIGA. Lako se vidi da je ta operacija asocijativna.

Skup prirodnih brojeva N\mathbf{N} (nulu ne računamo) je polugrupa s obzirom na operaciju zbrajanja. Možemo promatrati broj nn kao riječ koja se sastoji od nn simbola \bullet. Npr. 3=3 = \bullet\bullet\bullet. Tada je zbrajanje prirodnih brojeva isto što i konkatenacija u W(A)W(A) gdje je AA jednočlani skup A={}A = \{\bullet\}. Npr. 2+3=+==52+3 = \bullet\bullet+\bullet\bullet\bullet = \bullet\bullet\bullet\bullet\bullet = 5. U polugrupama riječi je redoslijed slova bitan, ali ako imamo samo jedno slovo na raspolaganju, onda ne možemo razlikovati poredak.

Monoid (M,,e)(M,\cdot,e) je polugrupa (M,)(M,\cdot) u kojoj postoji neutralni element, tj. element ee takav da em=e=mee\cdot m = e = m\cdot e za sve mMm\in M.

Neutralni element u monoidu je jedinstven zbog asocijativnosti (to nije točno za svaku magmu). Zaista, ako je ee neki lijevi neutralni element u polugrupi MM, tj. em=me\cdot m = m za svaki mMm\in M i ee' neki desni neutralni element u polugrupi MM, tj. ne=nn\cdot e' = n za svaki nMn\in M, tada je e=ee=ee' = e\cdot e' = e. Prva jednakost vrijedi jer je ee neutralni slijeva, a druga jer je ee' neutralni zdesna. Dakle u polugrupi je svaki lijevi neutralni element jednak svakom desnom neutralnom elementu, pa su svi oni jednaki ako postoje lijevi i desni. Ako je posebno neki element obostrani neutralni element, takav je dakle neutralan.

Jednostavni primjer monoida je polugrupa riječi (W 0(A),)(W_0(A), \cdot) gdje je AA neki skup simbola, koji zovemo alfabet, a W 0(A)W_0(A) je skup svih riječi u zagradama gdje dozvoljavamo i praznu riječ (), tj. slogova (= konačnih nizova) simbola koje se mogu sastaviti iz alfabeta unutar jednog para zagrada, npr. (KNJI). Operacija je spajanje (konkatenacija) riječi, pri čemu ispustimo unutarnje zagrade. Npr. za alfabet možemo uzeti skup slova abecede pa će npr. (KNJI)\cdot(GA) = (KNJIGA). Lako se vidi da je ta operacija asocijativna i da je prazna riječ () neutralni element, npr. ()\cdot(WORD) = (WORD). Konkatenacija riječi nije komutativna. Npr.

(LAS)\cdot(TA) == (LASTA) \neq (TALAS) = (TA)\cdot(LAS).

Prirodni brojevi s nulom čine monoid ( 0,+)(\mathbb{N}_0,+) u odnosu na zbrajanje. Uvjerite se u to! Taj primjer se može tretirati, slično kao i gore, kao konkatenacija riječi u alfabetu s jednim slovom, pri čemu dozvoljavamo i praznu riječ pa je zgodno riječ staviti u vanjske zagrade.

Najvažnija klasa monoida su grupe.

category: zadarmat4

Last revised on July 9, 2018 at 09:37:00. See the history of this page for a list of all contributions to it.