pbmatepbmatePrețuriAutentificare
pbmate logo
pbmate

Matematică pentru elevii care vor mai mult de 9

Autentificare

Platforma de matematică pentru clasele 5–12: probleme noi în fiecare zi, ajustate pentru nivelul tău — cu soluții complete, pas cu pas, până la BAC M1 și Evaluarea Națională. Sub 20 RON pe săptămână.

Ești profesor?

Clasa a 12-a

Exerciții rezolvate cu semigrupuri și monoizi — clasa a 12-a

Pe această pagină găsești 36 exerciții rezolvate cu semigrupuri și monoizi pentru clasa a 12-a, fiecare cu rezolvare completă, pas cu pas, în stilul baremului oficial de BAC. Sunt probleme tipice de examen și de teză, alese ca să exersezi eficient și să înțelegi unde apar cele mai frecvente greșeli.

Semigrupuri și monoizi #1

Un semigrup este o mulțime nevidă cu o lege de compoziție care este:
  1. A. comutativa˘\text{comutativă}
  2. B. asociativa˘\text{asociativă}
  3. C. ambele\text{ambele}
  4. D. niciuna\text{niciuna}
Rezolvare

Răspuns corect: B. asociativa˘\text{asociativă}

Un semigrup este o mulțime cu o lege de compoziție asociativă.

Semigrupuri și monoizi #2

Un monoid este un semigrup care are în plus:
  1. A. inverse pentru orice element\text{inverse}\text{ }\allowbreak{}\text{pentru}\text{ }\allowbreak{}\text{orice}\text{ }\allowbreak{}\text{element}
  2. B. un element neutru\text{un}\text{ }\allowbreak{}\text{element}\text{ }\allowbreak{}\text{neutru}
  3. C. comutativitate\text{comutativitate}
  4. D. un element zero\text{un}\text{ }\allowbreak{}\text{element}\text{ }\allowbreak{}\text{zero}
Rezolvare

Răspuns corect: B. un element neutru\text{un}\text{ }\allowbreak{}\text{element}\text{ }\allowbreak{}\text{neutru}

Monoid = semigrup + element neutru. (Un grup adaugă axioma existenței elementului simetric.)

Semigrupuri și monoizi #3

Mulțimea tuturor cuvintelor finite peste un alfabet Σ\Sigma, cu operația de concatenare, este:
  1. A. un grup\text{un}\text{ }\allowbreak{}\text{grup}
  2. B. un monoid (monoid liber)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(monoid}\text{ }\allowbreak{}\text{liber)}
  3. C. un semigrup, dar nu un monoid\text{un}\text{ }\allowbreak{}\text{semigrup,}\text{ }\allowbreak{}\text{dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{monoid}
  4. D. nici ma˘car un semigrup\text{nici}\text{ }\allowbreak{}\text{măcar}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{semigrup}
Rezolvare

Răspuns corect: B. un monoid (monoid liber)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(monoid}\text{ }\allowbreak{}\text{liber)}

Concatenarea este asociativă; cuvântul vid ε\varepsilon este elementul neutru. Nu există inverse (nu se pot „șterge" litere), deci este un monoid (nu un grup). Este monoidul liber pe Σ\Sigma.

Semigrupuri și monoizi #4

(Mn(R),⋅)(M_n(\mathbb{R}), \cdot) — matricele pătrate față de înmulțire — este:
  1. A. un grup\text{un}\text{ }\allowbreak{}\text{grup}
  2. B. un monoid (dar nu un grup)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup)}
  3. C. un semigrup, dar nu un monoid\text{un}\text{ }\allowbreak{}\text{semigrup,}\text{ }\allowbreak{}\text{dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{monoid}
  4. D. neasociativ\text{neasociativ}
Rezolvare

Răspuns corect: B. un monoid (dar nu un grup)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup)}

Înmulțirea matricelor este asociativă. Matricea unitate InI_n este elementul neutru. Dar matricea nulă nu are inversă, deci nu orice element este inversabil — este un monoid, nu un grup.

Semigrupuri și monoizi #5

