Def. Olgu f ja g naturaalarvuliste argumentidega ja positiivsete väärtustega
funktsioonid. Siis f on O(g(n)) parajasti siis kui leidub c>0 ja N>0 nii, et
f(n)
M(x) = ∞ - masin ei peatu x korral kunagi või peatub jõudmata lõppkonfiguratsiooni Aktsepteeriv Turingi masin on selline, millel on aktsepteeriv lõppolek qa ja tagasilükkav qr. Karakteristlik aktsepteeriv TM on selline, mis aktsepteerib, kui x kuulub keelde. Muul juhul lükkab tagasi. Genereeriv aktsepteeriv TM on selline, mis aktsepteerib, kui x kuulub keelde. Muul juhul ei peatu. DEF: Hulka (keelt), millel leidub karakteristlik Turingi masin, nimetatakse lahenduvaks ehk rekursiivseks. DEF: Hulka (keelt), millel leidub genereeriv Turingi masin, nimetatakse rekursiivselt loenduvaks ehk genereeritavaks. Lemma: Iga lahenduv hulk on rekursiivselt loenduv. T: Igal lahenduva hulga karakteristlikku masinat saab tesendada nii, et ta jääks olekusse qr jõudmise asemel tsüklisse ehk muutuks genereerivaks masinaks. Registermasin sisaldab registreid R1… (sisuks naturaalarv) ja märgendeid N1… Operaatorid on INC (+1),
Kui astmelisele kujule
viidud laiendatud maatriksis leidub rida, kus ainsaks nullist erinevaks elemendiks on vabaliige,
siis on süsteem vastuoluline. Kui sellist rida ei ole, on süsteem lahenduv. Kui lahenduvas
süsteemis on n tundmatut ja astmelisele kujule viidud maatriksis on k juhtelementi siis juhul
n=k on süsteemil ainult üks lahend, juhul k
samasuseks kõik võrrandid süsteemis (1) või maatriksvõrrandi (2), nimetatakse LINEAARSE VÕRRANDISÜSTEEMI LAHENDIKS. MÄRKUS. Süsteemi lahend ei tarvitse olla üheselt määratud ja võib sõltuda teatud arvust parameetritest. Selliseid lahendeid nimetatakse SÜSTEEMI ÜLDLAHENDITEKS. Lahendeid, mis saadakse üldlahendist parameetrite fikseerimise teel, nimetatakse SÜSTEEMI ERILAHEN- DITEKS. DEFINITSIOON 4. Kui süsteemil on lahend olemas, siis nimetatakse süsteemi LAHENDUVAKS, vastasel korral aga MITTELAHENDUVAKS ehk vastuoluliseks. 16 DEFINITSIOON 5. Lineaarseid võrrandisüsteeme, millel on samad lahendite hulgad, nimetatakse EKVIVALENTSETEKS. LINEAARSE VÕRRANDISÜSTEEMI LAHENDUVUSTINGIMUS KRONECKER-CAPELLI TEOREEM (1864). Lineaarne võrrandisüsteem on lahenduv parajasti siis, kui süsteemimaatriksi A astak on võrdne laiendatud maatriksi A|B astakuga, st rank A = rank A|B.
samasuseks kõik võrrandid süsteemis (1) või maatriksvõrrandi (2), nimetatakse LINEAARSE VÕRRANDISÜSTEEMI LAHENDIKS. MÄRKUS. Süsteemi lahend ei tarvitse olla üheselt määratud ja võib sõltuda teatud arvust parameetritest. Selliseid lahendeid nimetatakse SÜSTEEMI ÜLDLAHENDITEKS. Lahendeid, mis saadakse üldlahendist parameetrite fikseerimise teel, nimetatakse SÜSTEEMI ERILAHEN- DITEKS. DEFINITSIOON 4. Kui süsteemil on lahend olemas, siis nimetatakse süsteemi LAHENDUVAKS, vastasel korral aga MITTELAHENDUVAKS ehk vastuoluliseks. 16 DEFINITSIOON 5. Lineaarseid võrrandisüsteeme, millel on samad lahendite hulgad, nimetatakse EKVIVALENTSETEKS. LINEAARSE VÕRRANDISÜSTEEMI LAHENDUVUSTINGIMUS KRONECKER-CAPELLI TEOREEM (1864). Lineaarne võrrandisüsteem on lahenduv parajasti siis, kui süsteemimaatriksi A astak on võrdne laiendatud maatriksi A|B astakuga, st rank A = rank A|B.
erinevaks elemendiks on vabaliige, siis on süsteem vastuoluline. Kui sellist rida ei ole, on süsteem lahenduv. b) Kui lahenduvas süsteemis on n tundmatut ja astmelisele kujule viidud maatriksis on k juhtelementi siis juhul n = k on süsteemil ainult üks lahend, juhul k < n aga lõpmata palju lahendeid. Kolmandas etapis leitakse antud süsteemi lahendid, kui süsteem osutus lahenduvaks. Lahendite leidmiseks kirjutatakse välja esimeses etapis saadud teisendatud maatriksile vastav võrrandisüsteem. a) ühe lahendi korral leitakse tundmatute arvulised väärtused alustades alumisest reast ja liikudes rida realt ülespoole. b) Juhul k < n jäetakse igas võrrandis vasakule poole ridade juhtelementidele vastavad k tundmatut (nn sõltuvad tundmatud), ülejäänud r = n - k tundmatut (nn vabu tundmatuid) sisaldavad liidetavad
laiendatud maatriksiks. Võrrandisüsteemi (1) saame nüüd kirja panna ka maatrikskujul: LVS üldlahend fikseeritud reaalarvude komplekt x1 = 1 jne... LVS erilahend Fikseeritud reaalarvude komplekti x1 = 1, x2 = 2, . . . , xn = n nimetatakse lineaarvõrrandisüsteemi (1) lahendiks ehk erilahendiks, kui nende arvude asendamisel süsteemi (1) võrranditesse tundmatute asemele same samasused. Lahenduv LVS Lineaarvõrrandisüsteemi (1) nimetatakse lahenduvaks, kui tal leidub vähemalt üks lahend Vastuoluline LVS - Lineaarvõrrandisüsteemi (1) nimetatakse vastuoluliseks ehk vasturääkivaks, kui süsteemil (1) ei ole lahendeid. Elementaarteisendused: nim. 1) tema mistahes võrrandi korrutamist nullist erineva reaalarvuga 2) tema mingile võrrandile teise mistahes arvuga läbikorrutatud võrrandi liitmist Gaussi meetodi kirjeldus - Gaussi meetodi puhul kirjutatakse välja süsteemi laiendatud maatriks, mis koosneb
Kokkuvõtteks: loogika uurib selliseid formaalseid keeli, mille jaoks suudetakse kirja panna selles keeles kirjutatud õigete väidete tuletamise algoritm. Loogika poolt kasutatav keel käib alati paaris n.ö. mehaanilise mõtlemise mehhanismiga; keelest ja tuletamismehhanismist koosnevat paari nimetatakse teooriaks ehk arvutuseks. Arvutust, mille iga lause jaoks saab algoritmiselt lahendada, kas ta on tõene või väär, nimetatakse lahenduvaks (näide: lausearvutus), ülejäänuid nimetatakse mittelahenduvaks (näide: predikaatarvutus). 1.6 Lihtsatest väidetest ehitatakse keerulisi Meie näited olid siiamaani triviaalsed ja lugejal võib tekkida kahtlus, et kas selliste triviaalsuste uurimine saab öelda midagi olulist mõtlemise või üldse millegi kohta. Vastuseks ütleme, et loogika alustab teadlikult triviaalsustest, ning mida triviaalsematest, seda parem: nende õigsuse suhtes ei teki kellelgi mingeid kahtlusi
Kc & Vc (7., 9.; Conj) 11. ∃x (Kx & Vx) (10.; EG) N9.9. Kõik filosoofid on pikad või mittepikad. Kõik filosoofid on lühikesed või mittelühikesed. Seega on mõned pikad või mittepikad asjad lühikesed või mittelühikesed. Ülesanne pole lahenduv ei süllogistika reeglite järgi ega ka mitte Venni diagrammide abil.4 Lahenduseks fikseerime interpretatsiooni: Px – x on filosoof; Tx – x on pikk; Sx – x on lühike. 4 Hausman et al., 2010: 354. Eelduste vahetamine ei muuda süllogismi lahenduvaks. 12 Lisaks märgime, et a on indiviidikonstant, mille interpretatsioon on suvaline asi, st suvaline objekt universaalhulgast. 1. ∀x [Px → (Tx ∨ ￢Tx)] (e) 2. ∀x [Px → (Sx ∨ ￢Sx)] (e) ∴ ∃x [(Tx ∨ ￢Tx) & (Sx ∨ ￢Sx)] 3. │￢Ta (AP) 4. │￢Ta ∨ ￢Ta (3.; Add) 5. │￢Ta (4.; Taut) 6. ￢Ta → ￢Ta (3.–5.; CP) 7. Ta ∨ ￢Ta (6.; CE, DN) 8. │￢Sa (AP) 9. │￢Sa ∨ ￢Sa (8.; Add) 10. │￢Sa (9.; Taut) 11. ￢Sa → ￢Sa (8.–10.; CP) 12
11. x (Kx & Vx) (10.; EG) N9.9. Kõik filosoofid on pikad või mittepikad. Kõik filosoofid on lühikesed või mittelühikesed. Seega on mõned pikad või mittepikad asjad lühikesed või mittelühikesed. Ülesanne pole lahenduv ei süllogistika reeglite järgi ega ka mitte Venni diagrammide abil.4 Lahenduseks fikseerime interpretatsiooni: Px x on filosoof; Tx x on pikk; Sx x on lühike. 4 Hausman et al., 2010: 354. Eelduste vahetamine ei muuda süllogismi lahenduvaks. 12 Lisaks märgime, et a on indiviidikonstant, mille interpretatsioon on suvaline asi, st suvaline objekt universaalhulgast. 1. x [Px (Tx ¬Tx)] (e) 2. x [Px (Sx ¬Sx)] (e) x [(Tx ¬Tx) & (Sx ¬Sx)] 3
annaabi.ee 
