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 znanjaMeđuispit i završni ispit u tjednima bez nastave.
KonzultacijeNajmanje jednom tjedno.
OstaloDomać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.
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
Nositelji
Izvedba
ID 61648
Zimski semestar
4 ECTS
R0 Engleski jezik
R1 E-učenje
45 Predavanja
0 Auditorne vježbe
0 Laboratorijske vježbe
0 Konstrukcijske vježbe
Ocjenjivanje
85 izvrstan
75 vrlo dobar
60 dobar
45 dovoljan