Matematická logika - NMAG331

• Anglický název: Mathematical Logic
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• 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í
• Způsob výuky: prezenční
• Další informace: https://users.math.cas.cz/~jerabek/teaching/mathlog.html
• Garant: 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

čeština

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)

angličtina

An advanced course in mathematical logic. It breifly recalls basic concepts and costructions. The main topic is the incompleteness and the undecidability, and Godel's theorems in particular. A recommended course for specializations Mathematical Analysis and Mathematical Structures within General Mathematics.

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

čeština

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

angličtina

Oral exam, see http://www.karlin.mff.cuni.cz/~krajicek/zk-mll.html

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

Literatura

čeština

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)

angličtina

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.

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

čeština

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)

angličtina

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

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

Sylabus

čeština

Ú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.html a https://www.karlin.mff.cuni.cz/~krajicek/mll.html

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (02.10.2023)

angličtina

A review of basics of first-order logic, including elements of model theory.

Turing machines, the universal machine, the undecidability of the halting problem.

Peano arithmetic PA, Gödel’s theorems, formalization of syntax in PA.

See also https://users.math.cas.cz/~jerabek/teaching/mathlog.html and https://www.karlin.mff.cuni.cz/~krajicek/mll.html

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (02.10.2023)

Vstupní požadavky

čeština

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)

angličtina

This is an informal continuation of NMAG162 Introduction of mathematical logic. The students are expected to understand basic syntactic and semantic properties of propositional and predicate logics.

Poslední úprava: Stanovský David, doc. RNDr., Ph.D. (25.09.2018)