Matematická logika 2025/26
Semestrální kurz na FJFI ČVUT v zimním semestru 2025/26
Termíny: pondělí 1600 v T-112 (přednášky) a pátek 1600 v T-204 (cvičení, nepravidelné, sledujte aktuální)
AKTUALNÍ INFO: přednášky začnou 29.9.; cvičení 3.10., 10.10. nebude, další průběh bude upřesněn
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/C je třeba to zvádnout uspokojivě/výborně bez podkladů a na známky B/A je třeba navíc zodpovědět dodatečné teoretické otázky.
Termíny zkoušek: bude oznámeno.
Místo zkoušek: zasedací místnost č. dveří 419 na Ústavu Informatiky AV ČR.
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.
Předběžný sylabus (Lekce 1 až Lekce 6)
Úvod: motivace, historie, úvodní seznámení s klasickou výrokovou logikou (slajdy)
Sémantika výrokové logiky: ohodnocení, tautologie, Booleovské funkce, funkční úplnost, CNF a DNF, báze, model, splnitelnost, kompaktnost (slajdy, cvičení)
Axiomatizace výrokové logiky: axiomy, teorémy, věta o dedukci, korektnost, úplnost a rozhodnutelnost kalkulu Hilbertova a Gentzenova typu (slajdy, cvičení)
Úvod do predikátové logiky: jazyk, termy, formule, relační struktury, model, splňování, pravdivost, tautologie, sémantický důsledek, prenexace (slajdy, cvičení)
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 (slajdy, cvičení)
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 (slajdy, cvičení)
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