PředmětyPředměty(verze: 873)
Předmět, akademický rok 2020/2021
  
Výroková a predikátová logika - NAIL062
Anglický název: Propositional and Predicate Logic
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Petr Gregor, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Neslučitelnost : NAIX062
Záměnnost : NAIX062
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: G_I (05.06.2003)
Výroková logika, normální tvary formulí, predikátová logika, věty o úplnosti výrokové a predikátové logiky, prenexní tvary formulí, modely teorií 1. řádu. Meze formální metody, Gödelovy věty.
Cíl předmětu -
Poslední úprava: T_KTI (26.05.2008)

Naučit základy výrokové a predikátové logiky

Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. Petr Gregor, Ph.D. (11.10.2017)

Formou kontroly studia předmětu je zápočet a zkouška. Získání zápočtu je nutnou podmínkou pro absolvování zkoušky s výjimkou předtermínů. Zápočet udělují vyučující na jednotlivých cvičeních na základě bodového hodnocení průběžných testů, případných domácích úloh, aktivity apod. Povaha kontroly na zápočet vylučuje možnost jejího opakování.

Literatura -
Poslední úprava: RNDr. Jakub Bulín, Ph.D. (18.11.2019)
A. Nerode, R. A. Shore, Logic for Applications, Springer, 2. vydání, 1997.
P. Pudlák, Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction, Springer, 2013.
V. Švejdar, Logika, neúplnost, složitost a nutnost, Academia, Praha, 2002.
A. Sochor, Klasická matematická logika, Univerzita Karlova v Praze - Karolinum, 2001.
W. Hodges, Shorter Model Theory, Cambridge University Press, 1997.
W. Rautenberg, A concise introduction to mathematical logic, Springer, 2009.

J. Mlček, Výroková a predikátová logika, el. skripta, 2012.
P. Štěpánek, Meze formální metody, el. skripta, 2000.

Požadavky ke zkoušce -
Poslední úprava: doc. Mgr. Petr Gregor, Ph.D. (09.10.2017)

Zkouška se skládá z písemné a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že celá zkouška je hodnocena známkou nevyhověl(a) a ústní částí se již nepokračuje. Nesložení ústní části znamená, že při příštím termínu je nutno opakovat obě části zkoušky, písemnou i ústní. Výsledná známka ze zkoušky se stanoví na základě hodnocení písemné i ústní části.

Písemná část se skládá ze tří příkladů. Vzory písemné části z minulých let jsou k dispozici na stránce k přednášce.

Požadavky u ústní části zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce.

Sylabus -
Poslední úprava: doc. Mgr. Petr Gregor, Ph.D. (09.10.2017)

Výroková logika: základní syntax a sémantika, normální tvary formulí, problém splnitelnosti. Tablo metoda a rezoluce ve výrokové logice. Věta o úplnosti výrokové logiky.

Predikátová logika: základní syntax a sémantika, prenexní tvary formulí, vlastnosti a modely teorií 1. řádu. Tablo metoda a rezoluce v predikátové logice. Skolemova věta, Herbrandova věta. Věta o úplnosti predikátové logiky, kompaktnost.

Kompletnost a její kritéria, rozhodnutelnost. Meze formální metody, Gödelovy věty.

 
Univerzita Karlova | Informační systém UK