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.
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)
- Ú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