Matematička logika i izračunljivost

Prikazani su podaci za akademsku godinu: 2024./2025.

Nositelji

Izv. prof. dr. sc.
Ante Đerek
Prof. dr. sc.
Mladen Vuković

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.

Preduvjeti

Od studenta koji upisuju ovaj predmet očekuje se da su u već položenim predmetima matematičkog sadržaja naučili formalni matematički jezik te strogu argumentaciju u matematičkim dokazima.

Studijski programi

Sveučilišni diplomski
[FER3-HR] Audiotehnologije i elektroakustika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Automatika i robotika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektroenergetika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektroničko i računalno inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektronika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektrostrojarstvo i automatizacija - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Informacijsko i komunikacijsko inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Komunikacijske i svemirske tehnologije - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Programsko inženjerstvo i informacijski sustavi - profil
Izborni predmeti (1. semestar)
Izborni predmet profila (1. semestar)
[FER3-HR] Računalno inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Računalno modeliranje u inženjerstvu - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Računarska znanost - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Znanost o mrežama - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Znanost o podacima - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER2-HR] Automatika - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Bežične komunikacijske tehnologije - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Elektroenergetika - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Elektroničko i računalno inženjerstvo - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Elektronika - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Elektrotehnički sustavi i tehnologija - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Obradba informacija - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Programsko inženjerstvo i informacijski sustavi - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Računalno inženjerstvo - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Računarska znanost - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
[FER2-HR] Telekomunikacije i informatika - profil
Predmeti matematike, fizike i prirodoslovlja (1. semestar)

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.

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

Izvedba

ID 222646
  Zimski semestar
5 ECTS
R1 Engleski jezik
R1 E-učenje
45 Predavanja
0 Seminar
0 Auditorne vježbe
0 Laboratorijske vježbe
0 Konstrukcijske vježbe
0 Vježbe tjelesnog odgoja

Ocjenjivanje

85 izvrstan
75 vrlo dobar
60 dobar
45 dovoljan

Sličan predmet