I. LAUSEARVUTUS
1.Lause, tõeväärtus, loogiline tehe, valem.
Põhimõistete defineerimisel tehtud kokkulepped. Väärtustused.
2.Samaselt tõesed, kehtestatavad ja samaselt väärad
valemid.
3.Loogiliselt samaväärsed valemid. Põhisamaväärsused
ja nende kasutamine teisendustel. Tehete avaldamine teiste kaudu.
4.Täielik disjunktiivne normaalkuju. Lemmad tõesuspiirkonna
kohta. Lausearvutuse tehete komplekti piisavus liitlausete moodustamise
formaliseerimiseks. TDNK leidmise algoritm.
5. Järeldumine. Seosed samaväärsuse ja DNK-ga.
II. PREDIKAATLOOGIKA
1.Indiviidid ja predikaadid. Kvantorid. Tõesuspiirkonnad.
2.Keele signatuur: konstant-, funktsionaal- ja predikaatsümbolid.
Valem. Vabad ja seotud muutujad.
3.Signatuuri interpretatsioonid (algebralised süsteemid,
mudelid). Valemi tõesus mudelil.
4.Väidete kirjutamine I j. keeles.
5.Samaselt tõesus ja loogiline samaväärsus.
Predikaatloogika põhisamaväärsused. Nende tõestamine
interpretatsioonide terminites.
6.Tehete ja kvantoritega seotud tõestusvõtted
(eelduse ja väite jaoks). Näited teoreemide tõestamisest
loogikasümbolitele vastavaid samme kasutades.
III. TURINGI MASINAD.
1.Turingi masin. Arvuliste funktsioonide arvutamine Turingi
masinal.
2.Turingi masinate kompositsioon ja hargnemine.
3.Turingi masinate numeratsioon.
4.Turingi mõttes mittearvutatavad funktsioonid. Eneselerakendatavuse
ja peatumise probleemi mittelahenduvus. Järeldused programmeerimisteooria
jaoks.
-------------------------------------------------------------------
Eksamil tuleb vastata 3 küsimusele, mis võivad olla erinevat
tüüpi: definitsioonide ja väidete formuleeringud, teoreemid
ja nende (osade) tõestused, ülesanded, ülevaated mingi
probleemi arengu kohta kursuses. Iga peatüki kohta on tüüpiliselt
üks küsimus, aga on võimalik, et küsimus puudutab
mitut peatükki .
-------------------------------------------------------------------
Eelmiste eksamite küsimusi: 1999A
1999D