Matemaatiline loogika ja
algoritmiteooria
kevadsemestril 2012
Kordamisküsimused
Numbrid nurksulgudes viitavad kirjanduse nimekirjale
I. ALGORITMITEOORIA
1. Algoritmid matemaatikas enne
algoritmiteooriat. Algoritmide üldised omadused. Algoritmilist
lahendust
oodanud probleemid. Vajadus
algoritmi mõiste formaliseerimiseks.
2.
Lihtrekursiivse funktsiooni mõiste. Näiteid. LRF omadusi.
[1,8]
3. Lihtrekursiivsed hulgad. [1,8]
4. Lihtrekursiivsed predikaadid. [1,8]
5.
Osaliselt rekursiivse funktsiooni mõiste. [1,8]
6. Turingi masin. Turingi mõttes arvutatavad
funktsioonid. [3]
7. TM kompositsion ja
hargnemine. [3]
8. Rekursiivsete funktsioonide
arvutatavus.
9.
Turingi mõttes arvutatavate funktsioonide rekursiivsus.
Situatsioonide numeratsioon. Algsituatsiooni
number ja numbri muutumine arvutuse jooksul. Resultatiivsuse
tingimuste rekursiivsus. [9]
10. Turingi masinate ja
rekursiivsete funktsioonide numeratsioon.
[3,9]
11. Peatumise probleem. Mittejätkatavad
funktsioonid. [3,8,10]
12. Rekursiivsed ja
rekursiivselt loetletavad hulgad. [3,8,10]
13.
Mitmedimensionaalsed hulgad. Projektsiooniteoreemid. [8,10]
14. Püsipunkti teoreem. Rice’i teoreem. Rice-Shapiro
teoreem. Järeldused programmeerimisteoorias. [8,10]
II. MATEMAATILINE LOOGIKA
1. Ülevaade lausearvutusest. Lause, tõeväärtus, loogiline tehe, valem. Väärtustused.Samaselt tõesed, kehtestatavad ja samaselt väärad valemid. Loogiliselt samaväärsed valemid. Põhisamaväärsused ja nende kasutamine teisendustel. Disjunktiivne ja konjunktiivne normaalkuju. [2,3,4,5,6,7,9]
2. Predikaadid ja kvantorid. Tõesuspiirkonnad. [2,….]
3. Esimest järku keeled. Signatuur. Term. Valem. Vabad ja seotud muutujad. [2,...]
4. Signatuuri interpretatsioonid (algebralised süsteemid, mudelid). Valemi tõesus interpretatsioonis. Samaselt tõesus. Samaväärsus. [2,...]
5. Tõesus ja struktuuri võimsus. Churchi teoreem. Reaalarvude järjestuse elementaarteooria.
6. Predikaatloogika põhisamaväärsused. Nende tõestamine interpretatsioonide terminites. Valemite prefikskuju. [2,...]
7. Samaselt tõesuse näitamine ja kontramudeli konstrueerimine Bethi semantiliste tabelite abil. [11].
8. Loogiline järeldumine.
9. Formaalne aksiomaatiline teooria. Korrektsuse ja täielikkuse probleemid. Mittevasturääkivus. [2,...]
10. Tuletatavate valemite hulga rekursiivne loetletavus. Süntaktiliselt täielike teooriate lahenduvus.
11. Lausearvutuse aksiomaatika. Lausearvutuse korrektsus ja mittevasturääkivus, täielikkus. [2,3,4,5,6,7,9]
12. Puhas predikaatarvutus. Predikaatarvutuse korrektsus, mittevasturääkivus, täielikkus. [2,...]
13. Võrdusega predikaatarvutus. Võrduse põhiomaduste tuletamine. Korrektsus, mittevasturääkivus ja täielikkus.[3]
14. I järku aksiomaatilised teooriad, nende korrektsus, mittevasturääkivus, täielikkus. [2,...]
15. Teoreem mudelist ja predikaatloogika täielikkuse teoreemi tõestus.
16. Peano aritmeetika. Aksioomide mõte. Teist järku aritmeetika mudelid. I järku teooria mittestandardsed mudelid.
17. Aritmeetiline ja Kleene-Mostowski hierarhia. Predikaatide väljendatavus formaalse aritmeetika keeles.
18. Gödeli teoreem mittetäielikkusest. [2,4,5,6,9]
19. Aritmeetika mittevasturääkivuse probleem. [2,4,5,6,9]
III. ALGORITMILISED PROBLEEMID FORMAALSETE KEELTE TEOORIAS
1. Genereerivad grammatikad. Loetletavate sõnahulkade
esitamine genereeritava keelena. Kontekstivaba keele lahenduvus.
2.
Sõnade ekvivalentsi probleem.
3. Tuletatavus Thue
poolsüsteemides.