Matematická logika 2023/24

Semestrální kurz na FJFI ČVUT v zimním semestru 2023/24

Termíny: úterý 1000 v T-207 a úterý 1600 v T-208

AKTUÁLNÍ INFO: Termíny přednášek a cvičení dle aktuální domluvy. 

Přednášející: Petr Cintula a Nicholas Ferenz 

Cvičící: Filip Jankovec  

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.

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)

1. Úvod: motivace, historie, úvodní seznámení s klasickou výrokovou logikou (slajdy)

2. Sémantika výrokové logiky: ohodnocení, tautologie, Booleovské funkce, funkční úplnost, CNF a DNF, báze, model, splnitelnost, kompaktnost (slajdy, cvičení)

3. Axiomatizace výrokové logiky: axiomy, teorémy, věta o dedukci, korektnost, úplnost a rozhodnutelnost kalkulu Hilbertova a Gentzenova typu (slajdy, 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 (slajdy, 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 (slajdy, 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 (slajdy, cvičení)

Studijní materiály

1. V. Švejdar: Logika - neúplnost, složitost a nutnost. Academia, Praha 2002. Volně ke stažení na http://www1.cuni.cz/~svejdar/

2. J. Mareš: Matematická logika. ČVUT, Praha, 2009.

3. N.J.J. Smith. Logic: The Laws of Truth. Princeton University Press, 2012