Filozofická Fakulta

Katedra logiky

Studentské hodnocení výuky

Aktuality

There are not any news

Státní závěrečná zkouška, volitelné předměty, přihláška

Státní závěrečná zkouška (SZZk) zakončuje magisterské studium. Obhajoba magisterské práce je součástí SZZk a předchází ústní část SZZk.

Ústní část SZZk sestává ze zkoušky z tématického okruhu Klasická logika a ze zkoušky ze dvou volitelných tématických okruhů. Volitelnými okruhy pro nástupní ročník 2009/10 nebo pozdější jsou Teorie množin a její modely, Filosofie logiky a jazyka, Neklasické logiky, Teorie modelů, Výpočtová složitost, Teorie důkazů, Umělá inteligence, Teorie rekurzívních funkcí a množin, Obecná jazykověda.

O organizaci a průběhu zkoušky, termínech přihlášky a podání práce a o sdělení předběžných informací platí totéž, co je řečeno k BZk.

Požadavky k SZZk

Klasická logika

  • Vlastnosti logických kalkulů; kvantitativní aspekty, souvislosti s rekurzívně spočetnými množinami a s otevřenými problémy ve výpočtové složitosti
  • Věta o kompaktnosti a její důsledky; axiomatizovatelné (tj. elementární) třídy struktur, konečně axiomatizovatelné třídy struktur; existence a struktura nestandardních modelů Peanovy aritmetiky
  • Vlastnosti axiomatických teorií: bezespornost, úplnost, rozhodnutelnost, konečná axiomatizovatelnost, rekurzívní axiomatizovatelnost; vztahy mezi nimi
  • Eliminace kvantifikátorů, definovatelné množiny
  • První Gödelova věta, Rosserova věta a jejich strukturální důkaz; souvislosti s aritmetickou hierarchií a s efektivně nerekurzívními množinami
  • Autoreference; vlastnosti Gödelovy, Rosserovy a Henkinovy sentence, formalizovatelnost těchto vlastností v Peanově aritmetice PA
  • Důležité axiomatické teorie: PA, Q, ZF a GB (nověji též označovaná NBG), případně MK (Morse‑Kelley); vlastnosti těchto teorií, možnost a nemožnost konečné axiomatizovatelnosti
  • Druhá Gödelova věta, význam, Hilbertův program; Löbovy podmínky pro dokazatelnost, jejich platnost a jejich další aplikace, například formalizovaná verze Druhé Gödelovy věty
  • Základy logiky dokazatelnosti, její aplikace
  • Intuicionistická logika, její kripkovská sémantika a kalkuly, vztah k logice klasické

Teorie množin a její modely

Doporučujeme kontaktovat zkoušejícího (R. Honzík) a ověřit témata ke zkoušce (předmět je pokročilejšího charakteru a v různých ročnících se může trochu lišit). K dispozici jsou sktripta (kontaktujte R. Honzíka).

  • Vše jako pro bakalářskou zkoušku plus následující:
  • V-hierarchie a H-hierarchie, základní vztahy a vlastnosti
  • Fundovaná transfinitní rekurze, Mostowského kolaps
  • Princip reflexe a jeho užití (ZF není konečně axiomatizovatelná)
  • Tranzitivní třídy jako modely, interpretace (užití: equikonzistence (ZF bez fundovanosti) a ZF)
  • Kombinatorika: club filtr, stacionární množiny, stromy

Filosofie logiky a jazyka

  • Fregeho základní sémantické distinkce
  • Teorie deskripcí (Russell, Strawson, Donnellan)
  • Teorie jmen (Frege, Russell, Strawson, Searle, Kripke)
  • Externalistická a internalistická konstrukce propozice (Putnam, Burge, Searle)
  • Griceova intencionální sémantika a jeho teorie implikatur
  • Davidsonova teorie významu a interpretace
  • Searlova teorie mluvních aktů

Neklasické logiky

jako Modální Logiky pro BZK plus:

  • Sémantika intuicionistické výrokové i predikátové logiky, vztah intuicionistické a klasické logiky, výrokové i predikátové (Glivenkova věta, dvojnegační překlad)
  • Úplnost intuicionistické výrokové a predikátové logiky a její důsledky (rozhodnutelnost výrokové IL, velikost modelu v případě predikátové IL, vlastnost disjunkce a existence)
  • Heytingova aritmetika a její vlastnosti (vlastnost disjunkce a existence, vztah k Peanově aritmetice, de Jonghova věta, rozhodnutelnost některých formulí)
  • Algebraická sémantika intuicionistické výrokové logiky, silná úplnost
  • Dualita algebraické a kripkovaké sémantiky intuicionistické nebo modální výrokové logiky
  • Substrukturální logiky: vymezení třídy logik, algebraická a případně i kripkovská sémantika, teorie důkazů. Vybraná substrukturální logika a její vlastnosti

Teorie modelů

Doporučujeme kontaktovat zkoušejícího (J. Verner) a ověřit témata ke zkoušce.

  • základní nástroje: podstruktury, homomorfizmy, elementární vnoření, elementární ekvivalence, diagram, elementární řetěz, Tarského test, ...
  • Löwenheimovy–Skolemovy–Tarského věty, Łośův–Vaughtův test
  • definovatelné množiny, typy
  • saturované modely, univerzální modely (existence lambda-saturovaných modelů)
  • prime modely (věta o pomíjení typů, nezávislé množiny)
  • Morleyův rank
  • stabilita a Morleyova věta o kategoričnosti

Výpočtová složitost

Požadavky ke zkoušce jsou v samostatném dokumentu.

