PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Úvod do matematické logiky - NMAG162
Anglický název: Introduction to Mathematical Logic
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017 do 2018
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: prof. RNDr. Jan Krajíček, DrSc.
Třída: M Bc. FM
M Bc. FM > Doporučené volitelné
M Bc. MMIB
M Bc. MMIB > Doporučené volitelné
M Bc. MMIB > 1. ročník
M Bc. MMIT
M Bc. MMIT > Doporučené volitelné
M Bc. OM
M Bc. OM > Zaměření MSTR
M Bc. OM > Doporučené volitelné
M Bc. OM > 1. ročník
Kategorizace předmětu: Matematika > Algebra, Diskrétní matematika
Neslučitelnost : NALG108
Záměnnost : NALG108
Anotace -
Poslední úprava: G_M (15.05.2012)
Volitelný předmět pro bakalářské studium matematiky. Probíraná témata zahrnují základy výrokové a predikátové logiky a nejzákladnější pojmy a fakta z teorie modelů a teorie množin.
Literatura -
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (11.08.2015)
Sylabus -
Poslední úprava: G_M (15.05.2012)
  • 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.

 
Univerzita Karlova | Informační systém UK