Detail předmětu
Logika
FIT-LOGAk. 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 informatice.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Studenti se naučí exaktnímu formálnímu myšlení, které jim umožní provádět korektní a efektivní algoritmizaci řešení zadaných problémů. Také získají schopnost ověřovat správnost již vytvořených algoritmizací (verifikace programů).
Prerekvizity
Způsob a kritéria hodnocení
Osnovy výuky
- Osnova přednášek:
- Základy teorie množin a kardinální aritmetiky
- Jazyk, formule a sémantika výrokové logiky
- Formální systém výrokové logiky
- Dokazatelnost ve výrokové logice, věta o úplnosti
- Jazyk predikátové logiky, termy a formule
- Sémantika predikátové logiky
- Formální systém predikátové logiky 1. řádu
- Dokazatelnost v predikátové logice
- Věta o úplnosti a o kompaktnosti, prenexní tvar formulí
- Teorie 1. řádu a jejich modely
- Nerozhodnutelnost teorií prvního řádu, Gödelovy věty o neúplnosti
- Teorie 2. řádu (monadická logika, SkS a WSkS)
- Některé další logiky (intuicionistická, modální a temporální logika, Presburgerova aritmetika)
- Relační systémy a univerzální algebry
- Množiny, kardinální čísla a kardinální aritmetika
- Výroky, výrokové spojky, pravdivostní tabulky, tautologie a kontradikce
- Nezávislost logických spojek, axiomy výrokové logiky
- Věta o dedukci a dokazování formulí výrokové logiky
- Termy a formule predikátové logiky
- Interpretace, splnitelnost a pravdivost
- Axiomy a odvozovací pravidla predikátové logiky
- Věta o dedukci a dokazování formulí v predikátové logice
- Převody formulí na prenexní tvar
- Teorie 1. řádu a jejich modely
- Monadické logiky SkS a WSkS
- Intuicionistická, modální a temporální logika, Presburgerova aritmetika
Osnova numerických cvičení:
Učební cíle
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Základní literatura
Doporučená literatura
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MBI , 0 ročník, letní semestr, volitelný
obor MBS , 0 ročník, letní semestr, volitelný
obor MIN , 0 ročník, letní semestr, volitelný
obor MIS , 0 ročník, letní semestr, volitelný
obor MMI , 0 ročník, letní semestr, volitelný
obor MMM , 0 ročník, letní semestr, povinný
obor MPV , 0 ročník, letní semestr, volitelný
obor MSK , 1 ročník, letní semestr, povinně volitelný
obor MGM , 0 ročník, letní semestr, volitelný