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

  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.

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 Napomena / komentar 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
Automatika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Bežične komunikacijske tehnologije (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektroenergetika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektroničko i računalno inženjerstvo (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektronika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektrotehnički sustavi i tehnologija (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Obradba informacija (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Računalno inženjerstvo (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Računarska znanost (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Telekomunikacije i informatika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)

Literatura

Mladen Vuković (2009.), Matematička logika, Element, Zagreb
Mladen Vuković (2007.), Izračunljivost, web-izdanje
R. Cori, D. Lascar (2000.), Mathematical Logic, Part I, Oxford University Press
M. Sipser (1997.), Introduction to the Theory of Computation, PWS Pub. Company;1997.
J. R. Shoefield (1993.), Recursion Theory, Springer-Verlag

Izvedba

ID 61648
  Zimski semestar
4 ECTS
R0 Engleski jezik
R1 E-učenje
45 Predavanja
0 Auditorne vježbe
0 Laboratorijske vježbe

Ocjenjivanje

85 izvrstan
75 vrlo dobar
60 dobar
45 dovoljan