Sylabus a literatura k prednasce

"Uvod do matematicke logiky", Jan Krajicek

Kod predmetu: NMAG162

Informace o zkousce

Zaznam prednasek z jara 2014

Studentsky logicky seminar (kazdy semestr)

Sylabus:

Temata v zavorkach [...] prednasim jen je-li cas.

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

  • [ Vyrokovy pocet (sekvencni kalkulus nebo Hilbertovsky), jeho uplnost a korektnost. V. o dedukci. ]

  • Vyrokova resoluce a jeji uplnost.

  • 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, pravdivostni ohodnoceni v booleovske algebre podmnozin dane mnoziny.

  • 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 pod.

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

  • Teorie [a diagram] struktury. Zachovavani existencnich resp. universalnich formuli v nad- resp. pod-strukturach.

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

  • Predikatovy pocet. V. o uplnosti. [Idea Henkinovy konstrukce.]

  • V. o kompaktnosti a jeji dukaz z V. o uplnosti. [Dukaz pres ultraproduct.]

  • Aplikace kompaktnosti: Elementarni rozsireni, Lowenheim-Skolemova v. smerem nahoru, nestandartni modely telesa realnych cisel a prirozenych cisel. Teorie teles charakteristiky 0 a charakteristiky p > 0. [Ax - Grothendieckova veta.]

  • [Skolemovske funkce a Skolemizace teorie. Lowenheim-Skolemova v. smerem dolu.]

  • Eliminace kvantifikatoru. Pr.: husta linearni usporadani (s dk.), a bez dk. realne uzavrena telesa, algebraicky uzavrena telesa (bude-li cas: prirozena cisla s naslednikem, Pressburgerova aritmetika). Ne-eliminovatelnost kvantifikatoru ve strukture prirozenych cisel.

  • Definovatelne mnoziny a funkce. RCF a o-minimalita, pr.: nedefinovatelnost celych cisel v realnych cislech. ACF a silna minimalita.

  • Bez dk.: Nerozhodnutelnost vlastnosti, je-li formule dokazatelna v predikatovem poctu. Rekursivni vycislitelnost mnoziny dokazatelnych formuli. Rozhodnutelnost relace splnovani v usporadanem telese realnych cisel ci v komplexnich cislech, nerozhodnutelnost splnovani v prirozenych cislech. Slabsi forma Godelovy v. o neuplnosti: Zadna algoritmicky rozhodnutelna teorie majici prirozena cisla za model neni uplna.

  • [ Priklady rozsireni logiky 1.radu FO: SO, WSO, nekonecne formule, nove kvantifikatory, neklasicke logiky, ... . Elementarni tridy struktur a pr. prirozenych ne-elementarnich trid struktur: torsni grupy, lokalne konecna telesa, ... ]

  • [ Funkce a mnoziny na strukture versus definovatelne funkce a mnoziny. Mnozinove-teoreticky charakter R_2 (realna cisla a vsechny funkce na nich), pr.: formulace CH. Algebraicko-geometricky charakter R s definovatelnymi funkcemi, pr.: rozklad definovatelnych mnozin na bunky, Eulerova charakteristika, dimenze, ... . ]

  • Naivni teorie mnozin, Russelluv paradox. Hilbertuv program. Godelova v. o neuplnosti a nedokazatelnosti bezespornosti (neformalne).

  • Turingovy stroje a idea universalniho Turingova stroje. Halting problem a 10.Hilbertuv problem. Entscheidungsproblem.

    Literatura:

    Hlavni:

  • L. van den Dries, Lecture notes on mathematical logic (pdf soubor). Kap. 1. - 4. obsahuji temer vse, co prednasim. (ps soubor)

    Dale na webu:

  • S.Buss, Introduction to mathematical logic, draft of a book, pdf

  • V.Svejdar, Logika: neuplnost, slozitost a nutnost (pdf soubor), Academia, Praha, 2002.

    Dalsi literatura cesky:

  • A.Sochor, Klasicka matematicka logika, Karolinum, Praha, 2001.

  • B.Balcar a P.Stepanek, Teorie mnozin, Academia, Praha, 1986.

    Vhodne knihy dostupne v knihovne MFF:

  • H.D.Ebinghaus, J.Flum, W.Thomas, Mathematical Logic, 2.vyd., Springer-Verlag, 1994.

  • R.Cori, D.Lascar, Mathematical Logic (Part I.), Oxford U. Press, 2000.

    Knihovna MFF ma radu dalsich klasickych ucebnic matematicke logiky (Shoenfield, Kleene, Mendelsohn, Bell-Machover,...) ale ty jsou vesmes prilis podrobne pro uvodni kurs.
    Text o obvodech a jejich slozitosti:

  • R.Boppana a M.Sipser, The complexity of finite functions.

    To je sice vice jak 30 let stare, ale stale representativni.
    O vyrokove rezoluci a jeji uplnosti:

    stranky 11-13 ve starsich skriptech o dukazove slozitosti.