Final exams

All forms of study (i.e. undergraduate, graduate and postgraduate) require the student to pass a comprehensive formal exam. For the undergraduate and graduate programs this exam takes place at the end together with the thesis defense. In the postgraduate programs, students usually take the exam in the second year of their studies. The links below lead to more details.

Bachelor exam (Bachelor Degree)

State final exam (Masters Degree)

State doctoral exam (PhD Degree)


Bachelor exam

Every student in the bachelor program is required to pass the Bachelor exam in the last year of his studies. The exam consists of bachelor thesis defense followed by an oral exam. The defense should not exceed 20 minutes and is started by a presentation of the thesis by the student; in case students would like to take advantage of the projector for their presentation, it is advisable to contact the secretary in advance to make necessary preparations. The oral exam only takes place in case of successful defense.

The oral exam consists of three parts, each of which should not exceed 20 minutes. The subject of the first part is Logic, the remaining parts focus on two distinct topics chosen by the student from among the following:  Set theoryModal logicComputabilityAnalytical philosophyStructures and algebra. Requirements for the different topics are listed below.

Students apply to take the bachelor exam after or close to passing all credit and other requirements. The deadlines for applications are set by the faculty and the applications are handled by the SIS. Bachelor theses need to be uploaded electronically to the SIS by the deadline set by the department.  This deadline is typically later than the faculty deadline for exam applications. The exam application is conditional and is binding only after thesis submission. We kindly ask the students to inform the head of the department via e-mail ahead of time of their intention to apply for bachelor exams so that necessary planning can take place and so that a date for the exam can be set (otherwise, in particular for the February terms, the department might not set a date at all).

Exam requirements

Below we list typical requirements sorted according to topics.

Some basic notions are required regardless of the chosen topics, e.g. tautologies, satisfiable formula, logically valid formula, entailment, disjunctive and conjunctive normal form, prenex normal form, the deduction theorem, axiomatical theory, model, recursively enumerable and recursive sets, Post's theorem, functions, relations and their properties, groups, rings, ordinal and cardinal numbers.

Note that it is always advisable to check with the department the current list of topics.

Typical requirements (in Czech):

Logic

  • Syntax a sémantika, logické kalkuly a jejich vlastnosti
  • Věta o kompaktnosti a její důsledky, axiomatizovatelné a konečně axiomatizovatelné třídy struktur
  • Vlastnosti axiomatických teorií: bezespornost, úplnost, rozhodnutelnost, konečná axiomatizovatelnost, rekurzívní axiomatizovatelnost; vztahy mezi nimi
  • Eliminace kvantifikátorů, definovatelné množiny
  • Robinsonova a Peanova aritmetika: modely, ekvivalentní axiomatizace, S-úplnost; společné vlastnosti a vlastnosti, kterými se obě teorie liší
  • Definovatelné množiny ve struktuře N přirozených čísel; slabá varianta První Gödelovy věty jako důsledek faktu, že Th(N) je nearitmetická množina
  • S-korektní teorie, První Gödelova věta a její strukturální důkaz
  • Rosserova věta: znění, porovnání s První Gödelovou větou, myšlenka důkazu
  • Věta o autoreferenci, klasický důkaz První Gödelovy věty
  • Druhá Gödelova věta, význam, Hilbertův program; Löbovy podmínky pro dokazatelnost
  • Intuicionistická logika, její kripkovská sémantika a kalkuly, vztah k logice klasické

Set theory

Požadavky odpovídají skriptům z přednášek teorie množin (první a druhý semestr; jeden soubor), které lze stáhnout na stránce Radka Honzíka v aktuální verzi.

  • Axiomy teorie množin (ZFC)
  • Cantorova věta, Cantor-Bernsteinova věta
  • Věta o počtu reálných čísel (R má stejnou velikost jako potence omega)
  • Axiom výběru a jeho ekvivalenty (Princip maximality, Princip dobrého uspořádání)
  • Základní vlastnosti ordinálních čísel
  • Transfinitní indukce, definice fundovaného univerza rekurzí
  • Ordinální aritmetika
  • Kardinální čísla a kardinální aritmetika, GCH
  • Regulární a singulární kardinály, kofinalita

