Vyčíslitelnost a matematická logika

Garant předmětu:

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