((0,+∞),⋅)((0, +\infty), \cdot) — numerele reale pozitive față de înmulțire — este:
  1. A. un grup\text{un}\text{ }\allowbreak{}\text{grup}
  2. B. un monoid, dar nu un grup\text{un}\text{ }\allowbreak{}\text{monoid,}\text{ }\allowbreak{}\text{dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup}
  3. C. un semigrup, dar nu un monoid\text{un}\text{ }\allowbreak{}\text{semigrup,}\text{ }\allowbreak{}\text{dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{monoid}
  4. D. neasociativ\text{neasociativ}
Rezolvare

Răspuns corect: A. un grup\text{un}\text{ }\allowbreak{}\text{grup}

Asociativ ✓, element neutru 11 ✓, orice element are inversă ✓. Deci este un grup (comutativ).

Semigrupuri și monoizi #6

(F(E),∘)(F(E), \circ) — toate funcțiile f:E→Ef: E \to E față de compunere — este:
  1. A. un grup\text{un}\text{ }\allowbreak{}\text{grup}
  2. B. un monoid (dar nu un grup)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup)}
  3. C. un semigrup, dar nu un monoid\text{un}\text{ }\allowbreak{}\text{semigrup,}\text{ }\allowbreak{}\text{dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{monoid}
  4. D. neasociativ\text{neasociativ}
Rezolvare

Răspuns corect: B. un monoid (dar nu un grup)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup)}

Compunerea este asociativă; id⁡E\operatorname{id}_E este elementul neutru. Numai funcțiile bijective au inverse; cele nebijective nu. Deci este un monoid, nu un grup. (Grupul este SE=S_E = bijecțiile.)

Semigrupuri și monoizi #7

