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.