Matematička logika i izračunljivost

Prijava

Matematička logika i izračunljivost

Opis predmeta

Kolegij se sastoji od tri dijela. U prvom dijelu obrađuje se klasična logika sudova. Naglasak je na razlikovanju sintakse i semantike, te prvi dio služi kao uvod i motivacija za drugi dio u kojem se razmatra logika prvog reda. U tom dijelu se posebno ističe neodlučivost logike prvog reda, te se naglašava nužnost definicije pojma algoritma. U trećem dijelu razmatraju se osnove teorije izračunljivosti. Kao osnovni model izračunavanja razmatraju se RAM-strojevi. Definira se klasa parcijalno rekurzivnih funkcija, te dokazuje da je jednaka klasi svih RAM-izračunljivih funkcija. To je motivacija za iskazivanje Churchove teze.

Opće kompetencije

Osnove klasične logike sudova, logike prvog reda i modalne logike. Temeljna znanja iz teorije izračunljivosti i teorije rekurzije. Iskustvo u određivanju normalnih formi formula, primjenama glavnog testa, te određivanju rekurzivnosti funkcija i skupova.

Ishodi učenja

pretvoriti formulu logike sudova u normalnu fomu
definirati pojam dokaza i teorema
koristiti glavni test za ispitivanje valjanosti formula
navesti osnove modalne logike
definirati pojam strukture prvog reda
pretvoriti formulu logike prvog reda u preneksnu normalnu fomu
definirati pojmove RAM-izračunljive i parcijalno rekurzivne funkcije
objasniti važnost Churchove teze

Oblici nastave

Predavanja

Predavanja koja sadrže veliki broj primjera i zadataka.

Provjere znanja

Međuispit i završni ispit u tjednima bez nastave.

Konzultacije

Najmanje jednom tjedno.

Ostalo

Domaće zadaće.

Način ocjenjivanja

	Kontinuirana nastava		Ispitni rok
Vrsta provjere	Prag	Udio u ocjeni	Prag	Udio u ocjeni
Domaće zadaće	0 %	10 %	0 %	10 %
Međuispit: Pismeni	0 %	45 %	0 %
Završni ispit: Pismeni	0 %	45 %
Ispit: Pismeni			0 %	90 %

Tjedni plan nastave

Osnovno o skupovima. Uvod o logici sudova. Sintaksa logike sudova. Semantika logike sudova.
Normalne forme u logici sudova. Glavni test. Odlučivost. Problem P=NP.
Aksiomatski sistem za logiku sudova. Dokaz, teorem i izvod. Teorem adekvatnosti. Konzistentnost.
Skica dokaza teorema potpunosti za logiku sudova.
Modalna logika: sistem K, Kripkeovi okviri i modeli, teoremi potpunosti i adekvatnosti za sistem K.
Logika prvog reda: sintaksa proizvoljne teorije, termi i formule.
Semantika logike prvog reda: interpretacija, istinitost formula. Preneksna normalna forma.
Međuispit.
Glavni test za logiku prvog reda. Churchov teorem.
Aksiomatski sistem za logiku prvog reda. Dokaz, teorem i izvod. Teorem dedukcije. Teroem adekvatnosti.
Konzistentnost. Skica dokaza Goedelovog teorema potpunosti. Teorem kompaktnosti.
Izračunljivost: RAM-stroj, RAM-izračunljiva funkcija. Makro-stroj.
Primitivno rekurzivne funkcije: inicijalne funkcije, kompozicija i primitivna rekurzija. Ackermannova funkcija. Parcijalno rekurzivne funkcije. Rekurzivni skupovi.
Dokaz da je svaka parcijalno rekurzivna funkciaj RAM-izracunljiva. Kodiranje konačnih nizova prirodnih brojeva. Kodiranje RAM-stroja. Univerzalna funkcija.
Kleeenijev teorem o normalnoj formi za parcijalno rekurzivne funkcije. Jednakost klasa RAM-izracunljivih i parcijalno rekurzivnih funkcija. Teorem rekurzije. Riceov teroem. Churchova teza. Halting problem. Skica dokaza Churchovog teorema.