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.

Ishodi učenja

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

Oblici nastave

Predavanja

Predavanja koja sadrže veliki broj primjera i zadataka.

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

  1. Osnovno o skupovima. Uvod o logici sudova. Sintaksa logike sudova. Semantika logike sudova.
  2. Normalne forme u logici sudova. Glavni test. Odlučivost. Problem P=NP.
  3. Aksiomatski sistem za logiku sudova. Dokaz, teorem i izvod. Teorem adekvatnosti. Konzistentnost.
  4. Skica dokaza teorema potpunosti za logiku sudova.
  5. Modalna logika: sistem K, Kripkeovi okviri i modeli, teoremi potpunosti i adekvatnosti za sistem K.
  6. Logika prvog reda: sintaksa proizvoljne teorije, termi i formule.
  7. Semantika logike prvog reda: interpretacija, istinitost formula. Preneksna normalna forma.
  8. Međuispit.
  9. Glavni test za logiku prvog reda. Churchov teorem.
  10. Aksiomatski sistem za logiku prvog reda. Dokaz, teorem i izvod. Teorem dedukcije. Teroem adekvatnosti.
  11. Konzistentnost. Skica dokaza Goedelovog teorema potpunosti. Teorem kompaktnosti.
  12. Izračunljivost: RAM-stroj, RAM-izračunljiva funkcija. Makro-stroj.
  13. Primitivno rekurzivne funkcije: inicijalne funkcije, kompozicija i primitivna rekurzija. Ackermannova funkcija. Parcijalno rekurzivne funkcije. Rekurzivni skupovi.
  14. Dokaz da je svaka parcijalno rekurzivna funkciaj RAM-izracunljiva. Kodiranje konačnih nizova prirodnih brojeva. Kodiranje RAM-stroja. Univerzalna funkcija.
  15. 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.

Studijski programi

Sveučilišni diplomski
Audiotehnologije i elektroakustika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Automatika i robotika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektroenergetika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektroničko i računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektronika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektrostrojarstvo i automatizacija (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Informacijsko i komunikacijsko inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Komunikacijske i svemirske tehnologije (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Izborni predmet profila (1. semestar)
Računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Računalno modeliranje u inženjerstvu (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Računarska znanost (profil)
Slobodni izborni predmeti (3. semestar) Slobodni zborni predmeti (1. semestar)
Znanost o mrežama (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Znanost o podacima (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)

Literatura

Mladen Vuković (.), Matematička logika i izračunljivost, web-izdanje; https://www.pmf.unizg.hr/_download/repository/MLI-predavanja-2017.pdf
Mladen Vuković (2009.), Matematička logika, Element, Zagreb
Mladen Vuković (2015.), Izračunljivost, web-izdanje; https://www.pmf.unizg.hr/_download/repository/IZN-predavanja-2015%5B1%5D.pdf
R. Cori, D. Lascar (2000.), Mathematical Logic, Part I,, Oxford University Press
Michael Sipser (1997.), Introduction to the Theory of Computation, Course Technology Ptr
J. R. Shoefield (2017.), Recursion Theory, Cambridge University Press

Za studente

Izvedba

ID 222646
  Zimski semestar
5 ECTS
R3 Engleski jezik
R1 E-učenje
45 Predavanja

Ocjenjivanje

85 izvrstan
75 vrlo dobar
60 dobar
45 dovoljan