Matematická logika - NMAG331

• Anglický název: Mathematical Logic
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• Virtuální mobilita / počet míst: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Další informace: http://www.karlin.mff.cuni.cz/~stanovsk/
• 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: prof. RNDr. Jan Krajíček, DrSc. (10.09.2019)

Cílem je nahlédnout do problematiky logických základů matematiky a vyložit zejména algoritmickou nerozhodnutelnost

Halting problému a Godelovu 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: doc. RNDr. David Stanovský, Ph.D. (25.09.2018)

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

J.R.Shoenfield: Mathematical logic; Addison-Wesley Publishing Company, London . Don Mills, Ontario, 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: prof. RNDr. Jan Krajíček, DrSc. (14.07.2019)

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

Peanova aritmetika PA, formalizace syntaxe v PA.

Nerozhodnutelnost a neúplnost - vyčíslitelné funkce, Turingův stroj, halting problem, Gödelova a Churchova věta o neúplnosti a nerozhodnutelnosti aritmetiky

Viz též http://www.karlin.mff.cuni.cz/~krajicek/mll.html

angličtina

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

A review of basics of first-order logic, including elements of model theory. Peano arithmetic PA, formalization of syntax in PA. Godel's theorems. Turing machines, the universal machine, the undecidability of the halting problem.

See also http://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.