Leidsid 33 sarnast õppematerjali, mis on seotud failiga "Graafid ja matemaatiline loogika eksamimaterjal". Need materjalid aitavad sul teemat sügavamalt mõista.
graaf, graafi, lemma, parajasti, muutujalgoritm, tipus, predikaat, lausearvutus, teoreem, disjunktsioonlgoritmi, naturaalarvu, tippe, servad, implikatsioon, tipud, servadehelat, puus, liitmise, graafiks, maatriks, tsükkel, tõeväärtus, konjunktsioonid, kordu, konjuktsioon, sammul, samaselt, normaalkuju, term, graafil, komponent, etappi, tipuga„Kas A või B, 1 aga mitte mõlemad“, näiteks „Ma külvan põllule rukist või panen põllule kartulid“. Disjunktsiooni all mõistame mittevälistavat „võid“. o Implikatsioon (märk →) väljendab tingimuslikku konstruktsiooni „kui . . . , siis . . . “. Näiteks „Kui Sven terve aasta korralikult õpib, siis suudab ta kevadel eksamid hõlpsasti ära teha“ või „Kui kehtib teoreem P, siis kehtib teoreem Q“. Mõlemad laused võib kirja panna valemiga A → B. o Ekvivalents (märk ↔) tähendab matemaatikas sagedasti kasutatavat seost „parajasti siis, kui“ ehk „siis ja ainult siis, kui“. Näiteks lause „hulk X on kinnine parajasti siis, kui X ühtib oma sulundiga“ on valemkujul A ↔ B. Tehete järjekord o ¬, &, ∨, →, ↔ o vasakassotsiatiivsus: kui mitme liikme konjuktsioonis või
b. Konjunktsioon (märk &) tähendab seost ,,ja". c. Disjunktsioon (märk ) väljendab seost ,,või". Siin on kasutusel mittevälistav ,,või". d. Implikatsioon (märk ) väljendab tingimuslikku konstruktsiooni ,,kui ..., siis ...". e. Ekvivalents (märk ) tähendab matemaatikas sagedasti kasutatavat seost ,,parajasti siis, kui". f. Tehete järjekord kõrgemast madalamani ¬, &, , , . g. Def. Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil. g.i. Iga lausemuutuja on lausearvutuse valem. g.ii. Kui on lausearvutuse valem, siis ka ¬ on lausearvutuse valem. g.iii. Kui ja on lausearvutuse valemid, siis ka ( & ), ( ), ( ) ja ( ) on lausearvutuse valemid. 3) a. Kui vaatluse all on korraga hulk lausemuutujaid ja me omistame tõeväärtuse
Lucas` arvud. [18]. Catalani arvud. [19]. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus. [20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis. [21]. Täistõenäosuse valem. Bayesi reegel. [22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral). [23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid. [33]. Puud. Puude omadused. [34]. Graafi vähima kaaluga aluspuud. [35]. Märgendatud puud. Puude esitamine arvuti mälus. [36]. Prüferi kood
Lausearvutus: Diskreetne matemaatika ei tegele pidevate funktsioonidega. Diskreetne mate ei tegele reaalarvudega. Verbaalne esitus on lingvistilise keele kasutamine info edastamiseks. Formaalne esitus on ilma lingivtilise keele kasutamise info edastamine, peamiselt sümbolite abil. Formaalne esitus peab olema üheselt mõistetav. Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause on lause, millele saab omistada tõeväärtust(0,1). Tõeväärtuseid on kaks, 0-väär, 1-tõene. Lihtlause on lihtsaim lausearvutuse lause. Lausearvutuse lauseid tähistatakse suutre tähtedega A, B, C. Liitlause koosneb lihtlausetest ning neid siduvatest konstruktisoonidest ja sidesõnadest. Lausearvutuse loogikatehted on inversioon, konjunktsioon, disjunktsioon,
Lausearvutus Disjunktsioon: liitlause on tõene, kui vähemalt üks osalause on tõene Ekvivalents: liitlause on tõene, kui osalaused on sarnased Implikatsioon: liitlause on tõene, kui esimene muutuja on väär või teine muutuja on tõene Inversioon: eitus Ja-tehe: konjunktsioon Konjunktsioon: liitlause on tõene, kui mõlemad osalaused on tõesed Lause: iga lause, mille puhul saab rääkida tema vastavusest tegelikkusele (millel on tõeväärtus) Olemasolu kvantor: näitab, et predikaat kehtib oma määramispiirkonna vähemalt ühe muutujate puhul Predikaat: lause, mis sisaldab ühte või enamat muutujat Samaselt tõene predikaat: predikaat, mis kehtib kogu määramispiirkonnas Samaselt väär predikaat: predikaat, mis ei kehti kusagil määramispiirkonnas Tautoloogia: samaselt tõene lause Täidetav predikaat: predikaat, mis on tõene osas oma määramispiirkonnas Üldsuse kvantor: näitab, et predikaat kehtib oma määramispiirkonna kõigi muutujate puhul
elementi vastavusse seadnud. Nendeks on 0 ja 10. Nüüd hakkan juhindudes tabelist(alustan paremalt) lisama puule uusi tippe(ülemine rida) ja ühendama neid vastava alumisest reast ehk koodist pärit tipuga. Ehk esimesena lisan puule tipu 1 ning ühendan selle tipuga 0. Seejärel lisan tipu 9 ja ühendan selle tipuga 1. Ülejäänud tippudega käitun analoogiliselt. Tulemuseks saan järgmise puu: Vastus: ÜLESANNE 3. Võrdlen alguses mõlema graafi kõigi tippude astmeid. Märgin ära iga tipu astme. Diskreetne matemaatika II Kodused ülesanded 5 Olga Dalton 104493 IAPB21 Nii parem- kui vasakpoolsel graafil on olemas 2 tippu, mille aste on 3, ja 4 tippu, mille aste on 2.
Relatsiooni transitiivne sulund: R on seos hulgal A. R transitiivne sulund on seos R + hulgal A nii, et aR+b kehtib parajasti siis, kui eksisteerib i >= 1 nii, et aRib. Transitiivne sulund on R-le lisatud vähima paaride arvuga seos, mis on transitiivne. Relatsiooni refleksiivne transitiivne sulund: R on seos hulgal A. R refleksiivne transitiivne sulund on seos R *, mille korral: · iga a puhul aR*a · aR*b kehtib, kui kehtib aR+b · R* sisaldab parajasti nii palju elemente, kui eelmised tingimused ette näevad * R on seos, mis on saadud R-le minimaalse arvu paaride lisamisel nii, et saaksime refleksiivse ja transitiivse seose. Järjestusseosed: · osalise järjestuse seos (kõigile saab leida ülem- ja alamelemendid, kuid kõik pole järjestusse seatud): o transitiivne o irrefkeksiivne (näiteks alamhulgaks olemise seos kõigi osahulkade hulgal) · refleksiivne osaline järjestus (seos R)
Graafid Graaf koosneb tippudest(sõlmedest) ja neid ühendavatest kaartest. Kaarega võib ühendada suvalisi graafi tippe, sealhulgas on võimalik kaar samale tipule (iseendale). Iga kaar on määratud kahe tipuga. Orienteeritud graaf: kaared on järjestatud tipupaarid. Def: Graaf on paar (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad. Näide lk 47 (Palm) Tipu aste tipust väljuvate servade arv. Teoreem: Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. Järeldus: Igas graafis on paaritu astemga tippe paarisarv. Ahel graafis tippude järjend, kus iga kaks järjestikust tippu on servaga ühendatud (esimene ja viimane on otstipud vahepeal sisetipud).
raske tõestada. 2.2.2 Tugevad küljed: • Paljudel juhtudel on teda kergem koostada • Töötab kiiremini kui DP algoritm Optimiseerimise juures on vajalikud teatud tingimused: 1. Kandidaatide hulk (graafi tipud, teede pikkused, rahatähtede suurused...) 2. Valitute hulk, mis või kes on juba kasutatud (sobivaks tunnistatud, tagasi antud rahatähed, läbitud graafi tipud...) 3. Eeldatav lahendus, otsitav summa vms, mille järgi saab otsustada, kas välja valitud kandidaadid moodustavad lahendused (ei pruugi olla optimaalne) 4. Jätkamise näitaja, mille järgi saab otsustada, kas kandidaatide hulka saab suurendada, et lahendust leida. 5. Valikufunktsioon, mille abil valitakse uusi kandidaate väljavalitute hulka 6. Vastusefunktsioon, mis annab lõpliku väärtuse lahendusele 2.2.3 Näide kasutamisest:
LAUSEARVUTUS Diskreetne matemaatika ei tegele reaalarvudega ega pidevate funktsioonidega. Verbaalne esitus on mistahes info esitamine lingvistilise keele abil. Formaalne esitus on mistahes info esitamine ilma lingvistilise keele abita ehk esitus kokkulepitud sümbolite abil. Formaalne esitus peab olema üheselt tõlgendatav. Lausearvutus on loogilise mõtlemise matemaatiline mudel. Lausearvutuse lause võib olla iga verbaalne väide, millele saame omistada tõeväärtuse – tõene või vale. Lihtlause on lihtsaim võimalik lausearvutuslause. Lausearvutuslauseid tähistatakse formaalselt suurtähtedega: A, B, P, Q … Lihtlausetest koostatakse kindlate sidesõnade ja loog konstruktsioonide abil liitlauseid. Lausearvutuse lihtlauseid seotakse liitlauseteks 5 loogilise konstruktsiooni ehk loogikatehte abil.
ÜLESANNE 1. $ - 2 0 (J 11) Toon x-i sulgude ette. ( - 2) 0 (J 11) Siit järeldub, et kas 11É või 11É( - 2), sest vastasel juhul ei saaks jäägiks 0-i. Seega on võrrandil kaks lahendit: # 0 (J 11) ja $ 2 (J 11), sest jäägi null annab - 2, seega peab $ ise andma jäägiks 2-e. Vastus: # 0 (J 11); $ 2 (J 11) ÜLESANNE 2. 25 + 41 = 1 Täisarvuliste kordajatega võrrandil I + I = I leiduvad täisarvulised lahendid parajasti siis, kui gcd(I, I)ÉI. Seega leian alguses kordajad u ja v nii, et 25 + 41 = gcd(25,41) Kasutan selleks Eukleidese algoritmi. gcd(25,41) = gcd(16,25) = gcd(9,16) = gcd(7,9) = gcd(2,7) = gcd(1,2) = 1 Kirjutan välja, kuidas jäägiga jagamine täpselt toimub. 41 = 25 1 + 16 16 = 41 - 25 1 25 = 16 1 + 9 9 = 25 - 16 1 = 25 - (41 - 25 1) = 25 - 41 + 25 1 = 2 25 - 41 16 = 9 1 + 7 7 = 16 - 9 1 = 41 - 25 1 - 2 25 + 41 = 2 41 - 3 25
Topeltseotud ahela iga element sisaldab viita nii eelmisele kui ka järgmisele elemendile. Tõene That is what "doubly linked" means Right parenthetic expression becomes Reverse Polish Notation after removing parentheses and commas. Avaldise pööratud poola kuju (RPN) saadakse parempoolsest suluesitusest sulgude ja komade ärajätmise teel. Tõene Full graph is a simple graph. Iga täisgraaf on lihtgraaf. Tõene Each weakly connected digraph is strongly connected. Iga nõrgalt sidus graaf on tugevalt sidus. Väär If there is a cycle in a graph it is impossible to find the topological order of vertices. Kui graafis esineb tsükkel, siis ei saa graafi tippe topoloogiliselt järjestada. Tõene It is possible to convert recursion to loops using stack. Rekursiooni saab magasini abil teisendada tsükliteks. Tõene Exhaustive search algorithms tend to have exponential time complexity. Ammendava otsingu algoritmid on üldjuhul eksponentsiaalse ajalise keerukusega. Tõene
Postorder – läbida vasak alampuu, läbida parem alampuu, väljastada (töödelda) juur. Inorder – läbida vasak alampuu, väljastada (töödelda) juur, läbida parem alampuu. Puu realiseerimine arvutis – Eelistatud on dünaamiline realisatsioon, kuna see ei nõua esialgu suur mälumahtu & on loomulikum. Sõlmes on kaks viidavälja (rlink, llink) ja võtmeväli (key). Puu koosneb ühest viidast juurele (root). Tühja viida tähis (none). 9. Graaf. Suunatud ja suunamata graaf. Atsükliline graaf. Kaalutud graaf. Graafi realiseerimine arvutis. Topoloogiline sorteerimine. Sügavuti otsimine. Laiuti otsimine (+ lühim tee). Lühim tee kaalutud graafis (Dijkstra algoritm). Graaf – tippude ja servade hulk, servad ühendavad omavahel konkreetseid tippe. Suunatud graaf – iga kaare jaoks on määratud, millisest tipust algab ja millises lõpeb, tähistatakse noolega kaare otsas. Seosel on suund
1 0 0 1 0 1 1 1 0 0 1 0 G= 0 1 1 0 0 1 H= 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 Lahendus. Joonistades välja graafide täiendid, leiame, et graafi G täiend on tsükkel tippudega 1, 4, 5, 3, 2, 6 ning graafi H täiend on tsükkel tippudega 1, 2, 5, 4, 3, 6. Et kaks sama tippude arvuga tsüklit on isomorfsed, siis on ka graafid G ja H isomorfsed. Üks isomorfism on näiteks bijektsioon , mis teisendab graafi G tipud graafi H tippudeks järgmisel viisil: (1) = 1, (2) = 3, (3) = 4, (4) = 2, (5) = 5, (6) = 6. Materjal õpikus. Lk 5759 (graafide isomorfism). Lk 62, ülesanded 3741. Ülesanne 4
Kuidas teda tähistatakse? 28. Mitu täiendit saab olla tõkestatud distributiivse võre igal elemendil? 29. Milline võre on täienditega võre? 30. Milline võre on Boole’i algebra? Tuua näiteid Hasse diagrammidena? Boole’i algebrad on tõkestatud, distributiivsed ja täienditega võred. 31. Milliseid osalise järjestussuhte elemente nimetatakse aatomiteks?` 32. Kuidas on Boole’i algebras tema kõik elemendid aatomite kaudu esitatavad? Graafid 1. Mis on graaf? Millest graaf koosneb? Graaf on objektidevaheliste seoste joonismudel. Graaf koosneb kahte tüüpi elementidest: tippudest ja neid ühendavatest kaartest. 2. Mille poolest erinevad orienteeritud graaf ja orienteerimata graaf? Orienteeritud graafi kõik kaared on suunatud ja neid esitatakse graafi joonisel nooltega, orienteerimata graafi kõik kaared on suunamata ja neid esitatakse graafi joonisel kahte tippu ühendava lihtsa joonega. 3. Mis on tühi graaf? Mis on täielik graaf (täisgraaf)
= 0,1,2,... korral. T: Olgu L = L (M ), kus M = (Q , Σ, δ , Q0 , F ) ja Q = {q0 ,1 , . . . , qn }. Valime p = n. Siis sõne z = a1a2...an+1 aktsepteerimiseks peab automaat M tegema n+1 sammu. Järelikult vähemalt 1 olek peab korduma. Järelikult uw ∈ L(M), uvw ∈ L(M), uv2w ∈ L(M) jne. Keel L = {0n1n|n > 0} pole regulaarne. Sellise keele jaoks on vaja mälu. 6 Myhill-Nerode teoreem. DEF: Olgu keele L ⊆ Σ* (keel on kõigi sõnede hulga alamhulk) jaoks antud ekvivalentsiseos HL ⊆ Σ* × Σ* selline, et xHLy kehtib parajasti siis, kui iga z ∈ Σ* korral kehtib xz ∈ L yz ∈ L (iga suvalise z lisamisel x ja y sappa, kuuluvad saadud xz ja yz mõlemad keelde L või ei kuulu mõlemad). Teoreem: Keel L on regulaarne parajasti siis, kui seose HL ekvivalentsiklasside hulk on lõplik.
SISSEJUHATUS MATEMAATILISSE LOOGIKASSE Kordamisküsimused (orienteeruv) Mõnede sümbolite tähendused sõna Materjal puudub & Konjuktsioon Ekvivalents üldisuskvantor Järeldumine Disjunktisoon ¬ Eitus olemasolukvantor Signatuur Implikatsioon Samaväärsus Loogiline järeldumine I. Lausearvutus Laused. Lausearvutuse tehted. Valem. Valemi tõeväärtus. Tõeväärtustabel. Laused Põhilised uuritavad objektid lausearvutuses on laused, mis võimaldavad pärineda ükskõik millisest valdkonnast. Oluline on, et igale lausearvutusele saaks vastavusse seada tõeväärtuse, mis kirjeldab lause tegelikkusele vastava määra. Eeldame, et käsitlevad laused rahuldavad järgmisi tingimusi: · Välistatud kolmanda seadus
ehk sümbolites: Kui A, siis B Kui ¬B, siis ¬A. Öeldakse ka, et need laused on loogiliselt samaväärsed. Näide1: Lause: ,,Kui nelinurk on rööpkülik, siis tema diagonaalid poolitavad teineteist." Pöördvastandlause: ,,Kui nelinurga diagonaalid ei poolita teineteist, siis nelinurk ei ole rööpkülik." Kehtigu teoreem: Kui A, siis B. Sel juhul öeldakse, et A on piisav tingimus selleks, et kehtiks B. Samuti öeldakse, et B on tarvilik tingimus selleks, et kehtiks A. Näide: Lause: Kui tuleb riiklik toetus, siis saame ürituse läbi viia. Riiklik toetus on piisav selleks, et üritust läbi viia. Ürituse läbiviimiseks on tarvilik, et oleks riiklik toetus. Kui koos teoreemiga (Kui A, siis B) kehtib ka pöördteoreem (Kui B, siis A), siis võetakse
Tingimused 1. Välistatud kolmanda seadus. Iga lause on kas tõene või väär. 2. Mittevasturääkivuse seadus. Ükski lause pole korraga tõene ja väär. Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite järgi: 1. Iga lausemuutuja on lausearvutuse valem. 2. Kui F on lausearvutuse valem, siis ka F on lausearvutuse valem. 3. Kui F ja G on lausearvutuse valemid, siis ka (F&G), (FVG),(F->G) ja (F<->G) on lausearvutuse valemid. Osavalem : Kõiki antud valemi konstrueerimise käigus tekkinud valemeid nimetatakse selle valemi osavalemiteks ehk alamvalemiteks, konstrueerimise viimasel sammul kasutatud suhet aga peatehteks.
Tõestamise teooria. Loogika seadused. Vastandab tegelikult oleva ja kindla teadmise sofistidele. Induktsioon. Sokrates (470-399). Induktsioon ja üldiste tunnuste leidmine üksikutes mõistetes. Platon (427-347). Väitluskunsti ülesanne on vastuolude avastamine. ARISTOTELES (384-322) Loogika on tööriist kõikide teaduste jaoks. Võttis kasutusele muutujad, väite komponendid (1) kvantor, (2) subjekt, (3) koopula, (4) eitus, (5) predikaat. Süllogismid. Modaalsed väited. Stoikud: Zenon Kitionist (333-264) ja eriti Chrysippos (279-206). Lausearvutuse elemendid. Keskajal Boethius (480-525). Aristoteles ladina keelde. Skolastikud panevad aluse ka analüütilisele filosoofiale. Raimon Lull (1235-1315) Võtab kasutusele sümbolid. G. W. Leibnitz (1646-1716). Idee luua universaalne sümbolkeel, mida võib kontrolloda ka masinaga. Tegi palju matematilise loogika jaoks, kuid ei avaldanud. G. Boole (1815-64) Lausearvutus
1. Sissejuhatus: 1.1. Mis on loogiline programmeerimine? l Programmeerimise paradigma l loogiline (LP) l funktsionaalne (FP) l jt Fookus: MIDA ARVUTADA l LP ja FP on deklaratiivsed programmeerimisstiilid; l LP põhineb loogika printsiipidel ja kasutab automaattõestamise protseduure (resolutsioon, unifitseerimine); l LP keel on Prolog, kuid LP ≠ Prolog; 1.1. Mis on loogiline programmeerimine? (2) l LP sobib tehisintellekti rakenduste programmeerimiseks: l loomuliku keele analüüs ( DCG grammatikareeglid) l ekspertsüsteemid (otsingu- ja järeldusreeglid) l kujundituvastus (tuvastusreeglid) l kitsendustega planeerimine (logistika, marsruudi otsimine) l rekursiivsete funktsioonide püsipunkti arvutus l jne l LP ei sobi: l Kiired numbrilised arvutused (n. maatriksarvutused, võrrandid) l OOP (kuigi on toetatud mõnes prologis) l kasutajaliideste programmeerimine (tugi on
Ajalooliselt oli esimene loogika Aristotelese loogika, mis arenes edasi nn traditsiooniliseks loogikaks. Traditsiooniline loogika koosneb peamiselt aristotellikust süllogistikast ning sellega seotud väite- ja mõisteõpetusest. Traditsiooniline loogika on tänapäeval taandunud lausearvutuse ja predikaatarvutuse ees, mis on arvutuslikult võimsamad kui traditsiooniline loogika. Klassikaline loogika on lausearvutus ja predikaatarvutus. Mõneti lihtsustatult võib öelda, et traditsiooniline loogika on mõisteloogika ja klassikaline loogika on predikaatarvutus ehk predikaatloogika, kuna lausearvutus on esitatav predikaatarvutuse osana. Klassikalises loogikas on väljend lause sama tähendusega, mis propositsioon (väitlause sisu, mis pole seotud konkreetse keele või ütlemisviisiga). Klassikalises loogikas järgitakse loogika kolme esimest
eeskujul saab loogikat jaotada traditsiooniliseks, klassikaliseks ja mitteklassikaliseks.Ajalooliselt oli esimene loogika Aristotelese loogika, mis arenes edasi nn traditsiooniliseks loogikaks. Traditsiooniline loogika koosneb peamiselt aristotellikust süllogistikast ning sellega seotud väite- ja mõisteõpetusest. Traditsiooniline loogika on tänapäeval taandunud lausearvutuse ja predikaatarvutuse ees, mis on arvutuslikult võimsamad kui traditsiooniline loogika. Klassikaline loogika on lausearvutus ja predikaatarvutus. Mõneti lihtsustatult võib öelda, et traditsiooniline loogika on mõisteloogika ja klassikaline loogika on predikaatarvutus ehk predikaatloogika, kuna lausearvutus on esitatav predikaatarvutuse osana. Klassikalises loogikas on väljend lause sama tähendusega, mis propositsioon (väitlause sisu, mis pole seotud konkreetse keele või ütlemisviisiga). Klassikalises loogikas järgitakse loogika kolme esimest
. . . . . . . . . . . . 33 2.1.4 Tähtsad piirväärtused . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Koonduvuseteooria neli printsiipi . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.1 Monotoonsuseprintsiip . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.2 Bolzano–Weierstrassi teoreem . . . . . . . . . . . . . . . . . . . . . . 36 2.2.3 Cauchy kriteerium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.4 Cantori teoreem üksteisesse sisestatud lõikudest . . . . . . . . . . . . 38 2.2.5 Reaalarvu kümnendesitus . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.6 Arv e . . . . . . . . . . . . . . . . . . . .
Ü les anne: A ntud on hulgad A= { 1,2,3,4} j a B= A .D efineerida relats ioon aRb nii et a< = b,leida s elle relats iooni mä äramis p iirkond j a muutu mi s piirkond. R = { (a,b): a< = b} R = { (1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} D om (R )= A R ange (R )= A 2. Relatsiooni esitamine (R.Palm järgi) R elats iooni võib es itada paaride loendina nagu ees pool, eriti j uhul kui paare on vähe. Teine võima lus relats ioonide es itamis eks on suunatud graaf. K as utame hulga A j a hulga B ele ment e gaafi tippudena (punktid joonis el) ja tõmb ame kaare punktis t a A punktini b B juhul kui paar (a,b) kuulub vas tavas s e relats iooni. Tule mus ena s aame graafi kus kaared viivad hulgas t A hulka B j a hulkade s ee s kaari pole N äiteks olgu hulk tähes tik A= { a,b} j a hulk B kõigi kahetähelis t e s õnade hulk, mida s aab hulga A tähtedes t koos tada B= { aa,ab,ba,bb} . Loe me, et hulga A täht j a hulga
Ü les anne: A ntud on hulgad A= { 1,2,3,4} j a B= A .D efineerida relats ioon aRb nii et a< = b,leida s elle relats iooni mä äramis p iirkond j a muutu mi s piirkond. R = { (a,b): a< = b} R = { (1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} D om (R )= A R ange (R )= A 2. Relatsiooni esitamine (R.Palm järgi) R elats iooni võib es itada paaride loendina nagu ees pool, eriti j uhul kui paare on vähe. Teine võima lus relats ioonide es itamis eks on suunatud graaf. K as utame hulga A j a hulga B ele ment e gaafi tippudena (punktid joonis el) ja tõmb ame kaare punktis t a A punktini b B juhul kui paar (a,b) kuulub vas tavas s e relats iooni. Tule mus ena s aame graafi kus kaared viivad hulgas t A hulka B j a hulkade s ee s kaari pole N äiteks olgu hulk tähes tik A= { a,b} j a hulk B kõigi kahetähelis t e s õnade hulk, mida s aab hulga A tähtedes t koos tada B= { aa,ab,ba,bb} . Loe me, et hulga A täht j a hulga
mille esimeseks reaks on omakorda substitutsioon j1 , j2 , ... , jn . Kui paar ik , il ( k < l ) moodustab inversiooni substitutsioonis i1 , i2 , ... , in , siis ik > il ja seetõttu paar l, k moodustab inversiooni substitutsioonis j1 , j2 , ... , jn . Nii tekib üksühene vastavus substitutsioonide i1 , i2 , ... , in ja j1 , j2 , ... , jn inversioone moodustavate paaride vahel. Seega kehtib Lemma 1. Kui i1 , i2 , ... , in on n-ndat järku substitutsioon ja substitutsioon j1 , j2 , ... , jn on saadud substitutsioonist i1 , i2 , ... , in äsja kirjeldatud viisil, siis ( i1 , i2 , ... , in ) = ( j1 , j2 , ... , jn ) . Näide 4. Vaatleme näites 2 esinevat neljandat järku substitutsiooni 4, 1, 3, 2. Siin 1 2 3 4 ^ 2 4 3 1
6.2 Hausdorffi ruumi omadusi . . . . . . . . . . . . . . . . . . . . . . . .64 ¨ 6.3 Ulesandeid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66 7 KOMPAKTSUS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.1 Kompaktsuse definitsioon ja lihtsamaid j¨areldusi . 68 7.2 Kompaktsus loenduva baasiga ruumides . . . . . . . . . .72 7.3 Kompaktsus meetrilistes ruumides . . . . . . . . . . . . . . . 76 7.4 Heine-Boreli teoreem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .79 7.5 Kompaktsus ja pidevad kujutused . . . . . . . . . . . . . . . .83 ¨ 7.6 Ulesandeid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84 8 SIDUSUS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.1 Sidusus ja tema komponendid . . . . . . . . . . . . . . . . . . . .85 8.2 Sidusad hulgad arvteljel . . . . . . . . . . . . . . . . . . . . . . . .
Formaalsete esituste ainus otstarve on nendes sisalduv info hiljem jälle verbaalseks (ehk mõnda lingvistilisse keelde) tagasi "üles lugeda" — Hulgad: Hulgaalgebra (Cantori algebra), Hulgaaritmeetika (taastada). — Loogika: Lausearvutus, Predikaatarvutus, Tõestusmeetodid Mistahes formaalne esitus peab olema üheselt tõlgendatav! — Loogikaalgebra (Boole'i algebra) — Loogikafunktsioonid: minimeerimine, normaalkujud . . . — Algebralised struktuurid: "mitteformaalne" ≡ "verbaalne" (sünonüümid) Fundamentaalalgebrad: Võred, Rühmad, Ringid, Korpused
1290 sisestada ruutjuure alune arv arvutisse, Leida arvutil ruutjuur, ümardada vajutada klahvile "ruutjuur"; vajadusel sajandikeni. ümardada; arv on väiksem kui 1: ruutjuur =9.542012366 9,54 antakse standardkujul, näiteks 6.1646 -01, s.t. et koma tuleb nihutada ühe koha võrra =99.994999875 99,99 vasakule 0,61646, ümardades vastuse näiteks sajandikeni 0,62 NB ruutjuure saab leida ka vastava matemaatilise tabeli abil 7.Korrutise ruutjuur - TEOREEM. Näited. Mittenegatiivsete arvude korrutise ruutjuur võrdub tegurite ruutjuurte korrutisega. NB ühest ruutjuurest võib saada kahe (mitme) ruutjuure korrutise või vastupidi 8.Jagatise ruutjuur - TEOREEM. Ül.1304, 1306 Mittenega-tiivse arvu ja positiivse arvu jagatise ruutjuur võrdub jagatava = = ruutjuure ning jagaja ruutjuure jagatisega. = = =
() (). Seega, () = () () = () (). (f)= =1 . Riemanni integraal () eksisteerib parajasti siis, kui lim () + lim () + lim (( ) - ()) = () +
funktsiooni x = f −1 (y ) , mis igale arvule y ∈ Y = f (X ) seab vastavusse arvu x ∈ X , Osajadad. Bolzano-Wierstrassi)Monotoonseks jadaks nimetatakse jada, mis on kogu kusjuures y = f (x). ulatuses mittekasvav või mittekahanev. *Monotoonseks nimetatakse funktsiooni, mis kogu oma määramispiirkonnas on *Bolzano- Weierstrassi teoreem: Igast tõkestatud jadast saab eraldada koonduva mittekasvav või mittekahanev. osajada. *Rangelt monotoonseks nimetatakse funktsiooni, mis kogu oma määramispiirkonnas *Jada {Xn} osajadaks {Yn} nim. jada, mis on saadud jadast {Xn} lõpliku või lõpmatu on kasvav või kahanev
muudu avaldises domineerima. Seetõttu võime lugeda diferentsiaali dy funktsiooni muudu peaosaks. jääkliikme võib väikese x korral funktsiooni muudu avaldises ära jätta. Kehtib ligikaudne valem y dy kui x 0 . Diferentsiaali omadused. 1. d(u + v) = du + dv, 2. d(u - v) = du - dv, 3. d(uv) = vdu + udv, 4. d(Cu) = Cdu , C - konstant, 5. d() = kui v 0. 24. Funktsiooni lokaalsete ekstreemumite definitsioonid. Sõnastada ja tõestada Fermat' lemma. Öeldakse, et funktsioonil f on punktis x1 lokaalne maksimum, kui 1. funktsioon f on määratud punkti x1 mingis ümbruses (x1 - , x1 + ); 2. iga x (x1 - , x1 + ) korral kehtib võrratus f(x) f(x1). Öeldakse, et funktsioonil f on punktis x1 lokaalne miinimum, kui 1. funktsioon f on määratud punkti x1 mingis ümbruses (x1 - , x1 + ); 2. iga x (x1 - , x1 + ) korral kehtib võrratus f(x) f(x1). Funktsiooni lokaalseid maksimume ja miinimume nimetatakse selle funktsiooni
annaabi.ee 
