Filozofická Fakulta

Katedra logiky

Aktuality

Začínají až v druhém týdnu semestru (od 27.2.)

V letním semestru...

14. únor 2017

dne 14.2. odpadá. Kvůli dalším termínům se na mě prosím obraťte mailem.
14. únor 2017

Obecné informace

Termíny SZZk

Jaro a podzim podle Harmonogramu školního roku. Konkrétní termíny budou vyhlášeny do 18. 1., 10. 5. a 1. 9., nejpozději vsak 14 dní předem. Přihláška k SZZK: na tiskopise do 15. 12., 30. 4. nebo 31. 7. včetne přihlášky ke zkoušce z voliteného předmětu. Uzavření studijních povinností podle Harmonogramu školního roku. Na přihlášce musí být potvtrzeno uzavření studijních povinností.

Opakování SZZk

Opakování SZZk je možné nejvýše dvakrát, a to nejpozději do dvou let od termínu prvního neúspěšného pokusu; nejpozději do 8 let od zahájení studia, nejdřive v nejbližším termínu pro konání SZZk. SZZk se opakuje celá.

Požadavky ke SZZk na oboru Logika:

Státní závěrečná zkouška ve studijním programu Logika se koná z těchto částí:

  1. Hlavní předmět, jímž je jedna z variant

    I. filozofická logika
    II. logika a metamatematika
    III. logika a teorie modelů

  2. Volitený předmět, který si student vybere z následující nabídky s tím, že v závorkách je uvedeno, při které volbě hlavního předmětu nelze volitelný předmět vybrat:

    algoritmy a rekurzívní funkce
    filozofická logika (I)
    Booleovy algebry (III)
    dějiny logiky (I)
    neklasické logiky (I)
    neúplnost a nerozhodnutelnost (II)
    teorie množin 
    teorie modelů (III)
    teorie racionálního usuzování (zahrnuje i logické programování) 
    výpočtová složitost 

  3. Druhý volitelný předmět (pouze pro jednooborové studium)

  4. Specializační blok (dříve doplněk – pouze pro jednooborové studium)

Pro každý předmět je připraven seznam požadavků. Pro hlavní předmět je ve všech variantách stanovena společná část (viz dále), která je rozšířena o požadavky vybraného zaměření.

Společná část SZZk z logiky – u každé zvolené kombinace se předpokládá znalost následujících pojmů a fakt:

Konjunktivní a disjunktivní normální forma. Úplnost výrokového počtu. Prenexní normální forma. Sémantika klasické predikátové logiky (Tarského definice). Obecný pojem kalkulu. Korektnost. Důkaz věty o dedukci v Hilbertově kalkulu. Důkaz úplnosti kalkulu v predikátové logice prvního řádu. Věta o kompaktnosti. Existence nejvýše spočetného modelu. Konzervativní rozšíření. Rozšíření teorie o definice. Axiomatické teorie. Bezesporné a úplné teorie.

Ordinální a kardinální čísla. Axiomatika teorií množin (ZF, GB), axiom výběru. Rekurzivně spočetné množiny, Postova věta. NP-úplnost. Struktura reálných čísel.

Základní fakta z dějin logiky: Aristotelés, sylogistika, Boole, Frege, paradoxy, Russell a teorie typů, intuicionismus.

 

HLAVNÍ PŘEDMĚTY

  1. Filosofická logika

    • otázky v zip formatu zde; jejich podoba se může průběžně měnit!

  2. Logika a metamatematika

    • Sémantika predikátové logiky. Důsledek (ve výrokové logice, v predikátové logice, v predikátové logice s rovností). Důkaz (odvození) v hilbertovském kalkulu, věta o dedukci. Pojem algoritmu. Rekurzívní a rekurzívně spočetné množiny. Postova věta, m-převeditelnost, m-kompletnost.
    • Věta o kompaktnosti a její důsledky.
    • Vlastnosti logických kakulů. Korektnost a úplnost vzhledem k sémantice klasické výrokové a predikátové logiky, hilbertovské a gentzenovské kalkuly, věta o dedukci, pravidlo řezu, NP-kompletnost množiny všech splnitelných výrokových formulí.
    • Vlastnosti axiomatických teorií. Bezespornost, úplnost, Vaughtův test, rozhodnutelnost, Craigova věta o rekurzívní axiomatizovatelnosti, rozhodnutelnost konečného rozšíření rozhodnutelné teorie.
    • Eliminace kvantifikátorů, definovatelné množiny.
    • Robinsonova a Peanova aritmetika, příklady tvrzení dokazatelných a nedokazatelných v Robinsonově aritmetice, S-úplnost Robinsonovy aritmetiky, příklady tvrzení dokazatelných v Peanově aritmetice, existence nestandardních modelů, jiné metamatematické vlastnosti obou teorií.
    • Definovatelné množiny v nějaké struktuře, definovatelné množiny ve standardním modelu aritmetiky, aritmetická hierarchie.
    • První Gödelova věta, S-korektní teorie, neúplnost a nerozhodnutelnost S-korektních rozšíření Robinsonovy aritmetiky, produktivní a kreativní množiny.
    • Rosserovo zobecnění První Gödelovy věty, (efektivně) rekurzívně neoddělitelné dvojice množin - definice a některé vlastnosti.
    • Věta o autoreferenci, tj. Gödelovo diagonální lemma, některá užití: neexistence formální definice pravdy, klasický důkaz První Gödelovy věty.
    • Druhá Gödelova věta, význam, Hilbertův program.
    • Intuicionistická logika, kripkovská sémantika, kalkuly a jejich korektnost, interpretace klasické logiky v intuicionistické.

  3. Logika a teorie modelů

    • Konstrukce a splňování ve strukturách. Homomorfní obraz, podstruktura, kartézský součin, ultraprodukt.
    • Model teorie. Věta o úplnosti, konstrukce modelu bezesporné teorie pomocí úplného Henkinova rozšíření dané teorie.
    • Elementární ekvivalence. Elementárně ekvivalentní struktury, elementární podstruktury a extenze, Tarského test, elementární vnoření.
    • Axiomatizovatelné třídy.
    • Lowenheim-Skolem-Taského věty o existenci modelů daných mohutností.
    • Úplnost a kategoričnost. Charakterizae úplnosti dané teorie pomocí elementární ekvivalence jejích modelů, teorie kategorická v dané mohutnosti, Los-Vaughtovo kriterium úplnosti. Morleyova věta (bez důkazu).
    • Souběžná bezespornost. Craig-Robinsonova věta, Robinsonova věta o souběžné bezespornosti, (Craigův) interpolant formulí.
    • Implicitní a explicitní definovatelnost formulí.

 

