Matematička logika i računarstvo

O kolegiju

• pristupni kolegij na zajedničkom doktorskom studiju matematike
• nastava: 30 tjedana po 2 sata predavanja (četvrtkom 13–15 sati, studeni 2022. – srpanj 2023.)
  • prvih 15 tjedana (logika): Vedran Čačić
  • drugih 15 tjedana (računarstvo): Marko Horvat
• predavanja se mogu pratiti:
  • uživo u predavaonici 105 PMF–MO
  • u realnom vremenu preko platforme Microsoft Teams (javite mi se za link)
  • gledanjem snimki koje će biti objavljene na YouTubeu (link će biti poznat kasnije)
• na Meduzi se mogu naći snimke predavanja iz prethodnih akademskih godina:
  • 2018/19. Tin Perkov
  • 2019/20. Vedran Čačić
  • 2020/21. Mladen Vuković
  • 2021/22. Marko Horvat & Tin Perkov
  • 2022/23. Vedran Čačić & Marko Horvat (u nastajanju)
• Primjer domaćih zadaća (iz akademske godine 2019/20.): prva, druga, treća
• slajdovi s predavanja (javite mi se za zadnju verziju)

Gradivo

1. elementarni modeli i proširenja, parcijalni izomorfizmi
2. teorem kompaktnosti, Löwenheim–Skolemovi teoremi, metoda dijagrama
3. Łoś–Vaughtov test, Robinsonov teorem konzistentnosti
4. interpolacija, definabilnost, ultrafilteri, ultraprodukti
5. teoremi o očuvanju, omašivanje tipova, eliminacija kvantifikatora, saturacija
6. sintaksa i semantika modalne logike
7. osnovne konstrukcije okvira i modela, bisimulacije
8. standardna translacija, ultrafilterska proširenja, modalna saturacija
9. hilbertovski sistemi, prirodna dedukcija, sistemi sekvenata, normalizacija
10. teorija rekurzije, RAM-strojevi, Turingovi strojevi
11. aritmetička hijerarhija, aritmetizacija, definabilnost i reprezentabilnost
12. prvi i drugi Gödelov teorem nepotpunosti, Hilbert–Bernaysovi uvjeti
13. vremenska i prostorna složenost, nedeterminizam, Savitchev teorem
14. polinomna reducibilnost, problem SAT, NP-potpunost
15. λ-račun, račun induktivnih konstrukcija, Coq, dokazi korektnosti softvera

Literatura

• Vuković: Primijenjena logika, skripta koja pokriva većinu gradiva kolegija (javite mi se za zadnju verziju)
• Ebbinghaus, Flum, Thomas: Mathematical Logic
• Chang, Keisler: Model Theory
• Blackburn, de Rijke, Venema: Modal logic (4th ed.)
• Vuković: Izračunljivost
• Čačić: Komputonomikon
• Sipser: Introduction to the Theory of Computation (Part 3: Complexity)