Filozofická Fakulta

Katedra logiky

Studentské hodnocení výuky

Aktuality

Výuka Klasické logiky I 16. a 17.10. z důvodu pracovní cesty odpadá. M. Bílková.

15. říjen 2017

byla umluvena na Pondělí 14:10 do učebny 119b. První přednáška proběhne v pondělí 9. října.

06. říjen 2017

začínají až ve Čt 12.10. (učebna 137, 15:00).
04. říjen 2017

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.