VOLITELNÉ PŘEDMĚTY

  1. Algoritmy a rekurzívní funkce

    • Definice (částečně, primitivně) rekurzívních funkcí, definice rekurzívně spočetných a (primitivně) rekurzívních množin a relací (predikátů) jako základní matematické zpřesnění pojmu algoritmus. Odvozené operace s funkcemi a množinami, dvojná (ordinální) rekurze.
    • Některé výpočtové modely jiné než částečně rekurzívní funkce. Turingovy stroje, vývojové diagramy, jednoduchý vyšší programovací jazyk. Jejich vzájemná ekvivalence, Churchova teze.
    • Aritmetizace odvození a výpočtů, věta o normální formě, enumerace částečně rekurzívních funkcí a rekurzívně spočetných množin.
    • Diagonální metoda. Rekurzívní funkce nebo množiny, které nejsou primitivně rekurzívní. Rekurzívně spočetné množiny, které nejsou rekurzívní. Problém zastavení. Pojem univerzální funkce.
    • Věta o projekci. Souvislosti mezi rekurzívností funkce a rekurzívností jejího grafu. Ekvivalentní definice rekurzívně spočetných množin. Postova věta. Uzavřenost tříd PR, OR a RE na operace.
    • Věta o parametrech, m-převeditelnost, m-kompletnost, m-kompletnost problému zastavení. Produktivní a kreativní množiny. Kreativnost m-kompletních množin.
    • Věta o rekurzi. Riceova věta. m-kompletnost kreativních množin.
    • Imunní množiny. Prosté (simple) množiny jako příklad množin, které nejsou m-kompletní.
    • Aritmetická hierarchie, P2-kompletní množiny.
    • 1-převeditelnost, 1-kompletnost, cylindry.

  2. Filosofická logika

    • otázky v zip formatu zde; jejich podoba se může průběžně měnit!

  3. Booleovy algebry

    Podle skript k přednášce Booleovy algebry (včetně volitelných sekcí). Ke stažení na stránce Radka Honzíka. Tento předmět předpokládá znalost relevantních částí také z přednášky Úvod do teorie modelů.

  4. Dějiny logiky

    • otázky v zip formatu zde; jejich podoba se může průběžně měnit!

  5. Neklasické logiky

    • Modální logiky - Kripkovská sémantika, normální modální logiky. Definovatelnost a nedefinovatelnost tříd rámců modálními a prvořádovými formulemi – porovnání, příklady. Pojem morfismu rámců a bisimulace, vlastnosti. Vztah modální výrokové logiky ke klasické prvořádové logice - standardní překlad.
    • Modální logiky – Kripkovská sémantika, dva typy sémantického důsledku. (Silná) úplnost výrokových modálních logik (předveďte na příkladu vybrané logiky) – kanonický model, vlastnost konečných modelů (protipříkladů), rozhodnutelnost. Vztah modální výrokové logiky ke klasické prvořádové logice - standardní překlad.
    • Intuicionistická výroková logika – Kripkovská a algebraická sémantika a jejich vzájemný vztah, pro obě sémantiky příklady modelů (resp. protipříkladů), úplnost. Interpretace intuicionistické výrokové logiky v modální logice S4.
    • Intuicionistická (predikátová) logika – L. E. J. Brouwer, A. Heyting, A. N. Kolmogorov (BHK) interpretace, filosofická východiska. Hilbertovský kalkul, fragmenty, přípustná pravidla. Kripkovská sémantika, příklady modelů, platných a neplatných formulí, úplnost. IL s rovností.
    • Intuicionistická (predikátová) logika a metamatematika – Kripkovská sémantika, vlastnost disjunkce. Vztah intuicionistické logiky ke klasické logice (Glivenkova věta, dvojnegační překlad). IL s rovností. Heytingova aritmetika, vlastnost disjunkce, de Jonghova věta.
    • Substrukturální logiky – strukturální pravidla, motivace pro jejich přijetí/odmítnutí. Vyberte si jednu z následujících možností, předveďte na příkladu vybrané substrukturální logiky:
      1. Algebraická sémantika axiomatických rozšíření Full Lambekova kalkulu – residuované svazy, algebraické ekvivalenty strukturálních pravidel, úplnost.
      2. Pro distributivní logiky – relační sémantika, charakteristické podmínky odpovídající strukturálním pravidlům, úplnost.

  6. Neúplnost a nerozhodnutelnost

    • Syntax a sémantika klasické predikátové logiky. Korektnost a úplnost kalkulů, kompaktnost. Rekurzívní a rekurzívně spočetné množiny. Postova věta, m-převeditelnost, m-kompletnost.
    • Axiomatické teorie a jejich vlastnosti, bezespornost, úplnost. Metody prokazování úplnosti konkrétních teorií, Vaughtův test. Rozhodnutelné a nerozhodnutelné teorie, Craigova věta o rekurzívní axiomatizovatelnosti, rozhodnutelnost konečného rozšíření rozhodnutelné teorie.
    • Robinsonova a Peanova aritmetika, příklady tvrzení dokazatelných a nedokazatelných v Robinsonově aritmetice, S-úplnost Robinsonovy aritmetiky, příklady tvrzení dokazatelných v Peanově aritmetice, existence nestandardních modelů, jiné metamatematické vlastnosti obou teorií.
    • Definovatelné množiny v nějaké struktuře, definovatelné množiny ve standardním modelu aritmetiky, aritmetická hierarchie.
    • První Gödelova věta, S-korektní teorie, neúplnost a nerozhodnutelnost S-korektních rozšíření Robinsonovy aritmetiky, produktivní a kreativní množiny.
    • Rosserovo zobecnění První Gödelovy věty, (efektivně) rekurzívně neoddělitelné dvojice množin - definice a některé vlastnosti.
    • Věta o autoreferenci, tj. Gödelovo diagonální lemma, některá užití: neexistence formální definice pravdy, klasický důkaz První Gödelovy věty.
    • Druhá Gödelova věta, význam, Hilbertův program.
    • Intuicionistická logika, kripkovská sémantika, kalkuly a jejich korektnost, interpretace klasické logiky v intuicionistické.

  7. Teorie množin

    Podle skript k přednášce Teorie množin (včetně volitelných sekcí) a Modely teorie množin (včetně volitelných sekcí). Ke stažení na stránce Radka Honzíka.

  8. Teorie modelů

    • Ultraprodukt a splňování v něm.
    • Model teorie. Věta o úplnosti, konstrukce modelu bezesporné teorie pomocí úplného Henkinova rozšíření dané teorie.
    • Elementární ekvivalence. Elementárně ekvivalentní struktury, elementární podstruktury a extenze, Tarského test, elementární vnoření, algebraická charakterizace elementární ekvivalence.
    • Axiomatizovatelné třídy, konečně axiomatizovatelné třídy.
    • Lowenheim-Skolem-Taského věty o existenci modelů daných mohutností.
    • Úplnost a kategoričnost. Charakterizae úplnosti dané teorie pomocí elementární ekvivalence jejích modelů, teorie kategorická v dané mohutnosti, Los-Vaughtovo kriterium úplnosti. Morleyova věta (bez důkazu).
    • Souběžná bezespornost. Craig-Robinsonova věta, Robinsonova věta o souběžné bezespornosti, (Craigův) interpolant formulí.
    • Implicitní a explicitní definovatelnost formulí.

  9. Teorie racionálního usuzování

    • Logické programy. Definice logických programů, klauzule, Hornovy klauzule, substituce otázky, unifikace, unifikační algoritmus a jeho vlastnosti.
    • Herbrandovy modely logických programů. Herbrandova věta, Herbrandův model. Užití Herbrandovy věty pro strojové dokazování.
    • Robinsonův rezoluční princip. SLD rezoluce. Negace jako neúspěch (negation-as-failure). Poblém výskytu termu.
    • Logika defaultů. Reiterova logika, uzavřené defaulty, pojem extenze, minimalita extenzí, ortogonalita extenzí, seminormální a normální defaulty.
    • Cirkumscriptivní logiky. Modely a jejich sémantická omezení, stabilní množiny. Sémantika možných světů pro autoepistemické logiky.
    • Usuzování z neúplných znalostí. Revize přesvědčení, expanze, kontrakce a revize teorií. Postuláty racionality (podle P. Gärdenforse).

  10. Výpočtová složitost