Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Vyčíslitelnost a matematická logika

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
01VYML ZK 4 4+0 česky
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra matematiky
Anotace:

Pojem algoritmu, algoritmicky vyčíslitelné funkce a algoritmicky definovatelné množiny a jejich klasické matematické formulace. Teorie rekurze. Klasická výroková a predikátová logika. Aplikace teorie rekurze na logiku.

Požadavky:
Osnova přednášek:

Algoritmy a algoritmicky vyčíslitelné funkce, Markovovy normální algoritmy, Turingův stroj, rekurzívní funkce, rekurzívní a rekurzívně spočetné množiny a predikáty, s-m-n teorém, produktivní a kreativní množiny, algoritmicky neřešitelné problémy. Výroky, tautologie, axiomy, teorémy, korektnost, úplnost a rozhodnutelnost výrokového kalkulu. Relační struktury, jazyk predikátového kalkulu, termy, formule, axiomy, teorémy, splňování, pravdivost, tautologie, korektnost, konstrukce modelu, Gödelova věta o úplnosti, nerozhodnutelnost predikátového kalkulu, rezoluční metoda.

Osnova cvičení:
Cíle studia:

Znalosti:

Teorie rekurze jakožto matematické precizace intuitivního pojmu algoritmu a s používanými finitními a konstruktivními metodami. Základní výsledky klasické logiky.

Schopnosti:

Orientace ve specifické oblasti finitního popisu funkcí a množin a v klasické výrokové a predikátové logice.

Studijní materiály:

Povinná literatura:

[1] J. Mareš: Teorie vyčíslitelnosti. Skripta. Vydavatelství ČVUT, Praha 2008.

[2] J. Mareš: Matematická logika. Skripta. Vydavatelství ČVUT, Praha 2009.

Doporučená literatura:

[3] A. Sochor: Klasická matematická logika. Karolinum, Praha 2001.

[4] V. Švejdar: Logika - neúplnost, složitost a nutnost. Academia, Praha 2002.

[5] Z. Manna: Matematická teorie programů. SNTL, Praha 1981.

Poznámka:
Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 7. 8. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet13405.html