Redukovany sylabus k prednasce

"Uvod do matematicke logiky" - jaro 2020, Jan Krajicek

Zkouska:

Zkouska u tohoto predmetu i v beznem semestru testuje jen absolutni minimum, bez ktereho se zadny matematik neobejde, at se venuje kterekoliv oblasti: schopnost definovat logickou formuli ruzne vlastnosti (prvku, funkci,... i celych struktur) a take schopnost spravne takove formule interpretovat.
Z tohotu duvodu zustavaji v platnosti puvodni pozadavky, ale bez poslednich tri typu otazek. Zkouska bude pisemna, o neco kratsi nez obvykle (viz priklady na strance vyse) a presencni (nezasahne-li jeste nejak vyssi moc). Predterminy (ktere v beznem semestru zkousim ustne) letos nenabizim.

Redukovany sylabus:

Sylabus je pro tento semestr vyznamne zredukovany. Zustalo jen to nejpodstatnejsi, co by mel znat kazdy matematik s universitnim vzdelanim:
- formalni jazyk logiky: vyrokove formule a formule 1.radu a jejich interpretace, teorie,
- struktury 1.radu a jejich vztah k formulim a teoriim: Tarskeho splnovani, Veta o uplnosti (jen zneni, ne dukaz),
- nejdulezitejsi fakt logiky pro aplikace mimo logiku: Veta o kompaktnosti (jeji dukaz z V. o uplnosti a par jejich nejelementarnejsich dusledku),
- pojmy isomorfismu a elementarni ekvivalence struktur a jejich rozdil.

Obsah:

  • Vyrokova logika: jazyk, formule, pravdivostni ohodnoceni. Splnitelnost, tautologie. Pravdivostni tabulky. Jednoznacnost zapisu formuli.

  • Logicky ekvivalentni formule, DNF a CNF. Reprezentace booleovskych funkci formulemi a jejich velikost. DeMorganovy zakony, komutativita, asociativita a distributivita konjunkce a disjunkce. Interpolace.

  • Splnitelne mnoziny vyrokovych formuli. V. o kompaktnosti pro vyrokovou logiku.
    Pr.: kompaktnost 3-obarvitelnosti nekonecnych grafu

  • Logika prvniho radu, jazyk, rovnost, termy, formule. Volne a vazane vyskyty promennych, otevrene formule, sentence. Logicky ekvivalentni formule, prenexni tvar formule a prenexni operace.

  • Struktury a interpretace jazyka. Tarskeho definice splnovani.
    Pr. struktur: usporadane teleso realnych cisel, teleso komplexnich cisel, grupy, vektorove prostory, okruh celych cisel, usporadani, grafy.

  • Formule definujici zakladni vlastnosti relaci: relace ekvivalence, graf funkce, graf bijekce a podobne.

  • Vnoreni a izomorfismus struktur, podstruktury. Elementarni ekvivalence a Ehrenfeucht-Fraisseho hra.
    Pr. DLO - huste linearni usporadani bez nejvetsiho a nejmensiho prvku.

  • Teorie struktury. Zachovavani existencnich resp. universalnich formuli v nad- resp. v pod-strukturach.

  • Teorie, axiomy, model teorie.
    Pr. teorii: usporadani, telesa, grupy, relace ekvivalence. Axiomy rovnosti.

  • Predikatovy pocet. V. o uplnosti (jen zneni, bez dukazu).

  • V. o kompaktnosti a jeji dukaz z V. o uplnosti.

  • Aplikace kompaktnosti: Lowenheim-Skolemova v. smerem nahoru, nestandartni model telesa realnych cisel.

  • Definovatelne mnoziny a funkce.