Kurz 01 MAL, FJFI ČVUT, zimní semestr 2018/19

Přednášející:

• Igor Sedlár
• Tomáš Lávička
• Petr Cintula

Cvičící:

• Igor Sedlár
• Tomáš Lávička

Cíl předmětu

Logika je zároveň objektem, který matematika studuje, i jazykem, ve kterém je matematika formulována a pomocí kterého je zkoumána. Cílem předmětu je představit základní pojmy a výsledky klasické matematické logiky s důrazem na výrokovou a predikátovou logiku a Gödelovy věty o neúplnosti aritmetiky.

Požadavky k zápočtu a zkoušce:

Ke každé z lekcí 2 až 6 je dáno 10 cvičení. Každý student si zvolí množinu nejméně 30 cvičení obsahující aspoň 4 cvičení z každé lekce, vybraná cvičení vyřeší a na ústní zkoušce zadanou část z vybraných cvičení vysvětlí. Na zápočet a známku E stačí uspokojivě vysvětlit s pomocí doma vypracovaných podkladů. Na známky D nebo C je třeba to zvádnou výborně a bez podkladů a na  známky A nebo B je třeba navíc zodpovědět dodatečné teoretické otázky k lekcím 2 až 6.

Předběžný sylabus

1. Úvod: motivace, historie, úvodní seznámení s klasickou výrokovou logikou (slides)
2. Sémantika výrokové logiky: ohodnocení, tautologie, Booleovské funkce, funkční úplnost, CNF a DNF,báze, model, splnitelnost, kompaktnost  (slides) (cvičení)
3. Axiomatizace výrokové logiky: axiomy, teorémy, věta o dedukci, korektnost, úplnost a rozhodnutelnost kalkulu Hilbertova a Gentzenova typu  (slides) (cvičení)
4. Úvod do predikátové logiky: jazyk, termy, formule, relační struktury, model, splňování, pravdivost, tautologie, sémantický důsledek, prenexace (slides) (cvičení)
5. Axiomatizace predikátové logiky: Gödelova věta o úplnosti kalkulu Hilbertova typu a její důsledky: Löwenheim–Skolemova věta, Skolemizace, Herbrandova věta (slides) (cvičení)
6. Aritmetika a Gödelovy věty o neúplnosti: první a druhá Gödelova věta o neúplnosti Peanovy aritmetiky a jejich důsledky, nerozhodnutelnost predikátového kalkulu (slides) (cvičení)
7. Závěr: teorie množin, neklasické logiky, intuicionismus, základy matematiky

Program

• 2. 10. Přednáška: Úvod, motivace a seznámení s klasickou výrokovou logikou (I. Sedlár)
• 9. 10. Přednáška: Sémantika výrokové logiky (T. Lávička)
• 11. 10. Přednáška: Důkazové kalkuly VL 1 (T. Lávička)
• 16. 10. Přednáška: Důkazové kalkuly VL 2 (T. Lávička)
• 18. 10. Cvičení: Sémantika VL (I. Sedlár)
• 23. 10. Cvičení: Sémantika a kalkuly VL (I. Sedlár)
• 30. 10. Cvičení: Kalkuly VL (I. Sedlár)
• 6. 11. Přednáška: Úvod do predikátové logiky, sémantika PL (I. Sedlár)
• 13. 11. Cvičení: Sémantika PL (I. Sedlár)
• 20. 11. Přednáška: Důkazové kalkuly PL 1 (T. Lávička)
• 22. 11. Přednáška: Důkazové kalkuly PL 2 (T. Lávička)
• 29. 11. Cvičení: Lekce 5 (T. Lávička)
• 4. 12. Přednáška: Lekce 6, část 1 (I. Sedlár)
• 6. 12. Cvičení: Lekce 6 (T. Lávička)
• 11. 12. Přednáška: Lekce 6, část 2 (I. Sedlár)
• 18. 12. Přednáška: Lekce 6, část 3 (I. Sedlár)
• 20. 12. Cvičení: Lekce 6 (T. Lávička)
• 3. 1. Přednáška: Lekce 7 (P. Cintula)

Studijní materiály

•    V. Švejdar: Logika - neúplnost, složitost a nutnost. Academia, Praha 2002. Volně ke stažení na http://www1.cuni.cz/~svejdar/
•    J. Mareš: Matematická logika. ČVUT, Praha, 2009.
•    N.J.J. Smith. Logic: The Laws of Truth. Princeton University Press, 2012.