Teorie důkazů

  • Kalkuly přirozené dedukce klasické a intuicionistické predikátové logiky, vztah k hilbertovským a/nebo sekventovým kalkulům (vzájemná simulace)
  • Věta o normalizaci, důkaz pro intuicionistickou a klasickou logiku
  • Věta o normalizaci, struktura normálních důkazů a aplikace věty o normalizaci
  • Sekventové kalkuly klasické a intuicionistické logiky, jejich strukturální varianty, varianta G3 a přípustnost pravidel oslabení a kontrakce
  • Věta o eliminovatelnosti řezu, důkaz, vlastnosti bezřezových důkazů a aplikace věty o eliminaci řezu

Umělá inteligence

Doporučujeme kontaktovat zkoušejícího (M. Peliš, J. Verner) a ověřit témata ke zkoušce.

  • Reprezentace znalostí v logice
    Epistemické logiky, Dynamické logiky a programy, Dynamické epistemické logiky - změny znalostí a stavů (PAL, AM), Logika otázek
  • Modely usuzování v logice
    "B쾞né / přirozené" usuzování, Klasická relace důsledku (reflexivita, kumulativní tranzitivita, monotonie), Supraklasická a paraklasická relace důsledku, Způsoby rozššíření klasické relace důsledku (dodatečné předpoklady, omezení modelů, dodatečná pravidla
  • Nemonotonní logiky
    Dodatečné předpoklady, Omezování třídy modelů, Dodatečná pravidla Nemonotonní epistemické logiky
  • Logika defaultù
    Operaèní sémantika, Normální a semi-normální teorie
  • Teorie rozhodování a teorie her
    Dolování z dat (data mining), Hra (normální a explicitní tvar), optimální řeššení (Nash equilibrium), individuální a skupinová racionalita
  • Prohledávání stavového prostoru
    lokální (genetické algoritmy, simulované žíhání, ...), globální algoritmy (A*, ...)
  • Constraint Satisfaction Problem
    constraint propagation, SAT, back-tracking, back-jumping
  • Strojové učení
    Bayesovské sítě, rozhodovací stromy, neuronové sítě (matematický model neuronu, Hopfieldovy sítě, učící algoritmus backpropagation)
  • Zpracování obrazu
    detekce objektů (hran, tvarů, ...), rozpoznávání objektů

Teorie rekurzívních funkcí a množin

  • 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, věta o normální formě; Churchova teze
  • 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 RS 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) případně hyperprosté (hypersimple) množiny jako příklad množin, které nejsou m-kompletní
  • Aritmetická hierarchie, P2-kompletní množiny
  • 1-převeditelnost, 1-kompletnost, cylindry

Obecná jazykověda

  • Funkce jazyka. Pojem jazykového znaku, jeho vlastnosti. Arbitrárnost jazykového znaku. Jazyk mluvený a psaný: odlišnosti. Písmo a grafický znak v jazyce.
  • Vnější lingvistika — vnější vazby jazykovědy. Jazykové společenství: typ, variety, postoje, situace. Jazyková politika a kultura, bilingvismus, zdvořilost, malé jazyky. Jazyk a vědomí: psycholingvistika. Jazyk a etnikum: etnolingvistika, antropolingvistika. Jazyk a mozek: neurolingvistika, biolingvistika.
  • Původ a vývoj jazyka. Ontogeneze a fylogeneze jazyka. Jazyková divergence, jazykový kontakt. Fylogeneze jazyka — vznik a vývoj jazyka. Teorie vzniku jazyka. Fylogeneze a princip jazykové změny. Fonetické změny. Vývoj slovní zásoby. Vývoj gramatiky. Diferenciační a integrační tendence v jazyce. Klasifikace jazyků. Typologická klasifikace jazyků světa. Genetická klasifikace jazyků. Jazykové univerzálie.
  • Fonetika artikulační (organogenetická) a akustická. Samohlásky, souhlásky, sonanty. Způsob a místo artikulace. Orgány. Slabika.
  • Fonologie. Teorie fonologických opozic. Struktura promluvy a jednotky jazyka. Segmentální a suprasegmentální jednotky.
  • Morfologie a morfematika přirozených jazyků. Pojem morf, alomorf, morfém. Morfém lexikální a gramatický. Alomorfy prvního a druhého řádu. Alternace prvního a druhého řádu. Derivační a flektivní morfologie. Morfologická homonymie a synonymie. Morfonologické změny. Gramatické kategorie. Gramatikalizace. Problém automatického zpracování morfologie.
  • Struktura jazyka — vnitřní lingvistika. Syntagmatika a paradigmatika. Strukturní lingvistika. Struktura a systém, langue/parole. Jazyková diachronie a synchronie. Formy a funkce ve struktuře jazyka. Stratifikační popis jazyka. Homonymie a synonymie jako vztah forem a funkcí.
  • Pojem slova z různých hledisek.
  • Syntax přirozeného jazyka. Různé typy syntaktické struktury (závislostní, bezprostředněsložková, kategoriální). Syntaktické vztahy. Valenční a generativní syntax. Aktuální členění věty. Syntaktická homonymie a synonymie v přirozených jazycích. Syntaktická analýza a syntaktická syntéza. Problémy automatického zpracování syntaxe.
  • Lexikon: Nominace, slovní druhy, autosémantika a synsémantika. Paradigmatika a syntagmatika lexikonu. Frazémy a idiomy. Lexikologie, slovní zásoba a její systém. Lexikografie.
  • Sémantika přirozeného jazyka. Lexém, věta a výpověď. Paradigmatika a syntagmatika významu.
  • Pragmatika přirozeného jazyka.