Detail předmětu

Matematická logika

FSI-SMLAk. rok: 2016/2017

V předmětu budou systematicky vyloženy základy výrokové a predikátové logiky. Nejprve budou studenti seznámeni se syntaxí a sémantikou těchto logik, pak budou logiky studovány jako formální teorie s důrazem na problematiku dokazování formulí. Prodiskutovány budou také klasické věty o korektnosti, úplnosti a kompaktnosti. Po probrání převodu formulí na prenexní tvar budou uvedeny některé vlastnosti a modely teorií 1. řádu. Pozornost bude také věnována nerozhodnutelnosti teorií 1. řádu vyplývající ze známých Gödelových vět o neúplnosti.

Jazyk výuky

čeština

Počet kreditů

Garant předmětu

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

Ústav matematiky (ÚM)

Výsledky učení předmětu

Po absolvování předmětu získají studenti schopnost chápání principů axiomatických matematických teorií i schopnost přesného (formálního) matematického vyjadřování. Naučí se také formálně odvozovat nové formule a dokazovat formule dané. Uvědomí si efektivitu formálního uvažování, ale také jeho hranice.

Prerekvizity

Předpokládá se znalost předmětů Obecná algebra a Metody diskrétní matematiky z balkalářského studia.

Plánované vzdělávací činnosti a výukové metody

Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách.

Způsob a kritéria hodnocení

Zápočet bude udělen na základě aktivní účasti ve cvičení a úspěšného složení písemného testu v půli semestru. Zkouška proběhne písemnou formou na konci semestru.

Učební cíle

Cílem předmětu je seznámit studenty se základními metodami uvažování v matematice. Studenti by si měli osvojit obecné principy predikátové logiky a získat tak schopnost přesného matematického uvažování a vyjadřování. Také by se měli naučit pracovat s některými dalšími důležitými formálními teoriemi využívanými v matematice a informatice.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Bude kontrolována účast na cvičeních.

Základní literatura

A. Nerode, R.A. Shore, Logic for Applications, Springer-Verlag 1993 (EN)
E.Mendelson, Introduction to Mathematical Logic, Chapman&Hall, 2001 (EN)

Doporučená literatura

J.Rachůnek, Logika, skriptum PřF UP Olomouc, 1986 (CS)

Zařazení předmětu ve studijních plánech

  • Program M2A-P magisterský navazující

    obor M-MAI , 1 ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

1. Úvod do matematické logiky
2. Výroky a jejich pravdivost, logické spojky
3. Jazyk, formule a sémantika výrokové logiky
4. Princip duality, aplikace výrokové logiky
5. Formální systém výrokové logiky
6. Dokazatelnost ve výrokové logice, věta o úplnosti
7. Jazyk predikátové logiky, termy a formule
8. Sémantika predikátové logiky
9. Formální systém predikátové logiky 1. řádu
10. Dokazatelnost v predikátové logice
11. Věta o úplnosti a o kompaktnosti, prenexní tvar formulí
12.Teorie 1. řádu a jejich modely
13.Nerozhodnutelnost teorií prvního řádu, Gödelovy věty o neúplnosti

Cvičení

26 hod., povinná

Vyučující / Lektor

Mgr. Jan Pavlík, Ph.D.

Osnova

1. Relační systémy a univerzální algebry
2. Množiny, kardinální čísla a kardinální aritmetika
3. Výroky, výrokové spojky, pravdivostní tabulky, tautologie a kontradikce
4. Nezávislost logických spojek, axiomy výrokové logiky
5. Věta o dedukci a dokazování formulí výrokové logiky
6. Termy a formule predikátové logiky
7. Interpretace, splnitelnost a pravdivost
8. Axiomy a odvozovací pravidla predikátové logiky
9. Věta o dedukci a dokazování formulí v predikátové logice
10.Převody formulí na prenexní tvar
11.Teorie 1. řádu a jejich modely
12.Monadické logiky SkS a WSkS
13.Intuicionistická, modální a temporální logika, Presburgerova aritmetika