Filozofická Fakulta

Katedra logiky

Studentské hodnocení výuky

Aktuality

The traditional festive meeting of the department & friends of logic will take place...

11. prosinec 2017

jsou z důvodu dovolené sekretariát a knihovna uzavřeny

11. prosinec 2017

V současné době přecházíme na nové stránky http://logic.ff.cuni.cz, které jsou primárně v...

29. listopad 2017

Složení státní doktorské zkoušky je (spolu s obhajobou disertační práce) klíčovou podmínkou úspěšného zakončení postgraduálního studia a získání titulu PhD. Obecné podmínky platné na FF UK naleznete zde.

 Seznam tematických okruhů ke státní závěrečné doktorské zkoušce

Státní doktorská zkouška z logiky sestává ze tří předmětů, z nichž dva jsou z předem připraveného seznamu (přičemž spadá-li první do skupiny (A), je druhým povinně Filosofie logiky, zatímco spadá-li do skupiny (B), je druhým povinně Matematická logika, třetí pak  může být vybrán podle zaměření doktorandovy disertační práce; to vše po domluvě a na návrh školitele; volba všech tří předmětů je schvalována oborovou radou

(A) Matematická logika

Matematická logika 
Axiomatické teorie a jejich vlastnosti: bezespornost, úplnost, rozhodnutelnost, k-kategoričnost. Základy teorie modelů, Löwenheim-Skolemovy věty. Základy teorie množin; různé axiomatizace, axiom výběru. Peanova a Robinsonova aritmetika, Gödelovy věty o neúplnosti a jejich důsledky. Rekurzívní a rekurzívně spočetné množiny.   

Algoritmy a rekurzívní funkce 
Výpočtové modely. Rekurzívní a rekurzívně spočetné množiny. Věta o normální formě a věta o parametrech. M-převeditelnost a m-kompletnost. Aritmetická hierarchie. Produktivní a kreativní množiny, (efektivně) rekurzívně neoddělitelné množiny. Věta o rekurzi. Cylindry, 1-převeditelnost. Algoritmy s orákulem. Friedberg-Mučnikova věta. 

Neúplnost a nerozhodnutelnost 
Vlastnosti axiomatických teorií: bezespornost, úplnost, rozhodnutelnost,`kategoričnost. Souvislost mezi nimi. Axiomatizovatelné třídy, kompaktnost. Eliminace kvantifikátorů, definovatelné množiny. Interpretovatelnost. Rozhodnutelnost struktury realných čísel. Peanova a Robinsonova aritmetika. Aritmetická hierarchie a definovatelnost ve struktuře přirozených čísel. Různé varianty První Gödelovy věty o neúplnosti, její strukturální důkazy a důkaz založený na autoreferenci. Rosserova věta. Druhá Gödelova věta: význam a aplikace. 

Teorie množin
Ekvivalenty axiomu výběru. Ordinální a kardinální aritmetika. Nestandardní analýza (ultraprodukt a srovnání sanalýzou založenou na pojmu limity). Ramseyova věta. Silverova věta. Konečná axiomatizovatelnost různých teorií množin. Bezespornost a nezávislost axiomu fundovanosti. Fraenkel-Mostowského permutační modely. 
konstruovatelné množiny. Cohenovo rozšíření (booleovské modely). Booleovské a permutační modely. 

Teorie modelů
Podmodel, elementární podmodel, diagram, homomorfismus, vnoření, elementární vnoře ní, isomorfismus, Löwenheim-Skolemovy věty. Základní konstrukce modelů: věta o po míjení typů, elementární řetězce, Robinsonova věta o bezespornosti, skolemizace, nerozli šitelné prvky. Věta o kompaktnosti. Lindenbaumovy algebry a algebry definovatelných množin, typy. Saturova né, kompaktní, homogenní a univerzální modely. Velké a silně homogenní modely. Prvo modely a atomické modely. Ultraprodukt, elementární třídy, saturovanost ultraproduktu  regulární a dobré ultrafiltry. Stabilní teorie. Morleyova věta o nespočetné kategoričnosti. 

Výpočtová složitost 
Základní pojmy výpočtové složitosti: formalizace pojmu rozhodovací úloha, formální jazyky, Turingovy stroje, měření časové a prostorové složitosti, vztah rozhodovacích a obecných úloh. Polynomiální algoritmy,  třídy P a NP. NP-úplnost:  p-převeditelnost, NP-úplné úlohy, úloha SAT a její NP-úplnost, další NP-úplné úlohy . Obecné třídy složitosti definované omezením času či prostoru. Třídy EXP, PSPACE a polynomiální hierarchie PH, a příklady problémů v nich ležících. PCP věta (bez důkazu) a její aplikace na neaproximovatelnost některých optimalizačních úloh. Booleovská složitost: DNF, CNF, rozhodovací stromy, formule a obvody. Souvislost velikosti obvodů a časové složitosti. Pravděpodobnostní algoritmy a třída BPP, simulace polynomiálními obvody. Pojem jednosměrné funkce a příklady funkcí, které mohou být jednosměrné. 

Matematický aspekt neklasických logik 
Modální výrokové logiky a jejich kripkovská sémantika. Důkaz úplnosti pomocí charakteristického modelu a důkaz rozhodnutelnosti pomocí filtrace. Slabé modální logiky a multimodální logiky. Intuicionistická logika a její kripkovská sémantika (úplnost, rozhodnutelnost). Vícehodnotové logiky (Lukasiewiczova troj- a vícehodnotová, Kleeneho trojhodnotová, parakonzistentní čtyřhodnotová) a fuzzy logiky (různé možné varianty). Vztah nestandardních logik ke standardní logice prvního řádu. Varianty logiky druhého a vyšších řádů; lambda-kalkul. Standardní vs. henkinovská interpretace. Důkaz neúplnosti vzhledem ke standardní sémantice. (Ne)přeložitelnost logiky druhého řádu do řádu prvního. Druhořádová aritmetika a teorie množin. 


(B) Filosofická logika a informatika

Filosofie logiky 
Povaha logiky a jejího předmětu. Základní pojmy logiky a vztahy mezi nimi: pravdivost (Tarského teorie, různé názory na povahu pravdivosti a argumenty pro a proti nim), analytičnost a logičnost (problém hranic empirické/analytické a analytické/logické, vyplývání (Tarského definice, vztah k analytičnosti), dokazování (dokazatelnost jako rekonstrukce pravdivosti, Hilbertův program, Gödelův důkaz). Paradoxy a jejich důsledky (Russellův paradox a paradox lháře, důsledky Tarského teorie pravdivosti, souvislost mezi Russellovým paradoxem a Gödelovým důkazem neúplnosti). Sémantika (smysl a význam, intenze a extenze, jména vs. popisy, možné světy; hyperintenzionální a dynamické teorie významu). Logika a 'ontologie'. 

Dějiny moderní logiky 
Anticipace a pojmová východiska moderní logiky (Leibniz, Kant, Bolzano), algebra logiky (Boole, Schröder. Peirce), predikátová logika a filosofie matematiky (Frege, Dedekind), teorie množin (Cantor, Zermelo, von Neumann), teorie deskripcí a typů (Russell), axiomatismus a formalismus (Peano, Hilbert), intuicionismus a konstruktivismus (Brouwer, Heyting, Weyl), matematická logika a metamatematika (Gödel, Tarski), filosofie jazyka a vědy (Wittgenstein, Vídeňský kroužek), neklasické logiky (Lewis, Post, Lukasiewicz).  Novější vývoj logiky s ohledem na konkrétní zaměření doktoranda. 

Filosofický aspekt neklasických logik 
Základní modální výrokové logiky (K, T, S4, S5) a jejich kripkovská sémantika. Slabé modální logiky a multimodální logiky. Temporální logiky. Deontické logiky. Modální predikátová logika a problém vztahu mezi možnými světy a univerzem. Montaguova IL. TIL. Filosofické otázky kolem možných světů. Intuicionistická logika, její motivace a její kripkovská sémantika. Vícehodnotové logiky (Lukasiewiczova trojhodnotová, Kleeneho trojhodnotová, parakonzistentní čtyřhodnotová) a fuzzy logiky (různé možné varianty). Relevanční logiky a jejich sémantika. Dynamická logika a logiky založené na teorii her (Hintikkova IFL). Meze vyjadřovacích schopností logiky prvního řádu (syntaktické a sémantické). (Ne)přeložitelnost logiky druhého řádu do řádu prvního. Argumenty pro a proti přijetí logiky druhého řádu za základ matematiky. 

Logické metody pro reprezentaci znalostí a umělou inteligenci
Řešení úloh a využívání znalostí: Stavový prostor, prohledávání stavového prostoru, hry, algoritmy minimax a alfa-beta. Dokazování vět ve vztahu k řešení úloh. Rezoluční metoda, unifikace, zamítání, omezování množiny rezolvent. Metody reprezentace znalostí: predikátová logika, produkční systémy, sémantické sítě, rámce a scénáře. Nemonotónní odvozování (logika defaultů, autoepistemické logiky). Programovací prostředky pro umělou inteligenci. Automatické dokazování,  SAT, "constraint satisfaction problem". 

Matematická analýza jazyka 
Matematický popis popis přirozeného jazyka (formální jazyky a gramatiky z hlediska aplikace na přirozené jazyky, formalizace lingvistických poznatků, matematické metody užívané v lingvistice). Typy gramatik (bezprostředněsložkové, závislostní, kategoriální), morfologická a syntaktická analýza přirozených jazyků, popis syntaxe přirozených jazyků v různých systémech (stratifikační popis jazyka, popisy jazyka založené na unifikaci). Matematické metody popisu sémantiky (extenzionální, intenzionální a hyperintenzionální sémantické modely), vztah mezi sémantikou a logikou. Korpusová lingvistika (koncepce a budování jazykového korpusu, žánrová reprezentativnost korpusů, správní a textové značkování korpusů, metody  jazykového značkování korpusů, typy korpusů z různých hledisek (morfologicky/syntakticky/sémanticky anotované korpusy, paralelní korpusy, korpusy autorské, korpusy psaného a mluveného jazyka).