Matematická logika 2018/19


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


Přednášející:

Cvičící:


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
  2. Sémantika výrokové logiky: ohodnocení, tautologie, Booleovské funkce, funkční úplnost, CNF a DNF, báze, model, splnitelnost, kompaktnost 
  3. Axiomatizace výrokové logiky: axiomy, teorémy, věta o dedukci, korektnost, úplnost a rozhodnutelnost kalkulu Hilbertova a Gentzenova typu 
  4. Úvod do predikátové logiky: jazyk, termy, formule, relační struktury, model, splňování, pravdivost, tautologie, sémantický důsledek, prenexace
  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
  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
  7. Závěr: teorie množin, neklasické logiky, intuicionismus, základy matematiky

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.