Matematická logika

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Studenti se naučí logicky analyzovat text a rozumět mu, převést jednodušší texty do formálního zápisu. Budou umět rozhodnout o platnosti logických formulí a dokázat je. Porozumí rozdílu mezi syntaxí a sémantikou formální logiky, budou schopni pracovat s axiomatickými systémy a znát jejich základní matematické vlastnosti. Zvládnou Booleovu algebru, jak teoreticky jako formální systém a instanci univerzální algebry, tak prakticky jako nástroj sloužící k popisu číslicových systémů. Získají potřebné návyky pro práci s Booleovskými funkcemi, normálními formami, mapami a metodami minimalizace, které budou potřebovat v dalších předmětech. Své znalosti budou mít zasazeny do širšího historického kontextu.

Požadavky:

Předpokládá se schopnost práce s matematickou abstrakcí na úrovni získané středoškolským studiem matematiky.

Osnova přednášek:

1. Význam logiky, historie. Výroková logika. Formalizace přirozeného jazyka. Základní pojmy: jazyk, formule. Sémantika VL: ohodnocení, pravdivostní tabulky. Tautologie, kontradikce, splnitelnost, tautologický důsledek, základní zákony VL.

2. Disjunktivní a konjunktní normální tvar formulí, rozkladové stromy. Logický rozbor textu. Booleova algebra. Minimalizace logické funkce. Mapy.

3. Syntax VL: Hilbertův axiomatický systém. Formální důkaz, typy matematických důkazů. Věta o dedukci. Korektnost a úplnost. Věta o kompaktnosti.

4. Predikátová logika. Formalizace přirozeného jazyka. Základní pojmy: jazyk, kvantifikátory, termy, formule. Sémantika PL: Tarskiho definice pravdy. Platnost formulí, logicky ekvivalentní formule, základní zákony PL.

5. Interpretace, model, teorie. Rozkladové stromy. Příklady modelů a teorií.

6. Logický rozbor textu. Prenexní tvar formulí. Syntax PL: Hilbertův axiomatický systém. Korektnost a úplnost.

7. Základní myšlenky teorie množin: aktuální a potenciální nekonečno, význam množin, mohutnosti, hypotéza kontinua, axiom výběru, formální systémy, nezávislá tvrzení.

Osnova cvičení:

1. Formalizace jednoduchých textů ve VL. Pravdivostní tabulky. Určení tautologie, kontradikce, splnitelnosti, tautologického důsledku. Disjunktivní a konjunktní normální tvar formulí. Booleova algebra. Minimalizace, mapy. Rozkladové stromy. Logický rozbor textu. Tři typy logické splnitelnosti v PL. Důkazy v Hilbertově axiomatickém systému. Typy matematických důkazů.

2. Formalizace jednoduchých textů do PL. Interpretace, model, teorie. Rozkladové stromy. Prenexní tvar formulí. Logický rozbor textu. Příklady modelů a teorií. Korektnost, bezespornost a úplnost. Mohutnosti množin, vzájemně jednoznačná zobrazení.

Cíle studia:

Cílem předmětu je ukázat, proč je v matematice užitečné namísto přirozeného jazyka používat formule výrokového a predikátového kalkulu, jakým způsobem se formalizuje pojem pravdivosti a dokazatelnosti a jak se pracuje s axiomatickými systémy. Booleova algebra je předvedena jako příklad matematické teorie a zároveň jako nástroj sloužící popisu číslicových systémů, přitom se rovněž vyloží standardní postupy sloužící minimalizaci vyjádření Booleovských funkcí.

Studijní materiály:

M. Demlová, B. Pondělíček: „Matematická logika.“ ČVUT Praha, 1997.

J. Kolář, O. Štěpánková, M. Chytil: „Logika, algebry a grafy.“ SNTL Praha 1989.

V. Švejdar: „Logika - neúplnost, složitost a nutnost.“ Academia Praha, 2002.

A. Sochor: „Klasická matematická logika.“ Karolinum Praha, 2001.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-MLO/

Další informace:

https://courses.fit.cvut.cz/BI-MLO/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, kombi., 2015 - 2020 (povinný předmět programu)
• Bc. obor Bezpečnost a informační technologie, kombi., 2015 - 2019 (povinný předmět programu)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, kombi., 2015 - 2020 (povinný předmět programu)
• Bc. obor Bezpečnost a informační technologie, kombinovaná forma studia, 2020 (povinný předmět programu)