|
|
|
||
|
Poslední úprava: T_KA (11.04.2007)
|
|
||
|
Poslední úprava: KRAJICEK/MFF.CUNI.CZ (01.10.2009)
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.html
|
|
||
|
Poslední úprava: prof. RNDr. Jan Krajíček, DrSc. (06.03.2007)
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.
Poznamky 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.
Zbude-li čas: Turingovy stroje, Universální Turingův stroj a algoritmická nerozhodnutelnost Halting problému. 10.Hilbertův problém. Rozhodnutelnost teorie reálných čísel.
|