Tõestus. 1. Hulgal defineeritud samasusteisendus () = seab hulga üksühesesse vastavusse iseendaga. 2. Kui , siis leidub bijektsioon : . Funktsiooni pöördfunktsioon -1 on siis samuti bijektsioon 3. Kui ja , siis leiduvad bijektsioonid : ja : . Nende kompositsioon : on siis samuti bijektsioon. Hulga võimsuseks nimetatakse tema ekvivalentsiklassi seose ~ järgi. Võimsusi nimetatakse ka kardinaalarvudeks. Hulga võimsuse jaoks kasutatakse tähiseid ||, ja . Loenduvad hulgad Hulka nimetatakse loenduvaks, kui leidub üksühene vastavus naturaalarvude hulga ja hulga vahel. Seega loenduvad on parajasti need hulgad , mida saab esitada kujul ={1,2,3,...}. Näiteid 1. Täisarvude hulk ja paaris-naturaalarvude hulk on loenduvad hulgad. 2. Igasugune hulga lõpmatu osahulk on ise loenduv ning sama võimsusega kui naturaalarvude hulk . 3. Ratsionaalarvude hulk on loenduv ning sama võimsusega kui naturaalarvude hulk või täisarvude hulk . 4
Kui hulk on lõplik, siis on ta ka loenduv Vali üks: Tõene Väär Küsimus 16 - Õige / Hinne 1,00 / 1,00 vali õige: on iga hulga osahulgaks. tühi hulk Küsimus 17 - Õige / Hinne 1,00 / 1,00 Kaks hulka on võrdsed siis, kui . . . Vali üks või enam: . . . neis mõlemas on samapalju elemente . . . nad mõlemad on mitteloenduvad hulgad . . . nad mõlemad on tähistatud mingi suurtähega . . . nad mõlemad on loenduvad hulgad . . . nad koosnevad täpselt samadest hulgaelementidest . . . nende mõlema elementideks on täisarvud . . . nad mõlemad on lõplikud hulgad . . . nad mõlemad on lõpmatud hulgad Küsimus 18 - Õige / Hinne 1,00 / 1,00 Vali kõik viisid / vahendid, mida kasutatakse hulkade esitamiseks: Vali üks või enam: Hasse diagramm tõeväärtust omava lause kaudu, mis on tõene iga hulgaelemendi korral hulgaelementide täielik loetelu loogikaavaldis numbriline kümnendesitus
. . nad mõlemad on tähistatud mingi suurtähega . . . nad mõlemad on lõplikud hulgad . . . nad mõlemad on mitteloenduvad hulgad . . . nad mõlemad on lõpmatud hulgad . . . nad koosnevad täpselt samadest hulgaelementidest . . . nende mõlema elementideks on täisarvud . . . neis mõlemas on samapalju elemente . . . nad mõlemad on loenduvad hulgad Küsimus 17 Õige Hindepunkte 2,00/2,00 vali õiged: hulkade ühisosa on hulkade korrutamine ja selle tehte tulemuseks olev hulk on (üldjuhul) väiksem kui operandideks olnud hulgad Küsimus 18 Õige Hindepunkte 1,00/1,00 Kas väide on õige või vale ? Kui hulk on loenduv, siis on ta ka lõplik Valige üks: Tõene Väär Küsimus 19 Õige Hindepunkte 1,00/1,00 A ja B on hulgad
. . . neis mõlemas on samapalju elemente . . . nad koosnevad täpselt samadest hulgaelementidest . . . nad mõlemad on lõplikud hulgad . . . nad mõlemad on tähistatud sama suurtähega . . . nad mõlemad on loenduvad hulgad Question 19 kas järgnev väide on õige või vale ? Lehekülg 3/4 24.11.2012 19:39 KONTROLLKÜSIMUSTEGA TEST -- hulgad I file:///C:/Users/CPU/Desktop/Diskmati_TESTID_moodle__'s_-_100%... Correct tühi hulk ja universaalhulk on iga hulga osahulkadeks.
kasutatakse hulkade üksühese vastavuse mõistet. Ütleme, et hulgad A ja B on sama võimsusega, kui leidub bijektsioon f : A B. Tähis: A B, öeldakse ka, et hulgad A ja B on ekvivalentsed. Kehtivad omadused: · refleksiivsus: A A · sümmeetrilisus: kui A B, siis B A · transitiivsus: kui A B ja B C, siis A C Hulka, mis on sama võimsusega nagu naturaalarvude hulk, nimetatakse loenduvaks hulgaks. · Järelikult on loenduvad parajasti need hulgad, mis on esitatavad jadana {a0, a1, a2, . . .}. · Iga lõpmatu hulk sisaldab loenduvat osahulka. · Loenduva hulga iga lõpmatu osahulk on samuti loenduv. Cantor-Bernsteini teoreem Definitsioon Ütleme, et hulga A võimsus ei ületa hulga B võimsust, kui leidub injektsioon f : A B. Teoreem (Cantor-Bernsteini teoreem.) Kui hulga A võimsus ei ületa hulga B võimsust ja
Chomsky keelte klassifikatisioon: • kitsenduseta fraasistruktuuri keeled: α → β, kus α ja β on mis tahes lausevormid tähestikus V = Σ∪N; • KS keeled: α → β , kus α sisaldab vähemalt üht mitteterminali ja |α| <= |β|, v.a. S → ε; • KV keeled: A→β; • regulaarsed keeled: A→a ja A→aB. Turingi masina keeled on kõik kitsenduseta fraasistruktuuri keeled. On ka mitte-TM keeli. 16 Turingi masin ja registermasin. Lahenduvad ja rekursiivselt loenduvad hulgad. Turingi masina sisendiks on mõlemas suunas lõpmatu lint, millelt saab korraga lugeda 1 sümboli. See kirjutatakse ka üle kas siis selle sama v mõne muu sümboliga. Liikuda saab igal taktil kas 1 koht paremale, vasakule või jääda paigale. Kogu aeg on masinal mingi olek. Üks neist on lähteolek, lõppolekuid võib olla 0…n. Üleminekufunktisoon on nagu käsk: qa→rbD. Kui oled olekus q ja loed lindilt a, siis lähed olekusse r,
-1 f :B A on siis samuti bijektsioon (kontrolli seda!); 3. Kui A B B C , siis leiduvad bijektsioonid f : A B ja ja g :B C . Nende kompositsioon g · f : A C on siis samuti bijektsioon. Definitsioon Hulka X nimetatakse loenduvaks, kui leidub bijektsioon hulga X ja naturaalarvude hulga N vahel. Märksus. · Loenduvad hulgad on lõpmatud hulgad · Leidub lõpmatuid hulki, mis ei ole loenduvad. Näide: · Z on loenduv · Q on loenduv · R ei ole loenduv! · (0, 1) ei ole loenduv! David Hilbert (18621943) tutvustas 1924. aastal ühes oma loengus järgmist lõpmatust illustreerivat näidet. Näide: Oletame, et meil on üks hotell, milles on loenduv arv tubasid ja selle hotelli igas toas on üks inimene. · Kas hotelli mahub veel üks külaline? · Kas hotelli mahub veel lõplik arv külalisi?
Hulk on lõplik, kui ta sisaldab kindla arvu elemente. 19. Millist hulka nimetatakse lõpmatuks hulgaks? Lõpmatu hulk sisaldab lõpmatult palju elemente. 20. Millist hulka nimetatakse loenduvaks hulgaks? Hulk on loendub, kui tema elementidele saab vastavusse seada naturaalarve {0,1,2,3,...}. 21. Mis on „loendamine“? Hulga elementidele naturaalarvude omistamine. 22. Tuua näide lõpmatust loenduvast hulgas ja lõpmatust mitteloenduvast hulgast. Lõpmatud loenduvad hulgad on naturaalarvude hulk ja täisarvudehulk . Lõpmatu mitteloenduv hulk on reaalarvude hulk . 23. Millised hulgaaritmeetilised tehted on olemas? Millised on nende tehtemärgid? Hulga täiend ¯ Hulkade ühend ∪ Hulkade ühisosa ∩ Hulkade vahe Hulkade sümmeetriline vahe 24. Millised on unaarsed ja millised on binaarsed hulgaaritmeetilised tehted? Unaarne rakendul ühele hulgale – hulga täiend.
u g ä o r s h w x v t KOLME HULGA Venni diagramm TÜHI HULK: lõpmatud ja loenduvad hulgad. Hulgas võivad elemendid ka täielikult puududa: { } Reaalarvude hulk R on lõpmatu ja mitteloenduv. Elementideta hulka nimetatakse tühjaks. Tühja hulka tähistatakse ka ∅ ( Diskreetne Matemaatika ei tegele reaalarvudega ) ehk: ∅ ={ } HULGAARITMEETILISED TEHTED
Levinuim meetod kriitiliste piirkondade kaitsmiseks on semafor mälupiirkond, mis toimib kriitiliste ressursside kaitse lukuna. S semafor, kaks funktsiooni wait ehk P(S) proberen "to test," ja signal ehk V(S) - verhogen ("increase"). Kriitilisse regiooni sisenedes funktsioon P(S) ja väljudes V(S). 28. Kirjutada vabalt valitud programmeerimiskeeles näidisprogramm (fragmendid) mingi süsteemi ressursi kaitsmiseks kasutades semafori. Selgitada selle programmi tööd. ??? 29. Mis on loenduvad semaforid, milleks neid kasutatakse? Vabade ressursside üle arvepidamiseks rohkem kui üks,wait MP(S) ja signal - MV(S), saab kujutada funktsioonidega, semafor S tuleb eelnevalt initsialiseerida ressursside hulgaga: 30. Mis on ummik (deadlock)? · Kaks või enam tegumit võistlevad pöördumises kahe või enama järjestikku kasutatava ressursi poole võib tekkida ummik (Deadlock või deadly embrace). Näites järgmisel slaidil tegum A
annaabi.ee 
