Předmět Úvod do matematické logiky (NMAG162)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NMAG162 - Úvod do matematické logiky, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).

Materiál	Typ	Datum	Počet stažení

Sylabus

Výroková logika (jazyk, formule, pravdivostní ohodnocení). Splnitelnost, tautologie. Pravdivostní tabulky. Jednoznačnost zápisu formulí. Sekvenční kalkulus (výrokový), jeho úplnost a korektnost. V. o dedukci. Logicky ekvivalentní formule, DNF a CNF. Reprezentace booleovských funkcí formulemi a jejich velikost. DeMorganovy zákony, komutatitivita, asociativita a distributivita konjunkce a disjunkce. Interpolace. Splnitelné množiny výrokových formulí. V. o kompaktnosti pro výrokovou logiku a její aplikace. Logika prvního řádu, jazyk, rovnost, termy, formule. Volné a vázané výskyty proměnných, otevřené formule, sentence. Logicky ekvivalentní formule, prenexní tvar formule a prenexní operace. Struktury a interpretace jazyka. Tarského definice splňování. Příklady: reálně uzavřená a algebraicky uzavřená tělesa, vektorové prostory, grupy, uspořádání, grafy, a pod.. Formule definující základní vlastnosti relací: relace ekvivalence, graf funkce, graf bijekce, a pod.. Vnoření a izomorfismus struktur, podstruktury. Elementární ekvivalence. Teorie struktury. Zachovávání existenčních formulí nahoru a universálních dolů. Diagram struktury. Teorie, axiomy, model teorie. Př.: uspořádání, tělesa, grupy, relace ekvivalence, PA. Axiomy rovnosti. Sekvenční kalkulus pro logiku prvního řádu. V. o úplnosti (bez dk.). V. o kompaktnosti a její tři dúkazy: z V. o úplnosti, Henkinova konstrukce a ultraprodukt. Poznámky o Godelově větě o neúplnosti. Aplikace kompaktnosti: Elementární rozšíření, Lowenheim-Skolemova v. směrem nahoru. Nestandartní modely uspořádaného tělesa reálných čísel a okruhu celých čísel. Eliminace kvantifikátorů. Př.: hustá lineární uspořádání a RCF (bez dk.). Intuitivní teorie množin. Russellův paradox. Hilbertův program. Godelova v. o neúplnosti (neformálně). Axiomy teorie ZFC. Axiom výběru, Zornovo lema a princip dobrého uspořádání a jejich ekvivalence. Ordinály a jejich aritmetika. Transfinitní indukce. Koncept mohutnosti množin. Kardinály a jejich aritmetika. Cantorův diagonální argument, Cantor-Bernsteinova věta. Značení alef. Hypotéza kontinua (znění). Konigovo lema.

Literatura

V.Švejdar, Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002.R.Cori, D.Lascar, Mathematical Logic (part I.), Oxford University Press, 2000.H.D.Ebinghaus, J.Flum, W.Thomas, Mathematical Logic, 2.vyd., Springer Verlag, 1994.literatura na webu (a další literatura): viz http://www.karlin.mff.cuni.cz/~krajicek/ml.htmlVideozáznamy přednášek

Garant

prof. RNDr. Jan Krajíček, DrSc.