Un set Π cu o operație asociativă binară definită în el se numește semigrup. Un semigrup cu element de unitate este numit monoid (sau pur și simplu un semigrup cu unitate).
1. Fie X un set arbitrar, M (X) setul tuturor mapărilor X în sine. Apoi, în ceea ce privește funcționarea compoziției hărților, M (X) este un monoid, este non-comutativ. Indicăm-o prin M (X, Oex).
2. Setul de matrici pătrate de ordinul n în raport cu matrice de multiplicare - monoid necomutativă cu un singur element - matricea de identitate, precum și în ceea ce privește adăugarea de matrici - monoid comutativ cu un singur element - matricea zero. Indicați-le respectiv (Mn (R), •, E), (Mn (R), +, 0).
3. Setul de numere întregi este un monoid comutativ atât în ceea ce privește adunarea, cât și multiplicarea. Îi desemnem respectiv (Z. +, 0), (Z, • • •, 1). Setul de numere întregi care sunt divizibili de n (n> 1) este un semigrup comutativ fără unitate în ceea ce privește multiplicarea. Indicăm acest lucru prin (nZ, •).
4. Fie A = a1. a> este un set finit de simboluri - un alfabet. O succesiune finită de simboluri este numită un cuvânt în alfabetul A. Pe un set Π de cuvinte din alfabetul A se introduce o operație binară, "atribuire"; dacă, atunci. Atunci P este semigrupa. Se numește semigrupa liberă generată de setul A.
5. Setul X1, X2. X3. X4> cu privire la operația dată de tabelul Cayley (vezi Tabelul 8.1.), Este un monoid comutativ al cărui element de unitate este X1.
Un subset II 'al unei semigrupuri Π este numit subsemigroup dacă α € Є' pentru toate a, b Є Π '. În acest caz, spunem, de asemenea, că subansamblul II "este închis în cadrul operațiunii luate în considerare. subsemigroup Evident P „in sine este un semigrup în cadrul operațiunii în P. Dacă M - monoid și un M subset“ nu este numai închis în ceea ce privește operațiunile, dar conține, de asemenea, un singur element, atunci M este numit submonoid M.
De exemplu, setul de numere care sunt multiplii de n este un subsemigrup în semigrupul de întregi în ceea ce privește multiplicarea (Z., 1) și un submonoid în (Z. +, 0). În semigrupa II a cuvintelor din alfabetul A, subsetul cuvintelor din alfabetul A # 900; Și, de asemenea, un subsemigroup.
Un element a unui monoid M cu elementul e este considerat a fi inversabil dacă pentru un element b este egal ab = ba = e. Elementul b este numit inversul a și este notat cu a-1. Elementul invers este unic. Într-adevăr, dacă și ab '= b'a = e, atunci b' = eb # 900; = (ba) b '= b (ab') = fi = b.
Setul tuturor elementelor inversibile ale monoidului formează un submonoid, deoarece conține un element unic și este închis sub operație: dacă a și b sunt inversabile, atunci b-la-1 este inversul lui ab.
Considerăm problema identității cuvintelor în semigrupuri.
Fie S = s1, .sn> - elemente P subset al unui semigrup astfel încât orice element al n poate fi reprezentat ca produsul dintre elementele mulțimii S. Apoi, sistemul S este denumit generatori de P. De exemplu, pentru semigrup P liber generat de alfabet A = a1 ,. a>, setul A în sine este un sistem de generatoare; pentru numerele întregi semigrupul sub plus (Z. +, 0) este setat sistem de formare, cât și pentru semigrupul de numere întregi sub multiplicare (Z. •, 1) generatoare sunt toate numerele prime si unitate.
Trebuie notat faptul că nu toate produsele elementelor setului S sunt elemente distincte ale semigrupului II. În general, problema egalității acestor produse este destul de complexă.
Considerăm semigrupurile generate de un set finit de elemente ale acestora. Ele sunt numite generat finit.
Este posibil să specificăm un mod de definire a semigrupurilor fără a folosi proprietățile individuale ale elementelor setului în care este definită o operație semigrup, și anume definirea semigrupului de către generatori și definirea relațiilor.
Fiecare semigrup P poate fi dat de generatoare
(alfabetul unei semigrupuri) și definirea relațiilor
Elementul semigrup, adică cuvântul din alfabet (8.2.1) este numit cuvântul semigrupului P.
O transformare elementară a unui semigrup II este o tranziție de la un cuvânt cu forma XAi Y la cuvântul XBi Y (sau invers), unde X, Y. sunt cuvinte arbitrare ale semigrupului II, iar Ai = Bi; Este una dintre relațiile definitorii (8.2.2).
Transformările elementare sunt reprezentate sub forma schemelor
Schemele de transformări elementare includ, de asemenea, tranziții tautologice ale formulei X → X. Coincidența grafică a două cuvinte X și Y reprezintă X # 333; Y.
Relații (8.2.2.) Determinați egalitatea cuvintelor în semigrupa II, care este legată de transformările elementare ale semigrupului II în felul următor. Două cuvinte X și Y ale semigrupului II sunt egale în Π dacă și numai dacă există o secvență de transformări elementare ale semigrupului Π
traducând cuvântul X în cuvântul Y.
Pentru o semigroupă liberă cu alfabet (8.2.1.) Setul de relații definitorii este gol; două cuvinte sunt egale dacă și numai dacă coincid grafic.
Semigrupul (Z. +, 0) din întregi în ceea ce privește adiția poate fi definit de generatori și de definirea (în notația aditivă) a relațiilor:
Problema identității cuvintelor într-o semigrupă constă în următoarele: indică un algoritm care, prin oricare două cuvinte, ar stabili dacă sunt sau nu egale în semigrupul II. Se demonstrează că această problemă este imposibil de rezolvat din punct de vedere algoritmic. Un exemplu simplu al unei semigrupuri cu probleme de identificare a cuvintelor insolvabile este un semigrup cu generatoarele a, b, c, d, e și definirea relațiilor ac = ca, ad = da. bc = cb, bd = db. ecc = ce, edb = de. cca = ccae.
Articole similare
-
Biblioteca electronică Piața valutară și operațiunile valutare
-
Cum se înregistrează în retrospectivă ordinea în jurnalul electronic, știri, reviste "
Trimiteți-le prietenilor: