SISSEJUHATUS MATEMAATILISSE LOOGIKASSE
Kordamisküsimused 2005.a. sügissemestril
<>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.
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). Formaalne aritmeetika
(tulemused).
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 (tõestuseta). Järeldused programmeerimise 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: 2002A 2002D