Detail předmětu

Matematická logika

FP-VmlPAk. rok: 2014/2015

V předmětu budou systematicky vyloženy základy výrokové a zejména 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. Závěrem předmětu bude pojednáno o některých dalších významných logikách, které nacházejí uplatnění v matematice a informatice.

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

Ústav informatiky (ÚI)

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

Dvouhodinová přednáška a dvouhodinové cvičení. Přednáška kombinující teorii a ilustrativní řešené příklady. Cvičení jsou zaměřená na zvládnutí početních úloh.

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 199... (EN)
E.Mendelson, Introduction to Mathematical Logic, Chapman&Hall, 200... (EN)
G. Metakides, A. Nerode, Principles of logic and logic programming... (EN)
J. Rachůnek, Logika, skriptum PřF UP Olomouc, 1986 (CS)
Vítězslav Švejnar, Logika - neúplnost,složitost a nutnost, Academi... (CS)

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 BAK-KME bakalářský

    obor BAK-MME , 3 ročník, letní semestr, povinně volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

1. Základy teorie množin a kardinální aritmetiky
2. Jazyk, formule a sémantika výrokové logiky
3. Formální systém výrokové logiky
4. Dokazatelnost ve výrokové logice, věta o úplnosti
5. Jazyk predikátové logiky, termy a formule
6. Sémantika predikátové logiky
7. Formální systém predikátové logiky 1. řádu
8. Dokazatelnost v predikátové logice
9. Věta o úplnosti a o kompaktnosti, prenexní tvar formulí
10.Teorie 1. řádu a jejich modely
11.Nerozhodnutelnost teorií prvního řádu, Gödelovy věty o neúplnosti
12.Teorie 2. řádu (monadická logika, SkS a WSkS)
13.Některé další logiky (intuicionistická, modální a temporální logika, Presburgerova aritmetika)

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