I. 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).
II. AKSIOMAATILISED TEOORIAD.
1. Aksiomaatilise teooria üldskeem.
2. Gentzeni tüüpi lausearvutus. Tuletamine
lausearvutuses.
3. Lausearvutuse korrektsus,
mittevastusrääkivus, täielikkus (tõestustega).
4. Gentzeni tüüpi predikaatarvutus.
Tuletamine predikaatarvutuses. Predikaatarvutuse korrektsus,
mittevasturääkivus , täielikkus (neist viimane
tõestuseta).
5. Võrdusega predikaatarvutus. Selle
korrektsuse, mittevasturääkivuse ja täielikkuse teoreemid
(neist viimane tõestuseta).
6. Esimest järku aksiomaatilised teooriad.
Teoreemid nende korrektsuse, mittevasturääkivuse ja
täielikkuse kohta (tõestuseta).
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. Rice'i
teoreem. Järeldused programmeerimisteooria jaoks.
-------------------------------------------------------------------
Eksamil tuleb vastata 3 küsimusele, mis võivad olla
erinevat tüüpi: mingi peatüki 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 (Matemaatilise loogika elementide) eksamite küsimusi: 1999A 1999D