1. Sisaldab vähemalt 3 elementi Olgu f bijektiine ja rekursiivne, kui A sisaldab vähemalt 3 elementi, siis f (A) samuti tänu bijektiivsusele 2. On tühi samuti tänu bijektiivsusele 3. On lõputu 2 Margus Martsepp, Rekursiooni- ja keerukusteooria harjutus 3.nb samuti tänu bijektiivsusele 4. On rekursiivselt loenduv (RL) A on rekursiivselt loendub hulk, ta on kas tühi (siis 3.) või leidub totaalne funktsioon f , nii et A range f . Olgu g suvaline bijektiivne rekursiivne funtsioon B g(a), B range (g f ), kus g f on totaalne arvutatav funktsioon ja annab täpselt B ele- menti. x f (x) annab A elementi, g on totaalne. g saab sisendiks ainult A elemente, seega tulemuseks ainust B elemendid. Millised neljast omadusest: 1. A = {x | x on paarisarv} Tegemist on rekursiivse funktsiooniga, sest eksisteerib karakteristlik funktsioon 1 , kui x mod 2 0 Xa x . 0 , kui x mod 2 0
Funktsiooni f: AB nimetatakse · Injektiivseks ehk üksüheseks, kui iga elemendipaari x1, x2 A, x1x2 korral f(x1)f(x2). · Sürjektiivseks ehk pealekujutuseks, kui igal elemendil hulgast B leidub originaal hulgas A. · Bijektiivseks ehk üksüheseks vastavuseks, kui funktsioon on korraga injektiivne ja sürjektiivne. Injektiivne funktsioon on selline, kus ühelgi elemendil hulgast B ei ole üle ühe originaali. Bijektiivne funktsioon on selline, kus igale elemendile hulgast B leidub täpselt üks originaal. Funktsiooni graafik: Vaatleme funktsiooni f: AB. Hulka {(x,f(x)) : xX} nimetatakse funktsiooni f graafikuks ning tähistatakse G(f). Graafik G(f) kuulub hulka AxB. Hulk C AxB on mingi funktsiooni graafik parajasti siis, kui kehtivad tingimused: · iga x A korral leidub y B, et (x, y) C (igale elemendile hulgast A peab vastama mingi element hulgast B).
2 · Funktsioon f : ¿ R , f (x)=x , ei ole sürjektiivne, aga on injektiivne. Definitsioon Olgu X ja Y hulgad. Funktsiooni f : X Y nimetatakse bijektiivseks ehk üksüheseks vastavuseks, kui f on nii injektiivne kui ka sürjektiivne. Märkus. Bijektiivsus tähendab, et igal hulga Y elemendil leidub täpselt üks originaal. Näide: - · Funktsioon sin :[ 2 , 2 ][-1,1] on bijektiivne. 2 · Funktsioon f :¿ ¿ , f (x )=x , on bijektiivne. Tuvipuuri printsiip Olgu meil A tuvide ja B tuvipuuride hulk. Võime vaadelda funktsiooni f : AB , kus tuvi x lendab puuri f ( x) . · Joonisel (a) on tuvisid rohkem kui tuvipuure, seega sel juhul vähemalt kaks tuvi peavad lendama ühte puuri. Teisisõnu, f pole injektiivne.
ning iga B elemendi b korral kehtib seos: (f(a) = b AND f(a') = b) => a = a' (igale elemendile vastavuses vid üks kindel element) · bijektsiooniks -> kui kujutus on samaaegselt sürjektsioon ja injektsioon Idee poolest on kujutus teatud tüüpi vastavus hulgast A hulka B. Hulgad A ja B on võrdvõimsad, kui leidub bijektiivne vastavus (M:A B) nende vahel (ehk siis kõik elemendid mõlemast hulgast on haaratud ja igaühele vastab vaid 1 kindel element). Lõpmatut hulka nimetatakse loenduvaks, kui see on võrdvõimas naturaalarvude hulgaga. |H| on hulga võimsus ehk lõpliku hulga korral elementide arv hulgas. Lõpmatu hulga võimsus leitakse, seades tema elemendid bijektiivsesse vastavusse (üks- ühesesse) mõne tuntud võimsusega hulga (näiteks naturaalarvude hulga) elementidega. 4. Graafid. Puude esitused
Kui A ⊆ B, siis f(A) ⊆ f(B) 16 4. f(A∪B) = f(A) ∪ f(B) 5. f(A∩B) ⊆ f(A) ∩ f(B) Originaali omadused o Olgu f funktsioon X→Y ja A, B ⊆ Y. Siis 1. f-1 (∅) = ∅ 2. f -1(Y) = X 3. Kui A ⊆ B, siis f -1(A) ⊆ f -1(B) 4. f -1(A∪B) = f -1(A) ∪ f -1(B) 5. f -1(A∩B) = f -1(A) ∩ f -1(B) 6. f -1(B’) = (f -1(B))’ st f -1(YB) = X f -1(B) 20. Injektiivne funktsioon. Sürjektiivne funktsioon. Bijektiivne funktsioon. Pöördfunktsiooni mõiste. [3, 4,5] Injektiivne funktsioon o DEF: Funktsiooni f : X→Y nimetatakse injektiivseks ehk üksüheseks, kui erinevate argumendi väärtuste korral on funktsiooni väärtused erinevad: x1!=x2 ⇒f(x1)!= f(x2). o Injektiivsus tähendab, et ühelgi hulga Y elemendil pole rohkem, kui üks originaal. Sürjektiivne funktsioon o DEF: Funktsiooni f : X→Y nimetatakse sürjektiivseks ehk pealekujutuseks, kui iga y∈Y
gf : Pn+ - Pn+ , f g : Pn- - Pn- , mille kohaselt gf (1 2 3 . . . n ) := g(f (1 2 3 . . . n )) = = g(2 1 3 . . . n ) = 1 2 3 . . . n ja f g(1 2 3 . . . n ) := f (g(1 2 3 . . . n )) = = f (2 1 3 . . . n ) = 1 2 3 . . . n . N¨aeme, et kujutused gf ja f g on samasuskujutused. Sel korral kujutus g on kujutuse f p¨o¨ordkujutus. Kujutus, millel on olemas p¨o¨ordkujutus, on bijektiivne. Seega l~oplikuelemendilistes hulkades Pn+ ja Pn- on samapalju elemente. Teoreemi 2.1 kohaselt on paaris- ja permutatsioonide arv 12 n!. 24 Selle teoreemi kirjapanekuks kasutasime kujutustega seotud m~oisteid ~oppeainest "Sissejuhatus erialasse". L~opuks vaatleme permutatsoonide hulgal Pn teatavat teisendust : Pn Pn . Tema definitsiooni andmiseks on vaja seletada, kuidas mista- hes permutatsiooni 1 2 ...n Pn korral leida kujutis (1 2 ..
mille kohaselt gf (α1 α2 α3 . . . αn ) := g(f (α1 α2 α3 . . . αn )) = = g(α2 α1 α3 . . . αn ) = α1 α2 α3 . . . αn ja f g(α1 α2 α3 . . . αn ) := f (g(α1 α2 α3 . . . αn )) = = f (α2 α1 α3 . . . αn ) = α1 α2 α3 . . . αn . N¨aeme, et kujutused gf ja f g on samasuskujutused. Sel korral kujutus g on kujutuse f p¨o¨ordkujutus. Kujutus, millel on olemas p¨o¨ordkujutus, on bijektiivne. Seega l˜oplikuelemendilistes hulkades Pn+ ja Pn− on samapalju elemente. Teoreemi 2.1 kohaselt on paaris- ja permutatsioonide arv 12 n!.♠ 24 Selle teoreemi kirjapanekuks kasutasime kujutustega seotud m˜oisteid ˜oppeainest ”Sissejuhatus erialasse”. L˜opuks vaatleme permutatsoonide hulgal Pn teatavat teisendust τ : Pn ↔ Pn . Tema definitsiooni andmiseks on vaja seletada, kuidas mista- hes permutatsiooni α1 α2 ..
- bijektiivseks, kui funktsioon on injektiivne ja sürjektiivne. Injektiivsus tähendab, et ühelgi hulga elemendil pole rohkem kui üks originaal. Sürjektiivsus tähendab, et igal hulga elemendil leidub vähemalt üks originaal. Bijektiivsus tähendab, et igal hulga elemendil leidub täpselt üks originaal. Bijektsioon kui üksühene vastavus Hulgateooria seisukohalt on funktsioonid : paaride hulgad ={(,) | =()}. Bijektiivne funktsioon : on siis selline paaride hulk, kus 1. iga jaoks leidub parajasti üks paar, milles on esimene komponent, 2. iga jaoks leidub parajasti üks paar, milles on teine komponent. Bijektiivseid funktsioone nimetatakse ka üksühesteks vastavusteks hulkade ja elementide vahel (või lihtsalt hulkade ja vahel). Näiteid üksüheste vastavuste kohta. 1. Olgu = {1,2,3,4,5} ja = {,,,,}. Nende hulkade elemendid saame seada
seid, n¨aiteks algebralisi), siis on neid ruume m˜oistlik lugeda topoloogiliselt samav¨a¨arseteks, kui nende vahel eksisteerib sel- line u¨ks¨uhene vastavus, milles u ¨he ruumi lahtisele hulgale vastab teise ruumi lahtine hulk ja vastupidi. Nii j˜outaksegi j¨argmise m˜oisteni. ¨ Definitsioon 4.5 Oeldakse, et topoloogilised ruumid X ja Y on hom¨ oomorfsed ja t¨ahistatakse X ≈ Y , kui lei- dub selline bijektiivne kujutus f : X −→ Y , et ruumi X iga alamhulga A korral hulk A on lahtine parajasti siis, kui tema kujutis f (A) on lahtine ruumis Y . Vastavat kujutust f nimetatakse hom¨ oomorfismiks. Teoreem 4.20 Topoloogilised ruumid X ja Y on hom¨ oomorf- sed parajasti siis, kui leidub selline bijektiivne kujutus f : X −→ Y , et nii f kui ka f −1 on pidevad. T˜oestus. Kui X ≈ Y , siis leidub selline bijektiivne kujutus
a. Tippude järjendit v0, v1,..., vk, kus iga kaks järjestikku tippu vi ja vi+1 on ühendatud kaarega vivi+1, nimetatakse suunatud ahelaks. b. Suunatud tsükkel on suunatud ahel, mis algab ja lõpeb samas tipus. c. Kui suunatud ahelas või suunatud tsüklis ükski tipp ega serv ei kordu, siis on tegemist suunatud lihtahela või suunatud lihttsükliga. d. Suunatud graafe G = (V, E) ja G' = (V', E') nimetatakse isomorfseteks, kui leidub selline bijektiivne funktsioon f: V V', et graafis G on olemas kaar uv parajasti siis, kui graafis G' on olemas kaar f(u)f(v). e. Graafide isomorfismi näitamiseks tuleb konstrueerida vastav bijektsioon. f. Mitteisomorfismi näitamiseks saab kasutada invariante, mis säilivad isomorfismi korral: tippude sisend- ja väljundastmed, tsüklid jms. 49) a. Suunatud graafi nimetatakse tugevalt sidusaks, kui iga kahe tipu u ja v korral leidub suunatud ahel tipust u tippu v
alamgraaf, mis ei sisaldu üheski teises tugevalt sidusas alamgraafis o Graaf on tugevalt sidus parajasti siis, kui tal on täpselt üks tugevalt sidus komponent Teoreem suundade määramisest: kui sidusas (suunamata) graafis ei leidu ühtegi silda, siis saab graafi servadele määrata suunad nii, et tekkinud suunatud graaf on tugevalt sidus Suunatud graafe =(,) ja '=(',') nimetatakse isomorfseteks, kui leidub selline bijektiivne funktsioon : ', et graafis on olemas kaar parajasti siis, kui graafis ' on olemas kaar ()() o Isomorfismi näitamiseks tuleb konstrueerida vastav bijektsioon o Mitteisomorfismi näitamiseks saab kasutada invariante: tippude ja servade arvud, tippude sisend- ja väljundastmed, mingi pikkusega tsüklite olemasolu, sidususe näitajad Lühima tee leidmine laiuti otsimise teel: o Olgu kaalutud suunatud graaf, mille tipud on nummerdatud
Kui vähemalt üks elemen- tidest a ja b on 0, siis ka ab = 0 (vt. lauset 1.1(a)). Juhul a > 0 ja b > 0 saame ab > 0. Juhul a > 0 ja b < 0 kehtib −b > 0 (miks?z) ning võrratuse a > 0 pooli positiivse elemendiga −b korrutades leiame, et a · (−b) > 0 · (−b), mistõttu −(ab) > 0 ehk ab < 0 (vt. lauset 1.1(c)). Analoogselt vaatame läbi ka ülejäänud kaks võimalust (iseseisvalt!)z. Definitsioon. Kahte järjestatud korpust F1 ja F2 nimetatakse isomorfseteks, kui eksis- teerib bijektiivne kujutus ϕ : F1 → F2 , mis rahuldab tingimusi 1) ϕ (q + q ′ ) = ϕ (q) + ϕ (q ′ ), 2) ϕ (qq ′ ) = ϕ (q) · ϕ (q ′ ) ja 3) q < q ′ korpuses F1 parajasti siis, kui ϕ (q) < ϕ (q ′ ) korpuses F2 . 1.1.3 Täielik järjestatud korpus Olgu X järjestatud korpuse F mittetühi alamhulk. Definitsioon. Öeldakse, et hulk X on ülalt tõkestatud (bounded from above, ограниченное сверху), kui leidub selline a ∈ F , et võrratus x 6 a kehtib iga x ∈ X korral
annaabi.ee 
