Matematická logika - NMAG331

• Anglický název: Mathematical Logic
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2025
• 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/
• 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. MMIB; M Mgr. MMIB > Povinně volitelné; M Mgr. MSTR; 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. Jedna otázka z následujícího seznamu:

1. Syntax and semantika logiky prvního řádu. Věty o úplnosti a kompaktnosti.

2. Turingovy stroje, rozhodnutelné a rekurzivně spočetné množiny. Univerzální Turingův stroj, problém zastavení a jeho nerozhodnutelnost.

3. Robinsonova a Peanova aritmetika a její neúplnost (Gödelova první věta o neúplnosti). Nerozhodnutelnost logiky prvního řádu (Hilbertův Entscheidungsproblem).

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

angličtina

Oral exam. One question from the following list:

1. Syntax and semantics of first-order logic. The completeness and compactness theorems.

2. Turing machines, decidable and semidecidable sets. Universal Turing machine, the halting problem and its undecidability.

3. Robinson and Peano arithmetic and its incompleteness (Gödel’s first incompleteness theorem). Undecidability of first-order logic (Hilbert’s Entscheidungsproblem).

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

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

Ústní zkouška. Jedna otázka z následujícího seznamu:

1. Syntax and semantika logiky prvního řádu. Věty o úplnosti a kompaktnosti.

2. Turingovy stroje, rozhodnutelné a rekurzivně spočetné množiny. Univerzální Turingův stroj, problém zastavení a jeho nerozhodnutelnost.

3. Robinsonova a Peanova aritmetika a její neúplnost (Gödelova první věta o neúplnosti). Nerozhodnutelnost logiky prvního řádu (Hilbertův Entscheidungsproblem).

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

angličtina

Oral exam. One question from the following list:

1. Syntax and semantics of first-order logic. The completeness and compactness theorems.

2. Turing machines, decidable and semidecidable sets. Universal Turing machine, the halting problem and its undecidability.

3. Robinson and Peano arithmetic and its incompleteness (Gödel’s first incompleteness theorem). Undecidability of first-order logic (Hilbert’s Entscheidungsproblem).

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

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

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

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

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

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)