Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Matematická logika

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BIK-MLO Z,ZK 5 13KP+4KC česky
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ů:
Platnost dat k 9. 12. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet1445306.html