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

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

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.

angličtina

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

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.

Cíl předmětu

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

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.

Podmínky zakončení předmětu

čeština

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

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

angličtina

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

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

Literatura

čeština

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

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.

angličtina

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

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.

Požadavky ke zkoušce

čeština

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

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

angličtina

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

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

Sylabus

čeština

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

Ú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

angličtina

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

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

Vstupní požadavky

čeština

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

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.

angličtina

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

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.