(Z,⋅)(\mathbb{Z}, \cdot) — numerele întregi față de înmulțire — este:
  1. A. un grup\text{un}\text{ }\allowbreak{}\text{grup}
  2. B. un monoid (dar nu un grup)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup)}
  3. C. un semigrup, dar nu un monoid\text{un}\text{ }\allowbreak{}\text{semigrup,}\text{ }\allowbreak{}\text{dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{monoid}
  4. D. neasociativ\text{neasociativ}
Rezolvare

Răspuns corect: B. un monoid (dar nu un grup)\text{un}\text{ }\allowbreak{}\text{monoid}\text{ }\allowbreak{}\text{(dar}\text{ }\allowbreak{}\text{nu}\text{ }\allowbreak{}\text{un}\text{ }\allowbreak{}\text{grup)}

Asociativ ✓, element neutru 11 ✓. Dar 22 nu are inversă multiplicativă în Z\mathbb{Z}. Deci este un monoid, nu un grup.

Semigrupuri și monoizi #8

Într-un monoid (M,∗)(M, *) cu legea simplificării, dacă a∗b=a∗ca * b = a * c, atunci:
  1. A. b=e (elementul neutru)b = e\text{ }\allowbreak{}\text{(elementul}\text{ }\allowbreak{}\text{neutru)}
  2. B. a este inversabila\text{ }\allowbreak{}\text{este}\text{ }\allowbreak{}\text{inversabil}
  3. C. b=cb = c
  4. D. b∗c=eb * c = e
Rezolvare

Răspuns corect: C. b=cb = c

Legea simplificării afirmă: a∗b=a∗c⇒b=ca * b = a * c \Rightarrow b = c. (Chiar și fără existența inverselor, această proprietate poate sau nu poate fi satisfăcută; într-un grup, ea este întotdeauna satisfăcută.)

Semigrupuri și monoizi #9

Pe N∗\mathbb{N}^* se definește legea x∗y=gcd⁡(x,y)x*y=\gcd(x,y) (cel mai mare divizor comun); se poate arăta că este asociativă, deci (N∗,∗)(\mathbb{N}^*,*) este semigrup comutativ. Câte elemente e∈{1,2,…,10}e\in\{1,2,\dots,10\} verifică x∗e=xx*e=x pentru TOȚI x∈{1,2,…,10}x\in\{1,2,\dots,10\} simultan (adică ar putea fi element neutru, cel puțin pe acest subset)?
  1. A. 00
  2. B. 11
  3. C. 22
  4. D. 1010
Rezolvare

Răspuns corect: A. 00

gcd⁡(x,e)=x⇔x∣e\gcd(x,e)=x\Leftrightarrow x\mid e. Pentru ca această condiție să se verifice SIMULTAN pentru toate valorile x=1,2,…,10x=1,2,\dots,10, numărul ee trebuie să fie multiplu al fiecăruia dintre ele, deci multiplu al cmmmc(1,2,…,10)=2520\mathrm{cmmmc}(1,2,\dots,10)=2520. Cum e∈{1,…,10}e\in\{1,\dots,10\} și 2520>102520>10, nu există niciun ee din acest interval care să satisfacă toate cele 1010 condiții simultan. Verificare: pentru e=10e=10 (candidatul cel mai mare), gcd⁡(3,10)=1≠3\gcd(3,10)=1\ne3 — deja eșuează la x=3x=3. Pentru e=1e=1, gcd⁡(2,1)=1≠2\gcd(2,1)=1\ne2 — eșuează la x=2x=2. Niciun e∈{1,…,10}e\in\{1,\dots,10\} nu funcționează pentru toți xx: (N∗,gcd⁡)(\mathbb{N}^*,\gcd) este semigrup, dar NU are element neutru (nu e monoid). Numărul căutat este 00. ✓

Semigrupuri și monoizi #10

Pe mulțimea S={Ma=(1a00):a∈R}S=\left\{M_a=\begin{pmatrix}1&a\\0&0\end{pmatrix} : a\in\mathbb{R}\right\}, înmulțirea matricelor verifică identitatea Ma⋅Mb=MbM_a\cdot M_b=M_b pentru orice a,b∈Ra,b\in\mathbb{R} (verificați prin calcul direct). Cum înmulțirea matricelor este asociativă, (S,⋅)(S,\cdot) este semigrup — dar fără element neutru (ar necesita Ma⋅Me=MaM_a\cdot M_e=M_a pentru orice aa, dar Ma⋅Me=MeM_a\cdot M_e=M_e conform identității, ceea ce ar forța Me=MaM_e=M_a pentru TOȚI aa, imposibil). Elementul de pe poziția (1,2)(1,2) al produsului M3⋅M7⋅M−2⋅M0⋅M4M_3\cdot M_7\cdot M_{-2}\cdot M_0\cdot M_4 este:
  1. A. 33
  2. B. 77
  3. C. −2-2
  4. D. 44
Rezolvare

Răspuns corect: D. 44

Verificăm întâi identitatea generală: Ma⋅Mb=(1a00)(1b00)=(1⋅1+a⋅01⋅b+a⋅000)=(1b00)=MbM_a\cdot M_b=\begin{pmatrix}1&a\\0&0\end{pmatrix}\begin{pmatrix}1&b\\0&0\end{pmatrix}=\begin{pmatrix}1\cdot1+a\cdot0&1\cdot b+a\cdot0\\0&0\end{pmatrix}=\begin{pmatrix}1&b\\0&0\end{pmatrix}=M_b — confirmată. Aplicând repetat, de la stânga la dreapta: M3⋅M7=M7M_3\cdot M_7=M_7; M7⋅M−2=M−2M_7\cdot M_{-2}=M_{-2}; M−2⋅M0=M0M_{-2}\cdot M_0=M_0; M0⋅M4=M4M_0\cdot M_4=M_4. Produsul final este M4=(1400)M_4=\begin{pmatrix}1&4\\0&0\end{pmatrix}, deci elementul de pe poziția (1,2)(1,2) este 44. Verificare prin calcul direct (fără truc): înmulțind cele 44 matrice succesiv, matricea rezultat are mereu forma (1∗00)\begin{pmatrix}1&*\\0&0\end{pmatrix} cu ∗* egal cu parametrul ultimului factor înmulțit — la final, 44. ✓

Semigrupuri și monoizi #11

Pe Z\mathbb{Z} se definește legea de compoziție x∗y=x+y−xyx*y=x+y-xy. Se știe că (Z,∗)(\mathbb{Z},*) este monoid, cu elementul neutru e=0e=0. Câte elemente ale lui Z\mathbb{Z} sunt inversabile în acest monoid?
  1. A. 11
  2. B. o infinitate\text{o}\text{ }\allowbreak{}\text{infinitate}
  3. C. 22
  4. D. 33
Rezolvare

Răspuns corect: C. 22

Fie t(x)=1−xt(x)=1-x. Atunci t(x∗y)=1−(x+y−xy)=1−x−y+xy=(1−x)(1−y)=t(x)⋅t(y).t(x*y)=1-(x+y-xy)=1-x-y+xy=(1-x)(1-y)=t(x)\cdot t(y). Cum t:Z→Zt:\mathbb{Z}\to\mathbb{Z} este bijectivă, tt este un izomorfism între (Z,∗)(\mathbb{Z},*) și (Z,⋅)(\mathbb{Z},\cdot). Elementele inversabile ale lui (Z,⋅)(\mathbb{Z},\cdot) sunt exact {1,−1}\{1,-1\}, deci elementele inversabile ale lui (Z,∗)(\mathbb{Z},*) sunt cele cu t(x)∈{1,−1}t(x)\in\{1,-1\}: t(x)=1⇒x=0t(x)=1\Rightarrow x=0; t(x)=−1⇒x=2t(x)=-1\Rightarrow x=2. Sunt exact 22 elemente inversabile: {0,2}\{0,2\}. Verificare directă: 0∗0=0+0−0=0=e0*0=0+0-0=0=e ✓ (neutrul e propriul invers). 2∗2=2+2−4=0=e2*2=2+2-4=0=e ✓, deci 22 e inversabil. Pentru x=3x=3: căutăm x′x' cu 3+x′−3x′=0⇒−2x′=−3⇒x′=32∉Z3+x'-3x'=0\Rightarrow-2x'=-3\Rightarrow x'=\tfrac32\notin\mathbb{Z} — nu e inversabil, confirmând că nu mai există alte valori. ✓

Semigrupuri și monoizi #12

Pe o mulțime cu 22 elemente, {0,1}\{0,1\}, o lege de compoziție este determinată complet de cele 44 valori 0∗0, 0∗1, 1∗0, 1∗1∈{0,1}0*0,\,0*1,\,1*0,\,1*1\in\{0,1\} — deci există 24=162^4=16 legi de compoziție posibile pe {0,1}\{0,1\}. Câte dintre aceste 1616 legi sunt asociative (deci determină o structură de semigrup pe {0,1}\{0,1\})?
  1. A. 44
  2. B. 88
  3. C. 1212
  4. D. 1616
Rezolvare

Răspuns corect: B. 88

Enumerăm exhaustiv (brute-force) toate cele 1616 legi și testăm asociativitatea pe toate cele 88 triplete posibile. Exact 88 dintre cele 1616 legi sunt asociative: - legile constante x∗y=0x*y=0 și x∗y=1x*y=1; - proiecțiile x∗y=xx*y=x (stânga) și x∗y=yx*y=y (dreapta); - „ȘI" logic (x∗y=1x*y=1 doar dacă x=y=1x=y=1) și „SAU" logic (x∗y=0x*y=0 doar dacă x=y=0x=y=0); - „XOR" (x∗y=1x*y=1 exact când x≠yx\ne y) și „echivalența" / XNOR (x∗y=1x*y=1 exact când x=yx=y). Verificare (exemplu pentru XOR, notat ⊕\oplus): (x⊕y)⊕z(x\oplus y)\oplus z și x⊕(y⊕z)x\oplus(y\oplus z) dau ambele 11 exact când numărul de 11-uri dintre x,y,zx,y,z este impar — coincid pentru toate cele 88 triplete. Verificare (exemplu pentru proiecția x∗y=xx*y=x): (x∗y)∗z=x(x*y)*z=x și x∗(y∗z)=xx*(y*z)=x — coincid trivial. Celelalte 88 legi (de exemplu cea cu 0∗0=1,0∗1=1,1∗0=0,1∗1=00*0=1,0*1=1,1*0=0,1*1=0) eșuează la cel puțin un triplet — de exemplu pentru legea menționată, (0∗1)∗0=1∗0=0(0*1)*0=1*0=0, dar 0∗(1∗0)=0∗0=1≠00*(1*0)=0*0=1\ne0. Numărul legilor asociative pe {0,1}\{0,1\} este 88. ✓
În aplicațieÎncă 24 exerciții cu semigrupuri și monoiziIntră în cont și continui direct de la semigrupuri și monoizi — nu de la zero.
Continuă în aplicație

Ești părinte? Vezi cât costă meditațiile la matematică — și alternativele.

← Toate exercițiile de clasa a 12-a