PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Matematická logika - NMAG331
Anglický název: Mathematical Logic
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: https://users.math.cas.cz/~jerabek/teaching/mathlog/mathlog.html
Garant: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.
Vyučující: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.
Třída: M Mgr. MSTR > Povinně volitelné
Kategorizace předmětu: Informatika > Diskrétní matematika
Matematika > Diskrétní matematika
Neslučitelnost : NLTM006
Záměnnost : NLTM006
Je záměnnost pro: NLTM006
Ve slož. prerekvizitě: NMAG349
Anotace -
Pokročilejší přednáška o matematické logice. Stručně zopakuje základní pojmy a konstrukce. Hlavním tématem přednášky je neúplnost a nerozhodnutelnost, zejména Gödelovy věty. Určeno pro zaměření Matematická analýza a Matematické struktury na OM.
Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.09.2013)
Cíl předmětu

Cílem je nahlédnout do problematiky logických základů matematiky a vyložit zejména algoritmickou nerozhodnutelnost Halting problému a Gödelovu větu o neúplnosti.

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (02.10.2023)
Podmínky zakončení předmětu -

Ústní zkouška, viz http://www.karlin.mff.cuni.cz/~krajicek/zk-mll.html

Poslední úprava: Krajíček Jan, prof. RNDr., DrSc. (14.07.2019)
Literatura -

Lou van den Dries: Lecture notes on mathematical logic, https://www.karlin.mff.cuni.cz/~krajicek/vddries.pdf

Michael Sipser: Introduction to the theory of computation, Thomson, 2006.

Vítězslav Švejdar: Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002.

René Cori and Daniel Lascar: Mathematical logic: A course with exercises (Part I and Part II), Oxford University Press, 2000.

Joseph R. Shoenfield: Mathematical logic; Addison-Wesley Publishing Company, London, 1967.

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (02.10.2023)
Požadavky ke zkoušce -

Viz http://www.karlin.mff.cuni.cz/~krajicek/zk-mll.html

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (28.10.2019)
Sylabus -

Úplnost — Syntax a semantika predikátové logiky (opakování), úplnost, kompaktnost, Löwenheim–Skolemovy věty, Vaughtův test, nestandardní modely

Vyčíslitelnost — Turingovy stroje, vyčíslitelné funkce, univerzální Turingův stroj, nerozhodnutelnost halting problemu

Nerozhodnutelnost a neúplnost — Peanova aritmetika PA, Gödelova a Churchova věta o neúplnosti a nerozhodnutelnosti aritmetiky, formalizace syntaxe v PA

Viz též https://users.math.cas.cz/~jerabek/teaching/mathlog/mathlog.html a https://www.karlin.mff.cuni.cz/~krajicek/mll.html

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (30.09.2024)
Vstupní požadavky -

Navazuje se na předmět NMAG162 Úvod do matematické logiky. K porozumění je nutné znát základní syntaktické a sémantické vlastnosti výrokové a predikátové logiky.

Poslední úprava: Stanovský David, doc. RNDr., Ph.D. (25.09.2018)
 
Univerzita Karlova | Informační systém UK