Modal logics

  • Kripkovská sémantika, pojem normální modální logiky; definovatelnost a nedefinovatelnost tříd rámců modálními a prvořádovými formulemi - porovnání, příklady (v základním modálním jazyce a temporálním modálním jazyce)
  • Pojem morfismu rámců a bisimulace modelů, vlastnosti (zachování platnosti formulí); aplikace v důkazech o nedefinovatelnosti tříd rámců nebo modelů modálními formulemi
  • Vztah modální výrokové logiky ke klasické prvořádové logice - standardní překlad, vlastnosti, použití (např. věta o kompaktnosti)
  • Kripkovská sémantika, dva typy sémantického důsledku a jejich rozlišení. Silná korektnost hilbertovských kalkulů (logiky K a alespoň jednoho jejího rozšíření)
  • Silná úplnost výrokových modálních logik (logika K a alespoň jedno její rozšíření) - kanonický model; příklad modální logiky, která není kompaktní, a tedy silně úplná
  • Úplnost pomocí konečného modelu - vlastnost konečných modelů (protipříkladů), rozhodnutelnost (logiky K a alespoň jednoho jejího rozšíření)

Computability

  • 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, například vývojové diagramy, 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ě spočetné množiny, které nejsou rekurzívní; problém zastavení; pojem univerzální funkce; částečně rekurzívní funkce, která nemá žádné rekurzívní prodloužení
  • 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
  • Aritmetická hierarchie, P2-kompletní množiny

Analytical philosophy

  • Fregeho základní sémantické distinkce
  • Russellův koncept přímé reference a jeho teorie deskripcí
  • Strawsonova teorie deskripcí, pojem presupozice, Donnellanova distinkce
  • Deskriptivistické teorie jmen (Frege, Russell, Strawson, Searle)
  • Kauzální teorie jmen (Kripke)
  • Spor externalismu a internalismu ve filosofii jazyka a mysli (Putnam, Burge, Searle)

Structures and algebra

Požadavky odpovídají skriptům z přednášek Úvod do teorie modelů a Booleovy algebry, které lze stáhnout na stránce Radka Honzíka v aktuální verzi.

  • Pojem struktury, porovnávání struktur (morfismy, vnoření, isomorfismum, elementární ekvivalence)
  • Löwenheim-Skolemovy věty, elementární vnoření, elementární extenze
  • Kategoričnost teorií (Morleyho věta, jen znění)
  • Ultraprodukt, ultramocnina
  • Užití ultraproduktové konstrukce: kompaktnost a elementární třídy struktur
  • Pojem grupy, okruhu a tělesa; Lagrangeova věta (řád podgrupy dělí řád konečné grupy)
  • Částečná uspořádání a svazy (základní pojmy, algebraická a množinová definice svazu)
  • Booleovy algebra, definice, základní vlastnosti
  • Příklady konstrukcí Booleových algeber - Clopen algebra topologického prostoru (Cantorův prostor), Lindenbaum-Tarského algebry
  • Nekonečné operace na Booleových algebrách
  • Pojem regulární podalgebry
  • Věty o reprezentaci (Stoneova věta, Stoneova dualita)

State final exam

Passing the State Final Exam is a requirement for finishing the Master's program. The exam consists of two parts, both of which must be passed. The first part is the thesis defense. Provided the student passes this part, he can continue to the next part which is an oral exam.

The oral exam consists of an  exam focusing on Classical Logic and two exams focusing on two distinct topics chosen by the student from the following: Set theoryPhilosphy of logic and languageNonclassical logicModel theoryComputational complexityProof theoryArtificial intelligenceTheory of recursive functions and setsGeneral linguistics.

Technical and organizational details are the same as for the Bachelor Exam.

Note that it is always advisable to check with the department the current list of topics.

Typical requirements (in Czech):

Exam requirements

(according to topics)

Classical logic

  • 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é

Set theory

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

Philosophy of language

  • 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ů

Nonclassical logic

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

Model theory

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

Computational complexity

Requirements are listed in a separate document.

Proof theory

  • 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

Artificial intelligence

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ů

Recursive functions and sets

  • 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

General linguistics

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


State doctoral exam

Successfuly passing the state doctoral exam (together with a successful dissertation defense) is a necessary requirement for completing the postgradual program and obtaining a PhD. The faculty has some general requirements applicable to all fields of study.

The state doctoral exam consists of three parts which are chosen by the advisor in coordination with the department board.